數(shù)據(jù)結(jié)構(gòu)課件完整版

2023/5/14數(shù)據(jù)結(jié)構(gòu)1數(shù)據(jù)結(jié)構(gòu)

2023/5/14數(shù)據(jù)結(jié)構(gòu)2講課安排：串講全書內(nèi)容典型習(xí)題分析前年、去年考題分析

2023/5/14數(shù)據(jù)結(jié)構(gòu)3第一章概論數(shù)據(jù)結(jié)構(gòu)及其概念

如何評(píng)價(jià)一個(gè)算法2023/5/14數(shù)據(jù)結(jié)構(gòu)4第一章概論1.1數(shù)據(jù)結(jié)構(gòu)的概念一、術(shù)語1.數(shù)據(jù)(Data):

是信息的載體，能被計(jì)算機(jī)識(shí)別、存儲(chǔ)、加工處理。2.數(shù)據(jù)元素(DataElement):

數(shù)據(jù)的基本單位,即數(shù)據(jù)集合中的一個(gè)個(gè)體。也稱元素、

結(jié)點(diǎn)、頂點(diǎn)、記錄數(shù)據(jù)項(xiàng):是具有獨(dú)立含義的最小標(biāo)識(shí)單位關(guān)鍵字（key)：唯一能識(shí)別一個(gè)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)。數(shù)據(jù)元素由數(shù)據(jù)項(xiàng)(dataitem)組成2023/5/14數(shù)據(jù)結(jié)構(gòu)5

3、數(shù)據(jù)類型(DataType):

是具有相同性質(zhì)的計(jì)算機(jī)數(shù)據(jù)的集合及在這個(gè)集合上的一組操作。原子數(shù)據(jù)類型(atomicdatatype)結(jié)構(gòu)數(shù)據(jù)類型(aggregatedatatype)4、數(shù)據(jù)結(jié)構(gòu)

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

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)的運(yùn)算：既對(duì)數(shù)據(jù)施加的操作2023/5/14數(shù)據(jù)結(jié)構(gòu)6邏輯結(jié)構(gòu)：(有時(shí)直接稱為數(shù)據(jù)結(jié)構(gòu)）線性結(jié)構(gòu)：線性表、棧、隊(duì)列、串(最多只有一個(gè)直接前趨和一個(gè)直接后繼)非線性結(jié)構(gòu)：樹、圖、多維數(shù)組、廣義表說明：1、邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容無關(guān)2、邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對(duì)位置無關(guān)3、邏輯結(jié)構(gòu)與所含結(jié)點(diǎn)個(gè)數(shù)無關(guān)2023/5/14數(shù)據(jù)結(jié)構(gòu)7存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)方法：數(shù)據(jù)元素在內(nèi)存中按序連續(xù)存儲(chǔ)，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)鏈接存儲(chǔ)方法：用指針指出其直接后繼結(jié)點(diǎn)的存儲(chǔ)位置，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)索引存儲(chǔ)方法：數(shù)據(jù)元素連續(xù)存放，再設(shè)一個(gè)索引表（有序），索引表由索引項(xiàng)組成，每個(gè)索引項(xiàng)由關(guān)鍵字和地址構(gòu)成分為稠密索引和稀疏索引散列存儲(chǔ)方法：確定散列函數(shù)后，根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。2023/5/14數(shù)據(jù)結(jié)構(gòu)8關(guān)系：邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，與存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。邏輯結(jié)構(gòu)是從具體問題抽象出來的數(shù)學(xué)模型存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn)（亦稱映象）數(shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的一個(gè)運(yùn)算的集合運(yùn)算的實(shí)現(xiàn)與存儲(chǔ)結(jié)構(gòu)密切相關(guān)邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是多對(duì)多的關(guān)系2023/5/14數(shù)據(jù)結(jié)構(gòu)9例：一個(gè)學(xué)生成績表：是一個(gè)數(shù)據(jù)結(jié)構(gòu)每行是一個(gè)結(jié)點(diǎn)（或記錄），由學(xué)號(hào)、姓名、各科成績及平均成績等數(shù)據(jù)項(xiàng)組成。邏輯關(guān)系：線性結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)：表的運(yùn)算：2023/5/14數(shù)據(jù)結(jié)構(gòu)10

邏輯結(jié)構(gòu)上定義的基本運(yùn)算在存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)是通過算法來描述的。一、算法定義

算法是對(duì)特定問題求解步驟的一種描述，由有限的指令序列構(gòu)成，其中每一條指令表示一個(gè)或多個(gè)操作。第一章概論1.3算法描述2023/5/14數(shù)據(jù)結(jié)構(gòu)11

二、算法應(yīng)具有的五個(gè)特性：（1）輸入一個(gè)算法有零個(gè)或多個(gè)的輸入，它們是算法 開始前給出的最初量（2）輸出一個(gè)算法至少有一個(gè)輸出，它們是同輸入

有某種關(guān)系的量（3）有窮性每一條指令的執(zhí)行次數(shù)必須是有限的（4）確定性每一條指令必須有確切的含義，無二義性（5）可行性每條指令的執(zhí)行時(shí)間都是有限的。2023/5/14數(shù)據(jù)結(jié)構(gòu)12第一章概論一、算法評(píng)價(jià)五要素

（1）正確性（2）執(zhí)行算法所耗費(fèi)的時(shí)間（3）執(zhí)行算法所耗費(fèi)的空間（4）可讀性（5）健壯性1.4算法分析2023/5/14數(shù)據(jù)結(jié)構(gòu)13第一章概論二、算法的時(shí)間復(fù)雜度

一個(gè)算法所耗費(fèi)的時(shí)間:該算法中每條語句的執(zhí)行時(shí)間之和。每條語句的執(zhí)行時(shí)間：該語句的執(zhí)行次數(shù)乘以該語句執(zhí)行一次所需時(shí)間。頻度：語句重復(fù)執(zhí)行的次數(shù)算法的時(shí)間耗費(fèi)T(n)=每條語句的執(zhí)行的時(shí)間

=（語句頻度×語句執(zhí)行一次所需時(shí)間）

=語句頻度算法的時(shí)間復(fù)雜度：就是算法的時(shí)間耗費(fèi)T(n)2023/5/14數(shù)據(jù)結(jié)構(gòu)14第一章概論三、（漸進(jìn)）時(shí)間復(fù)雜度(O(f(n))當(dāng)問題的規(guī)模n趨向無窮大時(shí)，時(shí)間復(fù)雜度T(n)的數(shù)量級(jí)（階）稱為算法的漸近時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度四、最壞時(shí)間復(fù)雜度依據(jù)數(shù)據(jù)集中可能出現(xiàn)的最壞情況估算出的時(shí)間復(fù)雜度稱為最壞時(shí)間復(fù)雜度。五、平均時(shí)間復(fù)雜度在假設(shè)數(shù)據(jù)集的分布是等概率的條件下，估算出的時(shí)間復(fù)雜度稱為平均時(shí)間復(fù)雜度。例：順序查找2023/5/14數(shù)據(jù)結(jié)構(gòu)15五、空間復(fù)雜度S(n)：

算法所耗費(fèi)的存儲(chǔ)空間，仍是問題規(guī)模n的函數(shù)。第一章概論2023/5/14數(shù)據(jù)結(jié)構(gòu)16第一章概論本章要求:1、掌握數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)等基本概念。2、掌握數(shù)據(jù)邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的分類。3、學(xué)會(huì)算法分析的基本方法。2023/5/14數(shù)據(jù)結(jié)構(gòu)17第二章線性表本章要學(xué)習(xí)的主要內(nèi)容1、線性表的邏輯結(jié)構(gòu)及基本運(yùn)算2、線性表的順序存儲(chǔ)結(jié)構(gòu)3、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：單鏈表、循環(huán)鏈表、雙鏈表、靜態(tài)鏈表4、順序表和鏈表的比較2023/5/14數(shù)據(jù)結(jié)構(gòu)182.1線性表的概念及運(yùn)算1.描述:

