Chapter_3表、栈和队列：链表

2019-11-14 11:10:10

字体：大中小

来源：转载

供稿：网友

1、单链表

如下图为单链表示意图：这里写图片描述只列出头文件以及单链表相关函数实现代码，均来源于书上，并整理出分析过程。

_List_H.h// _List_H.h#ifndef _List_Hstruct Node;typedef struct Node * PtrToNode;typedef PtrToNode List;typedef PtrToNode Position;List MakeEmpty(List L);int Isempty(List L);int IsLast(Position P,List L);Position Find(ElementType X,List L);Position FindPRevious(ElementType X,List L);void Delete(ElementType X,List L);void Insert(ElementType X,List L,Position P);void DeleteList(List L);Position Header(List L);Position First(List L);Position Advance(Position P);ElementType Retrieve(Position P);#endif /*_List_H*/List_Function.c// List_Function.c/*Place the implemention of the functions*/#include '_List_H.h'struct node{ ElementType Element; Position Next;};/*return true if L is empty*/int IsEmpty(List L){ return L->Next==NULL;}/*return true if P is the last position in list L*//*parameter L is unused in this implementation*/int IsLast(Position P,List L){ return P->Next==NULL;}/*return the podsition 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;}/*return the previous position of X;Null if not found X*/Position FindPrevious(ElementType X,List L){ Position P; P=L; /*Let P=L,for easier to check the next one*/ while(P->Next!=NULL && P->Next->Element!=X) P=P->Next; return P;}/*//Another version of FindPrevious(may some mistakes)Position FindPrevious(ElementType X,List L){ Position P_now,P_next; P_now=P->Next; //Difference:P_now!=L P_next=P_now->Next; if(P_now->Element==X) return P_now; else { while(P_now->Next!=NULL && P_next->Element!=X) { P_now=P_next; P_next=P_next->Next; } }}*//*Delete first occurrrence of X from a list*//*Assume use of a header node*/void Delete(ElementType X,List L){ Position P,TmpCell; /*TmpCell is used for free function*/ P=FindPrevious(X,L); if(!IsLast(P,L)) /*If IsLast(P,L) is true,then X must be NULL*/ { TmpCell=P->Next; P->Next=TmpCell->Next; free(TmpCell); } /*Attention:this is a 'void' function*/}/*Insert X after position P*/void Insert(ElementType X,List L,Position P){ Position TmpCell; TmpCell=malloc(sizeof(struct Node)); if(TmpCell==NULL) { printf("Out of space"); return -1; } TmpCell->Element=X; TmpCell->Next=P->Next; P->Next=TmpCell;}

重要经验：当编写涉及指针的数据结构或者算法时，最好先画出结构图分析过程，再进行写代码。（其实，除了涉及指针的要，很多数据结构、图论等相关算法都先画图分析，清楚思路后才码代码较好）

以下为分析过程图 这里写图片描述

2、双链表

双向链表如下图所示：这里写图片描述 即在单链表的每一个节点Node结构体上，加多一个struct Node * 的指针指向上一个结构体

优缺点

优点：简化删除操作，因为有现成的指向前一个指针可以更改指向即可缺点：增大空间需求（代码量），插入开销增加一倍，有双向指针要搞

3、循环链表

如下图所示，即在单（双）链表末端不接NULL，使其返回指向表头。如下图为双向循环，同理也有单向循环。这里写图片描述

4、几个栗子

多项式ADT（数组实现）//定义多项式组成typedef struct { int CoeffArray[MaxDegree+1]; int HighPower;} * Polynominal;//多项式初始化为0的操作void ZeroPolynominal(Polynominal Poly){ int i; /*系数全部变为0*/ for(i=0;i<=MaxDegree;i++) { Poly->CoeffArray[i]=0; } /*最高阶为0*/ Poly->HighPower=0;}//多项式相加操作void AddPolynominal(const Polynominal P1,const Polynominal P2,Polynominal Psum){ int i; ZeroPolynominal(Psum); Psum->HighPower=( P1->HighPower > P2->HighPower ?(P1->HighPower):(P2->HighPower) ); for(i=0;i<=Psum->HighPower;i++) Psum->CoeffArray[i]=P1->CoeffArray[i]+P2->CoeffArray[i];}//多项式乘法操作void MultPolynominal(const Polynominal P1,const Polynominal P2,Polynominal Pmult){ int i,j; ZeroPolynominal(Pmult); Psum->HighPower=P1->HighPower+P2->HighPower; if(Psum->HighPower > MaxDegree) /* 容易忽视的地方*/ { printf("Exceed size!"); return -1; } else { for(i=0;i<=P1->HighPower;i++) for(j=0;j<P2->HighPower;j++) Psum->CoeffArray[i+j]+=P1->CoeffArray[i] * P2->CoeffArray[j]; /* 多项式乘法：分分配律乘法 */ }}优点：简单易行，假设所有阶系数均不为0，对稠密型多项式（即1-N次阶系数均不为0）

