數(shù)據(jù)結(jié)構(gòu)總復(fù)習(xí)課件

《數(shù)據(jù)結(jié)構(gòu)》西南民院計算機(jī)系

TEmailliu-li-1@163.net

《數(shù)據(jù)結(jié)構(gòu)》西南民院計算機(jī)系1題型1選擇題2填空題3解答題4算法題題型第一章緒論第一章緒論第一章緒論計算機(jī)的發(fā)展硬件

CPU、內(nèi)、外存儲器等軟件：系統(tǒng)軟件、應(yīng)用軟件應(yīng)用科學(xué)計算數(shù)據(jù)處理過程控制等處理數(shù)據(jù)的能力和種類：數(shù)值字符、字符串具有多個屬性對象圖形圖像聲音第一章緒論計算機(jī)的發(fā)展數(shù)據(jù)結(jié)構(gòu)的研究對象：非數(shù)值數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，如何表示，

如何存儲，如何處理的問題。

本課程討論的問題：應(yīng)用中常用的幾種數(shù)據(jù)結(jié)構(gòu)，以及如何存儲,如何處理它們。第一章緒論數(shù)據(jù)結(jié)構(gòu)的研究對象：第一章緒論1數(shù)據(jù)：客觀對象的符號表示。例如：課程名，地名，書名都是數(shù)據(jù)2數(shù)據(jù)結(jié)構(gòu)：帶有結(jié)構(gòu)和操作的數(shù)據(jù)元素集合結(jié)構(gòu)：數(shù)據(jù)元素之間的關(guān)系；

操作：對數(shù)據(jù)的加工處理；第一章緒論1數(shù)據(jù)：客觀對象的符號表示。第一章第一章緒論3數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，是具體關(guān)系的抽象。4常用的有下列幾類基本結(jié)構(gòu)：

（1）集合

（2）線性結(jié)構(gòu)

（3）樹結(jié)構(gòu)

（4）圖結(jié)構(gòu)（5）其它復(fù)雜結(jié)構(gòu)5數(shù)據(jù)結(jié)構(gòu)的基本操作：也叫基本運算：是指對數(shù)據(jù)結(jié)構(gòu)的加工處理；第一章緒論3數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)之間的結(jié)構(gòu)第一章緒論6數(shù)據(jù)的存儲結(jié)構(gòu)：

數(shù)據(jù)結(jié)構(gòu)在計算機(jī)內(nèi)存中的表示。

7順序存儲結(jié)構(gòu)用一組連續(xù)的內(nèi)存單元存放數(shù)據(jù)元素，用元素相對的存儲位置表示元素之間的結(jié)構(gòu)關(guān)系；8鏈?zhǔn)酱鎯Y(jié)構(gòu)

用任意一組存儲單元存儲數(shù)據(jù)元素，對每個數(shù)據(jù)元素除了保存自身信息外，還保存相關(guān)元素的存儲位置。

數(shù)據(jù)結(jié)構(gòu)基本操作的實現(xiàn)：基本操作在計算機(jī)上的實現(xiàn)（方法）第一章緒論6數(shù)據(jù)的存儲結(jié)構(gòu)：9數(shù)據(jù)結(jié)構(gòu)的表示1圖示表示2二元組表示圖示表示：由頂點和邊構(gòu)成的圖，其中頂點表示數(shù)據(jù)，邊表示數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系；第一章緒論JIHGFEDBAC9數(shù)據(jù)結(jié)構(gòu)的表示圖示表示：由頂點和邊構(gòu)成的圖，其中頂點表示二元組表示

用一個二元組（D，S）表示數(shù)據(jù)結(jié)構(gòu)，其中D是數(shù)據(jù)元素集合，S是D上關(guān)系的集合。

D={A，B，C，D，E，F(xiàn)，G，H，I，J}

S={R}

R={〈A,B>,<B,C>,<C,D><D,E>,<E,F>,<F,G>,<G,H>,<H,I>,<I,J>}第一章緒論二元組表示

用一個二元組（D，S）表示數(shù)據(jù)結(jié)構(gòu)，其中第一章緒論10算法的概念

算法是求解問題的操作序列（或操作步驟）11時間復(fù)雜度T（n）

以求解問題的基本操作（原操作）的執(zhí)行次數(shù)作為算法的時間度量

空間復(fù)雜度用執(zhí)行算法所需的輔助空間的大小作為算法所需空間的度量第一章緒論10算法的概念第一章練習(xí)題1數(shù)據(jù)結(jié)構(gòu)：帶有結(jié)構(gòu)和操作的數(shù)據(jù)元素集合。2常用的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的表示4數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，是具體關(guān)系的抽象。數(shù)據(jù)結(jié)構(gòu)的基本操作：也叫基本運算：是指對數(shù)據(jù)結(jié)構(gòu)的加工處理；數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計算機(jī)內(nèi)存中的表示數(shù)據(jù)結(jié)構(gòu)基本操作的實現(xiàn)：基本操作在計算機(jī)上的實現(xiàn)（方法）順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)10算法的概念

算法是求解問題的操作序列（或操作步驟）。11時間復(fù)雜度T（n）以求解問題的基本操作（原操作）的執(zhí)行次數(shù)作為算法時間的度量第一章練習(xí)題1數(shù)據(jù)結(jié)構(gòu)：帶有結(jié)構(gòu)和操作的數(shù)據(jù)元素集合。第二章線性表第二章線性表常用的數(shù)據(jù)結(jié)構(gòu)1）集合

2）線性結(jié)構(gòu)

3）樹結(jié)構(gòu)

4）圖結(jié)構(gòu)

5）其它復(fù)雜結(jié)構(gòu)第二章線性表對每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下兩方面的問題1數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)的基本操作；2數(shù)據(jù)的存儲結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)基本操作的實現(xiàn)

常用的數(shù)據(jù)結(jié)構(gòu)第二章線性表對每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下兩

第二章線性表線性數(shù)據(jù)結(jié)構(gòu)：

除第一個元素和最后一個元素之外，其他元素都有且僅有一個直接前趨，有且僅有一個直接后繼。第二章線性表線性數(shù)據(jù)結(jié)構(gòu)：2.1線性表的概念

一線性表的邏輯結(jié)構(gòu)在線性表中，除第一個元素和最后一個元素之外，其他元素都有且僅有一個直接前趨，有且僅有一個直接后繼。2.1線性表的概念

a1

a2ai-1

aiai+1

an2.1線性表的概念

一線性表的邏輯結(jié)構(gòu)2.1線線性表的基本操作1初始化操作InitList(&L)2銷毀操作DetroyList(&L)3置空操作ClearList(&L)4判空操作ListEmpty(L)5求表長操作ListLength(L)6取元素操作：GetElem(L,i,&e)7查找操作LocateElem(L,e,compare())8插入操作ListInsert(&L,i,e)9刪除操作ListDelete(&L,i,&e)10遍歷操作ListTraverse(&L,visit())2.1線性表的概念線性表的基本操作2.1線性表的概念

2.2線性表的順序存儲和實現(xiàn)一線性表的順序存儲結(jié)構(gòu)——順序表1順序表用一組連續(xù)的內(nèi)存單元依次存放線性表的數(shù)據(jù)元素。2順序表的類型定義

