数据结构之线性表（顺序表、单双向链表）

一、顺序表

（一）顺序表的结构

可以将顺序表看作是一种结构体，该结构体中的成员有一个数组（用于存储数据）和两个变量（表示数组的实际长度与最大长度），但具体的成员设计有多种方式。

#define ElemType int #define LIST_INIT_SIZE 100 //列表初始元素个数 #define LISTINCREMENT 10 typedef struct{ //一个顺序表结构体 ElemType *elem; //元素值（数组） int length; //顺序表的实际长度 int listsize; //顺序表的最大长度 }SqList;

（二）初始化顺序表

初始化顺序表，首先要申请定长的内存（用malloc/calloc），大小=元素个数（自己定义的初始个数）*类型大小；申请后需要判空避免发生溢出申请失败；申请成功后更新实际元素个数和最大个数。

注意：传入参数必须是结构体的指针，才能申请空间修改其值可进行初始化。

//初始化顺序表 int InitList_Sq(SqList *L){ //分配内存空间，列表初始元素个数*每个元素的类型大小 L->elem=(ElemType *)calloc(LIST_INIT_SIZE,sizeof(ElemType)); if(L->elem==NULL) return OVERFLOW; //分配失败，返回溢出错误 L->length=0; //初始化当前元素个数为0 L->listsize=LIST_INIT_SIZE; //初始化最大元素个数 return OK; }

（三）在顺序表中添加元素

int AddElem_Sq(SqList *L,ElemType *values,int count)

参数：需要添加元素的顺序表（传指针，修改值），需要添加的元素数组values和元素个数count。

思路：

• 检查参数是否合法（传入的顺序表？数组？数量？）；
• 判断顺序表是否需要扩容，可以使用循环每次扩容的大小固定：使用临时变量进行扩容（不用顺序表直接扩容，防止扩容失败导致原来的数据丢失）并判空，扩容成功后再更新顺序表。
• 利用循环逐个添加元素（从原原顺序表元素结尾开始），并更新实际元素个数length。

//添加元素 int AddElem_Sq(SqList *L,ElemType *values,int count){ if(L==NULL || values==NULL || count<=0) return ERROR; //检查参数 while(L->length+count > L->listsize){//如果需要添加的元素个数>顺序表的最大长度，则需要对顺序表进行扩容 //使用临时变量，防止realloc失败导致数据丢失 ElemType *newElem=(ElemType *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType)); if(newElem==NULL) return OVERFLOW; L->elem=newElem; //更新最大长度 L->listsize+=LISTINCREMENT; } //逐个添加元素 for(int i=0;i<count;i++){ L->elem[L->length+i]=values[i]; } L->length+=count; return OK; }

（四）插入元素

int ListInsert_Sq(SqList *L,int i,ElemType e)

参数：需要添加元素的顺序表（传指针，修改值），需要插入的位置i，待插入元素e。

思路：

• 先检查参数是否合法；
• 再判断是否需要扩容（与添加元素中的扩容方法一致）；
• 利用指针定位到需要插入的位置，从后向前使用循环依次向后覆盖，空出第i个位置赋值e，并更新顺序表的实际元素个数。

//插入元素 int ListInsert_Sq(SqList *L,int i,ElemType e){ if(i<1 || i>L->length+1) return ERROR; //如果顺序表满了则需要扩容重新分配空间 if(L->length >= L->listsize){ //重新分配空间 ElemType *newbase=(ElemType *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase) exit(OVERFLOW); //分配成功则更新顺序表的基地址与最大长度 L->elem=newbase; L->listsize+=LISTINCREMENT; } //定位需要插入的位置 ElemType *q=L->elem+i-1; //从后往前以此向后覆盖空出第i位 for(ElemType *p=L->elem+L->length-1;p >= q;--p){ *(p+1)=*p; } *q=e; //插入第i位 ++L->length; //更新顺序表长度 return OK; }

（五）删除元素

int ListDelete_Sq(SqList *L,int i,ElemType *e)

参数：需要添加元素的顺序表（传指针，修改值），需要删除元素的位置i，e存放删除元素。

