數(shù)據(jù)結(jié)構(gòu)知識點匯總

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第二章2.1線性表的概念及其抽象數(shù)據(jù)類型的定義2.1.1 線性表的邏輯結(jié)構(gòu)線性表的定義線性表是n個類型相同的數(shù)據(jù)元素的有限序列，對n0,除第一個元素無直接前驅(qū)，最后一個元素無直接后繼外，其余的每個數(shù)據(jù)元素只有一個直接前驅(qū)和一個直接后繼。線性表的特點：1） 同一性：線性表有同類元素數(shù)據(jù)組成，每一個必須屬于同一數(shù)據(jù)類型。2） 有窮性：線性表由有限個數(shù)據(jù)元素組成，表長就是表中數(shù)據(jù)元素的個數(shù)。3）有序性：線性表中相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系。2.1.2線性表的抽象數(shù)據(jù)類型定義抽象數(shù)據(jù)類型定義：見課本。2.2線性表的順序存儲2.2.1線性表的順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)的定義線性

2、表的順序存儲結(jié)構(gòu)是指用一組地址連續(xù)的存儲單元依次存儲線性表中的各個元素，使得線性表中在邏輯上相鄰的數(shù)據(jù)元素存儲在相鄰的物理存儲單元中，即通過數(shù)據(jù)元素物理存儲的相鄰關(guān)系來反映數(shù)據(jù)元素之間邏輯上的相鄰關(guān)系。采用順序存儲結(jié)構(gòu)的線性表通常稱為順序表。將線性表歸納為：關(guān)系線性化，節(jié)點順序存。假定順序表中有個元素，每個元素占個單元，第一個元素的地址為，則可通過如下公式計算出第個元素的地址：其中，稱為基地址。線性存儲結(jié)構(gòu)的C語言定義#define MAXSIZE 100typedef structElemType elemMAXSIZE; /*ElemType 可為int，char等*/int last;/

3、*記錄線性表中最后一個元素在數(shù)組elem 中的位置(下標值)*/Seqlist;上述為定義一個結(jié)構(gòu)體，結(jié)構(gòu)名為Seqlist。知識延伸（typedef）（C課本用typedef聲明新類型名）2.2.2 線性表順序存儲結(jié)構(gòu)上的基本運算線性表的基本運算1、 查找操作2、 插入操作3、 刪除操作4、 順序表合并算法線性表順序存儲結(jié)構(gòu)的優(yōu)缺點分析2.3 線性表的鏈式存儲鏈表定義：采用鏈式存儲結(jié)構(gòu)的線性表稱為鏈表。鏈表的分類：1） 按實現(xiàn)角度看：鏈表可分為動態(tài)鏈表和靜態(tài)鏈表。2） 按鏈接方式的角度看：鏈表可分為單鏈表、循環(huán)鏈表和雙鏈表。2.3.1 單鏈表2.3.2 單鏈表上的基本操作線性表的基本運算1、