typedefstruct{

ElemType*elem;//線性表存儲空間基址

intlength;//當(dāng)前線性表長度

intlistsize;//當(dāng)前分配的存儲空間大小}SqList;2.2線性表的順序存儲和實現(xiàn)一線性表的順序順序表圖示設(shè)A=（a1,a2,a3,...an）是一線性表，L是SqList類型的結(jié)構(gòu)變量，用于存放A2.2線性表的順序存儲和實現(xiàn)L.elemL.lenghtL.listsizen99a1a2ai-1aiai+1an01i-2i-1in-199

順序表保存了哪些信息?順序表圖示設(shè)A=（a1,a2,a3,...an2.2線性表的順序存儲和實現(xiàn)

順序表保存了哪些信息？*線性表中的數(shù)據(jù)元素；

*線性表中數(shù)據(jù)元素的順序關(guān)系；*表中元素個數(shù)（簡化算法）*當(dāng)前分配的存儲空間

順序表如何保存這些信息？

3順序表存儲特點元素存儲在一組連續(xù)的內(nèi)存單元中；通過元素存儲順序元素之的邏輯順序；2.2線性表的順序存儲和實現(xiàn)順序表保存了哪些信息？二順序表的基本操作算法

1初始化算法InitList_Sq(SqList&L)2插入操作算法

ListInsert_Sq(SqList&L,inti,ElemTypee)3刪除操作算法

ListDelete_Sq(SqList&L,inti,ElemType&e)2.2線性表的順序存儲和實現(xiàn)二順序表的基本操作算法

1初始化算法2.2線性表2.2線性表的順序存儲和實現(xiàn)5順序表主要操作特點1）可隨機(jī)存取順序表的元素(用L.elem[i-1]或L.elem+(i-1)可直接定位元素的存儲地址)2）插入刪除操作通過移動元素實現(xiàn)2.2線性表的順序存儲和實現(xiàn)5順序表主要操作特點2．3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)和實現(xiàn)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

用一組任意的存儲單元存儲線性表中的數(shù)據(jù)元素，對每個數(shù)據(jù)元素除了保存自身信息外，還保存了相關(guān)元素的存儲位置。2．3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)和實現(xiàn)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3.1線性鏈表一線性鏈表的概念1線性鏈表

用一組任意的存儲單元存儲線性表中的數(shù)據(jù)元素，對每個數(shù)據(jù)元素除了保存自身信息外，還保存了直接后繼元素的存儲位置。2．3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)和實現(xiàn)2.3.1線性鏈表用一typedefstructLnode{

ElemTypedata;

StructLnode*next;

}LNode,*LinkList;

數(shù)據(jù)域指針域

datanext

L2線性鏈表的結(jié)點類型定義及指向結(jié)點的指針類型定義2.3.1線性鏈表ai-1aia1antypedefstructLnode{

El2.3.1線性鏈表3線性鏈表存儲特點1）用一組任意的存儲單元存儲線性表中的數(shù)據(jù)元素；2）通過保存直接后繼元素的存儲位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系；2.3.1線性鏈表3線性鏈表存儲特點二線性鏈表基本操作算法1初始化操作算法InitList_L(LinkList&L)2插入操作算法ListInsert_L(LinkList&L,inti,ElemTypee)3刪除操作算法ListInsert_L(LinkList&L,inti,ElemType&e)

2.3.1線性鏈表二線性鏈表基本操作算法2.3.1線性鏈2.3.1線性鏈表5線性鏈表操作主要特點1）不能隨機(jī)存取元素；2）插入、刪除操作通過修改結(jié)點的指針實現(xiàn)；2.3.1線性鏈表5線性鏈表操作主要特點循環(huán)鏈表

循環(huán)鏈表的特點是將線性鏈表的最后一個結(jié)點的指針指向鏈表的第一個結(jié)點

aia1ai+1ai-1anaiai+1ai-1anL2.3.2循環(huán)鏈表循環(huán)鏈表aia1ai+1ai-1anaiai+1ai-雙向鏈表

雙向鏈表中，每個結(jié)點有兩個指針域，一個指向直接后繼元素結(jié)點，另一個指向直接前趨元素結(jié)點。2.3.3雙向鏈表Laia1ai-1an雙向鏈表雙向鏈表中，每個結(jié)線性表的其他操作的實現(xiàn)1)通過調(diào)用基本操作算法2)直接實現(xiàn)線性表的其他操作的實現(xiàn)線性表的其他操作的實現(xiàn)線性表的其他操作的實現(xiàn)第二章練習(xí)題；

１線性表的邏輯結(jié)構(gòu)：在線性表中，除第一個元素和最后一個元素外，其他元素都有且僅有一個直接前趨，有且僅有一個直接后繼。２順序表存儲特點：1）元素存儲在一組連續(xù)的內(nèi)存單元中2）通過元素的存儲順序反映線性表中數(shù)據(jù)元素之的邏輯順序；３順序表操作特點：1）可隨機(jī)存取順序表的元素；2）順序表的插入刪除操作要通過移動元素實現(xiàn)

第二章練習(xí)題１線性表的邏輯結(jié)構(gòu)：在線性表中，除第一個元素和第二章練習(xí)題４線性鏈表存儲特點1）用任意一組的存儲單元存儲線性表中的數(shù)據(jù)元素；2）通過保存直接后繼元素的存儲位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系；５線性鏈表操作特點1）不能隨機(jī)存取元素；2）插入、刪除操作通過修改結(jié)點的指針實現(xiàn)；６順序表的插入、刪除操作平均要移動表的一半元素

第二章練習(xí)題４線性鏈表存儲特點第二章練習(xí)題７順序表能隨機(jī)存取元素的原因是：順序表能通過L.elem[i-1]或L.elem+(i-1)直接定位元素的存儲地址。８線性鏈表不能隨機(jī)存取元素的原因是：需從線性鏈表的頭指針開始，順著鏈指針定位元素的存儲地址９對于經(jīng)常要存取元素的應(yīng)用，線性表應(yīng)采用順序存儲結(jié)構(gòu)10對于經(jīng)常要插入刪除元素的應(yīng)用，線性表應(yīng)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)第二章練習(xí)題７順序表能隨機(jī)存取元素的原因是：順序表能通過L第三章棧和隊列第三章棧和隊列

棧是限定僅能在表尾進(jìn)行插入刪除操作的線性表。（a1,a2...ai-1,ai,ai+1,…,an）棧底棧頂插入刪除棧的特點后進(jìn)先出3.1棧一.棧的概念1

棧的定義棧是限定僅能在表尾進(jìn)行插入刪除操作的線性表。

3.1棧2棧的基本操作

1）

初始化操作InitStack((&S)2）銷毀棧操作DestroyStack(&S)3）置空棧操作ClearStack(&S)4）取棧頂元素操作GetTop(S,&e)5）進(jìn)棧操作Push(&S,e)6）退棧操作Pop(&S,&e）7）判空操作StackEmpty(S)3.1棧2棧的基本操作3.1棧二棧的順序存儲和實現(xiàn)1棧的順序存儲結(jié)構(gòu)1）用一組連續(xù)的內(nèi)存單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素；2）

棧頂元素的位置由棧頂指針指示；3.1棧二棧的順序存儲和實現(xiàn)typedefstruct{

SElemType*base;//棧底指針

SElemType*top//棧頂指針

intstacksize;//當(dāng)前分配的?？臻g大小//(以sizeof(SElemType)為單位）

}SqStack;3.1棧

2順序棧的類型定義typedefstruct{

SElemType*ba3.1棧S.stacksizeS.topS.base9999nn-1n-210

an

an-1a2a1

順序棧的圖示3.1棧S.stacksize9999順序棧的圖示棧操作算法1）進(jìn)棧操作算法：在棧頂插入元素Push(SqStack&S,SElemTypee)2）出棧操作算法：在棧頂插入元素Pop(SqStack&S,SElemType&e)4棧操作主要特點進(jìn)棧、出棧操作要修改棧頂指針3.1棧棧操作算法3.1棧3.1棧棧的鏈?zhǔn)酱鎯蛯崿F(xiàn)棧的鏈?zhǔn)酱鎯εc線性表的鏈?zhǔn)酱鎯︻愃?，可用帶頭結(jié)點的線性鏈表存儲。注意：棧頂指針就是帶頭結(jié)點的線性鏈表的頭指針ai+1aiana1S3.1棧棧的鏈?zhǔn)酱鎯蛯崿F(xiàn)ai+1aiana1S四棧的應(yīng)用舉例例2表達(dá)式求值算符優(yōu)先算法：掌握利用操作數(shù)棧OPND，運算符棧OPTR，對表達(dá)式求值的方法3.2棧四棧的應(yīng)用舉例3.2棧第三章練習(xí)題１棧是限定僅能在表尾一端進(jìn)行插入、刪除操作的線性表；2表尾稱為棧頂，表頭稱為棧底；3棧的具有后進(jìn)先出的特點；4棧頂元素的位置由一個棧頂指針指示；5進(jìn)棧、出棧操作要修改棧頂指針；6

