数据结构之【线性表】（顺序表、链表的基本操作实现）

概念

线性表：是N个数据元素的有限序列。
顺序表：用一组地址连续的存储单元依次存储【线性表 】的数据元素。（区别于有序表：表中的数据元素存在非递增或非递减有序）
链表：用一组任意的存储单元来存储【线性表】的数据元素。

顺序表的声明：
0、顺序表的声明
顺序表的基本操作：
1、初始化顺序表L（InitList_Sq）
2、销毁顺序表L（DestroyList_Sq）
3、创建顺序表（Create_Sq）
4、清空顺序表（ClearList_Sq）
5、判断顺序表是否为空（ListEmpty_Sq）
6、求顺序表的长度（ListLength_Sq）
7、获取第i个数据元素的值（GetElem_Sq）
8、定位某元素e的位置（LocateElem_Sq）
9、求当前元素的直接前驱元素（PriorElem_Sq）
10、求当前元素的直接后继元素（NextElem_Sq）
11、向顺序表中插入新的元素e（ListInsert_Sq）
12、删除顺序表中第i个位置的元素（ListDelete_Sq）
13、遍历顺序表（ListTraverse_Sq）
顺序表的其他操作：
14、顺序表的就地逆置（Reverse）
15、合并顺序表（MergeList）
16、将顺序表非递减有序排序（折半插入排序）（Sort）
17、向有序表中插入元素（InsertOrderList）

(线性)链表的声明：
0、带头结点的线性链表的声明
(线性)链表的基本操作：
1、初始化顺序表L（MakeNode）
2、释放结点（FreeNode）
3、初始化链表L（InitList）
4、清空链表，并释放结点空间（DestroyList）
5、销毁链表L（ClearList）
6、在头结点后、首元结点前插入元素（InsFirst）
7、删除首元结点（DelFirst）
8、在链表尾部【追加】新的链表或结点（Append）
9、删除表尾结点（Remove）
10、在表中结点前【插入】一个新结点（InsBefore）
11、在表中结点后【插入】一个新结点（InsAfter）
12、更新某结点中数据元素的值（SetCurElem）
13、获取某结点中数据元素的值（GetCurElem）
14、判断链表是否为空（ListEmpty）
15、获取某链表的长度（ListLength）
16、返回头结点的位置（GetHead）
17、返回尾结点的位置（GetLast）
18、返回某结点的直接前驱结点的位置（PriorPos）
19、返回某结点的直接后继结点的位置（NextPos）
20、返回链表中第i个结点的位置（LocatePos）
21、返回表中与e满足compare()判定关系的元素的位置（LocateElem）
22、遍历链表（ListTraverse）
(线性)链表的其他操作：
23、逆位序创建带头结点的线性链表L（CreateList）
24、将线性链表按非递减有序排列（SortList）
25、往有序链表中插入元素e（OrderInsert）
26、合并链表（MergeList_L）
27、用【头插法】逆置单链表（ReverseList）

顺序表

------- 线性表的动态分配顺序存储结构 -------回顶部

//关键字宏定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW 0
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LISTINCREMENT 10   //线性表存储空间的分配增量
//关键字类型说明
typedef int ElemType;
typedef int Status;
//数据元素（顺序表）的类型说明
typedef struct SqList{ElemType *elem; //存储空间的基地址int length;     //当前长度int listsize;   //当前分配的存储容量，以sizeof(ElemType)为单位
}SqList;

------- 顺序表的基本操作 -------

1、初始化顺序表L ----回顶部

//先分配空间，再将数组长度置为0 
Status InitList_Sq(SqList &L){ //初始化一个线性表L.elem=(ElemType*)malloc((LIST_INIT_SIZE)*sizeof(ElemType));if(!L.elem) exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;
}//InitList_Sq

2、销毁顺序表L ----回顶部

void DestroyList_Sq(SqList &L){ //销毁一个线性表if(L.elem)free(L.elem);
}

3、创建顺序表 ----回顶部

