數(shù)據(jù)結(jié)構(gòu)內(nèi)容概要

1、第一章 緒論 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算：查找、排序、插入、刪除、修改等數(shù)據(jù)的運(yùn)算：查找、排序、插入、刪除、修改等 線性結(jié)構(gòu)線性結(jié)構(gòu) 非線性結(jié)構(gòu)非線性結(jié)構(gòu) 順序存儲順序存儲 鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯?線性表線性表?xiàng)：完?duì)列棧和隊(duì)列串串樹形結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)組和廣義表數(shù)組和廣義表數(shù)據(jù)結(jié)構(gòu)的三個方面：數(shù)據(jù)結(jié)構(gòu)的三個方面：算法算法 = = 控制結(jié)構(gòu)控制結(jié)構(gòu) + + 原操作原操作 （固有數(shù)據(jù)類型的操作）算法的執(zhí)行時間算法的執(zhí)行時間 =原操作原操作(i)(i)的執(zhí)行次數(shù)的執(zhí)行次數(shù)原操作原操作(i)(i)的執(zhí)行時間的執(zhí)行時間如何估算算法的時間復(fù)雜度？如何估算算

2、法的時間復(fù)雜度？ 從算法中選取一種對于所研究的問題來說是 基本操作基本操作 的原操作，以該基本操作 在算法中重復(fù)執(zhí)行在算法中重復(fù)執(zhí)行的次數(shù)的次數(shù) 作為算法運(yùn)行時間的衡量準(zhǔn)則。void mult(int a, int b, int& c ) / 以二維數(shù)組存儲矩陣元素，c 為 a 和 b 的乘積 for (i=1; i=n; +i) for (j=1; j=n; +j) ci,j = 0; for (k=1; k=n; +k) ci,j += ai,k*bk,j; /for /mult基本操作: 乘法乘法操作時間復(fù)雜度: O(n3)例例1 1 兩個兩個矩陣相乘矩陣相乘例例2 +x; s=0;T(

3、n)=T(n)=(1)(1) T(n)= T(n)= O(n)O(n)(1)(log2n)(n)(n2)(n3)(2n) 例例3 for (i=1; i=n; +i) +x; s+=x;例例4 for( i=2; i=n; +i ) for( j=2; j=i-1; +j ) +x; ai,j=x; T(n)= T(n)= O(nO(n2 2) )2)2)(1()(nnnf change = FALSE; / change 為元素進(jìn)行交換標(biāo)志 for (j=0; j aj+1) aj aj+1; change = TRUE ; / 一趟起泡void bubble_sort(int& a, in

4、t n) / 將 a 中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。for (i=n-1, change=TRUE; i1 & change; -i) / bubble_sort基本操作: 交換交換操作時間復(fù)雜度: O(n2)例例5 5 起泡排序起泡排序四、算法的存儲空間需求四、算法的存儲空間需求算法的空間復(fù)雜度空間復(fù)雜度: : 表示隨著問題規(guī)模表示隨著問題規(guī)模 n 的增大，算的增大，算法運(yùn)行法運(yùn)行所需存儲量所需存儲量的增長率與的增長率與 g(n) 的的增長率相同。增長率相同。S(n) = O( g(n) )算法的存儲量包括：算法的存儲量包括： （1）輸入數(shù)據(jù)輸入數(shù)據(jù)所占空間； （2）程序本身程

5、序本身所占空間； （3）輔助變量輔助變量所占空間。第二章 線性表線性表的順序表示：線性表的順序表示： 用一組用一組地址連續(xù)地址連續(xù)的儲存單元的儲存單元依次依次存放存放線性表的數(shù)據(jù)元素。線性表的數(shù)據(jù)元素。 a1 a2 ai-1 ai an線性表的線性表的起始地址起始地址稱作線性表的稱作線性表的基地址基地址 (a1, , ai-1, ai, , an) 改變?yōu)楦淖優(yōu)?(a1, , ai-1, e, ai, , an)a1 a2 ai-1 ai ana1 a2 ai-1 ai ean, 表的長度增加插入操作插入操作ListInsert_Sq(&L, i, e) 21 18 30 75 42 56 8

6、721 18 30 75例如：ListInsert_Sq( L, 5, 66 ) L.length-10pppq87564266pq = &(L.elemi-1); / q 指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p;for( j=n-1; j=i-1; -j) L.elemj+1= L.elemj;L.elemj+1=e; Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在順序表L的第 i 個元素之前插入新的元素e, / i 的合法范圍為 1iL.length+

7、1 / ListInsert_Sq q = &(L.elemi-1); / q 指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移元素右移*q = e; / 插入e+L.length; / 表長增1return OK;算法時間復(fù)雜度算法時間復(fù)雜度為為: :O( ListLength(L) )if (L.length = L.listsize) / 當(dāng)前存儲空間已滿，增加分配 newbase = (ElemType *) realloc (L.elem, (L.listsize+LISTINCREM

8、ENT)*sizeof (ElemType); if (!newbase) exit(OVERFLOW); / 存儲分配失敗 L.elem = newbase; / 新基址 L.listsize += LISTINCREMENT; / 增加存儲容量if (i L.length+1) return ERROR; / 插入位置不合法考慮移動元素的平均情況考慮移動元素的平均情況: : 假設(shè)在第 i 個元素之前插入的概率為 ， 則在長度為n 的線性表中插入一個元素所需插入一個元素所需移動元素次數(shù)的期望值移動元素次數(shù)的期望值為：ip11) 1(niiisinpE11) 1(11niisinnE2n 若假

9、定假定在線性表中任何一個位置上進(jìn)行插入插入的概率的概率都是相等相等的，則移動元素的期望值移動元素的期望值為： (a1, , ai-1, ai, ai+1, , an) 改變?yōu)楦淖優(yōu)?(a1, , ai-1, ai+1, , an)ai+1 an, 表的長度減少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 刪除操作刪除操作ListDelete(&L, i, &e)Status ListDelete_Sq (SqList &L, int i, ElemType &e) / ListDelete_Sqfor (+p; p = q; +p) *(p-1) = *p; / 被刪除元素之

10、后的元素左移-L.length; /表長減1return OK;算法算法時間復(fù)雜度時間復(fù)雜度為為: : O( ListLength(L)p = &(L.elemi-1); / p 為被刪除元素的位置e = *p; /被刪除元素的值賦給 eq = L.elem+L.length-1; /表尾元素的位置 if (i L.length) return ERROR; /刪除位置不合法v優(yōu)點(diǎn)優(yōu)點(diǎn)l邏輯相鄰，物理也相鄰邏輯相鄰，物理也相鄰l可隨機(jī)存取任一元素可隨機(jī)存取任一元素l存儲空間使用緊湊存儲空間使用緊湊v缺點(diǎn)缺點(diǎn)l插入、刪除操作需要移動大量的元素插入、刪除操作需要移動大量的元素l需事先分配一定大小的

11、連續(xù)的存儲空需事先分配一定大小的連續(xù)的存儲空間間順序存儲線性表的優(yōu)缺點(diǎn)：順序存儲線性表的優(yōu)缺點(diǎn)：用一組用一組任意任意的存儲單元存儲線性表的存儲單元存儲線性表的數(shù)據(jù)元素。的數(shù)據(jù)元素。數(shù)據(jù)域 指針域結(jié)點(diǎn)以元素元素(數(shù)據(jù)元素的映象數(shù)據(jù)元素的映象) + 指針指針(指示后繼元素存儲位置指示后繼元素存儲位置) = 結(jié)點(diǎn)結(jié)點(diǎn) (表示數(shù)據(jù)元素 或 數(shù)據(jù)元素的映象數(shù)據(jù)元素的映象)ai-1線性表的操作線性表的操作ListInsert(&L, i, e) 在單鏈表中的實(shí)現(xiàn)在單鏈表中的實(shí)現(xiàn)： 有序?qū)τ行驅(qū)?改變?yōu)楦淖優(yōu)?和和 eaiai-1 Status ListInsert_L(LinkList L, int i,

12、 ElemType e) / L 為帶頭結(jié)點(diǎn)的單鏈表的頭指針，本算法為帶頭結(jié)點(diǎn)的單鏈表的頭指針，本算法 / 在鏈表中第在鏈表中第i 個結(jié)點(diǎn)之前插入新的元素個結(jié)點(diǎn)之前插入新的元素 e / LinstInsert_L算法的算法的時間復(fù)雜度時間復(fù)雜度為:O(ListLength(L)p = L; j = 0;while (p & j next; +j; / 尋找第尋找第 i-1 個結(jié)點(diǎn)個結(jié)點(diǎn)if (!p | j i-1) return ERROR; / i 大于表長或者小于大于表長或者小于1 線性表的操作線性表的操作ListDelete (&L, i, &e) 在鏈表中的實(shí)現(xiàn)在鏈表中的實(shí)現(xiàn):有序?qū)τ?/p>

13、序?qū)?和和 改變?yōu)楦淖優(yōu)?ai-1aiai+1ai-1 Status ListDelete_L(LinkList L, int i, ElemType &e) / 刪除以 L 為頭指針(帶頭結(jié)點(diǎn))的單鏈表中第 i 個結(jié)點(diǎn) / ListDelete_L算法的算法的時間復(fù)雜度時間復(fù)雜度為: O(ListLength(L)p = L; j = 0;while (p-next & j next; +j; / 尋找第 i 個結(jié)點(diǎn)，并令 p 指向其前趨if (!(p-next) | j i-1) return ERROR; / 刪除位置不合理q = p-next; p-next = q-next; / 刪

14、除并釋放結(jié)點(diǎn)e = q-data; free(q);return OK;例如：例如：逆位序逆位序輸入輸入 n n 個數(shù)據(jù)元素的值，個數(shù)據(jù)元素的值， 建立帶頭結(jié)點(diǎn)的單鏈表。建立帶頭結(jié)點(diǎn)的單鏈表。操作步驟：操作步驟：一、建立一個一、建立一個“空表空表”；二、輸入數(shù)據(jù)元素二、輸入數(shù)據(jù)元素an， 建立結(jié)點(diǎn)并插入；建立結(jié)點(diǎn)并插入；三、輸入數(shù)據(jù)元素三、輸入數(shù)據(jù)元素an-1， 建立結(jié)點(diǎn)并插入；建立結(jié)點(diǎn)并插入；ananan-1四、依次類推，直至輸入四、依次類推，直至輸入a a1 1為止。為止。void CreateList_L(LinkList &L, int n) / 逆序輸入 n 個數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)

15、的單鏈表 / CreateList_L算法的算法的時間復(fù)雜度時間復(fù)雜度為:O(Listlength(L)L = (LinkList) malloc (sizeof (LNode);L-next = NULL; / 先建立一個帶頭結(jié)點(diǎn)的單鏈表for (i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode); scanf(&p-data); / 輸入元素值 p-next = L-next; L-next = p; / 插入利用鏈?zhǔn)浇Y(jié)構(gòu)的特點(diǎn)改進(jìn)算法:void MergeList(LinkList La,LinkList &Lb,LinkList

16、&Lc)/ 算法2.12 pa=La-next;pb=Lb-next,pc; Lc=pc=La; / 用La的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn) while(pa&pb) if(pa-datadata) pc-next=pa; pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next; pc-next=pa?pa:pb; / 插入剩余段 free(Lb); / 釋放Lb的頭結(jié)點(diǎn)算法時間復(fù)雜度算法時間復(fù)雜度 v優(yōu)點(diǎn)優(yōu)點(diǎn)l它是一種動態(tài)結(jié)構(gòu)，整個存儲空間它是一種動態(tài)結(jié)構(gòu)，整個存儲空間為多個鏈表共用為多個鏈表共用l不需預(yù)先分配空間不需預(yù)先分配空間l插入、刪除操作方

17、便插入、刪除操作方便v缺點(diǎn)缺點(diǎn)l指針占用額外存儲空間指針占用額外存儲空間l不能隨機(jī)存取，查找速度慢不能隨機(jī)存取，查找速度慢鏈?zhǔn)酱鎯€性表的優(yōu)缺點(diǎn)：鏈?zhǔn)酱鎯€性表的優(yōu)缺點(diǎn)： 最后一個結(jié)點(diǎn)的指針域的指針又指回第最后一個結(jié)點(diǎn)的指針域的指針又指回第一個結(jié)點(diǎn)的鏈表。一個結(jié)點(diǎn)的鏈表。 a1 a2 . an 循環(huán)鏈表循環(huán)鏈表 和單鏈表的差別僅在于，判別鏈表中最后一個結(jié)點(diǎn)的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點(diǎn)”。四、其他形式的鏈表四、其他形式的鏈表雙向鏈表雙向鏈表typedef struct DuLNode ElemType data; / 數(shù)據(jù)域 struct DuLNode *prior;