線性表是由n(n>=0)個(gè)數(shù)據(jù)元素(點(diǎn))a1,a2,….,ai,….,an組成的有限序列。其中，數(shù)據(jù)元素的個(gè)數(shù)n定義為表長。當(dāng)n=0時(shí)稱為空表，非空的線性表(n>0)記為：(a1,a2,….,ai,…..,an)一、邏輯結(jié)構(gòu)注意:1.數(shù)據(jù)元素ai是一個(gè)抽象的符號(hào)

2.ai可取各種數(shù)據(jù)類型

3.一般情況下,同一線性表中的元素具有相同的數(shù)據(jù)類型

4.i是元素的序號(hào)(1<=i<=n)2.邏輯特征：僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼2023/5/14數(shù)據(jù)結(jié)構(gòu)19線性表的常見基本運(yùn)算包括：

（1）置空表SETNULL(L)

（2）建表CREATLIST(L)二、線性表的運(yùn)算

（4）取結(jié)點(diǎn)GET(L,i)

（5）定位LOCATE(L,x)

（6）插入INSERT(L,x,i)

（7）刪除DELETE(L,i)

（3）求表長LENGTH(L)復(fù)雜的運(yùn)算可以由這些基本運(yùn)算組合來實(shí)現(xiàn)2023/5/14數(shù)據(jù)結(jié)構(gòu)202.2線性表的順序存儲(chǔ)1、順序存儲(chǔ)：將線性表的結(jié)點(diǎn)按邏輯次序依次存放在一組地址連續(xù)的存儲(chǔ)單元里。3、存儲(chǔ)地址的計(jì)算：

LOC(ai)=LOC(a1)+(i-1)*c1<=i<=n

這里：LOC(a1)為結(jié)點(diǎn)a1的存儲(chǔ)起址(基地址），c為每個(gè)結(jié)點(diǎn)所占存儲(chǔ)單元數(shù)。一、順序表2、順序表：采用順序存儲(chǔ)方法存儲(chǔ)的線性表稱順序表。順序表是一種隨機(jī)存取結(jié)構(gòu)2023/5/14數(shù)據(jù)結(jié)構(gòu)21

typedef

int

datetype;#definemaxsize1024

typedef

struct{datatype

data[maxsize];

intlast;}sequenlist;4、順序表的描述：說明:(1).datatype是表中的數(shù)據(jù)類型,依具體情況而定(2).向量下標(biāo)可以看作表中結(jié)點(diǎn)的相對(duì)地址(3).

順序表的長度為last+1(4).結(jié)點(diǎn)的引用:定義一個(gè)順序表：sequenlist*L;

(*L).data[0]a1(*L).data[1]a2....

(*L).data[(*L).last]ana1a2...anMaxsize-1(*L).last01last2023/5/14數(shù)據(jù)結(jié)構(gòu)22二、順序表上的基本運(yùn)算（實(shí)現(xiàn)）2.2線性表的順序存儲(chǔ)SETNULL（L）： (*L).last=-1LENGTH(L): (*L).last+1GET(L,i): (*L).data[i-1]LOCATE(L,x)INSERT(L,x,i)DELETE(L,i)

2023/5/14數(shù)據(jù)結(jié)構(gòu)23順序表的特點(diǎn)：

用物理位置上的鄰接關(guān)系表示結(jié)點(diǎn)間的邏輯關(guān)系順序表的優(yōu)點(diǎn)：（1）無須增加額外的存儲(chǔ)空間表示結(jié)點(diǎn)間的邏輯關(guān)系。（2）可以方便地隨機(jī)存取表中任一結(jié)點(diǎn)。順序表的缺點(diǎn)：（1）插入和刪除運(yùn)算不方便，通常須移動(dòng)大量結(jié)點(diǎn)，效率較低。（2）難以進(jìn)行連續(xù)的存儲(chǔ)空間的預(yù)分配，尤其是當(dāng)表變化較大時(shí)。2023/5/14數(shù)據(jù)結(jié)構(gòu)242.3線性表的鏈?zhǔn)酱鎯?chǔ)一、鏈表1、鏈?zhǔn)酱鎯?chǔ)：用一組任意的存儲(chǔ)單元存儲(chǔ)線性表,邏輯上相鄰的結(jié)點(diǎn)在物理位置上不一定相鄰，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)結(jié)點(diǎn)時(shí)附加的指針字段表示2、鏈表：采用鏈?zhǔn)酱鎯?chǔ)方法的線性表稱為鏈表。2023/5/14數(shù)據(jù)結(jié)構(gòu)252.3.1單鏈表1、單鏈表的特點(diǎn)：每個(gè)結(jié)點(diǎn)只有一個(gè)鏈域，指向其直接后繼

（尾結(jié)點(diǎn)除外）。4、單鏈表的存儲(chǔ)結(jié)構(gòu)描述如下：

typedef

int

dataype;

typedefstructnode{datatypedata;structnode*next;}linklist;linklist*head,*p;2、結(jié)點(diǎn)結(jié)構(gòu)：datanext3、圖示法表示單鏈表a1a2an.....^head因?yàn)閱捂湵碛深^指針唯一決定2023/5/14數(shù)據(jù)結(jié)構(gòu)26說明：區(qū)分指針變量和結(jié)點(diǎn)變量:p,*p結(jié)點(diǎn)的動(dòng)態(tài)分配和釋放

typedef

int

datatype;

typedefstructnode{datatypedata;structnode*next;}linklist;linklist*head,*p;

申請(qǐng)一個(gè)結(jié)點(diǎn)p=(linklist*)malloc(sizeof(linklist));釋放一個(gè)結(jié)點(diǎn)free(p);2023/5/14數(shù)據(jù)結(jié)構(gòu)272.3.2單鏈表上的基本運(yùn)算（實(shí)現(xiàn)）1.建立單鏈表（1）頭插法建表（2）尾插法建表方法:從一個(gè)空表開始,重復(fù)讀入數(shù)據(jù),生成新結(jié)點(diǎn),將讀入數(shù)據(jù)存放在新結(jié)點(diǎn)的數(shù)據(jù)域,然后將新結(jié)點(diǎn)插入當(dāng)前鏈表中,直到結(jié)束。頭插法建表：將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭ds優(yōu)點(diǎn)：算法簡單缺點(diǎn)：鏈表中結(jié)點(diǎn)次序和輸入次序相反cbaHead^122023/5/14數(shù)據(jù)結(jié)構(gòu)28Linklist*CREATLIST(){charch;linklist*head,*s;head=NULL;ch=getchar();dscbaHead^12while(ch!=‘$’){s=malloc(sizeof(linklist));s->data=ch;

s->next=head;head=s;ch=getchar();}returnhead;}2023/5/14數(shù)據(jù)結(jié)構(gòu)292.3.2單鏈表上的基本運(yùn)算（實(shí)現(xiàn)）尾插法建表：將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾（需引入r）dsrabcHeadr^^不帶頭結(jié)點(diǎn)的尾插法：插入時(shí)，第一個(gè)結(jié)點(diǎn)的處理與其 它結(jié)點(diǎn)的處理有區(qū)別。

