數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)整理(清華大學(xué)出版社)

1、第一章緒論1 .數(shù)據(jù)Z§構(gòu)：主要研究非數(shù)值計(jì)算問(wèn)題中計(jì)算機(jī)的操作對(duì)象有哪些結(jié)構(gòu)（邏輯結(jié)構(gòu)卜這些結(jié)構(gòu)在計(jì)算機(jī)中的表示及其操作的定義和實(shí)現(xiàn)問(wèn)題。2 .邏輯結(jié)構(gòu)：不考慮實(shí)現(xiàn)，僅看問(wèn)題域中數(shù)據(jù)元素根據(jù)相互間的邏輯關(guān)系形成的結(jié)構(gòu)稱為數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)。通常說(shuō)的數(shù)據(jù)結(jié)構(gòu)即此義。分類：如書目表根據(jù)一對(duì)一相鄰關(guān)系形成線性結(jié)構(gòu)、棋盤格局間根據(jù)下棋規(guī)則（一對(duì)多）形成一個(gè)樹形數(shù)據(jù)結(jié)構(gòu)，城市間據(jù)通路（多對(duì)多）形成圖狀結(jié)構(gòu)，此外還有集合結(jié)構(gòu)（除同屬一個(gè)集合外,無(wú)其它關(guān)聯(lián)），共四類3 .數(shù)據(jù)Z勾（數(shù)據(jù)元素及關(guān)系/結(jié)構(gòu)）在計(jì)算機(jī)中的表示或者說(shuō)映像稱為該數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)或存儲(chǔ)結(jié)構(gòu)。4 .順序存儲(chǔ)結(jié)構(gòu)：關(guān)系采取順序

2、映像表示，即借助元素在存儲(chǔ)器中的位置上的“相鄰”關(guān)系隱式表示數(shù)據(jù)元素間具有關(guān)系。此時(shí)物理結(jié)構(gòu)對(duì)應(yīng)一個(gè)數(shù)組。優(yōu)點(diǎn)：可根據(jù)起始地址隨機(jī)訪問(wèn)各元素。缺點(diǎn)：需事先分配一足夠大空間，且插入刪除結(jié)點(diǎn)需移動(dòng)大量數(shù)據(jù)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：關(guān)系采取鏈?zhǔn)接诚癖硎荆唇柚郊有畔⒅羔橈@式表示元素間的關(guān)系，對(duì)應(yīng)一個(gè)鏈表。優(yōu)點(diǎn)是更有效利用空間、插入或者刪除結(jié)點(diǎn)快，但要順序訪問(wèn)各元素。5 .度量指標(biāo)：算法運(yùn)行時(shí)間主要取決于基本操作的執(zhí)行次數(shù)（頻度），執(zhí)行次數(shù)通常隨問(wèn)題規(guī)模擴(kuò)大而增加，增加越快意味著算法隨問(wèn)題規(guī)模的擴(kuò)大，運(yùn)行時(shí)間增長(zhǎng)的也快，從而該種算法效果較差；增長(zhǎng)越慢算法越好，故可用基本操作的頻度隨問(wèn)題規(guī)模的增長(zhǎng)率反映算法的效

3、率。6 .時(shí)間復(fù)雜度：頻度函數(shù)的增長(zhǎng)率基本與函數(shù)中“關(guān)鍵項(xiàng)”（去掉低次項(xiàng)和常數(shù)項(xiàng)）的增長(zhǎng)率相同，故可用“關(guān)鍵項(xiàng)”反映算法效率。假設(shè)關(guān)鍵項(xiàng)為f（n）,用T（n）=O（f（n）表示算法時(shí)間增長(zhǎng)率與f（n）增長(zhǎng)率同階。稱O（f（n）為算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。f（n）的增長(zhǎng)率為f（n+1）/f（n）,如對(duì)復(fù)雜度為O（n）的算法其運(yùn)行時(shí)間隨問(wèn)題規(guī)模增長(zhǎng)率為1+1/n,復(fù)雜度為0（1）的算法時(shí)間增長(zhǎng)率為1。7 .按增長(zhǎng)率由小至大的順序排列下列各函數(shù)（Z3）n-2100-bg2n-n"2-n-nlog2n-n32-2n-n!-nn第二章線性表1 .順序表：借助元素在存儲(chǔ)器中位置上的“

4、相鄰”關(guān)系表示數(shù)據(jù)元素間具有的關(guān)系，如此存儲(chǔ)的線性表稱為順序表。順序表優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單方便，可隨機(jī)訪問(wèn)各元素；缺點(diǎn)是插入或刪除元素時(shí)會(huì)引起大量的數(shù)據(jù)元素移動(dòng)（表尾除外）；對(duì)于長(zhǎng)度變化較大的線性表，要一次性地分配足夠的存儲(chǔ)空間，但這些空間常常得不到充分利用。2 .線性鏈表：采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表對(duì)應(yīng)一個(gè)鏈表。結(jié)點(diǎn)包含數(shù)據(jù)域和指針域兩部分。鏈表名指向第一個(gè)結(jié)點(diǎn)（頭指針），尾結(jié)點(diǎn)指針域值為NULL。鏈表優(yōu)點(diǎn)是空間利用好，插入刪除不移動(dòng)數(shù)據(jù)，表頭表尾操作快（改進(jìn)的單鏈表）,位置概念強(qiáng)；缺點(diǎn)是需要順序訪問(wèn)各元素，位序概念弱。順序表相關(guān)程序：#defineLIST_INIT_SIZE100/#define

