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

1、專業(yè)好文檔自考數(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ù)的存儲(chǔ)結(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ù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn)，它依賴于計(jì)算機(jī)語言。數(shù)據(jù)的運(yùn)算，即對(duì)數(shù)據(jù)施加的操作。最常用的檢索、插入、刪除、更新、排序等。

2、6. 數(shù)據(jù)的邏輯結(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ù)的四種基本存儲(chǔ)方法: 順序存儲(chǔ)方法、鏈接存儲(chǔ)方法、索引存儲(chǔ)方法、散列存儲(chǔ)方法（1）順序存儲(chǔ)方法：該方法把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。通常借助程序語言的數(shù)組描述。（2）鏈接存儲(chǔ)方法：該方法不要求邏輯上相鄰的結(jié)點(diǎn)在

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

4、抽象數(shù)據(jù)的組織和與之相關(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ù)結(jié)構(gòu)=程序 數(shù)據(jù)結(jié)構(gòu)：是指數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu) 算法：是對(duì)數(shù)據(jù)運(yùn)算的描述10. 數(shù)據(jù)的運(yùn)算通過算法描述的。算法是任意一個(gè)良定義的計(jì)算過程。它以一個(gè)或多個(gè)值作為輸入，并產(chǎn)生一個(gè)或多個(gè)值作為輸出。若一個(gè)算法對(duì)于每個(gè)輸入實(shí)例均能終止并給出正確的結(jié)果，則稱該算法是正確的。正確的算法解決了給定的計(jì)算問題。11. 選用的算法首先應(yīng)該是

5、正確的。此外，主要考慮如下三點(diǎn)： 執(zhí)行算法所耗費(fèi)的時(shí)間； 執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間，其中主要考慮輔助存儲(chǔ)空間； 算法應(yīng)易于理解，易于編碼，易于調(diào)試等等。12. 一個(gè)算法所耗費(fèi)的時(shí)間=算法中每條語句的執(zhí)行時(shí)間之和，每條語句的執(zhí)行時(shí)間=語句的執(zhí)行次數(shù)(即頻度(frequency count)語句執(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í)(階)稱為算法的漸進(jìn)時(shí)間復(fù)雜度。平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例均以等

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

7、繼，有且僅有一個(gè)直接前趨an-1； 其余的內(nèi)部結(jié)點(diǎn)ai（2in-1）都有且僅有一個(gè)直接前趨ai-1和一個(gè)ai+1。3.常見的線性表的基本運(yùn)算:(1)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)，這里要求1ilistlength（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)insertlist（

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

9、的結(jié)點(diǎn)其物理位置亦相鄰。5.順序表中結(jié)點(diǎn)ai 的存儲(chǔ)地址: loc（ai）= loc（a1）+（i-1）*c 1in， 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í)，才無須移動(dòng)結(jié)點(diǎn)，直接將x插入表的末尾。具體算法：void insertlist(seqlist *l，datatype x，int i) /將新結(jié)點(diǎn)x插入l所指的順序表的第i個(gè)結(jié)點(diǎn)ai的位置上算法的時(shí)間主要花費(fèi)在for循環(huán)中的結(jié)點(diǎn)后

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