一個棧的輸入序列為a,b,c，則所有可能的出棧序列為：

abc,acb,bac,bca,cba第三章練習(xí)題１棧是限定僅能在表尾一端進(jìn)行插入、刪除操作的線一隊列的概念

１隊列的定義

隊列是限定僅能在表頭刪除，表尾插入的線性表。入隊

a1

a2

an隊頭隊尾出隊隊列的特點先進(jìn)先出3．4隊列一隊列的概念

１隊列的定義隊列是限定僅能2隊列的基本操作1）初始化操作InitQueue(&Q)

2）銷毀操作DestroyQueue(&Q)

3）置空操作ClearQueue(&Q)4）判空操作QueueEmpty(Q)5）取隊頭元素操作GetHead(Q,&e)

6）入隊操作EnQueue(&Q,e)

7）出隊操作DeQueue(&Q,&e)3．4隊列2隊列的基本操作3．4隊列二循環(huán)隊列——隊列的順序存儲和實現(xiàn)循環(huán)隊列——隊列的順序存貯結(jié)構(gòu)（1）在隊列的順序存貯結(jié)構(gòu)中用一組連續(xù)存儲單元依次存儲隊列的數(shù)據(jù)元素（2）隊頭、隊尾元素的位置分別由隊頭指針和隊尾指針指示；（3）將順序隊列設(shè)想為首尾相連的環(huán)狀空間3．4隊列二循環(huán)隊列——隊列的順序存儲和實現(xiàn)3．4隊列

2循環(huán)隊列的類型定義#defineMAXSIZE100//最大隊列長度