//先输入线性表的长度，然后依次输入元素 
Status Create_Sq(SqList &L){ //创建一个顺序表printf("please input number:\n");scanf("%d",&L.length);	printf("please input keyvalue with enter:\n");for(int i=1;i<=L.length;i++)//subscript start from 1,方便排序  scanf("%d",&L.elem[i]);	return OK;
}

4、清空顺序表 ----回顶部

//将线性表的长度置为0 
Status  ClearList_Sq(SqList &L){L.length=0;return OK;
}

5、判断顺序表是否为空 ----回顶部

//通过判断线性表的长度来断定 
Status ListEmpty_Sq(SqList L){ //线性表判空if (L.length==0)return TRUE;      else return FALSE;
}

6、求顺序表的长度 ----回顶部

int ListLength_Sq(SqList L){ //求线性表长度return L.length;             
}

7、获取第i个数据元素的值 ----回顶部

int GetElem_Sq(SqList L,int i,ElemType &e){ //获取表中第i个位置的元素，用e返回if (i<1 || i>L.length){ //取元素的位置不合法printf("wrong position\n");return ERROR;   }e=L.elem[i];//数组元素下标从1开始       return OK;
}

8、定位某元素e的位置 ----回顶部

Status compare(ElemType x,ElemType y){ //两个数据元素比较大小if(x>y)return 1;elseif(x==y)  return 0;elsereturn -1;
}

int LocateElem_Sq(SqList L,ElemType e,Status (*compare)(ElemType x,ElemType y)){ //在表中定位元素eint i;for(i=1;i<=L.length;i++){if(!compare(e,L.elem[i]))return i;}print("未找到");return ERROR;
}

9、求当前元素的直接前驱元素 ----回顶部

//先判断当前元素是否存在并得到其位置，然后再判断 
int PriorElem_Sq(SqList L,ElemType cur_e,ElemType &pre_e){ //求当前元素的直接前驱元素int i=LocateElem_Sq(L,cur_e,compare);if(!i){printf("%d isn't in the list",cur_e);return ERROR;}if(i==1){printf("%d is the first elem,it hasn't prior.\n",cur_e);return ERROR;}pre_e=L.elem[i-1];return OK;
}

10、求当前元素的直接后继元素 ----回顶部

//先判断当前元素是否存在以及所在的位置，然后再求其后继元素 
Status NextElem_Sq(SqList L,ElemType cur_e,ElemType &next_e){ //求当前元素的直接后继元素int i;if( ListEmpty_Sq(L) && (i=LocateElem_Sq(L,cur_e，compare)) ){if(i!=L.length){next_e=L.elem[i+1];return OK;}else {printf("%d is the last elem,it hasn't next.\n",cur_e);return ERROR;}}else{printf("%d isn't in the list",cur_e);return ERROR;}
}

11、向顺序表中插入新的元素e ----回顶部

Status ListInsert_Sq(SqList &L,int i,ElemType e){ //将e插入到L的第i个位置之前，L长度加1if(i<1 || i>L.length+1){ //限制合法的插入位置printf("position is wrong\n");return ERROR;}int *p,*q;//临时指针int *newbase;//新的基地址if(L.length>=L.listsize){newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if (!newbase) //分配不成功exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}q = &(L.elem[i]);//顺序表在数组中的存储从1开始for(p = &(L.elem[L.length]); p>=q; --p)*(p+1) = *p; //寻找插入位置，移动元素*(q) = e;//完成插入L.length++;//线性表长度增1return OK;
}

12、删除顺序表中第i个位置的元素 ----回顶部

//先判断要删除的位置是否合法，然后将指向此元素的指针赋给另一个变量，再将后面的元素依次向前移动一位，长度-1 
Status ListDelete_Sq(SqList &L,int i,ElemType &e){ //删除第i个位置的元素，并用e返回被删除元素int *p,*q;if( i<1 || i>L.length){printf("position is wrong\n");return ERROR;}p = &(L.elem[i]);//因为从下标1开始存数据元素，位序与下标相同e = *p;q = L.elem + L.length;for(++p; p<=q; ++p)*(p-1) = *p;L.length--;return OK;
}

