一、顺序表一顺序表的结构可以将顺序表看作是一种结构体该结构体中的成员有一个数组用于存储数据和两个变量表示数组的实际长度与最大长度但具体的成员设计有多种方式。#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-elemNULL) return OVERFLOW; //分配失败返回溢出错误 L-length0; //初始化当前元素个数为0 L-listsizeLIST_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(LNULL || valuesNULL || count0) return ERROR; //检查参数 while(L-lengthcount L-listsize){//如果需要添加的元素个数顺序表的最大长度则需要对顺序表进行扩容 //使用临时变量防止realloc失败导致数据丢失 ElemType *newElem(ElemType *)realloc(L-elem,(L-listsizeLISTINCREMENT)*sizeof(ElemType)); if(newElemNULL) return OVERFLOW; L-elemnewElem; //更新最大长度 L-listsizeLISTINCREMENT; } //逐个添加元素 for(int i0;icount;i){ L-elem[L-lengthi]values[i]; } L-lengthcount; 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(i1 || iL-length1) return ERROR; //如果顺序表满了则需要扩容重新分配空间 if(L-length L-listsize){ //重新分配空间 ElemType *newbase(ElemType *)realloc(L-elem,(L-listsizeLISTINCREMENT)*sizeof(ElemType)); if(!newbase) exit(OVERFLOW); //分配成功则更新顺序表的基地址与最大长度 L-elemnewbase; L-listsizeLISTINCREMENT; } //定位需要插入的位置 ElemType *qL-elemi-1; //从后往前以此向后覆盖空出第i位 for(ElemType *pL-elemL-length-1;p q;--p){ *(p1)*p; } *qe; //插入第i位 L-length; //更新顺序表长度 return OK; }五删除元素int ListDelete_Sq(SqList *L,int i,ElemType *e)参数需要添加元素的顺序表传指针修改值需要删除元素的位置ie存放删除元素。思路先检查参数然后定位到需要删除的元素的位置用参数e暂存删除的元素值使用循环将待删除元素的后一个元素向前覆盖待删元素直到顺序表的最后一个元素最后更新实际元素个数。//删除元素 int ListDelete_Sq(SqList *L,int i,ElemType *e){ if(i1 || iL-length) return ERROR; ElemType *pL-elemi-1; //定位需要删除元素的位置 *e*p; // 保留需要删除的元素值 ElemType *qL-elemL-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; paLa-elem; pbLb-elem; Lc-listsizeLa-listsizeLb-listsize; //更新合并顺序表的最大元素个数 Lc-lengthLa-lengthLb-length; //更新合并顺序表的实际元素个数 Lc-elem(ElemType *)malloc(Lc-listsize*sizeof(ElemType)); //申请空间 if(!Lc-elem) return OVERFLOW; pcLc-elem; pa_lastLa-elemLa-length-1; //设定La边界 pb_lastLb-elemLb-length-1; //设定Lb边界 while(papa_last pbpb_last){ //循环遍历两个有序顺序表并比较对应元素值 if(*pa*pb){ //将较小元素值更新到顺序表Lc *pc*pa; }else{ *pc*pb; } } while(papa_last) *pc*pa; //将La剩余元素更新到合并顺序表Lc while(pbpb_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-elemNULL) return OVERFLOW; //分配失败返回溢出错误 L-length0; //初始化当前元素个数为0 L-listsizeLIST_INIT_SIZE; //初始化最大元素个数 return OK; } //添加元素 int AddElem_Sq(SqList *L,ElemType *values,int count){ if(LNULL || valuesNULL || count0) return ERROR; //检查参数 while(L-lengthcount L-listsize){//如果需要添加的元素个数顺序表的最大长度则需要对顺序表进行扩容 //使用临时变量防止realloc失败导致数据丢失 ElemType *newElem(ElemType *)realloc(L-elem,(L-listsizeLISTINCREMENT)*sizeof(ElemType)); if(newElemNULL) return OVERFLOW; L-elemnewElem; //更新最大长度 L-listsizeLISTINCREMENT; } //逐个添加元素 for(int i0;icount;i){ L-elem[L-lengthi]values[i]; } L-lengthcount; return OK; } //插入元素 int ListInsert_Sq(SqList *L,int i,ElemType e){ if(i1 || iL-length1) return ERROR; //如果顺序表满了则需要扩容重新分配空间 if(L-length L-listsize){ //重新分配空间 ElemType *newbase(ElemType *)realloc(L-elem,(L-listsizeLISTINCREMENT)*sizeof(ElemType)); if(!newbase) exit(OVERFLOW); //分配成功则更新顺序表的基地址与最大长度 L-elemnewbase; L-listsizeLISTINCREMENT; } //定位需要插入的位置 ElemType *qL-elemi-1; //从后往前以此向后覆盖空出第i位 for(ElemType *pL-elemL-length-1;p q;--p){ *(p1)*p; } *qe; //插入第i位 L-length; //更新顺序表长度 return OK; } //删除元素 int ListDelete_Sq(SqList *L,int i,ElemType *e){ if(i1 || iL-length) return ERROR; ElemType *pL-elemi-1; //定位需要删除元素的位置 *e*p; // 保留需要删除的元素值 ElemType *qL-elemL-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; paLa-elem; pbLb-elem; Lc-listsizeLa-listsizeLb-listsize; //更新合并顺序表的最大元素个数 Lc-lengthLa-lengthLb-length; //更新合并顺序表的实际元素个数 Lc-elem(ElemType *)malloc(Lc-listsize*sizeof(ElemType)); //申请空间 if(!Lc-elem) exit(OVERFLOW); pcLc-elem; pa_lastLa-elemLa-length-1; //设定La边界 pb_lastLb-elemLb-length-1; //设定Lb边界 while(papa_last pbpb_last){ //循环遍历两个有序顺序表并比较对应元素值 if(*pa*pb){ //将较小元素值更新到顺序表Lc *pc*pa; }else{ *pc*pb; } } while(papa_last) *pc*pa; //将La剩余元素更新到合并顺序表Lc while(pbpb_last) *pc*pb; //将Lb剩余元素更新到合并顺序表Lc } int main(){ SqList List; InitList_Sq(List); ElemType values[]{10,20,30,40,50}; int countsizeof(values)/sizeof(values[0]); AddElem_Sq(List,values,count); for(int i0;iList.length;i){ printf(%d ,List.elem[i]); } printf(\n); ElemType x25; ListInsert_Sq(List,3,x); for(int i0;iList.length;i){ printf(%d ,List.elem[i]); } printf(\n); ElemType e0; ListDelete_Sq(List,3,e); for(int i0;iList.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 count1sizeof(values1)/sizeof(values1[0]); int count2sizeof(values2)/sizeof(values2[0]); AddElem_Sq(List1,values1,count1); AddElem_Sq(List2,values2,count2); MergeList_Sq(List1,List2,List3); printf(\n); for(int i0;iList3.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)-nextp。这两步顺序不能改变如果改变会导致数据丢失注意使用头插法输入元素的顺序与实际链表中元素的顺序相反。尾插法顺序一致。//创建链表头插法尾插法 int CreateList_L(LinkList *L,int n){ //创建一个链表指针L指向头结点 //L为二级指针指向LinkListLinkList指向LNode //所以*L为指向LNode *L(LinkList)malloc(sizeof(LNode)); if(*LNULL){ //*L为指针指向头结点 printf(Memory allocation failed!\n); return ERROR; } //初始化链表为空链表 (*L)-nextNULL; LNode *tail*L; //尾指针 //创建链表插入n个元素 for(int i0;in;i){ //创建新结点p为指针指向新结点 LNode *p(LNode *)malloc(sizeof(LNode)); if(pNULL){ printf(Memory allocation failed!\n); return ERROR; } //printf(请输入第%d个元素,n-i); //头插法逆序插入 printf(请输入第%d个元素,i1); //尾插法顺序插入 scanf(%d,p-data); p-nextNULL; tail-nextp; //尾插法:使用尾指针从前往后链接 tailp; // p-next(*L)-next; //头插法先链接后面再链接前面 // (*L)-nextp; } 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 j0; while(p ji-1){ //定位到需要插入的地方 pp-next; j; } //遍历到链表尾或i值非法为0/负值 if(!p || ji-1) return ERROR; //创建新结点 LinkList s(LinkList)malloc(sizeof(LNode)); if(!s) return ERROR; s-datae; s-nextp-next; //先链接后面再链接前面 p-nexts; return OK; }四查找结点定义一个指针p使用循环用于定位需要查找结点的位置如需要查找第i个位置的结点元素将其数据域的元素存入e。//查找第i个结点并存入e int GetElem_L(LinkList L,int i,ElemType *e){ LinkList pL-next; int j0; while(p ji-1){ pp-next; j; } if(!p || ji) return ERROR; *ep-data; return OK; }五删除结点定义一个指针p使用循环用于定位需要删除结点的前驱如需要删除第i个结点则定位到第i-1个结点然后用指针q指向待删结点qp-next将其数据域存入e中qp-next最后修改指针跳过直接指向q的后继结点 p-nextq-next并释放删除结点的内存 free(q)。//删除第i个结点并将其存入e int ListDelete_L(LinkList *L,int i,ElemType *e){ LinkList q,p*L;//p为待删元素的前驱 int j0; while(p ji-1){ pp-next; j; } if(!(p-next) || ji-1) return ERROR; qp-next; p-nextq-next; *eq-data; free(q); return OK; }六合并有序链表原地操作La与Lb为待合并的有序链表Lc指向La将Lb合并插入到链表La上。利用循环使pa与pb分别遍历La与Lb比较对应的结点数据域每次将较小的结点连接到pc后面pc-nextpa;并更新其指向 pcpa、papa-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-nextpa; //先链接后移动 pcpa; papa-next; }else{ pc-nextpb; pcpb; pbpb-next; } } pc-nextpa?pa:pb; //链接剩余链表 free(*Lb);//释放Lb *LbNULL;//防止野指针 }单链表测试完整代码#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为二级指针指向LinkListLinkList指向LNode //所以*L为指向LNode *L(LinkList)malloc(sizeof(LNode)); if(*LNULL){ //*L为指针指向头结点 printf(Memory allocation failed!\n); return ERROR; } //初始化链表为空链表 (*L)-nextNULL; LNode *tail*L; //尾指针 //创建链表插入n个元素 for(int i0;in;i){ //创建新结点p为指针指向新结点 LNode *p(LNode *)malloc(sizeof(LNode)); if(pNULL){ printf(Memory allocation failed!\n); return ERROR; } //printf(请输入第%d个元素,n-i); //头插法逆序插入 printf(请输入第%d个元素,i1); //尾插法顺序插入 scanf(%d,p-data); p-nextNULL; tail-nextp; //尾插法:使用尾指针从前往后链接 tailp; // p-next(*L)-next; //头插法先链接后面再链接前面 // (*L)-nextp; } return OK; } //在第i个位置插入结点 int ListInsert_L(LinkList *L,int i,ElemType e){ LinkList p*L; int j0; while(p ji-1){ //定位到需要插入的地方 pp-next; j; } //遍历到链表尾或i值非法为0/负值 if(!p || ji-1) return ERROR; //创建新结点 LinkList s(LinkList)malloc(sizeof(LNode)); if(!s) return ERROR; s-datae; s-nextp-next; //先链接后面再链接前面 p-nexts; return OK; } //查找第i个结点并存入e int GetElem_L(LinkList L,int i,ElemType *e){ LinkList pL-next; int j0; while(p ji-1){ pp-next; j; } if(!p || ji) return ERROR; *ep-data; return OK; } //删除第i个结点并将其存入e int ListDelete_L(LinkList *L,int i,ElemType *e){ LinkList q,p*L;//p为待删元素的前驱 int j0; while(p ji-1){ pp-next; j; } if(!(p-next) || ji-1) return ERROR; qp-next; p-nextq-next; *eq-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-nextpa; //先链接后移动 pcpa; papa-next; }else{ pc-nextpb; pcpb; pbpb-next; } } pc-nextpa?pa:pb; //链接剩余链表 free(*Lb);//释放Lb } int main(){ LinkList L; int n; printf(请输入链表的长度); scanf(%d,n); CreateList_L(L,n); //头结点没有数据next指向第一个数据 LNode *pL-next; while(p!NULL){ printf(%d ,p-data); pp-next; } int i,e; printf(\n请输入插入位置和元素); scanf(%d%d,i,e); ListInsert_L(L,i,e); pL-next; while(p!NULL){ printf(%d ,p-data); pp-next; } GetElem_L(L,3,e); printf(\n第3个元素为%d\n,e); ListDelete_L(L,3,e); printf(删除第3个元素); pL-next; while(p!NULL){ printf(%d ,p-data); pp-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 *qL3-next; while(q){ printf(%d ,q-data); qq-next; } return 0; }七线性链表的逆置反转先检查是否为空链表或只有一个元素这两种情况都不需要进行反转。定义三个指针prevpcurrcnextn遍历链表逐个改变结点的next指针方向实现原地反转。最后将头结点指向反转后的新头结点。注意可以将此过程看作顺序遍历整个链表逐个将结点按照头插法依次插入原链表头插法输入元素的顺序与实际链表中元素的顺序相反。//线性链表的逆置 int reverseListWithHeader(LinkList L){ //空链表或只有一个元素时不需要反转 if(LNULL || L-nextNULL) return OK; LNode *prevNULL; LNode *currL-next; LNode *nextNULL; while(curr!NULL){ nextcurr-next; //下一个需要插入的结点 curr-nextprev; //利用头插法插入结点 prevcurr; //更新第一个结点 currnext; //更新当前插入结点 } L-nextprev; //头结点指向反转后的新头结点 return OK; }三、单链表扩展无头结点一删除链表中所有等于val的结点定义一个哑结点dummy作为首结点第一个数据结点的前驱哑结点的next指向原链表头统一处理首结点删除的情况。定义一个指针current从哑结点开始遍历链表如果current下一个结点的值等于val则删除下一个结点将current的next直接链接到current后继的后继最后释放哑结点并返回新首结点。//删除链表中所有满足 Node.valval 的结点并返回新的头结点 LinkList deleteNode_L(LinkList head,int val){ if(headNULL) return NULL; //空链表 //没有头结点所以需要定义一个哑结点作为首结点的前驱 //避免首结点就等于val无法删除使用哑结点方便操作 LinkList dummy(LinkList)malloc(sizeof(LNode)); if(dummyNULL) return NULL; dummy-nexthead; //作用与头结点一致无数据指向首结点 //从哑结点开始往后遍历链表依次删除val的结点 LinkList currentdummy; while(current-next!NULL){ if(current-next-valval){//比较下一个结点的数据是否等于val LinkList tempcurrent-next; //暂存删除结点 current-nextcurrent-next-next; //当前结点直接链接删除结点的后继跳过链接 free(temp); //将删除的结点释放 }else{ currentcurrent-next; //遍历链表 } } LinkList newNodedummy-next; //用于返回首结点 free(dummy); //释放内存防止内存泄漏 //释放后不需要再置空了因为dummy为局部变量函数结束后会自动销毁 return newNode; }二返回链表的中间节点使用快慢指针利用循环遍历整个链表快指针fast每次都两步慢指针slow每次只走一步。当快指针fast到达链表尾部时慢指针刚好指向链表的中间结点。注意初始化时slow和fast都指向首结点第一个有数据的结点非头结点当链表长度为偶数时慢指针slow会指向第二个中间结点。//返回链表的中间节点如果有两个中间节点则返回第二个中间节点 LinkList searchMiddleNode_L(LinkList head){ if(headNULL) return NULL; LinkList slowhead; LinkList fasthead; while(fast!NULL fast-next!NULL){ slowslow-next; //慢指针slow每次只走一步 fastfast-next-next; //快指针fast每次都两步 } return slow; }三返回链表中的倒数第k个结点定义两个指针p和q并初始化为首结点第一个有数据的结点非头结点先让指针p走k步此时p与q相差k-1中间有k-1个节点然后p和q同时移动当p到达链表末尾时pNULLq刚好指向倒数第k个结点p与q相差k-1个结点p此时为NULL则q为倒数第k个结点。//返回链表中的倒数第k个节点 LinkList searchNode_L(LinkList head,int k){ if(k0 || headNULL) return NULL; LinkList phead; LinkList qhead; for(int i0;ik;i){ if(pNULL) return NULL; //不存在k个结点 pp-next; //定位到第k个结点 }//此时p与q相差中间有k-1个结点 while(p!NULL){ //定位后pq同时移动 pp-next; qq-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(LNULL) return NULL; L-priorL; L-nextL; return L; }三按位置查找结点从头结点的后继首元素开始遍历计数到第 i 个结点数据结点返回该结点的指针。特殊处理i0时返回头结点无数据首元素的前驱。//按位置查找结点 DuLinkList GetElem_DuL(DuLinkList L,int i){ if(LNULL || i0) return NULL; if(i0) return L; DuLinkList pL-next; int j1; while(p!L ji){ //循环遍历找到位置 pp-next; j; } //pL说明已经遍历完整个链表没有k个结点 if(pL || 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 pGetElem_DuL(*L,i-1); //定位到第i个元素的前驱 if(p NULL) return ERROR; DuLinkList s(DuLinkList)malloc(sizeof(DuLNode));//创建新结点 if(sNULL) return ERROR; s-datae; //赋值 s-priorp; //新结点的prior指针指向第i个结点的前驱p s-nextp-next; //新结点的next指向p的后继原链表第i个结点 p-next-priors; //将原链表第i个结点连接到新结点的后面 p-nexts; //将新结点连接到p的后面 return OK; }五删除结点调用查找函数定位到第 i 个结点待删结点先暂存待删结点的数据在修改其前后指针将原链表第i-1个结点的next与第i1个结点的prior链接将待删结点从链表中摘除最后释放删除结点的内存。//删除第i个结点 int ListDelete_DuL(DuLinkList *L,int i,ElemType *e){ DuLinkList pGetElem_DuL(*L,i); if(pNULL) return ERROR; *ep-data; //暂存数据 p-prior-nextp-next; //修改前后指针 p-next-priorp-prior; free(p); return OK; }