這個鏈表是帶有表頭的雙鏈表。實現(xiàn)鏈表的一些規(guī)范操作，初始化，插入，刪除等。包括兩個頭文件list.h，fatal.h，庫函數(shù)list.c，測試函數(shù)testlist.c。頭文件放的都是函數(shù)聲明，庫函數(shù)list.c放的的函數(shù)的定義。

頭文件list.h

1 typedef int ElementType; 2 #ifndef _List_H 3 struct Node; 4 typedef struct Node *PtrToNode; 5 typedef PtrToNode List; 6 typedef PtrToNode Position; 7 #include<stdbool.h> 8 List MakeEmpty(List L); 9 void DeleteList(List L); 10 bool IsEmpty(List L); 11 bool IsLast(Position P, List L); 12 Position Find(ElementType X, List L); 13 void Delete(ElementType X, List L); 14 void Insert(ElementType X, List L,Position P); 15 Position Header(List L); 16 Position First(List L); 17 Position Advance(Position P); 18 Position Front(Position P); 19 ElementType Retrieve(Position P); 20 void PrintList(const List L); 21 void PrintLots(List L, List P); 22 void SwapWithNext(Position P, List L); 23 void SwapWithNoNext(Position P1,Position P2, List L); 24 List IntersectList(List L, List P); 25 List UnionList(Position L, Position P); 26 #endif // !_List_H

頭文件fatal.h：

1 #include<stdio.h> 2 #include<stdlib.h> 3 #define Error(Str) FatalError(Str) 4 #define FatalError(Str) fprintf(stderr,"%s\n",Str),exit(1);

?庫函數(shù)list.c：

//引用頭文件 #include "list.h" #include<stdlib.h> #include "fatal.h"//結構體定義，一個前指針Pre和一個后指針Next struct Node {ElementType Element;Position Next;Position Prev; };//初始化鏈表 List MakeEmpty(List L) {if (L != NULL)DeleteList(L);L = malloc(sizeof(struct Node));if (L == NULL)FatalError("Out of memory!");L->Next = NULL;L->Prev = L;return L; }//刪除鏈表 void DeleteList(List L) {Position P, Temp;P = L->Next;L->Next = NULL;while (P != NULL){Temp = P->Next;free(P);P = Temp;} }//判斷鏈表是否為空 bool IsEmpty(List L) {return L->Next == NULL; }//判斷當前指針P是否指向鏈表最后一個元素 bool IsLast(Position P, List L) {return P->Next == NULL; }//在鏈表中找元素X，如果返回是NULL說明沒找到 Position Find(ElementType X, List L) {Position P;P = L->Next;while (P != NULL && P->Element != X)P = P->Next;return P; }//刪除鏈表中的元素X，若返回NULL，說明在鏈表中沒找到元素X void Delete(ElementType X, List L) {Position P;P = Find(X, L);//if P==NULL，說明沒找到if (P != NULL)//當P不是空指針，說明找到了 {if (!IsLast(P, L)){P->Prev->Next = P->Next;P->Next->Prev = P->Prev;free(P);}else //最后一個結點特殊處理，最后一個結點p->next無prev {P->Prev->Next = NULL;free(P);}}}//插入元素X到位置P后面 void Insert(ElementType X, List L, Position P) {Position TmpCell;TmpCell = malloc(sizeof(struct Node));if (TmpCell == NULL)FatalError("Out of Space!!!");TmpCell->Element = X;TmpCell->Next = P->Next;P->Next = TmpCell;TmpCell->Prev = P; }//獲取鏈表頭 Position Header(List L) {return L; }//獲取鏈表第一個元素的位置 Position First(List L) {return L->Next; }//獲取位置P的下（后）一個位置 Position Advance(Position P) {return P->Next; }//獲取位置P的上（前）一個位置 Position Front(Position P) {return P->Prev; }//提取位置P處結構里面的值 ElementType Retrieve(Position P) {return P->Element; }//打印鏈表 void PrintList(const List L) {Position P = Header(L);if (IsEmpty(L))printf("Empty list\n");else{do{P = Advance(P);printf("%d ", Retrieve(P));} while (!IsLast(P, L));printf("\n");} }//打印鏈表L中那些由P所指定的位置上的元素。例如P=1，3，4，6，將L //中的第1，第3，第4，第6個元素打印出來 void PrintLots(List L, List P) {int count = 1;Position Lpos, Ppos;Lpos = First(L);Ppos = First(P);while (Lpos != NULL&&Ppos != NULL){if (Ppos->Element == count++){printf("%d ", Ppos->Element);Ppos = Advance(Ppos);}Lpos = Advance(Lpos);}}//通過只調整指針來交換兩個相鄰的元素，P是要調換兩個元素中的前一 //個指針 void SwapWithNext(Position P, List L) {Position AfterP;//AfterP是后一個指針if (P != NULL){AfterP = Advance(P);if (AfterP != NULL)//下面總共六條語句動六根線（除去if）， //前兩條動P的一個節(jié)點，接下來兩條語句動AfterP的后一個節(jié)點，最后兩條 //語句動P和AfterP兩個節(jié)點 {P->Prev->Next = AfterP;//先調換P的前一個節(jié)點的 //next，讓它指向AfterPAfterP->Prev = P->Prev;//再讓AfterP的前節(jié)點指向P //的前一個節(jié)點，這樣P的前一個節(jié)點就指向好了if (Advance(AfterP) != NULL)//為了防止After是尾指 //針，如果After是尾指針,則AfterP->Next=NULL，沒有前節(jié)點，就什么 //都不做AfterP->Next->Prev = P; // 讓AfterP的后一個 //節(jié)點的前節(jié)點改為指向P；P->Next = AfterP->Next;//P的Next指向AfterP的下一 //個節(jié)點AfterP->Next = P;//AfterP的下一個節(jié)點指向P；P->Prev = AfterP;//P的前節(jié)點指向After; }} }//通過只調整指針來交換兩個不相鄰的元素p1和p2 void SwapWithNoNext(Position P1, Position P2, List L)//p1在前，p2 //在后 {Position P1f, P1b, P2f, P2b;//構造四個中間變量,清晰P1f = P1->Prev;P1b = P1->Next;P2f = P2->Prev;P2b = P2->Next;//八條語句P1f->Next = P2;P2->Prev = P1f;P2->Next = P1b;P1b->Prev = P2;P2f->Next = P1;P1->Prev = P2f;P1->Next = P2b;if (P2b!=NULL)//如果P2b=NULL,就沒有前指針PrevP2b->Prev = P1; }//求兩個鏈表的交集 List IntersectList(List L1, List L2) {List ResultList;Position L1Pos, L2Pos, ResultPos;ResultList = MakeEmpty(NULL);L1Pos = First(L1);L2Pos = First(L2);ResultPos = Header(ResultList);while (L1Pos != NULL&&L2Pos != NULL){if (L1Pos->Element < L2Pos->Element)L1Pos = Advance(L1Pos);else if (L1Pos->Element > L2Pos->Element)L2Pos = Advance(L2Pos);else{Insert(L1Pos->Element, ResultList, ResultPos);ResultPos = Advance(ResultPos);L1Pos = Advance(L1Pos);L2Pos = Advance(L2Pos);}}return ResultList; }//求兩個鏈表的并集 List UnionList(Position L1, Position L2) {List ResultList;ElementType InsertElement;Position L1Pos, L2Pos, ResultPos;ResultList = MakeEmpty(NULL);L1Pos = First(L1);L2Pos = First(L2);ResultPos = Header(ResultList);while (L1Pos != NULL&&L2Pos != NULL){if (L1Pos->Element < L2Pos->Element){InsertElement = L1Pos->Element;L1Pos = Advance(L1Pos);}else if (L1Pos->Element > L2Pos->Element){InsertElement = L2Pos->Element;L2Pos = Advance(L2Pos);}else{InsertElement = L1Pos->Element;L1Pos = Advance(L1Pos);L2Pos = Advance(L2Pos);}Insert(InsertElement, ResultList, ResultPos);ResultPos = Advance(ResultPos);}while (L1Pos != NULL){Insert(L1Pos->Element, ResultList, ResultPos);ResultPos = Advance(ResultPos);L1Pos = Advance(L1Pos);}while (L2Pos != NULL){Insert(L2Pos->Element, ResultList, ResultPos);ResultPos = Advance(ResultPos);L2Pos = Advance(L2Pos);}return ResultList; }