5、LISTINCREMENT10typedef*ElemType;typedefstructElemType*elem;/存儲(chǔ)空間基址intlength;intlistsize;/SqList;SqListLa,Lb,Lc;StatusInitList_Sq(SqList&L)/構(gòu)造空線性表LL.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)if(L.elem=0)exit(OVERFLOW);L.length=0;初始化表長(zhǎng)為0,“空”表L.listsize=LIST_INIT_SIZE;初始化存儲(chǔ)容量return(OK);

6、/InitList_SqvoidListDelete(SqList&L,inti,ElemType&e)/在順序表L中刪除第i個(gè)元素，用e返回其值.小的合法值是1,ListLength(L)if(i<1|i>L.length)returnERROR;/刪除位置不合理ElemType*p=&L.elemi-1,*q=L.elem+L.length-1;e=*p;while(p<q)*p=*(p+1);+p;/刪除位置后元素左移-L.length;returnOk;/ListDelete_SqStatusListInsert_Sq(SqList&L

7、,inti,ElemTypee)/在順序表L的第i個(gè)位置前插入元素e,i的合法值為1.L.length+1if(i<1|i>L.length+1)returnERROR;/插入不合法if(L.length>=L.listsize)表滿，增加存儲(chǔ)容量ElemType*newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType)if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;ElemType*q=&a

8、mp;L.elemi-1,*p=&L.elemL.length-1;while(p>=q)線性表相關(guān)程序：typedef*ElemType;typedefstructLNodeElemTypedata;/數(shù)據(jù)域structLNode*next;/指針域LNode,*LinkList;默認(rèn)帶頭結(jié)點(diǎn)，需說(shuō)明LNodenodel;LinkListLa;StatusGetElem_L(LinkListL,inti,ElemType&e)/L為帶頭結(jié)點(diǎn)的單鏈表的頭指針。第i個(gè)元素存在時(shí)其值賦給e并返回OK,否則返回ERRORLNode*p=L->next;/p指向"

9、第1個(gè)”結(jié)點(diǎn)，intj=1;/j為指向結(jié)點(diǎn)的位序while(p&&j<i)順序查找，只要p不空且未到第i結(jié)點(diǎn)就前進(jìn)p=p->next;+j;if(!p)returnERROR;/第i個(gè)元素不存在e=p->data;/取第i個(gè)元素returnOK;StatusListInsert_L(LinkList&L,inti,ElemTypee)/向鏈表L中第i個(gè)位置插入eLNode*p=L;intj=0;/*p始終指向第j個(gè)結(jié)點(diǎn)*/while(p&&j<i-1)p=p->next;+j;/尋找第i-1個(gè)結(jié)點(diǎn)if(!p)returnER

10、ROR;LNode*temp;temp=(LNode*)Malloc(sizeof(LNode);if(!temp)exit(OVERFLOW);temp->data=e;相關(guān)兩表的歸并voidMergeList_Sq(SqListLa,SqListLb,Sqlist&Lc)歸并非降順序表La與Lb構(gòu)成非降順序表LcLc.listsize=Lc.length=La.length+Lb.length;Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType);If(!Lc.elem)exit(OVERFLOW);存儲(chǔ)分配失敗Elem

11、Type*pa=La.elem,*pb=Lb.elem,*pc=Lc.elem;ElemType*pa_last=La.elem+La.listsize-1;ElemType*pb_last=Lb.elem+La.listsize-1;while(pa<=pa_last&&pb<=pb_last)*(p+1)=*p;-p;/插入位置后的元素右移*q=e;+L.length;returnOK;/ListInsert_Stemp->next=p->next;p->next=temp;return(OK);/ListInsert_LStatusListD