13、遍历顺序表 ----回顶部

//先判断线性表是否为空，若不空，则从头开始依次遍历，此处从1开始，是因为刚开始创建线性表时就从1开始的 
void ListTraverse_Sq(SqList L){//在屏幕上输出顺序表int i;if(ListEmpty_Sq(L)){printf("the Sqlist is empty!\n");return;}for(i=1; i<=L.length; i++){ //数组下标从1开始printf("%d ",L.elem[i]);	}printf("\n");
}

------- 顺序表的其它操作 -------

14、顺序表的就地逆置 ----回顶部

// 算法1
//顺序表的第一个元素与最后一个元素交换，然后指针依次加1减1，重复上述活动，直到两者相遇 
void Reverse1(SqList &L){ //顺序表的就地逆置printf("After reve:\n");int temp,i,j;for(i=1,j=L.length; i<=j; i++,j--){temp=L.elem[i];L.elem[i]=L.elem[j];L.elem[j]=temp;}
}//reverse 

// 算法2
void Reverse2(SqList &L){ //顺序表的就地逆置 printf("After reve:\n");int temp,i;for(i=1;i<=(L.length)/2;i++){temp=L.elem[i];L.elem[i]=L.elem[L.length+1-i];L.elem[L.length+1-i]=temp;}
}//reverse

15、合并顺序表 ----回顶部

//前提：La和Lb是非递减有序的
void MergeList(SqList La,SqList Lb,SqList &Lc){InitList_Sq(Lc); int *pa,*pb,*pc,*pa_last,*pb_last;pa = &(La.elem[1]);pb = &(Lb.elem[1]); //subscript start from 1Lc.length = ListLength_Sq(La)+ListLength_Sq(Lb);Lc.listsize = ListLength_Sq(La)+ListLength_Sq(Lb);pc = (ElemType *)malloc(Lc.listsize*sizeof(ElemType));pc = &(Lc.elem[1]);//subscript start from 1if(!Lc.elem) exit(OVERFLOW); //存储分配失败pa_last = &(La.elem[La.length]);pb_last = &(Lb.elem[Lb.length]);while((pa<=pa_last) && (pb<=pb_last)){if(*pa <= *pb)      *pc++ = *pa++;else*pc++ = *pb++;}while(pa<=pa_last)*pc++ = *pa++;while(pb<=pb_last)*pc++ = *pb++;
}//MergeList

16、将顺序表非递减有序排序（折半插入排序） ----回顶部

Status Sort(SqList &L){//折半插入排序int i,j,m,low,high;for(i=2;i<=L.length;++i){ L.elem[0]=L.elem[i];low=1; high=i-1;	while(low<=high){     m=(low+high)/2;             if(L.elem[0]<L.elem[m]) high=m-1;else  low=m+1; }//whilefor(j=i-1;j>=high+1;--j)L.elem[j+1] = L.elem[j];			L.elem[high+1]= L.elem[0];  }//forreturn OK;
}  

17、向有序表中插入元素 ----回顶部

// 算法1
Status InsertOrderList1(SqList &L,ElemType x){//将x插入到递增有序的顺序表L中，插入后L仍然递增有序(算法1)int *p;//临时指针int *newbase;//新的基地址if(L.length >= L.listsize){newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if (!newbase) //分配不成功exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}p = &(L.elem[L.length]); //下标从1开始while(p>=&(L.elem[1]) && *p>x){ //寻找插入位置，移动元素*(p+1)=*p; --p;}*(p+1) = x;//完成插入L.length++;//线性表长度增1return OK;
}

//算法2
Status InsertOrderList2(SqList &L,ElemType x){ //将x插入到递增有序的顺序表L中，插入后L仍然递增有序(算法2)printf("After algo2:\n");int *newbase;if(L.length >= L.listsize){newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if (!newbase) exit(OVERFLOW);L.elem = newbase;L.listsize += LISTINCREMENT;}int i = L.length;//数组下标从1开始while((i >= 1) && (x<L.elem[i]))i--;//i是插入位置int j;for(j=L.length; j>=i+1/*是在插入位置之后插入元素*/; j--){L.elem[j+1]=L.elem[j];//从第i+1到第n个元素后移}L.elem[i+1] = x;//插入L.length++;//长度增1return OK;
}

