數(shù)據(jù)結(jié)構(gòu)考研課程總結(jié)課件

1、數(shù)據(jù)結(jié)構(gòu) 主講 劉鐵銘單位工院一系二教Tel: 319468/22/20221數(shù)據(jù)結(jié)構(gòu)講課安排：串講全書內(nèi)容典型習(xí)題分析前年、去年考題分析 8/22/20222數(shù)據(jù)結(jié)構(gòu)第一章 概 論數(shù)據(jù)結(jié)構(gòu)及其概念 如何評(píng)價(jià)一個(gè)算法8/22/20223數(shù)據(jù)結(jié)構(gòu)第一章 概 論1.1 數(shù)據(jù)結(jié)構(gòu)的概念一、術(shù)語(yǔ)1.數(shù)據(jù)(Data): 是信息的載體，能被計(jì)算機(jī)識(shí)別、存儲(chǔ)、加工處理。2.數(shù)據(jù)元素(Data Element): 數(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)(data item)組成8

2、/22/20224數(shù)據(jù)結(jié)構(gòu) 3、數(shù)據(jù)類型(Data Type): 是具有相同性質(zhì)的計(jì)算機(jī)數(shù)據(jù)的集合及在這個(gè)集合上的一組操作。原子數(shù)據(jù)類型(atomic data type)結(jié)構(gòu)數(shù)據(jù)類型(aggregate data type)4、數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算：既對(duì)數(shù)據(jù)施加的操作8/22/20225數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)：(有時(shí)直接稱為數(shù)據(jù)結(jié)構(gòu)）線性結(jié)構(gòu)：線性表、棧、隊(duì)列、串(最多只有一個(gè)直接前趨和一個(gè)直接后繼)非線性結(jié)構(gòu)：樹(shù) 、圖、多維數(shù)組、廣義表說(shuō)明：1、邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容無(wú)關(guān)2、邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對(duì)位置無(wú)關(guān)3、邏輯結(jié)構(gòu)與所含結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)8/22/202

3、26數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)方法：數(shù)據(jù)元素在內(nèi)存中按序連續(xù)存儲(chǔ)， 結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)鏈接存儲(chǔ)方法：用指針指出其直接后繼結(jié)點(diǎn)的存儲(chǔ)位置， 結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(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ǔ)地址。8/22/20227數(shù)據(jù)結(jié)構(gòu)關(guān)系：邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，與存儲(chǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。邏輯結(jié)構(gòu)是從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)（亦稱映象）數(shù)據(jù)的運(yùn)算

4、是定義在數(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)系8/22/20228數(shù)據(jù)結(jié)構(gòu)例：一個(gè)學(xué)生成績(jī)表：是一個(gè)數(shù)據(jù)結(jié)構(gòu)每行是一個(gè)結(jié)點(diǎn)（或記錄），由學(xué)號(hào)、姓名、各科成績(jī) 及平均成績(jī)等數(shù)據(jù)項(xiàng)組成。邏輯關(guān)系：線性結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)：表的運(yùn)算：8/22/20229數(shù)據(jù)結(jié)構(gòu) 邏輯結(jié)構(gòu)上定義的基本運(yùn)算在存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)是通過(guò)算法來(lái)描述的。一、算法定義 算法是對(duì)特定問(wèn)題求解步驟的一種描述，由有限的指令序列構(gòu)成，其中每一條指令表示一個(gè)或多個(gè)操作。第一章 概 論1.3 算法描述8/22/202210數(shù)據(jù)結(jié)構(gòu) 二、算法應(yīng)具有的五個(gè)特性：（1）輸入 一個(gè)算法有零個(gè)或多個(gè)的輸入，

5、它們是算法開(kāi)始前給出的最初量（2）輸出 一個(gè)算法至少有一個(gè)輸出，它們是同輸入 有某種關(guān)系的量（3）有窮性 每一條指令的執(zhí)行次數(shù)必須是有限的（4）確定性 每一條指令必須有確切的含義，無(wú)二義性（5）可行性 每條指令的執(zhí)行時(shí)間都是有限的。8/22/202211數(shù)據(jù)結(jié)構(gòu)第一章 概 論一、算法評(píng)價(jià)五要素 （1）正確性（2）執(zhí)行算法所耗費(fèi)的時(shí)間（3）執(zhí)行算法所耗費(fèi)的空間（4）可讀性（5）健壯性1.4 算法分析8/22/202212數(shù)據(jù)結(jié)構(gòu)第一章 概 論二、算法的時(shí)間復(fù)雜度 一個(gè)算法所耗費(fèi)的時(shí)間:該算法中每條語(yǔ)句的執(zhí)行時(shí)間之和。每條語(yǔ)句的執(zhí)行時(shí)間：該語(yǔ)句的執(zhí)行次數(shù)乘以該語(yǔ)句執(zhí)行一次所需時(shí)間。頻度：語(yǔ)句重復(fù)執(zhí)

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

7、模n的函數(shù)。第一章 概 論8/22/202215數(shù)據(jù)結(jié)構(gòu)第一章 概 論本章要求:1、掌握數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)等基本概念。2、掌握數(shù)據(jù)邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的分類。3、學(xué)會(huì)算法分析的基本方法。8/22/202216數(shù)據(jù)結(jié)構(gòu)第二章 線性表本章要學(xué)習(xí)的主要內(nèi)容1、線性表的邏輯結(jié)構(gòu)及基本運(yùn)算2、線性表的順序存儲(chǔ)結(jié)構(gòu)3、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：?jiǎn)捂湵?、循環(huán)鏈表、雙鏈表、靜態(tài)鏈表4、順序表和鏈表的比較8/22/202217數(shù)據(jù)結(jié)構(gòu)2.1 線性表的概念及運(yùn)算1.描述: 線性表是由n (n=0)個(gè)數(shù)據(jù)元素(點(diǎn))a1,a2,.,ai,.,an組成的有限序列。其中，數(shù)據(jù)元素的個(gè)數(shù)n定義為表長(zhǎng)。當(dāng)n=0時(shí)稱為空表，非