typedefstruct{

QElemType*base;隊空間基址

intfront;//隊頭指針

intrear;//隊尾指針}SqQueue;3．4隊列2循環(huán)隊列的類型定義#defineMAXSIZE103．4隊列2隊列操作算法入隊操作：在隊尾插入元素；出隊操作：在隊頭刪除元素；Q.baseQ.frontQ.rear03014325J3J2J13．4隊列2隊列操作算法Q.base0014325J3第三章練習(xí)題１隊列是限定僅能在表尾一端插入，表頭一端刪除操作的線性表；2表尾稱為隊頭，表頭稱為隊尾

3隊頭、隊尾元素的位置分別由隊頭指針和隊尾指針指示；4隊列具有先進(jìn)先出的特點5入隊操作要修改隊尾指針，出隊操作要修改隊頭指針；第三章練習(xí)題１隊列是限定僅能在表尾一端插入，表頭一端刪除操第四章串第四章串4.1串的基本概念一、串的概念

1什么是串串是由零個或多個字符組成的有限序列，一般記作s=‘a(chǎn)1,a2,a3,...an’4.1串的基本概念一、串的概念

1什么是串4.1串的基本概念2串的基本操作（了解）

串的邏輯結(jié)構(gòu)與線性表一樣，都是線性結(jié)構(gòu)。但由于串的應(yīng)用與線性表不同，串的基本操作與線性表有很大差別。串連接操作Concat(&T,S1,S2)求子串操作SubString(&Sub,S,pos,len)求子串位置操作Index(S,T,pos)

串插入操作StrInsert(&S,pos,T)串刪除操作StrDelete(&S,pos,len)4.1串的基本概念2串的基本操作（了解）

串4.2串存儲和實現(xiàn)一、串的存儲（了解）1定長順序存儲結(jié)構(gòu)

定長順序存儲結(jié)構(gòu)類似于C語言的字符數(shù)組，以一組地址連續(xù)的存儲單元存放串值字符序列，其類型說明如下：#defineMAXSTRLEN255TypedefunsignedcharSString[MAXSTRLEN+1]

4.2串存儲和實現(xiàn)一、串的存儲（了解）4.2串存儲和實現(xiàn)2、堆分配存儲堆分配存儲類似于線性表的順序存儲結(jié)構(gòu)

堆分配存儲的類型說明Typedefstruct{char*ch;//指向存放串值的存儲空間基址intlength;//整型域：存放串長}Hstring;4.2串存儲和實現(xiàn)2、堆分配存儲第四章練習(xí)題１從邏輯結(jié)構(gòu)上看串是線性數(shù)據(jù)結(jié)構(gòu)；２S=‘a(chǎn)babcabcac’,S1=‘a(chǎn)bc’，S2=‘isastring’Concat(Hstring&T,HstringS1,HstringS2)T=’abcisastring’3請列舉兩個線性表所沒有的串操作:求子串,求子串位置，第四章練習(xí)題１從邏輯結(jié)構(gòu)上看串是線性數(shù)據(jù)結(jié)構(gòu)；第五章數(shù)組和廣義表第五章數(shù)組和廣義表5．1數(shù)組1數(shù)組的邏輯結(jié)構(gòu)

n維數(shù)組中的每個元素都受n個線性關(guān)系的約束，以二維數(shù)組為例：二維數(shù)組中的每個元素都受兩個線性關(guān)系的約束5．1數(shù)組1數(shù)組的邏輯結(jié)構(gòu)5．1數(shù)組2數(shù)組的基本操作（了解）初始化操作InitArray(&A,n,bound1,…,boundn)功能：參數(shù)合法，構(gòu)造數(shù)組A，并返回OK；銷毀操作DestroyArray(&A)功能：銷毀數(shù)組A；3讀元素操作

Value(A,&e,index1,…,indexn)功能：若指定下標(biāo)不越界，讀指定下標(biāo)的元素，用e返回，并返回OK；寫元素操作

Assign(A,e,index1,…,indexn)功能：若指定下標(biāo)不越界，將e賦值給A指定的下標(biāo)元素，并返回OK；5．1數(shù)組2數(shù)組的基本操作（了解）

5．1數(shù)組3數(shù)組的順序存貯結(jié)構(gòu)(以二維數(shù)組為例)兩種方式：以行為主序的方式，以列序為主序的方式4數(shù)組元素存儲地址的計算5．1數(shù)組3數(shù)組的順序存貯結(jié)構(gòu)(以二維數(shù)組為例第五章練習(xí)題1從邏輯結(jié)構(gòu)來看，二維數(shù)組中的每個元素都受兩個線性關(guān)系的約束２在行關(guān)系中aij直接前趨是aij-1，aij直接后繼是aij+1；在列關(guān)系中aij直接前趨是ai-1jaij直接后繼是ai+1j；３二維數(shù)組的兩種順序存貯結(jié)構(gòu)為：１）以行為主序的方式，２）以列序為主序的方式。４數(shù)組元素存儲地址的計算

第五章練習(xí)題1從邏輯結(jié)構(gòu)來看，二維數(shù)組中的每個元素都受兩5．2矩陣的壓縮存儲矩陣壓縮存儲是指為多個值相同的元素分配一個存儲空間，對零元素不分配存儲空間一特殊矩陣1什么是特殊矩陣值相同元素或者零元素分布有一定規(guī)律的矩陣稱為特殊矩陣2特殊矩陣壓縮存儲特殊矩陣的壓縮存儲是根據(jù)元素的分布規(guī)律，確定元素的存儲位置與元素在矩陣中的位置的對應(yīng)關(guān)系；

5．2矩陣的壓縮存儲矩陣壓縮存儲是指為多個值相同的元5．2矩陣的壓縮存儲二稀疏矩陣1什么是稀疏矩陣有較多值相同元素或較多零元素，且值相同元素或者零元素分布沒有一定規(guī)律的矩陣稱為稀疏矩陣。

2

稀疏矩陣的壓縮存儲（只討論有較多零元素矩陣的壓縮存儲）稀疏矩陣的壓縮存儲只存非零元，對每一非零元，除了要保存非零元素的值外，還要保存非零元素在矩陣中的位置；5．2矩陣的壓縮存儲二稀疏矩陣5．2矩陣的壓縮存儲3稀疏矩陣的（非零元）三元組表

A=((1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))4三元組順序表用順序表存儲三元組表，非零元三元組以行為主序存儲5．2矩陣的壓縮存儲3稀疏矩陣的（非零元）三元組表第五章練習(xí)題1矩陣壓縮存儲是指為多個值相同的元素分配一個存儲空間，對零元素不分配存儲空間；2特殊矩陣的壓縮存儲是根據(jù)元素的分布規(guī)律，確定元素的存儲位置與元素在矩陣中的位置的對應(yīng)關(guān)系；3(含零元的)稀疏矩陣的壓縮存儲只存非零元，對每一非零元，除了要保存零元素的值外，還要保存零元素在矩陣中的位置；4給出稀疏矩陣，寫出對應(yīng)的（非零元）三元組表

A=((1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))第五章練習(xí)題1矩陣壓縮存儲是指為多個值相同的元素分配一5．3廣義表1什么是廣義表廣義表是數(shù)據(jù)元素的有限序列。記作：LS=(α1,α2,…,αn)。其中αi其可以是單個元素，也可以是廣義表。2廣義表的基本操作求表頭求表尾表頭：廣義表的第一個元素表尾：除第一個元素外，起它元素組成的表

5．3廣義表1什么是廣義表5．3廣義表３廣義表的存儲結(jié)構(gòu)（了解）廣義表通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。鏈表中有兩種的結(jié)點：一種是表結(jié)點，用以表示廣義表；一種是原子結(jié)點，用以表示原子；5．3廣義表３廣義表的存儲結(jié)構(gòu)（了解）第五章練習(xí)題１廣義表是數(shù)據(jù)元素的有限序列。其元素可以是單個元素，也可以是廣義表。2表頭：廣義表的第一個元素表尾：除第一個元素外，其它元素組成的表第五章練習(xí)題１廣義表是數(shù)據(jù)元素的有限序列。其元素可以是單個第六章樹和二叉樹第六章樹和二叉樹6.1樹的有關(guān)概念一樹的概念1樹的邏輯結(jié)構(gòu)樹：是一種一對多的結(jié)構(gòu)關(guān)系或稱為分枝結(jié)構(gòu)關(guān)系，除了根之外，每個元素只有一個直接前趨；，但每個元素可以有零個或多個直接后繼；JIHGFEDBAC6.1樹的有關(guān)概念一樹的概念JIHGFEDBAC6.1樹的有關(guān)概念

2樹的基本操作（了解）1）InitTree(&T);2）DestroyTree(&T);3）CreateTree(&T,definition);4）ClearTree(&T);5）TreeEmpty(T);6）TreeDepth(T);6.1樹的有關(guān)概念2樹的基本操作（了解）6.1樹的有關(guān)概念Root(T);Value(T,cur_e);Assign(T,cur_e,value);Paret(T,cur_e);LeftChild(T,cur_e);RightSibling(T,cur_e);InsertChild(&T,&p,i,c);DeleteChild(&T,&p,i);TraverseTree(T,Visit());6.1樹的有關(guān)概念Root(T);6.1樹的有關(guān)概念2．樹的應(yīng)用

1）樹可表示具有分枝結(jié)構(gòu)關(guān)系的對象例1．家族族譜JIHGFEDBAC6.1樹的有關(guān)概念2．樹的應(yīng)用

1）樹可表示具有分枝結(jié)構(gòu)6.1樹的有關(guān)概念2）樹是常用的數(shù)據(jù)組織形式有些應(yīng)用中數(shù)據(jù)元素之間并不存在間分支結(jié)構(gòu)關(guān)系，但是為了便于管理和使用數(shù)據(jù)，將它們用樹的形式來組織。文件夾1文件夾n文件1文件2文件夾21文件夾22文件21文件22C6.1樹的有關(guān)概念2）樹是常用的數(shù)據(jù)組織形式文件夾16.1樹的有關(guān)概念3）一些應(yīng)用問題的求解過程可用樹結(jié)構(gòu)的來描述

{1}{}{1,2}{1}{2}{}{1,2,3}{1,2}{1,3}{1}{2,3}{2}{3}{}{}例5求A={1,2,3}的冪集6.1樹的有關(guān)概念3）一些應(yīng)用問題的求解過程可用樹結(jié)構(gòu)的6.1樹的有關(guān)概念樹的基本術(shù)語（了解）樹的結(jié)點孩子結(jié)點雙親結(jié)點兄弟結(jié)點結(jié)點層樹的高度結(jié)點的度樹的度葉子結(jié)點分枝結(jié)點森林JIHGFEDBAC6.1樹的有關(guān)概念樹的基本術(shù)語（了解）JIHGFEDBA6.2二叉樹一二叉樹的概念1二叉樹的定義二叉樹：或為空樹，或由根及兩顆不相交的左子樹、右子樹構(gòu)成，并且左、右子樹本身也是二叉樹。

A

F

G

E

D

C

B6.2二叉樹一二叉樹的概念A(yù)FGED6.2二叉樹二叉樹的五種基本形態(tài)φ6.2二叉樹二叉樹的五種基本形態(tài)φ6.2二叉樹2基本操作：（了解）InitBiTree(&T);DestroyBiTree(&T);CreateBiTree(&T,definition);ClearBiTree(&T);BiTreeEmpty(T);BiTreeDepth(T);6.2二叉樹2基本操作：（了解）6.2二叉樹Root(T);Value(T,e);Assign(T,&e,value);Parent(T,e);LeftChild(T,e)RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);6.2二叉樹Root(T);6.2二叉樹InsertChild(T,p,LR,c);DeleteChild(T,p,LP);PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());6.2二叉樹InsertChild(T,p,L6.2二叉樹3二叉樹性質(zhì)（了解）

A

F

E

D

C

B1234566.2二叉樹3二叉樹性質(zhì)（了解）AFED6.2二叉樹三二叉樹存貯結(jié)構(gòu)1二叉樹的順序結(jié)構(gòu)

167245389

A

F

G

E

D

C

B

A

F

G

E

D

C

B123456789m-1

ABCDEFG6.2二叉樹三二叉樹存貯結(jié)構(gòu)1672453896.2二叉樹2二叉鏈表

二叉鏈表中每個結(jié)點至少包含三個域：數(shù)據(jù)域、左指針域、右指針域

A

B∧

C∧∧

D∧

E∧∧F∧

A

F

E

D

C

B6.2二叉樹2二叉鏈表AB∧6.2二叉樹3三叉鏈表

三叉鏈表中每個結(jié)點至少包含四個域：數(shù)據(jù)域、雙親指針域、左指針域、右指針域6.2二叉樹3三叉鏈表6.2二叉樹靜態(tài)二叉鏈表（了解）A13C05B00E00F00D4

0123456Lchilddatarchild

A

F

E

D

C

B6.2二叉樹靜態(tài)二叉鏈表（了解）A10Lc6.3二叉樹的遍歷遍歷：按某種搜索路徑訪問二叉樹的每個結(jié)點，而且每個結(jié)點僅被訪問一次。1二叉樹的遍歷方法先序遍歷DLR中序遍歷LDR后序遍歷LRD6.3二叉樹的遍歷遍歷：按某種搜索路徑訪問二叉樹的每個結(jié)6.3二叉樹的遍歷先序遍歷（DLR）若二叉樹非空

（1）訪問根結(jié)點；

（2）先序遍歷左子樹；

（3）先序遍歷右子樹；例先序遍歷序列：-,+,a,*,b,-,c,d,/,e,f

e

d

c

b

f

a

+

*

/

-

-6.3二叉樹的遍歷先序遍歷（DLR）例先序遍歷序列：6.3二叉樹的遍歷中序遍歷（LDR）若二叉樹非空

（1）中序遍歷左子樹

（2）訪問根結(jié)點（3）中序遍歷右子樹例中序遍歷序列：a,+,b,*,c,-,d,-,e,/,f

e

d

c

b

f

a

+

*

/

-

-6.3二叉樹的遍歷中序遍歷（LDR）例中序遍歷序列：6.3二叉樹的遍歷后序遍歷（LRD）若二叉樹非空

（1）后序遍歷左子樹

（2）后序遍歷右子樹（3）訪問根結(jié)點例后序遍歷序列：a,b,c,d,-,*,+,e,f,/,-

e

d

c

b

f

a

+

*

/

-

-6.3二叉樹的遍歷后序遍歷（LRD）例后序遍歷序列：6.4遍歷的應(yīng)用例1求二叉樹的葉子結(jié)點個數(shù)

輸入：二叉樹的二叉鏈表

結(jié)果：二叉樹的葉子結(jié)點個數(shù)基本思想：在二叉樹遍歷的過程中，統(tǒng)計葉子結(jié)點的個數(shù)6.4遍歷的應(yīng)用例1求二叉樹的葉子結(jié)點個數(shù)

輸入：二6.5線索二叉樹1．線索二叉樹加上結(jié)點前趨后繼信息（結(jié)索）的二叉樹稱為線索二叉樹中序序列：D,B,H,E,A,F,C,G

A

G

H

E

D

C

B

F

A

G

H

E

D

C

B

F6.5線索二叉樹1．線索二叉樹中序序列：D,B,H,E,6.5線索二叉樹F11E01G11D11A00B00H11C0001頭結(jié)點2線索鏈表線索二叉樹的存儲結(jié)構(gòu)，利用二叉鏈表的空指針域保存結(jié)點的前趨后繼結(jié)點的指針6.5線索二叉樹F11E01G11D11A00B00H16.6樹和森林

一．樹的存貯結(jié)構(gòu)（了解）了解樹的存貯方法1雙親表示法

雙親表示法：通過保存每個結(jié)點的雙親結(jié)點的位置，表示樹中結(jié)點之間的結(jié)構(gòu)關(guān)系。

6.6樹和森林一．樹的存貯結(jié)構(gòu)（了解）

6.6樹和森林2、孩子表示法

孩子表示法：通過保存每個結(jié)點的孩子結(jié)點的位置，表示樹中結(jié)點之間的結(jié)構(gòu)關(guān)系。方法I：多重鏈表（類似二叉鏈表）3孩子兄弟表示法

該方法用二叉鏈表作為樹的存貯結(jié)構(gòu)

通過保存每個結(jié)點的第一個結(jié)點和它的緊鄰的右兄弟的位置，表示樹中結(jié)點之間的結(jié)構(gòu)關(guān)系。

6.6樹和森林2、孩子表示法

孩子表示法：通過保存每個6.6樹和森林樹與二叉樹的轉(zhuǎn)換

二叉樹與樹都可用二叉鏈表存貯，以二叉鏈表作中介，可導(dǎo)出樹與二叉樹之間的轉(zhuǎn)換。樹與二叉樹轉(zhuǎn)換方法樹根結(jié)點X的第一個孩子結(jié)點X緊鄰的右兄弟二叉樹根結(jié)點X的左孩子結(jié)點X的右孩子6.6樹和森林樹與二叉樹的轉(zhuǎn)換樹二叉樹6.6樹和森林樹根結(jié)點X的第一個孩子結(jié)點X緊鄰的右兄弟二叉樹根結(jié)點X的左孩子結(jié)點X的右孩子FIABDHGCEIHGFEDBAC6.6樹和森林樹二叉樹FIABDHGCEIHGFEDBA6.6樹和森林三樹的遍歷先根遍歷先訪問根，然后依次先根遍歷根每一顆子樹。

例先根遍歷序列ABCDE后根遍歷依次后根遍歷根的每一顆子樹，然后訪問根。

后根遍歷序列BDCEA6.6樹和森林三樹的遍歷6.7哈夫曼樹及應(yīng)用

1哈夫曼樹

帶權(quán)路徑最短的二叉樹2哈夫曼編碼

6.7哈夫曼樹及應(yīng)用

1哈夫曼樹第六章練習(xí)題1二叉樹的順序結(jié)構(gòu):通過二叉樹結(jié)點的相對位置，表示結(jié)點之間結(jié)構(gòu)關(guān)系2二叉鏈表：通過保存每個結(jié)點的左、右孩子結(jié)點的存儲位置，表示結(jié)點之間的結(jié)構(gòu)關(guān)系。3遍歷：按某種搜索路徑訪問二叉樹的每個結(jié)點，而且每個結(jié)點僅被訪問一次。4二叉樹的遍歷方法:先序遍歷DLR、中序遍歷LDR、后序遍歷LRD第六章練習(xí)題1二叉樹的順序結(jié)構(gòu):通過二叉樹結(jié)點的相對位置第六章練習(xí)題5設(shè)p是指向二叉鏈表某結(jié)點的指針，請寫出將左孩子結(jié)點數(shù)據(jù)賦值給變量e的主要操作語句：q=p-lchild;.e=q->data;6加上結(jié)點前趨后繼信息的二叉樹稱為線索二叉樹7在線索鏈表中左右指針域或指向孩子結(jié)點或指向前趨后繼結(jié)點8列舉與樹的兩種存儲結(jié)構(gòu)第六章練習(xí)題5設(shè)p是指向二叉鏈表某結(jié)點的指針，請寫出將左孩7.1圖的基本概念一圖的概念1圖的邏輯結(jié)構(gòu)是一種多對多的結(jié)構(gòu)關(guān)系，每個元素可以有零個或多個直接前趨；零個或多個直接后繼；7.1圖的基本概念一圖的概念7.1圖的基本概念無向圖：在圖G中，若所有邊是無向邊，則稱G為無向圖

有向圖：在圖G中，若所有邊是有向邊，則稱G為有向圖

混和圖：在圖G中，即有無向邊也有有向邊，則稱G為混合圖

V5

V1

V2

V4

V3

V1

V2

V3

V4

V1

V2

V3

V47.1圖的基本概念無向圖：在圖G中，若所有邊是無向邊，則7.1圖的基本概念2圖的基本操作（了解）

CreateGraph(&G,V,VR);DestroyGraph(&G);LocateVex(G,u);GetVex(G,v);PutVex(&G,v,value);7.1圖的基本概念2圖的基本操作（了解）

7.1圖的基本概念FirstAdjVex(G,v);NextAdjVex(G,v,w);InsertVex(&G,v);DeleteVex(&G,v);InsertArc(&G,v,w);DeleteArc(&G,v,w);DFSTraverse(G,v,Visit());BFSTraverse(G,v,Visit());7.1圖的基本概念FirstAdjVex(G,v);7.1圖的基本概念二圖的應(yīng)用舉例（了解）

例1交通圖（公路、鐵路）頂點：地點邊：連接地點的公路交通圖中的有單行道雙行道，分別用有向邊、無向邊表示；例4各種流程圖

V5

V1

V2

V4

V37.1圖的基本概念二圖的應(yīng)用舉例（了解）

V5V17.1圖的基本概念三圖的基本術(shù)語（了解）1）鄰接點及關(guān)聯(lián)邊2）頂點的度、入度、出度3）路徑、回路4）連通圖5）子圖

V5

V1

V2

V4

V37.1圖的基本概念三圖的基本術(shù)語（了解）V5V17.2圖的存儲結(jié)構(gòu)一數(shù)組表示法圖的鄰接矩陣

數(shù)組表示法是圖的一種順序存儲結(jié)構(gòu)

V5

V1

V2

V4

V3010100101010110100011007.2圖的存儲結(jié)構(gòu)一數(shù)組表示法圖的鄰接矩陣7.2圖的存儲結(jié)構(gòu)數(shù)組表示法頂點的存儲：通常按頂點的編號順序?qū)㈨旤c數(shù)據(jù)存儲在一維數(shù)組中;

頂點間關(guān)系的存儲：用二維數(shù)組存儲圖的鄰接矩陣；7.2圖的存儲結(jié)構(gòu)數(shù)組表示法7.2圖的存儲結(jié)構(gòu)012345m-1V1V2V3V4V5010101010101234mm+1m+2m+3m+4存儲頂點的一維數(shù)組存儲鄰接矩陣的二維數(shù)組7.2圖的存儲結(jié)構(gòu)0V100存儲頂點的存儲鄰接矩陣的7.2圖的存儲結(jié)構(gòu)無向圖數(shù)組表示法特點：

1）無向圖鄰接矩陣是對稱矩陣，同一條邊表示了兩次；

2）判斷兩頂點v、u是否為鄰接點：只需判二維數(shù)組對應(yīng)分量是否為1；

3）頂點不變，在圖中增加、刪除邊：只需對二維數(shù)組對應(yīng)分量賦值1或清0；

4）設(shè)存儲頂點的一維數(shù)組大小為m(m圖的頂點數(shù)n),G占用存儲空間：m+m2；G占用存儲空間只與它的頂點數(shù)有關(guān)，與邊數(shù)無關(guān)；適用于邊稠密的圖；

7.2圖的存儲結(jié)構(gòu)無向圖數(shù)組表示法特點：

1）無向圖鄰接7.2圖的存儲結(jié)構(gòu)鄰接表鄰接表是圖的鏈?zhǔn)酱鎯Y(jié)構(gòu)