12、elete_L(LinkList&L,inti,ElemType&e)LNode*p=L,*q;intj=0;/*p始終指向第j個(gè)結(jié)點(diǎn)*/while(p&&j<i-1)p=p->next;+j;/尋找第i-1個(gè)結(jié)點(diǎn),j最終為i-1,除非到表尾p空if(!p|!p->next)returnERROR;/1i個(gè)或更前結(jié)點(diǎn)不存在q=p->next;e=q->data;p->next=q->next;free(q);return(OK);/ListDelete_LStatusCreateList_L(LinkList&L

13、,intn)/逆位序輸入n個(gè)元素的值，建立帶頭結(jié)點(diǎn)的單鏈表L。LNode*p;L=(LinkList)malloc(sizeof(LNode);L->next=NULL;for(inti=1;i<=n;+i)p=(LNode*)malloc(sizeof(LNode);/LNode*等同LinkListscanf(“”->d&pQ;p->next=L->next;L->next=p;插入到表頭/CreateList_L歸并if(*pa<=*pb)*pc+=*pa+;else*pc+=*pb+;while(pa<pa_last)*pc+=*

14、pa+;/插入La剩余段while(pb<pb_last)*pc+=*pb+;/插入Lb剩余段/MergeList_SqStatusListMerge_SortedL(SortedSqListLa,SortedSqListLb,SortedSqList&Lc)/將兩個(gè)有序順序表La與Lb歸并為有序順序表Lcintla_len=ListLength_Sq(La);intlb_len=ListLength_Sq(Lb);inti=1,j=1,k=1;ElemTypea,b;InitList_Sq(Lc);while(i<=la_len&&j<=lb_len

15、)歸并GetElem_Sq(La,i,a);GetElem_Sq(Lb,j,b);if(a<b)ListInsert_Sq(Lc,k+,a);+i;3 .注意鏈表中4 .順序表的就地逆置思路：分別設(shè)兩個(gè)指針+p,-q。單鏈表的就地逆置思路：p為空StatusListInverse_Sq(SqList&L)/順序表就地逆置ElemType*p,*q;ElemTypee;p=L.elem;q=L.elem+L.length-1;while(p<q)temp=*p;*p=*q;*q=temp;+P；-q；returnOK;StatusListInverse_L(LinkList&

16、amp;L)next指針的應(yīng)用，如插入，刪除等操作各個(gè)元素的鏈接。p與q指向第一個(gè)和最后一個(gè)元素，當(dāng)令指針p指向首元結(jié)點(diǎn)，頭結(jié)點(diǎn)斷開，將p所指結(jié)點(diǎn)插入到表頭后有序順序表插入StatusListInsert_SortedSq(SqList&L,ElemTypee)/在非降順序表L中插入元素e,使得L中各元素仍然非降。注意插入位置據(jù)e求得思路：從最后一個(gè)元素開始，只要它比待插入元素大就后移。條件不成立時(shí)退出循環(huán)，將e插入當(dāng)前位置后即可。順序表插入操作莫忘表滿的處理。只要是順序表的插入操作就需要判斷是否表滿，對(duì)于鏈表則無(wú)此要求if(L.length>=L.listsize)表滿，增加存

17、儲(chǔ)容量ElemType*newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);5 .循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表的特點(diǎn)和基本操作。H/-線性表白雙向(循環(huán))鏈表存儲(chǔ)結(jié)構(gòu)-typedefstructDuLNodeElemTypedata;elseListInsert_Sq(Lc,k+,b);+j;while(i<=la_len)插入La的剩余元素GetElem_Sq(La,i+,a);ListInsert_Sq(Lc,k+,a);while(j<=lb_len)/插入Lb的剩余元

18、素GetElem_Sq(Lb,j+,b);ListInsert_Sq(Lc,k+,b);returnOK;/復(fù)雜度O(ListLength(La)+ListLength(Lb),因只在表尾插入)p<q時(shí)*p與*q互換，之后,p后移，直至思路:令指針p指向首元結(jié)點(diǎn)，頭結(jié)點(diǎn)斷開，將p所指結(jié)點(diǎn)插入到表頭后,p后移，至p空LNode*p,*q;p=L->next;L->next=NULL;while(p!=NULL)q=p->next;/令q指向p的后繼結(jié)點(diǎn)，以便以后p后移接下來(lái)兩句將p所指向節(jié)點(diǎn)插入到頭結(jié)點(diǎn)后p->next=L->next;L->next=p

19、;p=q;/q后移returnOK;if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;/下面從最后一個(gè)元素開始，只要大于e就后移,最后插入當(dāng)前位置后p=L.elem+L.length-1;while(p>=L.elem&&*p>e)*(p+1)=*p;-p;*(p+1)=e;+L.length;表長(zhǎng)力口1returnOK;要是插入刪除的相關(guān)指針操作。structDuLNode*prior;structDuLNode*next;DuLNode,*DuLinkList;StatusLi

20、stInsert_DuL(DuLinkList&L,inti,ElemType&e)/在帶頭結(jié)點(diǎn)的雙向鏈表L的第i個(gè)位置插入e,1<i<表長(zhǎng)+1DuLNode*p=L;intj=0;while(j<i-1&&p)p=p->next;+j;if(!p)returnERROR;s=(DuLNode*)malloc(sizeof(DuLNode);if(!s)exit(OVERFLOW);s->data=e;s->prior=p;s->next=p->next;記:注意分析指針改變p->next->prior

21、=s;p->next=s;/次序?qū)Y(jié)果的影響returnOK;另外看下多項(xiàng)式的相關(guān)課件，老師復(fù)習(xí)提綱上有寫這方面的代碼。第三章棧和隊(duì)列1.棧（Stack）是定義在線性結(jié)構(gòu)上的抽象數(shù)據(jù)類型，其操作類似線性表操作，但元素的插入、刪除和訪問(wèn)都必須在表的一端進(jìn)行，為形象起見(jiàn)，稱允許操作端為棧頂（Top）,另一端為棧底（base）,注意Top指向待插入位置。特性:LastInFirstOut后進(jìn)先出總是訪問(wèn)最近插入的一個(gè)按插入順序倒著訪問(wèn)。#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef ? SElemType;棧元素類型typ

22、edef structSElemType *base; 棧底指針SElemType *top; / 棧頂指針 intstacksize; 棧容量SqStackStatus InitStack(SqStack &S)構(gòu)造空棧SS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S.base)exit(OVERFLOW); 存儲(chǔ)分配失敗 S.top=S.base; / 空棧S.stacksize=STACK_INIT_SIZE;return(OK);/InitStack 復(fù)雜度 " O(1) ”Stat

23、us DestroyStack(SqStack &S)銷毀棧Sfree(S.base);S.base=NULL;S.top=NULL;S.stacksize=0;return OK; 復(fù)雜度O(1)Status ClearStack(SqStack &S)/置S為空棧S.top=S.base; return OK; 復(fù)雜度O(1)Status Push(SqStack &S, SElemType e)插入e為棧頂元素if(S.top-S.base=S.stacksi才e 判斷棧滿/棧滿則應(yīng)重新分配空間S.base=(SElemType *)realloc(S.base,

24、(S.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S.base) exit(OVERFLOW);S.top=(S.base+S.stacksize);/使彳S S.top 重新指向 棧頂，因reallocS.stacksize+=STACKINCREMENT;*S.top +=e; /top指向待插入位置return(OK);/Push ,復(fù)雜度 O(1)Status Pop(SqStack &S,SElemType &e)/若棧不空則棧頂元素出棧并用e帶回其值if(S.top=S.base return ERROR/ 判斷

25、?？?e=*(-S.top); 棧頂元素為 *(S.top-1) return OK;"/復(fù)雜度O(1)Status StackEmpty(SqStack S)if(S.top=S.base)return TRUE;elsereturn FALSE;int StackLength (SqStack S) return (S.top-S.base); Status GetTop(SqStack S,SElemType &e)if(S.top=S.base) return ERROR;e=*(S.top-1); 注意top指向待插入位置 return OK;棧的遍歷一直沒(méi)用到，可

26、以自己找找課件看。2.隊(duì)列類似線性表和棧，也是定義在線性結(jié)構(gòu)上的ADT與線性表和棧的區(qū)別在于,端進(jìn)行。類似日常生活中排隊(duì)，允許插入的一端為隊(duì)尾（rear）,允許刪除端稱隊(duì)頭元素的插入和刪除分別在表的兩（front）。特性：First In First Out 先進(jìn)先出，如操作系統(tǒng)中的作業(yè)隊(duì)列和打印任務(wù)隊(duì)列、日常生活中各類排隊(duì)業(yè)務(wù)等均可用隊(duì)列模擬。#define*QElemTypetypedefstructQNodeQElemTypedata;structQNode*next;QNode,*QueuePtr;typedefstructQueuePtrfront;/隊(duì)頭指針QueuePtrrear

27、;隊(duì)尾指針LinkQueue;/鏈隊(duì)歹UStatusInitQueue(LinkQueue&Q)/構(gòu)造一個(gè)空隊(duì)列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);Q.front->next=NULL;莫忘！returnOK;時(shí)間復(fù)雜度O(1)StatusDestroyQueue(LinkQueue&Q)銷毀隊(duì)列Q,此處不同于教材，先清空元素結(jié)點(diǎn)，后釋放頭結(jié)點(diǎn)QueuePtrp=Q.front->next;while(p)/依次釋放首元素至最后一個(gè)元素Q.front-&g

28、t;next=p->next;free(p);3.循環(huán)隊(duì)列#defineMAXQSIZE100/最大隊(duì)列長(zhǎng)度typedefstructQElemType*base;/動(dòng)態(tài)分配存儲(chǔ)空間intfront;/頭指針，隊(duì)列不空則指向隊(duì)列頭元素intrear;/尾指針，指向待插入元素位置SqQueue;StatusInitQueue(SqQueue&Q)/構(gòu)造一個(gè)空隊(duì)列QQ.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType);if(!Q.base)exit(OVERFLOW);/存儲(chǔ)分配失敗Q.front=Q.rear=0;returnOK

29、;復(fù)雜度O(1)StatusDestroyQueue(SqQueue&Q)/銷毀隊(duì)列Qfree(Q.base);Q.front=Q.rear=0;returnOK;時(shí)間復(fù)雜度O(1),比鏈隊(duì)列快p=Q.front->next;free(Q.front);Q.front=NULL;Q.rear=NULL;returnOK;/去掉下劃線部分為置空操作，復(fù)雜度O(n)StatusEnQueue(LinkQueue&Q,QElemTypee)/插入元素e為Q的新的隊(duì)尾元素QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(O

30、VERFLOW);存儲(chǔ)分配失敗p->data=e;p->next=NULL;/莫忘！!Q.rear->next=p;Q.rear=p;returnOK;/復(fù)雜度O(1)StatusDeQueue(LinkQueue&Q,QElemType&e)/若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用e返回其值”if(Q.front=Q.rear)returnERROR;空隊(duì)歹UQueuePtrp=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear=p)Q.rear=Q.front;/只1個(gè)結(jié)點(diǎn)時(shí)改

31、尾指針free(p);returnOK;/復(fù)雜度O(1)StatusClearQueue(SqQueue&Q)/將隊(duì)列Q置空Q.front=Q.rear=0;只要想等即可returnOK;/復(fù)雜度O(1)比鏈隊(duì)列快StatusEnQueue(SqQueue&Q,QElemTypee)/插入元素e為Q的新的隊(duì)尾元素，無(wú)法插入(已?t)貝U返回ERRORif(Q.rear+1)%MAXQSIZE=Q.fron0returnERROR;/判斷循環(huán)隊(duì)列滿的條件Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;/加便可能越界，故取余returnOK;時(shí)間

32、復(fù)雜度O(1)StatusDeQueue(SqQueue&Q,ElemType&e)隊(duì)列不空則刪除隊(duì)頭元素，用e帶回其值并返OK;否貝U返ERRORif(Q.rear=Q.front)returnERROR;判斷循環(huán)隊(duì)列空e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;加就可能越界，故取余returnOK;時(shí)間復(fù)雜度0(1)intQueueLength(SqQueueQ)返回隊(duì)長(zhǎng)return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE/減可能為負(fù)時(shí)間復(fù)雜度0(1),比鏈隊(duì)列快，可修改鏈隊(duì)列定義StatusQueu

33、eEmpty(SqQueueQ)判斷隊(duì)列空if(Q.rear=Q.front)returnTRUE;elsereturnFALSE;。StatusGetHead(SqQueueQ,QElemType&e)if(Q.rear=Q.front)returnERROR;e=Q.baseQ.front;returnOK;/O(1)若要修改對(duì)頭元素的值可新設(shè)SetHead(&Q,e)4.證明：若借助棧由輸入序列12f得到的輸出序列為p1p2pn(它是輸入序列的一個(gè)排列)，則在輸出序列中不可能出現(xiàn)這樣的情形：存在i<j<k使pj<pspi。思路：假設(shè)pj<pspi往

34、證i<j<k不成立。進(jìn)一步假設(shè)j<k成立，則pj在pk及pk以后的元素”入棧前已經(jīng)出棧，故pk及pk以后的元素”必然后于pj出現(xiàn)，而pi就是這樣的一個(gè)元素，其出現(xiàn)次序?yàn)閕,故i>j,從而i<j<k不成立。第四章申第五章數(shù)組和廣義表1 .三元組順序表存儲(chǔ)結(jié)構(gòu)：#defineMAXSIZE12500typedefstructinti,j;非零元的下標(biāo)ElemTypee;非零元的值Triple;/三元組類型typedefstructTripledataMAXSIZE+1;/data0不用intmu,nu,tu;/行列數(shù)與非零元個(gè)數(shù)TSMatrix;/稀疏矩陣類型c

35、ol從1變到n, T.data中。2 .初始化一個(gè)“空”的稀疏矩陣，按照目標(biāo)矩陣中的出現(xiàn)次序?qū)υ仃囍械脑刂饌€(gè)轉(zhuǎn)置，列號(hào)每次從頭至尾掃描M.data,對(duì)列標(biāo)等于col的三元組，將其行標(biāo)、列標(biāo)互換后依次放入07000360028022-73136121434281336211422-7432851-5M.cheadM.rhead3.稀疏矩陣的十字鏈表表示:typedefStructOLink*rhead,*chead;intmu,nu,tuCrossList/行頭指針與列頭指針數(shù)組4.上下三角矩陣存到一位數(shù)組的下標(biāo)轉(zhuǎn)換。相關(guān)稀疏矩陣的程序可以看看課件。第六章樹和二叉

