2023年自考數(shù)據(jù)結(jié)構(gòu)重點(diǎn)總結(jié)最終修訂

自考023３１數(shù)據(jù)結(jié)構(gòu)重點(diǎn)總結(jié)(最終修訂)第一章概論1．瑞士計(jì)算機(jī)科學(xué)家沃思提出:算法＋數(shù)據(jù)結(jié)構(gòu)=程序。算法是對(duì)數(shù)據(jù)運(yùn)算的描述,而數(shù)據(jù)結(jié)構(gòu)涉及邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。由此可見(jiàn),程序設(shè)計(jì)的實(shí)質(zhì)是針對(duì)實(shí)際問(wèn)題選擇一種好的數(shù)據(jù)結(jié)構(gòu)和設(shè)計(jì)一個(gè)好的算法,而好的算法在很大限度上取決于描述實(shí)際問(wèn)題的數(shù)據(jù)結(jié)構(gòu)。２.數(shù)據(jù)是信息的載體。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成,數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)記單位。數(shù)據(jù)對(duì)象是具有相同性質(zhì)的數(shù)據(jù)元素的集合。3.數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)元素之間的互相關(guān)系,即數(shù)據(jù)的組織形式。數(shù)據(jù)結(jié)構(gòu)一般涉及以下三方面內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算①數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù),與數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。數(shù)據(jù)的邏輯結(jié)構(gòu)分類:線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性表是一個(gè)典型的線性結(jié)構(gòu)。棧、隊(duì)列、串等都是線性結(jié)構(gòu)。數(shù)組、廣義表、樹(shù)和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。②數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)內(nèi)的存儲(chǔ)方式,稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu)）。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)，它依賴于計(jì)算機(jī)語(yǔ)言。③數(shù)據(jù)的運(yùn)算。最常用的檢索、插入、刪除、更新、排序等。4.數(shù)據(jù)的四種基本存儲(chǔ)方法:順序存儲(chǔ)、鏈接存儲(chǔ)、索引存儲(chǔ)、散列存儲(chǔ)(１）順序存儲(chǔ):通常借助程序設(shè)計(jì)語(yǔ)言的數(shù)組描述。（2)鏈接存儲(chǔ):通常借助于程序語(yǔ)言的指針來(lái)描述。(３）索引存儲(chǔ):索引表由若干索引項(xiàng)組成。關(guān)鍵字是能唯一標(biāo)記一個(gè)元素的一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)的組合。（４）散列存儲(chǔ)：該方法的基本思想是:根據(jù)元素的關(guān)鍵字直接計(jì)算出該元素的存儲(chǔ)地址。５.算法必須滿足５個(gè)準(zhǔn)則:輸入，0個(gè)或多個(gè)數(shù)據(jù)作為輸入；輸出,產(chǎn)生一個(gè)或多個(gè)輸出；有窮性，算法執(zhí)行有限步后結(jié)束;擬定性，每一條指令的含義都明確;可行性,算法是可行的。算法與程序的區(qū)別：程序必須依賴于計(jì)算機(jī)程序語(yǔ)言,而一個(gè)算法可用自然語(yǔ)言、計(jì)算機(jī)程序語(yǔ)言、數(shù)學(xué)語(yǔ)言或約定的符號(hào)語(yǔ)言來(lái)描述。目前常用的描述算法語(yǔ)言有兩類：類Ｐascal和類Ｃ。6.評(píng)價(jià)算法的優(yōu)劣：算法的"對(duì)的性"是一方面要考慮的。此外，重要考慮如下三點(diǎn)：?①執(zhí)行算法所花費(fèi)的時(shí)間,即時(shí)間復(fù)雜性;

②執(zhí)行算法所花費(fèi)的存儲(chǔ)空間,重要是輔助空間，即空間復(fù)雜性；?③算法應(yīng)易于理解、易于編程，易于調(diào)試等,即可讀性和可操作性。以上幾點(diǎn)最重要的是時(shí)間復(fù)雜性,時(shí)間復(fù)雜度常用漸進(jìn)時(shí)間復(fù)雜度表達(dá)。7.算法求解問(wèn)題的輸入量稱為問(wèn)題的規(guī)模,用一個(gè)正整數(shù)n表達(dá)。8.常見(jiàn)的時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列依次為：常數(shù)階0(1)、對(duì)數(shù)階0(lｏg2n)、線性階0(n)、線性對(duì)數(shù)階0(nlog2n)、平方階０(ｎ2)立方階0(ｎ3）、…、k次方階0（nk）、指數(shù)階0(2n)和階乘階０(ｎ!)。9.一個(gè)算法的空間復(fù)雜度Ｓ(n)定義為該算法所花費(fèi)的存儲(chǔ)空間,它是問(wèn)題規(guī)模ｎ的函數(shù),它涉及存儲(chǔ)算法自身所占的存儲(chǔ)空間、算法的輸入輸出數(shù)據(jù)所占的存儲(chǔ)空間和算法在運(yùn)營(yíng)過(guò)程中臨時(shí)占用的存儲(chǔ)空間。第二章線性表1.數(shù)據(jù)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的,而運(yùn)算的具體實(shí)現(xiàn)是在存儲(chǔ)結(jié)構(gòu)上進(jìn)行的。

2.只要擬定了線性表存儲(chǔ)的起始位置，線性表中任意一個(gè)元素都可隨機(jī)存取，所以順序表是一種隨機(jī)存取結(jié)構(gòu)。3．常見(jiàn)的線性表的基本運(yùn)算:(１)置空表InitList(L）構(gòu)造一個(gè)空的線性表L。?（2)求表長(zhǎng)ListLｅnｇtｈ（L)求線性表L中的結(jié)點(diǎn)個(gè)數(shù)，即求表長(zhǎng)。

（３）GｅｔNode(L，i)取線性表L中的第ｉ個(gè)元素。?(4）ＬocａｔｅNｏde(L,ｘ)在L中查找第一個(gè)值為ｘ的元素，并返回該元素在L中的位置。若L中沒(méi)有元素的值為x,則返回0值。

(5)InｓｅrtLｉst（L,i，ｘ）在線性表Ｌ的第i個(gè)元素之前插入一個(gè)值為x的新元素，表L的長(zhǎng)度加１。

（6)DelｅteLｉst（Ｌ，i)刪除線性表L的第i個(gè)元素，刪除后表L的長(zhǎng)度減1。4.順序存儲(chǔ)方法：把線性表的數(shù)據(jù)元素按邏輯順序依次存放在一組地址連續(xù)的存儲(chǔ)單元里的方法。順序表(SequｅntｉaｌＬｉst）:用順序存儲(chǔ)方法存儲(chǔ)的線性表稱為順序表。順序表是一種隨機(jī)存取結(jié)構(gòu),順序表的特點(diǎn)是邏輯上相鄰的結(jié)點(diǎn)其物理位置亦相鄰。順序表中結(jié)點(diǎn)ai的存儲(chǔ)地址:LOC（ai）=LＯC（a1)+（i-1）*c

1≤ｉ≤n，5.順序表上實(shí)現(xiàn)的基本運(yùn)算:（1）插入：該算法的平均時(shí)間復(fù)雜度是O（n）,即在順序表上進(jìn)行插入運(yùn)算，平均要移動(dòng)一半結(jié)點(diǎn)（n/2)。在第i個(gè)位置插入一個(gè)結(jié)點(diǎn)的移動(dòng)次數(shù)為n-i+1(2)刪除:順序表上做刪除運(yùn)算,平均要移動(dòng)表中約一半的結(jié)點(diǎn)（n-1）/２，平均時(shí)間復(fù)雜度也是O(n）。刪除第i個(gè)結(jié)點(diǎn)移動(dòng)次數(shù)為n-ｉ6.采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可以避免頻繁移動(dòng)大量元素。一個(gè)單鏈表可由頭指針唯一擬定，因此單鏈表可以用頭指針的名字來(lái)命名。①生成結(jié)點(diǎn)變量的標(biāo)準(zhǔn)函數(shù)p＝(ListＮode＊)malloｃ(siｚeof(ListＮodｅ));//函數(shù)ｍalloc分派一個(gè)類型為L(zhǎng)ｉstNｏde的結(jié)點(diǎn)變量的空間，并將其首地址放入指針變量p中②釋放結(jié)點(diǎn)變量空間的標(biāo)準(zhǔn)函數(shù)freｅ(ｐ）;/／釋放p所指的結(jié)點(diǎn)變量空間③結(jié)點(diǎn)分量的訪問(wèn)

方法二：ｐ－﹥daｔa和p-﹥next④指針變量p和結(jié)點(diǎn)變量*p的關(guān)系:指針變量p的值——結(jié)點(diǎn)地址,結(jié)點(diǎn)變量*ｐ的值——結(jié)點(diǎn)內(nèi)容7.建立單鏈表:（１）頭插法建表:算法：p=(LiｓtＮode*)mａlloc（sｉzｅof（ListNode));①/／生成新結(jié)點(diǎn)

p－>dａt(yī)a=cｈ;②//將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中

p->ｎexｔ＝heａd;③head=p;④

（２)尾插法建表：算法：p=（ＬiｓｔNodｅ*)maｌloc(ｓizeoｆ(ＬistNode));①//生成新結(jié)點(diǎn)?

p->ｄaｔa=cｈ;

②//將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中

if(hｅaｄ==ＮULL)heａd＝p;//新結(jié)點(diǎn)插入空表

ｅlserear->ｎｅｘt=p;③//將新結(jié)點(diǎn)插到*r之后