//算法3
Status InsertOrderList3(SqList &L,int x){//将x插入到递增有序的顺序表L中，插入后L仍然递增有序(算法3)int i;i=L.length;//数组下标从1开始while((i>=1) && (x<L.elem[i]))i--; //查找i是插入位置ListInsert_Sq(L,(i+1),x);return OK;
}

//算法4
Status InsertOrderList4(SqList &L,int x)//将x插入到递增有序的顺序表L中，插入后L仍然递增有序(算法4)
{int i;i=1;//数组下标从1开始while((i<=L.length) && (x>L.elem[i]))i++; //查找i是插入位置printf("i is  %d",i);ListInsert_Sq(L,i,x);//插在第i个元素之前，所以直接调用return OK;
}

（线性)链表

------- 线性表的【线性链表】存储结构 -------回顶部

//关键字宏定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW 0
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LISTINCREMENT 10   //线性表存储空间的分配增量
//关键字类型说明
typedef int ElemType;
typedef int Status;
//数据元素（带头结点的线性链表）的类型说明
typedef struct LNode{ //结点类型ElemType data;struct LNode *next;
}*Link,*Position;
typedef struct{ //链表类型Link head,tail; //分别指向线性链表中的头结点和最后一个结点int len;        //指示线性链表中数据元素的个数
}LinkList;

------- 线性链表的基本操作 -------
1、构造结点-MakeNode ----回顶部

 //构造一个结点，给结点分配空间并指明数据域和指针域 
Status MakeNode(Link &p,ElemType e){//分配由p指向的值为e的结点，并返回OK，若分配失败，返回ERRORp=(Link)malloc(sizeof(LNode));if(p){p->data=e;p->next=NULL;return OK;}elsereturn ERROR;
}//MakeNode

2、释放结点 ----回顶部

Status FreeNode(Link &p){//释放p所指结点if(p)free(p);return OK;
}

3、初始化链表L ----回顶部

Status InitList(LinkList  &L){//构造一个空链表LL.head=(Link)malloc(sizeof(LNode));if(L.head){L.head->next=NULL;L.tail=L.head;L.len=0;return OK;}else return ERROR;
}

4、清空链表，并释放结点空间 ----回顶部

//逐步释放链表的结点，并将链表的长度每次减1，直到头尾结点相等，且长度为0 
Status ClearList(LinkList &L){//重置L为空表，并释放原链表的结点空间Link p,q;if(L.head!=L.tail){p=L.head->next;L.head->next=NULL;while(p!=L.tail){q=p->next;free(p);p=q;}free(p);L.tail=L.head;L.len=0;}if(L.head == L.tail )return OK;return ERROR;
}

5、销毁链表L ----回顶部

//先清空链表，然后释放头尾结点 
Status DestroyList(LinkList &L){//销毁链表，L不再存在ClearList(L);FreeNode(L.head);return OK;
}

6、在头结点后、首元结点前插入元素 ----回顶部

//将新节点插入到头节点的后面（若原来为空链表，则直接连接到头节点后面），并将长度加1 
Status InsFirst(LinkList &L,Link h,Link s){//已知 h指向L的头结点//在L的头部插入s为新首元结点s->next=h->next;h->next=s;if(h==L.tail)//原来是空表L.tail=h->next;L.len++;return OK;
}

7、删除首元结点 ----回顶部

//删除首元结点，直接将首元结点的下一个结点连接到头节点处，并释放原首元结点 
Status DelFirst(LinkList &L,Link h,Link &q){//已知 h指向L的头结点q = h->next;if(q){h->next = q->next;if(!h->next)//删除q后为空表L.tail = h;L.len--;free(q);return OK;}else return ERROR;
}

8、在链表尾部【追加】新的链表或结点 ----回顶部