36、樹1 .樹的結(jié)構(gòu)特點(diǎn)：樹是一個(gè)層次結(jié)構(gòu)，“有且僅有一個(gè)根結(jié)點(diǎn)無(wú)前驅(qū)(第一層)；有一或多個(gè)葉結(jié)點(diǎn)無(wú)后繼；其余結(jié)點(diǎn)有唯一前驅(qū)和若干后繼”。遞歸定義：樹由根結(jié)點(diǎn)(唯一)及該根結(jié)點(diǎn)的若干(零或多個(gè))“子樹”組成。不含任何結(jié)點(diǎn)也是樹，稱為空樹2 .樹的相關(guān)術(shù)語(yǔ)如結(jié)點(diǎn)，度，見(jiàn)P120o(1) 結(jié)點(diǎn)(node):一個(gè)數(shù)據(jù)元素及其若干指向其子樹的分支。(2) 結(jié)點(diǎn)白度(degree)、樹的度：結(jié)點(diǎn)所擁有的子樹的棵數(shù)稱為結(jié)點(diǎn)的度。樹中結(jié)點(diǎn)度的最大值稱為樹的度。(3) 葉子(left)結(jié)點(diǎn)、非葉子結(jié)點(diǎn)：樹中度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)(或終端結(jié)點(diǎn))。相對(duì)應(yīng)地，度不為0的結(jié)點(diǎn)稱為非葉子結(jié)點(diǎn)（或非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)）。除