?測試函數(shù)testlist.c

1 #include<stdio.h> 2 #include "list.h" 3 main() 4 { 5 List L,L1; 6 Position P,P1; 7 int i; 8 L = MakeEmpty(NULL); 9 P = Header(L); 10 PrintList(L); 11 12 L1 = MakeEmpty(NULL); 13 P1 = Header(L1); 14 PrintList(L1); 15 16 17 for (i = 0; i < 50; i+=1) 18 { 19 Insert(i, L, P); 20 //PrintList(L); 21 P = Advance(P); 22 } 23 PrintList(L); 24 printf("\n"); 25 for (i = 1; i < 100; i+=3) 26 { 27 Insert(i, L1, P1); 28 //PrintList(L); 29 P1 = Advance(P1); 30 } 31 PrintList(L1); 32 printf("\n"); 33 34 PrintList(IntersectList(L, L1)); 35 printf("\n"); 36 PrintList(UnionList(L, L1)); 37 //PrintLots(L, L1); 38 39 //SwapWithNext(Advance(Advance(Advance(L))),L);//換頭兩個元素 40 //SwapWithNoNext(Advance(L), Advance(Advance(Advance(Advance(L)))),L); 41 //for (i = 0; i < 10; i += 2) 42 // Delete(i, L); 43 //for (i = 0; i < 10; i++) 44 //{ 45 // if ((i % 2 == 0) == (Find(i, L) != NULL)) 46 // printf("Find fails\n"); 47 //} 48 //printf("Finished deletions\n"); 49 //PrintList(L); 50 DeleteList(L); 51 DeleteList(L1); 52 return 0; 53 }

轉載于:https://www.cnblogs.com/xinlovedai/p/6216160.html

總結

以上是生活随笔為你收集整理的双链表的基本操作---插入，删除，交，并，相邻元素的交换，不相邻元素的交换...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。