11、t i) /從l所指的順序表中刪除第i個(gè)結(jié)點(diǎn)ai結(jié)點(diǎn)的移動(dòng)次數(shù)由表長n和位置i決定：i=n時(shí)，結(jié)點(diǎn)的移動(dòng)次數(shù)為0，即為0(1)，i=1時(shí)，結(jié)點(diǎn)的移動(dòng)次數(shù)為n-1，算法時(shí)間復(fù)雜度分別是o(n)順序表上做刪除運(yùn)算，平均要移動(dòng)表中約一半的結(jié)點(diǎn)（n-1）/2，平均時(shí)間復(fù)雜度也是o(n)。7. 鏈接方式存儲(chǔ)的線性表簡稱為鏈表（linked list）。鏈表的具體存儲(chǔ)表示為：用一組任意的存儲(chǔ)單元來存放線性表的結(jié)點(diǎn)，鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同（這組存儲(chǔ)單元既可以是連續(xù)的，也可以是不連續(xù)的）。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其后繼結(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)的存儲(chǔ)地址是存放在其前趨結(jié)點(diǎn)next域中，而開始結(jié)點(diǎn)無前趨，故應(yīng)設(shè)頭指針head指向開始結(jié)點(diǎn)。終端結(jié)點(diǎn)無后繼，故終端結(jié)點(diǎn)的指針域?yàn)榭?，即null。9. 生成結(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;（2） 尾插法建表：從一個(gè)空表開始,重復(fù)讀入數(shù)據(jù),生成新結(jié)點(diǎn),將讀入數(shù)據(jù)存放在新結(jié)點(diǎn)的數(shù)據(jù)域中,然

14、后將新結(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)插入空表 else r-next=s;/將新結(jié)點(diǎn)插到*r之后 r=s;/尾指針指向新表尾（3） 尾插法建帶頭結(jié)點(diǎn)的單鏈表：頭結(jié)點(diǎn)及作用：頭結(jié)點(diǎn)是在鏈表的開始結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)。它具有兩個(gè)優(yōu)點(diǎn): 由于開始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中,所以在鏈表的第一個(gè)位置上的操作就和在表的其它位置上操作一致,無須進(jìn)行特殊處理; 無論鏈表是否