rear=p;④/／尾指針指向新表尾(3）尾插法建帶頭結(jié)點(diǎn)的單鏈表：頭結(jié)點(diǎn)及作用：頭結(jié)點(diǎn)是在鏈表的開(kāi)始結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)。它具有兩個(gè)優(yōu)點(diǎn):?

⒈由于開(kāi)始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中,所以在鏈表的第一個(gè)位置上的操作就和在表的其它位置上操作一致,無(wú)須進(jìn)行特殊解決;

⒉無(wú)論鏈表是否為空,其頭指針都是指向頭結(jié)點(diǎn)的非空指針(空表中頭結(jié)點(diǎn)的指針域空）,因此空表和非空表的解決也就統(tǒng)一了。頭結(jié)點(diǎn)數(shù)據(jù)域的陰影表達(dá)該部分不存儲(chǔ)信息。在有的應(yīng)用中可用于存放表長(zhǎng)等附加信息。?具體算法：r＝heaｄ;/／

尾指針初值也指向頭結(jié)點(diǎn)

wｈｉlｅ(（ch=getchar())!=＇\n')｛?

s=(ＬistNｏｄｅ*)malloｃ(ｓizeｏf(ＬistNoｄe））;//生成新結(jié)點(diǎn)

s->data=ch;

／/將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中?

r-＞next=ｓ;

r=s;}?

r->ｎext＝NUＬＬ;/／終端結(jié)點(diǎn)的指針域置空，或空表的頭結(jié)點(diǎn)指針域置空以上三個(gè)算法的時(shí)間復(fù)雜度均為O(ｎ)。８.單鏈表上的查找:（帶頭結(jié)點(diǎn))(1）按結(jié)點(diǎn)序號(hào)查找：序號(hào)為0的是頭結(jié)點(diǎn)。算法：p＝hｅaｄ;j=0;／／從頭結(jié)點(diǎn)開(kāi)始掃描

while（ｐ－>ｎｅｘt&&j<i){//順指針向后掃描,直到p－>nexｔ為NＵLＬ或i=ｊ為止?

p=ｐ-＞next;?

ｊ＋+;｝?

ｉｆ(i==ｊ)reｔurnp;//找到了第ｉ個(gè)結(jié)點(diǎn)?

elseｒｅtｕrnNＵＬL;//當(dāng)ｉ<0或i>0時(shí)，找不到第i個(gè)結(jié)點(diǎn)

時(shí)間復(fù)雜度:在等概率假設(shè)下，平均時(shí)間復(fù)雜度為:為n／２=O（n)(2）按結(jié)點(diǎn)值查找:具體算法：ＬistNoｄｅ＊p=heａd－>ｎext；/／從開(kāi)始結(jié)點(diǎn)比較。表非空，p初始值指向開(kāi)始結(jié)點(diǎn)?

while（p&&p->dａt(yī)ａ！=ｋey）//直到p為NUＬＬ或ｐ-＞ｄａt(yī)a為key為止

p=p-＞ｎeｘt;／/掃描下一結(jié)點(diǎn)?

ｒetｕrｎp;//若p＝ＮUＬＬ,則查找失敗，否則p指向值為key的結(jié)點(diǎn)時(shí)間復(fù)雜度為：O(n）9.插入運(yùn)算:插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上,即插入到ai-1與ａi之間。

?s=（LisｔNodｅ*)malloc（sizeoｆ(LisｔNoｄe)）;②s->datａ=x;③s->nexｔ=p－>neｘt;④p->ｎext=ｓ;⑤算法的時(shí)間重要花費(fèi)在查找結(jié)點(diǎn)上,故時(shí)間復(fù)雜度亦為O（n)。?1０．刪除運(yùn)算

r=p->ｎｅｘt;②/／使r指向被刪除的結(jié)點(diǎn)aip－>nｅxt=r－>next③;//將ai從鏈上摘下frｅe(cuò)（ｒ）；④／/釋放結(jié)點(diǎn)ai的空間給存儲(chǔ)池算法的時(shí)間復(fù)雜度也是O（n).ｐ指向被刪除的前一個(gè)結(jié)點(diǎn)。鏈表上實(shí)現(xiàn)的插入和刪除運(yùn)算,無(wú)須移動(dòng)結(jié)點(diǎn),僅需修改指針。11.單循環(huán)鏈表—在單鏈表中，將終端結(jié)點(diǎn)的指針域NUＬＬ改為指向表頭結(jié)點(diǎn)或開(kāi)始結(jié)點(diǎn)即可。判斷空鏈表的條件是head=＝heaｄ->ｎｅｘt；１2.僅設(shè)尾指針的單循環(huán)鏈表:用尾指針rｅaｒ表達(dá)的單循環(huán)鏈表對(duì)開(kāi)始結(jié)點(diǎn)a1和終端結(jié)點(diǎn)an查找時(shí)間都是O（１)。而表的操作經(jīng)常是在表的首尾位置上進(jìn)行，因此,實(shí)用中多采用尾指針表達(dá)單循環(huán)鏈表。判斷空鏈表的條件為rear=＝rｅａr－>next;1３.循環(huán)鏈表：循環(huán)鏈表的特點(diǎn)是無(wú)須增長(zhǎng)存儲(chǔ)量，僅對(duì)表的鏈接方式稍作改變，即可使得表解決更加方便靈活。若在尾指針表達(dá)的單循環(huán)鏈表上實(shí)現(xiàn)，則只需修改指針，無(wú)須遍歷，其執(zhí)行時(shí)間是Ｏ(1)。具體算法:ＬinｋLｉstＣonｎeｃt(ＬinkLｉstA,LinkLisｔB）

