數(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)及其概念

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法所耗費的存儲空間，仍是問題規(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é)會算法分析的基本方法。2023/5/14數(shù)據(jù)結(jié)構(gòu)17第二章線性表本章要學(xué)習(xí)的主要內(nèi)容1、線性表的邏輯結(jié)構(gòu)及基本運算2、線性表的順序存儲結(jié)構(gòu)3、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)：單鏈表、循環(huán)鏈表、雙鏈表、靜態(tài)鏈表4、順序表和鏈表的比較2023/5/14數(shù)據(jù)結(jié)構(gòu)182.1線性表的概念及運算1.描述:

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

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

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

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

（1）置空表SETNULL(L)

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

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

（5）定位LOCATE(L,x)

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

（7）刪除DELETE(L,i)

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

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

這里：LOC(a1)為結(jié)點a1的存儲起址(基地址），c為每個結(jié)點所占存儲單元數(shù)。一、順序表2、順序表：采用順序存儲方法存儲的線性表稱順序表。順序表是一種隨機存取結(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é)點的相對地址(3).

順序表的長度為last+1(4).結(jié)點的引用:定義一個順序表：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二、順序表上的基本運算（實現(xiàn)）2.2線性表的順序存儲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順序表的特點：

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

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

typedef

int

dataype;

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

typedef

int

datatype;

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

申請一個結(jié)點p=(linklist*)malloc(sizeof(linklist));釋放一個結(jié)點free(p);2023/5/14數(shù)據(jù)結(jié)構(gòu)272.3.2單鏈表上的基本運算（實現(xiàn)）1.建立單鏈表（1）頭插法建表（2）尾插法建表方法:從一個空表開始,重復(fù)讀入數(shù)據(jù),生成新結(jié)點,將讀入數(shù)據(jù)存放在新結(jié)點的數(shù)據(jù)域,然后將新結(jié)點插入當(dāng)前鏈表中,直到結(jié)束。頭插法建表：將新結(jié)點插入到當(dāng)前鏈表的表頭ds優(yōu)點：算法簡單缺點：鏈表中結(jié)點次序和輸入次序相反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單鏈表上的基本運算（實現(xiàn)）尾插法建表：將新結(jié)點插入到當(dāng)前鏈表的表尾（需引入r）dsrabcHeadr^^不帶頭結(jié)點的尾插法：插入時，第一個結(jié)點的處理與其 它結(jié)點的處理有區(qū)別。

結(jié)束時，空表和非空表的處理有區(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單鏈表上的基本運算（實現(xiàn)）尾插法建表：將新結(jié)點插入到當(dāng)前鏈表的表尾（需引入r）dsrabcHeadr^^不帶頭結(jié)點的尾插法：插入時，第一個結(jié)點的處理與其 它結(jié)點的處理有區(qū)別。

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

2）空表和非空表的處理相一致。2023/5/14數(shù)據(jù)結(jié)構(gòu)322.3.2單鏈表上的基本運算（實現(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單鏈表上的基本運算（實現(xiàn)）

二、查找運算（1）按序號查找GET（L，i）

給定一個序號，在單鏈表中查找該序號對應(yīng)的結(jié)點，

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

linklist*locate(head,key)

linklist*head;

datatyekey;

{linklist*p;

p=headnext;

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

if(pdata!=key)

p=pnext;

elsebreak;

returnp;

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

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

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

實用中常采用尾指針單循環(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.

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

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

typedef

struct

dnode{datatypedata;

struct

dnode*prior,*next;}dlinklist;

dlinklist*head;

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

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

/*刪除雙鏈表結(jié)點*p*/dlinklist*p;{p->prior->next=p->next;p->next->prior=p->prior;free(p);}Headp2023/5/14數(shù)據(jù)結(jié)構(gòu)41插入運算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)鏈表

實現(xiàn)方法

存儲空間

分配和釋放

靜態(tài)鏈表

游

標(biāo)

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

用戶定義

動態(tài)鏈表

指

針

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

系統(tǒng)提供

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

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

＃definemaxsize1024 typedefintdatatype; typedef

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

cursornext;游標(biāo)

}node;nodenodepool[maxsize];存儲池

cursorav;游標(biāo)變量

2.3.5靜態(tài)鏈表1、用數(shù)組和“游標(biāo)”實現(xiàn)鏈?zhǔn)酱鎯Φ姆椒ㄊ牵?/p>

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

3、可用空間表:將存儲池中所有空閑結(jié)點鏈成一個頭指針為av的單鏈表,構(gòu)成一個可用空間表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;}動態(tài)鏈表由系統(tǒng)分配和回收結(jié)點空間,靜態(tài)鏈表由程序員編程分配和釋放結(jié)點2023/5/14數(shù)據(jù)結(jié)構(gòu)464、節(jié)點的分配與回收GETNODE():將表av上的第一個結(jié)點取出，并把該結(jié)點的位置付給pCursorGETNODE(){cursorp;if(av==NULL)p=NULL;else{p=av; av=nodepool[av].next; }returnp;}FREENODE(p)將p所指的結(jié)點插入到表av的頭上。FREENODE(p){nodepool[p].next=av;av=p}2023/5/14數(shù)據(jù)結(jié)構(gòu)475、靜態(tài)鏈表基本運算的實現(xiàn)

:

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

算的線性表

棧頂(top)為進行插入和刪除運算的一端

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

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

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

datatypepop(s)5）取棧頂

datatypetop(s)

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

為了充分利用向量存儲空間，多個棧共用一段存儲空間。缺點：使棧運算的實現(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)酱鎯Y(jié)構(gòu)的棧稱為鏈棧。

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

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

typedefintdatatype;typedef

structnode{datatypedata;structnode*next;}

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

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

1）

進棧

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隊列1定義：隊列(queue)

是一端進行刪除另一端進行插入的線性表。

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

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

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

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

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

sq->frontsq->rear43210DCBA43210DC

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

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

sqrear=sqfront隊滿：

sqrear－sqfront=maxsize下溢：隊空時，若要進行出隊操作時發(fā)生上溢：隊滿時，進行入隊操作時出現(xiàn)?！凹偕弦纭保寒?dāng)sq->rear=maxsize-1但隊列并不滿

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

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

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