15、為空，其頭指針都是指向頭結(jié)點(diǎn)的非空指針（空表中頭結(jié)點(diǎn)的指針域空），因此空表和非空表的處理也就統(tǒng)一了。頭結(jié)點(diǎn)數(shù)據(jù)域的陰影表示該部分不存儲(chǔ)信息。在有的應(yīng)用中可用于存放表長等附加信息。具體算法：r=head; /尾指針初值也指向頭結(jié)點(diǎn) while(ch=getchar()!=n) s=(listnode *)malloc(sizeof(listnode);/生成新結(jié)點(diǎn) s-data=ch; /將讀入的數(shù)據(jù)放入新結(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）鏈表不是

16、隨機(jī)存取結(jié)構(gòu) 在鏈表中，即使知道被訪問結(jié)點(diǎn)的序號(hào)i，也不能像順序表中那樣直接按序號(hào)i訪問結(jié)點(diǎn)，而只能從鏈表的頭指針出發(fā)，順鏈域next逐個(gè)結(jié)點(diǎn)往下搜索，直至搜索到第i個(gè)結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。（2）查找的思想方法 計(jì)數(shù)器j置為0后，掃描指針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指針指為null且ji時(shí)，則表示找不到第i個(gè)結(jié)點(diǎn)。頭結(jié)點(diǎn)可看做是第0個(gè)結(jié)點(diǎn)。算法：p=head;j=0;/從頭結(jié)點(diǎn)開始掃描 while(p-next&jnext為null或i=j為止 p=p-next; j+;

17、if(i=j) return p;/找到了第i個(gè)結(jié)點(diǎn) else return null;/當(dāng)i0時(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(p&p-data!=key)/直到p為null或p-data為key為止 p=p-next;/掃描下一結(jié)點(diǎn) return p;/若p=null，則查找失敗，否則p指向值為key的結(jié)點(diǎn)時(shí)間復(fù)雜度為：o(n)12.插入運(yùn)算：插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到ai

18、-1與ai之間。具體步驟： （1）找到ai-1存儲(chǔ)位置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)ai。具體算法：p=getnode(head,i-1);/尋找第i-1個(gè)結(jié)點(diǎn) if (p=null)/in+1時(shí)插入位置i有錯(cuò) error(position error)； 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)刪去。具體

19、步驟： （1）找到ai-1的存儲(chǔ)位置p（因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)ai的存儲(chǔ)地址是在其直接前趨結(jié)點(diǎn)ai-1的指針域next中） （2）令p-next指向ai的直接后繼結(jié)點(diǎn)（即把a(bǔ)i從鏈上摘下） （3）釋放結(jié)點(diǎn)ai的空間，將其歸還給存儲(chǔ)池。具體算法：p=getnode(head,i-1);/找到第i-1個(gè)結(jié)點(diǎn) if (p=null|p-next=null)/in時(shí)，刪除位置錯(cuò) error(position error);/退出程序運(yùn)行 r=p-next;/使r指向被刪除的結(jié)點(diǎn)ai p-next=r-next;/將ai從鏈上摘下 free(r);/釋放結(jié)點(diǎn)ai的空間給存儲(chǔ)池算法的時(shí)間復(fù)雜度也是o（n）。

20、鏈表上實(shí)現(xiàn)的插入和刪除運(yùn)算，無須移動(dòng)結(jié)點(diǎn)，僅需修改指針。14.單循環(huán)鏈表在單鏈表中，將終端結(jié)點(diǎn)的指針域null改為指向表頭結(jié)點(diǎn)或開始結(jié)點(diǎn)即可。判斷空鏈表的條件是head=head-next;15. 僅設(shè)尾指針的單循環(huán)鏈表: 用尾指針rear表示的單循環(huán)鏈表對(duì)開始結(jié)點(diǎn)a1和終端結(jié)點(diǎn)an查找時(shí)間都是o(1)。而表的操作常常是在表的首尾位置上進(jìn)行，因此，實(shí)用中多采用尾指針表示單循環(huán)鏈表。判斷空鏈表的條件為rear=rear-next;16.循環(huán)鏈表：循環(huán)鏈表的特點(diǎn)是無須增加存儲(chǔ)量，僅對(duì)表的鏈接方式稍作改變，即可使得表處理更加方便靈活。若在尾指針表示的單循環(huán)鏈表上實(shí)現(xiàn)，則只需修改指針，無須遍歷，其執(zhí)行

21、時(shí)間是o(1)。具體算法：linklist connect(linklist a,linklist b) /假設(shè)a，b為非空循環(huán)鏈表的尾指針linklist p=a-next;/保存a表的頭結(jié)點(diǎn)位置 a-next=b-next-next;/b表的開始結(jié)點(diǎn)鏈接到a表尾 free(b-next);/釋放b表的頭結(jié)點(diǎn) b-next=p;/ return b;/返回新循環(huán)鏈表的尾指針循環(huán)鏈表中沒有null指針。涉及遍歷操作時(shí)，其終止條件就不再是像非循環(huán)鏈表那樣判別p或p-next是否為空，而是判別它們是否等于某一指定指針，如頭指針或尾指針等。在單鏈表中，從一已知結(jié)點(diǎn)出發(fā)，只能訪問到該結(jié)點(diǎn)及其后續(xù)結(jié)點(diǎn)，

22、無法找到該結(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)。17. 雙向鏈表: 雙（向）鏈表中有兩條方向不同的鏈，即每個(gè)結(jié)點(diǎn)中除next域存放后繼結(jié)點(diǎn)地址外，還增加一個(gè)指向其直接前趨的指針域prior。雙鏈表由頭指針head惟一確定的。帶頭結(jié)點(diǎn)的雙鏈表的某些運(yùn)算變得方便。將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來，為雙（向）循環(huán)鏈表。18.雙向鏈表的前插和刪除本結(jié)點(diǎn)操作雙鏈表的前插操作void dinsertbefore(dlistnode *p,datatype x)/在帶頭結(jié)點(diǎn)的雙鏈表中，將值為x的新結(jié)點(diǎn)插入*p之前，設(shè)pnull dlis

23、tnode *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自身的操作void ddeletenode(dlistnode *p) /在帶頭結(jié)點(diǎn)的雙鏈表中，刪除結(jié)點(diǎn)*p，設(shè)*p為非終端結(jié)點(diǎn) p-prior-next=p-next;/ p-next-prior=p-prior;/ free(p);/ 與單鏈表上的插入和刪除操作不同的是，在雙鏈表中插入和刪除必須同時(shí)修改兩個(gè)方向上的指針。上述兩個(gè)算法的時(shí)間復(fù)雜度均為o(1)。19.

24、 存儲(chǔ)密度（storage density）是指結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)量和整個(gè)結(jié)點(diǎn)結(jié)構(gòu)所占的存儲(chǔ)量之比，即,存儲(chǔ)密度=（結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)量）/（結(jié)點(diǎn)結(jié)構(gòu)所占的存儲(chǔ)總量）。 20.順序表和鏈表比較順序表和鏈表各有短長。在實(shí)際應(yīng)用中究竟選用哪一種存儲(chǔ)結(jié)構(gòu)呢？這要根據(jù)具體問題的要求和性質(zhì)來決定。通常有以下幾方面的考慮：順序表鏈表分配方式靜態(tài)分配。程序執(zhí)行之前必須明確規(guī)定存儲(chǔ)規(guī)模。若線性表長度n變化較大，則存儲(chǔ)規(guī)模難于預(yù)先確定估計(jì)過大將造成空間浪費(fèi)，估計(jì)太小又將使空間溢出機(jī)會(huì)增多。動(dòng)態(tài)分配只要內(nèi)存空間尚有空閑，就不會(huì)產(chǎn)生溢出。因此，當(dāng)線性表的長度變化較大，難以估計(jì)其存儲(chǔ)規(guī)模時(shí)，以采用動(dòng)態(tài)鏈表作為