8、空的線性表(n0)記為： (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è)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼8/22/202218數(shù)據(jù)結(jié)構(gòu)線性表的常見(jiàn)基本運(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

9、(L,i) （3）求表長(zhǎng)LENGTH(L)復(fù)雜的運(yùn)算可以由這些基本運(yùn)算組合來(lái)實(shí)現(xiàn)8/22/202219數(shù)據(jù)結(jié)構(gòu)2.2 線性表的順序存儲(chǔ)1、順序存儲(chǔ)：將線性表的結(jié)點(diǎn)按邏輯次序依次存放在一組地址連續(xù)的存儲(chǔ)單元里。 3、存儲(chǔ)地址的計(jì)算： LOC(ai)=LOC(a1)+(i-1)*c 1=idata=ch; s-next=head; head=s; ch=getchar( );return head;8/22/202228數(shù)據(jù)結(jié)構(gòu)2.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)的處理

10、有區(qū)別。 結(jié)束時(shí)，空表和非空表的處理有區(qū)別。8/22/202229數(shù)據(jù)結(jié)構(gòu)Linklist *CREATLISTR( ) char ch; linklist *head,*s,*r; head=NULL; r=NULL; ch=getchar( ); while (ch!=$) s=malloc(sizeof(linklist) ; s-data=ch; if(head=NULL) head=s else r-next=s; r=s; ch=getchar( ); if (r!=NULL) r-next=NULL; return head;8/22/202230數(shù)據(jù)結(jié)構(gòu)2.3.2 單鏈表上的基

11、本運(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）空表和非空表的處理相一致。8/22/202231數(shù)據(jù)結(jié)構(gòu)2.3.2 單鏈表上的基本運(yùn)算（實(shí)現(xiàn)）Linklist *CREATLISTR1() char ch; linklist *head,*s,*r; head=malloc(sizeof(linklist); r=head; ch=getchar(); while(ch!=“$”)

12、 s=malloc(sizeof(linklist); s-data=ch; r-next=s; r=s; ch=getchar(); r-next=NULL; return head; dsrcHeadr8/22/202232數(shù)據(jù)結(jié)構(gòu)2.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)算只能通過(guò)掃描單鏈表來(lái)完成。設(shè)置一個(gè)計(jì)數(shù)器j一個(gè)p，初始指向頭結(jié)點(diǎn)P向后每移動(dòng)一個(gè)位置j+當(dāng)j=i時(shí)返回8/22/202233數(shù)據(jù)結(jié)構(gòu)按

13、值查找即在鏈表中查找是否有值等于給定值key的結(jié)點(diǎn)。若有則返回首次找到的其值為key的結(jié)點(diǎn)的指針，否則返回NULL。算法描述如下： linklist *locate(head,key) linklist *head; datatye key; linklist *p; p=head next;在等概率的情況下，該算法的平均時(shí)間復(fù)雜度亦為O(n)（2）按值查找 LOCATE（head，key）2.3.2 單鏈表上的基本運(yùn)算（實(shí)現(xiàn)）while (p!=NULL) if (p data!=key) p=p next; else break ; return p; 8/22/202234數(shù)據(jù)結(jié)構(gòu) 3.

14、插入運(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.Headpq8/22/202235數(shù)據(jù)結(jié)構(gòu)Headpax 3.插入運(yùn)算:將前插操作轉(zhuǎn)變?yōu)楹蟛宀僮鱴sxsaINSERTBEFORE(p,x)linklist *p;datatype x;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)盡量將單鏈表上的插入操

15、作轉(zhuǎn)化為后插操作！8/22/202236數(shù)據(jù)結(jié)構(gòu) 4.刪除運(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)算無(wú)須移動(dòng)結(jié)點(diǎn)，僅須修改指針改進(jìn)?8/22/202237數(shù)據(jù)結(jié)構(gòu)2.單循環(huán)鏈表的特點(diǎn)：鏈表尾結(jié)點(diǎn)的next域不為空，而是指向頭結(jié)點(diǎn)或開(kāi)始結(jié)點(diǎn)。（優(yōu)點(diǎn)：從任一結(jié)點(diǎn)開(kāi)始，均可找到其前趨和后繼結(jié)點(diǎn)。）3、引入單循環(huán)鏈表的目的在于方便一些運(yùn)算的實(shí)現(xiàn)。實(shí)用中常采用尾指針單循環(huán)鏈表,而不是頭指針單循環(huán)鏈表。4、單循環(huán)鏈表上的操作與單鏈表基本一致 差別僅在于：循環(huán)控制

16、條件不是判空，而是判斷是否等于頭指針或尾指針。2.3.3 單循環(huán)鏈表1.循環(huán)鏈表:是一種首尾相接的鏈表單循環(huán)鏈表雙循環(huán)鏈表8/22/202238數(shù)據(jù)結(jié)構(gòu) 1. 雙鏈表的特點(diǎn)：每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，分別指向其直接 前趨和后繼。2.雙鏈表存儲(chǔ)結(jié)構(gòu)描述如下： typedef struct dnode datatype data; struct dnode *prior,*next; dlinklist; dlinklist *head; 對(duì)于雙向鏈表，當(dāng)將頭、尾結(jié)點(diǎn)鏈起來(lái)時(shí)，便成了雙向循環(huán)鏈表。2.3.4 雙鏈表 priornextdata為了指示雙鏈表，也須引入一個(gè)頭指針head，指向其開(kāi)始結(jié)點(diǎn)。

17、8/22/202239數(shù)據(jù)結(jié)構(gòu)3.雙向鏈表基本運(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);Headp8/22/202240數(shù)據(jù)結(jié)構(gòu)插入運(yùn)算DINSERTBEFORE(p,x)dlinklist *p;datatype x;dlinklist *s;Pxss=malloc(sizeof(dlinklist);s-data=x;s-p

18、rior=p -prior;s-next=p;p -prior -next=s;p -prior=s;8/22/202241數(shù)據(jù)結(jié)構(gòu)2.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ū)別8/22/202242數(shù)據(jù)結(jié)構(gòu) 2、靜態(tài)鏈表存儲(chǔ)結(jié)構(gòu)描述如下：define maxsize 1024typedef int datatype;typedef int cursor ; typedef struct datatype data; 數(shù)據(jù)域 cursor next; 游標(biāo) node;

19、 node nodepoolmaxsize; 存儲(chǔ)池 cursor av; 游標(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-1av0nodepoolmaxsize8/22/202243數(shù)據(jù)結(jié)構(gòu)說(shuō)明:靜態(tài)鏈表也可以用頭指針L唯一指示 ,L為cursor類型 3、可用空間表:將存儲(chǔ)池中所有空閑結(jié)點(diǎn)鏈成一個(gè)頭指針為av的單鏈表,構(gòu)成一個(gè)可用空間表8/2

20、2/202244數(shù)據(jù)結(jié)構(gòu)2.3.5 靜態(tài)鏈表12Maxsize-13NULL012Maxsize-1av1nodepoolmaxsize初始化：INITALIZE() int i; for (i=0;idata=x; p-next=top; return p;8/22/202256數(shù)據(jù)結(jié)構(gòu)Linkstack *POPLSTACK(top,datap)linkstack *top;datatype *datap; linkstack *p; if(top=NULL) printf(“underflow”); return NULL; else *datap=top-data; p=top; to

21、p=top-next; free(p); return top; 2） 退棧 *POPLSTACK(top,datap)8/22/202257數(shù)據(jù)結(jié)構(gòu)3.2 棧的應(yīng)用舉例1. 文字編輯器2. 函數(shù)的遞歸調(diào)用（p47)8/22/202258數(shù)據(jù)結(jié)構(gòu)3.3 隊(duì) 列1定義：隊(duì)列(queue) 是一端進(jìn)行刪除另一端進(jìn)行插入的線性表。允許插入的一端稱為隊(duì)尾(rear) ，允許刪除的一端稱為隊(duì)頭(front)。2特點(diǎn)： 先入隊(duì)(即插入隊(duì)尾）的元素必將被先刪除(即出隊(duì)）。因此，隊(duì)列是一種先進(jìn)先出(First In First Out)的線性表。3.3.1 隊(duì)列的概念及運(yùn)算出隊(duì)入隊(duì)隊(duì)頭隊(duì)尾a1 a2 an8/

22、22/202259數(shù)據(jù)結(jié)構(gòu) 3隊(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ì)頭元素8/22/202260數(shù)據(jù)結(jié)構(gòu)3.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)描述如下： typedef struct datatype datamaxsize; int front,rear; sequeue;

23、sequeue *sq;8/22/202261數(shù)據(jù)結(jié)構(gòu)4 3 2 1 0sq-rearsq-front sq-rear4 3 2 1 0DCBA4 3 2 1 0DC 空隊(duì)列 ABCD入隊(duì) AB出棧sq-front sq-front sq-rear3 順序隊(duì)列指針圖示4 順序隊(duì)列基本運(yùn)算初始時(shí)，sqrear=sq front=-1,在不考慮溢出的情況下，入隊(duì)和出隊(duì)的運(yùn)算如下： 入隊(duì)： sq rear+; sq datasq rear=x;出隊(duì)： sq front+;8/22/202262數(shù)據(jù)結(jié)構(gòu)隊(duì)空： sq rear=sq front隊(duì)滿： sq rear sq front=maxsize下溢

24、： 隊(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ì)列空間并沒(méi)用完。 4 幾種特殊情況8/22/202263數(shù)據(jù)結(jié)構(gòu)解決“假上溢”的方法有兩種： （1）當(dāng)元素出隊(duì)或出現(xiàn)假上溢時(shí)，移動(dòng)隊(duì)列元素。 sqrear=4sqfront=143210edcbaedc43210sqrear=2sqfront= -1移動(dòng)元素后（2）

25、采用循環(huán)隊(duì)列：即sq-data0 接在sq-datamaxsize-1之后循環(huán)隊(duì)列的示意圖054321sqrear=0sqfront=48/22/202264數(shù)據(jù)結(jié)構(gòu)采用循環(huán)隊(duì)列后，進(jìn)行入隊(duì)和出隊(duì)運(yùn)算時(shí)，頭、尾指針加1操作應(yīng)如下進(jìn)行： 出隊(duì)： sq front=(sq front+1)% maxsize; 入隊(duì)： sq rear=(sq rear+1)% maxsize;循環(huán)隊(duì)列如何判斷隊(duì)空和隊(duì)滿? 方法一：引入標(biāo)志flag 若 (sq front=sq rear)&(flag=0),則隊(duì)空,不能出棧。 若 (sq front=sq rear)&(flag=1),則隊(duì)滿,不能入棧。054321

26、sqrear=5sqfront=5054321sqfront=5sqrear=48/22/202265數(shù)據(jù)結(jié)構(gòu) 方法二：犧牲一個(gè)元素的空間（sq-datasq-front)，避免隊(duì)滿時(shí)頭、尾指針指向同一位置。 若 sq front=sq rear，則隊(duì)空。 若 (sq rear+1)%maxsize= sq front，則隊(duì)滿。054321sqrear=1sqfront=1054321sqfront=5sqrear=48/22/202266數(shù)據(jù)結(jié)構(gòu)3.3.3 鏈 隊(duì) 列1 、定義：采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的隊(duì)列稱為鏈隊(duì)列。（是限制在表頭刪除在表尾插入的單鏈表）2 、鏈隊(duì)列存儲(chǔ)結(jié)構(gòu)描述 typedef

27、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)。 front rear q頭結(jié)點(diǎn)qrearfront rear q頭結(jié)點(diǎn) qfront隊(duì)頭結(jié)點(diǎn)q-front=q-rear8/22/202267數(shù)據(jù)結(jié)構(gòu)1）入隊(duì)ENQUEUE（q,x)類似于單鏈表的尾插法8/22/202268數(shù)據(jù)結(jié)構(gòu)2）出隊(duì)qrearfront rear q頭結(jié)點(diǎn) qfront隊(duì)頭結(jié)點(diǎn)*sfront rear q頭結(jié)點(diǎn)a1*s front rear q頭結(jié)點(diǎn)S=q-front

28、-next; q-front-next=s-next; free(s);隊(duì)列長(zhǎng)度等于1時(shí)，不但修改頭結(jié)點(diǎn)的指針域，還需尾指針。隊(duì)列長(zhǎng)度大于1時(shí)，只需修改頭結(jié)點(diǎn)的指針域，尾指針不變。8/22/202269數(shù)據(jù)結(jié)構(gòu)解決方法：出隊(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ì)列長(zhǎng)度為1，也不用修改尾指針。qrearfront rear q頭結(jié)點(diǎn) 隊(duì)頭結(jié)點(diǎn)*s8/22/202270數(shù)據(jù)結(jié)構(gòu)串(即字符串）是一種特殊的線性表，其每個(gè)結(jié)點(diǎn)僅由一個(gè)字符組成。4.1 串及其運(yùn)算4.1.1 串的基本概念 1.

29、串(string):是由零個(gè)或多個(gè)字符組成的有限序列。 一般記為S=“a1a2.an”, 其中：S為串名，a1a2an為串值；ai(1=i=n)可 以是字母、數(shù)字和其它字符； 注意：僅含一個(gè)空格的串（“”）和空串（“ ”）是不同的兩個(gè)串。2.串長(zhǎng)度：串中所含的字符個(gè)數(shù) 空串：長(zhǎng)度為零的串（不含任何字符，和空格串嚴(yán)格區(qū)分）第四章 串8/22/202271數(shù)據(jù)結(jié)構(gòu)4.子串在主串中的序號(hào)：子串在主串中第一次出現(xiàn)時(shí)其第一個(gè)字符在主串中的序號(hào)。S1=“Iamastudent.”S2=“student”S2在S1中的序號(hào)為83.子串： 串中任意個(gè)連續(xù)的字符組成的子序列,該串相應(yīng)稱為主串?？沾疄槿我獯淖哟?/p>

30、，任意串為其自身的子串。兩串相等當(dāng)且僅當(dāng)兩串長(zhǎng)度相等且對(duì)應(yīng)位置上的字符相同。5. 在程序中使用的串可分為串常量和串變量S2=“student”將串常量命名為S2char object=“datastructure”第四章 串8/22/202272數(shù)據(jù)結(jié)構(gòu)4.1.2 串的基本運(yùn)算 串的基本運(yùn)算有九種，具體如下（p61）（1）賦值：=（2）聯(lián)接： strcat(ST1,ST2) （3）求串長(zhǎng)：strlen(S) （4）求子串：substr(S,i,j) （5）比較串的大?。簊trcmp(S,T) （6）插入：insert(S1,i,S2) （7）刪除：delete(S,i,j) （9）置換：rep

31、lace(S1,i,j,S2)， repl(S,T,V) 8/22/202273數(shù)據(jù)結(jié)構(gòu)4.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)的串稱為順序串。 H o w a r e y o u ? . 串S的順序存儲(chǔ)示意圖S=“How are you?”#define maxsize 32char smaxsize;8/22/202274數(shù)據(jù)結(jié)構(gòu) ） 順序串存儲(chǔ)結(jié)構(gòu)描述： #define maxsize 128;typedef struct char chmaxsize; int

32、curlen; seqstring;串字符存儲(chǔ)空間串長(zhǎng)度 缺點(diǎn)： 順序串上插入、刪除運(yùn)算不方便。8/22/202275數(shù)據(jù)結(jié)構(gòu) 2. 鏈?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í)也帶來(lái)了問(wèn)題： (1) 如何處理鏈串的最后一個(gè)結(jié)點(diǎn)，因?yàn)榇址麛?shù)不一定是結(jié)點(diǎn)大小的整數(shù)倍。 (2) 插入、刪除運(yùn)算實(shí)現(xiàn)起來(lái)不方便。(p64)8/22/202276數(shù)據(jù)結(jié)構(gòu) typedef struct linknode char data; struct linkno