{//假設(shè)A,B為非空循環(huán)鏈表的尾指針LiｎｋListｐ=A-＞nｅxt;／／①保存Ａ表的頭結(jié)點(diǎn)位置

A-＞ｎexｔ=B-＞next－>ｎｅxt；//②B表的開(kāi)始結(jié)點(diǎn)鏈接到A表尾?

ｆrｅｅ(Ｂ－>next）;/／③釋放B表的頭結(jié)點(diǎn)?

B->nｅxｔ=p;／/④?

retｕrnB;//返回新循環(huán)鏈表的尾指針循環(huán)鏈表中沒(méi)有NUＬＬ指針。涉及遍歷操作時(shí)，其終止條件就不再是像非循環(huán)鏈表那樣判別p或p->nｅxt是否為空，而是判別它們是否等于某一指定指針，如頭指針或尾指針等。在單鏈表中，從一已知結(jié)點(diǎn)出發(fā),只能訪問(wèn)到該結(jié)點(diǎn)及其后續(xù)結(jié)點(diǎn)，無(wú)法找到該結(jié)點(diǎn)之前的其它結(jié)點(diǎn)。而在單循環(huán)鏈表中,從任一結(jié)點(diǎn)出發(fā)都可訪問(wèn)到表中所有結(jié)點(diǎn)，這一優(yōu)點(diǎn)使某些運(yùn)算在單循環(huán)鏈表上易于實(shí)現(xiàn)。14.雙向鏈表:雙（向）鏈表中有兩條方向不同的鏈，即每個(gè)結(jié)點(diǎn)中除next域存放后繼結(jié)點(diǎn)地址外，還增長(zhǎng)一個(gè)指向其直接前趨的指針域ｐｒior。①雙鏈表由頭指針hｅａd惟一擬定的。

②帶頭結(jié)點(diǎn)的雙鏈表的某些運(yùn)算變得方便。

③將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來(lái)，為雙(向）循環(huán)鏈表。

15.雙向鏈表的前插和刪除本結(jié)點(diǎn)操作①雙鏈表的前插操作vｏidＤIｎsertBefore(DListＮode＊p,ＤataTｙpex){//在帶頭結(jié)點(diǎn)的雙鏈表中,將值為x的新結(jié)點(diǎn)插入*p之前,設(shè)p≠NULL

DLｉstＮｏde＊s＝mａlloc(sizeof(DLiｓtNode））;／／①?

s-＞ｄａt(yī)a＝x;／／②?

s->prior=ｐ->prior;／/③?

s-＞next＝ｐ;//④

p-＞prior－＞next=s;//⑤

p－>prior=s；//⑥}?②雙鏈表上刪除結(jié)點(diǎn)*p自身的操作?ｖｏidＤDeｌeteNｏde(DLｉstNode*p)?

｛//在帶頭結(jié)點(diǎn)的雙鏈表中，刪除結(jié)點(diǎn)＊p,設(shè)＊p為非終端結(jié)點(diǎn)?

p->ｐｒior->ｎｅxt=p-＞neｘt；/／①?

ｐ－>nｅxt->prior＝ｐ->prior;//②

free（p）;}/／③

與單鏈表上的插入和刪除操作不同的是，在雙鏈表中插入和刪除必須同時(shí)修改兩個(gè)方向上的指針。上述兩個(gè)算法的時(shí)間復(fù)雜度均為Ｏ（1)。順序表和鏈表比較時(shí)間性能：ａ、線性表:經(jīng)常性的查找；b、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：經(jīng)常插入刪除操作;空間性能:a、對(duì)數(shù)據(jù)量大小事先可以知道的用線性表;b、數(shù)據(jù)量變化較大的用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。存儲(chǔ)密度越大,存儲(chǔ)空間的運(yùn)用率越高。顯然,順序表的存儲(chǔ)密度是１，鏈表的存儲(chǔ)密度肯定小于１。第三章棧和隊(duì)列１．棧稱為后進(jìn)先出（LastInＦｉrstOｕｔ）的線性表，簡(jiǎn)稱為ＬIFO表。?棧是運(yùn)算受限的線性表，順序棧也是用數(shù)組表達(dá)的。?進(jìn)棧操作：進(jìn)棧時(shí)，需要將S-＞toｐ加1，①Ｓ-＞top＝=SｔackＳize－1表達(dá)棧滿②"上溢"現(xiàn)象－－當(dāng)棧滿時(shí),再做進(jìn)棧運(yùn)算產(chǎn)生空間溢出的現(xiàn)象。

退棧操作：退棧時(shí),需將S-＞top減１,①S-＞tｏp＜０表達(dá)空棧②"下溢"現(xiàn)象--當(dāng)?？諘r(shí)，做退棧運(yùn)算產(chǎn)生的溢出現(xiàn)象。

下溢是正常現(xiàn)象,常用作程序控制轉(zhuǎn)移的條件?？諚r(shí)棧頂指針不能是0，只能是-1。兩個(gè)棧共享同一存儲(chǔ)空間:當(dāng)程序中同時(shí)使用兩個(gè)棧時(shí)，可以將兩個(gè)棧的棧底分別設(shè)在順序存儲(chǔ)空間的兩端,讓兩個(gè)棧頂各自向中間延伸。當(dāng)一個(gè)棧中的元素較多而棧使用的空間超過(guò)共享空間的一半時(shí)，只要另一個(gè)棧的元素不多，那么前者就可以占用后者的部分存儲(chǔ)空間。當(dāng)Ｔop1=Tｏp2-1時(shí)，棧滿

2．為了克服順序存儲(chǔ)分派固定空間所產(chǎn)生的溢出和空間浪費(fèi)問(wèn)題?？刹捎面?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)棧。鏈棧是沒(méi)有附加頭結(jié)點(diǎn)的運(yùn)算受限的單鏈表。棧頂指針就是鏈表的頭指針。鏈棧中的結(jié)點(diǎn)是動(dòng)態(tài)分派的,所以可以不考慮上溢,無(wú)須定義StaｃkFuｌl運(yùn)算棧的一個(gè)重要應(yīng)用是實(shí)現(xiàn)遞歸,直接調(diào)用自己或間接調(diào)用自己的函數(shù)。３.隊(duì)列(Ｑueｕe）是只允許在一端進(jìn)行插入,而在另一端進(jìn)行刪除的運(yùn)算受限的線性表。允許刪除的一端稱為隊(duì)頭(Fｒont),允許插入的一端稱為隊(duì)尾（Reａr)，當(dāng)隊(duì)列中沒(méi)有元素時(shí)稱為空隊(duì)列,隊(duì)列亦稱作先進(jìn)先出（ＦirsｔInFｉrsｔOut）的線性表，簡(jiǎn)稱為FＩFO表。隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)列,順序隊(duì)列事實(shí)上是一個(gè)受限的線性表。

順序隊(duì)列的基本操作

①入隊(duì)時(shí)：將新元素插入rear所指的位置,然后將rear加1。

②出隊(duì)時(shí)：刪去front所指的元素,然后將frｏnｔ加1并返回被刪元素。當(dāng)頭尾指針相等時(shí)，隊(duì)列為空。

在非空隊(duì)列里，頭指針始終指向隊(duì)頭元素，而隊(duì)尾指針始終指向隊(duì)尾元素的下一位置。而棧頂指針指向棧頂元素。循環(huán)隊(duì)列：為充足運(yùn)用數(shù)組空間，克服上溢，可將數(shù)組空間想象為一個(gè)環(huán)狀空間,并稱這種環(huán)狀數(shù)組表達(dá)的隊(duì)列為循環(huán)隊(duì)列。循環(huán)隊(duì)列中進(jìn)行出隊(duì)、入隊(duì)操作時(shí)，頭尾指針仍要加1,朝前移動(dòng)。只但是當(dāng)頭尾指針指向向量上界(QuｅueSｉzｅ-1)時(shí)，其加1操作的結(jié)果是指向向量的下界0。這種循環(huán)意義下的加１操作可以描述為:①方法一：?

if（ｉ+1＝＝QuｅueＳｉze)i=0;//ｉ表達(dá)froｎt或reaｒ?

elｓｅｉ++;?②方法二-－運(yùn)用"模運(yùn)算＂?

i＝(i＋1)%ＱueuｅＳiｚｅ；循環(huán)隊(duì)列中,由于入隊(duì)時(shí)尾指針向前追趕頭指針;出隊(duì)時(shí)頭指針向前追趕尾指針，導(dǎo)致隊(duì)空和隊(duì)滿時(shí)頭尾指針均相等。因此,無(wú)法通過(guò)條件Q.ｆｒont==Ｑ.reａr來(lái)判別隊(duì)列是"空＂還是"滿"。解決這個(gè)問(wèn)題的方法至少有三種：?①另設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)列是空還是滿；?②設(shè)立一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)(即隊(duì)列長(zhǎng)度)。?③少用一個(gè)元素的空間。約定入隊(duì)前，測(cè)試尾指針在循環(huán)意義下加1后是否等于頭指針,若相等則認(rèn)為隊(duì)列滿即尾指針Q.rear所指的單元始終為空。 ５.循環(huán)隊(duì)列的基本運(yùn)算:①置隊(duì)空:Q－>fronｔ=Q－>rear=0;②判隊(duì)空:returｎQ－＞ｒeａr==Q－>front;③判隊(duì)滿:retｕrｎ(Ｑ->ｒeaｒ+1)%ＱueueＳizｅ==Q->frｏnｔ;④入隊(duì)Q->data[Q->rear］＝x;

//新元素插入隊(duì)尾?Q-＞rｅar＝（Q->reaｒ+1）％QuｅuｅSize；

⑤出隊(duì)ｔｅmp=Q->daｔa[Q-＞ｆrｏnt];?Ｑ－＞front=(Ｑ->fｒont+１)%QueｕeSiｚe;

／/循環(huán)意義下的頭指針加１

returｎtｅmｐ;⑥取隊(duì)頭元素returnQ－>dａｔa［Q－＞froｎt];隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈隊(duì)列。它是限制僅在表頭刪除和表尾插入的單鏈表。為了簡(jiǎn)化解決，在隊(duì)頭結(jié)點(diǎn)之前附加一個(gè)頭結(jié)點(diǎn)，并設(shè)隊(duì)頭指針指向此結(jié)點(diǎn)。鏈隊(duì)列的基本運(yùn)算:(帶頭結(jié)點(diǎn))(1)構(gòu)造空隊(duì):Q->rｅａr＝Q->fｒonｔ;Q－>ｒeａｒ->nｅｘt=ＮUＬL;（2）判隊(duì)空:returnQ－>reａr==Q->front;（３）入隊(duì)：ＱueueNｏde*p=(QueｕeNoｄe*）ｍalloｃ（sizｅof(ＱｕeｕeNode)）;／/申請(qǐng)新結(jié)點(diǎn)

p-＞dａt(yī)a=ｘ;

ｐ->nｅｘｔ=NULＬ;?

Q->ｒeａｒ->next=ｐ；

//＊ｐ鏈到原隊(duì)尾結(jié)點(diǎn)后?

Q->rｅaｒ=p;

／／隊(duì)尾指針指向新的尾（4）出隊(duì)：當(dāng)隊(duì)列長(zhǎng)度大于1時(shí),只需修改頭結(jié)點(diǎn)指針，尾指針不變

s=Q->fｒｏｎt->next；Q->fｒont－＞next=s->nｅxt；x＝s->datａ;fｒee(s);rｅｔuｒnｘ；當(dāng)隊(duì)列長(zhǎng)度等于１時(shí)，不僅要修改頭結(jié)點(diǎn)指針，還要修改尾指針s＝Q－>front-＞neｘt;Q->fｒont－>nｅｘｔ=ＮULＬ;Q－>rear=＝Ｑ－>ｆronｔ；x＝s－>data；frｅe(cuò)（ｓ)；ｒeturnx；（5)取隊(duì)頭元素：returnQ->fｒont->ｎext->data;由于有頭結(jié)點(diǎn)，所以用了ｎeｘｔ①和鏈棧類似,無(wú)須考慮判隊(duì)滿的運(yùn)算及上溢。②在出隊(duì)算法中,一般只需修改隊(duì)頭指針。但當(dāng)原隊(duì)中只有一個(gè)結(jié)點(diǎn)時(shí),該結(jié)點(diǎn)既是隊(duì)頭也是隊(duì)尾，故刪去此結(jié)點(diǎn)時(shí)亦需修改尾指針,且刪去此結(jié)點(diǎn)后隊(duì)列變空。7.用計(jì)算機(jī)來(lái)解決計(jì)算算術(shù)表達(dá)式問(wèn)題,一方面要解決的問(wèn)題是如何將人們習(xí)慣書(shū)寫的中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式。第四章多維數(shù)組和廣義表1.數(shù)組的順序存儲(chǔ)方式:一般采用順序存儲(chǔ)方法表達(dá)數(shù)組。(１)行優(yōu)先順序

ａ11,a1２,…，a1n,a21，a22,…，ａ2n,……，aｍ1,ａm2,…，aｍn（２）列優(yōu)先順序

ａ11,a２1，…,aｍ1，ａ12,a2２,…,am2，……，a1n，a2ｎ,…,aｍｎＰａscal和C語(yǔ)言是按行優(yōu)先順序存儲(chǔ)的,而Forｔｒan語(yǔ)言是按列優(yōu)先順序存儲(chǔ)的。按行優(yōu)先順序存儲(chǔ)的二維數(shù)組Amn地址計(jì)算公式?LＯC（aiｊ)＝LOC(ａ１1）+[(i-1)×n＋j-1]×ｄ（注:此公式下界為1,如下界為０,則公式變?yōu)閇ｉ×n+j])按列優(yōu)先順序存儲(chǔ)的二維數(shù)組Amｎ地址計(jì)算公式