37、根結(jié)點(diǎn)外，分支結(jié)點(diǎn)又稱為內(nèi)部結(jié)點(diǎn)。(4) 孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)、兄弟結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)（child）或子結(jié)點(diǎn)；相應(yīng)地，該結(jié)點(diǎn)是其孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)（parent）或父結(jié)點(diǎn)。3 .性質(zhì)1:在二叉機(jī)勺第i層上最多有2i-1個(gè)結(jié)點(diǎn)（降1）性質(zhì)2:深度為K的二叉樹最多有2K-1個(gè)結(jié)點(diǎn)（K>1）性質(zhì)3:對(duì)于任意一棵二叉樹BT,如果度為0的結(jié)點(diǎn)個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)個(gè)數(shù)為n2,則n0=n2+1。證：二叉樹上結(jié)點(diǎn)總數(shù)n=n0+n1+n2。二叉樹上邊的總數(shù)e=n1+2n2。根結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)都有且僅有一條邊（分支）'進(jìn)入"，故e=n-1。由此n-1=n0+n1+

38、n2-1,進(jìn)而n0=n2+1。性質(zhì)4：含n個(gè)結(jié)點(diǎn)的完全二叉樹深度為Jog2n_|+1。性質(zhì)5:若對(duì)含n個(gè)結(jié)點(diǎn)的完全二叉樹從上到下且從左至右進(jìn)行1至n的編號(hào)，則對(duì)完全二叉樹中編號(hào)為i的結(jié)點(diǎn)：（1）若i=1,則該結(jié)點(diǎn)是二叉樹的根，無(wú)雙親，否則，編號(hào)為/2的結(jié)點(diǎn)為其雙親結(jié)點(diǎn)；（2）若2i>n,則該結(jié)點(diǎn)無(wú)左孩子，否則，編號(hào)為2i的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)；（3）若2i+1>n,則該結(jié)點(diǎn)無(wú)右孩子，否則，編號(hào)為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。4 .含n個(gè)結(jié)點(diǎn)的樹中，只有度為k的分支結(jié)點(diǎn)和度為0的葉子結(jié)點(diǎn)，試求該樹含有的葉子結(jié)點(diǎn)數(shù)提示:n0+nk=n;e=knk=k（n-n0）=n-1故：n0=（nk-

39、n+1）/k5 .二叉樹是度不大于2的有序樹（每個(gè)結(jié)點(diǎn)最多兩棵子樹，子樹有左右之分）。6 .滿二叉樹：設(shè)深度為k,含2k-1個(gè)結(jié)點(diǎn)的二叉樹。結(jié)點(diǎn)數(shù)達(dá)最大。7 .完全二叉樹：設(shè)樹中含n個(gè)結(jié)點(diǎn)，它們和滿二叉樹中編號(hào)為1至n的結(jié)點(diǎn)位置上一一對(duì)應(yīng)（編號(hào)規(guī)則為由上到下，從左到右）。相比滿二叉樹僅少“最后的”若干個(gè)，不能少中間的。完全二叉樹特點(diǎn)：（1）葉子結(jié)點(diǎn)出現(xiàn)在最后2層或多或1層。（2）對(duì)于任意結(jié)點(diǎn)，若其右分支下的子孫的最大層次為L(zhǎng),則左分支下的子孫的最大層次為L(zhǎng)或L+1。8 .二叉樹順序存儲(chǔ)：將二叉樹映射到完全二叉樹上，不存在的結(jié)點(diǎn)以空標(biāo)記，之后用地址連續(xù)的存儲(chǔ)單元（一維數(shù)組）依次自上而下、自左而右