1無向圖的鄰接表頂點：通常按編號順序?qū)㈨旤c數(shù)據(jù)存儲在一維數(shù)組中；關(guān)聯(lián)同一頂點的邊：用線性鏈表存儲7.2圖的存儲結(jié)構(gòu)鄰接表7.2圖的存儲結(jié)構(gòu)

V5

V1

V2

V4

V3例01234m-1V1V2V3V4V5134221100437.2圖的存儲結(jié)構(gòu)V5V1V2V4V3例07.2圖的存儲結(jié)構(gòu)無向圖的鄰接表的特點（1）在G鄰接表中，同一條邊對應(yīng)兩個結(jié)點；

（2）判定兩頂點v，u是否鄰接：要看v對應(yīng)線性鏈表中有無對應(yīng)的結(jié)點；（3）在G中增減邊：要在兩個單鏈表插入、刪除結(jié)點；（4）G占用存儲空間：m+2*eG占用存儲空間與G的頂點數(shù)有關(guān)，與G的邊數(shù)有關(guān)；適用于邊稀疏的圖；7.2圖的存儲結(jié)構(gòu)無向圖的鄰接表的特點7.2圖的存儲結(jié)構(gòu)2有向圖的鄰接表和逆鄰接表1）有向圖的鄰接表類似于無向圖的鄰接表，所不同的是：以同一頂點為起點的弧：用線性鏈表存儲例：

