自考數(shù)據(jù)結(jié)構(gòu)重點(diǎn)珍藏版

1、自考數(shù)據(jù)結(jié)構(gòu)重點(diǎn)(周堯整理)第一章概論1 .數(shù)據(jù)是信息的載體。2 .數(shù)據(jù)元素是數(shù)據(jù)的基本單位。3 .一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。4 .數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。5 .數(shù)據(jù)結(jié)構(gòu)一般包括以下三方面內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算數(shù)據(jù)元素之間的邏輯關(guān)系，也稱數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關(guān)，是獨(dú)立于計(jì)算機(jī)的。數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲器內(nèi)的表示，稱為數(shù)據(jù)的存儲結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn)，它依賴于計(jì)算機(jī)語言。數(shù)據(jù)的運(yùn)算，即對數(shù)據(jù)施加的操作。最常用的檢索、插入、刪除、更新、排序等。6 .數(shù)據(jù)的

2、邏輯結(jié)構(gòu)分類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)：若結(jié)構(gòu)是非空集，則有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼。線性表是一個(gè)典型的線性結(jié)構(gòu)。棧、隊(duì)列、串等都是線性結(jié)構(gòu)。非線性結(jié)構(gòu)：一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。7 .數(shù)據(jù)的四種基本存儲方法：順序存儲方法、鏈接存儲方法、索引存儲方法、散列存儲方法(1)順序存儲方法：該方法把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置上相鄰的存儲單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。通常借助程序語言的數(shù)組描述。(2)鏈接存儲方法：該方法不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰

3、，結(jié)點(diǎn)間的邏輯關(guān)系由附加的指針字段表示。通常借助于程序語言的指針類型描述。(3)索引存儲方法：該方法通常在儲存結(jié)點(diǎn)信息的同時(shí)，還建立附加的索引表。索引表由若干索引項(xiàng)組成。若每個(gè)結(jié)點(diǎn)在索引表中都有一個(gè)索引項(xiàng)，則該索引表稱之為稠密索引，稠密索引中索引項(xiàng)的地址指示結(jié)點(diǎn)所在的存儲位置。若一組結(jié)點(diǎn)在索引表中只對應(yīng)一個(gè)索引項(xiàng)，則該索引表稱為稀疏索引稀疏索引中索引項(xiàng)的地址指示一組結(jié)點(diǎn)的起始存儲位置。索引項(xiàng)的一般形式是：(關(guān)鍵字、地址)關(guān)鍵字是能唯一標(biāo)識一個(gè)結(jié)點(diǎn)的那些數(shù)據(jù)項(xiàng)。(4)散列存儲方法：該方法的基本思想是：根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲地址。8 .抽象數(shù)據(jù)類型(ADT):是指抽象數(shù)據(jù)的組織和與

4、之相關(guān)的操作?？梢钥醋魇菙?shù)據(jù)的邏輯結(jié)構(gòu)及其在邏輯結(jié)構(gòu)上定義的操作。抽象數(shù)據(jù)類型可以看作是描述問題的模型，它獨(dú)立于具體實(shí)現(xiàn)。它的優(yōu)點(diǎn)是將數(shù)據(jù)和操作封裝在一起，使得用戶程序只能通過在ADT里定義的某些操作來訪問其中的數(shù)據(jù)，從而實(shí)現(xiàn)了信息隱藏。9 .算法+數(shù)據(jù)Z§構(gòu)=程序數(shù)據(jù)結(jié)構(gòu)：是指數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)算法：是對數(shù)據(jù)運(yùn)算的描述10 .數(shù)據(jù)的運(yùn)算通過算法描述的。算法是任意一個(gè)良定義的計(jì)算過程。它以一個(gè)或多個(gè)值作為輸入，并產(chǎn)生一個(gè)或多個(gè)值作為輸出。若一個(gè)算法對于每個(gè)輸入實(shí)例均能終止并給出正確的結(jié)果，則稱該算法是正確的。正確的算法解決了給定的計(jì)算問題。11 .選用的算法首先應(yīng)該是"

5、;正確"的。此外，主要考慮如下三點(diǎn)： 執(zhí)行算法所耗費(fèi)的時(shí)間； 執(zhí)行算法所耗費(fèi)的存儲空間，其中主要考慮輔助存儲空間； 算法應(yīng)易于理解，易于編碼，易于調(diào)試等等。12. 一個(gè)算法所耗費(fèi)的時(shí)間=算法中每條語句的執(zhí)行時(shí)間之和，每條語句的執(zhí)行時(shí)間=語句的執(zhí)行次數(shù)(即頻度(FrequencyCount)x語句執(zhí)行一次所需時(shí)間。13. 算法求解問題的輸入量稱為問題的規(guī)模(Size),一般用一個(gè)整數(shù)表示。14. 一個(gè)算法的時(shí)間復(fù)雜度T(n)是該算法的時(shí)間耗費(fèi)，是該算法所求解問題規(guī)模n的函數(shù)。當(dāng)問題的規(guī)模n趨向無窮大時(shí)，時(shí)間復(fù)雜度T(n)的數(shù)量級(階)稱為算法的漸進(jìn)時(shí)間復(fù)雜度。平均時(shí)間復(fù)雜度是指所有可能

6、的輸入實(shí)例均以等概率出現(xiàn)的情況下，算法的期望運(yùn)行時(shí)間。15. 常見的時(shí)間復(fù)雜度按數(shù)量級遞增排列依次為：常數(shù)0(1)、對數(shù)階0(log2n)、線形階0(n)、線形對數(shù)階0(nlog2n)、平方階0(n2)立方階0(n3)、，、k次方階0(nk)、指數(shù)階0(2n)。16. 一個(gè)算法的空間復(fù)雜度S(n)定義為該算法所耗費(fèi)的存儲空間，它也是問題規(guī)模n的函數(shù)。第二章線性表1 .線性表(LinearList)是由n(n>0)個(gè)數(shù)據(jù)元素(結(jié)點(diǎn))a1,a2,an組成的有限序列。2 .線性表的邏輯結(jié)構(gòu)特征，對于非空白線性表：有且僅有一個(gè)開始結(jié)點(diǎn)a%沒有直接前趨，有且僅有一個(gè)直接后繼a2；有且僅有一個(gè)終結(jié)結(jié)

7、點(diǎn)an,沒有直接后繼，有且僅有一個(gè)直接前趨an-1；其余的內(nèi)部結(jié)點(diǎn)ai(2<i<n-1)都有且僅有一個(gè)直接前趨a“和一個(gè)ai+1。3 .常見的線性表的基本運(yùn)算：InitList(L)構(gòu)造一個(gè)空的線性表L,即表的初始化。(2)ListLength(L)求線性表L中的結(jié)點(diǎn)個(gè)數(shù)，即求表長。(3)GetNode(L,i)取線性表L中的第i個(gè)結(jié)點(diǎn)，這里要求1wiwListLength(L)(4)LocateNode(L,x)在L中查找值為x的結(jié)點(diǎn)，并返回該結(jié)點(diǎn)在L中的位置。若L中有多個(gè)結(jié)點(diǎn)的值和x相同，則返回首次找到的結(jié)點(diǎn)位置；若L中沒有結(jié)點(diǎn)的值為x,則返回一個(gè)特殊值表示查找失敗。(5)In