18、/ 指向前驅(qū)的指針域 struct DuLNode *next; / 指向后繼的指針域 DuLNode, *DuLinklist; priordatanextbcapp-prior-next= p= p-next-proir; a1 a2 . an雙向循環(huán)鏈表雙向循環(huán)鏈表空表空表非空表非空表ai-1aies-prior= p-prior; p-prior -next=s;s-next = p; p-prior = s ;psai-1aiv插入操作插入操作實(shí)現(xiàn)：實(shí)現(xiàn)：一維數(shù)組一維數(shù)組sMtop123450進(jìn)棧進(jìn)棧Push(&S, e)A棧滿BCDEF設(shè)數(shù)組維數(shù)為Mtop=base,棧空，此時出棧

19、，則下溢（underflow)top=M,棧滿，此時入棧，則上溢（overflow)toptoptoptoptop123450空空棧棧topbasebasetoptop出棧出棧Pop(&S,&e)123450ABCDEFtoptoptoptop棧空basetoptop棧底指針base,始終指向棧底位置；棧頂指針top,其初值指向棧底，始終在棧頂元素的下一個位置ai-1v刪除操作刪除操作aiai+1p-prior-next = p-next;p-next-prior = p-prior;pai-1第三章 棧和隊(duì)列 Status Push (SqStack &S, SElemType e) if

