线性表 whl

一、顺序表可用一维数组实现

1、初步实现思路

　　假设数据类型为ElemType，存储100个元素的数组ElemType elem[100]；
　　顺序表还需要什么属性，怎样表示顺序表？
 将顺序表定义为：

顺序表定义 
1 typedef struct 
2 {
3     ElemType elem[MAXSIZE];//存储顺序表元素
4     int length; //元素数目，也称长度
5 }List;

1.1初始化

ListInit 
1 Status ListInit ( List &L )//初步实现——初始化
2 {  
3     L.length= 0 ;    
4     return OK ;   
5 }


1.2插入

　　在第i个元素之前插入一个新元素x，线性表长度增1
插入过程
　　将线性表L中的第i个至第n个元素后移一个位置
　　将结点x插入到结点第（i-1）个位置;
　　线性表长度加1;

ListInsert 
 1 Status ListInsert (List &L, int i, ElemType x)
 2 {
 3     int j ;
 4     if  ( i < 1 ||  ( i > L.length+1))  
 5         return  ERROR ;
 6     if  ( L.length >= MAX_SIZE)
 7     {
 8         printf("线性表溢出!\n");  
 9         return  ERROR ; 
10     }
11     /* i-1位置以后的所有结点后移  */
12     for  ( j=L.length-1; j>=i-1; --j )
13         L.elem[j+1] = L.elem[j];
14     L.elem[i-1]=x;    /* 在i-1位置插入结点 */
15     L.length++ ;
16     return  OK ;  
17 }

1.3初步实现的问题
　　线性表的长度是固定的，实际应用中受到很大限制
考虑问题：
　　1、表长是否可以实现动态调整
　　2、表长动态调整的情况下，如何实现内存的合理化管理

2、优化实现

优化后的定义方式为：

优化实现 
1 typedef struct 
2 {
3     ElemType *elem;   //存储顺序表元素
4    int length;        //元素数目
5    int size；         //当前存储容量
6 }List;

配合使用：