結(jié)束時(shí)，空表和非空表的處理有區(qū)別。2023/5/14數(shù)據(jù)結(jié)構(gòu)30Linklist*CREATLISTR(){charch;linklist*head,*s,*r;head=NULL;

r=NULL;

ch=getchar();

while(ch!=‘$’){s=malloc(sizeof(linklist));

s->data=ch;

if(head=NULL)head=s

elser->next=s;

r=s;ch=getchar();}if(r!=NULL)r->next=NULL;returnhead;}2023/5/14數(shù)據(jù)結(jié)構(gòu)312.3.2單鏈表上的基本運(yùn)算（實(shí)現(xiàn)）尾插法建表：將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾（需引入r）dsrabcHeadr^^不帶頭結(jié)點(diǎn)的尾插法：插入時(shí)，第一個(gè)結(jié)點(diǎn)的處理與其 它結(jié)點(diǎn)的處理有區(qū)別。

結(jié)束時(shí)，空表和非空表的處理有區(qū)別。帶頭結(jié)點(diǎn)的尾插法：1）鏈表第一個(gè)位置上的操作與其 它位置上的操作相一致。

2）空表和非空表的處理相一致。2023/5/14數(shù)據(jù)結(jié)構(gòu)322.3.2單鏈表上的基本運(yùn)算（實(shí)現(xiàn)）Linklist*CREATLISTR1(){charch;linklist*head,*s,*r;head=malloc(sizeof(linklist));r=head;ch=getchar();while(ch!=“$”){s=malloc(sizeof(linklist));s->data=ch;r->next=s;

r=s;ch=getchar();}

r->next=NULL;returnhead;}dsrcHeadr^^2023/5/14數(shù)據(jù)結(jié)構(gòu)332.3.2單鏈表上的基本運(yùn)算（實(shí)現(xiàn)）

二、查找運(yùn)算（1）按序號(hào)查找GET（L，i）

給定一個(gè)序號(hào)，在單鏈表中查找該序號(hào)對(duì)應(yīng)的結(jié)點(diǎn)，

若結(jié)點(diǎn)存在，則返回該結(jié)點(diǎn)的指針，否則返回空指針。方法：非隨機(jī)存儲(chǔ)結(jié)構(gòu)的鏈表，決定了上述查找運(yùn)算只能通過掃描單鏈表來完成。設(shè)置一個(gè)計(jì)數(shù)器j一個(gè)p，初始指向頭結(jié)點(diǎn)P向后每移動(dòng)一個(gè)位置j++當(dāng)j=i時(shí)返回2023/5/14數(shù)據(jù)結(jié)構(gòu)34按值查找即在鏈表中查找是否有值等于給定值key的結(jié)點(diǎn)。若有則返回首次找到的其值為key的結(jié)點(diǎn)的指針，否則返回NULL。算法描述如下：

linklist*locate(head,key)

linklist*head;

datatyekey;

{linklist*p;

p=headnext;

在等概率的情況下，該算法的平均時(shí)間復(fù)雜度亦為O(n)（2）按值查找LOCATE（head，key）2.3.2單鏈表上的基本運(yùn)算（實(shí)現(xiàn)）while(p!=NULL)

if(pdata!=key)

p=pnext;

elsebreak;

returnp;

}2023/5/14數(shù)據(jù)結(jié)構(gòu)353.插入運(yùn)算

（1）后插操作:在指針p所指結(jié)點(diǎn)之后插入xs

（2）前插操作:在指針p所指結(jié)點(diǎn)之前插入Headp時(shí)間復(fù)雜度度O(1)xs平均時(shí)間復(fù)雜度O(n)先從頭指針起,順鏈找到*p的前趨結(jié)點(diǎn)*q.Headpq2023/5/14數(shù)據(jù)結(jié)構(gòu)36Headpax3.插入運(yùn)算:將前插操作轉(zhuǎn)變?yōu)楹蟛宀僮鱴sxsaINSERTBEFORE(p,x)linklist*p;datatypex;{linklist*s;s=malloc(sizeof(linklist));s->data=p->data;s->next=p->next;p->data=x;p->next=s;}時(shí)間復(fù)雜度O(1)應(yīng)盡量將單鏈表上的插入操作轉(zhuǎn)化為后插操作！2023/5/14數(shù)據(jù)結(jié)構(gòu)374.刪除運(yùn)算時(shí)間復(fù)雜度O(1)刪除指定結(jié)點(diǎn)的直接后繼Headprr=p->next;p->next=r->next;free(r);刪除指定結(jié)點(diǎn)時(shí)間復(fù)雜度O(n)鏈表的優(yōu)點(diǎn):在鏈表上實(shí)現(xiàn)插入、刪除運(yùn)算無須移動(dòng)結(jié)點(diǎn)，僅須修改指針改進(jìn)?2023/5/14數(shù)據(jù)結(jié)構(gòu)382.單循環(huán)鏈表的特點(diǎn)：鏈表尾結(jié)點(diǎn)的next域不為空，而是指向頭結(jié)點(diǎn)或開始結(jié)點(diǎn)。（優(yōu)點(diǎn)：從任一結(jié)點(diǎn)開始，均可找到其前趨和后繼結(jié)點(diǎn)。）3、引入單循環(huán)鏈表的目的在于方便一些運(yùn)算的實(shí)現(xiàn)。

實(shí)用中常采用尾指針單循環(huán)鏈表,而不是頭指針單循環(huán)鏈表。4、單循環(huán)鏈表上的操作與單鏈表基本一致

差別僅在于：循環(huán)控制條件不是判空，而是判斷是否等于頭指針或尾指針。2.3.3單循環(huán)鏈表1.循環(huán)鏈表:是一種首尾相接的鏈表單循環(huán)鏈表雙循環(huán)鏈表2023/5/14數(shù)據(jù)結(jié)構(gòu)39

1.

雙鏈表的特點(diǎn)：每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，分別指向其直接

前趨和后繼。2.雙鏈表存儲(chǔ)結(jié)構(gòu)描述如下：

typedef

struct

dnode{datatypedata;

struct

dnode*prior,*next;}dlinklist;

dlinklist*head;

對(duì)于雙向鏈表，當(dāng)將頭、尾結(jié)點(diǎn)鏈起來時(shí)，便成了雙向循環(huán)鏈表。2.3.4雙鏈表

priornextdata為了指示雙鏈表，也須引入一個(gè)頭指針head，指向其開始結(jié)點(diǎn)。2023/5/14數(shù)據(jù)結(jié)構(gòu)403.雙向鏈表基本運(yùn)算的實(shí)現(xiàn)：（1）刪除運(yùn)算（2）插入運(yùn)算插入和刪除都非常方便p->prior->next=p=p->next->prior刪除運(yùn)算DELETENODE（p）

/*刪除雙鏈表結(jié)點(diǎn)*p*/dlinklist*p;{p->prior->next=p->next;p->next->prior=p->prior;free(p);}Headp2023/5/14數(shù)據(jù)結(jié)構(gòu)41插入運(yùn)算DINSERTBEFORE(p,x)dlinklist*p;datatypex;{dlinklist*s;Pxss=malloc(sizeof(dlinklist));s->data=x;s->prior=p->prior;s->next=p;p->prior->next=s;p->prior=s;}2023/5/14數(shù)據(jù)結(jié)構(gòu)422.3.5靜態(tài)鏈表

實(shí)現(xiàn)方法

存儲(chǔ)空間

分配和釋放

靜態(tài)鏈表

游

標(biāo)

預(yù)分配的一個(gè)連續(xù)空間

用戶定義

動(dòng)態(tài)鏈表

指

針

內(nèi)存所有可用空間

系統(tǒng)提供

靜態(tài)鏈表與動(dòng)態(tài)鏈表的區(qū)別2023/5/14數(shù)據(jù)結(jié)構(gòu)43

