双链表的基本操作---插入,删除,交,并,相邻元素的交换,不相邻元素的交换...
                                                            生活随笔
收集整理的這篇文章主要介紹了
                                双链表的基本操作---插入,删除,交,并,相邻元素的交换,不相邻元素的交换...
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.                        
                                這個鏈表是帶有表頭的雙鏈表。實現(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
總結
以上是生活随笔為你收集整理的双链表的基本操作---插入,删除,交,并,相邻元素的交换,不相邻元素的交换...的全部內容,希望文章能夠幫你解決所遇到的問題。
 
                            
                        - 上一篇: Render errors:One or
- 下一篇: python气象数据分析_气象数据分析-
