北京郵電大學(xué)-數(shù)據(jù)結(jié)構(gòu)講義課件

數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)

1題型(1)基本概念40選擇和判斷，20個(gè)左右簡答或給定實(shí)例執(zhí)行算法30（5-6個(gè)題目）概念或者某些數(shù)據(jù)結(jié)構(gòu)的性質(zhì)例如：霍夫曼編碼直接插入/冒泡/快速/選擇/堆排序等算法的執(zhí)行鏈地址法哈希表裝填根據(jù)二叉樹遍歷結(jié)果畫出樹關(guān)于圖的算法執(zhí)行，等等題型(1)基本概念402題型(2)算法設(shè)計(jì)題30常見題型的范圍（2-3題目)簡單題目（數(shù)組，單層或雙層循環(huán)，條件判斷）單向鏈表或雙向鏈表操作（插入/刪除/轉(zhuǎn)置/合并）二分查找，簡單排序算法的實(shí)現(xiàn)二叉樹（復(fù)制，相等，相似等，使用簡單遞歸算法）題型(2)算法設(shè)計(jì)題303第一章緒論第一章緒論4基本概念基本概念5學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義是為研究和解決如何有效地組織和處理非數(shù)值數(shù)據(jù)而產(chǎn)生的理論、技術(shù)和方法。是計(jì)算機(jī)科學(xué)中的一門綜合性的專業(yè)基礎(chǔ)課。涉及計(jì)算機(jī)軟件、硬件以及數(shù)學(xué)等學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義是為研究和解決如何有效地組織和處理非數(shù)值數(shù)6基本術(shù)語數(shù)據(jù)被計(jì)算機(jī)加工處理的對象。數(shù)據(jù)元素（記錄、表目）數(shù)據(jù)的基本單位，是數(shù)據(jù)集合中的一個(gè)有意義的個(gè)體。數(shù)據(jù)項(xiàng)一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。

組合項(xiàng)年月日學(xué)號(hào)姓名班號(hào)性別出生日期入學(xué)成績原子項(xiàng)基本術(shù)語數(shù)據(jù)被計(jì)算機(jī)加工處理的對象。組合項(xiàng)年月日學(xué)7基本術(shù)語2數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。

學(xué)號(hào)姓名班號(hào)性別出生日期入學(xué)成績

001劉影01女19840417623002李恒01男19831211679003陳誠02男19840910638………………數(shù)據(jù)結(jié)構(gòu)具有結(jié)構(gòu)的數(shù)據(jù)元素的集合。它包括數(shù)據(jù)元素的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和相適應(yīng)的運(yùn)算。數(shù)據(jù)元素基本術(shù)語2數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一8數(shù)據(jù)元素之間的邏輯關(guān)系，與計(jì)算機(jī)無關(guān)?？捎靡粋€(gè)二元組表示：Data_Structure=(D,R)D：數(shù)據(jù)元素的有窮集合，R：集合D上關(guān)系的有窮集合。

[例]

設(shè)有數(shù)據(jù)結(jié)構(gòu)B=(D,R)，其中D={d1,d2,d3,d4,d5,d6}，

R={r}，

r={<d1,d2>,<d1,d3>,<d1,d4>,<d3,d5>,<d3,d6>}，試畫出其邏輯結(jié)構(gòu)圖。d1d2d3d4d5d6邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的邏輯關(guān)系，與計(jì)算機(jī)無關(guān)。d1d2d39（以班級(jí)學(xué)生關(guān)系為例）(1)集合結(jié)構(gòu)數(shù)據(jù)元素除了“屬于同一集合”的聯(lián)系之外，沒有其它的關(guān)系。(2)線性結(jié)構(gòu)數(shù)據(jù)元素之間存在一對一的關(guān)系。(3)樹型結(jié)構(gòu)數(shù)據(jù)元素之間存在一對多的關(guān)系。(4)圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)

數(shù)據(jù)元素之間存在多對多的關(guān)系。成員關(guān)系長幼關(guān)系管理關(guān)系朋友關(guān)系四種基本的邏輯結(jié)構(gòu)（以班級(jí)學(xué)生關(guān)系為例）成員關(guān)系長幼關(guān)系管理關(guān)系朋友關(guān)系四種基10數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)11存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中如何表示。數(shù)據(jù)元素的映象用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素。每個(gè)數(shù)據(jù)元素的映象稱為結(jié)點(diǎn)每個(gè)數(shù)據(jù)項(xiàng)的映象稱為數(shù)據(jù)域關(guān)系的映象兩種基本方法及其組合使用。順序映象：以相對的存儲(chǔ)位置表示關(guān)系鏈?zhǔn)接诚螅阂愿郊有畔?指針)表示關(guān)系注意：數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的關(guān)系可以用數(shù)組等線形存儲(chǔ)的方式存儲(chǔ)邏輯上的樹形結(jié)構(gòu)也可以用樹狀的復(fù)雜的存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)邏輯上的集合關(guān)系以達(dá)到提高檢索速度的目的數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中如何表示。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)12

數(shù)據(jù)的邏輯結(jié)構(gòu)+運(yùn)算的定義-------面向用戶，需求分析（抽象數(shù)據(jù)類型）概念層數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)+運(yùn)算的實(shí)現(xiàn)-------面向計(jì)算機(jī)

實(shí)現(xiàn)層數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)13抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(ADT)一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作“抽象”是指數(shù)據(jù)類型的數(shù)學(xué)抽象特性，其定義僅僅取決于它的一組邏輯特性，而與在計(jì)算機(jī)內(nèi)部的表示和實(shí)現(xiàn)無關(guān)抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(ADT)14算法和算法分析算法和算法分析15算法的概念建立在數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上的、求解問題的一系列確切的步驟。一個(gè)算法必須滿足以下五個(gè)重要特性有窮性：對任何合法輸入執(zhí)行有窮步后能結(jié)束。確定性：每條指令必須有確切的含義。可行性：算法的每一條指令均能執(zhí)行。輸入：有零個(gè)或多個(gè)輸入。輸出：有一個(gè)或多個(gè)輸出。算法的概念和特性算法的概念算法的概念和特性16正確性（最重要的標(biāo)準(zhǔn)）算法應(yīng)滿足具體問題的需求對于典型的、苛刻而帶有刁難性的一組有效輸入得到正確的結(jié)果健壯性算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)對其作出反應(yīng)，而不是產(chǎn)生莫名其妙或隨機(jī)的輸出結(jié)果可讀性算法應(yīng)該好讀。以有利于閱讀者對程序的理解和維護(hù)高效性：時(shí)間復(fù)雜度算法執(zhí)行占用的CPU時(shí)間，隨問題規(guī)模n的變化函數(shù)高效性：空間復(fù)雜度算法執(zhí)行占用的內(nèi)存總量，隨問題規(guī)模n的變化函數(shù)評(píng)價(jià)算法優(yōu)劣的基本標(biāo)準(zhǔn)正確性（最重要的標(biāo)準(zhǔn)）評(píng)價(jià)算法優(yōu)劣的基本標(biāo)準(zhǔn)17算法效率的度量時(shí)間復(fù)雜度空間復(fù)雜度算法效率的度量時(shí)間復(fù)雜度18算法執(zhí)行的時(shí)間事后統(tǒng)計(jì)的方法先運(yùn)行依據(jù)算法的程序所得時(shí)間的統(tǒng)計(jì)量依賴于計(jì)算機(jī)的硬件、軟件等環(huán)境因素收集此算法的執(zhí)行時(shí)間和實(shí)際占用空間的統(tǒng)計(jì)資料。事前分析估算的方法求出該算法的一個(gè)時(shí)間界限函數(shù)；算法執(zhí)行的時(shí)間事后統(tǒng)計(jì)的方法19時(shí)間復(fù)雜度n問題規(guī)模，一般為數(shù)據(jù)的輸入量f(n)算法中基本操作重復(fù)執(zhí)行的次數(shù)—頻度是問題規(guī)模n的某個(gè)函數(shù)算法的時(shí)間量度、時(shí)間復(fù)雜度算法中各語句的頻度之和T(n)T(n)=O(f(n))隨問題規(guī)模的增大，執(zhí)行時(shí)間的增長率和f(n)的增長率相同時(shí)間復(fù)雜度n20時(shí)間復(fù)雜度曲線常見的時(shí)間復(fù)雜度：