2、靜態(tài)鏈表存儲(chǔ)結(jié)構(gòu)描述如下：

＃definemaxsize1024 typedefintdatatype; typedef

intcursor;typedefstruct{datatypedata;數(shù)據(jù)域

cursornext;游標(biāo)

}node;nodenodepool[maxsize];存儲(chǔ)池

cursorav;游標(biāo)變量

2.3.5靜態(tài)鏈表1、用數(shù)組和“游標(biāo)”實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)的方法是：

事先定義一個(gè)規(guī)模較大的結(jié)構(gòu)數(shù)組作為備用結(jié)點(diǎn)空間（即存儲(chǔ)池），當(dāng)申請(qǐng)結(jié)點(diǎn)空間時(shí)，從存儲(chǔ)池中取出結(jié)點(diǎn)，當(dāng)釋放結(jié)點(diǎn)空間時(shí)，將其歸還于存儲(chǔ)池內(nèi)。采用這種方法實(shí)現(xiàn)的鏈表稱為靜態(tài)鏈表。12Maxsize-13NULL012Maxsize-1av0nodepool[maxsize]2023/5/14數(shù)據(jù)結(jié)構(gòu)44說明:靜態(tài)鏈表也可以用頭指針L唯一指示,L為cursor類型

3、可用空間表:將存儲(chǔ)池中所有空閑結(jié)點(diǎn)鏈成一個(gè)頭指針為av的單鏈表,構(gòu)成一個(gè)可用空間表2023/5/14數(shù)據(jù)結(jié)構(gòu)452.3.5靜態(tài)鏈表12Maxsize-13NULL012Maxsize-1av1nodepool[maxsize]初始化：INITALIZE(){inti;for(i=0;i<maxsize-1,i++)nodepool[i].next=i+1;nodepool[maxsize-1].next=NULL;av=1;}動(dòng)態(tài)鏈表由系統(tǒng)分配和回收結(jié)點(diǎn)空間,靜態(tài)鏈表由程序員編程分配和釋放結(jié)點(diǎn)2023/5/14數(shù)據(jù)結(jié)構(gòu)464、節(jié)點(diǎn)的分配與回收GETNODE():將表av上的第一個(gè)結(jié)點(diǎn)取出，并把該結(jié)點(diǎn)的位置付給pCursorGETNODE(){cursorp;if(av==NULL)p=NULL;else{p=av; av=nodepool[av].next; }returnp;}FREENODE(p)將p所指的結(jié)點(diǎn)插入到表av的頭上。FREENODE(p){nodepool[p].next=av;av=p}2023/5/14數(shù)據(jù)結(jié)構(gòu)475、靜態(tài)鏈表基本運(yùn)算的實(shí)現(xiàn)

:

初始化可用空間表創(chuàng)建靜態(tài)鏈表表尾插入結(jié)點(diǎn)在指定結(jié)點(diǎn)前插入結(jié)點(diǎn)刪除指定結(jié)點(diǎn)查找指定結(jié)點(diǎn)?說明:靜態(tài)鏈表和動(dòng)態(tài)鏈表在邏輯上是一致的,靜態(tài)鏈表和動(dòng)態(tài)鏈表上的運(yùn)算的實(shí)現(xiàn)是一樣的,只要注意游標(biāo)和指針的對(duì)應(yīng)關(guān)系就可以了2023/5/14數(shù)據(jù)結(jié)構(gòu)483.1棧3.1.1棧的概念及運(yùn)算1定義：棧（Stack）是僅在表的一端進(jìn)行插入和刪除運(yùn)

算的線性表

棧頂(top)為進(jìn)行插入和刪除運(yùn)算的一端

棧底(bottom)為另一端2特點(diǎn):

最先入棧的元素總是最后出棧，而最后入棧的元素則總是最先出棧，因此，棧又被稱為后進(jìn)先出(LastInFirstOut)的線性表。棧頂棧底a1a2an退棧進(jìn)?！谌聴：完?duì)列2023/5/14數(shù)據(jù)結(jié)構(gòu)493棧的基本運(yùn)算包括：（1）置空棧SETNULL（S）（2）判?？誆MPTY（S）:布爾函數(shù)（3）入棧PUSH(S，x)（4）出棧POP（S）（5）取棧頂TOP（S）棧頂棧底a1a2an退棧進(jìn)?！?023/5/14數(shù)據(jù)結(jié)構(gòu)503.1.2順序棧1定義：順序棧是采用順序存儲(chǔ)結(jié)構(gòu)的棧，c語言中通過數(shù)組來實(shí)現(xiàn)。棧頂指針top為指示棧頂位置的變量，用數(shù)組元素的下標(biāo)來表示。2順序棧存儲(chǔ)結(jié)構(gòu)描述：

typedefintdatatype;#definemaxsize100;

typedefstruct

{datatypedata[maxsize];

inttop;}seqstack;seqstack*s;2023/5/14數(shù)據(jù)結(jié)構(gòu)513棧頂指針和棧中元素的關(guān)系：seqstacks;4321

0top=-1top=34321

0DCBA4321

0BAtop=1

空棧入棧出棧Sdata[0]toptoptoptypedefstruct

{datatypedata[maxsize];

inttop;}seqstack;seqstack*s;2023/5/14數(shù)據(jù)結(jié)構(gòu)524順序棧上基本運(yùn)算的實(shí)現(xiàn)：1）置?？誷etnull(s)2）判?？読ntempty(s)3）進(jìn)棧

seqstack*push(s,x)4）退棧

datatypepop(s)5）取棧頂

datatypetop(s)

2023/5/14數(shù)據(jù)結(jié)構(gòu)535技巧

為了充分利用向量存儲(chǔ)空間，多個(gè)棧共用一段存儲(chǔ)空間。缺點(diǎn)：使棧運(yùn)算的實(shí)現(xiàn)更復(fù)雜。.........棧1棧2棧1底棧1頂棧2頂棧2底棧1空：top1=-1棧2空:top2=maxsize棧滿:top1+1=top22023/5/14數(shù)據(jù)結(jié)構(gòu)543.1.3鏈棧1定義：采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧稱為鏈棧。

鏈棧實(shí)際上是操作受限的單鏈表，其插入和刪除操

作均在表頭進(jìn)行。2鏈棧的存儲(chǔ)結(jié)構(gòu)描述如下：

typedefintdatatype;typedef

structnode{datatypedata;structnode*next;}

linkstack;linkstack*top;2023/5/14數(shù)據(jù)結(jié)構(gòu)55鏈棧中的結(jié)點(diǎn)動(dòng)態(tài)產(chǎn)生,因而可以不考慮上溢問題棧底^top

datanext棧頂鏈棧示意圖當(dāng)top=NULL時(shí)，鏈棧為空。3鏈棧示意圖2023/5/14數(shù)據(jù)結(jié)構(gòu)564鏈棧上基本運(yùn)算的實(shí)現(xiàn)：

1）

進(jìn)棧

PUSHLSTACK(top,x)

Linkstack*PUSHLSTACK(top,x)linkstack*top;datatypex;{linkstack*p;p=malloc(sizeof(linkstack));

p->data=x;p->next=top;returnp;}2023/5/14數(shù)據(jù)結(jié)構(gòu)57Linkstack*POPLSTACK(top,datap)

linkstack*top;

datatype*datap;{linkstack*p;

if(top==NULL){printf(“underflow”);returnNULL;}

else{*datap=top->data;

p=top;

top=top->next;

free(p);

returntop;

} }

2）

退棧

*POPLSTACK(top,datap)

2023/5/14數(shù)據(jù)結(jié)構(gòu)583.2棧的應(yīng)用舉例1.文字編輯器2.