//直接将要链接的结点连接到尾结点上，并指明新的尾结点，且链表长度要改变。 
Status Append(LinkList &L,Link s){//将指针s所指的一串结点链接在线性链表L的最后一个结点后。int i = 1;L.tail->next = s;while(s->next){s = s->next;i++;}L.tail = s;//改变L的为指针指向新的尾元结点L.len += i;return OK;
}

9、删除表尾结点 ----回顶部

//先判断链表是否为空，若不空，则从头节点开始依次查找直到尾结点的前驱结点，将其指定为新对的尾结点，并删除释放原尾结点，长度-1 
Status Remove(LinkList &L,Link &q){//删除线性链表L中的尾结点并将q返回，改变链表L的尾指针指向新的尾节点。Link p;if(L.len == 0){q = NULL;return FALSE;}p = L.head->next;q = L.tail;while(p->next != q)p = p->next;L.tail = p;p->next = NULL;FreeNode(q);return OK;
}

10、在表中某结点前【插入】一个新结点 ----回顶部

//从头节点开始查找，直到要插入结点的前驱结点，然后插入 
Status InsBefore(LinkList &L,Link &p,Link s) {//在L中p结点前插入s,并修改指针p指向新插入的结点Link q;q = L.head;while(q && q->next && q->next!=p)q = q->next;s->next = q->next;q->next=s;p = s;L.len++;return OK;
}

11、在表中某结点后【插入】一个新结点 ----回顶部

//已知要插入的结点，直接在结点后面插入即可 
Status InsAfter(LinkList &L,Link &p,Link s){ //在L中p结点后插入s,并修改指针p指向新插入的结点if(p->next){s->next = p->next;p->next = s;}else{p->next = s;L.tail = s; }p = s;L.len++;return OK;
}

12、更新某结点中数据元素的值 ----回顶部

Status SetCurElem(Link p,ElemType e){//用e更新p所指结点的元素值。p->data = e;return OK;
}

13、获取某结点中数据元素的值 ----回顶部

ElemType GetCurElem(Link p){//返回p所指结点的元素值return p->data;
}

14、判断链表是否为空 ----回顶部

Status ListEmpty(LinkList L) {//若L空，返回TRUE,否则返回FALSEif (L.head->next == NULL) return TRUE;else return FALSE;
}

15、获取某链表的长度 ----回顶部

int ListLength(LinkList L){//求L的长度return L.len;
}

16、返回头结点的位置 ----回顶部

Position GetHead(LinkList L){//返回L的头结点的位置。return L.head;
}

17、返回尾结点的位置 ----回顶部

Position GetTail(LinkList L){//返回L的尾元结点的位置。return L.tail;
}

18、返回某结点的直接前驱结点的位置 ----回顶部

//从头节点开始查找，直到该结点的前驱结点 
Position PriorPos(LinkList L,Link p){//p是L的一个结点，返回p的直接前驱的位置，如果无前驱，返回NULL。Link q;q = L.head->next;if(q==p){printf("It's the first element,no prior!\n");return NULL;}while(q && q->next!=p)q = q->next;return q;
}

19、返回某结点的直接后继结点的位置 ----回顶部

Position NextPos(LinkList L,Link p){//p是L的一个结点，返回p的直接后继的位置，如果无后继，返回NULL。if(p->next)return p->next;else{printf("It's the last element,no next!\n");return NULL;}
}

20、返回链表中第i个结点的位置 ----回顶部

//先检查位置是否合法，然后从头开始查找，并计数，直到找到 
Status LocatePos(LinkList L,int i,Link &p){//返回L中第i个结点的位置，用p表示，i不合法时返回ERROR;if(i<0 || i>ListLength(L))return ERROR;int j = 1; //不算头结点，从首元结点开始 p = L.head->next;while(p && j<i){j++;p = p->next;}return OK;
}

21、返回表中与e满足compare()判定关系的元素的位置 ----回顶部

int compare(ElemType x,ElemType y)
{if(x>y)return 1;elseif(x == y)  return 0;elsereturn -1;
}