思路：先检查参数；然后定位到需要删除的元素的位置，用参数e暂存删除的元素值，使用循环将待删除元素的后一个元素向前覆盖待删元素，直到顺序表的最后一个元素，最后更新实际元素个数。

//删除元素 int ListDelete_Sq(SqList *L,int i,ElemType *e){ if(i<1 || i>L->length) return ERROR; ElemType *p=L->elem+i-1; //定位需要删除元素的位置 *e=*p; // 保留需要删除的元素值 ElemType *q=L->elem+L->length-1; for(++p;p <= q;++p){ *(p-1)=*p; } --L->length; //更新长度 return OK; }

（六）有序顺序表的合并

void MergeList_Sq(SqList *La,SqList *Lb,SqList *Lc)

参数：两个有序顺序表La,Lb，合并的结果放在顺序表Lc。

思路：

• 定义两个指针pa和pb，分别从两个表的开头开始遍历；再定义两个指针pa_last,pb_last，用于表示两个顺序表的边界，判断是否遍历完。
• 动态分配足够的内存空间给合并顺序表Lc，总容量为两个表容量之和，实际元素个数为两个表长度之和。
• 循环遍历两个有序顺序表，每次比较pa和pb对应的元素，如果pa的元素更小，将它放入lc，然后后移pa与pc，反之则将pb的元素放入Lc并后移pb与pc。
• 当其中一个表遍历完，另一个表可能还有剩余元素，直接将剩余元素依次放入Lc（因为两个表本身有序，剩余元素一定都大于已放入的元素）。

//顺序表的合并 void MergeList_Sq(SqList *La,SqList *Lb,SqList *Lc){ ElemType *pa,*pb,*pc; ElemType *pa_last,*pb_last; pa=La->elem; pb=Lb->elem; Lc->listsize=La->listsize+Lb->listsize; //更新合并顺序表的最大元素个数 Lc->length=La->length+Lb->length; //更新合并顺序表的实际元素个数 Lc->elem=(ElemType *)malloc(Lc->listsize*sizeof(ElemType)); //申请空间 if(!Lc->elem) return OVERFLOW; pc=Lc->elem; pa_last=La->elem+La->length-1; //设定La边界 pb_last=Lb->elem+Lb->length-1; //设定Lb边界 while(pa<=pa_last && pb<=pb_last){ //循环遍历两个有序顺序表并比较对应元素值 if(*pa<*pb){ //将较小元素值更新到顺序表Lc *pc++=*pa++; }else{ *pc++=*pb++; } } while(pa<=pa_last) *pc++=*pa++; //将La剩余元素更新到合并顺序表Lc while(pb<=pb_last) *pc++=*pb++; //将Lb剩余元素更新到合并顺序表Lc }

顺序表测试全部代码：