函數(shù)的遞歸調(diào)用（p47)2023/5/14數(shù)據(jù)結(jié)構(gòu)593.3隊(duì)列1定義：隊(duì)列(queue)

是一端進(jìn)行刪除另一端進(jìn)行插入的線性表。

允許插入的一端稱為隊(duì)尾(rear)

，允許刪除的一端稱為隊(duì)頭(front)。2特點(diǎn)：先入隊(duì)(即插入隊(duì)尾）的元素必將被先刪除(即出隊(duì)）。因此，隊(duì)列是一種先進(jìn)先出(FirstInFirstOut)的線性表。3.3.1隊(duì)列的概念及運(yùn)算出隊(duì)入隊(duì)隊(duì)頭隊(duì)尾a1a2…an2023/5/14數(shù)據(jù)結(jié)構(gòu)603隊(duì)列的基本運(yùn)算：（1）SETNULL（Q）置隊(duì)空（2）EMPTY（Q）判隊(duì)空（3）FRONT（Q）取隊(duì)頭元素,隊(duì)中元素保持不變（4）ENQUEUE（Q,x)將元素x入隊(duì)（5）DEQUEUE（Q）出隊(duì),函數(shù)返回原隊(duì)頭元素2023/5/14數(shù)據(jù)結(jié)構(gòu)613.3.2順序隊(duì)列1定義：采用順序存儲(chǔ)結(jié)構(gòu)的隊(duì)列稱為順序隊(duì)列。

規(guī)定：front總是指向當(dāng)前隊(duì)頭元素的前一個(gè)位置

rear指向當(dāng)前隊(duì)尾元素的位置2順序隊(duì)列存儲(chǔ)結(jié)構(gòu)描述如下：

typedefstruct{datatypedata[maxsize];intfront,rear;}sequeue;sequeue*sq;2023/5/14數(shù)據(jù)結(jié)構(gòu)6243210sq->rear

sq->frontsq->rear43210DCBA43210DC

空隊(duì)列ABCD入隊(duì)AB出棧sq->frontsq->frontsq->rear3順序隊(duì)列指針圖示4順序隊(duì)列基本運(yùn)算初始時(shí)，sqrear=sqfront=-1,在不考慮溢出的情況下，入隊(duì)和出隊(duì)的運(yùn)算如下：

入隊(duì)：sqrear++;sqdata[sqrear]=x;出隊(duì)：sqfront++;2023/5/14數(shù)據(jù)結(jié)構(gòu)63隊(duì)空：

sqrear=sqfront隊(duì)滿：

sqrear－sqfront=maxsize下溢：隊(duì)空時(shí)，若要進(jìn)行出隊(duì)操作時(shí)發(fā)生上溢：隊(duì)滿時(shí)，進(jìn)行入隊(duì)操作時(shí)出現(xiàn)。“假上溢”：當(dāng)sq->rear=maxsize-1但隊(duì)列并不滿

時(shí)進(jìn)行入隊(duì)操作.sqrear=4sqfront=143210edcba這種情況（即sq->rear=maxsize-1)下若要進(jìn)行入隊(duì)運(yùn)算,sqrear的值將超出下標(biāo)范圍，故不能進(jìn)行這種運(yùn)算，但此時(shí)整個(gè)隊(duì)列空間并沒用完。4幾種特殊情況2023/5/14數(shù)據(jù)結(jié)構(gòu)64解決“假上溢”的方法有兩種：

（1）當(dāng)元素出隊(duì)或出現(xiàn)假上溢時(shí)，移動(dòng)隊(duì)列元素。

sqrear=4sqfront=143210edcbaedc43210sqrear=2sqfront=-1移動(dòng)元素后（2）采用循環(huán)隊(duì)列：即sq->data[0]接在sq->data[maxsize-1]之后循環(huán)隊(duì)列的示意圖054321sqrear=0sqfront=42023/5/14數(shù)據(jù)結(jié)構(gòu)65采用循環(huán)隊(duì)列后，進(jìn)行入隊(duì)和出隊(duì)運(yùn)算時(shí)，頭、尾指針加1操作應(yīng)如下進(jìn)行：出隊(duì)：sqfront=(sqfront+1)%maxsize;

入隊(duì)：

sqrear=(sqrear+1)%maxsize;循環(huán)隊(duì)列如何判斷隊(duì)空和隊(duì)滿?

方法一：引入標(biāo)志flag

若(sqfront=sqrear)&&(flag=0),則隊(duì)空,不能出棧。若(sqfront=sqrear)&&(flag=1),則隊(duì)滿,不能入棧。054321sqrear=5sqfront=5054321sqfront=5sqrear=42023/5/14數(shù)據(jù)結(jié)構(gòu)66

方法二：犧牲一個(gè)元素的空間（sq->data[sq->front])，避免隊(duì)滿時(shí)頭、尾指針指向同一位置。

若sqfront=sqrear，則隊(duì)空。若(sqrear+1)%maxsize=sqfront，則隊(duì)滿。054321sqrear=1sqfront=1054321sqfront=5sqrear=42023/5/14數(shù)據(jù)結(jié)構(gòu)673.3.3鏈隊(duì)列1、定義：采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的隊(duì)列稱為鏈隊(duì)列。（是限制在表頭刪除在表尾插入的單鏈表）2、鏈隊(duì)列存儲(chǔ)結(jié)構(gòu)描述

typedef

struct{linklist*front,*rear;}linkqueue;linkqueue*q;

為了運(yùn)算實(shí)現(xiàn)的方便，在隊(duì)頭結(jié)點(diǎn)前引入一個(gè)頭結(jié)點(diǎn)。初始時(shí)（即隊(duì)空）鏈隊(duì)的頭、尾指針均指向頭結(jié)點(diǎn)。

^frontrearq頭結(jié)點(diǎn)qrearfrontrearq頭結(jié)點(diǎn)

^qfront隊(duì)頭結(jié)點(diǎn)q->front=q->rear2023/5/14數(shù)據(jù)結(jié)構(gòu)681）入隊(duì)ENQUEUE（q,x)類似于單鏈表的尾插法2023/5/14數(shù)據(jù)結(jié)構(gòu)692）出隊(duì)qrearfrontrearq頭結(jié)點(diǎn)

^qfront隊(duì)頭結(jié)點(diǎn)*sfrontrearq頭結(jié)點(diǎn)a1*s

^frontrearq頭結(jié)點(diǎn)S=q->front->next;q->front->next=s->next;free(s);隊(duì)列長度等于1時(shí)，不但修改頭結(jié)點(diǎn)的指針域，還需尾指針。隊(duì)列長度大于1時(shí)，只需修改頭結(jié)點(diǎn)的指針域，尾指針不變。2023/5/14數(shù)據(jù)結(jié)構(gòu)70解決方法：出隊(duì)時(shí)只修改頭指針，刪除頭結(jié)點(diǎn)，使鏈隊(duì)列上的隊(duì)頭結(jié)點(diǎn)成為新的鏈表的頭結(jié)點(diǎn)，隊(duì)列上的第2個(gè)結(jié)點(diǎn)成為隊(duì)頭結(jié)點(diǎn)。即物理上刪除頭結(jié)點(diǎn)，邏輯上刪除對(duì)頭結(jié)點(diǎn)。即使當(dāng)前隊(duì)列長度為1，也不用修改尾指針。qrearfrontrearq頭結(jié)點(diǎn)