8、sertList(L,x,i)在線性表L的第i個(gè)位置上插入一個(gè)值為x的新結(jié)點(diǎn)，使得原編號為i,i+1,n的結(jié)點(diǎn)變?yōu)榫幪枮閕+1,i+2,n+1的結(jié)點(diǎn)。這里1Wiwn+1,而n是原表L的長度。插入后，表L的長度加1。(6)DeleteList(L,i)刪除線性表L的第i個(gè)結(jié)點(diǎn)，使得原編號為i+1,i+2,n的結(jié)點(diǎn)變成編號為i,i+1,n-1的結(jié)點(diǎn)。這里1WiWn,而n是原表L的長度。刪除后表L的長度減1。4 .順序存儲方法：把線性表的結(jié)點(diǎn)按邏輯次序依次存放在一組地址連續(xù)的存儲單元里的方法。順序表(SequentialList):用順序存儲方法存儲的線性表簡稱為順序表。順序表是一種隨機(jī)存取結(jié)構(gòu)，順

9、序表的的特點(diǎn)是邏輯上相鄰的結(jié)點(diǎn)其物理位置亦相鄰。5 .順序表中結(jié)點(diǎn)a的存儲地址：LOC(a)=LOC(a)+(i-1)*c1<i<n,6 .順序表上實(shí)現(xiàn)的基本運(yùn)算：(1)插入：在順序表中，結(jié)點(diǎn)的物理順序必須和結(jié)點(diǎn)的邏輯順序保持一致，因此必須將表中位置為n,n-1,i上的結(jié)點(diǎn)，依次后移到位置n+1,n,i+1上，空出第i個(gè)位置，然后在該位置上插入新結(jié)點(diǎn)x。僅當(dāng)插入位置i=n+1時(shí)，才無須移動結(jié)點(diǎn)，直接將x插入表的末尾。具體算法：voidInsertList(SeqList*L,DataTypex,inti)/將新結(jié)點(diǎn)x插入L所指的順序表的第i個(gè)結(jié)點(diǎn)ai的位置上算法的時(shí)間主要花費(fèi)在fo

10、r循環(huán)中的結(jié)點(diǎn)后移語句上。該語句的執(zhí)行次數(shù)是n-i+1,在表中第i個(gè)位置插入一個(gè)結(jié)點(diǎn)的移動次數(shù)為n-i+1,當(dāng)i=n+1:移動結(jié)點(diǎn)次數(shù)為0,即算法在最好時(shí)間復(fù)雜度是O(1),當(dāng)i=1：移動結(jié)點(diǎn)次數(shù)為n,即算法在最壞情況下時(shí)間復(fù)雜度是O(n)即在順序表上進(jìn)行插入運(yùn)算，平均要移動一半結(jié)點(diǎn)(n/2)。(2)刪除：在順序表上實(shí)現(xiàn)刪除運(yùn)算必須移動結(jié)點(diǎn)，才能反映出結(jié)點(diǎn)間的邏輯關(guān)系的變化。若i=n,則只要簡單地刪除終端結(jié)點(diǎn)，無須移動結(jié)點(diǎn)；若1wiwn-1,則必須將表中位置i+1,i+2,n的結(jié)點(diǎn)，依次前移到位置i,i+1,n-1上，以填補(bǔ)刪除操作造成的空缺。具體算法：voidDeleteList(SeqLi

11、st*L,inti)/從L所指的順序表中刪除第i個(gè)結(jié)點(diǎn)ai結(jié)點(diǎn)的移動次數(shù)由表長n和位置i決定：i=n時(shí)，結(jié)點(diǎn)的移動次數(shù)為0,即為0(1),i=1時(shí)，結(jié)點(diǎn)的移動次數(shù)為n-1,算法時(shí)間復(fù)雜度分別是O(n)順序表上做刪除運(yùn)算，平均要移動表中約一半的結(jié)點(diǎn)(n-1)/2,平均時(shí)間復(fù)雜度也是O(n)。7 .鏈接方式存儲的線性表簡稱為鏈表(LinkedList)。鏈表的具體存儲表示為：用一組任意的存儲單元來存放線性表的結(jié)點(diǎn)，鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同(這組存儲單元既可以是連續(xù)的，也可以是不連續(xù)的)。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲指示其后繼結(jié)點(diǎn)的地址(或位置)