#include <stdio.h> #include <stdlib.h> #define OVERFLOW 0 #define ERROR 0 #define OK 1 #define ElemType int #define LIST_INIT_SIZE 100 //列表初始元素个数 #define LISTINCREMENT 10 typedef struct{ //一个顺序表结构体 ElemType *elem; //元素值（数组） int length; //顺序表的实际长度 int listsize; //顺序表的最大长度 }SqList; //初始化顺序表 int InitList_Sq(SqList *L){ //分配内存空间，列表初始元素个数*每个元素的类型大小 L->elem=(ElemType *)calloc(LIST_INIT_SIZE,sizeof(ElemType)); if(L->elem==NULL) return OVERFLOW; //分配失败，返回溢出错误 L->length=0; //初始化当前元素个数为0 L->listsize=LIST_INIT_SIZE; //初始化最大元素个数 return OK; } //添加元素 int AddElem_Sq(SqList *L,ElemType *values,int count){ if(L==NULL || values==NULL || count<=0) return ERROR; //检查参数 while(L->length+count > L->listsize){//如果需要添加的元素个数>顺序表的最大长度，则需要对顺序表进行扩容 //使用临时变量，防止realloc失败导致数据丢失 ElemType *newElem=(ElemType *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType)); if(newElem==NULL) return OVERFLOW; L->elem=newElem; //更新最大长度 L->listsize+=LISTINCREMENT; } //逐个添加元素 for(int i=0;i<count;i++){ L->elem[L->length+i]=values[i]; } L->length+=count; return OK; } //插入元素 int ListInsert_Sq(SqList *L,int i,ElemType e){ if(i<1 || i>L->length+1) return ERROR; //如果顺序表满了则需要扩容重新分配空间 if(L->length >= L->listsize){ //重新分配空间 ElemType *newbase=(ElemType *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase) exit(OVERFLOW); //分配成功则更新顺序表的基地址与最大长度 L->elem=newbase; L->listsize+=LISTINCREMENT; } //定位需要插入的位置 ElemType *q=L->elem+i-1; //从后往前以此向后覆盖空出第i位 for(ElemType *p=L->elem+L->length-1;p >= q;--p){ *(p+1)=*p; } *q=e; //插入第i位 ++L->length; //更新顺序表长度 return OK; } //删除元素 int ListDelete_Sq(SqList *L,int i,ElemType *e){ if(i<1 || i>L->length) return ERROR; ElemType *p=L->elem+i-1; //定位需要删除元素的位置 *e=*p; // 保留需要删除的元素值 ElemType *q=L->elem+L->length-1; for(++p;p <= q;++p){ *(p-1)=*p; } --L->length; //更新长度 return OK; } //顺序表的合并 void MergeList_Sq(SqList *La,SqList *Lb,SqList *Lc){ ElemType *pa,*pb,*pc; ElemType *pa_last,*pb_last; pa=La->elem; pb=Lb->elem; Lc->listsize=La->listsize+Lb->listsize; //更新合并顺序表的最大元素个数 Lc->length=La->length+Lb->length; //更新合并顺序表的实际元素个数 Lc->elem=(ElemType *)malloc(Lc->listsize*sizeof(ElemType)); //申请空间 if(!Lc->elem) exit(OVERFLOW); pc=Lc->elem; pa_last=La->elem+La->length-1; //设定La边界 pb_last=Lb->elem+Lb->length-1; //设定Lb边界 while(pa<=pa_last && pb<=pb_last){ //循环遍历两个有序顺序表并比较对应元素值 if(*pa<*pb){ //将较小元素值更新到顺序表Lc *pc++=*pa++; }else{ *pc++=*pb++; } } while(pa<=pa_last) *pc++=*pa++; //将La剩余元素更新到合并顺序表Lc while(pb<=pb_last) *pc++=*pb++; //将Lb剩余元素更新到合并顺序表Lc } int main(){ SqList List; InitList_Sq(&List); ElemType values[]={10,20,30,40,50}; int count=sizeof(values)/sizeof(values[0]); AddElem_Sq(&List,values,count); for(int i=0;i<List.length;i++){ printf("%d ",List.elem[i]); } printf("\n"); ElemType x=25; ListInsert_Sq(&List,3,x); for(int i=0;i<List.length;i++){ printf("%d ",List.elem[i]); } printf("\n"); ElemType e=0; ListDelete_Sq(&List,3,&e); for(int i=0;i<List.length;i++){ printf("%d ",List.elem[i]); } SqList List1,List2,List3; InitList_Sq(&List1); InitList_Sq(&List2); ElemType values1[]={11,21,31,41,51}; ElemType values2[]={12,22,32,42,52}; int count1=sizeof(values1)/sizeof(values1[0]); int count2=sizeof(values2)/sizeof(values2[0]); AddElem_Sq(&List1,values1,count1); AddElem_Sq(&List2,values2,count2); MergeList_Sq(&List1,&List2,&List3); printf("\n"); for(int i=0;i<List3.length;i++){ printf("%d ",List3.elem[i]); } return 0; }

二、单链表

（一）单链表结构

单链表有很多个结构体（结点）组成，每个结构体有数据域（变量，存放数据）和指针域（指针，存放下一个结构体的地址）。

#define ElemType int typedef struct LNode{ ElemType data; struct LNode *next; //LNode为结点，LinkList为指向结点的指针 }LNode,*LinkList;

