单链表的基本操作---插入,删除,交,并,相邻元…
2018-06-18 04:11:53来源:未知 阅读 ()
这个链表是带有表头的单链表。实现链表的一些规范操作,初始化,插入,删除等。包括两个头文件list.h,fatal.h,库函数list.c,测试函数testlist.c。头文件放的都是函数声明,库函数list.c放的的函数的定义。
头文件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 Position FindPrevious(ElementType X, List L); 15 void Insert(ElementType X, List L, Position P); 16 Position Header(List L); 17 Position First(List L); 18 Position Advance(Position P); 19 ElementType Retrieve(Position P); 20 void PrintList(const List L); 21 void PrintLots(List L, List P); 22 void SwapWithNext(Position BeforeP, List L); 23 List IntersectList(List L, List P); 24 List UnionList(Position L, Position P); 25 void ReverseList(List L); 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);
库函数list.c:
//引用头文件 #include "list.h" #include<stdlib.h> #include "fatal.h" //结构体定义 struct Node { ElementType Element; Position Next; }; //初始化链表 List MakeEmpty(List L) { if (L != NULL) DeleteList(L);//如果链表非空,则删除链表 L = malloc(sizeof(struct Node)); if (L == NULL) FatalError("Out of memory!"); L->Next = NULL; 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; } //return Position of X in L;NULL if not found 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, TempCell; P = FindPrevious(X, L); if (!IsLast(P, L))//当P不是尾针,说明找到了 { TempCell = P->Next; P->Next = TempCell->Next; free(TempCell); TempCell = NULL; } } //如果返回的P指向最后一个元素,说明没有找到,1==IsLast(P,L) Position FindPrevious(ElementType X, List L) { Position P; P = L; while (P->Next != NULL&&P->Next->Element != X) P = P->Next; return 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; } //获取链表头 Position Header(List L) { return L; } //获取链表第一个元素的位置 Position First(List L) { return L->Next; } //获取位置P的下一个位置 Position Advance(Position P) { return P->Next; } //提取位置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); } } //通过只调整指针来交换两个相邻的元素,BeforeP是要调换两个元素的前一 //个指针 void SwapWithNext(Position BeforeP, List L) { Position P, AfterP; if (BeforeP != NULL) { P = Advance(BeforeP); if (P != NULL) { AfterP = Advance(P); if (AfterP != NULL) { P->Next = AfterP->Next; BeforeP->Next = AfterP; AfterP->Next = P; } } } } //求两个链表的交集 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; } //将链表以O(N)进行反转链表 void ReverseList(List L) { if (IsEmpty(L)||L->Next->Next==NULL)//如果链表是空或者只有一个元素,则不排序 return; Position CurrentPos, PreviousPos, NextPos; CurrentPos = L->Next;//当前指针 PreviousPos = NULL;//上一个指针 NextPos = L->Next->Next;//探测指针 while (NextPos!=NULL)//探测指针指向链表尾部时,停止循环 { CurrentPos->Next = PreviousPos;//当前指针指向指向上一个指针 PreviousPos = CurrentPos;//将上一个指针后移 CurrentPos = NextPos;//将当前指针后移 NextPos = Advance(NextPos);//将探测指针后移,直到触到尾指针NULL } CurrentPos->Next = PreviousPos;//最后一个指针还没有链接前一个指针 L->Next = CurrentPos;//将头结点链接原来尾节点 }
测试函数testlist.c
1 #include<stdlib.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+=2) 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 ReverseList(L1); 34 PrintList(IntersectList(L, L1)); 35 printf("\n"); 36 PrintList(UnionList(L, L1)); 37 //PrintLots(L, L1); 38 39 //SwapWithNext(L, L);//换头两个元素 40 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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:使用CMake构建复杂工程
下一篇:简单的串口通信程序控制光源
- 单链表 2020-03-31
- 小游戏二之---------------五子棋 2020-03-23
- C++ 静态成员----细谈static修饰的成员 2020-03-19
- 二叉树(1)二叉树基本操作通用接口 2020-02-06
- 数据结构---二叉搜索树 2020-02-06
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash