常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1

1、會(huì)計(jì)學(xué)1常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1第1頁/共170頁2022-6-2122.1 概述概述2.1.1 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu) 程序程序=數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)+算法算法數(shù)據(jù)結(jié)構(gòu)示例數(shù)據(jù)結(jié)構(gòu)示例 學(xué)號(hào) 姓名 性別 籍貫 電 話 通 訊 地 址 01 張三 男 長(zhǎng)沙 8639000 麓山南路 327 號(hào) 02 李四 男 北京 23456789 學(xué)院路 435 號(hào) 03 王五 女 廣州 30472589 天河路 478 號(hào) 04 趙六 男 上海 41237568 南京路 1563 號(hào) 05 錢七 女 南京 5013472 南京大學(xué) 06 劉八 女 武漢 61543726 武漢大學(xué) 07

2、 朱九 男 昆明 4089651 云南大學(xué) 08 孫十 女 杭州 6154372 西湖路 635 號(hào) 圖 1-1 學(xué)生數(shù)據(jù)表 1.線性表示例線性表示例第2頁/共170頁2022-6-2132.樹形結(jié)構(gòu)示例樹形結(jié)構(gòu)示例 a1 a b c b1 a2 Tt b2 c1 c2 d d1 d2 d3 圖 1-2 樹形結(jié)構(gòu)示意圖 一層二層三層四層第3頁/共170頁2022-6-2143.圖形結(jié)構(gòu)示例圖形結(jié)構(gòu)示例 1 2 3 4 5 6 圖 1-3 圖形結(jié)構(gòu)示意圖 第4頁/共170頁2022-6-215第5頁/共170頁2022-6-2162.1.2 基本術(shù)語基本術(shù)語1 數(shù)據(jù)（數(shù)據(jù)（data）數(shù)據(jù)是信息的

3、載體,它可以用計(jì)算機(jī)表示并加工。例如：數(shù)字、字母、漢字、圖形、圖像、聲音都稱為數(shù)據(jù)。 第6頁/共170頁2022-6-217第7頁/共170頁2022-6-2183 數(shù)據(jù)對(duì)象（數(shù)據(jù)對(duì)象（data object）是性質(zhì)相同的數(shù)據(jù)元素組成的集合，是數(shù)據(jù)的一個(gè)子集。例如，整數(shù)數(shù)據(jù)對(duì)象是集合N0，1，2.，字母字符數(shù)據(jù)對(duì)象是集合C=A,B,Z。第8頁/共170頁2022-6-219第9頁/共170頁2022-6-2110第10頁/共170頁2022-6-2111第11頁/共170頁2022-6-2112a. 集合結(jié)構(gòu)(set)：數(shù)據(jù)元素的有限集合。數(shù)據(jù)元素之間除了“屬于同一個(gè)集合”的關(guān)系之外沒有其他關(guān)

4、系。元素順序是隨意的。 b. 線性結(jié)構(gòu)(linear) ：數(shù)據(jù)元素的有序集合。數(shù)據(jù)元素之間形成一對(duì)一的關(guān)系。c. 樹形結(jié)構(gòu)(tree)：樹是層次數(shù)據(jù)結(jié)構(gòu)，樹中數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。d. 圖結(jié)構(gòu)(graph)：圖中數(shù)據(jù)元素之間的關(guān)系是多對(duì)多的。從邏輯結(jié)構(gòu)劃分?jǐn)?shù)據(jù)結(jié)構(gòu)從邏輯結(jié)構(gòu)劃分?jǐn)?shù)據(jù)結(jié)構(gòu)第12頁/共170頁2022-6-2113圖12 四種基本結(jié)構(gòu)示意圖 (a) 集合結(jié)構(gòu)； (b) 線性結(jié)構(gòu)； (c) 樹形結(jié)構(gòu)； (d) 圖結(jié)構(gòu)(a)(b)(c)(d)第13頁/共170頁2022-6-2114 上述四種基本的結(jié)構(gòu)關(guān)系可分為兩類：線性結(jié)構(gòu)(linear structure)和非線性結(jié)構(gòu)(n

5、on-linear structure)。我們把除了線性結(jié)構(gòu)以外的幾種結(jié)構(gòu)關(guān)系樹、圖和集合歸入非線性結(jié)構(gòu)一類。第14頁/共170頁2022-6-2115第15頁/共170頁2022-6-2116第16頁/共170頁2022-6-2117第17頁/共170頁2022-6-21181.基本概念基本概念算法（算法（algorithm）算法是解決某一特定類型問題的有限運(yùn)算序列。它必須滿足下述條件（也稱為算法的五大特性）：1）有窮性有窮性 一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。且每一步都在有窮時(shí)間內(nèi)完成。2）確定性確定性 算法中每一條指令

6、必須有確切的含義。不存算法中每一條指令必須有確切的含義。不存在二義性。且算法只有一個(gè)入口和一個(gè)出口。在二義性。且算法只有一個(gè)入口和一個(gè)出口。3）可行性可行性 一個(gè)算法是可行的。即算法描述的操作都是一個(gè)算法是可行的。即算法描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的?？梢酝ㄟ^已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的。4）輸入輸入 一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定的對(duì)象集合。某個(gè)特定的對(duì)象集合。5）輸出輸出 一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是同輸一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是同輸入有著某些特定關(guān)系的量入有著某些特定關(guān)系的量。

7、第18頁/共170頁2022-6-2119算法和程序的關(guān)系算法和程序的關(guān)系算法的含義與程序十分相似，但二者是有區(qū)別的。一個(gè)程序不一定滿足有窮性（死循環(huán)），另外，程序中的指令必須是機(jī)器可執(zhí)行的，而算法中的指令則無此限制。一個(gè)算法若用計(jì)算機(jī)語言來書寫，則它就可以是一個(gè)程序。第19頁/共170頁2022-6-2120用流程圖描述算法用流程圖描述算法一個(gè)算法可以用流程圖的方式來描述，輸入輸出、判斷、處理分別用不同的框圖表示，用箭頭表示流程的流向。這是一種描述算法的較好方法，目前在一些高級(jí)語言程序設(shè)計(jì)中仍然采用。用自然語言描述算法用自然語言描述算法用我們?nèi)粘Ｉ钪械淖匀徽Z言（可以是中文形式，也可以是英文

8、形式）也可以描述算法。 第20頁/共170頁2022-6-2121用其它方式描述算法用其它方式描述算法我們還可以用數(shù)學(xué)語言或約定的符號(hào)語言來描述算法。用用C語言描述算法語言描述算法第21頁/共170頁2022-6-2122第22頁/共170頁2022-6-2123第23頁/共170頁2022-6-2124第24頁/共170頁2022-6-2125第25頁/共170頁2022-6-2126第26頁/共170頁2022-6-2127第27頁/共170頁2022-6-2128第28頁/共170頁2022-6-2129第29頁/共170頁2022-6-2130練習(xí)1.是數(shù)據(jù)的基本單位，.是具有獨(dú)立含義

9、的最小標(biāo)識(shí)單位。2.什么是數(shù)據(jù)結(jié)構(gòu)?3.數(shù)據(jù)的.與數(shù)據(jù)的存儲(chǔ)無關(guān)，它是獨(dú)立于計(jì)算機(jī)的。4.通常數(shù)據(jù)結(jié)構(gòu)分為.、 .、 .、 .四類。5.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、.、.第30頁/共170頁2022-6-2131下面給出幾個(gè)線性表的例子：例例2-1 26個(gè)大寫的英文字母表：(A，B，C，.，Z) 例例2-2 某校從1996年到2002年各種型號(hào)計(jì)算機(jī)擁有量的變化情況，可以用線性表給出： (200，220，250，300，400，700，1200)2.2 線線 性性 表表 一、 線性表的定義和運(yùn)算1.定義第31頁/共170頁2022-6-2132n 數(shù)據(jù)元素的個(gè)數(shù)數(shù)據(jù)元素的個(gè)數(shù)

10、 表的長(zhǎng)度表的長(zhǎng)度n = 0 空表空表n0 非空表非空表 第32頁/共170頁2022-6-2133線性表的結(jié)構(gòu)僅涉及諸元素的相對(duì)位置，即第i個(gè)元素ai處在第i-1個(gè)元素ai-1的后面和第i+1個(gè)元素ai+1的前面，這種位置上的有序性就是一種線性關(guān)系，所以線性表是一種線性結(jié)構(gòu)。線性表中每個(gè)數(shù)據(jù)元素?cái)?shù)據(jù)元素ai的具體含義的具體含義，在不同情況下各不相同，它可以是一個(gè)數(shù)，或是一個(gè)符號(hào)，或者一個(gè)記錄，甚至是其它更復(fù)雜的信息。但在同一個(gè)線性表中的數(shù)據(jù)元素必須具有相同的特性(或者說具有相同的類型)。若線性表中的數(shù)據(jù)元素相互之間可比較,且 則該線性表稱為有序表否則稱為無序表。,.,3 , 2,1niaai

11、i 第33頁/共170頁2022-6-2134第34頁/共170頁2022-6-2135線性表是一種典型的線性結(jié)構(gòu)，用二元組表示為 L=（D，R）其中：D=a1，a2, ., an2 ,|,11niDaaaaRiiii對(duì)應(yīng)的邏輯結(jié)構(gòu)圖如圖2-1所示。 a1 a2 an 圖 2-1 線性表邏輯結(jié)構(gòu)示意圖 第35頁/共170頁2022-6-21362、線性表的運(yùn)算、線性表的運(yùn)算常見線性表的運(yùn)算有：1) 置空表 SETNULL（&L）將線性表L置成空表2) 求長(zhǎng)度 LENGTH（L） 求給定線性表L的長(zhǎng)度3) 取元素 GET（L，i） 若1ilength(L),則取第i個(gè)位置上的元素，否則取得的元素

12、為NULL。 4) 求直接前趨 PRIOR（L，X）求線性表L中元素值為X的直接前趨，若X為第一個(gè)元素，前驅(qū)為NULL。第36頁/共170頁2022-6-21375) 求直接后繼 NEXT（L，X）求線性表L中元素值為X直接后繼，若X為最后一個(gè)元素，后繼為NULL。6) 定位函數(shù) LOCATE（L，X） 在線性表L中查找值為X的元素位置，若有多個(gè)值為X，則以第一個(gè)為準(zhǔn)，若沒有，位置為0。7) 插入 INSERT（&L，X，i）在線性表L中第i個(gè)位置上插入值為X的元素。8) 刪除 DELETE（&L，i） 刪除線性表L中第i個(gè)位置上的元素。線性表的運(yùn)算線性表的運(yùn)算第37頁/共170頁2022-6

13、-2138例2-1 假設(shè)線性表L=(23,56,89,76,18),i=3,x=56,y=88,則對(duì)L的一組操作及結(jié)果如下：Length(L); /所得結(jié)果為5Get(L,i) /所得結(jié)果為89Prior(L,x) /所得結(jié)果為23Next(L,x) /所得結(jié)果為89Locate(L,x) /所得結(jié)果為2Insert(&L,y,i) /所得結(jié)果為(23,56,88,89,76,18)Delete(&L,i+1) /所得結(jié)果為(23,56,88,76,18)第38頁/共170頁2022-6-2139二、二、 順序存儲(chǔ)線性表順序存儲(chǔ)線性表1.順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu),也稱為順序

14、表。其存儲(chǔ)方式為：在內(nèi)存中開辟一片連續(xù)存儲(chǔ)空間，但該連續(xù)存儲(chǔ)空間的大小要大于或等于順序表的長(zhǎng)度，然后讓線性表中第一個(gè)元素存放在連續(xù)存儲(chǔ)空間第一個(gè)位置，第二個(gè)元素緊跟著第一個(gè)之后，其余依此類推。第39頁/共170頁2022-6-2140圖2-2 線性表順序存儲(chǔ)結(jié)構(gòu)示意圖(設(shè)每個(gè)數(shù)據(jù)元素占有1個(gè)存儲(chǔ)單元) a1a2aian內(nèi) 存 狀 態(tài)存 儲(chǔ) 地 址元 素 序 號(hào)12in空 閑bb 1b (maxlen 1)b ( i 1)b ( n 1)第40頁/共170頁2022-6-2141第41頁/共170頁2022-6-2142第42頁/共170頁2022-6-21432.順序存儲(chǔ)結(jié)構(gòu)的插入、刪除運(yùn)算順

15、序存儲(chǔ)結(jié)構(gòu)的插入、刪除運(yùn)算第43頁/共170頁2022-6-2144結(jié)構(gòu)結(jié)構(gòu) 結(jié)構(gòu)(structure)是C語言提供的聚合數(shù)據(jù)的機(jī)制。使用結(jié)構(gòu)可以將不同類型的數(shù)據(jù)組合成一個(gè)整體，便于使用。 一個(gè)結(jié)構(gòu)(在許多其他程序設(shè)計(jì)語言中稱為記錄record)是數(shù)據(jù)項(xiàng)的聚集(collection)。每個(gè)數(shù)據(jù)項(xiàng)有名稱和類型，它們可以是不同的數(shù)據(jù)類型。補(bǔ)充內(nèi)容補(bǔ)充內(nèi)容第44頁/共170頁2022-6-2145例如：struct student char name20; char sex; int age; 第45頁/共170頁2022-6-2146 該語句定義了一個(gè)結(jié)構(gòu)類型 struct student，可以使

16、用它作為定義結(jié)構(gòu)變量的類型，如 struct student studA;，這里，變量studA是一個(gè)結(jié)構(gòu)?？梢允褂贸蓡T運(yùn)算符“.”對(duì)結(jié)構(gòu)變量的成員賦值。如，strcpy(studA.name, Wang); /*字符串賦值函數(shù)*/studA.age=19; studA.sex=M; 對(duì)成員變量可以像對(duì)普通變量一樣進(jìn)行其類型所允許的各種運(yùn)算。 ANSI C允許將一個(gè)結(jié)構(gòu)變量整體賦值給另一個(gè)具有相同結(jié)構(gòu)的結(jié)構(gòu)變量，但不能將一個(gè)結(jié)構(gòu)變量作為一個(gè)整體進(jìn)行輸入和輸出，也不能直接判定兩個(gè)結(jié)構(gòu)是否相同。第46頁/共170頁2022-6-2147 為了能像使用C語言類型int一樣使用一個(gè)結(jié)構(gòu)類型，我們可以用

17、typedef創(chuàng)建自己的結(jié)構(gòu)類型Student如下：typedef struct student char name20; char sex; int age; Student； 這里，student是結(jié)構(gòu)名，Student是結(jié)構(gòu)類型名，我們可以像使用類型int一樣用Student定義結(jié)構(gòu)變量。定義變量的語句為Student studA; ，無須加保留字struct。事實(shí)上，結(jié)構(gòu)名稱與結(jié)構(gòu)類型的名稱可以相同。第47頁/共170頁2022-6-2148第48頁/共170頁2022-6-2149求線性表的長(zhǎng)度求線性表的長(zhǎng)度length(L) #define maxlen 100typedef st

18、ruct int elemmaxlen; int last; sqlisttp;int length(sqlisttp L) return L. last; 該算法的語句頻度為1，時(shí)間復(fù)雜度為O(1)。第49頁/共170頁2022-6-2150（1）插入第50頁/共170頁2022-6-2151.a2a1an.ai+1ai01i-1in-1在線性表的第在線性表的第i i個(gè)元素之前插入一個(gè)新的元素，先移動(dòng)，后插入。個(gè)元素之前插入一個(gè)新的元素，先移動(dòng)，后插入。ai-1.a2a1alast ai+1ai x ai-1. a2 a1 ai ai+1 alast alast ai+1 ai x第51頁/

19、共170頁2022-6-2152#define maxlen 100typedef struct int elemmaxlen; int last; sqlisttp;第52頁/共170頁2022-6-2153nv.elemk+1 = v.elemk;nv.elemi-1 = x;nv.last+;n n第53頁/共170頁2022-6-2154（2）刪除第54頁/共170頁2022-6-2155.a2a1an.ai+1ai01i-1in-1刪除線性表的第刪除線性表的第i i個(gè)元素，后面所有元素前移。個(gè)元素，后面所有元素前移。ai-1.a2a1alastai+1ai ai-1. a2 a1 a

20、i ai+1 alast刪除刪除結(jié)點(diǎn)結(jié)點(diǎn)a ai i ai+1 alast第55頁/共170頁2022-6-2156第56頁/共170頁2022-6-21572n1)i(n1n11n1i(3)運(yùn)算的時(shí)間分析第57頁/共170頁2022-6-215821ni)(nn1n1i第58頁/共170頁2022-6-2159第59頁/共170頁2022-6-2160第60頁/共170頁2022-6-2161datadatanextnext NODE； 數(shù)據(jù)元素的結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)如下：第61頁/共170頁2022-6-2162補(bǔ)充內(nèi)容補(bǔ)充內(nèi)容指針指針 C語言中，指針(pointer)也稱為鏈(link)或引

21、用(reference)。C語言使用下列語句定義一個(gè)整型變量i 和一個(gè)指向整型變量的指針變量pi： int i, *pi; 第62頁/共170頁2022-6-2163 事實(shí)上，對(duì)任意類型T，都可定義指向該類型的指針類型。指針類型變量的值是一個(gè)存儲(chǔ)地址。C語言中有兩個(gè)十分重要的與指針類型相關(guān)的運(yùn)算符：取地址運(yùn)算符(address operator)& 和間接引用運(yùn)算符(dereferencing operator) *。間接引用運(yùn)算符用來對(duì)指針變量所指示的變量進(jìn)行操作。第63頁/共170頁2022-6-2164看下面的程序段： int i, *pi; /* 定義整型變量 i 和指向整型的指針變量

22、pi */ pi=&i; /* 將變量i 的地址賦給指針(變量)pi */ i=5; /* 對(duì)變量i 賦整數(shù)值5 */ printf(%d ，i); /* 輸出 i 的值 5 和逗號(hào) */ *pi=10; /* 對(duì)指針pi所指示的存儲(chǔ)位置(變量i)賦值10 */ printf(%d ，*pi); /* 輸出 i 的當(dāng)前值 10 */運(yùn)行上面的程序段將顯示：5，10。第64頁/共170頁2022-6-2165 C語言有一個(gè)特殊的指針值NULL，它不指向任何數(shù)據(jù)對(duì)象和函數(shù)。一般地，NULL由整數(shù)0表示。上述程序段的執(zhí)行過程可以對(duì)照?qǐng)D22來理解。應(yīng)注意的是：指針變量pi的值是整型變量i的地址，這里假

23、定分配給變量i的地址是254。 第65頁/共170頁2022-6-2166圖 22 指針定義和運(yùn)算254piipi&i;2545piii5;25410piipi10;pi&i254inti, *pi;*第66頁/共170頁2022-6-2167 指向結(jié)構(gòu)的指針 前面介紹了結(jié)構(gòu)和結(jié)構(gòu)類型。一個(gè)結(jié)構(gòu)的成員可以是多種類型的，也可以是指針類型的。這個(gè)指針可以指向其他結(jié)構(gòu)類型，也可以指向它所在的結(jié)構(gòu)類型。例如， struct node int Data;struct node *Link; ; Link是結(jié)構(gòu)的成員名，它是指向struct node類型的指針。當(dāng)一個(gè)結(jié)構(gòu)中有一個(gè)或多個(gè)成員是指向它自身的指

24、針時(shí)，稱這種結(jié)構(gòu)為自引用結(jié)構(gòu)。第67頁/共170頁2022-6-2168 定義一個(gè)指向結(jié)構(gòu)的指針可以使用定義語句：struct node *p;。使用typedef定義指向結(jié)構(gòu)的指針類型的方法更靈活。例如： typedef struct node *Nodeptr; typedef struct node int Data;Nodeptr *Link; Node; 這里，我們定義了一個(gè)結(jié)構(gòu)類型Node（node為結(jié)構(gòu)名稱），以及指向該結(jié)構(gòu)類型的指針類型Nodeptr。第68頁/共170頁2022-6-2169datadatanextnext NODE； 數(shù)據(jù)元素的結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)如下：第69頁

25、/共170頁2022-6-2170n個(gè)結(jié)點(diǎn)鏈接成一個(gè)鏈表，即為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。由于每個(gè)結(jié)點(diǎn)中只有一個(gè)一個(gè)指針域，故稱此鏈表為線性鏈表線性鏈表或或單鏈表單鏈表。第70頁/共170頁2022-6-2171第71頁/共170頁2022-6-2172圖2-4 線性鏈表的邏輯狀態(tài)邏輯狀態(tài)示意圖圖2-3 線性鏈表的物理狀態(tài)物理狀態(tài)示意圖 第72頁/共170頁2022-6-2173第73頁/共170頁2022-6-2174圖2-5 帶頭結(jié)點(diǎn)的單鏈表 第74頁/共170頁2022-6-2175第75頁/共170頁2022-6-2176第76頁/共170頁2022-6-2177第77頁/共170頁2022

26、-6-2178第78頁/共170頁2022-6-2179struct nodeint data;struct node *next; ;typedef struct node NODE;第79頁/共170頁2022-6-2180n return p; /* 找到,1=inext = null ) return 0;/鏈表為空，返回0 else while(p-next) p = p-next; j+; return j; /返回鏈表的長(zhǎng)度while(p-next) p=p-next; j+;return j;第83頁/共170頁2022-6-2184第84頁/共170頁2022-6-2185圖

27、2-6 帶頭結(jié)點(diǎn)單鏈表的邏輯狀態(tài)a1ai1headanai第85頁/共170頁2022-6-2186第86頁/共170頁2022-6-2187圖2-7 在單鏈表中插入結(jié)點(diǎn)S 第87頁/共170頁2022-6-2188i-1n s - d a t a = x ; /* */n s - n e x t = p - n e x t ; /* */n p - n e x t = s ; /* */nn第88頁/共170頁2022-6-2189第89頁/共170頁2022-6-2190第90頁/共170頁2022-6-2191圖2-8 帶頭結(jié)點(diǎn)的單鏈表a1ai1headanaiai1p圖2-9 在單鏈表

28、中刪除一個(gè)結(jié)點(diǎn)第91頁/共170頁2022-6-2192n第92頁/共170頁2022-6-2193第93頁/共170頁2022-6-2194第94頁/共170頁2022-6-2195圖2-10 循環(huán)單鏈表第95頁/共170頁2022-6-2196第96頁/共170頁2022-6-2197第97頁/共170頁2022-6-2198圖2-11 雙向鏈表結(jié)點(diǎn)結(jié)構(gòu)第98頁/共170頁2022-6-2199圖2-12 帶頭結(jié)點(diǎn)的空雙向鏈表 head 和循環(huán)單鏈表類似，也可將雙向鏈表的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來組成雙向循環(huán)鏈表。 雙向鏈表的幾種不同狀態(tài)如圖2-12，圖2-13，圖2-14和圖2-15所示。h

29、eada1a2an圖2-13 帶頭結(jié)點(diǎn)的非空雙向鏈表 第99頁/共170頁2022-6-21100圖2-14 空的雙向循環(huán)鏈表 headheada1a2an圖2-15 非空雙向循環(huán)鏈表第100頁/共170頁2022-6-21101第101頁/共170頁2022-6-21102第102頁/共170頁2022-6-21103第103頁/共170頁2022-6-21104第104頁/共170頁2022-6-21105第105頁/共170頁2022-6-21106第106頁/共170頁2022-6-21107第107頁/共170頁2022-6-21108第108頁/共170頁2022-6-21109圖

30、2-19 棧頂指示器和棧中元素之間的關(guān)系 第109頁/共170頁2022-6-21110第110頁/共170頁2022-6-21111第111頁/共170頁2022-6-21112第112頁/共170頁2022-6-21113第113頁/共170頁2022-6-21114第114頁/共170頁2022-6-21115 其中top為棧頂指針，指示棧頂元素位置，若top=Null，則表示空棧。鏈棧一般不會(huì)出現(xiàn)“上溢”，除非內(nèi)存中已不存在可用空間。 下面給出鏈棧的定義，鏈棧的出、入棧操作類似于單鏈表，下面給出相應(yīng)的算法。第115頁/共170頁2022-6-21116 SNODE ；第116頁/共17

31、0頁2022-6-21117第117頁/共170頁2022-6-21118topdatalink棧頂棧底第118頁/共170頁2022-6-21119第119頁/共170頁2022-6-21120topdata link棧頂棧底第120頁/共170頁2022-6-21121第121頁/共170頁2022-6-21122圖2-22 隊(duì)列的示意圖第122頁/共170頁2022-6-21123第123頁/共170頁2022-6-21124第124頁/共170頁2022-6-21125第125頁/共170頁2022-6-21126圖2-23 順序隊(duì)列中頭、尾指針變化(設(shè)MAXSIZE=m=6 )012

32、34m-1=5rearfront(a)空隊(duì)列DCBArearfront(b)A,B,C,D 相繼入隊(duì)rearfront(c)A,B,C,D 相繼出隊(duì)FErearfront(d)E,F 入隊(duì)-1第126頁/共170頁2022-6-21127第127頁/共170頁2022-6-21128第128頁/共170頁2022-6-21129圖2-24 循環(huán)隊(duì)列示意圖第129頁/共170頁2022-6-21130第130頁/共170頁2022-6-21131第131頁/共170頁2022-6-21132第132頁/共170頁2022-6-21133第133頁/共170頁2022-6-21134第134頁/共

33、170頁2022-6-21135第135頁/共170頁2022-6-21136圖2-25 鏈隊(duì)列示意圖 鏈隊(duì)列的邏輯狀態(tài)如圖2-25所示。第136頁/共170頁2022-6-21137第137頁/共170頁2022-6-21138第138頁/共170頁2022-6-21139第139頁/共170頁2022-6-21140第140頁/共170頁2022-6-21141第141頁/共170頁2022-6-21142第142頁/共170頁2022-6-21143第143頁/共170頁2022-6-21144A =a11 a12 . a1n a21 a22 . a2n am1 am2 . amn 如下

34、所示，就是一個(gè)m行n列的二維數(shù)組(也稱為矩陣)，記作Am, n。第144頁/共170頁2022-6-21145第145頁/共170頁2022-6-21146第146頁/共170頁2022-6-21147第147頁/共170頁2022-6-21148第148頁/共170頁2022-6-21149第149頁/共170頁2022-6-21150第150頁/共170頁2022-6-21151圖2-31 二維數(shù)組的兩種存儲(chǔ)方式第151頁/共170頁2022-6-21152第152頁/共170頁2022-6-21153第153頁/共170頁2022-6-21154第154頁/共170頁2022-6-21155第155頁/共170頁2022-6-21156A=a11 0 0 a21 a22 0 an1 an2 ann 在下三角矩陣中，對(duì)角線以上元素全部為0，我們只需存儲(chǔ)下三角的元素。第156頁/共170頁2022-6-21157 假設(shè)以一維數(shù)組S