（二）创建链表

先创建头结点（只作为链表的起始，不存储数据）并初始化为NULL，需要使用二级指针（因为要在函数内修改外部的指针变量）。

• 尾插法：定义尾指针tail并初始化为头结点，表示当前链表的尾部，用于从前往后添加结点。使用循环，为新元素申请分配空间，并提示从键盘输入新结点元素值。将链表的尾结点的next指向新建结点tail->next = p，并更新尾指针tail = p。
• 前插法：不需要额外定义指针，直接使用头结点（每次在头结点插入新节点）。使用循环，为新元素申请分配空间，并提示从键盘输入新结点元素值。将新结点的next指向第一个元素（头结点的后继）p->next=(*L)->next，再将头结点的next指向新结点(*L)->next=p。（这两步顺序不能改变，如果改变会导致数据丢失）

注意：使用头插法，输入元素的顺序与实际链表中元素的顺序相反。尾插法顺序一致。

//创建链表：头插法+尾插法 int CreateList_L(LinkList *L,int n){ //创建一个链表（指针），L指向头结点 //L为二级指针：指向LinkList，LinkList指向LNode //所以*L为指向LNode *L=(LinkList)malloc(sizeof(LNode)); if(*L==NULL){ //*L为指针指向头结点 printf("Memory allocation failed!\n"); return ERROR; } //初始化链表为空链表 (*L)->next=NULL; LNode *tail=*L; //尾指针 //创建链表，插入n个元素 for(int i=0;i<n;i++){ //创建新结点，p为指针指向新结点 LNode *p=(LNode *)malloc(sizeof(LNode)); if(p==NULL){ printf("Memory allocation failed!\n"); return ERROR; } //printf("请输入第%d个元素：",n-i); //头插法：逆序插入 printf("请输入第%d个元素：",i+1); //尾插法：顺序插入 scanf("%d",&p->data); p->next=NULL; tail->next=p; //尾插法:使用尾指针从前往后链接 tail=p; // p->next=(*L)->next; //头插法：先链接后面再链接前面 // (*L)->next=p; } return OK; }

（三）插入结点

定义一个指针p使用循环用于定位需要插入位置的前驱（如在第一个位置插入则p指向头结点，在头结点后面插入结点），定位后需要检查是否遍历到链表尾部或位置的合法性。创建新结点并赋值，先链接后面（将新结点的next指向原链表中第i个结点s->next = p->next），再链接后面（更新第i-1个结点的next指向新结点p->next = s）。

//在第i个位置插入结点 int ListInsert_L(LinkList *L,int i,ElemType e){ LinkList p=*L; int j=0; while(p && j<i-1){ //定位到需要插入的地方 p=p->next; ++j; } //遍历到链表尾或i值非法（为0/负值） if(!p || j>i-1) return ERROR; //创建新结点 LinkList s=(LinkList)malloc(sizeof(LNode)); if(!s) return ERROR; s->data=e; s->next=p->next; //先链接后面再链接前面 p->next=s; return OK; }

（四）查找结点

定义一个指针p使用循环用于定位需要查找结点的位置（如需要查找第i个位置的结点元素），将其数据域的元素存入e。

//查找第i个结点，并存入e int GetElem_L(LinkList L,int i,ElemType *e){ LinkList p=L->next; int j=0; while(p && j<i-1){ p=p->next; ++j; } if(!p || j>i) return ERROR; *e=p->data; return OK; }

（五）删除结点

定义一个指针p使用循环用于定位需要删除结点的前驱（如需要删除第i个结点则定位到第i-1个结点），然后用指针q指向待删结点q=p->next，将其数据域存入e中q=p->next，最后修改指针跳过直接指向q的后继结点 p->next=q->next，并释放删除结点的内存 free(q)。

//删除第i个结点并将其存入e int ListDelete_L(LinkList *L,int i,ElemType *e){ LinkList q,p=*L;//p为待删元素的前驱 int j=0; while(p && j<i-1){ 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; }

（六）合并有序链表（原地操作）