40、存儲(chǔ)完全二叉樹上的各元素.（將一般二叉樹以完全二叉樹形式存儲(chǔ)，最壞情況下k個(gè)結(jié)點(diǎn)需2k-1個(gè)單元。但適合完全二叉樹的存儲(chǔ)，操作簡(jiǎn)單方便。9 .二叉樹鏈表存儲(chǔ)：二叉鏈表包含內(nèi)容，左孩子及右孩子的指針。三叉鏈表多了一個(gè)指向雙親結(jié)點(diǎn)的指針。typedefstructBiTNodetypedefstructTriTNodeTElemTypedata;structTriTNode*parent;structBiTNode*lchild,*rchild;TElemTypedata;BiTNode,*BiTree;structTriTNode*lchild,*rchild;BiTreeT;TriTNode,

41、*TriTre10 .先（根）序遍歷：樹非空則訪問(wèn)根結(jié)點(diǎn)，后遞歸地先序遍歷其左子樹；再遞歸地先序遍歷其右子樹；空則無(wú)操作。中（根）序遍歷：樹非空則遞歸地中序遍歷根左子樹；后訪問(wèn)根結(jié)點(diǎn)，再遞歸地中序遍歷右子樹；空則無(wú)操作。后（根）序遍歷：樹非空則遞歸地后序遍歷根右子樹；后遞歸地后序遍歷右子樹，再訪問(wèn)根結(jié)點(diǎn)；空則無(wú)操作層次遍歷：由上到下，由左到右，不宜遞歸typedefstructBiTNodeTElemTypedata;structBiTNode*lchild,*rchild;BiTNode,*BiTree;BiTreeT;/typedefintTElemType;StatusCreateBiT