V1

V2

V3

V40123

m-1V1V2V3V412307.2圖的存儲結(jié)構(gòu)2有向圖的鄰接表和逆鄰接表V7.2圖的存儲結(jié)構(gòu)2）有向圖的逆鄰接表類似于無向圖的鄰接表，所不同的是：以同一頂點為終點的弧：用線性鏈表存儲例：

V1

V2

V3

V40123

m-1V1V2V3V400237.2圖的存儲結(jié)構(gòu)2）有向圖的逆鄰接表V1V2V37.3圖的遍歷

圖的遍歷：從圖的某頂點出發(fā)，訪問圖中所有頂點，并且每個頂點僅訪問一次。1深度優(yōu)先遍歷（連通圖的遍歷）

從圖中某頂點v出發(fā)：

1）訪問頂點v；

2）從v的未被訪問的鄰接點出發(fā)對圖進(jìn)行深度優(yōu)先遍歷；7.3圖的遍歷圖的遍歷：從圖的某7.3圖的遍歷例圖G中，以V1起點的的深度優(yōu)先序列：(1)V1,V2,V4,V5,V8,V3,V6,V7(2)V1,V3,V6,V7,V2,V4,V8,V5,由于沒為有規(guī)定訪問鄰接點的順序，深度優(yōu)先序列不是唯一的

V4

V1

V2

V5

V8

V8

V7

V6

V5

V4

V3

V2

V17.3圖的遍歷例圖G中，以V1起點的的深度優(yōu)先序列：7.3圖的遍歷2廣義優(yōu)先遍歷（按層遍歷）從圖中某頂點v出發(fā)：1）訪問出發(fā)點v；2）然后訪問v的所有未被訪問的鄰接點w1,w2,

…wk；3）然后依次從這些鄰接點出發(fā)，訪問它們的所有未被訪問的鄰接點;依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問；7.3圖的遍歷2廣義優(yōu)先遍歷（按層遍歷）7.3圖的遍歷例圖G中，以V1起點的的廣度優(yōu)先序列：

V1,V2,V3,V4,V8,V5,V6,V7,

V1,V3,V2,V6,V7,V4,V5,V8由于沒為有規(guī)定訪問鄰接點的順序，深度優(yōu)先序列不是唯一的

V8

V7

V6

V5

V4

V3

V2

V17.3圖的遍歷例圖G中，以V1起點的的廣度優(yōu)先序列：7.3圖的遍歷3非連通圖的遍歷（了解）

深度優(yōu)先序列：V1,V2,V3,V4,V5,V6廣度優(yōu)先序列：V1,V2,V4,V3,V5,V6,

V5

V6

V3

V1

V2

V4

V3

V1

V2

V4

V5

V67.3圖的遍歷3非連通圖的遍歷（了解）

V5V67.4有向無環(huán)圖的應(yīng)用應(yīng)用中，可用有向圖來表示工程的流程AOV網(wǎng)(activityonvertexnet）AOE網(wǎng)(activityonedgenet7.4有向無環(huán)圖的應(yīng)用應(yīng)用中，可用有向圖來表示工程的流7.4有向無環(huán)圖的應(yīng)用AOV網(wǎng)(activityonvertexnet)用頂點表示活動，邊表示活動的順序的有向圖稱為AOV網(wǎng)例1某工程可分為7個子工程，工程流程可用如下AOV網(wǎng)表示：

V1

V4

V7

V3

V6

V5

V27.4有向無環(huán)圖的應(yīng)用AOV網(wǎng)(activityo7.4有向無環(huán)圖的應(yīng)用4AOE網(wǎng)(activityonedgenet)用邊表示活動，頂點表示事件的有向圖稱為AOE網(wǎng)事件發(fā)生表示以該事件為起點的話動可以開始，以該事件為終點的話動已經(jīng)。

V6

V5

V1

V4

V3

V2

V7

V8a1a3a6a2a5a4a7a8a97.4有向無環(huán)圖的應(yīng)用4AOE網(wǎng)(activit7.4有向無環(huán)圖的應(yīng)用2拓?fù)渑判蛲負(fù)湫蛄校河邢驁DD的一個頂點序列稱作一個拓?fù)湫蛄校绻撔蛄兄腥蝺身旤cv、u，若在D中v是u前趨，則在序列中v也是u前趨。

拓?fù)渑判?就是將有向圖中頂點排成拓?fù)湫蛄?/p>

V1

V4

V7

V3

V6

V5

V27.4有向無環(huán)圖的應(yīng)用2拓?fù)渑判騐1V4V77.4有向無環(huán)圖的應(yīng)用拓?fù)渑判蚍椒ǎ?）從有向圖選一無前趨的頂點V，輸出；

2）從有向圖中刪除V及以V為尾的孤；

3）重復(fù)1）、2）、直接全部輸出全部頂點或有向圖中不存在無前趨頂點例；

V1

V4

V7

V3

V6

V5

V2拓?fù)湫蛄校篤1V2V3V4V5V6V7V2V1V5V4V3V7V67.4有向無環(huán)圖的應(yīng)用拓?fù)渑判蚍椒ǎ篤1V4V7第七章練習(xí)題1圖的邏輯結(jié)構(gòu)：圖是一種多對多的結(jié)構(gòu)關(guān)系，每個元素可以有零個或多個直接前趨；零個或多個直接后繼；3數(shù)組表示法用鄰接矩陣表示結(jié)點間的鄰接關(guān)系4鄰接表是圖的鏈?zhǔn)酱鎯Y(jié)構(gòu)5鄰接表用頂點關(guān)聯(lián)邊的線性鏈表表示結(jié)點間的鄰接關(guān)系；第七章練習(xí)題1圖的邏輯結(jié)構(gòu)：圖是一種多對多的結(jié)構(gòu)關(guān)系，每9.1概述本章討論數(shù)據(jù)結(jié)構(gòu)：查找表一查找表的概念1查找表：由同一類型數(shù)據(jù)元素（或記錄）構(gòu)成的集合。2查找表基本操作構(gòu)造查找表Create(&ST,n)2銷毀查找表Destroy(&ST)3各種查找操作9.1概述本章討論數(shù)據(jù)結(jié)構(gòu)：查找表2查找表基本操作9.1概述二查找的分類及查找的概念（了解）