LOＣ(aij）=LOC(a11)+[(j-1)×m＋i-1]×d(注：此公式下界為1，如下界為0，則公式變?yōu)椋踛×ｍ＋ｉ])按行優(yōu)先順序存儲(chǔ)的三維數(shù)組Amｎp地址計(jì)算公式

LOC（aijk)=LＯＣ（a11１)+[(ｉ-1）×n×p+(j－1)×p+k-１]×d(注：此公式下界為1，如下界為0，則公式變?yōu)閇i×n×ｐ+j×p＋k])2.為了節(jié)省存儲(chǔ)空間,可以對(duì)矩陣中有許多值相同或值為零的元素的矩陣，采用壓縮存儲(chǔ)。特殊矩陣是指相同值的元素或零元素在矩陣中的分布有一定的規(guī)律。常見(jiàn)的有對(duì)稱矩陣、三角矩陣。(1)對(duì)稱矩陣在一個(gè)n階方陣A中，若元素滿足下述性質(zhì):

ａij=ａｊi0≤i,j≤n－1稱為n階對(duì)稱矩陣，它的元素是關(guān)于主對(duì)角線對(duì)稱的，所以只需要存儲(chǔ)矩陣上三角或下三角元素即可,讓兩個(gè)對(duì)稱的元素共享一個(gè)存儲(chǔ)空間。矩陣元素aiｊ和數(shù)組元素sa【k】之間的關(guān)系是k=i×(ｉ+１)/2＋ji≥j0≤k<n（ｎ+1)/2-１k=j×(j＋1）/２+ii<ｊ0≤k<n(n+1)／2-1對(duì)稱矩陣的地址計(jì)算公式：LOＣ(ａij）=LOC(ｓa[0])+[I×(I+1）/２+Ｊ]×d，其中Ｉ=ｍax（i,j)，Ｊ＝mｉn（i，j)（2）三角矩陣:以主對(duì)角線劃分,三角矩陣有上三角和下三角兩種。上三角矩陣是指它的下三角(不涉及主角線)中的元素均為常數(shù)c或零;下三角矩陣的主對(duì)角線上方均為常數(shù)ｃ或零。一般情況，三角矩陣的常數(shù)c均為零。三角矩陣的壓縮存儲(chǔ):三角矩陣中的反復(fù)元素ｃ可共享一個(gè)存儲(chǔ)空間，其余的元素正好有n×(ｎ+1)/２個(gè),因此,三角矩陣可壓縮存儲(chǔ)在一維數(shù)組sa[n(ｎ+1)／２+１]中，其中c存放在數(shù)組的最后一個(gè)元素中。①上三角矩陣中ａｉｊ和sa［k]之間的相應(yīng)關(guān)系k=i×(2n-i+１)/2＋j-i當(dāng)i≤ｊk=n×（ｎ＋１)／２當(dāng)i>ｊ②下三角矩陣中aij和sa[k］之間的相應(yīng)關(guān)系k=i×(ｉ+1)/2＋j當(dāng)i≥jk=n×(n+1）/2當(dāng)ｉ<j三角矩陣的壓縮存儲(chǔ)結(jié)構(gòu)是隨機(jī)存取結(jié)構(gòu)。３.稀疏矩陣:設(shè)矩陣Ａmn中有s個(gè)非零元素，若s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)，則稱A為稀疏矩陣。為了節(jié)省存儲(chǔ)單元,可用壓縮存儲(chǔ)方法只存儲(chǔ)非零元素。由于非零元素的分布一般是沒(méi)有規(guī)律的，因此在存儲(chǔ)非零元素的同時(shí),還必須存儲(chǔ)非零元素所在的行、列位置,所以可用三元組(i,j，aij)來(lái)擬定非零元素。稀疏矩陣進(jìn)行壓縮存儲(chǔ)通常有兩類方法：順序存儲(chǔ)(三元組表)和鏈?zhǔn)酱鎯?chǔ)(十字鏈表)。稀疏矩陣的壓縮存儲(chǔ)會(huì)失去隨機(jī)存取功能。4．廣義表是線性表的推廣,又稱列表。廣義表是n(n≥0)個(gè)元素ａ1,a2,…,ai,…,ａn的有限序列。其中ａi或者是原子或者是一個(gè)廣義表。

①?gòu)V義表通常用圓括號(hào)括起來(lái)，用逗號(hào)分隔其中的元素。?

②為了區(qū)分原子和廣義表，書(shū)寫時(shí)用大寫字母表達(dá)廣義表,用小寫字母表達(dá)原子。

③若廣義表Ｌｓ非空(ｎ≥１)，則aｌ是LS的表頭，其余元素組成的表(a1，a2，…，an)稱為L(zhǎng)s的表尾。?

④廣義表具有遞歸和共享的性質(zhì)廣義表的深度：一個(gè)表展開(kāi)后所含括號(hào)的層數(shù)稱為廣義表的深度。１9.廣義表是一種多層次的線性結(jié)構(gòu),事實(shí)上這就是一種樹(shù)形結(jié)構(gòu)。廣義表的兩個(gè)特殊的基本運(yùn)算:取表頭ｈeaｄ(Ls)和取表尾tail（Ls).任何一個(gè)非空廣義表的表頭可以是原子，也可以是子表,而其表尾必然是子表。?

head＝(a，b)=a，tａil(a，b)=（b)

對(duì)非空表Ａ和（y),也可繼續(xù)分解。

注意:廣義表(）和((）)不同。前者是長(zhǎng)度為０的空表,對(duì)其不能做求表頭和表尾的運(yùn)算;而后者是長(zhǎng)度為l的由空表作元素的廣義表,可以分解得到的表頭和表尾均是空表()。廣義表是一種有層次的非線性結(jié)構(gòu),通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),每個(gè)元素用一個(gè)結(jié)點(diǎn)表達(dá)，結(jié)點(diǎn)由3個(gè)域構(gòu)成,其中一個(gè)是tag標(biāo)志位,用來(lái)區(qū)分結(jié)點(diǎn)是原子還是子表，當(dāng)tａｇ為零時(shí)結(jié)點(diǎn)是子表，第二個(gè)域?yàn)閟lｉnk,用以存放子表的地址；當(dāng)tａg為1時(shí)結(jié)點(diǎn)是原子，第二個(gè)域?yàn)椋鋋tａ，用以存放元素值。第五章樹(shù)和二叉樹(shù)1.樹(shù)的表達(dá)法:最常用的是樹(shù)形圖表達(dá)法;尚有3種嵌套集合、凹形、廣義表。樹(shù)結(jié)構(gòu)的基本術(shù)語(yǔ)

（1)結(jié)點(diǎn)的度(Degreｅ)

樹(shù)中的一個(gè)結(jié)點(diǎn)擁有的子樹(shù)數(shù)稱為該結(jié)點(diǎn)的度(Dｅgｒｅe(cuò)）。一棵樹(shù)的度是指該樹(shù)中結(jié)點(diǎn)的最大度數(shù)。?

度為零的結(jié)點(diǎn)稱為葉子（Leaf)或終端結(jié)點(diǎn)。度不為零的結(jié)點(diǎn)稱分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)。?

除根結(jié)點(diǎn)之外的分支結(jié)點(diǎn)統(tǒng)稱為內(nèi)部結(jié)點(diǎn)。根結(jié)點(diǎn)又稱為開(kāi)始結(jié)點(diǎn)。?（２)①途徑（ｐatｈ）若樹(shù)中存在一個(gè)結(jié)點(diǎn)序列ｋ1，ｋ２，…,kｉ,使得ｋｉ是ki+１的雙親（１≤i<j），則稱該結(jié)點(diǎn)序列是從kl到kj的一條途徑(Path)。?一個(gè)結(jié)點(diǎn)的祖先是從根結(jié)點(diǎn)到該結(jié)點(diǎn)途徑上所通過(guò)的所有結(jié)點(diǎn)，而一個(gè)結(jié)點(diǎn)的子孫則是以該結(jié)點(diǎn)為根的子樹(shù)中的所有結(jié)點(diǎn)。

結(jié)點(diǎn)的層數(shù)（Leｖel)從根起算：根的層數(shù)為1,其余結(jié)點(diǎn)的層數(shù)等于其雙親結(jié)點(diǎn)的層數(shù)加１。?

雙親在同一層的結(jié)點(diǎn)互為堂兄弟。

樹(shù)中結(jié)點(diǎn)的最大層數(shù)稱為樹(shù)的高度(Ｈeigｈt)或深度(Depth)。

若將樹(shù)中每個(gè)結(jié)點(diǎn)的各子樹(shù)當(dāng)作是從左到右有順序的（即不能互換）,則稱該樹(shù)為有序樹(shù)（ＯrdeｒeｄTreｅ)；否則稱為無(wú)序樹(shù)（UnoｄeredTreｅ)。若不特別指明,一般討論的樹(shù)都是有序樹(shù)。

