Chapter

1、单链表

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

_List_H.h // _List_H.h #ifndef _List_H struct 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 ：设置一个空数组 count[M] ，并初始化为0数组。 Step2 ：读入 N 个数数列Ai，并有 count[Ai]++ 。循环完N个数 Step3 ：对数组打印出顺序。规则：从count[0]到count[M]遍历，在数组第 i 个元素处输出count[M]个数字 i <script type="math/tex" id="MathJax-Element-30">i</script>基数排序思想： 对一组数先计算数字最高位数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_H typedef 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); */