O(1),O(log2n),O(n),O(nlog2n),O(n2),O(n3),O(2n)O(1)<O(log2n)＜O(n)＜O(nlog2n)＜(n2)＜O(n3)＜＜O(2n)時(shí)間復(fù)雜度曲線常見的時(shí)間復(fù)雜度：21空間復(fù)雜度算法所需存儲(chǔ)空間的度量記作：S(n)=O(f(n))其中n為問題的規(guī)模(或大小)存儲(chǔ)密度d=數(shù)據(jù)本身存儲(chǔ)量/實(shí)際所占存儲(chǔ)量空間復(fù)雜度22第二章線性表第二章線性表23線性結(jié)構(gòu)的特點(diǎn)在數(shù)據(jù)元素的非空有限集中存在唯一的一個(gè)被稱為“第一個(gè)”的數(shù)據(jù)元素存在唯一的一個(gè)被稱為“最后一個(gè)”的數(shù)據(jù)元素除第一個(gè)之外，集合中每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)除最后一個(gè)之外，集合中每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼線性結(jié)構(gòu)的特點(diǎn)在數(shù)據(jù)元素的非空有限集中24

順序表

順序表25線性表的順序存儲(chǔ)結(jié)構(gòu)bb+lb+2l…b+(i-1)l…b+(n-1)l順序存儲(chǔ)空間的獲得：靜態(tài)數(shù)組在源程序中指定大小，編譯時(shí)確定運(yùn)行時(shí)存儲(chǔ)空間尺寸不可增減有效數(shù)據(jù)限制在0-n順序存儲(chǔ)空間的獲得：動(dòng)態(tài)申請運(yùn)行時(shí)通過malloc函數(shù)動(dòng)態(tài)申請指定大小的存儲(chǔ)空間可以通過realloc函數(shù)擴(kuò)充或者縮小存儲(chǔ)空間大小，但是，可能需要內(nèi)存拷貝操作（開銷大）可以通過free函數(shù)釋放申請的空間線性表的順序存儲(chǔ)結(jié)構(gòu)bb+lb+2l26線性表的順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)優(yōu)點(diǎn)邏輯相鄰，物理相鄰可隨機(jī)存取任一元素存儲(chǔ)空間使用緊湊缺點(diǎn)插入、刪除操作需要移動(dòng)大量的元素；預(yù)先分配空間需按最大空間分配，利用不充分；表容量難以擴(kuò)充線性表的順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)優(yōu)點(diǎn)27線性表的單向鏈?zhǔn)酱鎯?chǔ)線性表的單向鏈?zhǔn)酱鎯?chǔ)28線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與實(shí)現(xiàn)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素?cái)?shù)據(jù)元素可零散地分布在內(nèi)存的任何位置上鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。即：邏輯上相鄰未必在物理上相鄰。結(jié)點(diǎn)之間的相對位置由鏈表中的指針域指示，而結(jié)點(diǎn)在存儲(chǔ)器中的存儲(chǔ)位置是隨意的。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與實(shí)現(xiàn)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)29線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)結(jié)點(diǎn)的組成數(shù)據(jù)域存放數(shù)據(jù)元素的值。指針域（鏈域）單向鏈表的每個(gè)結(jié)點(diǎn)都只有一個(gè)指針域。存放下一個(gè)結(jié)點(diǎn)（直接后繼）的地址。通過鏈域，可將n個(gè)結(jié)點(diǎn)按邏輯順序鏈接在一起（不論其物理次序如何）。數(shù)據(jù)域指針域線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)結(jié)點(diǎn)的組成數(shù)據(jù)域30單鏈表的類型定義typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;不帶頭節(jié)點(diǎn)的單鏈表

structLNode*L;或者

LinkListL;

如果L為NULL標(biāo)志空鏈表，否則，L為指向鏈表首個(gè)元素的指針單鏈表的類型定義typedefstructLNode{31帶頭節(jié)點(diǎn)的單鏈表頭結(jié)點(diǎn)在單鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)的結(jié)點(diǎn)；為了確定鏈表中第一個(gè)結(jié)點(diǎn)的位置而設(shè)立；數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可以存放關(guān)于線性表的附加信息，如長度等；尾結(jié)點(diǎn)指針域?yàn)榭眨o后繼），用NULL表示。帶頭節(jié)點(diǎn)的單鏈表32帶頭結(jié)點(diǎn)的單鏈表插入運(yùn)算具體操作X②

S

①③

④

P帶頭結(jié)點(diǎn)的單鏈表插入運(yùn)算具體操作X②S33帶頭結(jié)點(diǎn)的單鏈表插入算法將元素e插入到p節(jié)點(diǎn)之后s=(LNode*)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;

帶頭結(jié)點(diǎn)的單鏈表插入算法將元素e插入到p節(jié)點(diǎn)之后34帶頭結(jié)點(diǎn)單鏈表的刪除算法具體操作存儲(chǔ)池pq帶頭結(jié)點(diǎn)單鏈表的刪除算法具體操作存儲(chǔ)池p35帶頭結(jié)點(diǎn)單鏈表的刪除算法刪除p節(jié)點(diǎn)之后的節(jié)點(diǎn)q=p->next;if(q!=NULL){p->next=q->next;free(q);}帶頭結(jié)點(diǎn)單鏈表的刪除算法刪除p節(jié)點(diǎn)之后的節(jié)點(diǎn)36不帶頭單鏈表的轉(zhuǎn)置

pre=NULL;p=head;while(p!=NULL){t=p->next;p->next=pre;pre=p;p=t;}head=pre;

不帶頭單鏈表的轉(zhuǎn)置pre=NULL;37單鏈表的缺點(diǎn)獲取節(jié)點(diǎn)P的前驅(qū)的算法刪除節(jié)點(diǎn)p的算法替換節(jié)點(diǎn)p的算法在節(jié)點(diǎn)p之前插入新節(jié)點(diǎn)的算法單鏈表的缺點(diǎn)獲取節(jié)點(diǎn)P的前驅(qū)的算法38線性表的雙向鏈?zhǔn)酱鎯?chǔ)線性表的雙向鏈?zhǔn)酱鎯?chǔ)39雙向鏈表雙鏈表的定義：每個(gè)節(jié)點(diǎn)有兩個(gè)指針typedefstructDuLNode{ElemTypedata; structDuLNode*prior; structDuLNode*next;}DuLNode,*DuLinkList;結(jié)點(diǎn)的物理表示雙向鏈表雙鏈表的定義：每個(gè)節(jié)點(diǎn)有兩個(gè)指針結(jié)點(diǎn)的物理表示40帶頭結(jié)點(diǎn)雙向循環(huán)鏈表的插入將新元素e插入到雙向鏈表中p節(jié)點(diǎn)前s=(DuLNode*)malloc(sizeof(DuLNode));s->data=e;s->prior=p->prior; p->prior->next=s;s->next=p;p->prior=s;帶頭結(jié)點(diǎn)雙向循環(huán)鏈表的插入將新元素e插入到雙向鏈表中p節(jié)點(diǎn)前41帶頭結(jié)點(diǎn)雙向循環(huán)鏈表的刪除刪除節(jié)點(diǎn)pp->prior->next=p->next;p->next->prior=p->prior;free(p);帶頭結(jié)點(diǎn)雙向循環(huán)鏈表的刪除刪除節(jié)點(diǎn)p42第三章棧和隊(duì)列第三章棧和隊(duì)列43插入和刪除操作受限的線性表?xiàng)：完?duì)列都是線性表，只是在操作上做了限制棧（stack）后進(jìn)先出(LIFO:LastInFirstOut)的線性表表頭端稱為棧底（bottom）表尾端稱為棧頂（top）插入和刪除都在棧頂進(jìn)行隊(duì)列（queue）先進(jìn)先出(FIFO:FirstInFirstOut)的線性表表頭端稱為隊(duì)頭（front）表尾端稱為隊(duì)尾（rear）插入在隊(duì)尾進(jìn)行，而刪除則在隊(duì)頭進(jìn)行插入和刪除操作受限的線性表?xiàng)：完?duì)列都是線性表，只是在操作上做44棧的定義和基本操作棧的定義和基本操作45棧的基本操作InitStack(&s)初始化堆棧StackEmpty(s)判斷堆棧是否空push(s,e)將元素e壓入堆棧pop(s,&e)彈出棧頂元素棧的基本操作InitStack(&s)46棧的存儲(chǔ)結(jié)構(gòu)兩種方式順序表方式（常用）鏈表方式順序表方式的堆棧類型定義#defineSTACK_SIZE128ElemTypestack[STACK_SIZE];inttop;堆棧容量的設(shè)計(jì)：根據(jù)算法需要，分析算法的空間復(fù)雜度編號(hào)系統(tǒng)0~(n-1)，top記載下個(gè)空位位置，或者說，元素個(gè)數(shù)棧滿和?？眨ā吧弦纭迸c“下溢”）棧的存儲(chǔ)結(jié)構(gòu)兩種方式47順序表方式的堆棧操作#defineInitStack()top=0#defineStackEmpty()(top==0)Statuspush(elemTypee){if(top==STACK_SIZE)returnERROR;stack[top++]=e;returnOK;}