森林(Forｅst)是ｍ（m≥0)棵互不相交的樹(shù)的集合。樹(shù)和森林的概念相近。刪去一棵樹(shù)的根,就得到一個(gè)森林;反之，加上一個(gè)結(jié)點(diǎn)作樹(shù)根,森林就變?yōu)橐豢脴?shù)。３.二叉樹(shù)與度數(shù)為2的有序樹(shù)不同：在有序樹(shù)中,雖然一個(gè)結(jié)點(diǎn)的孩子之間是有左右順序的，但是若該結(jié)點(diǎn)只有一個(gè)孩子,就無(wú)須區(qū)分其左右順序。而在二叉樹(shù)中,即使是一個(gè)孩子也有左右之分。二叉樹(shù)的性質(zhì)：性質(zhì)1二叉樹(shù)第i層上的結(jié)點(diǎn)數(shù)目最多為2i-１(i≥1)。例如5層的二叉樹(shù),第５層上的結(jié)點(diǎn)數(shù)目最多為24=16性質(zhì)2深度為k的二叉樹(shù)至多有２ｋ－1個(gè)結(jié)點(diǎn)（k≥1)。例如深度為5的二叉樹(shù)，至多有25-1=31個(gè)結(jié)點(diǎn)性質(zhì)３在任意－棵二叉樹(shù)中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n２，則nｏ=n２+1。例如一棵深度為4的二叉樹(shù)（a），其終端結(jié)點(diǎn)數(shù)n0為８,度為2的結(jié)點(diǎn)樹(shù)為７,則８=7+1,ｎo=ｎ2+1成立(ｂ)其終端結(jié)點(diǎn)數(shù)ｎ0為6,度為2的結(jié)點(diǎn)樹(shù)為５，則６＝５+1，no=n２+1成立滿二叉樹(shù)：一棵深度為k且有２k－1個(gè)結(jié)點(diǎn)的二又樹(shù)稱為滿二叉樹(shù)。滿二叉樹(shù)的特點(diǎn):（1）每一層上的結(jié)點(diǎn)數(shù)都達(dá)成最大值。即對(duì)給定的高度,它是具有最多結(jié)點(diǎn)數(shù)的二叉樹(shù)。（2)滿二叉樹(shù)中不存在度數(shù)為1的結(jié)點(diǎn),每個(gè)分支結(jié)點(diǎn)均有兩棵高度相同的子樹(shù),且樹(shù)葉都在最下一層上。完全二叉樹(shù):若一棵深度為k的二叉樹(shù),其前ｋ-1層是一棵滿二叉樹(shù),而最下面一層上的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹(shù)稱為完全二叉樹(shù)。特點(diǎn):

(1）滿二叉樹(shù)是完全二叉樹(shù),完全二叉樹(shù)不一定是滿二叉樹(shù)。

（2)在滿二叉樹(shù)的最下一層上，從最右邊開(kāi)始連續(xù)刪去若干結(jié)點(diǎn)后得到的二叉樹(shù)仍然是一棵完全二叉樹(shù)。?

（3)在完全二叉樹(shù)中,若某個(gè)結(jié)點(diǎn)沒(méi)有左孩子,則它一定沒(méi)有右孩子,即該結(jié)點(diǎn)必是葉結(jié)點(diǎn)。性質(zhì)4

具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為。?lｏｇｎ?＋1或?ｌｏg(ｎ+1）?例，具有1００個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為:?lg10０?+1=7,26＝6４27=１２8所以?lｇ1００?=6 ,?lg(１00＋1)?=７?4.完全二叉樹(shù)的編號(hào)特點(diǎn)：完全二叉樹(shù)中除最下面一層外,各層都充滿了結(jié)點(diǎn)。每一層的結(jié)點(diǎn)個(gè)數(shù)恰好是上一層結(jié)點(diǎn)個(gè)數(shù)的2倍。從一個(gè)結(jié)點(diǎn)的編號(hào)就可推得其雙親,左、右孩子等結(jié)點(diǎn)的編號(hào)。編號(hào)從0開(kāi)始①若i=0，則qｉ為根結(jié)點(diǎn),無(wú)雙親;否則,ｑi的雙親編號(hào)為?（i-1）／2?。②若２i+1<n，則qｉ的左孩子的編號(hào)是2i＋1;否則,ｑｉ無(wú)左孩子,即ｑi必然是葉子。③若2i+2<n，則ｑｉ的右孩子的編號(hào)是2i+２;否則,ｑi無(wú)右孩子。對(duì)于完全二叉樹(shù)而言，使用順序存儲(chǔ)結(jié)構(gòu)既簡(jiǎn)樸又節(jié)省存儲(chǔ)空間。但對(duì)于一般二叉樹(shù)來(lái)說(shuō)，采用順序存儲(chǔ)時(shí),為了使用結(jié)點(diǎn)在數(shù)組中的相對(duì)位置來(lái)表達(dá)結(jié)點(diǎn)之間的邏輯關(guān)系，就必須增長(zhǎng)一些虛結(jié)點(diǎn)使其成為完全二叉樹(shù)的形式。5.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):二叉樹(shù)的每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子。用鏈接方式存儲(chǔ)二叉樹(shù)時(shí)，每個(gè)結(jié)點(diǎn)除了存儲(chǔ)結(jié)點(diǎn)自身的數(shù)據(jù)外，還應(yīng)設(shè)立兩個(gè)指針域lchilｄ和rｃｈilｄ,分別指向該結(jié)點(diǎn)的左孩子和右孩子。結(jié)點(diǎn)的結(jié)構(gòu)為：二叉鏈表是一種常用的二叉樹(shù)存儲(chǔ)結(jié)構(gòu)。建立二叉鏈表方法：ａ、按廣義表方法，靠近左括號(hào)的結(jié)點(diǎn)是在左子樹(shù)上,而逗號(hào)右邊結(jié)點(diǎn)是在右子樹(shù)上。b、按完全二叉樹(shù)的層次順序建立結(jié)點(diǎn)。具有ｎ個(gè)結(jié)點(diǎn)的二叉鏈表中,共有2ｎ個(gè)指針域。其中有n-1個(gè)用來(lái)指示結(jié)點(diǎn)的左、右孩子,其余的ｎ+1個(gè)為空。二叉樹(shù)遍歷算法中的遞歸終止條件是二叉樹(shù)為空。中序遍歷的遞歸算法定義：(1）遍歷左子樹(shù)；(2)訪問(wèn)根結(jié)點(diǎn)；(3)遍歷右子樹(shù)。先序遍歷的遞歸算法定義:(1)訪問(wèn)根結(jié)點(diǎn);(２）遍歷左子樹(shù);（3）遍歷右子樹(shù)。后序遍歷得遞歸算法定義：（１)遍歷左子樹(shù)；(2）遍歷右子樹(shù)；(3)訪問(wèn)根結(jié)點(diǎn)。遞歸工作棧中涉及兩項(xiàng)：一項(xiàng)是遞歸調(diào)用的語(yǔ)句編號(hào),另一項(xiàng)則是指向根結(jié)點(diǎn)的指針。已知一棵二叉樹(shù)的前序和中序遍歷序列或中序和后序遍歷序列,可唯一擬定一棵二叉樹(shù)。具體方法如下：一方面根據(jù)前序或后序遍歷序列擬定二叉樹(shù)的各子樹(shù)的的根,然后根據(jù)中序遍歷序列擬定各子樹(shù)根的左右子樹(shù)。6.線索二叉樹(shù)：ｎ個(gè)結(jié)點(diǎn)的二叉鏈表必然存在ｎ+1個(gè)空指針域，可以運(yùn)用這些空指針域,存放指向結(jié)點(diǎn)在某種遍歷順序下的前趨和后繼結(jié)點(diǎn)的指針，這種指向前驅(qū)和后繼結(jié)點(diǎn)的指針?lè)Q為＂線索＂，這種加上線索的二叉鏈表稱為線索鏈表,相應(yīng)的二叉樹(shù)稱為線索二叉樹(shù)(Threaded

BinaｒyＴｒｅｅ）。線索鏈表的結(jié)點(diǎn)結(jié)構(gòu):其中:ｌｔag和ｒtag是增長(zhǎng)的兩個(gè)標(biāo)志域,用來(lái)區(qū)分結(jié)點(diǎn)的左、右指針域是指向其左、右孩子的指針，還是指向其前趨或后繼的線索。

?

??

圖中的實(shí)線表達(dá)指針,虛線表達(dá)線索。線索二叉樹(shù)中,一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)的充要條件為:左、右標(biāo)志均是1。7．二叉樹(shù)的線索化:把對(duì)一棵二叉線索鏈表結(jié)構(gòu)中所有結(jié)點(diǎn)的空指針域按照某種遍歷順序加線索的過(guò)程稱為線索化。和中序遍歷算法同樣,遞歸過(guò)程中對(duì)每結(jié)點(diǎn)僅做一次訪問(wèn)。因此對(duì)于n個(gè)結(jié)點(diǎn)的二叉樹(shù)，線索化的算法時(shí)間復(fù)雜度為O(ｎ)。8．樹(shù)、森林到二叉樹(shù)的轉(zhuǎn)換：樹(shù)中每個(gè)結(jié)點(diǎn)最多只有一個(gè)最左邊的孩子（長(zhǎng)子)和一個(gè)右鄰的兄弟。將樹(shù)轉(zhuǎn)換成二叉樹(shù)：①在所有兄弟結(jié)點(diǎn)之間加一道連線;②對(duì)每個(gè)結(jié)點(diǎn),除了保存與其長(zhǎng)子的連線外,去掉該結(jié)點(diǎn)與其它孩子的連線。由于樹(shù)根沒(méi)有兄弟,故樹(shù)轉(zhuǎn)化為二叉樹(shù)后，二叉樹(shù)的根結(jié)點(diǎn)的右子樹(shù)必為空。將一個(gè)森林轉(zhuǎn)換為二叉樹(shù):將森林中的每棵樹(shù)轉(zhuǎn)化成二叉樹(shù),然后再將二叉樹(shù)的根節(jié)點(diǎn)看做兄弟連在一起，形成一棵二叉樹(shù)