20、(S.top - S.base = S.stacksize) /棧滿，追加存儲空間 S.base = (SElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (SElemType); if (!S.base) exit (OVERFLOW); /存儲分配失敗 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top + + = e; return OK; Status Pop (SqStack &S, SElemType &e)

21、/ 若棧不空，則刪除S的棧頂元素， / 用e返回其值，并返回OK； / 否則返回ERROR if ( S.top = S.base ) return ERROR; e = *- -S.top; return OK;實(shí)現(xiàn)：實(shí)現(xiàn)：用一維數(shù)組實(shí)現(xiàn)用一維數(shù)組實(shí)現(xiàn)baseM123450空隊(duì)列rear=0 front=0J1J2J3rearrear123450J4,J5,J6入隊(duì)J4J5J6frontrearrear123450frontJ1,J2,J3入隊(duì)rear123450J1,J2,J3出隊(duì)J1J2J3frontfrontfrontfrontv存在問題：存在問題：l當(dāng)當(dāng)front=0,rear=M時

22、，再有元素入隊(duì)發(fā)生溢出時，再有元素入隊(duì)發(fā)生溢出真溢出真溢出l當(dāng)當(dāng)front0,rear=M時，再有元素入隊(duì)發(fā)生溢出時，再有元素入隊(duì)發(fā)生溢出假溢出假溢出v解決方案解決方案l隊(duì)首固定，每次出隊(duì)剩余元素向下移動隊(duì)首固定，每次出隊(duì)剩余元素向下移動浪費(fèi)時間浪費(fèi)時間l循環(huán)隊(duì)列循環(huán)隊(duì)列u 基本思想：把隊(duì)列基本思想：把隊(duì)列設(shè)想成環(huán)形設(shè)想成環(huán)形，讓，讓base0接在接在baseM-1 之后，若之后，若rear+1=M,則令則令rear=0;u實(shí)現(xiàn)：利用實(shí)現(xiàn)：利用“模?！边\(yùn)算運(yùn)算u入隊(duì)：入隊(duì)： baserear = e; rear = (rear+1)%M; u出隊(duì)：出隊(duì)： e = basefront; fron

23、t = (front+1)%M; u隊(duì)滿、隊(duì)空判定條件隊(duì)滿、隊(duì)空判定條件012345rearfrontJ5J6J7012345rearfrontJ4J9J8J4,J5,J6出隊(duì)J7,J8,J9入隊(duì)隊(duì)空：隊(duì)空：front=rear隊(duì)滿：隊(duì)滿：front=rear解決方案：解決方案：1.另外另外設(shè)一個標(biāo)志位設(shè)一個標(biāo)志位以區(qū)別隊(duì)空、隊(duì)滿以區(qū)別隊(duì)空、隊(duì)滿2.少用一個元素空間少用一個元素空間： 隊(duì)空：隊(duì)空：front=rear 隊(duì)滿：隊(duì)滿：(rear+1)%M=front3.使用一個計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)使用一個計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)J5J6012345rearfront初始狀態(tài)J4Status