La与Lb为待合并的有序链表，Lc指向La（将Lb合并（插入）到链表La上）。利用循环使pa与pb分别遍历La与Lb比较对应的结点数据域，每次将较小的结点连接到pc后面pc->next=pa;并更新其指向 pc=pa、pa=pa->next。循环结束后将剩余链表链接到pc后面，最后释放Lb的头结点并置空。

//合并有序链表 void MergeList_L(LinkList *La,LinkList *Lb,LinkList *Lc){ LinkList pa=(*La)->next; LinkList pb=(*Lb)->next; LinkList pc; *Lc=*La; //在La上合并 pc=*La; //以指针pc进行遍历合并 while(pa && pb){ if(pa->data <= pb->data){ pc->next=pa; //先链接后移动 pc=pa; pa=pa->next; }else{ pc->next=pb; pc=pb; pb=pb->next; } } pc->next=pa?pa:pb; //链接剩余链表 free(*Lb);//释放Lb *Lb=NULL;//防止野指针 }

单链表测试完整代码：

#include <stdio.h> #include <stdlib.h> #define ElemType int #define ERROR 0 #define OK 1 //结点 typedef struct LNode{ ElemType data; struct LNode *next; //LNode为结点，LinkList为指向结点的指针 }LNode,*LinkList; //创建链表：头插法+尾插法 int CreateList_L(LinkList *L,int n){ //创建一个链表（指针），L指向头结点 //L为二级指针：指向LinkList，LinkList指向LNode //所以*L为指向LNode *L=(LinkList)malloc(sizeof(LNode)); if(*L==NULL){ //*L为指针指向头结点 printf("Memory allocation failed!\n"); return ERROR; } //初始化链表为空链表 (*L)->next=NULL; LNode *tail=*L; //尾指针 //创建链表，插入n个元素 for(int i=0;i<n;i++){ //创建新结点，p为指针指向新结点 LNode *p=(LNode *)malloc(sizeof(LNode)); if(p==NULL){ printf("Memory allocation failed!\n"); return ERROR; } //printf("请输入第%d个元素：",n-i); //头插法：逆序插入 printf("请输入第%d个元素：",i+1); //尾插法：顺序插入 scanf("%d",&p->data); p->next=NULL; tail->next=p; //尾插法:使用尾指针从前往后链接 tail=p; // p->next=(*L)->next; //头插法：先链接后面再链接前面 // (*L)->next=p; } return OK; } //在第i个位置插入结点 int ListInsert_L(LinkList *L,int i,ElemType e){ LinkList p=*L; int j=0; while(p && j<i-1){ //定位到需要插入的地方 p=p->next; ++j; } //遍历到链表尾或i值非法（为0/负值） if(!p || j>i-1) return ERROR; //创建新结点 LinkList s=(LinkList)malloc(sizeof(LNode)); if(!s) return ERROR; s->data=e; s->next=p->next; //先链接后面再链接前面 p->next=s; return OK; } //查找第i个结点，并存入e int GetElem_L(LinkList L,int i,ElemType *e){ LinkList p=L->next; int j=0; while(p && j<i-1){ p=p->next; ++j; } if(!p || j>i) return ERROR; *e=p->data; return OK; } //删除第i个结点并将其存入e int ListDelete_L(LinkList *L,int i,ElemType *e){ LinkList q,p=*L;//p为待删元素的前驱 int j=0; while(p && j<i-1){ 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; } //合并有序链表 void MergeList_L(LinkList *La,LinkList *Lb,LinkList *Lc){ LinkList pa=(*La)->next; LinkList pb=(*Lb)->next; LinkList pc; *Lc=*La; //在La上合并 pc=*La; //以指针pc进行遍历合并 while(pa && pb){ if(pa->data <= pb->data){ pc->next=pa; //先链接后移动 pc=pa; pa=pa->next; }else{ pc->next=pb; pc=pb; pb=pb->next; } } pc->next=pa?pa:pb; //链接剩余链表 free(*Lb);//释放Lb } int main(){ LinkList L; int n; printf("请输入链表的长度："); scanf("%d",&n); CreateList_L(&L,n); //头结点没有数据，next指向第一个数据 LNode *p=L->next; while(p!=NULL){ printf("%d ",p->data); p=p->next; } int i,e; printf("\n请输入插入位置和元素："); scanf("%d%d",&i,&e); ListInsert_L(&L,i,e); p=L->next; while(p!=NULL){ printf("%d ",p->data); p=p->next; } GetElem_L(L,3,&e); printf("\n第3个元素为%d\n",e); ListDelete_L(&L,3,&e); printf("删除第3个元素："); p=L->next; while(p!=NULL){ printf("%d ",p->data); p=p->next; } LinkList L1,L2,L3; printf("\n请输入两个有序链表的长度："); scanf("%d",&n); printf("\n请输入第一个有序链表：\n"); CreateList_L(&L1,n); printf("\n请输入第二个有序链表：\n"); CreateList_L(&L2,n); MergeList_L(&L1,&L2,&L3); //头结点没有数据，next指向第一个数据 LNode *q=L3->next; while(q){ printf("%d ",q->data); q=q->next; } return 0; }