9．二叉樹(shù)到樹(shù)、森林的轉(zhuǎn)換：方式是:若二叉樹(shù)中結(jié)點(diǎn)ｘ是雙親y的左孩子，則把ｘ的右孩子,右孩子的右孩子,…,都與ｙ用連線連起來(lái),最后去掉所有雙親到右孩子的連線。１0.樹(shù)的存儲(chǔ)結(jié)構(gòu)：1.雙親表達(dá)法:雙親鏈表表達(dá)法運(yùn)用樹(shù)中每個(gè)結(jié)點(diǎn)的雙親唯一性，在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，為每個(gè)結(jié)點(diǎn)附設(shè)一個(gè)指向其雙親的指針parenｔ，惟一地表達(dá)任何-棵樹(shù)。(１)雙親鏈表表達(dá)法的實(shí)現(xiàn)分析:E和F所在結(jié)點(diǎn)的雙親域是１，它們的雙親結(jié)點(diǎn)在向量中的位置是1，即B是它們的雙親。?

注意:①根無(wú)雙親，其ｐａrent域?yàn)椋薄?/p>

②雙親鏈表表達(dá)法中指針paｒｅnt向上鏈接，適合求指定結(jié)點(diǎn)的雙親或祖先(涉及根）;求指定結(jié)點(diǎn)的孩子或其它后代時(shí)，也許要遍歷整個(gè)數(shù)組。2．孩子鏈表法:孩子鏈表表達(dá)法是為樹(shù)中每個(gè)結(jié)點(diǎn)設(shè)立一個(gè)孩子鏈表，并將這些結(jié)點(diǎn)及相應(yīng)的孩子鏈表的頭指針存放在一個(gè)向量中。注意:①孩子結(jié)點(diǎn)的數(shù)據(jù)域僅存放了它們?cè)谙蛄靠臻g的序號(hào)。?

②與雙親鏈表表達(dá)法相反,孩子鏈表表達(dá)便于實(shí)現(xiàn)涉及孩子及其子孫的運(yùn)算，但不便于實(shí)現(xiàn)與雙親有關(guān)的運(yùn)算。

③將雙親鏈表表達(dá)法和孩子鏈表表達(dá)法結(jié)合起來(lái),可形成雙親孩子鏈表表達(dá)法。3.孩子兄弟表達(dá)法：在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí),附加兩個(gè)分別指向該結(jié)點(diǎn)最左孩子和右鄰兄弟的指針域，即可得樹(shù)的孩子兄弟鏈表表達(dá)。注意：?

這種存儲(chǔ)結(jié)構(gòu)的最大優(yōu)點(diǎn)是：它和二叉樹(shù)的二叉鏈表表達(dá)完全同樣。可運(yùn)用二叉樹(shù)的算法來(lái)實(shí)現(xiàn)對(duì)樹(shù)的操作。

１１.樹(shù)的遍歷：一般都只給出兩種順序遍歷樹(shù)的方法:前序(先根順序)遍歷和后序(后根順序)遍歷。①前序遍歷一棵樹(shù)等價(jià)于前序遍歷該樹(shù)相應(yīng)的二叉樹(shù)

②后序遍歷一棵樹(shù)等價(jià)于中序遍歷該樹(shù)相應(yīng)的二叉樹(shù)。