33、de *next; linkstring; linkstring *s;如果結(jié)點(diǎn)大小不為1，則此處應(yīng)說(shuō)明一個(gè)字符數(shù)組。 鏈串存儲(chǔ)結(jié)構(gòu)描述如下： 8/22/202277數(shù)據(jù)結(jié)構(gòu) 1）帶長(zhǎng)度的名字表 2）帶末指針的名字表 3）帶特征位的名字表 4）帶位移量的名字表 3. 索引存儲(chǔ)特點(diǎn)：將串的串名作為關(guān)鍵字組織名字表(即索引表)，名字表中的每一項(xiàng)記錄了串名和串值存放單元的起址及確定串長(zhǎng)的有關(guān)數(shù)據(jù)。 名字表一般采用順序存儲(chǔ)方式存儲(chǔ)。其組織形式主要有如下幾種：(p65)8/22/202278數(shù)據(jù)結(jié)構(gòu) 本節(jié)討論子串定位運(yùn)算(也稱模式匹配)在順序串上的實(shí)現(xiàn),及在鏈串上的實(shí)現(xiàn)子串定位運(yùn)算的含意：4.3 串運(yùn)算

34、的實(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中的位置，這種情況稱為匹配成功；否則稱為匹配失敗。8/22/202279數(shù)據(jù)結(jié)構(gòu) 1. 樸素的匹配算法基本思想：初始時(shí)，從S的第一個(gè)字符開(kāi)始將T的第一個(gè)字符與其進(jìn)行比較，若相等，則繼續(xù)逐個(gè)比較后續(xù)字符，如匹配成功，則返回子串在S中的位置，否則，將T向右移動(dòng)一個(gè)字符位置，從T的第一個(gè)字符開(kāi)始與S中第二個(gè)字符進(jìn)行比較，并在相等的情況下逐個(gè)比較后續(xù)字符，進(jìn)行第二趟匹配，成功則返回子串在S

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

36、或匹配成功，或當(dāng)T右移到無(wú)法與S繼續(xù)進(jìn)行比較時(shí)，匹配失敗。 a b a b c a b c a c b a b a b c a c8/22/202281數(shù)據(jù)結(jié)構(gòu) a b a b c a b c a c b a b 設(shè)S=“ababcabcacbab” T=“abcac” a b c a ci=0j=0i=1j=1i=2j=2i指針回溯的位置為：i=i-j+1（i的值為1） 1. 樸素的匹配算法8/22/202282數(shù)據(jù)結(jié)構(gòu) a b a b c a b c a c b a b 設(shè)S=“ababcabcacbab” T=“abcac” a b c a ci=1j=0i指針回溯的位置為：i=i-j+

37、1（i的值為2）8/22/202283數(shù)據(jù)結(jié)構(gòu)設(shè)S=“ababcabcacbab” T=“abcac” a b a b c a b c a c b a b a b c a ci=2j=0i=3j=1i=4j=2i=5j=3i=6j=4i指針回溯的位置為：i=i-j+1（i的值為3）8/22/202284數(shù)據(jù)結(jié)構(gòu) a b a b c a b c a c b a b 設(shè)S=“ababcabcacbab” T=“abcac” a b c a ci=3j=0i指針回溯的位置為：i=i-j+1（i的值為4）8/22/202285數(shù)據(jù)結(jié)構(gòu) a b a b c a b c a c b a b 設(shè)S=“aba

38、bcabcacbab” T=“abcac” a b c a ci=4j=0i指針回溯的位置為：i=i-j+1（i的值為5）8/22/202286數(shù)據(jù)結(jié)構(gòu) a b a b c a b c a c b a b 設(shè)S=“ababcabcacbab” T=“abcac” a b c a ci=5j=0i=6j=1i=7j=2i=8j=3i=9j=4i=10j=5返回子串的位置為：i-j+1=6（串的起始位置從1開(kāi)始算起）8/22/202287數(shù)據(jù)結(jié)構(gòu) int index(s,t) seqstring *s,*t; int i=0,j=0;while (iscurlen)&(jt curlen) if

39、(s chi=t chj i+;j+; else i=i-j+1;j=0; if (j=t curlen) return (i-j+1) else return (-1); 樸素的模式匹配算法描述如下：8/22/202288數(shù)據(jù)結(jié)構(gòu)5.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=a11 a12 a1na21 a22 a2n am1 am2 amn8/22/202289數(shù)據(jù)結(jié)

40、構(gòu)2.三維及多維數(shù)組三維數(shù)組Amnp: 可看成有p個(gè)二維數(shù)組（m*n)所組成的向量每個(gè)元素aijk同屬于三個(gè)向量（二維數(shù)組）最多有3個(gè)直接前趨和直接后繼（除角、邊、面上的結(jié)點(diǎn)）推廣：多維數(shù)組An1n2nm可看成nm個(gè)（m-1）維數(shù)組所構(gòu)成的向量任一元素ai1i2im都屬于m個(gè)向量，最多有m個(gè)直接前趨和m個(gè)直接后繼8/22/202290數(shù)據(jù)結(jié)構(gòu)對(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)算說(shuō)明：對(duì)于數(shù)組，通常只進(jìn)行讀、寫操作，不進(jìn)行元素的插入和刪除操作。因此，一般采用順序存儲(chǔ)結(jié)

41、構(gòu)表示數(shù)組。8/22/202291數(shù)據(jù)結(jié)構(gòu)1、兩種順序存儲(chǔ)方法： (1) 行優(yōu)先順序(row major order) (c,pascal語(yǔ)言采用） 特點(diǎn)：將數(shù)組元素按行向量排列 (以二維數(shù)組為例）(2) 列優(yōu)先順序(column major order) (fortran語(yǔ)言采用） 特點(diǎn)：將數(shù)組元素按列向量排列 (以二維數(shù)組為例）a11 a12 . a1n a21 a22 a2n am1 am2 amn 第1行 第2行 第m行a11 a21 . am1 a12 a22 am2 a1n a2n amn 第1列 第2列 第n列三、順序存儲(chǔ)方法8/22/202292數(shù)據(jù)結(jié)構(gòu)2、特點(diǎn) 順序存儲(chǔ)的數(shù)組

42、是一個(gè)隨機(jī)存取結(jié)構(gòu)，即只要知道開(kāi)始元素的存儲(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ù)開(kāi)始元素的存儲(chǔ)起址n為列數(shù)c語(yǔ)言中因數(shù)組下標(biāo)從0開(kāi)始，因此上面的式子應(yīng)改為： LOC(aij)=LOC(a00)+(i*n+j)*d8/22/202293數(shù)據(jù)結(jié)構(gòu)5.2 矩陣的壓縮存儲(chǔ)壓縮存儲(chǔ): 前提：非零元素呈某種規(guī)律分布或矩陣中有大量零元素 定義：多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間，值為0的 元素不分配空間采用壓縮存儲(chǔ)的矩陣

43、分為兩類：特殊矩陣和稀疏矩陣。 5.2.1 特 殊 矩 陣特殊矩陣：指的是非零元素或零元素的分布有一定規(guī)律的矩陣。對(duì)特殊矩陣常采用一維數(shù)組存儲(chǔ)。需解決的問(wèn)題：如何將二維數(shù)組元素下標(biāo)轉(zhuǎn)換成一維數(shù)組元素下標(biāo)。8/22/202294數(shù)據(jù)結(jié)構(gòu) 1.對(duì)稱矩陣 1）定義: 已知n階方陣A，若其元素滿足如下性質(zhì)： aij=aji 0=i,j=j 則 k=i*(i+1)/2+j b: 若 ij 則 k=j*(j+1)/2+i(這是由對(duì)稱性質(zhì)決定的） 注意：進(jìn)行壓縮存儲(chǔ)后，沒(méi)有改變?cè)捎枚S數(shù)組存儲(chǔ)時(shí)能進(jìn)行隨機(jī)訪問(wèn)的特性。綜合a、b，令I(lǐng)=max(i,j), J=min(i,j)，則k=I*(I+1)/2+Jl

44、oc(aij)=loc(sak)=loc(sa0)+k*d =loc(sa0)+(I*(I+1)/2+J)*da00a10 a11a20 a21 a22 aij a n-1,0 a n-1,1 an-1,2 a n-1,n-18/22/202296數(shù)據(jù)結(jié)構(gòu)2.三角矩陣（方陣） 1）分類：三角矩陣以主對(duì)角線劃分，可分為上三角矩陣和下三角矩陣。a00 c c ca10 a11 c a20 a21 c a n-1,0 a n-1,1 an-1,2 a n-1,n-18/22/202297數(shù)據(jù)結(jié)構(gòu)2.三角矩陣（方陣） 2）存儲(chǔ)方法： 只需存儲(chǔ)非常數(shù)三角中的所有元素，另外再加一個(gè)存儲(chǔ)單元存儲(chǔ)常數(shù)C。 非

45、常數(shù)三角中的所有元素個(gè)數(shù)為n(n+1)/2,外加一個(gè)常數(shù),總共有n(n+1)/2+1個(gè)元素，可用一維數(shù)組sn*(n+1)/2+1存儲(chǔ)，常數(shù)存于最后一個(gè)存儲(chǔ)單元。 1）分類：三角矩陣以主對(duì)角線劃分，可分為上三角矩陣和下三角矩陣。8/22/202298數(shù)據(jù)結(jié)構(gòu)上三角矩陣中aij與sk的對(duì)應(yīng)關(guān)系：下三角矩陣中aij與sk的對(duì)應(yīng)關(guān)系： i*(2n-i+1)/2+j-i ij i*(i+1)/2+j i=j k= n*(n+1)/2 ija00 a01 a0,n-1 c a11 a1,n-1 aii aij c c an-1,n-13)存儲(chǔ)地址的計(jì)算i*n-(i-1) *i /28/22/202299數(shù)

46、據(jù)結(jié)構(gòu)3.對(duì)角矩陣特點(diǎn)：所有的非零元素都集中在以對(duì)角線為中心的帶狀區(qū)域中。帶狀區(qū)域外的所有元素均為零。以三對(duì)角矩陣為例（p75)三對(duì)角矩陣中所有非零元素為3*n-2,可用一維數(shù)組s3*n-2存儲(chǔ).再次強(qiáng)調(diào)：特殊矩陣的壓縮存儲(chǔ)沒(méi)有改變?cè)捎枚S數(shù)組存儲(chǔ)時(shí)所具有的隨機(jī)存取特性。 8/22/2022100數(shù)據(jù)結(jié)構(gòu)5.2.2 稀 疏 矩 陣稀疏矩陣的壓縮存儲(chǔ)通常有兩種方式：三元組表和十字鏈表。稀疏矩陣：非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)少于矩陣元素的總數(shù)的矩陣（sm=3; a-n=5; a-t=4; a- data16 8/22/2022105數(shù)據(jù)結(jié)構(gòu)傳統(tǒng)轉(zhuǎn)置方法介紹基本思想：由于A的列是B的行，因此按a-data的

47、列序轉(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) 0 1 2 1 3 1 2 0 -3 2 3 2 i j vA的三元組表 i j v 0 2 -3 1 0 2 3 1 1 3 2 2 B 的三元組表轉(zhuǎn)置后8/22/2022106數(shù)據(jù)結(jié)構(gòu) 3、十字鏈表1) 十字鏈表中結(jié)點(diǎn)的結(jié)構(gòu)： i j v/next cptr rptr存儲(chǔ)行號(hào)存儲(chǔ)列號(hào)存儲(chǔ)元素值或指向下一個(gè)表頭結(jié)點(diǎn)列指針