12、信息(稱為指針(pointer)或鏈(link)。8 .鏈表的結(jié)點(diǎn)結(jié)構(gòu)：data域-存放結(jié)點(diǎn)值的數(shù)據(jù)域，next域-存放結(jié)點(diǎn)的直接后繼的地址(位置)的指針域(鏈域)單鏈表中每個(gè)結(jié)點(diǎn)的存儲地址是存放在其前趨結(jié)點(diǎn)next域中，而開始結(jié)點(diǎn)無前趨，故應(yīng)設(shè)頭指針head指向開始結(jié)點(diǎn)。終端結(jié)點(diǎn)無后繼，故終端結(jié)點(diǎn)的指針域?yàn)榭眨碞ULL9 .生成結(jié)點(diǎn)變量的標(biāo)準(zhǔn)函數(shù)p=(ListNode*)malloc(sizeof(ListNode);/函數(shù)malloc分配一個(gè)類型為ListNode的結(jié)點(diǎn)變量的空間，并將其首地址放入指針變量p中釋放結(jié)點(diǎn)變量空間的標(biāo)準(zhǔn)函數(shù)free(p);釋放p所指的結(jié)點(diǎn)變量空間結(jié)點(diǎn)分量的訪問

13、方法二：p->data和p->next指針變量p和結(jié)點(diǎn)變量*p的關(guān)系：指針變量p的值一一結(jié)點(diǎn)地址，結(jié)點(diǎn)變量*p的值一一結(jié)點(diǎn)內(nèi)容10 .建立單鏈表：(1)頭插法建表：從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放在新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。算法：s=(ListNode*)malloc(sizeof(ListNode);生成新結(jié)點(diǎn)s->data=ch;/將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中s->next=head;head=s;5. r-飛將皓點(diǎn)喇i列單值表加期的工r(2)尾插法建表：從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)，生成

14、新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放在新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，直到讀入結(jié)束標(biāo)志為止。算法：s=(ListNode*)malloc(sizeof(ListNode);生成新結(jié)點(diǎn)s->data=ch;/將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中if(head!=NULL)head=s;/新結(jié)點(diǎn)插入空表elser->next=s;將新結(jié)點(diǎn)插到*r之后r=s;尾指針指向新表尾希寐結(jié)心嘲到單值表hCFl，i的足|(3)尾插法建帶頭結(jié)點(diǎn)的單鏈表：頭結(jié)點(diǎn)及作用：頭結(jié)點(diǎn)是在鏈表的開始結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)。它具有兩個(gè)優(yōu)點(diǎn)1 .由于開始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中，所以在鏈表的第一個(gè)位置上

15、的操作就和在表的其它位置上操作一致，無須進(jìn)行特殊處理；2 .無論鏈表是否為空，其頭指針都是指向頭結(jié)點(diǎn)的非空指針(空表中頭結(jié)點(diǎn)的指針域空)，因此空表和非空表頭結(jié)點(diǎn)數(shù)據(jù)域的陰影表示該部分不存儲信息。在有的應(yīng)用中可用于存放表長等附加信息。的處理也就統(tǒng)一了。Mad強(qiáng)結(jié)點(diǎn)開始蹈點(diǎn)彗輯結(jié)點(diǎn)口*1已日七->1anlA|川非空表PHF1圍中工不用電至表沿頭結(jié)點(diǎn)的革燧能具體算法：r=head;/尾指針初值也指向頭結(jié)點(diǎn)while(ch=getchar()!='n')s=(ListNode*)malloc(sizeof(ListNode);/生成新結(jié)點(diǎn)s->data=ch;/將讀入的數(shù)據(jù)

16、放入新結(jié)點(diǎn)的數(shù)據(jù)域中r->next=s;r=s;r->next=NULL;/終端結(jié)點(diǎn)的指針域置空，或空表的頭結(jié)點(diǎn)指針域置空以上三個(gè)算法的時(shí)間復(fù)雜度均為O(n)。11.單鏈表上的查找：(1)鏈表不是隨機(jī)存取結(jié)構(gòu)在鏈表中，即使知道被訪問結(jié)點(diǎn)的序號i,也不能像順序表中那樣直接按序號i訪問結(jié)點(diǎn)，而只能從鏈表的頭指針出發(fā)，順鏈域next逐個(gè)結(jié)點(diǎn)往下搜索，直至搜索到第i個(gè)結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。(2)查找的思想方法計(jì)數(shù)器j置為。后，掃描指針p指針從鏈表的頭結(jié)點(diǎn)開始順著鏈掃描。當(dāng)p掃描下一個(gè)結(jié)點(diǎn)時(shí)，計(jì)數(shù)器j相應(yīng)地加1。當(dāng)j=i時(shí)，指針p所指的結(jié)點(diǎn)就是要找的第i個(gè)結(jié)點(diǎn)。而當(dāng)p指針指為

17、null且jwi時(shí)，則表示找不到第i個(gè)結(jié)點(diǎn)。頭結(jié)點(diǎn)可看做是第0個(gè)結(jié)點(diǎn)。算法：p=head;j=0;/從頭結(jié)點(diǎn)開始掃描while(p->next&&j<i)順指針向后掃描，直到p->next為NULLi=j為止p=p->next;j+;if(i=j)returnp;/找到了第i個(gè)結(jié)點(diǎn)elsereturnNULL;/當(dāng)i<0或i>0時(shí)，找不到第i個(gè)結(jié)點(diǎn)時(shí)間復(fù)雜度：在等概率假設(shè)下，平均時(shí)間復(fù)雜度為：為n/2=O(n)(2)按值查找：具體算法：ListNode*p=head->next;/從開始結(jié)點(diǎn)比較。表非空，p初始值指向開始結(jié)點(diǎn)while(

18、p&&p->data!=key)/直到p為NULLp->data為key為止p=p->next;/掃描下一結(jié)點(diǎn)returnp;/若p=NULL則查找失敗，否則p指向彳I為key的結(jié)點(diǎn)時(shí)間復(fù)雜度為：O(n)12.插入運(yùn)算：插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到a“與ai之間。具體步驟：(1)找到ai-i存儲位置p(2)生成一個(gè)數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)*s(3)令結(jié)點(diǎn)*p的指針域指向新結(jié)點(diǎn)(4)新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)aiohcnd1 I*HFLIIA*在單錯表上植入站或不息用具體算法：p=GetNode(head,i-1);尋找第i-1個(gè)結(jié)點(diǎn)i

19、f(p=NULL)i<1或i>n+1時(shí)插入位置i有錯Error("positionerror");s=(ListNode*)malloc(sizeof(ListNode);s->data=x;s->next=p->next;p->next=s;算法的時(shí)間主要耗費(fèi)在查找操作GetNode上，故時(shí)間復(fù)雜度亦為O(n)。13 .刪除運(yùn)算刪除運(yùn)算是將表的第i個(gè)結(jié)點(diǎn)刪去。具體步驟：(1)找到ai-1的存儲位置p(因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)a的存儲地址是在其直接前趨結(jié)點(diǎn)ai-1的指針域next中)(2)令p->next指向a的直接后繼結(jié)點(diǎn)(即把a(bǔ)從鏈上

20、摘下)(3)釋放結(jié)點(diǎn)a的空間，將其歸還給“存儲池”。具體算法：p=GetNode(head,i-1);找到第i-1個(gè)結(jié)點(diǎn)if(p=NULL|p->next=NULL)/i<1或i>n時(shí)，刪除位置錯Error("positionerror");/退出程序運(yùn)行r=p->next;使r指向被刪除的結(jié)點(diǎn)aip->next=r->next;/將ai從鏈上摘下free(r);釋放結(jié)點(diǎn)ai的空間給存儲池算法的時(shí)間復(fù)雜度也是O(n)o鏈表上實(shí)現(xiàn)的插入和刪除運(yùn)算，無須移動結(jié)點(diǎn)，僅需修改指針。14 .單循環(huán)鏈表一一在單鏈表中，將終端結(jié)點(diǎn)的指針域NULL改為指