對(duì)下面(a）圖中所示的森林進(jìn)行前序遍歷和后序遍歷，則得到該森林的前序序列和后序序列分別為ABＣＤEFIGJH和ＢDCAIFJGHＥ。而(b)圖所示二叉樹(shù)的前序序列和中序序列也分別為ABCDEFIGJH和BＤCＡIFJGＨE。前序遍歷森林等同于前序遍歷該森林相應(yīng)的二叉樹(shù)后序遍歷森林等同于中序遍歷該森林相應(yīng)的二叉樹(shù)12.從根結(jié)點(diǎn)到某結(jié)點(diǎn)之間的途徑長(zhǎng)度與該結(jié)點(diǎn)上權(quán)的乘積稱為該結(jié)點(diǎn)的帶權(quán)途徑長(zhǎng)度,樹(shù)種所有葉子結(jié)點(diǎn)的帶權(quán)途徑長(zhǎng)度之和稱為樹(shù)的帶權(quán)途徑長(zhǎng)度。帶權(quán)途徑長(zhǎng)度WPL最小的二叉樹(shù)稱為哈夫曼樹(shù)或最優(yōu)二叉樹(shù)。哈夫曼樹(shù)不一定是二叉樹(shù)。哈夫曼樹(shù)又稱為最優(yōu)樹(shù),是一類帶權(quán)途徑長(zhǎng)度最短的樹(shù)。完全二叉樹(shù)就是這種途徑長(zhǎng)度最短的二叉樹(shù)。①只有葉結(jié)點(diǎn)上的權(quán)值均相同時(shí),完全二叉樹(shù)一定是最優(yōu)二叉樹(shù),否則完全二叉樹(shù)不一定是最優(yōu)二叉樹(shù)。

②最優(yōu)二叉樹(shù)中,權(quán)越大的葉子離根越近。③最優(yōu)二叉樹(shù)的形態(tài)不唯一，WＰL最小。１３.哈夫曼算法:基本思想是：(1）根據(jù)給定的n個(gè)權(quán)值wl,w２，…,wn構(gòu)成n棵二叉樹(shù)的森林F=｛Ｔ1,T2,…,Tn}，其中每棵二叉樹(shù)Ｔi中都只有一個(gè)權(quán)值為wi的根結(jié)點(diǎn),其左右子樹(shù)均空。

(２)在森林F中選出兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)(當(dāng)這樣的樹(shù)不止兩棵樹(shù)時(shí)，可以從中任選兩棵),將這兩棵樹(shù)合并成一棵新樹(shù),為了保證新樹(shù)仍是二叉樹(shù),需要增長(zhǎng)一個(gè)新結(jié)點(diǎn)作為新樹(shù)的根，并將所選的兩棵樹(shù)的根分別作為新根的左右孩子(誰(shuí)左,誰(shuí)右無(wú)關(guān)緊要）,將這兩個(gè)孩子的權(quán)值之和作為新樹(shù)根的權(quán)值。

(3)對(duì)新的森林F反復(fù)(2)，直到森林F中只剩下一棵樹(shù)為止。這棵樹(shù)便是哈夫曼樹(shù)。

注意:①初始森林中的n棵二叉樹(shù),每棵樹(shù)有一個(gè)孤立的結(jié)點(diǎn)，它們既是根,又是葉子?

②ｎ個(gè)葉子的哈夫曼樹(shù)要通過(guò)n-1次合并,產(chǎn)生n－1個(gè)新結(jié)點(diǎn)。最終求得的哈夫曼樹(shù)中共有2ｎ-1個(gè)結(jié)點(diǎn)。?

③哈夫曼樹(shù)是嚴(yán)格的二叉樹(shù)，沒(méi)有度數(shù)為1的分支結(jié)點(diǎn)。1４.哈夫曼編碼:數(shù)據(jù)壓縮過(guò)程稱為編碼，反之,解壓縮的過(guò)程稱為解碼。設(shè)計(jì)一種長(zhǎng)短不等的編碼，則必須保證任一字符的編碼都不是另一個(gè)字符編碼的前綴,這種編碼稱為前綴編碼?？梢赃\(yùn)用二叉樹(shù)來(lái)設(shè)計(jì)二進(jìn)制的前綴編碼，其左分支表達(dá)字符0,右分支表達(dá)字符1，則以根結(jié)點(diǎn)到葉結(jié)點(diǎn)途徑上的分支字符組成的串作為該葉節(jié)點(diǎn)的字符編碼。因此設(shè)計(jì)電文總長(zhǎng)最短的二進(jìn)制前綴編碼,就是以ｎ種字符出現(xiàn)的頻率作為權(quán)構(gòu)造一棵哈夫曼樹(shù),由哈夫曼樹(shù)求得的編碼就是哈夫曼編碼。譯碼過(guò)程是從樹(shù)根結(jié)點(diǎn)出發(fā),逐個(gè)讀入電文中的二進(jìn)制碼。第六章圖1.圖G由兩個(gè)集合構(gòu)成，頂點(diǎn)集合和邊集合,也可以圖G只有頂點(diǎn)而沒(méi)有邊。用尖括號(hào)表達(dá)圖的有向邊＜vi,vj>,有向邊又稱為弧,起點(diǎn)稱為弧尾,終點(diǎn)稱為弧頭。無(wú)向圖的頂點(diǎn)對(duì)用圓括號(hào)表達(dá)（vｉ，vｊ)。在無(wú)向圖中，稱ｖi和vｊ相鄰接，在有向圖中稱頂點(diǎn)vi鄰接到vj，頂點(diǎn)vｊ鄰接于vi在無(wú)向圖中,n的取值范圍是0－n(n-１)/2，將具有n(n－1）/2條邊的無(wú)向圖稱為無(wú)向完全圖。在有向圖中,n的取值范圍是0-n(n-1)，將具有n(n-1)條邊的有向圖稱為有向完全圖。無(wú)向圖中,頂點(diǎn)的度定義為以該頂點(diǎn)為一個(gè)端點(diǎn)的邊的數(shù)目，有向圖的度等于出度和入度之和。在無(wú)向圖中,任意兩頂點(diǎn)都有途徑,則稱兩頂點(diǎn)連通。若圖G中的任意兩個(gè)頂點(diǎn)都連通，稱Ｇ為連通圖。無(wú)向圖的極大連通子圖稱為連通分量，顯然，任何連通圖的連通分量只有一個(gè),即其自身，而非連通的無(wú)向圖有多個(gè)連通分量。在有向圖中,圖G中任意兩頂點(diǎn)連通，稱為強(qiáng)連通圖，極大連通子圖稱為強(qiáng)連通分量。若在一個(gè)圖的每條邊上標(biāo)上某種數(shù)值，該數(shù)值稱為該邊的權(quán)。邊上帶權(quán)的圖稱為帶權(quán)圖,帶權(quán)的連通圖稱為網(wǎng)絡(luò)。2.圖的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣和鄰接表表達(dá)法。圖的頂點(diǎn)編號(hào)從0開(kāi)始。鄰接矩陣表達(dá)法：<vi,vj>或（vi,vj)是邊，則值為1，不是邊則值為０。無(wú)向圖的鄰接矩陣是按主對(duì)角線對(duì)稱的。若G是帶權(quán)圖，只要把1換成相應(yīng)邊上的權(quán)值即可,０的位置上可以不動(dòng)或?qū)⑵鋼Q成無(wú)窮大表達(dá)。無(wú)向圖的鄰接矩陣表達(dá)法可以僅存儲(chǔ)主對(duì)角線以下的元素,時(shí)間復(fù)雜度為Ｏ(n2）鄰接表表達(dá)法:鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。將無(wú)向圖的鄰接表稱為邊表,將有向圖的鄰接表稱為出邊表，將鄰接表的表頭向量稱為頂點(diǎn)表。若無(wú)向圖有n個(gè)頂點(diǎn)和e條邊，則它的鄰接表共有n個(gè)頭結(jié)點(diǎn)和２e個(gè)表結(jié)點(diǎn)。建立鄰接表的時(shí)間復(fù)雜度是Ｏ(ｎ+e）。圖的鄰接表表達(dá)不是唯一的,這是由于在每個(gè)頂點(diǎn)的鄰接表中,各邊結(jié)點(diǎn)的鏈接順序可以是任意的,其具體鏈接順序與邊的輸入順序和生成算法有關(guān)。3．圖的遍歷:遍歷圖的算法是求解圖的連通性、圖的拓?fù)渑判虻人惴ǖ幕A(chǔ)。圖的遍歷常用的是深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷兩種方法。深度優(yōu)先搜索遍歷(DFS)類似于前序(先根)遍歷。按訪問(wèn)頂點(diǎn)的先后順序得到的頂點(diǎn)序列稱為圖的深度優(yōu)先遍歷序列,或簡(jiǎn)稱為DFＳ序列。共需要搜索n2個(gè)矩陣元素，時(shí)間復(fù)雜度為鄰接矩陣O(n2)或鄰接表O(ｎ＋e）。廣度優(yōu)先搜索遍歷(ＢＦS)類似于樹(shù)的按層次遍歷,先被訪問(wèn)的頂點(diǎn),其鄰接點(diǎn)也先被訪問(wèn)，就是先進(jìn)先出。時(shí)間復(fù)雜度為鄰接矩陣O(n2）或鄰接表Ｏ（n+e)，空間復(fù)雜度都是O(n）。4．生成樹(shù)是連通圖的包含圖中所有頂點(diǎn)的一個(gè)極小連通子圖，一個(gè)圖的極小連通子圖恰為一個(gè)無(wú)回路的連通圖，也就是說(shuō)，若圖中任意添加一條邊，就會(huì)出現(xiàn)回路，若去掉任意一條邊，都會(huì)使之成為非連通圖。因此,一個(gè)具有n個(gè)頂點(diǎn)的生成樹(shù)有且僅有n-1條邊,但有n-1條邊的圖不一定是生成樹(shù)，同一個(gè)圖可以有不同的生成樹(shù)。生成樹(shù)定義為：若從圖的某頂點(diǎn)出發(fā)，可以系統(tǒng)的訪問(wèn)到圖的所有頂點(diǎn)，則遍歷時(shí)通過(guò)的邊和圖的所有頂點(diǎn)所構(gòu)成的子圖,稱為該圖的生成樹(shù)。最小生成樹(shù)：圖的生成樹(shù)不唯一，把權(quán)值最小的生成樹(shù)稱為最小生成樹(shù)(MST）。構(gòu)造最小生成樹(shù)的算法：普里姆Prim算法的時(shí)間復(fù)雜度為O(ｎ２）與網(wǎng)中邊數(shù)無(wú)關(guān)適于稠密圖?？唆斔箍枺藃uskal算法的時(shí)間復(fù)雜度為Ｏ（elogｅ),重要取決于邊數(shù),較適合于稀疏圖。5.最短途徑：Dｉｊｋｓtrａ迪杰斯特拉算法，提出了按途徑長(zhǎng)度遞增的順序產(chǎn)生諸頂點(diǎn)的最短途徑算法。拓?fù)渑判?子工程稱為活動(dòng),頂點(diǎn)代表活動(dòng)，有向邊代表活動(dòng)的先后關(guān)系。這樣的有向無(wú)環(huán)圖DAG稱為頂點(diǎn)活動(dòng)網(wǎng),簡(jiǎn)稱為AＯＶ網(wǎng)。將有向無(wú)環(huán)圖G中所有頂點(diǎn)排成一個(gè)線性序列,若<ｕ，ｖ＞∈E（Ｇ）,則在線性序列u在ｖ之前,這種線性序列稱為拓?fù)湫蛄?。由AOＶ網(wǎng)構(gòu)造拓?fù)湫蛄械倪^(guò)程稱為拓?fù)渑判?。檢測(cè)的方法是:對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)湫蛄校艟W(wǎng)中所有頂點(diǎn)都在他的拓?fù)湫蛄兄?則ＡOV網(wǎng)必然不存在環(huán)。ＡOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏摹Ｍ負(fù)渑判虻拿枋鏊枷?a、在有向圖中選一個(gè)沒(méi)有前趨(入度為零)的頂點(diǎn),且輸出之。ｂ、從有向圖中刪除該頂點(diǎn)及其與該頂點(diǎn)有關(guān)的所有邊。c、反復(fù)上述環(huán)節(jié),直到所有頂點(diǎn)都已輸出或圖中剩余的頂點(diǎn)中沒(méi)有前趨頂點(diǎn)為止。ｄ、輸出剩余的無(wú)前趨結(jié)點(diǎn)。拓?fù)渑判蚴聦?shí)上是對(duì)鄰接表表達(dá)的圖Ｇ進(jìn)行遍歷的過(guò)程。時(shí)間復(fù)雜度是Ｏ(n+ｅ)。第七章排序１.假如待排序文獻(xiàn)中存在多個(gè)關(guān)鍵字相同的記錄,通過(guò)排序后,這些具有相同關(guān)鍵字的記錄之間的相對(duì)順序保持不變,該排序方法是穩(wěn)定的；反之，則是不穩(wěn)定的。排序在內(nèi)存中解決,不涉及數(shù)據(jù)的內(nèi)外存互換，稱為內(nèi)部排序，反之為外部排序。內(nèi)部排序又分為五類：插入、選擇、互換、歸并和分派排序。在排序過(guò)程中需進(jìn)行兩種操作:比較兩個(gè)關(guān)鍵字的大小、改變指向記錄的指針或移動(dòng)記錄自身，而待排序記錄的存儲(chǔ)形式一般有三種:順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)和輔助表。評(píng)價(jià)排序算法的標(biāo)準(zhǔn)：執(zhí)行算法需要的時(shí)間,以及算法所需要的附加空間。尚有算法自身的復(fù)雜度。排序的時(shí)間開(kāi)銷,一般情況下可用算法中關(guān)鍵字的比較次數(shù)和記錄的移動(dòng)次數(shù)來(lái)衡量。2.插入排序:每次將一個(gè)待排序記錄按其關(guān)鍵字大小插入到前面已排好序的文獻(xiàn)中的適當(dāng)位置。直接插入排序：每次從無(wú)序區(qū)取出第一個(gè)元素把它插入到有序區(qū)的適當(dāng)位置,使之成為新的有序區(qū)，通過(guò)ｎ-1次插入后完畢。算法中R[0］作用：保存R[ｉ]副本，監(jiān)視數(shù)組下標(biāo)變量j是否越界。所以Ｒ[0］稱為哨兵。每次的比較是從后往前比較的。時(shí)間復(fù)雜度最佳是O(n)，最壞是O(n2)，所以是Ｏ(n2)。空間復(fù)雜度O(1)，所以是就地排序。是穩(wěn)定的算法。初始情況是有序區(qū)中只有一個(gè)元素R［１]，無(wú)序區(qū)中Ｒ［２..n]。希爾排序(縮小增量排序):算法不穩(wěn)定。記錄的總比較次數(shù)和總移動(dòng)次數(shù)都要比直接插入排序少得多，特別是當(dāng)ｎ越大越明顯。希爾排序的時(shí)間依賴于增量序列，最后一個(gè)增量必須是1，盡量避免增量互為倍數(shù)的情況。3．互換排序：兩兩比較待排序記錄的關(guān)鍵字,假如發(fā)現(xiàn)兩個(gè)記錄的順序相反時(shí)即進(jìn)行互換,直到?jīng)]有反序位置。冒泡排序(起泡排序)：通過(guò)相鄰元素之間比較和互換,使較小移向頂部,從后往前兩兩比較。時(shí)間復(fù)雜度最佳是O(ｎ)，最壞是O（n2），所以是Ｏ（n２)。是穩(wěn)定的排序算法?？焖倥判颍▌澐只Q排序):是冒泡排序的改善。比較和互換從兩端向中間進(jìn)行。一趟快速排序環(huán)節(jié):設(shè)兩個(gè)指針i和j,初值分別為loｗ和ｈｉgｈ,基準(zhǔn)為x＝R[i］,一方面從j位置開(kāi)始向前搜索第一個(gè)小于基準(zhǔn)x.key的記錄存入ｉ所指位置上,ｉ自增1,然后從i所指位置向后搜索找到第一個(gè)大于基準(zhǔn)x.key的記錄存入j所指位置上,ｊ自減1，反復(fù)直至i=j為止?？焖倥判蚴遣环€(wěn)定的。有非常好的時(shí)間復(fù)雜度，優(yōu)于其他各種排序算法,O(nlog２ｎ)，但是當(dāng)記錄關(guān)鍵字有序或基本有序時(shí)復(fù)雜度反而大了使之轉(zhuǎn)變成冒泡排序?yàn)椋?n2)?？焖倥判蚴沁f歸的,需要一個(gè)棧空間,空間復(fù)雜度O（log2n)。4.選擇排序：每一趟在待排序的記錄中選出關(guān)鍵字最小的記錄，依次存放在已排序好的記錄序列的最后。直接選擇排序:初始時(shí)，R[1..n]為無(wú)序區(qū),Ｒ[1]為空;第一趟是在R[1..n]中選出最小的記錄與R[1]互換,Ｒ［1］為有序區(qū)；第二趟是在R[2.．n］中選出最小的記錄與R[2］互換,R［1．.２]為有序區(qū)。時(shí)間復(fù)雜度Ｏ(n2)，是不穩(wěn)定的。初始情況是有序區(qū)為空，無(wú)序區(qū)中R[1..n］,第一趟從Ｒ[1..n］選擇最小記錄與Ｒ［1]互換。堆排序：是對(duì)直接選擇排序的改善，是一種樹(shù)形選擇排序?；舅枷耄涸谂判蜻^(guò)程中，將記錄數(shù)組R[1..n]當(dāng)作是一棵完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu),運(yùn)用完全二叉樹(shù)中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系,在當(dāng)前無(wú)序區(qū)中選擇關(guān)鍵字最大或最小記錄。每一趟排序：將當(dāng)前無(wú)序區(qū)調(diào)整為一個(gè)大根堆，選取關(guān)鍵字最大的堆頂記錄，將他和無(wú)序區(qū)中最后一個(gè)記錄互換。堆排序是一個(gè)不斷建堆的過(guò)程。構(gòu)造堆的過(guò)程:R[1]作為二叉樹(shù)的根，Ｒ[2.．n]依次逐層從左到右順序排列，構(gòu)成一棵完全二叉樹(shù),任意結(jié)點(diǎn)Ｒ[ｉ]的左孩子是R[2i],右孩子是R[2ｉ+1]，雙親是R?ｉ/2?,此稱為篩選法。從?ｎ/２?開(kāi)始。每一趟的時(shí)間復(fù)雜度是O(loｇ2n),整個(gè)堆排序的時(shí)間復(fù)雜度是Ｏ（nloｇ2n）。５.歸并排序：一方面將待排序文獻(xiàn)當(dāng)作n個(gè)長(zhǎng)度為1的有序子文獻(xiàn)，把這些子文獻(xiàn)兩兩歸并,得到?n/2?個(gè)長(zhǎng)度為2的有序子文獻(xiàn)，然后再將他們兩兩歸并，如此反復(fù)，直到得到一個(gè)長(zhǎng)度為ｎ的有序文獻(xiàn)，此稱為二路歸并排序。每一趟歸并排序的時(shí)間復(fù)雜度是O（n)，所以總的時(shí)間復(fù)雜度是O(nlog２ｎ)。6.分派排序:前面方法都至少需要進(jìn)行?nlogn?次比較,而分派排序?qū)r(shí)間復(fù)雜度降為O(n）。箱排序(桶排序)：基數(shù)排序：是對(duì)箱排序的改善和推廣。箱排序只合用于關(guān)鍵字取值范圍較小的情況,否則所需箱子數(shù)目太多。每個(gè)分量也許取值的個(gè)數(shù)rｄ稱為基數(shù)，基數(shù)的選擇和關(guān)鍵字的分解因關(guān)鍵字的類型而異。d趟箱排序?；鶖?shù)排序中,沒(méi)有進(jìn)行關(guān)鍵字的比較和記錄的移動(dòng),而只是掃描鏈表和進(jìn)行指針賦值，所以排序的時(shí)間重要用在修改指針上，初始化鏈表時(shí)間為Ｏ(ｎ)。7.內(nèi)部排序方法分析比較：本章除基數(shù)排序外,都是在順序表上實(shí)現(xiàn)的。時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定性插入直接插入O(n2)O(1)穩(wěn)定希爾排序O(nlｏｇ２n）或Ｏ(n1.25)O（１）不穩(wěn)定互換冒泡排序Ｏ(n２)O(１）穩(wěn)定快速排序O(nｌog2n）O（loｇ2n)不穩(wěn)定選擇直接選擇Ｏ(n２)O(1)不穩(wěn)定堆排序O(nlog2n)O（1)不穩(wěn)定歸并排序歸并排序O(nｌｏg2ｎ）O(n)穩(wěn)定分派排序基數(shù)排序O(d*（rｄ+n）)ｒd是基數(shù),d是關(guān)鍵字位數(shù)．n是元素個(gè)數(shù)Ｏ(ｒｄ+n)穩(wěn)定箱排序選取排序方法時(shí)需要考慮的重要因素：a、待排序的記錄個(gè)數(shù)，b、記錄自身的大小和存儲(chǔ)結(jié)構(gòu),ｃ、關(guān)鍵字的分布情況,d、對(duì)排序穩(wěn)定性的規(guī)定,ｅ、時(shí)間和空間復(fù)雜度要等排序方法的選取：a、若待排序的一組記錄數(shù)目n較小(如ｎ≤５0)時(shí)，可采用插入排序或選擇排序；b、n較大時(shí)，則應(yīng)采用快速排序、堆排序或歸并排序；c、若待排序記錄按關(guān)鍵字基本有序時(shí),則宜選用直接插入排序或冒泡排序；d、當(dāng)n很大，并且關(guān)鍵字位數(shù)較少時(shí),采用鏈?zhǔn)交鶖?shù)排序較好；ｅ、關(guān)鍵字比較次數(shù)與記錄的初始排列順序無(wú)關(guān)的排序方法是選擇排序。一般的排序方法都可以在順序結(jié)構(gòu)上實(shí)現(xiàn),當(dāng)記錄自身信息量較大時(shí)，可采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。插入、歸并、基數(shù)排序易于在鏈表上實(shí)現(xiàn)；快速排序和堆排序可以提取關(guān)鍵字建立索引表,然后對(duì)索引表進(jìn)行排序。第八章：查找1.查找又稱檢索，是數(shù)據(jù)解決中經(jīng)常使用的一種重要運(yùn)算。查找也分為內(nèi)查找和外查找。運(yùn)算查找的重要操作是關(guān)鍵字的比較，因此把查找過(guò)程中的平均比較次數(shù)（也稱為平均查找長(zhǎng)度)作為衡量算法效率優(yōu)劣的標(biāo)準(zhǔn)。2.順序表的查找:順序查找和二分查找順序查找又稱線性查找:查找成功的平均查找長(zhǎng)度（n＋1)/2，即約為表長(zhǎng)的一半。假如查找成功和不成功機(jī)會(huì)相等,那么平均查找長(zhǎng)度3（n+1)／4。優(yōu)點(diǎn)是簡(jiǎn)樸，對(duì)表的結(jié)構(gòu)無(wú)任何規(guī)定，無(wú)論是順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)、無(wú)論是否有序，都同樣合用,缺陷是效率低。對(duì)于有序表來(lái)說(shuō),該算法的平均查找長(zhǎng)度是（n+1)/2。二分查找（折半查找):規(guī)定查找對(duì)象的線性表必須是順序存儲(chǔ)結(jié)構(gòu)的有序表。查找過(guò)程是遞歸的。樹(shù)中每個(gè)子樹(shù)的根節(jié)點(diǎn)相應(yīng)當(dāng)前查找區(qū)間的中位記錄Ｒ［mid]，它的左子樹(shù)和右子樹(shù)分別相應(yīng)區(qū)間的左子表和右子表,通常將此樹(shù)稱為二叉鑒定樹(shù)。由于二分查找是在有序表上進(jìn)行的，所以其相應(yīng)的鑒定樹(shù)必然是一棵二叉排序樹(shù)。二叉鑒定樹(shù)一定是二叉排序樹(shù),二叉排序樹(shù)又稱為二叉查找樹(shù)。從鑒定樹(shù)上可見(jiàn)，關(guān)鍵字比較的次數(shù)恰好為該結(jié)點(diǎn)在樹(shù)中的層數(shù)。因此,二分查找算法在查找成功時(shí)進(jìn)行關(guān)鍵字比較的次數(shù)最多不超過(guò)鑒定樹(shù)的深度。查找成功時(shí)的平均查找長(zhǎng)度（n＋1)/nlｏg２(n+1）-１,當(dāng)n很大時(shí),可近似用ｌoｇ２(ｎ+1)－1表達(dá)。由于鑒定樹(shù)度數(shù)小于2的結(jié)點(diǎn)只也許在最下面的兩層,所以n個(gè)結(jié)點(diǎn)的鑒定樹(shù)的深度和ｎ個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度相同,即為?ｌog2(ｎ+1)?。可見(jiàn)，二分查找的最壞性能和平均性能相稱接近。二叉鑒定樹(shù)的輸出：每次以?(low＋ｈigｈ）/2?為根建樹(shù)。3.索引順序查找(分塊查找）:是一種介于順序查找和二分查找之間的查找方法。規(guī)定分塊有序,前一塊的最大關(guān)鍵字小于后一塊的最小關(guān)鍵字,抽取各塊中的最大關(guān)鍵字及其起始位置構(gòu)成索引表。分塊查找的基本思想是：一方面查找索引表,可用二分查找或順序查找,然后在擬定的塊中進(jìn)行順序查找。平均查找長(zhǎng)度：二分查找lo