24、 EnQueue (SqQueue &Q, QElemType e) / 插入元素e為Q的新的隊(duì)尾元素 if (Q.rear+1) % MAXQSIZE = Q.front) return ERROR; /隊(duì)列滿 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK; Status DeQueue (SqQueue &Q, QElemType &e) / 若隊(duì)列不空，則刪除Q的隊(duì)頭元素， / 用e返回其值，并返回OK; 否則返回ERROR if (Q.front = Q.rear) return ERROR; e = Q.bas

25、eQ.front; Q.front = (Q.front+1) % MAXQSIZE; return OK; Status Push (SqStack &S, SElemType e) if (S.top - S.base = S.stacksize) /棧滿，追加存儲空間 S.base = (SElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (SElemType); if (!S.base) exit (OVERFLOW); /存儲分配失敗 S.top = S.base + S.stacksize;

26、S.stacksize += STACKINCREMENT; *S.top + + = e; return OK; Status Pop (SqStack &S, SElemType &e) / 若棧不空，則刪除S的棧頂元素， / 用e返回其值，并返回OK； / 否則返回ERROR if ( S.top = S.base ) return ERROR; e = *- -S.top; return OK;Status EnQueue (SqQueue &Q, QElemType e) / 插入元素e為Q的新的隊(duì)尾元素 if (Q.rear+1) % MAXQSIZE = Q.front) ret

27、urn ERROR; /隊(duì)列滿 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK; Status DeQueue (SqQueue &Q, QElemType &e) / 若隊(duì)列不空，則刪除Q的隊(duì)頭元素， / 用e返回其值，并返回OK; 否則返回ERROR if (Q.front = Q.rear) return ERROR; e = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE; return OK;第四章 串Concat (&T, S1, S2) /串聯(lián)接串聯(lián)接 初始條件

28、：初始條件：串串S1和和S2存在。存在。 操作結(jié)果：操作結(jié)果：用用T返回由返回由S1和和S2聯(lián)接而聯(lián)接而成的新串。成的新串。Concat(&T, data, structure )T=datastructureSubString (&Sub, S, pos, len) /求子串求子串子串：子串：由串中由串中任意個連續(xù)任意個連續(xù)的字符組成的字符組成的子序列。的子序列。主串：主串：包含子串的串。包含子串的串。 如：如：A= BEIJING B= JING SubString (&Sub, S, pos, len) /求子串求子串 初始條件：初始條件：串串S存在，存在，1posStrLength(S

29、)且且0lenStrLength(S)-pos+1。 操作結(jié)果：操作結(jié)果：用用Sub返回串返回串S的第的第pos個字符起個字符起長度為長度為len的子串。的子串。SubString(&sub, data structure, 6, 9)Sub=structureIndex (S, T, pos) /串定位串定位 初始條件：初始條件：串串S和和T存在，存在，T是非空串，是非空串， 1posStrLength(S)。 操作結(jié)果：操作結(jié)果：若主串若主串S中存在和串中存在和串T值相同值相同的子串的子串, 則返回它在主串則返回它在主串S中中第第pos個字符之個字符之后后第一次第一次出現(xiàn)的位置出現(xiàn)的位置;

30、 否則函數(shù)值為否則函數(shù)值為0。假設(shè)：假設(shè)： S = abcaabcaaabc , T = bca Index(S, T, 1) = 2；Index(S, T, 3) = 6；Index(S, T, 8) = 0；Replace (&S, T, V) /串替換串替換 初始條件：初始條件：串串S,T和和V存在，存在，T是非空串。是非空串。 操作結(jié)果：操作結(jié)果：用用V替換主串替換主串S中出現(xiàn)的所有中出現(xiàn)的所有與與T相等的相等的不重疊不重疊的子串。的子串。例如：例如：S=abcaabc, T=ab, V=xS=xcaxcV=bcS=bccabccStrInsert (&S, pos, T) 初始條件：