25、存儲(chǔ)結(jié)構(gòu)為好。存儲(chǔ)密度為1。當(dāng)線性表的長度變化不大，易于事先確定其大小時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序表作為存儲(chǔ)結(jié)構(gòu)。1存取方式隨機(jī)存取結(jié)構(gòu)，對(duì)表中任一結(jié)點(diǎn)都可在o（1）時(shí)間內(nèi)直接取得線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時(shí)，采用順序表做存儲(chǔ)結(jié)構(gòu)為宜。順序存取結(jié)構(gòu)，鏈表中的結(jié)點(diǎn)，需從頭指針起順著鏈掃描才能取得。插入刪除操作在順序表中進(jìn)行插入和刪除，平均要移動(dòng)表中近一半的結(jié)點(diǎn)，尤其是當(dāng)每個(gè)結(jié)點(diǎn)的信息量較大時(shí)，移動(dòng)結(jié)點(diǎn)的時(shí)間開銷就相當(dāng)可觀。在鏈表中的任何位置上進(jìn)行插入和刪除，都只需要修改指針。對(duì)于頻繁進(jìn)行插入和刪除的線性表，宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。若表的插入和刪除主要發(fā)生在表的首尾兩端，則

26、采用尾指針表示的單循環(huán)鏈表為宜第三章 棧1. 棧（stack）是限制僅在表的一端進(jìn)行插入和刪除運(yùn)算的線性表。(1)通常稱插入、刪除的這一端為棧頂（top），另一端稱為棧底（bottom）。(2)當(dāng)表中沒有元素時(shí)稱為空棧。(3)棧為后進(jìn)先出（last in first out）的線性表，簡稱為lifo表。 棧的修改是按后進(jìn)先出的原則進(jìn)行。每次刪除（退棧）的總是當(dāng)前棧中最新的元素，即最后插入（進(jìn)棧）的元素，而最先插入的是被放在棧的底部，要到最后才能刪除。2.順序棧：棧的順序存儲(chǔ)結(jié)構(gòu)簡稱為順序棧,它是運(yùn)算受限的順序表。順序棧中元素用向量存放棧底位置是固定不變的，可設(shè)置在向量兩端的任意一個(gè)端點(diǎn)棧頂位置