程序 
 1 #define  OK   1
 2 #define  ERROR   -1
 3 #define  MAX_SIZE  100
 4 typedef  int  Status ;
 5 typedef  int  ElemType ; 
 6 #define LIST_INIT_SIZE 100 //初始存储空间 
 7 #define LISTINCREMENT 10  //分配增量  
 8 typedef struct 
 9 {
10     ElemType *elem;   //存储顺序表元素
11    int length;        //元素数目
12    int size；         //当前存储容量
13 }List;
14 
15 
16 Status ListInit(List &L) 
17 {
18     L.elem= (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
19     if (!L.elem ) 
20         return ERROR;
21     L.length = 0;
22     L.size =  LIST_INIT_SIZE;
23     return OK;
24 }
25 Status ListInsert (List &L, int i ,ElemType x)
26 {
27     int j ;
28     ElemType *buffer; 
29     if  ( i<0 || i>L.length+1)   
30         return  ERROR ;
31     if  ( L.length >= L.size)
32     {  //当前空间已满，分配新空间   
33         buffer = (ElemType*)realloc(L.elem ,(L.size+LISTINCREMENT) * sizeof(ElemType)) ;
34         if ( buffer == NULL ) 
35             return ERROR;
36         L.elem = buffer;
37         L.size += LISTINCREMENT;
38     }
39     ……    //后续插入逻辑与初步实现相同
40 }
41 /*
42 原型：void *realloc( void *memblock, size_t size );　　
43 语法：指针名=（数据类型*）realloc（要改变内存大小的指针名，新的大小）。
44 新的大小一定要大于原来的大小不然的话会导致数据丢失！ 　　
45 
46 /*顺序表删除
47 将第i个元素删除，线性表长度减1
48 删除过程
49 将线性表L中的第i+1个至第n个元素依次向前移动一个位置
50 线性表长度减1
51 */
52 Status ListDelete ( List *L，int i )
53 {
54     int k;
55     if  (L->length==0)
56     {  
57         printf(“线性表L为空!\n”); 
58         return ERROR; 
59     } 
60     else if ( i<1||i>L->length ) 
61     {
62         printf(“要删除的数据元素不存在!\n”) ; 
63         return ERROR ; 
64     }
65     for ( k=i;  k<L->length; k++)//i位置以后的所有结点前移  
66         L->elem[k-1]=L->elem[k];
67     L->length--;  
68     return OK;
69 }
70 /*
71 在线性表 L= (a1，a2，…，an) 中查找值为x的第一个结点
72 查找过程
73 从起点开始顺序查找
74 */
75 Status  ListLocate(List *L，ElemType x)
76 {  
77     int  i; 
78     for ( i=0 ; i < L->length; i++) 
79         if ( L->Elem[i] == x ) 
80             return i; 
81     return 0;    
82 } 
83 Status  ListLocate(List *L，ElemType x，int (*compare)(ElemType,ElemType))
84 {  
85     int  i; 
86     for ( i=0 ; i < L->length; i++) 
87         if ( (*compare)( L->Elem[i], x) == 0 ) 
88             return i; 
89     return 0;    
90 }

补充：比较函数 compare( ElemType , ElemType )，前一个元素"大于"、"等于"或"小于"后一个元素时分别返回1，0或-1。

优点

　　逻辑上相邻的元素，物理上也相邻

　　可随机存取顺序表中的任一元素

缺点

　　插入和删除操作需要通过移动元素来实现，效率低

二、链式表

/*
二、线性表的链式表示与实现
1、线性表的链式存储结构
用一组任意的存储单元存放线性表的数据元素
每个节点由数据域和指针域组成
数据域存储数据元素信息
指针域存储后继元素的存储位置
通过指针域可将n个节点按其逻辑顺序链接在一起，称为链表
2、链表的特点
链表中结点，逻辑相邻不一定物理相邻
数据元素之间的逻辑关系由链表中的指针域指示，而节点在存储器中的存储位置时随意的
顺序存取，不能实现随机存取

3、带头结点的单链表
    每一个结点只包含一个指针域的链表，称为单链表
    为操作方便，一般会在链表的第一个结点之前附设一个头结点（头指针）head指向第一个结点，头结点的数据域可以不存储任何信息，也可或存储链表长度等信息
4、为何需要带头结点
    对于无头结点的链表被函数处理时，如果头结点发生移动，头指针即被改动，因此需要函数将更新后的头结点采用某种形式传回，增加了函数的负担，降低了通用性
    采用带有头结点的链表，则不必担心头指针被修改，解决了上述问题
*/
typedef struct LNode 
{
    ElemType data;        //结点的数据域
    struct LNode *next; //结点的指针域
}LNode,*LinkList;        //LinkList为指向结构体LNode的指针类型


//初始化带头结点单链表
//分配头结点空间
Status ListInit(LinkList &L)
{
    L=(LinkList)malloc(sizeof(LNode));//生成新结点作为头结点，用头指针L指向头结点
    L.next = NULL;//头结点的指针域置空
}

Status ListInsert(LinkList &L, int i, ElemType e) 
{  
    // 在带头结点的单链线性表L的第i个元素之前插入元素e
    LinkList  p, q;
    p = L;   
    int j = 0;
    while (p && j < i-1) 
    {  // 寻找第i-1个结点
        p = p->next;
        ++j;
    } 
    if (!p || j > i-1)
        return ERROR;      // i小于1或者大于表长
    q = (LinkList)malloc(sizeof(LNode));  // 生成新结点
    q->data = e; 
    q->next = p->next;      // 插入L中
    p->next = q;
    return OK;
} 
Status  ListDelete( LinkList &L, int i, ElemType &e) 
{
    //在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
    LinkList  p, q;
    p = L;
    int j = 0;
    while (p->next && j < i-1) 
    {  // 寻找第i个结点，并令p指向其前趋
        p = p->next;
        ++j; }
    if (!(p->next) || j > i-1) 
        return ERROR;  // 删除位置不合理
    q = p->next;
    p->next = q->next; // 删除并释放结点
    e = q->data;
    free(q);
    return OK;
} 

//获取指定结点数据
Status ListGetElem (LinkList &L, int i,  ElemType &e) 
{  
    // L为带头结点的单链表的头指针。当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
    LinkList  p;
    p = L->next;   
    int j = 1;           // 初始化，p指向第一个结点，j为计数器
    while (p && j<i) {   
        // 顺指针向后查找，直到p指向第i个元素或p为空
        p = p->next;  ++j;}
    if ( !p || j>i ) return ERROR;  // 第i个元素不存在
    e = p->data;   // 取第i个元素
    return OK;
} 
/*
链表的形态
单链表
循环链表
    最后一个结点的指针指向头结点，形成一个环
双向链表
    结点包含两个指针域，一个指向直接后继结点，一个指向直接前驱结点

链式存储结构的优缺点
优点
    结点空间可以动态申请和释放
    数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移动数据元素
缺点
    每个结点的指针域需要占用额外空间
    只能顺序访问，不能随机访问

顺序表 v.s. 链表
    顺序表基于数组实现；链表基于指针实现
    顺序表是一种随机存取结构，对表中任一结点都可以直接定位并存取；链表中的结点则需要从头结点开始顺链扫描
    若线性表的操作主要是查询，表建好后很少涉及插入、删除操作，宜采用顺序表结构；若要频繁进行插入、删除操作，则宜采用链表结构

*/
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/whl2012/p/2786261.html