學(xué)號姓名專業(yè) 年齡

01 王洪 計算機(jī)17

02孫文計算機(jī)18

03 謝軍計算機(jī)18

04 李輝 計算機(jī)20

05 沈祥福計算機(jī)25

…9.1概述二查找的分類及查找的概念（了解）

學(xué)號9.1概述1按查找條件等值查找：區(qū)域查找組合查找2按返回結(jié)果返回記錄的位置返回記錄或記錄的某些屬性3按查找操作是否修改查找表靜態(tài)查找：動態(tài)查找：

9.1概述1按查找條件9.1概述三查找表的組織方法和查找方法靜態(tài)查找表順序表及查找

有序表及查找

動態(tài)查找表

二叉排序樹哈希表哈希表及查找9.1概述三查找表的組織方法和查找方法9.1概述平均查找長度（了解）

（設(shè)查找不成功的可能性很小，可忽略不計）查找方法的平均查找長度=在查找過程中，與給定值比較的關(guān)鍵字個數(shù)的數(shù)學(xué)期望值9.1概述平均查找長度（了解）

9.2靜態(tài)查找表1順序表及查找（線性表及查找）查找表組織：將查找表中的記錄按線性表的形式來組織L1=(45,53,12,3,37,24,100,61,90,78)順序查找法1）基本思想：從表的最后一個記錄（或第一個記錄）開始，依次將記錄的關(guān)鍵字與給定值比較，若相等：查找成功，否則，繼續(xù)查找。9.2靜態(tài)查找表1順序表及查找（線性表及查找）9.2靜態(tài)查找表2）說明：優(yōu)點1）算法簡單2）對于查找表的存儲結(jié)構(gòu)沒有特別的要求缺點效率不高，平均查找長度=（n+1）/29.2靜態(tài)查找表2）說明：9.2靜態(tài)查找表有序表及查找

1有序表：查找表中的記錄按關(guān)鍵字有序序

2二分查找法1）基本步驟：將查找范圍中間位置的記錄關(guān)鍵字與給定值比較：

＜：繼續(xù)在前半個表中查找

=：查找成功，返回記錄位置

＞：繼續(xù)在后半個表中查找

12345678910L2=(3,12,24,37,45,53,61,78,90,100)K=249.2靜態(tài)查找表有序表及查找

1有序表：查找表中的記錄9.2靜態(tài)查找表2）說明：*效率比順序查找高;平均查找長度=log2（n+1）*要求查找表中的記錄按關(guān)鍵字有序；*查找表中的記錄要用順序表存儲；9.2靜態(tài)查找表2）說明：9.3動態(tài)查找表1

二叉排序樹2二叉排序樹插入3二叉排序樹的查找

45

53100

61

90

78

123

37

249.3動態(tài)查找表1

二叉排序樹4553100619.3動態(tài)查找表關(guān)鍵字序列：45,53,12,3,100,37,24,61,90,78

45

53100

61

90

78

123

37

249.3動態(tài)查找表關(guān)鍵字序列：45,53,12,3,100,9.4哈希表上兩節(jié)介紹的查找表的查找方法共同特點：通過比較查找，即通過將記錄關(guān)鍵字值與給定值比較，來進(jìn)行查找。查找算法的時間效率取決于查找過程中所進(jìn)行的比較次數(shù)。9.4哈希表上兩節(jié)介紹的查找表的查找方法共同特點：9.4哈希表1哈希函數(shù)

用來定義記錄的關(guān)鍵字與記錄存儲位置的對應(yīng)關(guān)系的函數(shù)2哈希表：將記錄按哈希函數(shù)或解決沖突的方法確定的位置存放，所構(gòu)成的表稱為哈希表1949195019511999200020002100220044004420年份人數(shù)1235152例1949-2000年某地區(qū)人口統(tǒng)計表哈希函數(shù)

H（KEY）=KEY-19489.4哈希表1哈希函數(shù)用來定義記錄的關(guān)鍵字與記錄存儲9.4哈希表哈希函數(shù)H（KEY）=KEY-19483沖突：不同的關(guān)鍵字由哈希函數(shù)確定的記錄的存儲位置相同4解決沖突的方法：開放地址法，鏈地址法5哈希表的查找方法：對于給定值，由哈希函數(shù)直接定位記錄的存儲位置1949195019511999200020002100220044004420年份人數(shù)12351529.4哈希表哈希函數(shù)H（KEY）=KEY-19483第九章練習(xí)題1查找表的邏輯結(jié)構(gòu)：查找表中的記錄除同屬一個集合外，沒有其他關(guān)系2順序查找法的優(yōu)點簡單、對查找表及存儲結(jié)構(gòu)沒有什么特殊的要求。3二分查找法的優(yōu)點查找效率高4二分查找法要求查找表中的記錄按關(guān)鍵字有序5用二叉排序樹組織查找表的優(yōu)點是既可能有較高的查找效率又可能有較高插入刪除效率第九章練習(xí)題1查找表的邏輯結(jié)構(gòu)：查找表中的記錄除同屬一個第九章練習(xí)題6哈希表：將記錄按哈希函數(shù)或解決沖突的方法確定的位置存放，所構(gòu)成的表稱為哈希表7何為沖突：不同的關(guān)鍵字由哈希函數(shù)確定的記錄的存儲位置相同8列舉兩種解決沖突的方法：開放地址法、鏈地址法第九章練習(xí)題6哈希表：將記錄按哈希函數(shù)或解決沖突的方法確10.1概述1排序定義

設(shè)R1

R2R3

…Rn是n個記錄，k1,k2,k3

…kn為它們的關(guān)鍵字，排序就是將記錄按關(guān)鍵字遞增（或遞減）的次序排列起來。10.1概述1排序定義10.1概述2分類（了解）

按記錄的存放位置分類有內(nèi)排序：待排記錄放在內(nèi)存

外排序：待排記錄放在外存·按排序原則分類（內(nèi)排序）

插入排序

交換排序

選擇排序

歸并排序

基數(shù)排序10.1概述2分類（了解）

按記錄的存放位置分類有10.1概述穩(wěn)性排序：在任何兩個關(guān)鍵字相同的記錄，用某種排序方法排序后相對位置不變，則稱這種排序方法是穩(wěn)定的，否則稱為不穩(wěn)定的。例設(shè)49,38,65,97,76,13,27,49是待排序列排序后:13,27,38,49,49,65,76,97——穩(wěn)定排序后:13,27,38,49,49,65,76,97——不穩(wěn)定10.1概述穩(wěn)性排序：第十章練習(xí)題1下面幾種排序方法的基本思想

插入，交換、選擇，歸并2能寫出直接插入、快速排序一趟排序過程第十章練習(xí)題1下面幾種排序方法的基本思想《數(shù)據(jù)結(jié)構(gòu)》西南民院計算機(jī)系

TEmailliu-li-1@163.net

《數(shù)據(jù)結(jié)構(gòu)》西南民院計算機(jī)系148題型1選擇題2填空題3解答題4算法題題型第一章緒論第一章緒論第一章緒論計算機(jī)的發(fā)展硬件

CPU、內(nèi)、外存儲器等軟件：系統(tǒng)軟件、應(yīng)用軟件應(yīng)用科學(xué)計算數(shù)據(jù)處理過程控制等處理數(shù)據(jù)的能力和種類：數(shù)值字符、字符串具有多個屬性對象圖形圖像聲音第一章緒論計算機(jī)的發(fā)展數(shù)據(jù)結(jié)構(gòu)的研究對象：非數(shù)值數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，如何表示，