48、域，指向本列下一個(gè)非零元素行指針域，指向本行下一個(gè)非零元素4)三元組表的優(yōu)點(diǎn)：結(jié)構(gòu)簡(jiǎn)單，易于實(shí)現(xiàn)，存儲(chǔ)密度高。 缺點(diǎn)：不具有隨機(jī)存儲(chǔ)特性；矩陣中非零元素發(fā)生變化時(shí)，將會(huì)引起三元組表中大量元素的移動(dòng)。8/22/2022107數(shù)據(jù)結(jié)構(gòu)十字鏈表h0 0 0 0 0 0 0 0 0 0 1 2 2 2 4 1 3 1 -3 3 4 2 0 0 0 0 0 0 3 5 H1H1H4H2H3H2H5H3 A= 0 2 0 0 0 0 0 0 1 0 -3 0 0 2 0 i j v/next cptr rptr8/22/2022108數(shù)據(jù)結(jié)構(gòu)2) 十字鏈表存儲(chǔ)結(jié)構(gòu)描述： typedef struct ln

49、ode int i,j; struct lnode *cptr,*rptr; union struct lnode *next; datatype v ; uval; link; 3)建立十字鏈表 i j v/next cptr rptr8/22/2022109數(shù)據(jù)結(jié)構(gòu)建立十字鏈表的算法分為兩步： 1.建立表頭結(jié)點(diǎn)的循環(huán)鏈表 2.依次讀入非零元素的三元組，每讀入一個(gè)三元組，生成一個(gè)表結(jié)點(diǎn)，并將其插入相應(yīng)行、列鏈表中的正確位置上。8/22/2022110數(shù)據(jù)結(jié)構(gòu)5.3 廣義表的概念廣義表(Lists)是n（n=0)個(gè)元素a1,a2,an的有限序列，其中ai或者是原子或者是一個(gè)廣義表，通常記為L(zhǎng)S