順序表方式的堆棧操作#defineInitStack()48順序表方式的堆棧操作Statuspop(elemType&e){if(top==0)returnERROR;e=stack[--top];returnOK;}順序表方式的堆棧操作Statuspop(elemType49棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)以及操作存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)不帶頭的單鏈表類型定義structNODE{ElemTypedata;structNODE*next;};structNODE*stack;操作算法InitStackClearStack:釋放所有節(jié)點(diǎn)其他操作：Push,Pop，StackEmpty棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)以及操作存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)50隊(duì)列隊(duì)列51隊(duì)列的定義隊(duì)列是一種特殊的線性表限定插入和刪除操作分別在表的兩端進(jìn)行具有先進(jìn)先出(FIFO—FirstInFirstOut)的特點(diǎn)。隊(duì)列的定義隊(duì)列是一種特殊的線性表52隊(duì)列的操作主要操作增加（入隊(duì)）EnQueue(Q,e);刪除（出隊(duì)）DeQueue(Q,&e);判斷隊(duì)列是否為空QueueEmpty(Q)其他操作初始化隊(duì)列InitQueue(Q)獲取隊(duì)列長度QueueLength(Q)清除隊(duì)列中的所有元素ClearQueue(Q)隊(duì)列的操作主要操作53隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)鏈表方式順序表方式隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)鏈表方式54鏈?zhǔn)疥?duì)列鏈?zhǔn)疥?duì)列55鏈?zhǔn)疥?duì)列的其它算法存儲(chǔ)結(jié)構(gòu)單鏈表，雙向循環(huán)鏈表，帶頭節(jié)點(diǎn)插入算法，刪除算法求隊(duì)列長度遍歷隊(duì)列中現(xiàn)有所有元素鏈?zhǔn)疥?duì)列的其它算法存儲(chǔ)結(jié)構(gòu)56使用順序表方式實(shí)現(xiàn)隊(duì)列使用順序表方式實(shí)現(xiàn)隊(duì)列57循環(huán)隊(duì)列(1)存儲(chǔ)結(jié)構(gòu)使用靜態(tài)的數(shù)組或者動(dòng)態(tài)申請的連續(xù)存儲(chǔ)空間(順序表)隊(duì)列描述隊(duì)頭隊(duì)尾基本算法增加元素:“假溢”現(xiàn)象，解決方法：循環(huán)隊(duì)列刪除元素循環(huán)隊(duì)列(1)存儲(chǔ)結(jié)構(gòu)58循環(huán)隊(duì)列(2)“上溢”與“下溢”的條件：隊(duì)列滿和隊(duì)列空的表示方法方法一：浪費(fèi)一個(gè)存儲(chǔ)空間，以(rear+1)%N==front判斷隊(duì)列滿方法二：設(shè)置隊(duì)列中的數(shù)據(jù)元素計(jì)數(shù)或者隊(duì)滿標(biāo)志循環(huán)隊(duì)列(2)59第五章數(shù)組和廣義表第五章數(shù)組和廣義表60數(shù)組數(shù)組61數(shù)組的順序表示和實(shí)現(xiàn)二維數(shù)組的順序存儲(chǔ)方式行優(yōu)先順序列優(yōu)先順序根據(jù)數(shù)組下表(i,j)檢索順序表中元素K的方式數(shù)組的順序表示和實(shí)現(xiàn)二維數(shù)組的順序存儲(chǔ)方式62數(shù)組的順序存儲(chǔ)方式（續(xù)）多維數(shù)組行優(yōu)先順序規(guī)定為先排最右的下標(biāo)，從右到左，最后排最左下標(biāo)：列優(yōu)先順序規(guī)定為先排最左下標(biāo)，從左向右，最后排最右下標(biāo)。數(shù)組的順序存儲(chǔ)特點(diǎn)只要已知開始結(jié)點(diǎn)的存放地址（即基地址）、數(shù)組維數(shù)、每維的上、下界，和每個(gè)數(shù)組元素所占用的單元數(shù)，就可以將數(shù)組元素的存放地址表示為其下標(biāo)的線性函數(shù)；數(shù)組中的任一元素可以在相同的時(shí)間內(nèi)存取，即順序存儲(chǔ)的數(shù)組是一個(gè)隨機(jī)存取結(jié)構(gòu)。例：數(shù)組：ElemTypeA[m][n];addr(A[i][j])=Base(A)+((i*n)+j)*sizeof(ElemType);addr(A[i][j])=Base(A)+((j*m)+i)*sizeof(ElemType);數(shù)組的順序存儲(chǔ)方式（續(xù)）多維數(shù)組63稀疏矩陣稀疏矩陣非零元素很少，分布沒有規(guī)律；設(shè)矩陣A中有s個(gè)非零元素，若s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)（即s≦m×n），則稱A為稀疏矩陣；令e=s/(m*n)，稱e為矩陣的稀疏因子。通常認(rèn)為e≦0.05時(shí)稱之為稀疏矩陣；在壓縮存儲(chǔ)時(shí)需要同時(shí)存儲(chǔ)非零元素的下標(biāo)和值；可用三元組存儲(chǔ)（行號(hào)，列號(hào)，值）。

0120000

100030

000500

000000

020006ijv1212211253345522566A稀疏矩陣稀疏矩陣012000064廣義表廣義表65廣義表的定義廣義表又稱列表，其每一個(gè)元素的結(jié)構(gòu)都可能是不同的；是n(n≥0)個(gè)元素a1,a2,a3,…,an的有限序列，其中ai或者是原子項(xiàng)，或者是一個(gè)廣義表；通常記作LS=(a1,a2,a3,…,an)LS是廣義表的名字，n為它的長度。若ai是廣義表，則稱它為LS的子表。第一個(gè)元素a1稱為表LS的表頭（head），由余下元素組成的表(a2,a3,...,an)稱為LS的表尾（tail）。廣義表中括號(hào)的重?cái)?shù)稱為廣義表的深度。廣義表的定義廣義表66

