国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發(fā)設計 > 正文

Chapter_3表、棧和隊列:鏈表

2019-11-14 09:46:40
字體:
供稿:網(wǎng)友

1、單鏈表

如下圖為單鏈表示意圖: 這里寫圖片描述 只列出頭文件以及單鏈表相關函數(shù)實現(xiàn)代碼,均來源于書上,并整理出分析過程。

_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;}

重要經(jīng)驗:當編寫涉及指針的數(shù)據(jù)結構或者算法時,最好先畫出結構圖分析過程,再進行寫代碼。(其實,除了涉及指針的要,很多數(shù)據(jù)結構、圖論等相關算法都先畫圖分析,清楚思路后才碼代碼較好)

以下為分析過程圖 這里寫圖片描述 這里寫圖片描述

2、雙鏈表

雙向鏈表如下圖所示: 這里寫圖片描述 即在單鏈表的每一個節(jié)點Node結構體上,加多一個struct Node * 的指針指向上一個結構體

優(yōu)缺點

優(yōu)點:簡化刪除操作,因為有現(xiàn)成的指向前一個指針可以更改指向即可缺點:增大空間需求(代碼量),插入開銷增加一倍,有雙向指針要搞

3、循環(huán)鏈表

如下圖所示,即在單(雙)鏈表末端不接NULL,使其返回指向表頭。 如下圖為雙向循環(huán),同理也有單向循環(huán)。 這里寫圖片描述

4、幾個栗子

多項式ADT(數(shù)組實現(xiàn))//定義多項式組成typedef struct { int CoeffArray[MaxDegree+1]; int HighPower;} * Polynominal;//多項式初始化為0的操作void ZeroPolynominal(Polynominal Poly){ int i; /*系數(shù)全部變?yōu)?*/ 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]; /* 多項式乘法:分分配律乘法 */ }}優(yōu)點:簡單易行,假設所有階系數(shù)均不為0,對稠密型多項式(即1-N次階系數(shù)均不為0)

缺點:對于非稠密型多項式運算緩慢

2.多項式ADT(單鏈表實現(xiàn))(暫時不會。。。) 只有一部分聲明。。

// 鏈表實現(xiàn)直接不要系數(shù)為0的項,且按階數(shù)遞減排序typedef struct Node * PtrToNode;struct Node{ int Coefficient; int Power; PtrToNode Next;};typedef PtrToNode Polynomial;

3.桶式排序&基數(shù)(卡式)排序

桶式排序思想:要求N個整數(shù)排序,且已知范圍為1-M。 步驟: Step1:設置一個空數(shù)組count[M],并初始化為0數(shù)組。 Step2:讀入N個數(shù)數(shù)列Ai,并有count[Ai]++。循環(huán)完N個數(shù) Step3:對數(shù)組打印出順序。規(guī)則:從count[0]到count[M]遍歷,在數(shù)組第 i 個元素處輸出count[M]個數(shù)字 i基數(shù)排序思想: 對一組數(shù)先計算數(shù)字最高位數(shù)A。先按個位排序,之后接著按十位排序,直到按A位排序完。(當在某次排序中,兩個數(shù)的某一個位數(shù)一致時,按上一級原排序,如下面的十位排序時的125,27排序) 如:一組數(shù):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的游標形式的函數(shù)。

注意鏈表有以下特性:

這里寫圖片描述 因此,游標鏈表也應該具有以上特點。

游標節(jié)點的實現(xiàn) 在游標節(jié)點實現(xiàn)中,引入數(shù)組實現(xiàn),以下為游標節(jié)點的例子。 這里寫圖片描述// 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;}/*相當于指針函數(shù) free*/static void CurvorFree(Position P){ CurvorSpace[P].Next=CurvorSpace[0].Next; CurvorSpace.Next=P;}/*剩下游標操作函數(shù)的實現(xiàn)和_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);*/
上一篇:【bzoj2697】特技飛行

下一篇:C語言中#if

發(fā)表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發(fā)表
主站蜘蛛池模板: 金华市| 循化| 田林县| 武清区| 津市市| 江津市| 治多县| 洛宁县| 荔浦县| 申扎县| 涿州市| 化隆| 格尔木市| 江北区| 栖霞市| 莱西市| 敦化市| 高尔夫| 宜良县| 铜鼓县| 调兵山市| 南岸区| 将乐县| 镇原县| 新泰市| 黎平县| 德阳市| 岳普湖县| 洛宁县| 庄河市| 万源市| 兴海县| 巴青县| 崇文区| 葵青区| 建始县| 民丰县| 永善县| 射阳县| 聊城市| 满洲里市|