50、=(a1,a2,an)1、定義：8/22/2022111數(shù)據(jù)結(jié)構(gòu)補(bǔ)充說(shuō)明：對(duì)于LS=(a1,a2,an)LS:廣義表的名字n: 廣義表的長(zhǎng)度。E=(a,E )如果ai是廣義表， 則稱它為L(zhǎng)S的子表書寫時(shí)，用大寫字母表示廣義表，小寫字母表示原子若LS非空(n=1)，則a1是LS的表頭，（a2,a3,an)構(gòu)成的表稱為L(zhǎng)S的表尾表是遞歸定義的，一個(gè)表的深度定義為表展開(kāi)后所含括號(hào)的層數(shù).D=(A,B,C )如果規(guī)定任何表都是有名字的，為了即表明每個(gè)表的名字，又說(shuō)明它的組成，則可以在每個(gè)表的前面冠以該表的名稱。 D (A( ),B ( b,c,d), C (a, B(b,c,d) ) )； 8/22/

51、2022112數(shù)據(jù)結(jié)構(gòu)2、廣義表的表示方法圖示法：用分支結(jié)點(diǎn)表示廣義表，非分支結(jié)點(diǎn)表示原子。特殊的，空表對(duì)應(yīng)的也是非分支結(jié)點(diǎn)。A=( )AB=( b,c,d)BbcdC=(a,(b,c,d) )bcdBCaD=(A,B,C )DABbcdCaE=(a,E )Ea純表：樹(shù)對(duì)應(yīng)的廣義表，限制了成分的共享與遞歸 A,B,C再入表：允許結(jié)點(diǎn)間共享的表 D 遞歸表：允許遞歸的表 E 8/22/2022113數(shù)據(jù)結(jié)構(gòu)3、廣義表的兩個(gè)特殊的運(yùn)算取表頭head(LS): 任何一個(gè)非空廣義表的表頭是表中第一個(gè)元素。取表尾tail(LS)：據(jù)表尾定義，必定是子表。例: head(B)=btail(B)=(c,d)