缺点：对于非稠密型多项式运算缓慢

2.多项式ADT（单链表实现）（暂时不会。。。）只有一部分声明。。

// 链表实现直接不要系数为0的项,且按阶数递减排序typedef struct Node * PtrToNode;struct Node{ int Coefficient; int Power; PtrToNode Next;};typedef PtrToNode Polynomial;

3.桶式排序&基数（卡式）排序

桶式排序思想：要求N个整数排序，且已知范围为1-M。步骤： Step1 $Step 1$ ：设置一个空数组count[M] $count[M]$ ，并初始化为0数组。 Step2 $Step 2$ ：读入N $N$ 个数数列Ai $Ai$ ，并有count[Ai]++ $count[Ai]++$ 。循环完N个数 Step3 $Step 3$ ：对数组打印出顺序。规则：从count[0]到count[M]遍历，在数组第 i $i$ 个元素处输出count[M] $count[M]$ 个数字 i $i$ 基数排序思想：对一组数先计算数字最高位数A。先按个位排序，之后接着按十位排序，直到按A位排序完。（当在某次排序中，两个数的某一个位数一致时，按上一级原排序，如下面的十位排序时的125，27排序）如：一组数：64，8，216，512，27，729，0，1，343，125。按个位排序：0，1，512，343，64，125，216，27，8，729。接着按十位排序：0，1，8，512，216，125，27，729，343，64。接着按百位排序：0，1，8，27，64，125，216，343，512，729。

4.注册表 eg：要知道一个学校的每个班的注册人以及每个学生对应注册的班级可以利用如下多重表这里写图片描述

5、游标

有些编程语言，如Basic等没有指针，此时就不能基于指针来写链表了。此时引入新的ADT”游标”来代替指针，且此时要重写关于malloc与free的游标形式的函数。

注意链表有以下特性：

这里写图片描述因此，游标链表也应该具有以上特点。

游标节点的实现在游标节点实现中，引入数组实现，以下为游标节点的例子。这里写图片描述

// Cursor List// _Cursor_H.h#ifndef _Cursor_Htypedef int PtrToNode;typedef PtrToNode List;typedef PtrToNode Position;void InitializeCursorSpace(void);List MakeEmpty(List L);int Isempty(List L);int IsLast(Position P,List L);Position Find(ElementType X,List L);Position FindPrevious(ElementType X,List L);void Delete(ElementType X,List L);void Insert(ElementType X,List L,Position P);void DeleteList(List L);Position Header(List L);Position First(List L);Position Advance(Position P);ElementType Retrieve(Position P);#endif /*_Cursor_H*//* implementation file */#include '_Curvor_H.h'struct Node{ ElementType Element; Position Next; /* data */};struct CurvorSpace[ SpaceSize ]; /*SpaceSize为自定空间*//*相当于指针链表中的malloc*/static Position CurvorAlloc(void){ Position P; P=CurvorSpace[0].Next; CurvorSpace[0].Next=CurvorSpace[P].Next; return P;}/*相当于指针函数 free*/static void CurvorFree(Position P){ CurvorSpace[P].Next=CurvorSpace[0].Next; CurvorSpace.Next=P;}/*剩下游标操作函数的实现和_List_Function.c里面的差不多List MakeEmpty(List L);int Isempty(List L);int IsLast(Position P,List L);Position Find(ElementType X,List L);Position FindPrevious(ElementType X,List L);void Delete(ElementType X,List L);void Insert(ElementType X,List L,Position P);void DeleteList(List L);Position Header(List L);Position First(List L);Position Advance(Position P);ElementType Retrieve(Position P);*/

上一篇：基础算法与常用格式

下一篇：通过反射机制调用某个类的方法