21、向表頭結(jié)點(diǎn)或開始結(jié)點(diǎn)即可。判斷空鏈表的條件是head=head->next;15 .僅設(shè)尾指針的單循環(huán)鏈表：用尾指針rear表示的單循環(huán)鏈表對開始結(jié)點(diǎn)a1和終端結(jié)點(diǎn)an查找時(shí)間都是O(1)。而表的操作常常是在表的首尾位置上進(jìn)行，因此，實(shí)用中多采用尾指針表示單循環(huán)鏈表。判斷空鏈表的條件為rear=rear->next;rMr*rrRF便設(shè)厘指針的單斯阡枝融16 .循環(huán)鏈表：循環(huán)鏈表的特點(diǎn)是無須增加存儲量，僅對表的鏈接方式稍作改變，即可使得表處理更加方便靈活。若O(1)Ohi_|>曲個(gè)單捎沖遺表的糧挨操忤示意國具體算法：LinkListConnect(LinkListA,Link

22、ListB)/假設(shè)A,B為非空循環(huán)鏈表的尾指針LinkListp=A->next;/A->next=B->next->next;/free(B->next);/B->next=p;/returnB;/循環(huán)鏈表中沒有保存A表的頭結(jié)點(diǎn)位置B表的開始結(jié)點(diǎn)鏈接到A表尾釋放B表的頭結(jié)點(diǎn)返回新循環(huán)鏈表的尾指針NULL指針。涉及遍歷操作時(shí)，其終止條件就不再是像非循環(huán)鏈表那樣判別p或p->next是否在尾指針表示的單循環(huán)鏈表上實(shí)現(xiàn)，則只需修改指針，無須遍歷，其執(zhí)行時(shí)間是為空，而是判別它們是否等于某一指定指針，如頭指針或尾指針等。在單鏈表中，從一已知結(jié)點(diǎn)出發(fā)，只能訪問到

23、該結(jié)點(diǎn)及其后續(xù)結(jié)點(diǎn)，無法找到該結(jié)點(diǎn)之前的其它結(jié)點(diǎn)。而在單循環(huán)鏈表中，從任一結(jié)點(diǎn)出發(fā)都可訪問到表中所有結(jié)點(diǎn)，這一優(yōu)點(diǎn)使某些運(yùn)算在單循環(huán)鏈表上易于實(shí)現(xiàn)。next域存放后繼結(jié)點(diǎn)地址外，還增加一個(gè)指17 .雙向鏈表：雙(向)鏈表中有兩條方向不同的鏈，即每個(gè)結(jié)點(diǎn)中除向其直接前趨的指針域prior。jjriairdkatiincAiQhcrld*_o雙鏈表由頭指針head惟一確定的。帶頭結(jié)點(diǎn)的雙鏈表的某些運(yùn)算變得方便。將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來，為雙(向)循環(huán)鏈表。(n)玷點(diǎn)站點(diǎn)(h)空的以肺阡俗衣會)I空的雙飾環(huán)轉(zhuǎn)&期他表示急圖18.雙向鏈表的前插和刪除本結(jié)點(diǎn)操作雙鏈表的前插操作voidDInse