27、是隨著進(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-topfront=q-rear=0;q-count=0; 判隊(duì)空:return q-count=0; 判隊(duì)滿:return q-count=queuesize; 入隊(duì)q-count +; /隊(duì)列元素個(gè)數(shù)加1q-dataq-rear=x; /新元素插入隊(duì)尾q-rear=(q-rear+1)%queuesize; 出隊(duì)temp=q

28、-dataq-front;q-count-; /隊(duì)列元素個(gè)數(shù)減1q-front=(q-front+1)%queuesize; /循環(huán)意義下的頭指針加1return temp;取隊(duì)頭元素return q-dataq-front;11. 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡稱為鏈隊(duì)列。它是限制僅在表頭刪除和表尾插入的單鏈表。鏈隊(duì)列的基本運(yùn)算:（1） 置空隊(duì)：q-front=q-rear=null;（2） 判隊(duì)空：return q-front=null&q-rear=null;（3） 入隊(duì)：queuenode *p=(queuenode *)malloc(sizeof(queuenode);/申請(qǐng)新結(jié)點(diǎn) p-dat

29、a=x; p-next=null; if(queueempty(q) q-front=q-rear=p; /將x插入空隊(duì)列 else /x插入非空隊(duì)列的尾 q-rear-next=p; /*p鏈到原隊(duì)尾結(jié)點(diǎn)后 q-rear=p; /隊(duì)尾指針指向新的尾（4） 出隊(duì)：p=q-front; /指向?qū)︻^結(jié)點(diǎn) x=p-data; /保存對(duì)頭結(jié)點(diǎn)的數(shù)據(jù) q-front=p-next; /將對(duì)頭結(jié)點(diǎn)從鏈上摘下 if(q-rear=p)/原隊(duì)中只有一個(gè)結(jié)點(diǎn)，刪去后隊(duì)列變空，此時(shí)隊(duì)頭指針已為空 q-rear=null; free(p); /釋放被刪隊(duì)頭結(jié)點(diǎn) return x; /返回原隊(duì)頭數(shù)據(jù)（5） 取隊(duì)頭元素

30、：if(queueempty(q) error(queue if empty.); return q-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)將會(huì)為調(diào)用

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

32、nk string）。 和分別表示長度為1的空白串和長度為0的空串。3. 串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串。包含子串的串相應(yīng)地稱為主串?？沾侨我獯淖哟?任意串是其自身的子串。4. 通常在程序中使用的串可分為：串變量和串常量。串變量和其它類型的變量一樣，其取值是可以改變的。串常量和整常數(shù)、實(shí)常數(shù)一樣，在程序中只能被引用但不能改變其值。即只能讀不能寫。5.串的基本運(yùn)算：求串長：int strlen(char *s);/求串s的長度串復(fù)制：char *strcpy(char *to,*from)；/將from串復(fù)制到to串中，并返回to開始處指針聯(lián)接：char *strcat(cha

33、r *to,char *from);/將from串復(fù)制到to串的末尾， /并返回to串開始處的指針串比較：int strcmp(char *s1,char *s2);/比較s1和s2的大小， /當(dāng)s1s2和s1=s2時(shí)，分別返回小于0、大于0和等于0的值【例】result=strcmp(baker,baker); /result0 result=strcmp(12,12); /result=0 result=strcmp(joe,joseph) /result0字符定位：char *strchr(char *s,char c);/找c在字符串s中第一次出現(xiàn)的位置， /若找到，則返回該位置，否則

34、返回null6. 串的順序存儲(chǔ)結(jié)構(gòu)簡稱為順序串。 與順序表類似，順序串是用一組地址連續(xù)的存儲(chǔ)單元來存儲(chǔ)串中的字符序列。按其存儲(chǔ)分配的不同可將順序串分為如下兩類：（1）靜態(tài)存儲(chǔ)分配的順序串 串值空間的大小在編譯時(shí)刻就已確定，是靜態(tài)的。難以適應(yīng)插入、鏈接等操作直接使用定長的字符數(shù)組存放串內(nèi)容外，一般可使用一個(gè)不會(huì)出現(xiàn)在串中的特殊字符放在串值的末尾來表示串的結(jié)束。所以串空間最大值為maxstrsize時(shí)，最多只能放maxstrsize-1個(gè)字符。c語言中以字符0表示串值的終結(jié)。 （2）動(dòng)態(tài)存儲(chǔ)分配的順序串:順序串的字符數(shù)組空間可使用c語言的malloc和free等動(dòng)態(tài)存儲(chǔ)管理函數(shù)，來根據(jù)實(shí)際需要?jiǎng)討B(tài)

35、地分配和釋放。7. 用單鏈表方式存儲(chǔ)串值，串的這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡稱為鏈串。鏈串和單鏈表的差異僅在于其結(jié)點(diǎn)數(shù)據(jù)域?yàn)閱蝹€(gè)字符：一個(gè)鏈串由頭指針唯一確定。鏈串的結(jié)點(diǎn)大小:為了提高存儲(chǔ)密度，可使每個(gè)結(jié)點(diǎn)存放多個(gè)字符。當(dāng)結(jié)點(diǎn)大小大于1時(shí)，串的長度不一定正好是結(jié)點(diǎn)大小的整數(shù)倍，因此要用特殊字符來填充最后一個(gè)結(jié)點(diǎn)，以表示串的終結(jié)。雖然提高結(jié)點(diǎn)的大小使得存儲(chǔ)密度增大，但是做插入、刪除運(yùn)算時(shí)，可能會(huì)引起大量字符的移動(dòng)，給運(yùn)算帶來不便。8. 子串定位運(yùn)算又稱串的模式匹配或串匹配。子串定位運(yùn)算類似于串的基本運(yùn)算中的字符定位運(yùn)算。只不過是找子串而不是找字符在主串中首次出現(xiàn)的位置。此運(yùn)算的應(yīng)用非常廣泛。在串匹配中，一般

36、將主串稱為目標(biāo)（串），子串稱為模式（串）。串匹配就是對(duì)于合法的位置（又稱合法的位移）0in-m，依次將目標(biāo)串中的子串titi+1ti+m-1和模式串p0p1p2pm-1進(jìn)行比較：若titi+1ti+m-1p0p1p2pm-1，則稱從位置i開始的匹配成功，或稱i為有效位移。若titi+1ti+m-1p0p1p2pm-1，則稱從位置i開始的匹配失敗，或稱i為無效位移。因此，串匹配問題可簡化為找出某給定模式串p在給定目標(biāo)串t中首次出現(xiàn)的有效位移。有些應(yīng)用中要求求出p在t中所有出現(xiàn)的有效位移。9.樸素的串匹配算法的基本思想：即用一個(gè)循環(huán)來依次檢查n-m+1個(gè)合法的位移i（0in-m）是否為有效位移。順

37、序串上的串匹配算法：最壞時(shí)間復(fù)雜度：為o(n-m+1)m)。模式匹配算法的改進(jìn)：樸素的串匹配算法雖然簡單，但效率低。其原因是在檢查位移i是否為有效位移時(shí)，沒有利用檢查位移i-1，i,0時(shí)的部分匹配結(jié)果。 若利用部分匹配結(jié)果，模式串右滑動(dòng)的距離就不會(huì)是每次一位，而是每次使其向右滑動(dòng)得盡可能遠(yuǎn)。這樣可使串匹配算法的最壞時(shí)間控制在o（m+n）數(shù)量級(jí)上。鏈串上的子串定位運(yùn)算：用結(jié)點(diǎn)大小為1的單鏈表做串的存儲(chǔ)結(jié)構(gòu)時(shí)，實(shí)現(xiàn)樸素的串匹配算法很簡單。只是現(xiàn)在的位移shift是結(jié)點(diǎn)地址而非整數(shù)，且單鏈表中沒有存儲(chǔ)長度信息。若匹配成功，則返回有效位移所指的結(jié)點(diǎn)地址，否則返回指針。第五章 多維數(shù)組和廣義表1. 多維

38、數(shù)組和廣義表是一種復(fù)雜的非線性結(jié)構(gòu)，它們的邏輯特征是：一個(gè)數(shù)據(jù)元素可能有多個(gè)直接前驅(qū)和多個(gè)直接后繼。2. 一維數(shù)組（向量）是存儲(chǔ)于計(jì)算機(jī)的連續(xù)存儲(chǔ)空間中的多個(gè)具有統(tǒng)一類型的數(shù)據(jù)元素。同一數(shù)組的不同元素通過不同的下標(biāo)標(biāo)識(shí)。 （a1,a2,an)3. 二維數(shù)組amn可視為由m個(gè)行向量組成的向量，或由n個(gè)列向量組成的向量。二維數(shù)組中的每個(gè)元素aij既屬于第i行的行向量，又屬于第j列的列向量。4. 多維數(shù)組: 三維數(shù)組amnp可視為以二維數(shù)組為數(shù)據(jù)元素的向量。四維數(shù)組可視為以三維數(shù)組為數(shù)據(jù)元素的向量 三維數(shù)組中的每個(gè)元素aijk都屬于三個(gè)向量。四維數(shù)組中的每個(gè)元素都屬于四個(gè)向量5. 數(shù)組的順序存儲(chǔ)方式

39、: 由于計(jì)算機(jī)內(nèi)存是一維的，多維數(shù)組的元素應(yīng)排成線性序列后存人存儲(chǔ)器。數(shù)組一般不做插入和刪除操作，即結(jié)構(gòu)中元素個(gè)數(shù)和元素間關(guān)系不變化。一般采用順序存儲(chǔ)方法表示數(shù)組。（1）行優(yōu)先順序：將數(shù)組元素按行向量排列，第i+1個(gè)行向量緊接在第i個(gè)行向量后面。【例】二維數(shù)組amn的按行優(yōu)先存儲(chǔ)的線性序列為： a11,a12,a1n,a21,a22,a2n,，am1,am2,，amn（2）列優(yōu)先順序 將數(shù)組元素按列向量排列，第i+1個(gè)列向量緊接在第i個(gè)列向量后面?！纠慷S數(shù)組amn的按列優(yōu)先存儲(chǔ)的線性序列為： a11,a21,am1,a12,a22,am2,，a1n,a2n,，amn6.數(shù)組元素的地址計(jì)算公

40、式:（1）按行優(yōu)先順序存儲(chǔ)的二維數(shù)組amn地址計(jì)算公式 loc(aij)=loc(a11)+(i-1)n+j-1d (注：此公式下界為1，如下界為0，則公式變?yōu)閕n+j) loc(a11)是開始結(jié)點(diǎn)的存放地址（即基地址） d為每個(gè)元素所占的存儲(chǔ)單元數(shù) 由地址計(jì)算公式可得，數(shù)組中任一元素可通過地址公式在相同時(shí)間內(nèi)存取。即順序存儲(chǔ)的數(shù)組是隨機(jī)存取結(jié)構(gòu)。（2）按列優(yōu)先順序存儲(chǔ)的二維數(shù)組amn地址計(jì)算公式loc(aij)=loc(a11)+(j-1)m+i-1d(注：此公式下界為1，如下界為0，則公式變?yōu)閖m+i)（3）按行優(yōu)先順序存儲(chǔ)的三維數(shù)組amnp地址計(jì)算公式 loc(aijk)=loc(a11

41、1)+(i-1)np+(j-1)p+k-1d(注：此公式下界為1，如下界為0，則公式變?yōu)閕np+jp+k)（4）下界不為1的二維數(shù)組的地址計(jì)算公式二維數(shù)組ac1.d1,c2.d2的地址計(jì)算公式： loc(aij)=loc(ac1c2)+(i-c1)(d2-c2+1)+j-c2d 下界為0的二維數(shù)組的地址計(jì)算公式（c語言中使用） loc(aij)=loc(a00)+i(d2+1)+jd7. 矩陣用二維數(shù)組描述時(shí)，存儲(chǔ)的密度為1?？梢詫?duì)其元素進(jìn)行隨機(jī)存取，各種矩陣運(yùn)算也非常簡單。矩陣的壓縮：矩陣中非零元素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況下，為了節(jié)省存儲(chǔ)空間，我們可以對(duì)這類矩陣進(jìn)行壓縮

42、存儲(chǔ)：即為多個(gè)相同的非零元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。8. 所謂特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣。常見的有對(duì)稱矩陣、三角矩陣和對(duì)角矩陣等。（1）對(duì)稱矩陣 在一個(gè)n階方陣a中，若元素滿足下述性質(zhì)： aij=aji 0i，jn-1（2）對(duì)稱矩陣的壓縮存儲(chǔ)對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱，故只要存儲(chǔ)矩陣中上三角或下三角中的元素，讓每兩個(gè)對(duì)稱的元素共享一個(gè)存儲(chǔ)空間。這樣，能節(jié)約近一半的存儲(chǔ)空間。按行優(yōu)先順序存儲(chǔ)主對(duì)角線(包括對(duì)角線)以下的元素（下三角矩陣中，元素總數(shù)為n(n+1)/2）。即按a00,a10,a11,，an-1,0,an-1,1，an-1,n-1次序存放在

43、一個(gè)向量sa0n(n+1)/2-1中sa0=a00 ,sa1=a10 ,san(n+1)/2-1= an-1,n-1元素aij的存放位置:sai(i+1)/2+j=aijaij和sak之間的對(duì)應(yīng)關(guān)系：令i=max(i,j)，j=min(i,j)，則k和i，j的對(duì)應(yīng)關(guān)系可統(tǒng)一為： k=i(i+1)/2+j 0k(k-1)2，則元素aij=0。對(duì)角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲(chǔ)到一個(gè)向量中，并且也能找到每個(gè)非零元素和向量下標(biāo)的對(duì)應(yīng)關(guān)系。12. 稀疏矩陣:設(shè)矩陣amn中有s個(gè)非零元素，若s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)(即smn)，則稱a為稀疏矩陣。為了節(jié)省存儲(chǔ)單元，可只存儲(chǔ)非零元素。由于非

44、零元素的分布一般是沒有規(guī)律的，因此在存儲(chǔ)非零元素的同時(shí)，還必須存儲(chǔ)非零元素所在的行號(hào)、列號(hào)，才能迅速確定一個(gè)非零元素是矩陣中的哪一個(gè)元素。稀疏矩陣的壓縮存儲(chǔ)會(huì)失去隨機(jī)存取功能。其中每一個(gè)非零元素所在的行號(hào)、列號(hào)和值組成一個(gè)三元組(i，j，aij)，并由此三元組惟一確定。稀疏矩陣進(jìn)行壓縮存儲(chǔ)通常有兩類方法：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。13. 三元組表：將表示稀疏矩陣的非零元素的三元組按行優(yōu)先(或列優(yōu)先)的順序排列(跳過零元素)，并依次存放在向量中，這種稀疏矩陣的順序存儲(chǔ)結(jié)構(gòu)稱為三元組表。14.壓縮存儲(chǔ)結(jié)構(gòu)上矩陣的轉(zhuǎn)置運(yùn)算一個(gè)mn的矩陣a，它的轉(zhuǎn)置矩陣b是一個(gè)nm的矩陣，且：aij=bji，0im，0jd

45、ata置換為b的三元組表b-data15.三元組表的轉(zhuǎn)置: 由于a的列是b的行，因此，按a-data的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置矩陣b的三元組表b-data必定是按行優(yōu)先存放的。 按這種方法設(shè)計(jì)的算法，其基本思想是：對(duì)a中的每一列col(0cola-n-1)，通過從頭至尾掃描三元組表a-data，找出所有列號(hào)等于col的那些三元組，將它們的行號(hào)和列號(hào)互換后依次放人b-data中，即可得到b的按行優(yōu)先的壓縮存貯表示。該算法的時(shí)間主要耗費(fèi)在col和p的二重循環(huán)上：若a的列數(shù)為n，非零元素個(gè)數(shù)t，則執(zhí)行時(shí)間為o(nt)，即與a的列數(shù)和非零元素個(gè)數(shù)的乘積成正比。通常用二維數(shù)組表示矩陣時(shí)，其轉(zhuǎn)置算法的執(zhí)行時(shí)間是o(mn)，它正比于行數(shù)和列數(shù)的乘積。16.帶行表的三元組表: 為了方便某些矩陣運(yùn)算，在按行優(yōu)先存儲(chǔ)的三元組表中，加入一個(gè)行表來記錄稀疏矩陣中每行的非零元素在三元組表中的起始位置。這就是帶行表的三元組表。相應(yīng)的算法描述較為簡單，但這類順序存儲(chǔ)方式對(duì)于非