廣義表的長度和深度((),(e),(a,(b,c,d)),(f,g))長度4，深度3廣義表的長度和深度((),(e),(a,(b,c,d))67

廣義表操作廣義表的長度和深度(P108,p113)((),(e),(a,(b,c,d)),(f,g))長度4，深度3head與tail操作(p108)A=(a,(b,c))Head(A)aB=Tail(A)((b,c))C=Head(B)(b,c)Tail(B)()Head(C)bD=Tail(C)(c)Head(D)cTail(D)()L=((a,b,c),(e,f,g))取出元素fHead(Tail(Head(Tail(L))))L=((a,b,c),x,(u,t,w))取出元素tHead(Tail(Head(Tail(Tail(L)))))廣義表操作廣義表的長度和深度(P108,p113)68第六章樹和二叉樹第六章樹和二叉樹69樹的定義和基本術(shù)語樹的定義和基本術(shù)語70樹的定義樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)；樹是n(n≥0)個(gè)結(jié)點(diǎn)的有限集，非空樹滿足：有且僅有一個(gè)特定的稱之為根(root)的結(jié)點(diǎn)；除根以外的其余結(jié)點(diǎn)可分為m(0m<n)個(gè)互不相交的子集T1,T2,T3…Tm，其中每個(gè)子集本身又是一棵樹，且稱為根的子樹。樹的定義樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次71樹的一些基本術(shù)語結(jié)點(diǎn)的度（degree）結(jié)點(diǎn)所擁有的子樹的數(shù)目。葉子結(jié)點(diǎn)（leaf--又稱終端結(jié)點(diǎn)terminalnode）度為零的結(jié)點(diǎn)。分支結(jié)點(diǎn)（branchnode）度不為零的結(jié)點(diǎn)孩子（child）結(jié)點(diǎn)的子樹的根稱為結(jié)點(diǎn)的孩子。樹的一些基本術(shù)語結(jié)點(diǎn)的度（degree）72樹的一些基本術(shù)語(續(xù))雙親（parent）結(jié)點(diǎn)是其孩子的雙親。祖先（forefather）從樹根到雙親的所有結(jié)點(diǎn)稱為該結(jié)點(diǎn)的祖先。子孫（progeny）以結(jié)點(diǎn)為根的子樹的所有結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子孫。兄弟（sibling）同一父母的所有孩子互稱兄弟。層次（level）樹根為第一層，其孩子為第二層，孫子為第三層，以此類推。樹的一些基本術(shù)語(續(xù))雙親（parent）73樹的一些基本術(shù)語(續(xù))堂兄弟（cousin）雙親在同一層的結(jié)點(diǎn)互稱堂兄弟。深度（depth）樹中結(jié)點(diǎn)的最大層次稱為樹的深度。有序樹（orderedtree）結(jié)點(diǎn)各子樹從左至右是有秩序的樹稱為有序樹。無序樹（unorderedtree）結(jié)點(diǎn)各子樹沒有秩序的樹稱為無序樹。森林（forest）森林是m(m≥0)棵互不相交的樹的集合。樹的一些基本術(shù)語(續(xù))堂兄弟（cousin）74二叉樹二叉樹75二叉樹的定義(1)定義二叉樹是n(n0)個(gè)結(jié)點(diǎn)的有限集合，它或?yàn)榭諛?n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的左子樹和右子樹的二叉樹組成。二叉樹的特點(diǎn)：定義是遞歸的；0結(jié)點(diǎn)的度2；是有序樹。二叉樹的定義(1)定義76二叉樹的定義(2)二叉樹的五種基本形態(tài)兩種特殊的二叉樹滿二叉樹：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)完全二叉樹：只有最下面兩層結(jié)點(diǎn)的度可小于2，而最下一層的葉結(jié)點(diǎn)集中在左邊若干位置上123456712345678910二叉樹的定義(2)二叉樹的五種基本形態(tài)1277二叉樹的性質(zhì)(1)性質(zhì)1二叉樹的第i層上至多有2i-1(i1)個(gè)結(jié)點(diǎn)。性質(zhì)2深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)(k1)。二叉樹的性質(zhì)(1)性質(zhì)178二叉樹的性質(zhì)(2)性質(zhì)3對任何一棵二叉樹T，如果其葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2

，則n0=n2+1證明設(shè)度為1的節(jié)點(diǎn)數(shù)為n1，結(jié)點(diǎn)總數(shù)為nn=n0+n1+n2(1)除根節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)都有一個(gè)分支射入，設(shè)分支數(shù)為B，有：B=n+1 (2)所有分支由非葉子節(jié)點(diǎn)射出，有B=n1+2n2(3)由(1)(2)(3)得：n0=n2+1二叉樹的性質(zhì)(2)性質(zhì)379二叉樹的性質(zhì)(3)性質(zhì)4具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1。二叉樹的性質(zhì)(3)性質(zhì)480二叉樹的性質(zhì)(4)性質(zhì)5對一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹，對其結(jié)點(diǎn)按層從上至下(每層從左至右)進(jìn)行1至n的編號(hào)，則對任一結(jié)點(diǎn)i(1in)有：若i=1，則i是根，無雙親；若i>1，則i的雙親是i/2。若2i>n，則i無左孩子;否則，i的左孩子是2i。若2i+1>n，則i無右孩子;否則，i的右孩子是2i+1。123456712345678910二叉樹的性質(zhì)(4)性質(zhì)5123481二叉樹的存儲(chǔ)結(jié)構(gòu)(1)順序存儲(chǔ)結(jié)構(gòu)按完全二叉樹存儲(chǔ)（可以用數(shù)組這樣線性的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)一個(gè)非線性的數(shù)據(jù)結(jié)構(gòu)）#defineMaxTreeSize128typedefTElemTypeSqBiTree[MaxTreeSize];SqBiTreebt;ABCDEF1234567ABDEFC二叉樹的存儲(chǔ)結(jié)構(gòu)(1)順序存儲(chǔ)結(jié)構(gòu)#defineMaxT82二叉樹的存儲(chǔ)結(jié)構(gòu)(2)順序存儲(chǔ)結(jié)構(gòu)用父母指針存儲(chǔ)存儲(chǔ)結(jié)點(diǎn)數(shù)據(jù)和其父結(jié)點(diǎn)的序號(hào)ABCDEF011233123456ABDEFC#defineMaxTreeSize100typedefstructNode{ Telemtypedata; intparent;}Node;typedefNodebTree[MaxTreeSize];

二叉樹的存儲(chǔ)結(jié)構(gòu)(2)順序存儲(chǔ)結(jié)構(gòu)ABCDEF011233183二叉樹的存儲(chǔ)結(jié)構(gòu)(3)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用二叉鏈表存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用三叉鏈表存儲(chǔ)

A^^B^

C^^D^E^bt

A^B^

C^^D^E^bt二叉樹的存儲(chǔ)結(jié)構(gòu)(3)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)A84二叉樹的存儲(chǔ)結(jié)構(gòu)(4)二叉鏈表的類型定義typedefstructBiTNode{ TElemTypedata；structBiTNode*lchild；

structBiTNode*rchild；}BiTNode,*BiTree；性質(zhì)：有N個(gè)節(jié)點(diǎn)的二叉樹共有N+1個(gè)空指針，N-1個(gè)非空指針。三叉鏈表的類型定義typedefstructTriTNode{ TElemTypedata；structBiTNode*lchild；

structBiTNode*rchild；

structBiTNode*parent；}TriTNode,*TriTree；二叉樹的存儲(chǔ)結(jié)構(gòu)(4)二叉鏈表的類型定義三叉鏈表的類型定義85遍歷二叉樹遍歷二叉樹86遍歷二叉樹遍歷二叉樹指按某條搜索路線走遍二叉樹的每個(gè)結(jié)點(diǎn)，使得樹中每個(gè)結(jié)點(diǎn)都被訪問一次，且僅被訪問一次。根據(jù)搜索路徑的不同，二叉樹的遍歷分為八種：1、前序遍歷（preordertraversal）DLR2、中序遍歷（inordertraversal）

LDR3、后序遍歷（postordertraversal）LRD4、逆前序遍歷（inverse

preordertraversal）DRL5、逆中序遍歷（inverse

inordertraversal）RDL6、逆后序遍歷（inverse