^隊(duì)頭結(jié)點(diǎn)*s2023/5/14數(shù)據(jù)結(jié)構(gòu)71串(即字符串）是一種特殊的線性表，其每個(gè)結(jié)點(diǎn)僅由一個(gè)字符組成。4.1串及其運(yùn)算4.1.1串的基本概念

1.串(string):是由零個(gè)或多個(gè)字符組成的有限序列。 一般記為S=“a1a2...an”,

其中：S為串名，a1a2…an為串值；ai(1<=i<=n)可

以是字母、數(shù)字和其它字符；

注意：僅含一個(gè)空格的串（“”）和空串（“”）是不同的兩個(gè)串。2.串長度：串中所含的字符個(gè)數(shù)

空串：長度為零的串（不含任何字符，和空格串嚴(yán)格區(qū)分）第四章串2023/5/14數(shù)據(jù)結(jié)構(gòu)724.子串在主串中的序號(hào)：子串在主串中第一次出現(xiàn)時(shí)其第一個(gè)字符在主串中的序號(hào)。S1=“Iamastudent.”S2=“student”S2在S1中的序號(hào)為83.子串：串中任意個(gè)連續(xù)的字符組成的子序列,該串相應(yīng)稱為主串?？沾疄槿我獯淖哟?，任意串為其自身的子串。

兩串相等當(dāng)且僅當(dāng)兩串長度相等且對(duì)應(yīng)位置上的字符相同。5.

在程序中使用的串可分為串常量和串變量S2=“student”將串常量命名為S2

charobject[]=“datastructure”第四章串2023/5/14數(shù)據(jù)結(jié)構(gòu)734.1.2串的基本運(yùn)算

串的基本運(yùn)算有九種，具體如下（p61）（1）賦值：=

（2）聯(lián)接：strcat(ST1,ST2)

（3）求串長：strlen(S)

（4）求子串：substr(S,i,j)

（5）比較串的大?。簊trcmp(S,T)

（6）插入：insert(S1,i,S2)

（7）刪除：delete(S,i,j)

（9）置換：replace(S1,i,j,S2)，repl(S,T,V)2023/5/14數(shù)據(jù)結(jié)構(gòu)744.2串的存儲(chǔ)結(jié)構(gòu)

串可以分別采用順序、鏈?zhǔn)胶退饕鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)存儲(chǔ)。1）用字符數(shù)組描述1、順序存儲(chǔ)

串中的字符被順序地存儲(chǔ)在內(nèi)存中相鄰的存儲(chǔ)單元中。采用順序存儲(chǔ)結(jié)構(gòu)的串稱為順序串。

Howareyou?\０…….串S的順序存儲(chǔ)示意圖S=“Howareyou?”#definemaxsize32chars[maxsize];2023/5/14數(shù)據(jù)結(jié)構(gòu)75

２）

順序串存儲(chǔ)結(jié)構(gòu)描述：

#definemaxsize128; typedefstruct {charch[maxsize]; intcurlen; }seqstring;串字符存儲(chǔ)空間串長度

缺點(diǎn)：順序串上插入、刪除運(yùn)算不方便。2023/5/14數(shù)據(jù)結(jié)構(gòu)762.鏈?zhǔn)酱鎯?chǔ)

采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的串稱為鏈串，鏈串中結(jié)點(diǎn)的數(shù)據(jù)域既可存儲(chǔ)單個(gè)字符，也可存儲(chǔ)多個(gè)字符，結(jié)點(diǎn)數(shù)據(jù)域存儲(chǔ)字符的個(gè)數(shù)稱為結(jié)點(diǎn)的大小。

顯然，結(jié)點(diǎn)大小大于1的鏈串，其結(jié)點(diǎn)的存儲(chǔ)密度提高了，但同時(shí)也帶來了問題：

(1)如何處理鏈串的最后一個(gè)結(jié)點(diǎn)，因?yàn)榇址麛?shù)不一定是結(jié)點(diǎn)大小的整數(shù)倍。

(2)插入、刪除運(yùn)算實(shí)現(xiàn)起來不方便。(p64)2023/5/14數(shù)據(jù)結(jié)構(gòu)77

typedefstructlinknode{chardata;structlinknode*next;}linkstring;linkstring*s;如果結(jié)點(diǎn)大小不為1，則此處應(yīng)說明一個(gè)字符數(shù)組。

鏈串存儲(chǔ)結(jié)構(gòu)描述如下：

2023/5/14數(shù)據(jù)結(jié)構(gòu)781）帶長度的名字表

2）帶末指針的名字表

3）帶特征位的名字表

4）帶位移量的名字表3.索引存儲(chǔ)特點(diǎn)：將串的串名作為關(guān)鍵字組織名字表(即索引表)，名字表中的每一項(xiàng)記錄了串名和串值存放單元的起址及確定串長的有關(guān)數(shù)據(jù)。

名字表一般采用順序存儲(chǔ)方式存儲(chǔ)。其組織形式主要有如下幾種：(p65)2023/5/14數(shù)據(jù)結(jié)構(gòu)79

本節(jié)討論子串定位運(yùn)算(也稱模式匹配)在順序串上的實(shí)現(xiàn),及在鏈串上的實(shí)現(xiàn)．子串定位運(yùn)算的含意：4.3串運(yùn)算的實(shí)現(xiàn)設(shè)有兩個(gè)順序串S和T，且：

S=“s0s1s2…..sn-1”目標(biāo)

T=“t0t1t2…...tm-1”模式

匹配有兩種結(jié)果：若在S中找到了模式為T的子串（若有多個(gè)模式為T的子串，只需找出第一個(gè)）時(shí)，則返回該子串在S中的位置，這種情況稱為匹配成功；否則稱為匹配失敗。2023/5/14數(shù)據(jù)結(jié)構(gòu)80

1.樸素的匹配算法基本思想：初始時(shí)，從S的第一個(gè)字符開始將T的第一個(gè)字符與其進(jìn)行比較，若相等，則繼續(xù)逐個(gè)比較后續(xù)字符，如匹配成功，則返回子串在S中的位置，否則，將T向右移動(dòng)一個(gè)字符位置，從T的第一個(gè)字符開始與S中第二個(gè)字符進(jìn)行比較，并在相等的情況下逐個(gè)比較后續(xù)字符，進(jìn)行第二趟匹配，成功則返回子串在S中的位置，否則，T再向右移動(dòng)一個(gè)字符位置，進(jìn)行第三趟匹配，如此反復(fù)，或匹配成功，或當(dāng)T右移到無法與S繼續(xù)進(jìn)行比較時(shí)，匹配失敗。

ababcabcacbababcac2023/5/14數(shù)據(jù)結(jié)構(gòu)81

1.樸素的匹配算法基本思想：初始時(shí)，從S的第一個(gè)字符開始將T的第一個(gè)字符與其進(jìn)行比較，若相等，則繼續(xù)逐個(gè)比較后續(xù)字符，如匹配成功，則返回子串在S中的位置，否則，將T向右移動(dòng)一個(gè)字符位置，從T的第一個(gè)字符開始與S中第二個(gè)字符進(jìn)行比較，并在相等的情況下逐個(gè)比較后續(xù)字符，進(jìn)行第二趟匹配，成功則返回子串在S中的位置，否則，T再向右移動(dòng)一個(gè)字符位置，進(jìn)行第三趟匹配，如此反復(fù)，或匹配成功，或當(dāng)T右移到無法與S繼續(xù)進(jìn)行比較時(shí)，匹配失敗。

ababcabcacbababcac2023/5/14數(shù)據(jù)結(jié)構(gòu)82

ababcabcacbab設(shè)S=“ababcabcacbab”T=“abcac”abcaci=0j=0i=1j=1i=2j=2i指針回溯的位置為：i=i-j+1（i的值為1）