（七）线性链表的逆置（反转）

先检查是否为空链表或只有一个元素，这两种情况都不需要进行反转。定义三个指针prev（p），curr（c），next（n）遍历链表，逐个改变结点的next指针方向，实现原地反转。最后将头结点指向反转后的新头结点。

注意：可以将此过程看作顺序遍历整个链表，逐个将结点按照头插法依次插入原链表（头插法：输入元素的顺序与实际链表中元素的顺序相反）。

//线性链表的逆置 int reverseListWithHeader(LinkList L){ //空链表或只有一个元素时不需要反转 if(L==NULL || L->next==NULL) return OK; LNode *prev=NULL; LNode *curr=L->next; LNode *next=NULL; while(curr!=NULL){ next=curr->next; //下一个需要插入的结点 curr->next=prev; //利用头插法插入结点 prev=curr; //更新第一个结点 curr=next; //更新当前插入结点 } L->next=prev; //头结点指向反转后的新头结点 return OK; }

三、单链表扩展（无头结点）

（一）删除链表中所有等于val的结点

定义一个哑结点dummy作为首结点（第一个数据结点）的前驱，哑结点的next指向原链表头，统一处理首结点删除的情况。

定义一个指针current从哑结点开始遍历链表，如果current下一个结点的值等于val，则删除下一个结点（将current的next直接链接到current后继的后继），最后释放哑结点并返回新首结点。

//删除链表中所有满足 Node.val==val 的结点，并返回新的头结点 LinkList deleteNode_L(LinkList head,int val){ if(head==NULL) return NULL; //空链表 //没有头结点，所以需要定义一个哑结点作为首结点的前驱 //避免首结点就等于val无法删除，使用哑结点方便操作 LinkList dummy=(LinkList)malloc(sizeof(LNode)); if(dummy==NULL) return NULL; dummy->next=head; //作用与头结点一致（无数据，指向首结点） //从哑结点开始往后遍历链表，依次删除==val的结点 LinkList current=dummy; while(current->next!=NULL){ if(current->next->val==val){//比较下一个结点的数据是否等于val LinkList temp=current->next; //暂存删除结点 current->next=current->next->next; //当前结点直接链接删除结点的后继（跳过链接） free(temp); //将删除的结点释放 }else{ current=current->next; //遍历链表 } } LinkList newNode=dummy->next; //用于返回首结点 free(dummy); //释放内存，防止内存泄漏 //释放后不需要再置空了，因为dummy为局部变量，函数结束后会自动销毁 return newNode; }

（二）返回链表的中间节点

使用快慢指针，利用循环遍历整个链表，快指针fast每次都两步，慢指针slow每次只走一步。当快指针fast到达链表尾部时，慢指针刚好指向链表的中间结点。

注意：初始化时slow和fast都指向首结点（第一个有数据的结点，非头结点），当链表长度为偶数时，慢指针slow会指向第二个中间结点。