4、 初始化單鏈表 InitList(LinkList *L) *L=(LinkList)malloc(sizeof(Node); /*建立頭結(jié)點*/ (*L)-next=NULL;/*建立空的單鏈表L*/ 注意：L是指向單鏈表的頭結(jié)點的指針，用來接收主程序中帶初始化單鏈表的頭指針變量的地址，*L相當于主程序中帶初始化單鏈表的頭指針變量。2、 建立單鏈表1）頭插法建表算法描述：從一個空表開始，重復讀入數(shù)據(jù)，生成新結(jié)點，將讀入數(shù)據(jù)存放到新節(jié)點的數(shù)據(jù)域中，然后將新節(jié)點插入到當前鏈表的表頭節(jié)點之后，直至讀入結(jié)束標志為止。單鏈表的存儲結(jié)構(gòu)：typedef struct Node /*結(jié)點類型定義，結(jié)構(gòu)體名

5、為Node*/ElemType data;struct Node * next;Node,*Linklist; /*LinkList為結(jié)構(gòu)指針類型*/LinkList與Node *同為結(jié)構(gòu)指針類型，這兩種類型是等價的。通常習慣上用LinkList說明指針變量，強調(diào)他是某個單鏈表的頭指針變量。例如，使用定義LinkList L，則L為單鏈表的頭指針，從而提高程序的可讀性。用Node *來定義指向單鏈表中節(jié)點的指針，例如，Node *p，則p為指向單鏈表中節(jié)點的指針變量。算法：typedef struct NodeElemType data;struct Node * next;Node,*Lin

6、klist;void CreatFromHead(LinkList L)Node *s;char c;int flag=1;while(flag)c=getchar();if(c!=$)s=(Node *)malloc(sizeof(Node);s-data=c;s-next=L-next;L-next=s;else flag=0;2） 尾插法建表算法描述：頭插法建立鏈表雖然簡單，但生成的鏈表中結(jié)點的次序和輸入的順序相反。若希望二者相同，可采用尾插法建表。該方法是將新節(jié)點插到當前單鏈表的尾上。為此需增加一個尾指針r，使之指向當前單鏈表的結(jié)尾。算法：typedef struct NodeElem

7、Type data;struct Node * next;Node,*Linklist;void CreatFromHead(LinkList L)Node *s,*r;r=L;char c;int flag=1;while(flag)c=getchar();if(c!=$)s=(Node *)malloc(sizeof(Node);s-data=c;r-next=s;r=s;else flag=0;r-next=NULL;3、 單鏈表查找1） 按序號查找算法描述：設帶頭結(jié)點的單鏈表的長度為n，要查找表中第i個結(jié)點，則需要從單鏈表的頭指針L出發(fā)，從頭結(jié)點(L-next)開始順著鏈域掃描，用指針

8、p指向當前掃描到的結(jié)點，初值指向頭結(jié)點,用j做計數(shù)器，累計當前掃描過的結(jié)點數(shù)(初值為0)，當j=i時，指針p所指的結(jié)點就是要找的第i個結(jié)點。算法：typedef struct NodeElemType data;struct Node * next;Node,*Linklist;Node * Get(LinkList L,int i)int j=0;Node *p;p=L:if(inext!=NULL)&(jnext;j+;if(p-next=NULL) return NULL; /*找不到i*/else return i; /*找到了i*/2） 按值查找算法描述：按值查找是指在單鏈表中查找是

9、否有節(jié)點值等于e的結(jié)點，若有的話，則返回首次找到的其值等于e的結(jié)點的存儲位置，否則返回NULL。查找過程從單鏈表的頭指針指向的頭結(jié)點出發(fā)，順著鏈逐個將結(jié)點的值和給定值e作比較。 算法：typedef struct NodeElemType data;struct Node * next;Node,*Linklist;Node *Locate(LinkList L,ElemType key)Node *p;p=L-next;while(p!=NULL)if(p-data=key)return p; /*找到了key*/p=p-next;return NULL; /*沒有找到了key*/ 4、 單

10、鏈表插入操作問題要求：在線性表的第個位置之前插入一個新元素e。算法思想：查找：在單鏈表中找到第i-1個結(jié)點并有指針pre指示。申請：申請新節(jié)點s，將其數(shù)據(jù)域的值置為e；插入掛鏈：通過修改指針域?qū)⑿鹿?jié)點s掛入單鏈表L。 算法：typedef struct NodeElemType data;struct Node * next;Node,*Linklist;void Inslist(ElemType e,int i,LinkList L)Node *pre,*s;int k;if(i=0) return ERROR;pre=L;k=0;while(pre!=NULL&knext;k+;if(k=

11、i)s=(Node *)malloc(sizeof(Node);s-data=e;s-next=pre-next;pre-next=s;return OK;elseprintf(插入位置不合理);return ERROR;5、 單鏈表刪除問題要求：將線性表的第個元素e刪除算法思想：查找：通過計數(shù)方式找到第i-1個結(jié)點并由指針pre指示；刪除第i個結(jié)點并釋放結(jié)點空間。結(jié)果：將長度為n的線性表變成長度為n-1 的線性表算法：typedef struct NodeElemType data;struct Node * next;Node,*Linklist;void DelList(LinkList

12、 L,int i,ElemType *e)Node *pre,*s;int k;if(inext!=NULL&knext;k+;if(pre-next=NULL)printf(刪除位置錯誤);return ERROR;s=pre-next; /*使得刪除得第i個位置的指針為s*/pre-next=s-next;*e=s-data;free(s); /*釋放被刪除的結(jié)點所占的內(nèi)存空間*/return OK;算法應用舉例1、 求單鏈表的長度算法描述：可以采用“數(shù)”結(jié)點的方法來求出單鏈表的長度，用指針p依次指向各個結(jié)點，從第一個元素開始“數(shù)”，一直“數(shù)”到最后一個結(jié)點(p-next=NULL).算法

13、：typedef struct NodeElemType data;struct Node * next;Node,*LinkList;int ListLength(LinkList L)Node *p;int k=0;p=L:while(p-next!=NULL)p=p-next;k+;return k;2、 求兩個集合的差已知：以單鏈表表示集合，假設集合A用單鏈表LA表示，集合B用單鏈表LB表示，設計算法求兩個集合的差，即A-B。算法思想：由集合運算的規(guī)則可知，集合的差A-B中包含所有屬于集合A而不屬于集合B的元素。具體做法是，對于集合A中的每個元素e，在集合B的鏈表LB中進行查找，若存在

14、與e相同的元素，則從LA中將其刪除。算法：typedef struct NodeElemType data;struct Node * next;Node,*LinkList;void Difference(LinkList LA,LinkList LB)Node *p,*q,*pre,*r;pre=LA;p=LA-next;while(p!=NULL)q=LB-next;while(p-data!=q-data&q!=NULL) /*查找有無相同元素*/q=q-next;if(p-data=q-data) /*有相同元素*/r=p; pre-next=p-next;/*本來pre-next=

15、p,現(xiàn)改為pre-next=p-next*/p=p-next; /*下一次判斷p-next*/free(r); /*釋放被刪除的元素的空間*/else pre=p; /*也可寫為pre=pre-next*/p=p-next;3、有兩個單鏈表LA和LB，其元素均為非遞減有序排列，編寫一個算法，將他們合并成一個單鏈表LC，要求LC也是非遞減有序排列。要求：新表LC利用現(xiàn)有的表LA和LB中的元素結(jié)點空間，而不要額外申請結(jié)點空間。例如，則。算法思想：要求利用現(xiàn)有的表LA和LB中的結(jié)點空間來建立新表LC，可通過更改結(jié)點的next域來重建新的元素之間的線性關(guān)系。為包證新表仍然遞增有序，可以利用尾插法建立單

16、鏈表的方法，只是新表中的結(jié)點不用malloc，而只要從表LA和LB中選擇合適的點插入新表LC即可。算法：typedef struct NodeElemType data;struct Node * next;Node,*LinkList;LinkList MergeLinkList(LinkList LA,LinkList LB)Node *pa,*pb,*pc;LinkList LC;/*pa和pb分別指向兩個單鏈表LA和LB中的將要判斷的結(jié)點，pc初值為LC且pc始終指向LC的表尾*/pa=LA-next;pb=LB-next;LC=LA;LC-next=NULL;/*將LC初始置為空表*

17、/pc=LC; /*pc始終指向LC的表尾*/*當兩表均未處理完時，選擇較小者*/while(pa!=NULL&pb!=NULL)if(pa-datadata)pc-next=pa;pc=pc-next;pa=pa-next;elsepc-next=pb;pc=pc-next;pb=pb-next;if(pa=NULL)/*表B未處理完*/pc-next=pb;else /*表A未處理完*/pc-next=pa;free(LB); /*表C是以表A為基礎(chǔ)，所以釋放表B*/return LC;2.3.3 循環(huán)鏈表循環(huán)鏈表：循環(huán)鏈表是一個首尾相接的鏈表。特點：將單鏈表最后一個結(jié)點的指針域由NULL

18、改為指向頭結(jié)點或線性表中的第一個結(jié)點，就得到了單鏈表形式的循環(huán)鏈表，并稱為循環(huán)單鏈表。在循環(huán)單鏈表中，表中所有結(jié)點被鏈在一個環(huán)上。 帶頭結(jié)點的循環(huán)鏈表的算法和帶頭結(jié)點的單鏈表的算法的區(qū)別僅在與算法中判別當前結(jié)點p是否為尾結(jié)點。單鏈表判別條件為，而循環(huán)單鏈表的判別條件為。例題：有兩個帶頭結(jié)點的循環(huán)單鏈表LA、LB，編寫算法，將兩個循環(huán)單鏈表合并為一個循環(huán)單鏈表，其頭指針為LA。算法思想：先找到兩個鏈表LA、LB的表尾，并分別由指針p，q指向它們，然后將第一個鏈表的尾與第二個鏈表的第一個結(jié)點鏈接起來，并修改第二表的表尾q，使它指向第一個表的頭結(jié)點。算法：typedef struct NodeEle

19、mType data;struct Node * next;Node,*LinkList;LinkList merge_1(LinkList LA,LinkList LB)Node *p,*q;p=LA;q=LB;/*尋找A的尾結(jié)點，并置為p*/while(p-next!=LA)p=p-next;/*尋找B的尾結(jié)點，并置為q*/while(q-next!=LB)q=q-next;/*修改A的尾指針，并使之為B的第一節(jié)點*/p-next=LB-next;/*修改B的尾指針，并使之為A的頭結(jié)點*/q-next=LA;free(LB);return LA;采用上面的方法，需要遍歷鏈表，找到表尾，其執(zhí)

20、行時間為。若循環(huán)單鏈表設置為尾指針表示，在實現(xiàn)上述合并時，無需循環(huán)遍歷找尾結(jié)點，只需直接修改尾結(jié)點的指針域，其執(zhí)行時間是。算法：typedef struct NodeElemType data;struct Node * next;Node,*LinkList;LinkList merge_2(LinkList RA,LinkList LB)Node *p;p=RA-next; /*記錄A的頭結(jié)點*/RA-next=RB-next-next;free(RB-next);RB-next=p;return RB; /*返回新循環(huán)鏈表的尾指針*/2.3.4 雙向鏈表雙向鏈表：給單鏈表的每個結(jié)點里再增

21、加一個指向其前驅(qū)的指針域prior。雙鏈表的結(jié)點的結(jié)構(gòu)如下圖： prior 前驅(qū)指針域數(shù)據(jù)域后繼指針域 data next雙鏈表的結(jié)構(gòu)定義如下：typedef struct DNodeElemType data;struct DNode *prior,*next;DNode,*DoubleList;設指針p指向雙鏈表中某一點，則有下式成立：1、 雙向鏈表的前插操作算法思想：欲在雙向鏈表第i個結(jié)點之前插入一個新的結(jié)點，則指針的變化情況如下圖：算法： typedef struct DNodeElemType data;struct DNode *prior,*next;DNode,*DoubleL

22、ist;int DlinkIns(DoubleList L,int i,ElemType e)DNode *p,*s;int k;if(i=0)return ERROR;p=L;k=0;while(p!=NULL&knext;k+;if(p=NULL)printf(插入位置不合理);return ERROR;s=(DNode *)malloc(sizeof(DNode);s-data=e;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;return OK; 2、 雙向鏈表的刪除操作算法思想：欲刪除雙向鏈表中的第i個結(jié)點，則指針的變化情況如下圖

23、所示：算法：typedef struct DNodeElemType data;struct DNode *prior,*next;DNode,*DoubleList;int DlinkDel(DoubleList L,int i,ElemType *e)/*將刪除的元素保存到*e中*/DNode *p;int k;if(i=0)return ERROR;p=L;k=0;while(p!=NULL&knext;k+;if(p=NULL)printf(插入位置錯誤);return ERROR;*e=p-data;p-prior-next=p-next;p-next=p-prior;free(p)

24、;return OK;3、 應用舉例例題：已知：設一個循環(huán)雙鏈表編寫一個算法將鏈表轉(zhuǎn)換為。算法思想：實際上是交換表中前兩個元素的次序。算法：typedef struct DNodeElemType data;struct DNode *prior,*next;DNode,*DoubleList;void swep(DLinkList L)DNode *p,*q,*r;p=L-next;q=p-next;r=p-prior;p-next=q-next;q-next-prior=p;p-prior=q;q-next=p;q-prior=r;L-next=q;return L;2.4 一元多項式的表

25、示及相加2.4.1 一元多項式的表示一元多項式可按升冪的形式寫成：其中，為第項的指數(shù)，是指數(shù)的項的系數(shù)，且。假設是一個一元多項式，則它可以用一個線性表來表示。即：若假設，則兩個多項式相加的結(jié)果，也可以用線性表來表示：2.4.2 一元多項式的存儲1、一元多項式的順序存儲表示2、一元多項式的鏈式存儲表示在鏈式存儲中，對一元多項式只存非零項，則該多項式中每一項由兩部分組成(指數(shù)項和系數(shù)項)，用單鏈表存儲表示的結(jié)點結(jié)構(gòu)如下圖：系數(shù)coef 指數(shù)exp指針next結(jié)點結(jié)構(gòu)定義如下： typedef struct Polynode int coef; int exp; struct Polynode *n

26、ext; Polynode,* Polylist;建立多項式鏈表：算法描述：通過鍵盤輸入一組多項式的系數(shù)和指數(shù)，用尾插法建立一元多項式鏈表。以輸入系數(shù)0為結(jié)束標志，并約定建立多項式鏈表時，總是按指數(shù)由小到大的順序排列。算法：typedef struct Polynodeint coef;int exp;Polynode *next;Polynode,*Polylist;Polylist PolyCreate()Polynode *head,*rear,*s;int c,e;/*申請頭結(jié)點*/head=(Polynode *)malloc(sizeof(Polynode);rear=head;

27、/*rear始終指向最后一個結(jié)點*/scanf(%d%d,&c,&e);while(c!=0)/*申請一個新的結(jié)點*/s=(Polynode *)malloc(sizeof(Polynode);s-coef=c;s-exp=e;rear-next=s; /*將鏈表連接起來*/rear=s; /*鏈表的結(jié)尾后移一位*/scanf(%d%d,&c,&e);rear-next=NULL;/*結(jié)束鏈表*/return head;/*返回鏈表的頭結(jié)點*/3、 兩個多項式相加運算規(guī)則：指數(shù)相同項的對應系數(shù)相加，若不為0，則構(gòu)成“和多項式”中的一項； 指數(shù)不相同的項均按升冪順序復制到“和多項式” 中。算法思

28、想：設p、q分別指向單鏈表polya和polyb的當前項，比較p、q結(jié)點的指數(shù)項，由此得到以下運算規(guī)則：1 若，則結(jié)點p所指的一項應該是“和多項式”中的一項，令指針p后移。2 若，則將兩個結(jié)點的指數(shù)相加，當和不為0時，修改結(jié)點p的系數(shù)域，釋放q結(jié)點；當和為0時，應該從polya中刪去p結(jié)點，同時釋放p和q結(jié)點。3 當，則結(jié)點q所指的一項應該是“和多項式”中的一項，將結(jié)點q插入在p之前，同時令指針q后移。算法：typedef struct Polynodeint coef;int exp;Polynode *next;Polynode,*Polylist;void PolyAdd(Polylis

29、t polya,Polylist polyb)/*p指向polya的當前比較點，q指向polyb的當前比較點tail指向和多項式的末尾點*/Polynode *p,*q,*tail,*temp;int sum;p=polya-next;q=polyb-next;tail=polya;while(p!=NULL&q!=NULL)if(p-expexp)tail-next=p;tail=p;p=p-next;else if(p-exp=q-exp)sum=p-coef+q-coef;if(sum=0)temp=p;p=p-next;free(p);temp=q;q=q-next;free(q);e

30、lsep-coef=sum;tail-next=p;tail=p;p=p-next;temp=q;q=q-next;free(temp);elsetail-next=q;tail=q;q=q-next;if(p!=NULL)tail-next=p;elsetail-next=q;return polya;假設A多項式有M項，B多項式有N項，則上述算法的時間復雜度為。2.5 順序表和鏈表的綜合比較2.5.1 順序表和鏈表的比較(課本)2.5.2 線性表鏈式存儲方式的比較2.6 總結(jié)與提高2.6.1主要知識點線性表的特征線性表中每個數(shù)據(jù)元素有且僅有一個直接前驅(qū)和直接后繼，第一個結(jié)點無前驅(qū)，最后一個

31、結(jié)點無后繼。線性表的存儲方式線性表在計算機中的存儲方式有順序存儲和鏈式存儲。線性表的順序存儲(順序表)：采用靜態(tài)分配方式，借助于C語言的數(shù)組類型，申請一組連續(xù)的地址空間，依次存放表中元素，其邏輯次序隱含在存儲順序中。線性表的鏈式存儲(鏈表)：采用動態(tài)分配方式，借助于C語言的指針類型，動態(tài)申請與動態(tài)釋放地址空間，故鏈表中的各結(jié)點的物理存儲可以是不連續(xù)的。單鏈表的操作特點（1） 順鏈操作技術(shù)：從“頭”開始，訪問單鏈表L中結(jié)點i(p指向該結(jié)點)時，由于第i個結(jié)點的地址在第i-1個結(jié)點(pre指向該結(jié)點，為p的前驅(qū))的指針域中存放，查找必須從單鏈表的“首結(jié)點”開始(p=L);通過p=p-next并輔助

32、計數(shù)器來實現(xiàn)。（2） 指針保留技術(shù)：通過對第i個結(jié)點進行插入、刪除等操作時，需要對第i-1個結(jié)點的指針域進行鏈址操作(pre-next)，因此在處理過程中始終需要維持當前指針p與其前驅(qū)指針pre的關(guān)系，將這種技術(shù)簡稱為“指針保留技術(shù)”。鏈表處理中的相關(guān)技術(shù)（1） 單鏈表與多重鏈表的差別在于指針域的個數(shù)。（2） 一般鏈表與循環(huán)鏈表的差別在于是否首尾相接，將非空表、空表等多種情況統(tǒng)一處理，以方便運算。（3） 判斷當前結(jié)點p是否是表尾。一般鏈表中，p結(jié)點是表尾結(jié)點的條件是：該結(jié)點的后繼指針值為空指針，即p-next=NULL;循環(huán)鏈表中，p結(jié)點是表尾結(jié)點的條件是：該結(jié)點的后繼指針值為頭指針值，即p-

33、next=head.（4） 鏈表的表長度并未顯示保存。由于鏈表是動態(tài)生成的結(jié)構(gòu)，其長度要通過順鏈查找到表尾得到。因此在處理鏈表時，往往是以當前處理位置是否是表尾作為控制條件，而不是以表長度n作為控制條件。2.6.2 典型例題例1：分解順序表為奇偶兩部分已知順序表L中的數(shù)據(jù)元素類型為int。設計算法將其調(diào)整為左右兩部分，左邊的元素(即排在前面的)均為奇數(shù)，右邊的所有元素(即排在后面的)均為偶數(shù)，并要求算法的時間復雜度為O(n),空間復雜度為O(1).問題分析：將位于表尾左半部分的偶數(shù)與位于表右半部分的奇數(shù)通過一個輔助變量進行交換。設置兩個位置指示器i和j，i的初值為0，j的初值為L-last.當L-elemi為偶數(shù)，L-elemj為奇數(shù)是，則將L-elemi與L-elemj交換否則，L-elemi為奇數(shù)，i+，L-elemj為偶數(shù)，j-。這樣既可以保證算法時間復雜度為0（n），亦可以保證空間復雜度為0（1）。算法：#define MaxSize 100typedef structint elemMaxSiz