1.樸素的匹配算法2023/5/14數(shù)據(jù)結(jié)構(gòu)83

ababcabcacbab設(shè)S=“ababcabcacbab”T=“abcac”abcaci=1j=0i指針回溯的位置為：i=i-j+1（i的值為2）2023/5/14數(shù)據(jù)結(jié)構(gòu)84設(shè)S=“ababcabcacbab”T=“abcac”

ababcabcacbababcaci=2j=0i=3j=1i=4j=2i=5j=3i=6j=4i指針回溯的位置為：i=i-j+1（i的值為3）2023/5/14數(shù)據(jù)結(jié)構(gòu)85

ababcabcacbab設(shè)S=“ababcabcacbab”T=“abcac”abcaci=3j=0i指針回溯的位置為：i=i-j+1（i的值為4）2023/5/14數(shù)據(jù)結(jié)構(gòu)86

ababcabcacbab設(shè)S=“ababcabcacbab”T=“abcac”abcaci=4j=0i指針回溯的位置為：i=i-j+1（i的值為5）2023/5/14數(shù)據(jù)結(jié)構(gòu)87

ababcabcacbab設(shè)S=“ababcabcacbab”T=“abcac”abcaci=5j=0i=6j=1i=7j=2i=8j=3i=9j=4i=10j=5返回子串的位置為：i-j+1=6（串的起始位置從1開始算起）2023/5/14數(shù)據(jù)結(jié)構(gòu)88

intindex(s,t)seqstring*s,*t;{ inti=0,j=0; while((i<scurlen)&&(j<tcurlen)) if(sch[i]==tch[j]{i++;j++;} else {i=i-j+1;j=0; } if(j==tcurlen)return(i-j+1)elsereturn(-1);}樸素的模式匹配算法描述如下：2023/5/14數(shù)據(jù)結(jié)構(gòu)895.1多維數(shù)組一、多維數(shù)組的概念多維數(shù)組可以看成是向量（一維數(shù)組）的擴(kuò)展1、二維數(shù)組：

可以看成是m個(gè)行向量和n個(gè)列向量組成的向量邏輯特征：

除邊界外，每個(gè)元素aij恰好有兩個(gè)直接前趨和兩個(gè)直接后繼。ai-1,jai,jai+1,jai,j-1ai,j+1Amn=a11a12…a1na21a22…a2n………am1am2…amn2023/5/14數(shù)據(jù)結(jié)構(gòu)902.三維及多維數(shù)組三維數(shù)組Amnp:

可看成有p個(gè)二維數(shù)組（m*n)所組成的向量每個(gè)元素aijk同屬于三個(gè)向量（二維數(shù)組）最多有3個(gè)直接前趨和直接后繼（除角、邊、面上的結(jié)點(diǎn)）推廣：多維數(shù)組An1n2…nm可看成nm個(gè)（m-1）維數(shù)組所構(gòu)成的向量任一元素ai1i2…im都屬于m個(gè)向量，最多有m個(gè)直接前趨和m個(gè)直接后繼 2023/5/14數(shù)據(jù)結(jié)構(gòu)91對(duì)于數(shù)組，通常只有兩種操作：

(1)取值：給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素；

(2)修改：給定一組下標(biāo)，修改相應(yīng)數(shù)據(jù)元素中的某一個(gè)或幾個(gè)數(shù)據(jù)項(xiàng)的值。二、多維數(shù)組的運(yùn)算說明：對(duì)于數(shù)組，通常只進(jìn)行讀、寫操作，不進(jìn)行元素的插入和刪除操作。因此，一般采用順序存儲(chǔ)結(jié)構(gòu)表示數(shù)組。2023/5/14數(shù)據(jù)結(jié)構(gòu)921、兩種順序存儲(chǔ)方法：

(1)行優(yōu)先順序(rowmajororder)(c,pascal語言采用）

特點(diǎn)：將數(shù)組元素按行向量排列(以二維數(shù)組為例）(2)列優(yōu)先順序(columnmajororder)(fortran語言采用）

特點(diǎn)：將數(shù)組元素按列向量排列(以二維數(shù)組為例）a11a12…...a1na21a22……a2n…am1am2amn

第1行第2行第m行a11a21…...am1a12a22……am2………a1na2namn

第1列第2列第n列三、順序存儲(chǔ)方法2023/5/14數(shù)據(jù)結(jié)構(gòu)932、特點(diǎn)

順序存儲(chǔ)的數(shù)組是一個(gè)隨機(jī)存取結(jié)構(gòu)，即只要知道開始元素的存儲(chǔ)起址、維數(shù)和每一維的上、下界及單個(gè)元素所占單元數(shù)，便可將數(shù)組元素的存儲(chǔ)地址表示為其下標(biāo)的線性函數(shù)。(以二維數(shù)組為例,且數(shù)組采用行優(yōu)先順序）

LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*dd為單個(gè)元素所占單元數(shù)開始元素的存儲(chǔ)起址n為列數(shù)c語言中因數(shù)組下標(biāo)從0開始，因此上面的式子應(yīng)改為：

LOC(aij)=LOC(a00)+(i*n+j)*d2023/5/14數(shù)據(jù)結(jié)構(gòu)945.2矩陣的壓縮存儲(chǔ)壓縮存儲(chǔ):

前提：非零元素呈某種規(guī)律分布或矩陣中有大量零元素定義：多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間，值為0的

元素不分配空間采用壓縮存儲(chǔ)的矩陣分為兩類：特殊矩陣和稀疏矩陣。5.2.1特殊矩陣特殊矩陣：指的是非零元素或零元素的分布有一定規(guī)律的矩陣。對(duì)特殊矩陣常采用一維數(shù)組存儲(chǔ)。需解決的問題：如何將二維數(shù)組元素下標(biāo)轉(zhuǎn)換成一維數(shù)組元素下標(biāo)。2023/5/14數(shù)據(jù)結(jié)構(gòu)95

1.對(duì)稱矩陣

1）定義:已知n階方陣A，若其元素滿足如下性質(zhì)：

aij=aji0<=i,j<=n-1

則稱A為對(duì)稱矩陣。讓每兩個(gè)對(duì)稱的元素共享一個(gè)存儲(chǔ)空間，即只存儲(chǔ)上三角或下三角矩陣元素。

需存儲(chǔ)元素的個(gè)數(shù)為n(n+1)/2，該數(shù)決定了一維數(shù)組s的大小。2)存儲(chǔ)方法：a00a10a11a20a21a22……an-1,0an-1,1an-1,2…an-1,n-12023/5/14數(shù)據(jù)結(jié)構(gòu)963)確定aij與s[k]的對(duì)應(yīng)關(guān)系

a:

若i>=j則k=i*(i+1)/2+jb:

若i<j則k=j*(j+1)/2+i(這是由對(duì)稱性質(zhì)決定的）

注意：進(jìn)行壓縮存儲(chǔ)后，沒有改變?cè)捎枚S數(shù)組存儲(chǔ)時(shí)能進(jìn)行隨機(jī)訪問的特性。綜合a、b，令I(lǐng)=max(i,j),J=min(i,j)，則

k=I*(I+1)/2+Jloc(aij)=loc(sa[k])=loc(sa[0])+k*d

=loc(sa[0])+(I*(I+1)/2+J)*da00a10a11a20a21a22…aij

an-1,0an-1,1an-1,2…an-1,n-12023/5/14數(shù)據(jù)結(jié)構(gòu)972.三角矩陣（方陣）1）分類：三角矩陣以主對(duì)角線劃分，可分為上三角矩陣和下三角矩陣。a00cc…ca10a11c…a20a21…c…………an-1,0an-1,1an-1,2…an-1,n-12023/5/14數(shù)據(jù)結(jié)構(gòu)982.三角矩陣（方陣）2）存儲(chǔ)方法：只需存儲(chǔ)非常數(shù)三角中的所有元素，另外再加一個(gè)存儲(chǔ)單元存儲(chǔ)常數(shù)C。

非常數(shù)三角中的所有元素個(gè)數(shù)為n(n+1)/2,外加一個(gè)常數(shù),總共有n(n+1)/2+1個(gè)元素，可用一維數(shù)組s[n*(n+1)/2+1]存儲(chǔ)，常數(shù)存于最后一個(gè)存儲(chǔ)單元。1）分類：三角矩陣以主對(duì)角線劃分，可分為上三角矩陣和下三角矩陣。2023/5/14數(shù)據(jù)結(jié)構(gòu)99上三角矩陣中aij與s[k]的對(duì)應(yīng)關(guān)系：下三角矩陣中aij與s[k]的對(duì)應(yīng)關(guān)系：

i*(2n-i+1)/2+j-ii<=jk=n*(n+1)/2i>j

i*(i+1)/2+ji>=jk=n*(n+1)/2i<ja00a01…a0,n-1ca11…a1,n-1……aii…aij…cc…an-1,n-13)存儲(chǔ)地址的計(jì)算i*n-(i-1)*i/22023/5/14數(shù)據(jù)結(jié)構(gòu)1003.對(duì)角矩陣特點(diǎn)：所有的非零元素都集中在以對(duì)角線為中心的帶狀區(qū)域中。帶狀區(qū)域外的所有元素均為零。以三對(duì)角矩陣為例（p75)三對(duì)角矩陣中所有非零元素為3*n-2,可用一維數(shù)組s[3*n-2]存儲(chǔ).再次強(qiáng)調(diào)：特殊矩陣的壓縮存儲(chǔ)沒有改變?cè)捎枚S數(shù)組存儲(chǔ)時(shí)所具有的隨機(jī)存取特性。