24、rtBefore(DListNode*p,DataTypex)/在帶頭結(jié)點(diǎn)的雙鏈表中，將值為x的新結(jié)點(diǎn)插入*ppwNULLDListNode*s=malloc(sizeof(DListNode);/s->data=x;/s->prior=p->prior;/s->next=p;/p->prior->next=s;/p->prior=s;/雙鏈表上刪除結(jié)點(diǎn)*p自身的操作1T4例&I副除姐即voidDDeleteNode(DListNode*p)/在帶頭結(jié)點(diǎn)的雙鏈表中，刪除結(jié)點(diǎn)*p,設(shè)*p為非終端結(jié)點(diǎn)p->prior->next=p-&

25、gt;next;/p->next->prior=p->prior;/free(p);/與單鏈表上的插入和刪除操作不同的是，在雙鏈表中插入和刪除必須同時(shí)修改兩個(gè)方向上的指針。上述兩個(gè)算法的時(shí)間復(fù)雜度均為。(1)。之前，設(shè)，存儲密19 .存儲密度(StorageDensity)是指結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲量和整個(gè)結(jié)點(diǎn)結(jié)構(gòu)所占的存儲量之比，即度=(結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲量)/(結(jié)點(diǎn)結(jié)構(gòu)所占的存儲總量)。20 .順序表和鏈表比較順序表和鏈表各有短長。在實(shí)際應(yīng)用中究竟選用哪一種存儲結(jié)構(gòu)呢？這要根據(jù)具體問題的要求和性質(zhì)來決定。通常有以下幾方面的考慮：順序表分配方式靜態(tài)分配。程序執(zhí)行之前必須

26、明確規(guī)定存儲規(guī)模。若線性表長度n變化較大，則存儲規(guī)模難于預(yù)先確定估計(jì)過大將造成空間浪費(fèi)，估計(jì)太小又將使空間溢出機(jī)會增多。動態(tài)分配只要內(nèi)存空間尚有空閑，就不會產(chǎn)生溢出。因此，當(dāng)線性表的長度變化較大，難以借計(jì)其存儲規(guī)模時(shí)，以米用動態(tài)鏈表作為存儲結(jié)構(gòu)為好。存儲密度為1。當(dāng)線性表的長度變化不大，易于事先確定其大小時(shí)，為了節(jié)約存儲空間，宜采用順序表作為存儲結(jié)構(gòu)。<1存取方式隨機(jī)存取結(jié)構(gòu)，對表中結(jié)點(diǎn)都可在O（1）時(shí)間內(nèi)直接取得線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時(shí)，采用順序表做存儲結(jié)構(gòu)為宜。順序存取結(jié)構(gòu)，鏈表中的結(jié)點(diǎn)，需從頭指針起順著鏈掃描才能取得。插入刪除操作在順序表中進(jìn)行插入和刪除，

27、平均要移動表中心半的結(jié)點(diǎn)，尤箕是當(dāng)每個(gè)結(jié)點(diǎn)的信息量較大時(shí)，移動結(jié)點(diǎn)的時(shí)間開銷就相當(dāng)可觀。在鏈表中的任何位置上進(jìn)行插入和刪除，都只需要修改指針。對于頻繁進(jìn)行插入和刪除的線性表，宜采用鏈表做存儲結(jié)構(gòu)。若表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜第三章棧1 .棧（Stack）是限制僅在表的一端進(jìn)行插入和刪除運(yùn)算的線性表。（1）通常稱插入、刪除的這一端為棧頂（Top）,另一端稱為棧底（Bottom）。（2）當(dāng)表中沒有元素時(shí)稱為空棧。（3）棧為后進(jìn)先出（LastInFirstOut）的線性表，簡稱為LIFO表。棧的修改是按后進(jìn)先出的原則進(jìn)行。每次刪除（退棧）的總是當(dāng)前棧中&q

28、uot;最新”的元素，即最后插入（進(jìn)棧）的元素，而最先插入的是被放在棧的底部，要到最后才能刪除。2 .順序棧：棧的順序存儲結(jié)構(gòu)簡稱為順序棧，它是運(yùn)算受限的順序表。順序棧中元素用向量存放棧底位置是固定不變的，可設(shè)置在向量兩端的任意一個(gè)端點(diǎn)棧頂位置是隨著進(jìn)棧和退棧操作而變化的，用一個(gè)整型量top（通常稱top為棧頂指針）來指示當(dāng)前棧頂位置3 .進(jìn)棧操作：進(jìn)棧時(shí)，需要將S->top加1,S->top=StackSize-1表示棧滿"上溢"現(xiàn)象-當(dāng)棧滿時(shí)，再做進(jìn)棧運(yùn)算產(chǎn)生空間溢出的現(xiàn)象。退棧操作：退棧時(shí)，需將S->top減1S->top<0表示空棧&q

29、uot;下溢"現(xiàn)象-當(dāng)?？諘r(shí)，做退棧運(yùn)算產(chǎn)生的溢出現(xiàn)象。下溢是正?，F(xiàn)象，常用作程序控制轉(zhuǎn)移的條件。4 .兩個(gè)棧共享同一存儲空間：當(dāng)程序中同時(shí)使用兩個(gè)棧時(shí)，可以將兩個(gè)棧的棧底設(shè)在向量空間的兩端，讓兩個(gè)棧各自向中間延伸。當(dāng)一個(gè)棧里的元素較多，超過向量空間的一半時(shí)，只要另一個(gè)棧的元素不多，那么前者就可以占用后者的部分存儲空間。順序棧明3E支用j'l.fl.琳tW±j'J>1當(dāng)Top1=Top2-1時(shí)，棧滿雨亂皿kl唯底知.卜工叫國!，個(gè)元素佃|臼同同d|Hlb|a|5 .鏈棧是沒有附加頭結(jié)點(diǎn)的運(yùn)算受限的單鏈表。棧頂指針就是鏈表的頭指針。鏈棧中的結(jié)點(diǎn)是動態(tài)分配

30、的，所以可以不考慮上溢，無須定義StackFull運(yùn)算6 .隊(duì)列（Queue）是只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的運(yùn)算受限的線性表。允許刪除的一端稱為隊(duì)頭（Front）,允許插入的一端稱為隊(duì)尾（Rear）,當(dāng)隊(duì)列中沒有元素時(shí)稱為空隊(duì)列，隊(duì)列亦稱作先進(jìn)先出(FirstInFirstOut）的線性表，簡稱為FIFO表。7 .隊(duì)列的順序存儲結(jié)構(gòu)稱為順序隊(duì)列，順序隊(duì)列實(shí)際上是運(yùn)算受限的順序表。rearI'ronv.rear儲）隊(duì)列初始為空frontfrontrear匚出隊(duì).時(shí)為空敬序隊(duì)列操作示卷圖順序隊(duì)列的基本操作入隊(duì)時(shí)：將新元素插入rear所指的位置，然后將rear加1。出隊(duì)時(shí)：刪去

31、front所指的元素，然后將front加1并返回被刪元素。當(dāng)頭尾指針相等時(shí)，隊(duì)列為空。在非空隊(duì)列里，隊(duì)頭指針始終指向隊(duì)頭元素，尾指針始終指向隊(duì)尾元素的下一位置。8 .順序隊(duì)列中的溢出現(xiàn)象：當(dāng)隊(duì)列為空時(shí)，做出隊(duì)運(yùn)算產(chǎn)生的溢出現(xiàn)象。“下溢”是正常現(xiàn)象，常用作程序控制轉(zhuǎn)移的條件。當(dāng)隊(duì)列滿時(shí)，做進(jìn)棧運(yùn)算產(chǎn)生空間溢出的現(xiàn)象。“真上溢”是一種出錯狀態(tài)，應(yīng)設(shè)法避免。"假上溢"現(xiàn)象：由于入隊(duì)和出隊(duì)操作中，頭尾指針只增加不減小，致使被刪元素的空間永遠(yuǎn)無法重新利用。當(dāng)隊(duì)列中實(shí)際的元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于向量空間的規(guī)模時(shí)，也可能由于尾指針已超越向量空間的上界而不能做入隊(duì)操作。該現(xiàn)象稱為“假上溢"

32、;現(xiàn)象。9 .循環(huán)隊(duì)列：為充分利用向量空間，克服"假上溢"現(xiàn)象的方法是：將向量空間想象為一個(gè)首尾相接的圓環(huán)，并稱這from種向量為循環(huán)向量。存儲在其中的隊(duì)列稱為循環(huán)隊(duì)列(CircularQueue)。循環(huán)隊(duì)列中進(jìn)行出隊(duì)、入隊(duì)操作時(shí)，頭尾指針仍要加1,朝前移動。只不過當(dāng)頭尾指針指向向量上界(QueueSize-1)時(shí)，其加1操作的結(jié)果是指向向量的下界0。這種循環(huán)意義下的加1操作可以描述為：方法一：if(i+1=QueueSize)/i表示front或reari=0;elsei+;方法二-利用"模運(yùn)算"i=(i+1)%QueueSize;循環(huán)隊(duì)列中，由于入隊(duì)

33、時(shí)尾指針向前追趕頭指針；出隊(duì)時(shí)頭指針向前追趕尾指針，造成隊(duì)空和隊(duì)滿時(shí)頭尾指針均相等。因此，無法通過條件front=rear來判別隊(duì)列是"空"還是"滿"。解決這個(gè)問題的方法至少有三種：另設(shè)一布爾變量以區(qū)別隊(duì)列的空和滿；少用一個(gè)元素的空間。約定入隊(duì)前，測試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等則認(rèn)為隊(duì)滿(注意：rear所指的單元始終為空)；使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)(即隊(duì)列長度)。個(gè)北素人隊(duì)藉.荒環(huán)以網(wǎng)個(gè)布解I。兒.元素A隊(duì)操作道行中.的星將指向卜，人隊(duì)O.甌新開始10 .循環(huán)隊(duì)列的基本運(yùn)算：置隊(duì)空：Q->front=Q->rea

34、r=0;Q->count=0;判隊(duì)空：returnQ->count=0;判隊(duì)滿：returnQ->count=QueueSize;隊(duì)列元素個(gè)數(shù)加1新元素插入隊(duì)尾入隊(duì)Q->count+;/Q->dataQ->rear=x;/Q->rear=(Q->rear+1)%QueueSize;出隊(duì)temp=Q->dataQ->front;隊(duì)列元素個(gè)數(shù)減1循環(huán)意義下的頭指針加1Q->count-;/Q->front=(Q->front+1)%QueueSize;/returntemp;取隊(duì)頭元素returnQ->dataQ-

35、>front;11 .隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈隊(duì)列。它是限制僅在表頭刪除和表尾插入的單鏈表。鏈隊(duì)列的基本運(yùn)算：(1)(2)(3)(5)（b”上空隊(duì)列Q-ft置空隊(duì)：Q->front=Q->rear=NULL;判隊(duì)空：returnQ->front=NULL&&Q->rear=Null;入隊(duì)：QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode);p->data=x;p->next=NULL;if(QueueEmpty(Q)Q->front=Q->rear=p;/else/xQ->

36、;rear->next=p;Q->rear=p;出隊(duì)：p=Q->front;x=p->data;Q->front=p->next;if(Q->rear=p)/Q->rear=NULL;free(p);/returnx;/插入非空隊(duì)列的尾/*p/申請新結(jié)點(diǎn)將X插入空隊(duì)列/鏈到原隊(duì)尾結(jié)點(diǎn)后隊(duì)尾指針指向新的尾指向?qū)︻^結(jié)點(diǎn)保存對頭結(jié)點(diǎn)的數(shù)據(jù)將對頭結(jié)點(diǎn)從鏈上摘下原隊(duì)中只有一個(gè)結(jié)點(diǎn)，刪去后隊(duì)列變空，此時(shí)隊(duì)頭指針已為空釋放被刪隊(duì)頭結(jié)點(diǎn)返回原隊(duì)頭數(shù)據(jù)取隊(duì)頭元素：if(QueueEmpty(Q)Error("Queueifempty.");re

37、turnQ->front->data;和鏈棧類似，無須考慮判隊(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ì)列變空。以上討論的是無頭結(jié)點(diǎn)鏈隊(duì)列的基本運(yùn)算。和單鏈表類似，為了簡化邊界條件的處理，在隊(duì)頭結(jié)點(diǎn)前也可附加一個(gè)頭結(jié)點(diǎn)，增加頭結(jié)點(diǎn)的鏈隊(duì)列的基本運(yùn)算。12.遞歸是指：若在一個(gè)函數(shù)、過程或者數(shù)據(jù)結(jié)構(gòu)定義的內(nèi)部，直接（或間接）出現(xiàn)定義本身的應(yīng)用，則稱它們是遞歸的，或者是遞歸定義的。調(diào)用函數(shù)時(shí)，系統(tǒng)將會為調(diào)用者構(gòu)造一個(gè)由參數(shù)表和返回地址組成的活動記錄，并將其壓入到由系統(tǒng)提供的運(yùn)行時(shí)刻棧

38、的棧頂，然后將程序的控制權(quán)轉(zhuǎn)移到被調(diào)函數(shù)。若被調(diào)函數(shù)有局部變量，則在運(yùn)行時(shí)刻棧的棧頂也要為其分配相應(yīng)的空間。因此，活動記錄和這些局部變量形成了一個(gè)可供被調(diào)函數(shù)使用的第四章串1 .串（又稱字符串）是一種特殊的線性表，它的每個(gè)結(jié)點(diǎn)僅由一個(gè)字符組成。串（的有限序列。一般記為S="a1a2,an"將串值括起來的雙引號本身不屬于串，它的作用是避免串與常數(shù)或與標(biāo)識符混淆。活動結(jié)構(gòu)。String）是零個(gè)或多個(gè)字符組成2 .長度為零的串稱為空串（EmptyString）,它不包含任何字符。（BlankString）。僅由一個(gè)或多個(gè)空格組成的串稱為空白串和分別表示長度為1的空白串和長度為0的

39、空串。3 .串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串。包含子串的串相應(yīng)地稱為主串?？沾侨我獯淖哟我獯瞧渥陨淼淖哟?。4 .通常在程序中使用的串可分為：串變量和串常量。串變量和其它類型的變量一樣，其取值是可以改變的。串常量和整常數(shù)、實(shí)常數(shù)一樣，在程序中只能被引用但不能改變其值。即只能讀不能寫。5 .串的基本運(yùn)算：串復(fù)制：char*strcpy(char*to,*from)聯(lián)接：char*strcat(char*to,char*from);/串比較:intstrcmp(char*s1,char*s2);/求串長：intstrlen(char*s);/求串s的長度/將from串復(fù)制到to串

40、中，并返回to開始處指針將from串復(fù)制到to串的末尾，并返回to串開始處的指針比較s1和s2的大小，/當(dāng)s1<s2、s1>s2和s1=s2時(shí)，分別返回小于0、大于0和等于0的值【例】result=strcmp("baker","Baker");/result>0result=strcmp("12","12");/result=0result=strcmp("Joe","joseph")/result<0字符定位：char*strchr(char*s,

41、charc);/找c在字符串s中第一次出現(xiàn)的位置，/若找到，則返回該位置，否則返回NULL6 .串的順序存儲結(jié)構(gòu)簡稱為順序串。與順序表類似，順序串是用一組地址連續(xù)的存儲單元來存儲串中的字符序列。按其存儲分配的不同可將順序串分為如下兩類：(1)靜態(tài)存儲分配的順序串串值空間的大小在編譯時(shí)刻就已確定，是靜態(tài)的。難以適應(yīng)插入、鏈接等操作直接使用定長的字符數(shù)組存放串內(nèi)容外，一般可使用一個(gè)不會出現(xiàn)在串中的特殊字符放在串值的末尾來表示串的結(jié)束。所以串空間最大值為MaxStrSize時(shí)，最多只能放MaxStrSize-1個(gè)字符。C語言中以字符'0'表示串值的終STUDENT0(2)動態(tài)存儲分配

42、的順序串：順序串的字符數(shù)組空間可使用C語言的malloc和free等動態(tài)存儲管理函數(shù)，來根據(jù)實(shí)際需要動態(tài)地分配和釋放。sI-HhI+-1+1l+LI"HI_H*3國軸點(diǎn)大小為i的依m(xù)sS_r|hc|dTe|f7八岫站點(diǎn)大小為*的轆州3(e)ifl圖&中的第：個(gè)字拘后招入、戶”后的過事b他中小癥M7 .用單鏈表方式存儲串值，串的這種鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈串。鏈串和單鏈表的差異僅在于其結(jié)點(diǎn)數(shù)據(jù)域?yàn)閱蝹€(gè)字符：一個(gè)鏈串由頭指針唯一確定。鏈串的結(jié)點(diǎn)大?。簽榱颂岣叽鎯γ芏?，可使每個(gè)結(jié)點(diǎn)存放多個(gè)字符。當(dāng)結(jié)點(diǎn)大小大于1時(shí)，串的長度不一定正好是結(jié)點(diǎn)大小的整數(shù)倍，因此要用特殊字符來填充最后一個(gè)結(jié)點(diǎn)

43、，以表示串的終結(jié)。雖然提高結(jié)點(diǎn)的大小使得存儲密度增大，但是做插入、刪除運(yùn)算時(shí)，可能會引起大量字符的移動，給運(yùn)算帶來不便。8 .子串定位運(yùn)算又稱串的模式匹配或串匹配。子串定位運(yùn)算類似于串的基本運(yùn)算中的字符定位運(yùn)算。只不過是找子串而不是找字符在主串中首次出現(xiàn)的位置。此運(yùn)算的應(yīng)用非常廣泛。在串匹配中，一般將主串稱為目標(biāo)(串)，子串稱為模式(串)。串匹配就是對于合法的位置(又稱合法的位移)0WiWn-m,依次將目標(biāo)串中的子串"titi+1,ti+m-1”和模式串"PoPQPm-1"進(jìn)行比較：若"titi+1,ti+m-1"="P0PiP2，P

44、m-1”，則稱從位置i開始的匹配成功，或稱i為有效位移。若"titi+1,ti+m-1"W"p0pip2,pm-1",則稱從位置i開始的匹配失敗，或稱i為無效位移。因此，串匹配問題可簡化為找出某給定模式串P在給定目標(biāo)串T中首次出現(xiàn)的有效位移。有些應(yīng)用中要求求出P在T中所有出現(xiàn)的有效位移。9 .樸素的串匹配算法的基本思想：即用一個(gè)循環(huán)來依次檢查n-m+1個(gè)合法的位移i(0WiWn-m)是否為有效位移。請輸入由sssxxsssxs與0施人模K*5SXS順序串上的串匹配算法：最壞時(shí)間復(fù)雜度：為O(n-m+1)m)。模式匹配算法的改進(jìn)：樸素的串匹配算法雖然簡單，

45、但效率低。其原因是在檢查位移i是否為有效位移時(shí)，沒有利用檢查位移i-1,i,0時(shí)的部分匹配結(jié)果。若利用部分匹配結(jié)果，模式串右滑動的距離就不會是每次一位，而是每次使其向右滑動得盡可能遠(yuǎn)。這樣可使串匹配算法的最壞時(shí)間控制在O(m+n)數(shù)量級上。鏈串上的子串定位運(yùn)算：用結(jié)點(diǎn)大小為1的單鏈表做串的存儲結(jié)構(gòu)時(shí)，實(shí)現(xiàn)樸素的串匹配算法很簡單。只是現(xiàn)在的位移shift是結(jié)點(diǎn)地址而非整數(shù)，且單鏈表中沒有存儲長度信息。若匹配成功，則返回有效位移所指的結(jié)點(diǎn)地址，否則返回指針。第五章多維數(shù)組和廣義表1 .多維數(shù)組和廣義表是一種復(fù)雜的非線性結(jié)構(gòu)，它們的邏輯特征是：一個(gè)數(shù)據(jù)元素可能有多個(gè)直接前驅(qū)和多個(gè)直接后繼。2 .一維

46、數(shù)組(向量)是存儲于計(jì)算機(jī)的連續(xù)存儲空間中的多個(gè)具有統(tǒng)一類型的數(shù)據(jù)元素。同一數(shù)組的不同元素通過不同的下標(biāo)標(biāo)識。(ai,a2,an)3 .二維數(shù)組Ann可視為由m個(gè)行向量組成的向量，或由n個(gè)列向量組成的向量。二維數(shù)組中的每個(gè)元素a”既屬于第i行的行向量，又屬于第j列的列向量。B個(gè)列向量4 .多維數(shù)組：三維數(shù)組Amnp可視為以二維數(shù)組為數(shù)據(jù)元素的向量。四維數(shù)組可視為以三維數(shù)組為數(shù)據(jù)元素的向量,，三維數(shù)組中的每個(gè)元素a”k都屬于三個(gè)向量。四維數(shù)組中的每個(gè)元素都屬于四個(gè)向量5 .數(shù)組的順序存儲方式：由于計(jì)算機(jī)內(nèi)存是一維的，多維數(shù)組的元素應(yīng)排成線性序列后存人存儲器。數(shù)組一般不做插入和刪除操作，即結(jié)構(gòu)中元

47、素個(gè)數(shù)和元素間關(guān)系不變化。一般采用順序存儲方法表示數(shù)組。(1)行優(yōu)先順序：將數(shù)組元素按行向量排列，第i+1個(gè)行向量緊接在第i個(gè)行向量后面?！纠慷S數(shù)組Ann的按行優(yōu)先存儲的線性序列為：a11,a12>>,a1n,a21,a22,a2n,am1,am2,a(2)列優(yōu)先順序?qū)?shù)組元素按列向量排列，第i+1個(gè)列向量緊接在第i個(gè)列向量后面?！纠慷S數(shù)組Ann的按列優(yōu)先存儲的線性序列為：a11,a21>>>am1,a12,a22,am2,a1n,a2n,a6 .數(shù)組元素的地址計(jì)算公式：(1)按行優(yōu)先順序存儲的二維數(shù)組Amn地址計(jì)算公式LOC(a”尸LOC(an)+(i-

48、1)xn+j-1xd(注：此公式下界為1,如下界為0,則公式變?yōu)閕xn+j)LOC(aQ是開始結(jié)點(diǎn)的存放地址(即基地址)d為每個(gè)元素所占的存儲單元數(shù)由地址計(jì)算公式可得，數(shù)組中任一元素可通過地址公式在相同時(shí)間內(nèi)存取。即順序存儲的數(shù)組是隨機(jī)存取結(jié)構(gòu)。(2)按列優(yōu)先順序存儲的二維數(shù)組Amn地址計(jì)算公式LOC(a")=LOC(a11)+(j-1)xm+i-1xd(注：此公式下界為1,如下界為0,則公式變?yōu)閖xm+i)(3)按行優(yōu)先順序存儲的三維數(shù)組Amnp地址計(jì)算公式LOC(a冰尸LOC(a111)+(i-1)XnXp+(j-1)Xp+k-1Xd(注：此公式下界為1,如下界為0,則公式變?yōu)閕

49、xnxp+jxp+k)(4)下界不為1的二維數(shù)組的地址計(jì)算公式二維數(shù)組Ac1.d1,c2.d2的地址計(jì)算公式：LOC(aij)=LOC(ac1c2)+(i-c1)x(d2-c2+1)+j-c2Xd下界為0的二維數(shù)組的地址計(jì)算公式(C語言中使用)LOC(aij)=LOC(a0°)+ix(d2+1)+jXd7 .矩陣用二維數(shù)組描述時(shí)，存儲的密度為1?？梢詫ζ湓剡M(jìn)行隨機(jī)存取，各種矩陣運(yùn)算也非常簡單。矩陣的壓縮：矩陣中非零元素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況下，為了節(jié)省存儲空間，我們可以對這類矩陣進(jìn)行壓縮存儲：即為多個(gè)相同的非零元素只分配一個(gè)存儲空間；對零元素不分配空間。8

50、.所謂特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣。常見的有對稱矩陣、三角矩陣和對角矩陣等。(1)對稱矩陣在一個(gè)n階方陣A中，若元素滿足下述性質(zhì)：aij=aji0<i,j<n-1(2)對稱矩陣的壓縮存儲對稱矩陣中的元素關(guān)于主對角線對稱，故只要存儲矩陣中上三角或下三角中的元素，讓每兩個(gè)對稱的元素共享一個(gè)存儲空間。這樣，能節(jié)約近一半的存儲空間。按"行優(yōu)先順序"存儲主又角線(包括對角線)以下的元素nuu-aiiu履II1兜H2I讓L-fl*1.1SnI,ZFhl.nH由(下三角矩陣中，元素總數(shù)為n(n+1)/2)。即按a00,ai0,aii,a-1,0,an-1

51、.1,拼.次序存放在一個(gè)向量sa0.n(n+1)/2-1中sa0=a00,sa1=a10,san(n+1)/2-1=an-m元素a”的存放位置：saix(i+1)/2+j=a”a”和sak之間的對應(yīng)關(guān)系：令I(lǐng)=max(i,j),J=min(i,j)，則k和i,j的對應(yīng)關(guān)系可統(tǒng)一為：k=Ix(|+1)/2+J0<k<n(n+1)/2(3)對稱矩陣的地址計(jì)算公式：LOC(aij)=LOC(sa0)+Ix(|+1)/2+JXd,其中I=max(i,j),J=min(i,j)9 .三角矩陣的劃分：以主對角線劃分，三角矩陣有上三角矩陣和下三角矩陣兩種。上三角矩陣：如下圖(a)所示，它的下三角

52、(不包括主角線)中的元素均為常數(shù)co下三角矩陣：與上三角矩陣相反，它的主對角線上方均為常數(shù)c,如下圖(b)所示。"auuam.ag,n-n-lawicc1caij.ai.ir-iian.cS)上三粕斯附缶)下三擔(dān)所附沈期降10 .三角矩陣的壓縮存儲：三角矩陣中的重復(fù)元素c可共享一個(gè)存儲空間，其余的元素正好有nX(n+1)/2個(gè)，因此,三角矩陣可壓縮存儲到向量sa0.n(n+1)/2中，其中c存放在向量的最后一個(gè)分量中。上三角矩陣中aij和sak之間的對應(yīng)關(guān)系k=ix(2n-i+1)/2+j-i當(dāng)iwjk=nX(n+1)/2當(dāng)i>j下三角矩陣中aij和sak之間的對應(yīng)關(guān)系k=ix

53、(i+1)/2+j當(dāng)i>jk=nX(n+1)/2當(dāng)ivj三角矩陣的壓縮存儲結(jié)構(gòu)是隨機(jī)存取結(jié)構(gòu)。11 .對角矢I陣：所有的非零元素集中在以主對角線為中心的帶狀區(qū)域中，即除了主對角線和主對角線相鄰兩側(cè)的若干條對角線上的元素之外，其余元素皆為零的矩陣為對角矩陣。*auiamanaiair-3tln-2m-3Sir-2n-|£inIn.-3fin-InT若|i-j|>(k-1)/2,則元素a”=0。對角矩陣可按行優(yōu)先順序或?qū)蔷€的順序,將其壓縮存儲到一個(gè)向量中，并且也能找到每個(gè)非零元素和向量下標(biāo)的對應(yīng)關(guān)系。12 .稀疏矢I陣：設(shè)矩陣A中有s個(gè)非零元素，若s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)(

54、即s<<m<n),則稱A為稀疏矩陣。為了節(jié)省存儲單元，可只存儲非零元素。由于非零元素的分布一般是沒有規(guī)律的，因此在存儲非零元素的同時(shí)，還必須存儲非零元素所在的行號、列號，才能迅速確定一個(gè)非零元素是矩陣中的哪一個(gè)元素。稀疏矩陣的壓縮存儲會失去隨機(jī)存取功能。其中每一個(gè)非零元素所在的行號、列號和值組成一個(gè)三元組(i,j,a”)，并由此三元組惟一確定。稀疏矩陣進(jìn)行壓縮存儲通常有兩類方法：順序存儲和鏈?zhǔn)酱鎯Α?3 .三元組表：將表示稀疏矩陣的非零元素的三元組按行優(yōu)先(或列優(yōu)先)的順序排列(跳過零元素)，并依次存放在向量中，這種稀疏矩陣的順序存儲結(jié)構(gòu)稱為三元組表。005Ax5=0-201

55、4 .壓縮存儲結(jié)構(gòu)上矩陣的轉(zhuǎn)置運(yùn)算,0Wi<m,0<j<n,即A的行是B一個(gè)mXn的矩陣A,它的轉(zhuǎn)置矩陣B是一個(gè)nXm的矩陣，且：Aij=Bji的列，A的列是B的行。三元組表表示的矩陣轉(zhuǎn)置的思想方法第一步：根據(jù)A矩陣的行數(shù)、列數(shù)和非零元總數(shù)確定B矩陣的列數(shù)、行數(shù)和非零元總數(shù)。第二步：當(dāng)三元組表非空(A矩陣的非零元不為0)時(shí)，根據(jù)A矩陣三元組表的結(jié)點(diǎn)空間data(以下簡稱為三元組表)，將A的三元組表a->data置換為B的三元組表b->data15 .三元組表的轉(zhuǎn)置：由于A的列是B的行，因此，按a->data的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置矩陣B的三元組表b->

56、data必定是按行優(yōu)先存放的。三元組表的轉(zhuǎn)置例:把50。A_1030久30-200_60。0轉(zhuǎn).置成-2000000。0J050080300b_按這種方法設(shè)計(jì)的算法，其基本思想是：對A中的每一列col(0<col<a->n-1),通過從頭至尾掃描三元組表a->data,找出所有列號等于col的那些三元組，將它們的行號和列號互換后依次放人b->data中，即可得到B的按行優(yōu)先的壓縮存貯表示。該算法的時(shí)間主要耗費(fèi)在col和p的二重循環(huán)上：若A的列數(shù)為n,非零元素個(gè)數(shù)t,則執(zhí)行時(shí)間為O(nxt),即與A的列數(shù)和非零元素個(gè)數(shù)的乘積成正比。通常用二維數(shù)組表示矩陣時(shí)，其轉(zhuǎn)置算法的執(zhí)行時(shí)間是O(nrKn),它正比于行數(shù)和列數(shù)的乘積。16 .帶行表的三元組表：為了方便某些矩陣運(yùn)算，在按行優(yōu)先存儲的三元組表中，加入一個(gè)行表來記錄稀疏矩陣中每行的非零元素在三元組表中的起始位置。這就是帶行表的三元組表。相應(yīng)的算法描述較為簡單，但這類順序存儲方式對于非零元的位置或個(gè)數(shù)經(jīng)常發(fā)生變化的矩陣運(yùn)算就顯得不太適合。17 .廣義表(Lists,又稱列表)是線性表的推廣。即廣義表中放松對表元素的原子限制，容許它們具有其自身結(jié)構(gòu)。廣義表是n(n>0)個(gè)元素ai,a2,a,an的有