52、head(D)=Atail(D)=（B,C)head( )=( )tail( )=( )線性表純表 再入表 遞歸表所以，廣義表不僅是線性表的推廣，還是樹(shù)的推廣8/22/2022114數(shù)據(jù)結(jié)構(gòu)5.3 廣義表的存儲(chǔ)p831、單鏈表示法（模仿單鏈表結(jié)構(gòu)）2、雙鏈表示法（類似于第六章的二叉鏈表）8/22/2022115數(shù)據(jù)結(jié)構(gòu)第六章 樹(shù) 樹(shù)形結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)，在我們的客觀世界和現(xiàn)實(shí)生活中大量存在。 樹(shù)形結(jié)構(gòu)：結(jié)點(diǎn)之間有分支，并且具有層次關(guān)系的結(jié)構(gòu)8/22/2022116數(shù)據(jù)結(jié)構(gòu)6.1 樹(shù)的概念1、樹(shù)的定義：樹(shù)(Tree)是n(n0)個(gè)結(jié)點(diǎn)的有限集合T，它滿足如下條件： (1) 有且僅有一個(gè)稱

53、為根(Root)的結(jié)點(diǎn)。 (2) 其余結(jié)點(diǎn)可分為m(m=0)個(gè)互不相交的有限集合,T1,T2,Tm,其中每個(gè)集合又是一棵樹(shù)，并稱其為根的子樹(shù)（Subtree） 。這是一個(gè)遞歸定義。 有時(shí)n=0也稱為空樹(shù)。ABCDEFG集合1集合2集合3一、樹(shù)的基本概念8/22/2022117數(shù)據(jù)結(jié)構(gòu)2、樹(shù)的表示方法1）樹(shù)形圖法2）嵌套集合法3）廣義表形式4）凹入表示法(A(B),C(E,F),D(G)ABCDEFGABCEFDGABDGEFC8/22/2022118數(shù)據(jù)結(jié)構(gòu)1）結(jié)點(diǎn)的度(Degree)：為該結(jié)點(diǎn)的子樹(shù)的個(gè)數(shù)。2）樹(shù)的度：為該樹(shù)中結(jié)點(diǎn)的最大度數(shù)。3）終端結(jié)點(diǎn)(葉子)：度為零的結(jié)點(diǎn)。4）非終端結(jié)點(diǎn)

54、(分支結(jié)點(diǎn))：度不為零的結(jié)點(diǎn)。5）內(nèi)部結(jié)點(diǎn)：除根結(jié)點(diǎn)之外的分支結(jié)點(diǎn)。ACDEFGB3、 樹(shù)結(jié)構(gòu)的基本術(shù)語(yǔ)8/22/2022119數(shù)據(jù)結(jié)構(gòu)6）孩子(child)：結(jié)點(diǎn)的子樹(shù)之根 雙親（parent):該結(jié)點(diǎn)稱為孩子的雙親 兄弟(sibling):同一雙親的孩子 堂兄弟（cousin):雙親不同但其雙親處于同一層的結(jié)點(diǎn)7）路徑(Path)：若樹(shù)中存在一個(gè)結(jié)點(diǎn)序列k1,k2,kj,使得ki是ki+1的雙親(1=i=0)棵互不相交的樹(shù)的集合稱為森林。關(guān)系：樹(shù)森林刪去一個(gè)樹(shù)根加上一個(gè)樹(shù)根ACDEFGB8/22/2022122數(shù)據(jù)結(jié)構(gòu)6.2 二 叉 樹(shù)6.2.1 二叉樹(shù)的概念一、二叉樹(shù)的定義： 二叉樹(shù)(B

55、inary Tree)是n(n=0)個(gè)結(jié)點(diǎn)的有限集，它或者是空集(n=0)或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的，分別稱為根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。 可以看出，二叉樹(shù)的定義和樹(shù)的定義一樣，均為遞歸定義。8/22/2022123數(shù)據(jù)結(jié)構(gòu)二、二叉樹(shù)的五種基本形態(tài)：空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)右子樹(shù)為空的二叉樹(shù)左子樹(shù)為空的二叉樹(shù)左、右子樹(shù)均非空的二叉樹(shù)注意：二叉樹(shù)中子樹(shù)是有左右之分的，即使只有一棵子樹(shù)，或?yàn)樽笞訕?shù)，或?yàn)橛易訕?shù)，這一點(diǎn)與度為2的有序樹(shù)不同。這不是二叉樹(shù)這是二叉樹(shù)8/22/2022124數(shù)據(jù)結(jié)構(gòu)6.2.2 二叉樹(shù)的性質(zhì)性質(zhì)1：二叉樹(shù)第i層上的結(jié)點(diǎn)數(shù)目最多為2i-1 (i=1)性質(zhì)2：深