31、初始條件：串串S和和T存在，存在， 1posStrLength(S)1。 操作結(jié)果：操作結(jié)果：在串在串S的第的第pos個字符之前個字符之前插入串插入串T。例如：例如：Sgod， StrInsert (S, 2, o)S=goodStrDelete (&S, pos, len) 初始條件：初始條件：串串S存在，存在， 1posStrLength(S)-len+1。 操作結(jié)果：操作結(jié)果：從串從串S中刪除第中刪除第pos個字符起個字符起 長度為長度為len的子串。的子串。例如例如：S= structure， StrDelete( S, 1, 5)S=ture2.串比較串比較Int StrCompar

32、e(Hstring S,Hstring T) /若ST，則返回值0; 若S=T，則返回值=0；若ST，則返回值0 for(i=0; iS.length & iT.length; +i) if (S.chi!=T.chi) return S.chi-T.chi; Return S.length - T.length; / StrCompareint Index(SString S, SString T, int pos) / 返回子串T在主串S中第pos個字符之后的位置。若不存在，/ 則函數(shù)值為0。其中，T非空，1posStrLength(S)。i = pos; j = 1; while (i

33、= S0 & j T0) return i-T0; else return 0; / Index 最壞情況O(m*n)實(shí)例演示實(shí)例演示第五章 數(shù)組稱為基地址或基址以“行序?yàn)橹餍颉钡拇鎯τ诚?二維數(shù)組A中任一元素ai j 的存儲位置 LOC(i,j) = LOC(0,0) + (nij) L 以“列序?yàn)橹餍颉钡拇鎯τ诚?二維數(shù)組A中任一元素ai j 的存儲位置 LOC(i,j) = LOC(0,0) + (mji) L 5.3.1 特殊矩陣特殊矩陣 特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣。 對稱矩陣元素滿足條件 aij=aji 1=i , j=n的n階矩陣。按行序?yàn)橹餍颍?a11 a

34、12 . . a1n a21 a22 . . a2n an1 an2 . ann . a11 a21 a22 a31 a32 an1 ann . k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 jiijjjijiik, 12/ ) 1(12/ ) 1(，三角矩陣三角矩陣按行序?yàn)橹餍颍篖oc( aij)=Loc(a11)+ i*(i-1)/2 +(j-1)*L a11 0 0 . 0 a21 a22 0 . 0 an1 an2 an3. ann . 0a11 a21 a22 a31 a32 an1 ann . k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 3 對

35、角矩陣若矩陣中所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中，區(qū)域外的值全為0，則稱為對角矩陣。常見的有三對角矩陣、五對角矩陣、七對角矩陣等。例如，圖5-3為77的三對角矩陣（即有三條對角線上元素非0）。圖5-3 一個77的三對角矩陣66655655544544433433322322211211100100000000000000000000000000000000aaaaaaaaaaaaaaaaaaa6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j e0 1 2 3 4 5 6 7 8760007001500

36、0001800000240001400003000000000009120M稀疏矩陣的三元表示方法二：快速轉(zhuǎn)置 按M.data中三元組次序轉(zhuǎn)置，轉(zhuǎn)置結(jié)果放入T.data中恰當(dāng)位置。 此法關(guān)鍵是要預(yù)先確定M中每一列第一個非零元在T.data中位置，為確定這些位置，轉(zhuǎn)置前應(yīng)先求得M的每一列中非零元個數(shù)。實(shí)現(xiàn)：設(shè)兩個數(shù)組numcol：表示矩陣M中第col列中非零元個數(shù)cpotcol：指示M中第col列第一個非零元在T.data中位置顯然有：cpot1=1;cpotcol=cpotcol-1+numcol-1; (2col M.nu)7600070015000001800000240001400003

37、000000000009120M6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j e0 1 2 3 4 5 6 7 8for (col=1; col=M.nu; +col) numcol = 0;for (t=1; t=M.tu; +t) +numM.datat.j;cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1; Col 1 2 3 4 5 6 7Numcolcpotcolt1t1t1t1t2t2t2t10 01 3 5

38、7 8 8 96 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j e0 1 2 3 4 5 6 7 8M.datai j e0 1 2 3 4 5 6 7 8T.datacolnumcolcpotcol1122323524715806817907 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 pppppppp4629753Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) T.mu = M.n

39、u; T.nu = M.mu; T.tu = M.tu; if (T.tu) for (col=1; col=M.nu; +col) numcol = 0; for (t=1; t=M.tu; +t) +numM.datat.j; cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1; for (p=1; p=M.tu; +p) / 轉(zhuǎn)置矩陣元素 col = M.datap.j; q = cpotcol; T.dataq.i =M.datap.j; T.dataq.j =M.datap.i; T.dataq.

40、e =M.datap.e; +cpotcol; / for / if return OK; / FastTransposeSMatrixT(n)=O(nu+tu)T(n)=O(mu*nu)第六章 樹與二叉樹 性質(zhì)性質(zhì) 1 ： 在二叉樹的第在二叉樹的第 i 層上至多有層上至多有2i-1 個結(jié)個結(jié) 點(diǎn)。點(diǎn)。 (i1) 用歸納法證明用歸納法證明： 歸納基歸納基： 歸納假設(shè)：歸納假設(shè)： 歸納證明：歸納證明：i = 1 層時，只有一個根結(jié)點(diǎn)： 2i-1 = 20 = 1；二叉樹上每個結(jié)點(diǎn)至多有兩棵子樹，則第 i 層的結(jié)點(diǎn)數(shù) = 2i-2 2 = 2i-1 。假設(shè)對所有的 j，1 j i，命題成立； 性質(zhì)