入隊：

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

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

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

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

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

typedef

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

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

^frontrearq頭結(jié)點qrearfrontrearq頭結(jié)點

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

^qfront隊頭結(jié)點*sfrontrearq頭結(jié)點a1*s

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

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

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

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

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

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

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

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

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

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

串的基本運算有九種，具體如下（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串的存儲結(jié)構(gòu)

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

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

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

２）

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

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

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

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

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

(1)如何處理鏈串的最后一個結(jié)點，因為串所含字符數(shù)不一定是結(jié)點大小的整數(shù)倍。

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

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

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

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

2）帶末指針的名字表

3）帶特征位的名字表

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

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

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

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

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

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

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

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

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

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ù)組）的擴展1、二維數(shù)組：

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

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

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

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

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

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

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

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

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

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

LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*dd為單個元素所占單元數(shù)開始元素的存儲起址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矩陣的壓縮存儲壓縮存儲:

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

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

1.對稱矩陣

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

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

則稱A為對稱矩陣。讓每兩個對稱的元素共享一個存儲空間，即只存儲上三角或下三角矩陣元素。

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

a:

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

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

注意：進行壓縮存儲后，沒有改變原采用二維數(shù)組存儲時能進行隨機訪問的特性。綜合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）分類：三角矩陣以主對角線劃分，可分為上三角矩陣和下三角矩陣。a00cc…ca10a11c…a20a21…c…………an-1,0an-1,1an-1,2…an-1,n-12023/5/14數(shù)據(jù)結(jié)構(gòu)982.三角矩陣（方陣）2）存儲方法：只需存儲非常數(shù)三角中的所有元素，另外再加一個存儲單元存儲常數(shù)C。

非常數(shù)三角中的所有元素個數(shù)為n(n+1)/2,外加一個常數(shù),總共有n(n+1)/2+1個元素，可用一維數(shù)組s[n*(n+1)/2+1]存儲，常數(shù)存于最后一個存儲單元。1）分類：三角矩陣以主對角線劃分，可分為上三角矩陣和下三角矩陣。2023/5/14數(shù)據(jù)結(jié)構(gòu)99上三角矩陣中aij與s[k]的對應(yīng)關(guān)系：下三角矩陣中aij與s[k]的對應(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)存儲地址的計算i*n-(i-1)*i/22023/5/14數(shù)據(jù)結(jié)構(gòu)1003.對角矩陣特點：所有的非零元素都集中在以對角線為中心的帶狀區(qū)域中。帶狀區(qū)域外的所有元素均為零。以三對角矩陣為例（p75)三對角矩陣中所有非零元素為3*n-2,可用一維數(shù)組s[3*n-2]存儲.再次強調(diào)：特殊矩陣的壓縮存儲沒有改變原采用二維數(shù)組存儲時所具有的隨機存取特性。

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

稀疏矩陣采用三元組表實現(xiàn)存儲后，其矩陣運算的實現(xiàn)比采用二維數(shù)組存儲時要復(fù)雜。2023/5/14數(shù)據(jù)結(jié)構(gòu)105a)矩陣的轉(zhuǎ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的每一列中的所有非零元素，需要對三元組表a->data從第一行起掃描一遍，由于a->data是按A的行優(yōu)先順序存放的，因此得到的恰是b->data應(yīng)有的順序。時間復(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é)點的結(jié)構(gòu)：

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

缺點：不具有隨機存儲特性；

矩陣中非零元素發(fā)生變化時，將會引起三 元組表中大量元素的移動。十字鏈表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)十字鏈表存儲結(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é)點的循環(huán)鏈表

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