如何存儲，如何處理的問題。

本課程討論的問題：應(yīng)用中常用的幾種數(shù)據(jù)結(jié)構(gòu)，以及如何存儲,如何處理它們。第一章緒論數(shù)據(jù)結(jié)構(gòu)的研究對象：第一章緒論1數(shù)據(jù)：客觀對象的符號表示。例如：課程名，地名，書名都是數(shù)據(jù)2數(shù)據(jù)結(jié)構(gòu)：帶有結(jié)構(gòu)和操作的數(shù)據(jù)元素集合結(jié)構(gòu)：數(shù)據(jù)元素之間的關(guān)系；

操作：對數(shù)據(jù)的加工處理；第一章緒論1數(shù)據(jù)：客觀對象的符號表示。第一章第一章緒論3數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，是具體關(guān)系的抽象。4常用的有下列幾類基本結(jié)構(gòu)：

（1）集合

（2）線性結(jié)構(gòu)

（3）樹結(jié)構(gòu)

（4）圖結(jié)構(gòu)（5）其它復(fù)雜結(jié)構(gòu)5數(shù)據(jù)結(jié)構(gòu)的基本操作：也叫基本運算：是指對數(shù)據(jù)結(jié)構(gòu)的加工處理；第一章緒論3數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)之間的結(jié)構(gòu)第一章緒論6數(shù)據(jù)的存儲結(jié)構(gòu)：

數(shù)據(jù)結(jié)構(gòu)在計算機(jī)內(nèi)存中的表示。

7順序存儲結(jié)構(gòu)用一組連續(xù)的內(nèi)存單元存放數(shù)據(jù)元素，用元素相對的存儲位置表示元素之間的結(jié)構(gòu)關(guān)系；8鏈?zhǔn)酱鎯Y(jié)構(gòu)

用任意一組存儲單元存儲數(shù)據(jù)元素，對每個數(shù)據(jù)元素除了保存自身信息外，還保存相關(guān)元素的存儲位置。

數(shù)據(jù)結(jié)構(gòu)基本操作的實現(xiàn)：基本操作在計算機(jī)上的實現(xiàn)（方法）第一章緒論6數(shù)據(jù)的存儲結(jié)構(gòu)：9數(shù)據(jù)結(jié)構(gòu)的表示1圖示表示2二元組表示圖示表示：由頂點和邊構(gòu)成的圖，其中頂點表示數(shù)據(jù)，邊表示數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系；第一章緒論JIHGFEDBAC9數(shù)據(jù)結(jié)構(gòu)的表示圖示表示：由頂點和邊構(gòu)成的圖，其中頂點表示二元組表示

用一個二元組（D，S）表示數(shù)據(jù)結(jié)構(gòu)，其中D是數(shù)據(jù)元素集合，S是D上關(guān)系的集合。

D={A，B，C，D，E，F(xiàn)，G，H，I，J}

S={R}

R={〈A,B>,<B,C>,<C,D><D,E>,<E,F>,<F,G>,<G,H>,<H,I>,<I,J>}第一章緒論二元組表示

用一個二元組（D，S）表示數(shù)據(jù)結(jié)構(gòu)，其中第一章緒論10算法的概念

算法是求解問題的操作序列（或操作步驟）11時間復(fù)雜度T（n）

以求解問題的基本操作（原操作）的執(zhí)行次數(shù)作為算法的時間度量

空間復(fù)雜度用執(zhí)行算法所需的輔助空間的大小作為算法所需空間的度量第一章緒論10算法的概念第一章練習(xí)題1數(shù)據(jù)結(jié)構(gòu)：帶有結(jié)構(gòu)和操作的數(shù)據(jù)元素集合。2常用的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的表示4數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，是具體關(guān)系的抽象。數(shù)據(jù)結(jié)構(gòu)的基本操作：也叫基本運算：是指對數(shù)據(jù)結(jié)構(gòu)的加工處理；數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計算機(jī)內(nèi)存中的表示數(shù)據(jù)結(jié)構(gòu)基本操作的實現(xiàn)：基本操作在計算機(jī)上的實現(xiàn)（方法）順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)10算法的概念

算法是求解問題的操作序列（或操作步驟）。11時間復(fù)雜度T（n）以求解問題的基本操作（原操作）的執(zhí)行次數(shù)作為算法時間的度量第一章練習(xí)題1數(shù)據(jù)結(jié)構(gòu)：帶有結(jié)構(gòu)和操作的數(shù)據(jù)元素集合。第二章線性表第二章線性表常用的數(shù)據(jù)結(jié)構(gòu)1）集合

2）線性結(jié)構(gòu)

3）樹結(jié)構(gòu)

4）圖結(jié)構(gòu)

5）其它復(fù)雜結(jié)構(gòu)第二章線性表對每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下兩方面的問題1數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)的基本操作；2數(shù)據(jù)的存儲結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)基本操作的實現(xiàn)

常用的數(shù)據(jù)結(jié)構(gòu)第二章線性表對每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下兩

第二章線性表線性數(shù)據(jù)結(jié)構(gòu)：

除第一個元素和最后一個元素之外，其他元素都有且僅有一個直接前趨，有且僅有一個直接后繼。第二章線性表線性數(shù)據(jù)結(jié)構(gòu)：2.1線性表的概念

一線性表的邏輯結(jié)構(gòu)在線性表中，除第一個元素和最后一個元素之外，其他元素都有且僅有一個直接前趨，有且僅有一個直接后繼。2.1線性表的概念

a1

a2ai-1

aiai+1

an2.1線性表的概念

一線性表的邏輯結(jié)構(gòu)2.1線線性表的基本操作1初始化操作InitList(&L)2銷毀操作DetroyList(&L)3置空操作ClearList(&L)4判空操作ListEmpty(L)5求表長操作ListLength(L)6取元素操作：GetElem(L,i,&e)7查找操作LocateElem(L,e,compare())8插入操作ListInsert(&L,i,e)9刪除操作ListDelete(&L,i,&e)10遍歷操作ListTraverse(&L,visit())2.1線性表的概念線性表的基本操作2.1線性表的概念

2.2線性表的順序存儲和實現(xiàn)一線性表的順序存儲結(jié)構(gòu)——順序表1順序表用一組連續(xù)的內(nèi)存單元依次存放線性表的數(shù)據(jù)元素。2順序表的類型定義

typedefstruct{

ElemType*elem;//線性表存儲空間基址

intlength;//當(dāng)前線性表長度

intlistsize;//當(dāng)前分配的存儲空間大小}SqList;2.2線性表的順序存儲和實現(xiàn)一線性表的順序順序表圖示設(shè)A=（a1,a2,a3,...an）是一線性表，L是SqList類型的結(jié)構(gòu)變量，用于存放A2.2線性表的順序存儲和實現(xiàn)L.elemL.lenghtL.listsizen99a1a2ai-1aiai+1an01i-2i-1in-199

順序表保存了哪些信息?順序表圖示設(shè)A=（a1,a2,a3,...an2.2線性表的順序存儲和實現(xiàn)

順序表保存了哪些信息？*線性表中的數(shù)據(jù)元素；

*線性表中數(shù)據(jù)元素的順序關(guān)系；*表中元素個數(shù)（簡化算法）*當(dāng)前分配的存儲空間

順序表如何保存這些信息？

3順序表存儲特點元素存儲在一組連續(xù)的內(nèi)存單元中；通過元素存儲順序元素之的邏輯順序；2.2線性表的順序存儲和實現(xiàn)順序表保存了哪些信息？二順序表的基本操作算法

1初始化算法InitList_Sq(SqList&L)2插入操作算法

ListInsert_Sq(SqList&L,inti,ElemTypee)3刪除操作算法

ListDelete_Sq(SqList&L,inti,ElemType&e)2.2線性表的順序存儲和實現(xiàn)二順序表的基本操作算法

1初始化算法2.2線性表2.2線性表的順序存儲和實現(xiàn)5順序表主要操作特點1）可隨機(jī)存取順序表的元素(用L.e