41、性質(zhì) 2 ： 深度為深度為 k 的二叉樹上至多含的二叉樹上至多含 2k-1 個結(jié)點(diǎn)（個結(jié)點(diǎn)（k1）。）。證明：證明： 基于上一條性質(zhì)，深度為基于上一條性質(zhì)，深度為 k 的二叉樹的二叉樹上的結(jié)點(diǎn)數(shù)至多為上的結(jié)點(diǎn)數(shù)至多為 20+21+ +2k-1 = 2k-1 性質(zhì)性質(zhì) 3 ： 對任何一棵二叉樹，若它含有對任何一棵二叉樹，若它含有n0 個個葉子結(jié)點(diǎn)、葉子結(jié)點(diǎn)、n2 個度為個度為 2 的結(jié)點(diǎn)，則必存的結(jié)點(diǎn)，則必存在關(guān)系式：在關(guān)系式：n0 = n2+1。證明：證明：設(shè) 二叉樹上結(jié)點(diǎn)總數(shù) n = n0 + n1 + n2又 二叉樹上分支總數(shù) b = n1+2n2 而 b = n-1 = n0 + n1

42、+ n2 - 1由此， n0 = n2 + 1 。兩種特殊形式的二叉樹兩種特殊形式的二叉樹v滿二叉樹滿二叉樹l定義定義：指的是深度為指的是深度為k且含有且含有2k-1個結(jié)個結(jié)點(diǎn)的二叉樹。點(diǎn)的二叉樹。l特點(diǎn)：特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。1231145891213671014151234567v 完全二叉樹完全二叉樹l定義：定義：樹中所含的樹中所含的 n 個結(jié)點(diǎn)和滿二叉樹中編個結(jié)點(diǎn)和滿二叉樹中編號為號為 1 至至 n 的結(jié)點(diǎn)一一對應(yīng)。的結(jié)點(diǎn)一一對應(yīng)。l特點(diǎn)：特點(diǎn)：u葉子結(jié)點(diǎn)只可能在葉子結(jié)點(diǎn)只可能在層次最大的兩層層次最大的兩層上出現(xiàn)上出現(xiàn)u對任一結(jié)點(diǎn)，若其對

43、任一結(jié)點(diǎn)，若其右分支右分支下子孫的最大層下子孫的最大層次為次為 L，則其則其左分支左分支下子孫的最大層次必下子孫的最大層次必為為L 或或L+1。123114589126710123456性質(zhì)性質(zhì) 4 ： 具有具有 n 個結(jié)點(diǎn)的完全二叉樹的個結(jié)點(diǎn)的完全二叉樹的深度深度為為 log2n +1 。證明：證明：設(shè)完全二叉樹的深度為 k ，則根據(jù)第二條性質(zhì)得 2k-1-1 n 2k-1 或 2k-1 n 2k 即 k-1 log2 n n，則該結(jié)點(diǎn)無左孩子，則該結(jié)點(diǎn)無左孩子， 否則，編號為否則，編號為 2i 的結(jié)點(diǎn)為其的結(jié)點(diǎn)為其左孩子左孩子結(jié)點(diǎn)；結(jié)點(diǎn)；(3) 若若 2i+1n，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)，則該