56、度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)(k=1)性質(zhì)3：任意二叉樹(shù)中，若葉結(jié)點(diǎn)的個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。8/22/2022125數(shù)據(jù)結(jié)構(gòu)兩種特殊形態(tài)的二叉樹(shù)：滿二叉樹(shù)和完全二叉樹(shù) 深度為k且有2 k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱為滿二叉樹(shù)。 若一棵二叉樹(shù)至多只有最下面的兩層上結(jié)點(diǎn)的度數(shù)可以小于2，并且最下一層上的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹(shù)稱為完全二叉樹(shù)。滿二叉樹(shù)1234567非完全二叉樹(shù)123456完全二叉樹(shù)234518/22/2022126數(shù)據(jù)結(jié)構(gòu)兩種特殊形態(tài)的二叉樹(shù)：滿二叉樹(shù)和完全二叉樹(shù) 深度為k且有2 k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱為滿二叉樹(shù)。 對(duì)滿二叉樹(shù)的結(jié)點(diǎn)

57、進(jìn)行編號(hào)，約定編號(hào)從根結(jié)點(diǎn)起，自上而下，自左至 右。 深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)，則稱之為完全二叉樹(shù)。滿二叉樹(shù)1234567非完全二叉樹(shù)123456完全二叉樹(shù)234518/22/2022127數(shù)據(jù)結(jié)構(gòu)根據(jù)定義:(1)滿二叉樹(shù)是完全二叉樹(shù),反之不成立; (2)對(duì)于完全二叉樹(shù),若某結(jié)點(diǎn)無(wú)左孩子,則必?zé)o右孩子,該結(jié)點(diǎn)為葉結(jié)點(diǎn);性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 log2n +1( log2(n+1) )8/22/2022128數(shù)據(jù)結(jié)構(gòu)性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層次編號(hào)(即自上而下，自左至右)，則對(duì)