postordertraversal）RLD7、按層次遍歷（level-by-leveltraversal）8、按層次逆遍歷（inverselevel-by-leveltraversal）√√√√遍歷二叉樹遍歷二叉樹根據(jù)搜索路徑的不同，二叉樹的遍歷分為八種87遍歷方法先序遍歷：ABDEC中序遍歷：DBEAC后序遍歷：DEBCAABCDE遍歷二叉樹示例ABDEFC1.ABDCEF2.DBAECF3.DBEFCA4.ACFEBD5.FCEABD6.FECDBA7.ABCDEF8.ACBFED1-前序2-中序3-后序4-逆前序5-逆中序6-逆后序7-層次8-層次逆遍歷方法ABCDE遍歷二叉88利用遍歷結(jié)果確定二叉樹問題先序序列+中序序列中序序列+后序序列先序序列+后序序列(x，為什么？)

先序序列:ABCDEFGH

中序序列:BDCEAFHGABFCGDEH思考：層序+先序/中序/后序，能否確定？如何做？利用遍歷結(jié)果確定二叉樹問題(1)例如：層序ABCDEFGHIJ,中序DBGEHJACIF

例如：中序ABCDEFGHIJ,后序ACDBHJIGFE利用遍歷結(jié)果確定二叉樹問題ABFCGDEH思考：層序+先序/89利用遍歷結(jié)果確定二叉樹問題(2)一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分未顯示出來，求出空格處的內(nèi)容，并畫出該二叉樹先序：_H_A_DIKC_B中序：J_FADG_KEI_后序：_F_AHCE_B_G先序：_

H_A_D

IKC_B中序：J_FAD

G

_KEI_

后序：_F_AH

CE_B_

