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);*/

上一篇：基礎算法與常用格式

下一篇：通過反射機制調用某個類的方法