//返回链表的中间节点，如果有两个中间节点，则返回第二个中间节点 LinkList searchMiddleNode_L(LinkList head){ if(head==NULL) return NULL; LinkList slow=head; LinkList fast=head; while(fast!=NULL && fast->next!=NULL){ slow=slow->next; //慢指针slow每次只走一步 fast=fast->next->next; //快指针fast每次都两步 } return slow; }

（三）返回链表中的倒数第k个结点

定义两个指针p和q并初始化为首结点（第一个有数据的结点，非头结点），先让指针p走k步，此时p与q相差k-1（中间有k-1个节点），然后p和q同时移动，当p到达链表末尾时（p==NULL），q刚好指向倒数第k个结点（p与q相差k-1个结点，p此时为NULL，则q为倒数第k个结点）。

//返回链表中的倒数第k个节点 LinkList searchNode_L(LinkList head,int k){ if(k<=0 || head==NULL) return NULL; LinkList p=head; LinkList q=head; for(int i=0;i<k;i++){ if(p==NULL) return NULL; //不存在k个结点 p=p->next; //定位到第k个结点 }//此时p与q相差（中间有）k-1个结点 while(p!=NULL){ //定位后p，q同时移动 p=p->next; q=q->next; } return q; }

四、双向链表

（一）双向链表的结构

双向链表与单链表的不同是，多了一个前向指针prior。

#define ElemType int typedef struct DuLNode{ ElemType data; struct DuLNode *prior,*next; }DuLNode,*DuLinkList;

（二）创建双向空链表

申请分配一个头结点的内存，将其prior和next指针都指向自身，形成一个双向循环空链表。

注意：空链表中，头结点的prior和next都指向自己，这是双向循环链表的标志。

//创建一个带头结点的双向空链表 DuLinkList CreateList_DuL(){ DuLinkList L=(DuLinkList)malloc(sizeof(DuLNode)); if(L==NULL) return NULL; L->prior=L; L->next=L; return L; }

（三）按位置查找结点

从头结点的后继（首元素）开始遍历，计数到第 i 个结点（数据结点），返回该结点的指针。特殊处理i=0时返回头结点（无数据，首元素的前驱）。

//按位置查找结点 DuLinkList GetElem_DuL(DuLinkList L,int i){ if(L==NULL || i<0) return NULL; if(i==0) return L; DuLinkList p=L->next; int j=1; while(p!=L && j<i){ //循环遍历找到位置 p=p->next; ++j; } //p==L说明已经遍历完整个链表，没有k个结点 if(p==L || j!=i) return NULL; return p; }

（四）插入结点

调用查找函数定位到第 i-1 个结点（插入位置的前驱），创建新结点p并申请空间，申请成功设置数据值，链接新结点（需要设置链表第i-1个结点的next、第i个结点的prior 与 新结点的prior、next进行链接）。

注意：连接顺序很重要，必须先链接新结点，再修改链表第i-1个结点的next、第i个结点的prior。

//插入第i个元素：尾插法(第一个位置和最后一个位置都能实现插入操作) int ListInsert_DuL(DuLinkList *L,int i,ElemType e){ DuLinkList p=GetElem_DuL(*L,i-1); //定位到第i个元素的前驱 if(p == NULL) return ERROR; DuLinkList s=(DuLinkList)malloc(sizeof(DuLNode));//创建新结点 if(s==NULL) return ERROR; s->data=e; //赋值 s->prior=p; //新结点的prior指针指向第i个结点的前驱p s->next=p->next; //新结点的next指向p的后继（原链表第i个结点） p->next->prior=s; //将原链表第i个结点连接到新结点的后面 p->next=s; //将新结点连接到p的后面 return OK; }

（五）删除结点

调用查找函数定位到第 i 个结点（待删结点），先暂存待删结点的数据，在修改其前后指针（将原链表第i-1个结点的next与第i+1个结点的prior链接），将待删结点从链表中摘除，最后释放删除结点的内存。

//删除第i个结点 int ListDelete_DuL(DuLinkList *L,int i,ElemType *e){ DuLinkList p=GetElem_DuL(*L,i); if(p==NULL) return ERROR; *e=p->data; //暂存数据 p->prior->next=p->next; //修改前后指针 p->next->prior=p->prior; free(p); return OK; }