G利用遍歷結(jié)果確定二叉樹問題(2)一棵二叉樹的先序、中序和后序90voidPreorder(BiTreet){if(t){visit(t);Preorder(t->lchild);Preorder(t->rchild);}}voidInorder(BiTreet){if(t){Inorder(t->lchild);visit(t);Inorder(t->rchild);}}voidPostorder(BiTreet){if(t){Postorder(t->lchild);Postorder(t->rchild);visit(t);}}遍歷二叉樹的遞歸算法voidPreorder(BiTreet)voidIn91判斷兩個(gè)二叉樹是否相等(相似）類似的其他遞歸式二叉樹算法(1)intcheck(BiTreea,BiTreeb){if(a==NULL)returnb==NULL;if(b==NULL)return0;

if(a->data!=b->data)return0;returncheck(a->lchild,b->lchild)&&check(a->rchild,b->rchild);}交換二叉樹的左右子樹）voidswap(BiTreet){if(t==NULL)return;

tmp=t->lchild;t->lchild=t->rchild;t->rchild=tmp;swap(t->lchild);swap(t->rchild);}判斷兩個(gè)二叉樹是否相等(相似）類似的其他遞歸式二叉樹算法(192類似的其他遞歸式二叉樹算法(2)拷貝二叉樹BiTreebtcopy(BiTreet){if(t==NULL)returnNULL;

p=malloc(sizeof(*BiTree));p->data=t->data;p->lchild=btcopy(t->lchild);p->rchild=btcopy(t->rchild);returnp;}類似的其他遞歸式二叉樹算法(2)拷貝二叉樹BiTreebt93樹和森林樹和森林94樹的存儲(chǔ)結(jié)構(gòu)：雙親表示法ABCDEFG^001033０123

456ABCEFGD

存儲(chǔ)方法：使用順序結(jié)構(gòu)#defineMAX_TREE_SIZE100typedefstructPTNode{TElemTypedata;intparent;}PTNode;/*節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)*/typedefstruct{/*順序存儲(chǔ)結(jié)構(gòu)*/PTNodenodes[MAX_TREE_SIZE];intr,n;/*根位置和節(jié)點(diǎn)數(shù)*/}PTree;優(yōu)點(diǎn)：簡單，緊湊，易于尋找雙親節(jié)點(diǎn)缺點(diǎn)：查詢某節(jié)點(diǎn)的孩子效率低樹的存儲(chǔ)結(jié)構(gòu)：雙親表示法ABCDEFG^001033０195樹的存儲(chǔ)結(jié)構(gòu):孩子兄弟表示法孩子兄弟表示法A∧B∧CD∧∧E∧∧F∧G∧ABCEFGD樹的存儲(chǔ)結(jié)構(gòu):孩子兄弟表示法孩子兄弟表示法A∧B∧CD∧∧E96森林與二叉樹的轉(zhuǎn)換轉(zhuǎn)換原則按孩子兄弟表示法進(jìn)行轉(zhuǎn)換。樹與二叉樹的轉(zhuǎn)換DE森林與二叉樹的轉(zhuǎn)換轉(zhuǎn)換原則DE97森林與二叉樹的轉(zhuǎn)換森林與二叉樹的轉(zhuǎn)換98赫夫曼樹及其應(yīng)用赫夫曼樹及其應(yīng)用99赫夫曼樹及其應(yīng)用赫夫曼樹最優(yōu)樹；是一類帶權(quán)路徑長度最短的樹；路徑長度指樹中兩個(gè)結(jié)點(diǎn)間路徑上所含有的分支數(shù)目。樹的路徑長度指從樹根到每一結(jié)點(diǎn)的路徑長度之和。帶權(quán)路徑長度指結(jié)點(diǎn)的路徑長度與該結(jié)點(diǎn)的權(quán)之積。赫夫曼樹及其應(yīng)用赫夫曼樹100赫夫曼樹樹的帶權(quán)路徑長度樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度；最優(yōu)二叉樹或赫夫曼樹。WPL最小的二叉樹。赫夫曼樹樹的帶權(quán)路徑長度101赫夫曼樹的構(gòu)造根據(jù)給定的n個(gè)權(quán)值{w1,w2,...wn}構(gòu)成n棵二叉樹的集合F={T1,T2,...,Tn}，其中每棵二叉樹Ti中只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹均空；在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。在F中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入F中；重復(fù)2和3，直到F中只含一棵樹為止；這棵樹就是赫夫曼樹；性質(zhì)：所有節(jié)點(diǎn)的度要么為0，要么為2；不一定是完全二叉樹；子樹也是赫夫曼樹赫夫曼樹的構(gòu)造根據(jù)給定的n個(gè)權(quán)值{w1,w2,...wn}構(gòu)102[例]

w={5,29,7,8,14,23,3,11}51429782331114297823113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295811358192342291487152958100赫夫曼樹構(gòu)造舉例1[例]w={5,29,7,8,14,23,3103例：已知字符A、B、C、D、E、F、G，使用頻度分別為：0.25、0.1、0.15、0.06、0.3、0.05、0.09，試以此構(gòu)造霍夫曼樹。GB0.19A0.44FD0.11C0.26E0.5611、0.250.10.150.060.30.050.092、0.250.10.150.30.09

0.11

3、0.250.150.30.11

0.19

4、

0.250.30.19

0.265、0.3

0.26

0.446、0.440.567、1.00赫夫曼樹構(gòu)造舉例2例：已知字符A、B、C、D、E、F、G，使用頻度分別為：0104GBAFDCE000000111111A:01B:001C:101D:1001E:11F:1000G:000E:100A:000B:001C:010D:011F:101G:110000000111111GBAFDCE0赫夫曼編碼等長編碼WPL霍夫曼編碼

=2.56WPL等長編碼

=3

利用赫夫曼編碼可提高效率：(3-2.56)/3≈15%赫夫曼編碼GBAFDCE000000111111A:01B:105赫夫曼編碼的特點(diǎn)不等長編碼

赫夫曼編碼是不等長編碼前綴編碼赫夫曼編碼是前綴編碼，即任一編碼都不是另一字符編碼的前綴發(fā)送過程（編碼）根據(jù)由赫夫曼樹得到的編碼表送出字符數(shù)據(jù)接收過程（解碼）按左0、右1的規(guī)定，從根結(jié)點(diǎn)走到一個(gè)葉結(jié)點(diǎn)，完成一個(gè)字符的譯碼。反復(fù)此過程，直到接收數(shù)據(jù)結(jié)束赫夫曼編碼的特點(diǎn)不等長編碼106第七章圖第七章圖107本章內(nèi)容定義和術(shù)語存儲(chǔ)結(jié)構(gòu)：鄰接矩陣、鄰接表，十字鏈表，鄰接多重表兩種遍歷策略：深度優(yōu)先搜索和廣度優(yōu)先搜索連通性和最小生成樹拓?fù)渑判蚝完P(guān)鍵路徑(AOV,AOE)求最短路徑問題的解法本章內(nèi)容定義和術(shù)語108圖的基本概念圖的基本概念109圖的定義和術(shù)語(1)圖G由兩個(gè)集合V(G)和E(G)組成，記作G=(V,E)其中V(G)是頂點(diǎn)的非空有窮集合，E(G)是邊的有窮集合，而邊是頂點(diǎn)的無序?qū)蛴行驅(qū)Α?12323423圖的定義和術(shù)語(1)圖G112323423110圖的基本術(shù)語(2)頂點(diǎn)(vertex)數(shù)據(jù)元素所構(gòu)成的結(jié)點(diǎn)通常稱為頂點(diǎn)。弧(arc)若兩個(gè)頂點(diǎn)間有關(guān)系<x,y>∈E，則稱<x,y>為一條弧?；☆^(又稱終端點(diǎn))若<x,y>為一條弧，則頂點(diǎn)y稱為弧頭?；∥?又稱初始點(diǎn))若<x,y>為一條弧，則頂點(diǎn)x稱為弧尾。邊(Edge)無向圖中兩條弧<x,y>和<y,x>可用一條邊(x,y)來表示。圖的基本術(shù)語(2)頂點(diǎn)(vertex)111圖的基本術(shù)語(3)頂點(diǎn)的度（degree）無向圖：與頂點(diǎn)相關(guān)聯(lián)的邊數(shù)稱為該頂點(diǎn)的度有向圖：分為入度和出度頂點(diǎn)的入度（indegree）以頂點(diǎn)為頭的弧數(shù)稱為該頂點(diǎn)的入度。頂點(diǎn)的出度（outdegree）以頂點(diǎn)為尾的弧數(shù)稱為該頂點(diǎn)的出度。路徑（path）由頂點(diǎn)vi經(jīng)過一系列邊和頂點(diǎn)到達(dá)頂點(diǎn)vj所得到的頂點(diǎn)序列?；芈罚╨oop--又稱環(huán)cycle）起點(diǎn)和終點(diǎn)為同一頂點(diǎn)的路徑稱為回路。ABCEFD圖的基本術(shù)語(3)頂點(diǎn)的度（degree）ABCEFD112圖的基本術(shù)語(4)簡單路徑(路徑的頂點(diǎn))序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。簡單回路(簡單環(huán))除路徑起點(diǎn)和終點(diǎn)相同外，其余頂點(diǎn)均不相同的回路。稀疏圖邊數(shù)很少的圖(如e<nlogn)。稠密圖邊數(shù)很多的圖。權(quán)(weight)有些圖的邊或弧具有一定的大小，稱之為權(quán)。網(wǎng)帶權(quán)值的圖又稱為網(wǎng)或網(wǎng)絡(luò)。ABCEFD圖的基本術(shù)語(4)簡單路徑ABCEFD113圖的基本術(shù)語(5)子圖由圖的部分頂點(diǎn)和邊組成的新圖稱為原圖的子圖。生成子圖由圖的全部頂點(diǎn)和部分邊組成的子圖稱為原圖的生成子圖。鄰接點(diǎn)若邊(vi,vj)∈E，則vi與vj互為鄰接點(diǎn)。圖的基本術(shù)語(5)子圖114圖的基本術(shù)語(6)有向圖若<x,y>∈E，并不總有<y,x>∈E，則稱此圖為有向圖無向圖若<x,y>∈E，總有<y,x>∈E，則稱此圖為無向圖完全圖具有n*(n-1)/2條邊的無向圖稱為完全圖。有向完全圖具有n*(n-1)條弧的有向圖稱為有向完全圖。圖的基本術(shù)語(6)有向圖115圖的基本術(shù)語(7)生成樹連通圖的極小連通生成子圖稱為原圖的生成樹。生成森林由多棵有向樹構(gòu)成的有向圖的生成子圖稱為生成森林。最小代價(jià)生成樹連通網(wǎng)中由最小權(quán)值的邊構(gòu)成的生成樹。圖的基本術(shù)語(7)生成樹116圖的存儲(chǔ)圖的存儲(chǔ)117圖的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣數(shù)組表示法鄰接矩陣ABCEFDAij={0(vi,vj)∈E1(vi,vj)∈EABCDEF000001101000000100000010010000000010ABCDEF#defineInfinityINT_MAXtypedefenum{DG,DN,AG,AN}GraphKind;typedefstructArcCell{VRTypeadj;InfoType*info;}ArcCell,AdjMatrix[20][20];typedefstructGragh{VertexTypevexs[20];intvtxnum,arcnum;AdjMatrixarcs;GraghKindkind;}Gragh;圖的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣數(shù)組表示法ABCEFDAij={0118帶權(quán)圖的存儲(chǔ)結(jié)構(gòu):鄰接矩陣

鄰接矩陣

32

45232542Aij={(vi,vj)∈E權(quán)值(vi,vj)∈EAB

CD帶權(quán)圖的存儲(chǔ)結(jié)構(gòu):鄰接矩陣鄰接矩陣325119圖的遍歷圖的遍歷120圖的遍歷圖的遍歷按某種搜索順序?qū)D中每個(gè)結(jié)點(diǎn)訪問且僅訪問一次。遍歷圖的兩種方式深度優(yōu)先搜索DFS廣度優(yōu)先搜索BFS圖的遍歷圖的遍歷121深度優(yōu)先搜索類似樹的先根邊歷從某頂點(diǎn)v0

出發(fā)，訪問該頂點(diǎn)依次從v0的未被訪問過的鄰接點(diǎn)中選取一個(gè)頂點(diǎn)作為新出發(fā)點(diǎn);用同樣的方法訪問其它所有未被訪問過鄰接頂點(diǎn)若此時(shí)仍有頂點(diǎn)未被訪問，則從未被訪問過的頂點(diǎn)中任意選取一個(gè)頂點(diǎn)作為新的出發(fā)點(diǎn)；反復(fù)此過程，直至圖中所有頂點(diǎn)均被訪問過一遍為止。ABCEFGDHABFEHCDG深度優(yōu)先搜索類似樹的先根邊歷ABCEFGDHABFEHCDG122廣度優(yōu)先搜索類似樹的按層次遍歷從某頂點(diǎn)v0出發(fā)，訪問該頂點(diǎn)依次訪問v0的所有未被訪問過的鄰接點(diǎn)然后將所有這些鄰接點(diǎn)作為新的出發(fā)點(diǎn)，用同樣的方法訪問其它所有頂點(diǎn)，直到所有與v0

連通的頂點(diǎn)均被訪問到為止；若此時(shí)仍有頂點(diǎn)尚未被訪問，則從未被訪問過的頂點(diǎn)中任意選取一個(gè)頂點(diǎn)作為新的出發(fā)點(diǎn)；反復(fù)此過程，直至圖中所有頂點(diǎn)均被訪問過一遍為止。ABCEFGDHABCFHDGE廣度優(yōu)先搜索類似樹的按層次遍歷ABCEFGDHABCFHDG123最小生成樹最小生成樹124無向圖的連通分量和生成樹無向圖的連通分量從圖中任一頂點(diǎn)出發(fā)，一次調(diào)用深度或廣度優(yōu)先搜索所得到的頂點(diǎn)集即為連通分量中的頂點(diǎn)集。生成樹連通分量中的節(jié)點(diǎn)，連同遍歷時(shí)走過的邊，構(gòu)成圖的生成樹非連通圖，多個(gè)生成樹，形成生成森林無向圖的連通分量和生成樹無向圖的連通分量125最小生成樹定義由一個(gè)網(wǎng)絡(luò)生成的各邊的權(quán)數(shù)總和最小的生成樹；構(gòu)造算法Prim算法Kruskal算法最小生成樹定義126Prim算法將圖中頂點(diǎn)分為兩個(gè)集合，其中集合X包含圖的一個(gè)頂點(diǎn)v0，集合Y包含除v0

外的其它所有頂點(diǎn)；將跨接這兩個(gè)集合的權(quán)值最小的邊加入圖中，并將其依附在該邊的集合Y中的頂點(diǎn)v1

從Y中移入集合X中；反復(fù)過程2，直到集合Y為空，所得生成子圖即為最小生成樹。算法復(fù)雜性O(shè)(n2)ABCEFD2313221ABCEFD21321Prim算法將圖中頂點(diǎn)分為兩個(gè)集合，其中集合X包含圖的一127拓?fù)渑判蚺c關(guān)鍵路徑拓?fù)渑判蚺c關(guān)鍵路徑128拓?fù)渑判蛲負(fù)渑判蛴赡臣仙系囊粋€(gè)偏序得到該集合上的一個(gè)全序AOV網(wǎng)(ActivityOnVertex)有向邊表示兩個(gè)活動(dòng)間的次序關(guān)系頂點(diǎn)表示活動(dòng)這類圖又稱為頂點(diǎn)活動(dòng)圖，簡稱AOV圖如用頂點(diǎn)表示課程，用弧表示某些課程是其它課程的先修課，則拓?fù)渑判蚓褪乔笤谕瑫r(shí)只能學(xué)習(xí)一門課程時(shí)的學(xué)習(xí)次序拓?fù)渑判蛲負(fù)渑判?29拓?fù)渑判虻乃惴ú襟E掃描圖中每個(gè)頂點(diǎn)，將入度為零的頂點(diǎn)入隊(duì)列；從隊(duì)列中取出一個(gè)頂點(diǎn)輸出，并將其所有鄰接點(diǎn)的入度減1，若入度減為零，則將該鄰接點(diǎn)入隊(duì)列

