杭州做网站电话,战队头像logo设计,网站建设成都创新互联,今天重大新闻头条新闻国际新闻这个链表是带有表头的双链表。实现链表的一些规范操作#xff0c;初始化#xff0c;插入#xff0c;删除等。包括两个头文件list.h#xff0c;fatal.h#xff0c;库函数list.c#xff0c;测试函数testlist.c。头文件放的都是函数声明#xff0c;库函数list.c放的的函数的… 这个链表是带有表头的双链表。实现链表的一些规范操作初始化插入删除等。包括两个头文件list.hfatal.h库函数list.c测试函数testlist.c。头文件放的都是函数声明库函数list.c放的的函数的定义。 头文件list.h 1 typedef int ElementType;2 #ifndef _List_H3 struct Node;4 typedef struct Node *PtrToNode;5 typedef PtrToNode List;6 typedef PtrToNode Position;7 #includestdbool.h8 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 #includestdio.h
2 #includestdlib.h
3 #define Error(Str) FatalError(Str)
4 #define FatalError(Str) fprintf(stderr,%s\n,Str),exit(1); 库函数list.c //引用头文件
#include list.h
#includestdlib.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 PNULL说明没找到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所指定的位置上的元素。例如P1346将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 ! NULLPpos ! 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的一个节点接下来两条语句动AfterP的后一个节点最后两条
//语句动P和AfterP两个节点{P-Prev-Next AfterP;//先调换P的前一个节点的
//next让它指向AfterPAfterP-Prev P-Prev;//再让AfterP的前节点指向P
//的前一个节点这样P的前一个节点就指向好了if (Advance(AfterP) ! NULL)//为了防止After是尾指
//针如果After是尾指针,则AfterP-NextNULL没有前节点就什么
//都不做AfterP-Next-Prev P; // 让AfterP的后一个
//节点的前节点改为指向PP-Next AfterP-Next;//P的Next指向AfterP的下一
//个节点AfterP-Next P;//AfterP的下一个节点指向PP-Prev AfterP;//P的前节点指向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)//如果P2bNULL,就没有前指针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 ! NULLL2Pos ! 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 ! NULLL2Pos ! 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;
} 测试函数testlist.c 1 #includestdio.h2 #include list.h3 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; i1)
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; i3)
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