2023/5/14數(shù)據(jù)結(jié)構(gòu)1015.2.2稀疏矩陣稀疏矩陣的壓縮存儲(chǔ)通常有兩種方式：三元組表和十字鏈表。稀疏矩陣：非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)少于矩陣元素的總數(shù)的矩陣（s<<m*n)。壓縮存儲(chǔ)：只存儲(chǔ)非零元素1、基本概念壓縮存儲(chǔ)特點(diǎn)：由于非零元素的分布是無規(guī)律的，在進(jìn)行壓縮存儲(chǔ)后，將破壞原采用二維數(shù)組存儲(chǔ)時(shí)所具有的隨機(jī)存儲(chǔ)特性。2023/5/14數(shù)據(jù)結(jié)構(gòu)1021）定義：用一個(gè)三元組(i,j,aij)來表示稀疏矩陣中的一個(gè)非零元素aij,將表示稀疏矩陣中所有非零元素的三元組按行優(yōu)先的原則順序排列，得到一個(gè)其結(jié)點(diǎn)均為三元組的線性表，該表稱為三元組表（結(jié)構(gòu)數(shù)組）。A4*4=050000300-2006000015231-2306ijvB4*5=05000003000-200060000所以，為了唯一確定一個(gè)稀疏矩陣，還必須存儲(chǔ)矩陣的行、列數(shù)。為了運(yùn)算實(shí)現(xiàn)的方便，通常將稀疏矩陣的行、列數(shù)與三元組表存儲(chǔ)在一起。2、三元組表2023/5/14數(shù)據(jù)結(jié)構(gòu)1032）稀疏矩陣用三元組表實(shí)現(xiàn)壓縮存儲(chǔ)時(shí)的存儲(chǔ)結(jié)構(gòu)描述#defineSMAX16typedefstruct

{inti,j;datatypev;}node;typedefstruct{intm,n,t；

nodedata[SMAX];}spmatrix;spmatrix*a;定義三元組結(jié)構(gòu)

定義三元組表結(jié)構(gòu)2023/5/14數(shù)據(jù)結(jié)構(gòu)1043)運(yùn)算：

稀疏矩陣采用三元組表實(shí)現(xiàn)存儲(chǔ)后，其矩陣運(yùn)算的實(shí)現(xiàn)比采用二維數(shù)組存儲(chǔ)時(shí)要復(fù)雜。2023/5/14數(shù)據(jù)結(jié)構(gòu)105a)矩陣的轉(zhuǎn)置運(yùn)算

A=

00-3200000012000B=轉(zhuǎn)置

0200000010-30020

01213120-3232

ijvA的三元組表

ijv

02-3102311322B的三元組表轉(zhuǎn)置后例：spmatrix*a;

a->m==3;a->n==5;a->t==4;a->data[16]2023/5/14數(shù)據(jù)結(jié)構(gòu)106傳統(tǒng)轉(zhuǎn)置方法介紹基本思想：由于A的列是B的行，因此按a->data的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置矩陣B的三元組表b->data必定是按行優(yōu)先順序存放的。為了找到A的每一列中的所有非零元素，需要對(duì)三元組表a->data從第一行起掃描一遍，由于a->data是按A的行優(yōu)先順序存放的，因此得到的恰是b->data應(yīng)有的順序。時(shí)間復(fù)雜度：O(n*t)>>O(m*n)

01213120-3232

ijvA的三元組表

ijv

02-3102311322B的三元組表轉(zhuǎn)置后2023/5/14數(shù)據(jù)結(jié)構(gòu)1073、十字鏈表1)十字鏈表中結(jié)點(diǎn)的結(jié)構(gòu)：

ijv/nextcptrrptr存儲(chǔ)行號(hào)存儲(chǔ)列號(hào)存儲(chǔ)元素值或指向下一個(gè)表頭結(jié)點(diǎn)列指針域，指向本列下一個(gè)非零元素行指針域，指向本行下一個(gè)非零元素4)三元組表的優(yōu)點(diǎn)：結(jié)構(gòu)簡單，易于實(shí)現(xiàn)，存儲(chǔ)密度高。

缺點(diǎn)：不具有隨機(jī)存儲(chǔ)特性；

矩陣中非零元素發(fā)生變化時(shí)，將會(huì)引起三 元組表中大量元素的移動(dòng)。十字鏈表h00

00

00

00

00

122

241

31-3

342

00

00

00

35

H1H1H4H2H3H2H5H3A=

0200000010-30020

ijv/nextcptrrptr2023/5/14數(shù)據(jù)結(jié)構(gòu)1092)十字鏈表存儲(chǔ)結(jié)構(gòu)描述：

typedefstructlnode{inti,j;structlnode*cptr,*rptr;

union{structlnode*next;datatypev;}uval;}link;3)建立十字鏈表

ijv/nextcptrrptr2023/5/14數(shù)據(jù)結(jié)構(gòu)110建立十字鏈表的算法分為兩步：

1.建立表頭結(jié)點(diǎn)的循環(huán)鏈表

2.依次讀入非零元素的三元組，每讀入一個(gè)三元組，生成一個(gè)表結(jié)點(diǎn)，并將其插入相應(yīng)行、列鏈表中的正確位置上。2023/5/14數(shù)據(jù)結(jié)構(gòu)1115.3廣義表的概念廣義表(Lists)是n（n>=0)個(gè)元素a1,a2,…an的有限序列，其中ai或者是原子或者是一個(gè)廣義表，通常記為LS=(a1,a2,…,an)1、定義：2023/5/14數(shù)據(jù)結(jié)構(gòu)112補(bǔ)充說明：對(duì)于LS=(a1,a2,…,an)LS:廣義表的名字n:廣義表的長度。E=(a,E)如果ai是