Position LocateELem(LinkList L,ElemType e,int(*compare)(int,int)){//L中第1个与e满足compare判定关系的元素的位置，若不存在这样的元素，则返回NULL。LNode *p;p = L.head->next;while(p){if(!compare(e,p->data))return p;p = p->next;}if(!p){printf("the element is not exists\n");return NULL;}
}

22、遍历链表 ----回顶部

//访问某结点元素
Status visit(Link p){if(p){	printf("%d->",p->data);return OK;}elsereturn ERROR;
}

void ListTraverse(LinkList L,Status(*visit)(Link p)){//依次对L中的每个元素调用函数visit，一旦visit失败，则操作失败Link p;p = L.head->next;//不带表头的输出while(p != NULL){visit(p);p = p->next;}printf("\n");
}

------- 线性链表的其它操作 -------

23、逆位序创建带头结点的线性链表L ----回顶部

Status CreateList(LinkList &L){ //逆位序创建一个带头结点的空单链表    int i;printf("input Length:");scanf("%d",&L.len);Link p;printf("input value with descend order!\n");for(i=L.len; i>0; --i){p = (Link)malloc(sizeof(LNode));scanf("%d",&p->data);p->next = L.head->next;L.head->next = p;   //头结点的指针永远指向最新的那一个结点 }p = L.head->next;while(p->next){p = p->next;}L.tail = p;return OK;
}

24、将线性链表按非递减有序排列 ----回顶部

void SortList(LinkList &L){//由低到高 Link p,q,r;ElemType t;for(p=L.head->next; p->next!=NULL; p=p->next){r = p;//第一个结点的 指针 for(q=p->next; q!=NULL; q=q->next){if(q->data < r->data)r = q;}if(r != p){t = r->data;r->data = p->data;p->data = t;}}
}

25、往有序链表中插入元素e ----回顶部

Status OrderInsert(LinkList &L,ElemType e,int (*compare)(ElemType,ElemType)){ // 已知L为有序线性链表，将元素e按非降序插入在L中。（用于一元多项式）Link s,p,q;q = L.head;p = q->next;while(p!=NULL && compare(p->data,e)<0){// p不是表尾且元素值小于eq = p;p = p->next;}s = (Link)malloc(sizeof(LNode)); // 生成结点s->data = e; // 赋值q->next = s; // 插入s->next = p;L.len++; // 表长加1if(!p) // 插在表尾L.tail = s; // 修改尾结点return OK;
}

26、合并链表 ----回顶部

Status MergeList_L(LinkList La,LinkList Lb,LinkList &Lc){Link ha,hb,pa,pb,q;ElemType a,b;if(!InitList(Lc))return ERROR;ha = GetHead(La);hb = GetHead(Lb); //ha、hb分别指向 La、Lb的头结点pa = NextPos(La,ha);pb = NextPos(Lb,hb);//初始时刻 pa、pb分别指向La、Lb的首元结点while(pa && pb){a = GetCurElem(pa);b = GetCurElem(pb); //a、b分别是当前结点的值if((*compare)(a,b)<=0){ //当 a <= b时DelFirst(La,ha,q);  //删除 La的首元结点InsFirst(Lc,Lc.tail,q); //注意，此处为将q插入Lc的尾部pa = NextPos(La,ha); //pa指向La新的首元结点}else{DelFirst(La,hb,q);InsFirst(Lc,Lc.tail,q);pb = NextPos(Lb,hb);}}if(pa)Append(Lc,pa);elseAppend(Lc,pb);FreeNode(ha);FreeNode(hb);return OK;
}

27、用【头插法】逆置单链表 ----回顶部

//逆置单链表 （用头插法） 
void ReverseList(LinkList &L){LNode *p,*q;p = L.head->next;L.head->next = NULL;while(p!=NULL){q = p->next;p->next = L.head->next;L.head->next = p;p = q;}
}

参考文献：
[1] 严蔚敏，吴伟民 ，《数据结构（C语言版）》.
[2] 程杰，《大话数据结构》，清华大学出版社，2011出版年.
[2] 明日科技，《C语言 从入门到精通》，清华大学出版社，2019年版