42、ree(BiTree&T)/遞歸創(chuàng)建二叉樹TElemTypee;scanf("%d",&e);if(e=0)T=NULL;elseT=(BiTree)malloc(sizeof(BiTNode);if(!T)exit(OVERFLOW);T->data=e;CreateBiTree(T->lchild);CreateBiTree(T->rchild);returnOK;/若元素為字符型則輸入時(shí)不可隨意加空格StatusDestroyBiTree(BiTree&T)/二叉鏈表的后序遞歸銷毀if(!T)returnOK;elseDest

43、royBiTree(T->lchild);DestroyBiTree(T->rchild);free(T);T=NULL;/不可丟！returnOK;StatusPreOrderTraverse(BiTreeT,Status(*visit)(TElemType)先序遍歷，先序輸出函數(shù)只要把(*visit)換為輸出函數(shù)if(T)if(*visit)(T->data)if(PreOrderTraverse(T->lchild,(*visit)if(PreOrderTraverse(T->rchild,(*visit)returnOKreturnERROR;elsere

44、turnOK;intTreeDepth(BiTreeT)遞歸法求樹的深度。思路：如果樹為空樹則深度為0,否則，先遞歸計(jì)算出左子樹的深度，再計(jì)算出右子樹的深度，最后，樹的深度為兩子樹深度的最大值加1if(T=NULL)d=0;elsed1=TreeDepth(T->lchild1);d2=TreeDepth(T->rchild);if(d1>d2)d=d1+1;elsed=d2+1;returnd;其余操作類似實(shí)現(xiàn)，務(wù)必掌握/遞歸求結(jié)點(diǎn)數(shù)，若二叉樹為空樹則節(jié)點(diǎn)數(shù)為0,否則先遞歸求左子樹和右子樹的節(jié)點(diǎn)數(shù)，整棵樹的節(jié)點(diǎn)數(shù)是左右子樹節(jié)點(diǎn)數(shù)之和再加1if(T=NULL)return0;

45、elsereturn1+NodeCount(T->lchild)+NodeCount(T->rchild);intLeafCount(BiTreeT)求葉子數(shù)，思路：若二叉樹為空樹則葉子節(jié)點(diǎn)數(shù)為0若二叉樹只含有一個(gè)節(jié)點(diǎn)則葉子數(shù)為1,否則先遞歸求左子樹和右子樹的葉節(jié)點(diǎn)數(shù)，整棵樹的節(jié)點(diǎn)數(shù)是左右子樹葉節(jié)點(diǎn)數(shù)之和。if(T=NULL)return0;elseif(T->lchild=NULL&&T->rchild=NULL)return1;elsereturnLeafCount(T->lchild)+LeafCount(T->rchild);Stat

46、usExchangeBiTree(BiTree&T)/二叉樹用二叉鏈表存儲(chǔ)，左右互換BiTNode*temp;if(T=NULL)returnOK;elsetemp=T->lchild;T->lchild=T->rchild;T->rchild=temp;ExchangeBiTree(T->lchild);ExchangeBiTree(T->rchild);returnOK;intNodeCount(BiTreeT)11 .由遍歷序列確定二叉樹：先序序列+中序序列：先序序列中第1個(gè)元素X為根，中序序列中唯有遍歷完X的左子樹后方訪問(wèn)X,故X之前的abc

47、必構(gòu)成X的左子樹，X之后的def必卞成X的右子樹。對(duì)于子樹類似處理，第1個(gè)在先序序列中出現(xiàn)的元素Y為該左子樹的根，中序序列中Y左側(cè)的元素構(gòu)成Y的左子樹，右側(cè)構(gòu)成右子樹，依此類推，最終可定。中序序列+后序序列：后序序列中最后一個(gè)元素為根，中序序列中該結(jié)點(diǎn)前的元素為左子樹，后的元素為右子樹。對(duì)于左/右子樹，最后一個(gè)在后序序列中出現(xiàn)的元素為子樹的根結(jié)點(diǎn)，再看中序序列，依此類推。先序輸出+后序輸出不能確定。如AB和BA。12 .二叉樹線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系，若結(jié)點(diǎn)有左子樹，則其lchild域指示其左孩子，否則令lchild域指示其前驅(qū)；若結(jié)點(diǎn)有右子樹，則其rc

48、hild域指示其右孩子，否則令rchild域指示其后繼。為了避免混淆，增加兩個(gè)標(biāo)志位LTag與RTag其為0是表示域指向孩子，為1時(shí)表示指向其前驅(qū)或者后繼。(詳細(xì)見(jiàn)課本P132)13 .二叉樹的線索化：設(shè)一棵二叉樹有n個(gè)結(jié)點(diǎn)，則有n-1條邊(指針連線)，而n個(gè)結(jié)點(diǎn)共有2n個(gè)指針域(Lchild和Rchild),顯然有n+1個(gè)空閑指針域未用。則可以利用這些空閑的指針域來(lái)存放結(jié)點(diǎn)的直接前驅(qū)和直接后繼信息。增設(shè)頭結(jié)點(diǎn)，左標(biāo)記為L(zhǎng)ink,左指針指根結(jié)點(diǎn)，右標(biāo)記為Thread,右指針指向最后被訪問(wèn)的結(jié)點(diǎn)，樹空則均指向頭結(jié)點(diǎn)。又稱雙向線索鏈表，先寫出遍歷序列，后添加頭結(jié)點(diǎn)，再據(jù)序列增加線索即可。用這種結(jié)點(diǎn)

49、結(jié)構(gòu)構(gòu)成的二叉樹的存儲(chǔ)結(jié)構(gòu)；叫做線索鏈表；指向結(jié)點(diǎn)前驅(qū)和后繼的指針叫做線索；按照某種次序遍歷，加上線索的二叉樹稱之為線索二叉樹。（數(shù)據(jù)域+ 雙親下標(biāo)域）。14 .樹的雙親表示法：以一組連續(xù)空間存儲(chǔ)結(jié)點(diǎn)，各結(jié)點(diǎn)附設(shè)指示器指示其雙親結(jié)點(diǎn)的位置線索化雙親表示法15 .樹的孩子表示法：結(jié)點(diǎn)中為其每個(gè)孩子附設(shè)一個(gè)指針。具體定義時(shí)各結(jié)點(diǎn)指針的個(gè)數(shù)可取最大，也可根據(jù)各自的度不同而不同。前者同構(gòu)，實(shí)現(xiàn)簡(jiǎn)單；后者需動(dòng)態(tài)開辟指針域，實(shí)現(xiàn)復(fù)雜但空間省。£hild1child2|由IdMAXd君tdegreechild1-childd16 .孩子雙親表示法：鏈?zhǔn)酱鎯?chǔ)與順序存儲(chǔ)結(jié)合，將各結(jié)點(diǎn)存儲(chǔ)在一個(gè)數(shù)組中，

50、每個(gè)數(shù)組元素附加一指針域指向結(jié)點(diǎn)的孩子形成的鏈表。若經(jīng)常進(jìn)行訪問(wèn)雙親結(jié)點(diǎn)的操作則可向數(shù)組元素追加雙親位置域。-I6IAy 二 A a B總'5 近、孩子雙親表示法孩子兄弟表示法17 .樹的孩子兄弟表示法（二叉鏈表存儲(chǔ)）：鏈?zhǔn)酱鎯?chǔ)，每個(gè)結(jié)點(diǎn)包括數(shù)據(jù)域和兩個(gè)指針域，左指針指向第一個(gè)孩子結(jié)點(diǎn)，右指針指向兄弟結(jié)點(diǎn).又稱二叉鏈表存儲(chǔ)法。（表示法能畫出來(lái)應(yīng)該就可以，各個(gè)存儲(chǔ)結(jié)構(gòu)應(yīng)該不會(huì)考吧，有興趣的自己找找書P135）18 .森林的孩子兄弟表示法（二叉鏈表存儲(chǔ)）：?jiǎn)晤w樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)中根結(jié)點(diǎn)的右指針必為空，若要存儲(chǔ)多顆樹組成的森林，可將后一顆樹的根結(jié)點(diǎn)看成前一顆樹根結(jié)點(diǎn)的兄弟，即將后一顆樹對(duì)應(yīng)

51、的二叉鏈表拼接到前一顆樹根結(jié)點(diǎn)的右指針上，這稱為森林的孩子兄弟表示法或二叉鏈表存儲(chǔ)法。19 .樹、森林與二叉樹的轉(zhuǎn)換：以二叉鏈表存儲(chǔ)結(jié)構(gòu)為轉(zhuǎn)換依據(jù)，將左右指針?biāo)附Y(jié)點(diǎn)理解為左右孩子結(jié)點(diǎn)則得到二叉樹；將左指針?biāo)附Y(jié)點(diǎn)理解為孩子，右指針?biāo)附Y(jié)點(diǎn)理解為當(dāng)前結(jié)點(diǎn)的兄弟則得樹或森林。20 .樹采用二叉鏈表存儲(chǔ)，對(duì)樹進(jìn)行遍歷即對(duì)二叉鏈表進(jìn)行遍歷。先序遍歷二叉鏈表（先根結(jié)點(diǎn)后左子樹再右子樹），對(duì)應(yīng)到樹上是先根，后自左到右遞歸遍歷各子樹”，稱為樹的先根序遍歷。對(duì)二叉鏈表進(jìn)彳T中序遍歷（先左子樹中根再右子樹）對(duì)應(yīng)到樹上是先從左到右各子樹，后根”，稱為樹的后根序遍歷。21 .森林采用二叉鏈表存儲(chǔ)（孩子兄弟表示法）

52、，先序遍歷二叉鏈表（先根結(jié)點(diǎn)后左子樹再右子樹），對(duì)應(yīng)到樹上為從左到右依次先根遍歷各顆樹”，稱為森林的先序遍歷。森林采用二叉鏈表存儲(chǔ)（孩子兄弟表示法），對(duì)二叉鏈表先左子樹中根再右子樹”中序遍歷，對(duì)應(yīng)到森林為從左到右依次后根遍歷各顆樹”，稱為森林的中序遍歷。22 .由樹的先根和后根遍歷序列確定樹：方法一（間接法，借助二叉鏈表）：樹的先根序列對(duì)應(yīng)二叉鏈表的先序序列、后根序列對(duì)應(yīng)二叉鏈表的中序序列，由先序序列與中序序列可確定出二叉鏈表，再根據(jù)此二叉鏈表按照孩子兄弟表示法的含義可得此二叉鏈表對(duì)應(yīng)的樹。方法二（直接法，根據(jù)先根后根）：先根序列中第1個(gè)X一定是整顆樹的根結(jié)點(diǎn)，而后根序列中唯有遍歷完X的所有子

53、樹后方訪問(wèn)X,故X必然出現(xiàn)在最后；先根序列中第二個(gè)頂點(diǎn)必然是第一個(gè)子樹的根結(jié)點(diǎn)，后根序列中該結(jié)點(diǎn)前的結(jié)點(diǎn)為此子樹中各結(jié)點(diǎn)；除去第一顆子樹中的結(jié)點(diǎn)后，先根序列中第一個(gè)結(jié)點(diǎn)必為第二顆子樹的根結(jié)點(diǎn)，而后根序列中此結(jié)點(diǎn)前的結(jié)點(diǎn)構(gòu)成第二顆子樹，以此類推，最終可確定。23 .由森林的先序和中序遍歷序列確定森林：方法一（間接法，借助二叉鏈表）:森林的先序序列對(duì)應(yīng)二叉鏈表的先序序列、中序序列對(duì)應(yīng)二叉鏈表的中序序列，由先序序列與中序序列可確定出二叉鏈表，再根據(jù)此二叉鏈表按照孩子兄弟表示法的含義可得此二叉鏈表對(duì)應(yīng)的森林方法二（直接法，根據(jù)先根后根）：先序序列中第1個(gè)X一定是第一顆樹的根結(jié)點(diǎn)，而中序序列中在遍歷完第

54、一顆樹的最后訪問(wèn)X故中序序列中X之前的結(jié)點(diǎn)構(gòu)成森林的第一顆樹，這些結(jié)點(diǎn)在先序和中序序列中的出現(xiàn)次序即為第一顆樹的先根序列和后根序列，根據(jù)樹的確定方法可得第一顆樹；除去第一顆樹的結(jié)點(diǎn)后，先序序列中余下的第一個(gè)結(jié)點(diǎn)為第二顆樹的根結(jié)點(diǎn)，中序序列中該結(jié)點(diǎn)前結(jié)點(diǎn)的構(gòu)成第二顆樹，依次類推，最終可得森林。24 .最優(yōu)二叉樹樹：設(shè)二叉樹具有n個(gè)帶權(quán)值的葉子結(jié)點(diǎn)，從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度與對(duì)應(yīng)葉子結(jié)點(diǎn)權(quán)值的乘積之和叫做二叉樹的帶權(quán)”路徑長(zhǎng)度，對(duì)于一組帶有確定權(quán)植的葉子結(jié)點(diǎn)，帶權(quán)路徑長(zhǎng)度最小的二叉樹稱為最優(yōu)二叉樹（如Huffman樹）。25 .如何構(gòu)造赫夫曼樹一赫夫曼算法：（1）創(chuàng)建n個(gè)根結(jié)點(diǎn)，權(quán)值wi,

55、W2,.,Wn,得森林T1,T2,.,Tn;（2）在森林中選取根結(jié)點(diǎn)權(quán)值最小的兩棵二叉樹歸并為新二叉樹，新二叉樹根結(jié)點(diǎn)權(quán)值為兩權(quán)值之和；（3）將新二叉樹加入森林，同時(shí)忽略被歸并的兩棵二叉樹，（4）重復(fù)（2）和（3,至森林只有一棵二叉樹。該二叉樹就是哈夫曼樹。26 .度為2的樹與二叉樹的區(qū)別：前者至少一結(jié)點(diǎn)度為2,且為無(wú)序樹；后者度主要不超過(guò)2即可，且為有序樹。第七章圖1 .定義：臨界點(diǎn)，度，入度，出度等見(jiàn)P158。2 .若無(wú)向圖G中任意兩個(gè)頂點(diǎn)之間都有路徑相通，則稱此圖為連通圖。如能找到一條含全部頂點(diǎn)的路徑則說(shuō)明是連通圖。無(wú)向圖中的極大連通子圖稱作此圖的連通分量。極大指頂點(diǎn)盡量多，頂點(diǎn)連同其關(guān)聯(lián)的邊構(gòu)