58、任一結(jié)點(diǎn)i(1=i1,則其雙親是編號(hào)為 i/2 的結(jié)點(diǎn)。 (2) 如果2*in,則結(jié)點(diǎn)i無(wú)左孩子；否則其左孩子是編號(hào)為2*i的結(jié)點(diǎn)。 (3) 如果2*i+1n,則結(jié)點(diǎn)i無(wú)右孩子；否則其右孩子是編號(hào)為2*i+1的結(jié)點(diǎn)。 (4)若i為奇數(shù)且不為1,則結(jié)點(diǎn)i的左兄弟的編號(hào)是i-1;否則,結(jié)點(diǎn)i無(wú)左兄弟。 (5)若 i為偶數(shù)且小于n,則結(jié)點(diǎn)i的右兄弟的編號(hào)是i+1;否則,結(jié)點(diǎn)i無(wú)右兄弟。234518/22/2022129數(shù)據(jù)結(jié)構(gòu)6.2.3 二叉樹(shù)的存儲(chǔ)1. 順序存儲(chǔ)結(jié)構(gòu)1）對(duì)于完全二叉樹(shù)可以采用順序存儲(chǔ)結(jié)構(gòu)(即一維數(shù)組)進(jìn)行存儲(chǔ)，編號(hào)為i的結(jié)點(diǎn)存放在第i個(gè)數(shù)組元素所分配的存儲(chǔ)單元中，完全二叉樹(shù)結(jié)點(diǎn)之間

59、的邏輯關(guān)系通過(guò)數(shù)組元素的下標(biāo)體現(xiàn)。完全二叉樹(shù)abcde非完全二叉樹(shù)abcdef 0 1 2 3 4 5 a b c d e 下標(biāo)元素 0 1 2 3 4 5 6 7 a b c * d e f 下標(biāo)元素“虛結(jié)點(diǎn)”占據(jù)的空間補(bǔ)設(shè)的“虛結(jié)點(diǎn)”8/22/2022130數(shù)據(jù)結(jié)構(gòu)2）對(duì)于非完全二叉樹(shù)，通過(guò)補(bǔ)設(shè)一些“虛結(jié)點(diǎn)”，使得二叉樹(shù)的結(jié)點(diǎn)的編號(hào)與完全二叉樹(shù)相同，再進(jìn)行順序存儲(chǔ)。每個(gè)“虛結(jié)點(diǎn)”都將占據(jù)一個(gè)數(shù)組元素存儲(chǔ)單元。結(jié)論：非完全二叉樹(shù)采用順序存儲(chǔ)結(jié)構(gòu)會(huì)造成存儲(chǔ)空間的浪費(fèi)。8/22/2022131數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)除了可以采用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)存儲(chǔ)外,還可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ),與采用順序存儲(chǔ)結(jié)構(gòu)相比

60、,采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)二叉樹(shù)的存儲(chǔ)顯得更自然.1）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中結(jié)點(diǎn)的結(jié)構(gòu): lchild data rchild指向左孩子的指針域指向右孩子的指針域存放數(shù)據(jù) 2、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)8/22/2022132數(shù)據(jù)結(jié)構(gòu)2）結(jié)點(diǎn)的存儲(chǔ)描述:typedef struct nodedatatype data; struct node *lchild,*rchild; bitree;bitree *root;所有類型為node的結(jié)點(diǎn)，再加上一個(gè)指向根結(jié)點(diǎn)的頭指針root，就構(gòu)成了二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，稱為二叉鏈表。 lchild data rchild指向左孩子的指針域指向右孩子的指針域存放數(shù)據(jù)8/22/20221