44、結(jié)點(diǎn)無右孩子結(jié)點(diǎn)， 否則，編號為否則，編號為2i+1 的結(jié)點(diǎn)為其的結(jié)點(diǎn)為其右孩子右孩子結(jié)點(diǎn)。結(jié)點(diǎn)。+/a*befcd先序遍歷：中序遍歷：后序遍歷：層次遍歷：- + a * b - c d / e f-+a*b-cd/ef-+ a*b-cd/ef-+a*b-c d/e f五五、遍歷算法的應(yīng)用舉例遍歷算法的應(yīng)用舉例v 統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個數(shù)統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個數(shù) (先序遍歷先序遍歷)v 求二叉樹的深度求二叉樹的深度(后序遍歷后序遍歷)v 建立二叉樹的存儲結(jié)構(gòu)建立二叉樹的存儲結(jié)構(gòu)例如例如: :以空白字符以空白字符“ ”“ ”表示表示ABCDA(B( ,C( , ),D( , )空樹空樹只含一

45、個根結(jié)點(diǎn)只含一個根結(jié)點(diǎn)的二叉樹的二叉樹A以字符串以字符串“A ” ”表示表示以下列字符串表示以下列字符串表示: :Status CreateBiTree(BiTree &T) scanf(&ch); if (ch= = ) T = NULL; else if (!(T = (BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW); T-data = ch; / 生成根結(jié)點(diǎn) CreateBiTree(T-lchild); / 構(gòu)造左子樹 CreateBiTree(T-rchild); / 構(gòu)造右子樹 return OK; / CreateBiTreev統(tǒng)計(jì)

46、二叉樹中葉子結(jié)點(diǎn)的個數(shù)統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個數(shù)算法基本思想算法基本思想: : 先序先序( (或中序或后序或中序或后序) )遍歷二叉樹，在遍歷二叉樹，在遍歷過程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。遍歷過程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。 由此，需在遍歷算法中增添一個由此，需在遍歷算法中增添一個“計(jì)計(jì)數(shù)數(shù)”的參數(shù)，并將算法中的參數(shù)，并將算法中“訪問結(jié)點(diǎn)訪問結(jié)點(diǎn)”的操作改為：的操作改為：若是葉子，則計(jì)數(shù)器增若是葉子，則計(jì)數(shù)器增1 1。void CountLeaf (BiTree T, int& count) if ( T ) if (!T-lchild)& (!T-rchild) count+; / 對葉子結(jié)點(diǎn)計(jì)數(shù)

47、CountLeaf ( T-lchild, count); CountLeaf ( T-rchild, count); / if / CountLeafv求二叉樹的深度求二叉樹的深度( (后序遍歷后序遍歷) )算法基本思想算法基本思想: : 從二叉樹深度的定義可知，二叉樹的二叉樹的深度應(yīng)為其左、右子樹深度的最大值加深度應(yīng)為其左、右子樹深度的最大值加1 1。由此，需先分別求得左、右子樹的深度，需先分別求得左、右子樹的深度，算法中“訪問結(jié)點(diǎn)”的操作為：求得左、求得左、右子樹深度的最大值，然后加右子樹深度的最大值，然后加1 1。 首先分析二叉樹的深度二叉樹的深度和它的左左、右右子樹深度子樹深度之間的

48、關(guān)系。int Depth (BiTree T ) / 返回二叉樹的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight) ; return depthval;ABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：BCAED帶頭結(jié)點(diǎn)的中序線索二叉樹 0 1 A B D C ET中序序列：BCAED中序線索二叉樹0

49、000111111void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e) p = T-lchild; / p指向根結(jié)點(diǎn) while (p != T) / 空樹或遍歷結(jié)束時，p=T while (p-LTag=Link) p=p-lchild; /第一個結(jié)點(diǎn) if ( !Visit(p-data) return ERROR; while (p-RTag=Thread & p-rchild!=T) p = p-rchild; Visit(p-data); / 訪問后繼結(jié)點(diǎn) p = p-rchild; / p進(jìn)至其右子樹根 /

50、 InOrderTraverse_ThrABCDEFGHIJABCDEFGHIJv森林轉(zhuǎn)換成二叉樹森林轉(zhuǎn)換成二叉樹ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJv二叉樹轉(zhuǎn)換成森林二叉樹轉(zhuǎn)換成森林ABCDEFGHIJ例：例：已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符，其概率分別是種字符，其概率分別是 0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，試設(shè)計(jì)赫夫曼編碼。試設(shè)計(jì)赫夫曼編碼。297853111423設(shè)權(quán)設(shè)權(quán)w(5,29,7,8,14,23,3,11)000000011111

51、1100010011001111011011101111第七章 圖例例G12413例例15324G100110001011101010101010100001100000000110特點(diǎn)：特點(diǎn)：v 無向圖無向圖的鄰接矩陣對稱，可壓縮存儲；有的鄰接矩陣對稱，可壓縮存儲；有n個頂點(diǎn)的無向圖需存儲空間為個頂點(diǎn)的無向圖需存儲空間為n(n+1)/2。v 有向圖有向圖鄰接矩陣不一定對稱；有鄰接矩陣不一定對稱；有n個頂點(diǎn)的個頂點(diǎn)的有向圖需存儲空間為有向圖需存儲空間為n。v 無向圖中頂點(diǎn)無向圖中頂點(diǎn)Vi的度的度TD(Vi)是鄰接矩陣是鄰接矩陣A中中第第i行行(或第或第i列列)元素之和。元素之和。v 有向圖中，

52、有向圖中，l頂點(diǎn)頂點(diǎn)Vi的的出度出度是是A中第中第i行元素之和。行元素之和。l頂點(diǎn)頂點(diǎn)Vi的的入度入度是是A中第中第i列元素之和。列元素之和。6183624127845375例例1452375318642 網(wǎng)絡(luò)的鄰接矩陣可定義為：網(wǎng)絡(luò)的鄰接矩陣可定義為：，其它VRjiAijjijiv,v或)v,(v若,例例G2BDAC例例AECBDG10123ACDB 2 1 3 00123ACDB 1 4 2 34E 3 20 41 0 2 1特點(diǎn)：特點(diǎn)：v 若無向圖中有若無向圖中有n個頂點(diǎn)、個頂點(diǎn)、e條邊，則它的條邊，則它的鄰接表需鄰接表需n個頭結(jié)點(diǎn)和個頭結(jié)點(diǎn)和2e個表結(jié)點(diǎn)。個表結(jié)點(diǎn)。v 無向圖無向圖中頂

53、點(diǎn)中頂點(diǎn)Vi的度為第的度為第i個單鏈表中的個單鏈表中的結(jié)點(diǎn)數(shù)。結(jié)點(diǎn)數(shù)。v 有向圖有向圖中中l(wèi)頂點(diǎn)頂點(diǎn)Vi的出度為第的出度為第i個單鏈表中的結(jié)點(diǎn)個數(shù)。個單鏈表中的結(jié)點(diǎn)個數(shù)。l頂點(diǎn)頂點(diǎn)Vi的入度為整個的入度為整個單鏈表中鄰接點(diǎn)域值是單鏈表中鄰接點(diǎn)域值是i的結(jié)點(diǎn)個數(shù)。的結(jié)點(diǎn)個數(shù)。v逆鄰接表：有向圖中對每個結(jié)點(diǎn)建立以逆鄰接表：有向圖中對每個結(jié)點(diǎn)建立以Vi為頭的弧的單鏈表。為頭的弧的單鏈表。例例G2BDAC0123ACD B 3 0 0 2V0V1V3V4V2V6V5V7例例深度遍歷：V00123v0v2v3v1 1 6 7 24v4 5 3 0 4 0 1 7 1v5v6v7567 6 2 5 2 4

54、 3V2 V6 V5V1V4V7 V3truetruetruetruetruetruetruetrue void BFSTraverse(Graph G, Status (*Visit)(int v) for (v=0; vG.vexnum; +v) visitedv = FALSE; /初始化訪問標(biāo)志 InitQueue(Q); / 置空的輔助隊(duì)列Q for ( v=0; vG.vexnum; +v ) if ( !visitedv) / v 尚未訪問 / BFSTraverse visitedv = TRUE; Visit(v); / 訪問vEnQueue(Q, v); / v入隊(duì)列whi

55、le (!QueueEmpty(Q) DeQueue(Q, u); / 隊(duì)頭元素出隊(duì)并置為u for(w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G,u,w) if ( ! visitedw) visitedw=TRUE; Visit(w); EnQueue(Q, w); / 訪問的頂點(diǎn)w入隊(duì)列 / if / whileV0V1V3V4V2V6V5V7例例廣度遍歷：V00123v0v2v3v1 1 6 7 24v4 5 3 0 4 0 1 7 1v5v6v7567 6 2 5 2 4 3V2 V1 V6V5V4V3V7TTTv0 v2v1 v6TTTTTTT

56、TTTTTTTTTTv5 v4TTTTTTv3v7abcdegf195141827168213ae12dcb7closedge0123456AdjvexLowcostaaa19141814例如例如:e12ee8168d3dd7213c5 5 a b c d e f g具體做法具體做法: 先構(gòu)造一個只含 n 個頂點(diǎn)的子圖 SG，然后從權(quán)值最小的邊開始，若它的添加不使SG 中產(chǎn)生回路，則在 SG 上加上這條邊，如此重復(fù)，直至加上 n-1 條邊為止?？紤]問題的出發(fā)點(diǎn)考慮問題的出發(fā)點(diǎn): 為使生成樹上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小。克魯斯卡爾算法的基本思想：克魯斯卡爾算法的

57、基本思想：abcdegf195141827168213ae12dcbgf7148531621例如例如: :712181932104例例v1v2v3v4v5v6050122indegree 4 4 3 2adjvex nextarc 3 1 41 30v1v2v3v4v5v6data012345i拓?fù)溆行蛐蛄校簐6p2p1iv1p03p02p1ipv31p01iv2iv4p04iv57.5.2 關(guān)鍵路徑關(guān)鍵路徑一、問題提出一、問題提出: 假設(shè)以有向網(wǎng)有向網(wǎng)表示一個施工流圖，弧上的權(quán)值表示完成該項(xiàng)子工程所需時間。問題：問題：(1) 完成整項(xiàng)工程至少需要多少時間？(2) 哪些活動是影響工程進(jìn)度的關(guān)鍵

58、？a2=4V8V9V7V6V4V5V3V2V1a1=6a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4二、定義二、定義 AOE網(wǎng)網(wǎng)(Activity On Edge)：即邊表示活動 的網(wǎng)。AOE網(wǎng)是一個帶權(quán)的有向無環(huán)圖， 其中頂點(diǎn)頂點(diǎn)表示事件，弧弧表示活動，權(quán)權(quán)表示 活動持續(xù)時間。整個工程完成的時間整個工程完成的時間：從源點(diǎn)源點(diǎn)到匯匯點(diǎn)點(diǎn)的最長路徑最長路徑。關(guān)鍵路徑：關(guān)鍵路徑：路徑長度最長的路徑。關(guān)鍵活動：關(guān)鍵活動：關(guān)鍵路徑上的活動。該弧上的權(quán)值增加將使有向圖上的最長路徑的長度增加。a2=4V8V9V7V6V4V5V3V2V1a1=6a3=5a4=1a5=1a6=2

59、a7=9a8=7a9=4a10=2a11=4v1v2v3v4v5v6v7v8v9 ve vl頂點(diǎn)頂點(diǎn)06457716 14 181814161078660活動活動 a1a2 a3a4a5 a6 a7a8 a9a10 a11 e l000645777161414161077866320 第九章 查找在等概率查找的情況下， 順序表查找的平均查找長度為：對順序表順序表而言，在查找成功查找成功時 Ci = n-i+1nPi121111n)i(nnASLnissASL = nP1 +(n-1)P2 +2Pn-1+Pn05 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5

60、 6 7 8 9 10 11 ST.elemST.length例如例如: key=64 的查找過程如下：lowhighmidlow mid high midlow 指示查找區(qū)間的下界high 指示查找區(qū)間的上界mid = (low+high)/2int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置區(qū)間初值 while (low 50時，可得近似結(jié)果 一般情況下，表長為 n 的折半查找的判定樹的深度和含有 n 個結(jié)點(diǎn)的完全二叉樹的深度相同。1) 1(log12112111nnnjnCnASLhjjnii