反復(fù)執(zhí)行步驟2，直至所有頂點(diǎn)的入度均為零若該有向圖是有環(huán)圖，則不存在拓?fù)渑判?，就不可能輸出全部頂點(diǎn)；否則就可以輸出全部頂點(diǎn)。此特點(diǎn)可用來判斷一個(gè)有向圖是否存在回路。C1C2C3C6C4C5C7C8C9C10C1C2C3C4C5C6C7C8C9C10C2C1C3C4C5C6C7C8C9C10C1C2C4C3C5C6C7C8C9C10C2C1C4C3C5C6C7C8C9C10C1C2C5C4C3C6C7C8C10C9拓?fù)渑判蚪Y(jié)果：拓?fù)渑判虻乃惴ú襟E掃描圖中每個(gè)頂點(diǎn)，將入度為零的頂點(diǎn)入隊(duì)列；130關(guān)鍵路徑AOE圖(ActivityOnEdge)頂點(diǎn)一般用來表示事件(狀態(tài))弧用來表示活動(dòng)弧的權(quán)值表示活動(dòng)所需時(shí)間AOE網(wǎng)的性質(zhì)進(jìn)入Vi的活動(dòng)都結(jié)束，Vi所代表的事件才發(fā)生頂點(diǎn)Vi所代表的事件發(fā)生，從Vi出發(fā)的活動(dòng)才能開始源點(diǎn):入度為0的頂點(diǎn)，即工程的開始點(diǎn)匯點(diǎn):出度為0的頂點(diǎn)，即工程的完成點(diǎn)關(guān)鍵路徑影響整個(gè)工程進(jìn)度的活動(dòng)所組成的路徑:從源點(diǎn)到匯點(diǎn)的最長路徑，是完成該工程的最短時(shí)間減少這些活動(dòng)所需時(shí)間，整個(gè)工程就可能提前完成關(guān)鍵活動(dòng)關(guān)鍵路徑上的活動(dòng)會(huì)延長工期，關(guān)鍵活動(dòng)的加快可能縮短工期關(guān)鍵路徑AOE圖(ActivityOnEdge)131關(guān)鍵路徑舉例V1V2V3V6V4V5V7V8V9V10a1=4a2=3a3=2a4=3a5=3a6=5a9=5a12=5a7=4a8=6a10=2a11=1a13=8a14=5如左圖所示工程，其最后完工時(shí)間為21天。能否加快某些活動(dòng)進(jìn)度，使整個(gè)工期縮短呢？關(guān)鍵路徑舉例V1V2V3V6V4V5V7V8V9V10a1=132第九章查找第九章查找133基本概念基本概念134基本概念查找表由同一類型的數(shù)據(jù)元素構(gòu)成的集合；靜態(tài)查找表對查找表的查找僅是以查詢?yōu)槟康?，不改?dòng)查找表中的數(shù)據(jù)。動(dòng)態(tài)查找表可以在查找表中插入不存在的記錄，或刪除某個(gè)已存在的記錄。關(guān)鍵字?jǐn)?shù)據(jù)元素（或記錄）的某個(gè)數(shù)據(jù)項(xiàng)，能用來標(biāo)識(shí)一個(gè)數(shù)據(jù)元素。查找指定某個(gè)值，在查找表中確定是否存在一個(gè)記錄，該記錄的關(guān)鍵字等于給定值?；靖拍畈檎冶?35基本概念（續(xù)）查找成功查找表中存在滿足查找條件的記錄。查找不成功查找表中不存在滿足查找條件的記錄。平均查找長度ASL——查找方法時(shí)效的度量為確定記錄在查找表中的位置，需將關(guān)鍵字和給定值比較次數(shù)的期望值。查找成功時(shí)的ASL計(jì)算方法：n：記錄的個(gè)數(shù)pi：查找第i個(gè)記錄的概率，(不特別聲明時(shí)認(rèn)為等概率pi=1/n)ci：找到第i個(gè)記錄所需的比較次數(shù)基本概念（續(xù)）查找成功136順序表的查找順序表的查找137靜態(tài)查找表順序表的查找通常查找表中的各元素（或記錄）的關(guān)鍵字的值是無序的。實(shí)際查找時(shí)，通常將給定值放在第0個(gè)記錄處，然后從后向前查找，直到找到所查記錄為止，找不到則返回結(jié)果0。因?yàn)橛涗?像哨兵一樣看守著查找表下界，所以不會(huì)越界。typedefstruct{ KeyTypekey; DataTypedata;}ElemType;typedefstruct{ ElemType*elem; intlength;}SSTable;靜態(tài)查找表順序表的查找typedefstruct{138順序表查找算法intseq_search(SSTablel,KeyTypekey){ for(i=0；i<l.length;i++)if(l.elem[i]==key)returni; return-1;}intseq_search(SSTablel,KeyTypekey){ l.elem[0].key=key; for(i=l.length;l.elem[i].key!=key;i--); returni;}順序表查找算法intseq_search(SSTable139順序表算法:采用鏈表結(jié)構(gòu)structELEM*seq_search(KeyTypekey){for(p=head;p!=NULL;p=p->next)if(p->key==key)returnp; returnNULL;}structELEM*seq_search(KeyTypekey){tail->key=key;for(p=head;p->key!=key;p=p->next);returnp==tail?NULL:p;}順序表算法:采用鏈表結(jié)構(gòu)structELEM*seq_s140順序表算法性能分析性能分析查找成功時(shí)ASLs(n)==(1+2+...+n)/n=(n+1)/2查找失敗時(shí)ASLf=n+1順序表算法性能分析性能分析141靜態(tài)查找表有序表的查找有序表查找表中的各元素（或記錄）的關(guān)鍵字的值是有序的。仍可用順序查找，但在找不到時(shí)不需比較到表尾在等概率情況下，平均查找長度為：ASL成功

=(n+1)/2ASL不成功

=(n+2)/2有序表的查找更好的方法是折半查找靜態(tài)查找表有序表的查找142折半查找折半查找143折半查找只有有序表才能用折半查找的方法將給定值與中間的記錄進(jìn)行比較；若找到則查找成功；否則若給定值比中間記錄小，則對前一半子表進(jìn)行折半查找，反之則對后一半子表進(jìn)行折半查找。若在查找過程中，遇到查找子表的上界小于下界，則表示查找失敗折半查找只有有序表才能用折半查找的方法144折半查找算法及性能分析intbinsearch(SSTableST,keytypekey){low=1;high=ST.length;while(low<=high) { mid=(low+high)/2; if(key==ST.elem[mid].key)returnmid;elseif(key<ST.elem[mid].key)high=mid-1; elsehigh=mid+1;}return0;}查找性能分析折半查找每次只查表的一半，其所有記錄的查找路徑構(gòu)成一棵二叉樹，稱為折半查找樹（或判定樹），每次查找只走了該樹的一條分支，故平均查找長度不超過log2n+1折半查找算法及性能分析intbinsearch(SST145哈希表哈希表146哈希表哈希表一個(gè)有限的連續(xù)地址空間，用以容納按哈希地址存儲(chǔ)的記錄。哈希函數(shù)記錄的存儲(chǔ)位置與它的關(guān)鍵字之間存在的一種對應(yīng)關(guān)系。

Loc(ri)=H(keyi)沖突不同的兩個(gè)關(guān)鍵字經(jīng)過哈希函數(shù)運(yùn)算后所得到的散列地址相同理想情況下沒有沖突，查找復(fù)雜度O(1)一般考慮哈希表，沖突是不可避免發(fā)生的；同義詞在同一地址出現(xiàn)沖突的各關(guān)鍵字。哈希(散列)地址根據(jù)設(shè)定的哈希函數(shù)H(key)和處理沖突的方法確定的記錄的存儲(chǔ)位置。裝填因子α=記錄數(shù)/哈希表長度α>1必然沖突，α<<1也有可能沖突哈希表哈希表147哈希函數(shù)的構(gòu)造方法直接定址法：H(key)=a*key+b，a、b為常數(shù)；數(shù)字分析法分析關(guān)鍵字，找出其中幾位數(shù)字作散列地址（例如：指針值）除留余數(shù)法H(key)=keyMODp，p≤m，m為比散列表長度小的數(shù)p可以選用素?cái)?shù)，更有利于“散列”，少?zèng)_突偽隨機(jī)數(shù)法選取一個(gè)用關(guān)鍵字作為種子的偽隨機(jī)數(shù)發(fā)生器生成散列地址哈希函數(shù)的構(gòu)造方法直接定址法：148解決沖突的方法開放定址法再散列法鏈地址法散列表設(shè)立指針，將所有散列地址為此位置的關(guān)鍵字記錄用單鏈表形式存儲(chǔ)起來；公共溢出區(qū)法建立公共溢出區(qū)，將所有發(fā)生沖突的關(guān)鍵字記錄存儲(chǔ)到公共溢出區(qū)中去解決沖突的方法開放定址法149哈希表建立、查找舉例有一組關(guān)鍵字序列(38、59、125、168、216、719、455、20)，用函數(shù)H(key)=keyMOD10將其按順序散列到散列表HT(0:9)中，用鏈地址法，畫出散列表，并分別求在等概率情況下查找成功和不成功的平均查找長度。哈希表建立、查找舉例有一組關(guān)鍵字序列(38、59、125、1150鏈地址法ASL成功=—————————=——=1.37581181+1+2+1+1+2+1+2ASL不成功=——————————=——=1.81018102+1+1+1+1+3+2+1+3+30∧1∧2∧3∧4∧5∧6∧7∧8∧9∧38∧59∧125∧216∧20∧168∧719∧455∧鏈地址法ASL成功=—————————=——=1151第十章內(nèi)部排序第十章內(nèi)部排序152基本概念基本概念153基本概念排序排序又稱分類，是計(jì)算機(jī)中很重要的操作，它是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列排列成一個(gè)按關(guān)鍵字有序的序列。定義設(shè)有記錄序列{R1、R2………..Rn}，其相應(yīng)的關(guān)鍵字序列為{K1、K2………..Kn}；若存在一種確定的關(guān)系：Kx≤Ky≤…≤Kz，則將記錄序列{R1、R2………..Rn}排成按該關(guān)鍵字有序的序列{Rx、Ry………..Rz}的操作，稱之為排序。關(guān)系是任意的，如通常經(jīng)常使用的小于、大于等關(guān)系。排序過程中的兩種基本操作比較操作：比較兩個(gè)關(guān)鍵字值的大小的操作。移動(dòng)操作：將記錄從一個(gè)位置移動(dòng)到另一個(gè)位置的操作?；靖拍钆判?54基本概念（續(xù)）排序方法穩(wěn)定的排序方法若待排序列中存在兩個(gè)或以上關(guān)鍵字相等的記錄，設(shè)Ki=Kj(1≤i<j≤n)，即排序前Ri在Rj前，若在排序后Ri仍在Rj前，則稱排序是穩(wěn)定的簡單的直接插入排序和冒泡排序都是穩(wěn)定排序不穩(wěn)定的排序方法待排序列中存在兩個(gè)或以上關(guān)鍵字相等的記錄，設(shè)Ki=Kj(1≤i<j≤n)，即排序前Ri在Rj前，若在排序后Rj卻在Ri前，則稱排序是不穩(wěn)定穩(wěn)定的希爾排序，快速排序和堆排序都是不穩(wěn)定排序基本概念（續(xù)）排序方法155基本概念（續(xù)）排序的分類內(nèi)部排序待排序列記錄全部存放在計(jì)算機(jī)隨機(jī)存儲(chǔ)器中進(jìn)行排序的過程稱為內(nèi)部排序。外部排序待排序列記錄數(shù)量太大，不能全部存放在計(jì)算機(jī)隨機(jī)存儲(chǔ)器中，排序過程中需對計(jì)算機(jī)外存進(jìn)行訪問，這種排序過程稱為外部排序。基本概念（續(xù)）排序的分類156基本概念（續(xù)）待排序列的三種存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)：存儲(chǔ)在地址連續(xù)的一組存儲(chǔ)單元中（以此為例）；鏈?zhǔn)酱鎯?chǔ)：存儲(chǔ)在地址不連續(xù)的一組存儲(chǔ)單元（鏈表）中；地址存儲(chǔ)：記錄順序存儲(chǔ)，另設(shè)關(guān)鍵字和記錄地址排序。基本概念（續(xù)）待排序列的三種存儲(chǔ)結(jié)構(gòu)157插入排序插入排序158直接插入排序一種簡單的排序方法將記錄一個(gè)個(gè)插入到已排序好的有序表中，從而得到長度增加的新的有序表。直接插入排序一種簡單的排序方法159r[0]用作哨兵。共執(zhí)行5遍操作。每遍操作：先將元素復(fù)制內(nèi)容放入r[0]，再將本元素與已排序的序列從尾開始進(jìn)行比較。在已排序的序列中尋找自己的位置進(jìn)行插入，或者尋找不到，一直進(jìn)行到哨兵為止，意味著本元素最小，應(yīng)該放在r[1]。每進(jìn)行一遍，排序的序列將增加一個(gè)元素。如果序列中有n個(gè)元素，那么最多進(jìn)行n遍即可。e.g:36、24、10、6、12存放在r數(shù)組的下標(biāo)為1至5的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為1至5的元素之中。012362410612345插入排序直接插入排序160r[0]用作哨兵。共執(zhí)行5遍操作。e.g:36、2直接插入排序算法Insert_sort()/*數(shù)據(jù)存于r[1]~r[N]*/{inti,j;for(i=2;i<=N;i++){if(r[i]<r[i-1]){r[0]=r[i];r[i]=r[i-1];