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

1、WORD格式自考 02331 數(shù)據(jù)構(gòu)造重點(diǎn)總結(jié)( 最終修訂 )第一章概論1. 瑞士計算機(jī)科學(xué)家沃思提出：算法+數(shù)據(jù)構(gòu)造 =程序。算法是對數(shù)據(jù)運(yùn)算的描述，而數(shù)據(jù)構(gòu)造包括邏輯構(gòu)造和存儲構(gòu)造。由此可見，程序設(shè)計的實(shí)質(zhì)是針對實(shí)際問題選擇一種好的數(shù)據(jù)構(gòu)造和設(shè)計一個好的算法，而好的算法在很大程度上取決于描述實(shí)際問題的數(shù)據(jù)構(gòu)造。2. 數(shù)據(jù) 是信息的載體。 數(shù)據(jù)元素 是數(shù)據(jù)的根本單位。一個數(shù)據(jù)元素可以由假設(shè)干個 數(shù)據(jù)項 組成， 數(shù)據(jù)項 是具有獨(dú)立含義的最小標(biāo)識單位。 數(shù)據(jù)對象 是具有一樣性質(zhì)的數(shù)據(jù)元素的集合。3. 數(shù)據(jù)構(gòu)造 指的是數(shù)據(jù)元素之間的相互關(guān)系，即數(shù)據(jù)的組織形式。數(shù)據(jù)構(gòu)造一般包括以下三方面內(nèi)容：數(shù)據(jù)的

2、邏輯構(gòu)造、數(shù)據(jù)的存儲構(gòu)造、數(shù)據(jù)的運(yùn)算數(shù)據(jù)的邏輯構(gòu)造是從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)元素的存儲構(gòu)造無關(guān)，是獨(dú)立于計算機(jī)的。數(shù)據(jù)的邏輯構(gòu)造分類 : 線性構(gòu)造和非線性構(gòu)造。線性表 是一個典型的線性構(gòu)造。棧、隊列、串等都是線性構(gòu)造。數(shù)組、廣義表、樹和圖等數(shù)據(jù)構(gòu)造都是非線性構(gòu)造。數(shù)據(jù)元素及其關(guān)系在計算機(jī)內(nèi)的存儲方式，稱為數(shù)據(jù)的存儲構(gòu)造物理構(gòu)造 。數(shù)據(jù)的存儲構(gòu)造是邏輯構(gòu)造用計算機(jī)語言的實(shí)現(xiàn)，它依賴于計算機(jī)語言。 數(shù)據(jù)的運(yùn)算 。最常用的檢索、插入、刪除、更新、排序等。4. 數(shù)據(jù)的四種根本存儲方法 : 順序存儲、存儲、索引存儲、散列存儲（ 1順序存儲： 通常借助程序設(shè)計語言的 數(shù)組 描述。（ 2存儲： 通常借助

3、于程序語言的指針來描述。（ 3索引存儲： 索引表由假設(shè)干索引項組成。關(guān)鍵字是能唯一標(biāo)識一個元素的一個或多個數(shù)據(jù)項的組合。（ 4散列存儲： 該方法的根本思想是：根據(jù)元素的關(guān)鍵字直接計算出該元素的存儲地址。5. 算法必須滿足5 個準(zhǔn)那么： 輸入 ， 0 個或多個數(shù)據(jù)作為輸入；輸出 ，產(chǎn)生一個或多個輸出；有窮性 ，算法執(zhí)行有限步后完畢； 確定性 ，每一條指令的含義都明確；可行性 ，算法是可行的。算法與程序的區(qū)別：程序必須依賴于計算機(jī)程序語言，而一個算法可用自然語言、計算機(jī)程序語言、數(shù)學(xué)語言或約定的符號語言來描述。目前常用的描述算法語言有兩類：類Pascal 和類 C。6. 評價算法的優(yōu)劣：算法的 &

4、quot; 正確性 " 是首先要考慮的。此外，主要考慮如下三點(diǎn)： 執(zhí)行算法所消耗的時間，即時間復(fù)雜性； 執(zhí)行算法所消耗的存儲空間，主要是輔助空間，即空間復(fù)雜性； 算法應(yīng)易于理解、易于編程，易于調(diào)試等，即可讀性和可操作性。以上幾點(diǎn)最主要的是時間復(fù)雜性，時間復(fù)雜度常用漸進(jìn)時間復(fù)雜度表示。7. 算法求解問題的 輸入量 稱為問題的規(guī)模 , 用一個正整數(shù) n 表示。8.常見的時間復(fù)雜度按數(shù)量級遞增排列依次為：常數(shù)階 0(1) 、對數(shù)階 0(log 2n) 、線性階 0(n) 、線性對數(shù)階 0(nlog2n)、平方階 0(n 2) 立方階 0(n 3) 、 k 次方階 0(n k) 、指數(shù)階 0

5、(2 n) 和階乘階 0(n!)。9.一個算法的空間復(fù)雜度S(n) 定義為該算法所消耗的存儲空間，它是問題規(guī)模n 的函數(shù) , 它包括存儲算法本身所占的存儲空間、算法的輸入輸出數(shù)據(jù)所占的存儲空間和算法在運(yùn)行過程中臨時占用的存儲空間。第二章線性表1. 數(shù)據(jù)的運(yùn)算是定義在邏輯構(gòu)造上的，而運(yùn)算的具體實(shí)現(xiàn)是在存儲構(gòu)造上進(jìn)展的。2. 只要確定了線性表存儲的起始位置，線性表中任意一個元素都可隨機(jī)存取，所以順序表是一種隨機(jī)存取構(gòu)造。3. 常見的線性表的根本運(yùn)算 :(1) 置空表 InitList L 構(gòu)造一個空的線性表 L。(2) 求表長 ListLength L求線性表 L 中的結(jié)點(diǎn)個數(shù)，即求表長。(3)G

6、etNode L， i 取線性表L 中的第 i 個元素。(4)LocateNode L，x在 L 中查找第一個值為x 的元素，并返回該元素在L 中的位置。假設(shè)L 中沒有元素的值為x ，那么返回 0 值。(5)InsertListL，i ， x在線性表L 的第 i 個元素之前插入一個值為x 的新元素，表L 的長度加1。(6)DeleteListL，i刪除線性表L 的第 i 個元素，刪除后表L 的長度減1。4. 順序存儲方法：把線性表的數(shù)據(jù)元素按邏輯次序依次存放在一組地址連續(xù)的存儲單元里的方法。順序表 SequentialList ：用順序存儲方法存儲的線性表稱為順序表。順序表 是一種 隨機(jī)存取構(gòu)

7、造, 順序表的特點(diǎn)是邏輯上相鄰的結(jié)點(diǎn)其物理位置亦相鄰。順序表中結(jié)點(diǎn)ai的存儲地址 : LOC ai = LOCa1+ i-1 *c1i n，專業(yè)資料整理WORD格式- 1 -專業(yè)資料整理WORD格式5. 順序表上實(shí)現(xiàn)的根本運(yùn)算： 1插入： 該算法的平均時間復(fù)雜度是O(n) ，即在順序表上進(jìn)展插入運(yùn)算，平均要移動一半結(jié)點(diǎn)n/2 。在第 i 個位置插入一個結(jié)點(diǎn)的移動次數(shù)為n-i+1 2刪除 ：順序表上做刪除運(yùn)算，平均要移動表中約一半的結(jié)點(diǎn)n-1 /2 ，平均時間復(fù)雜度也是O(n) 。刪除第 i 個結(jié)點(diǎn)移動次數(shù)為n-i6. 采用鏈?zhǔn)酱鎯?gòu)造可以防止頻繁移動大量元素。一個單鏈表可由頭指針唯一確定，因此

8、單鏈表可以用頭指針的名字來命名。生成結(jié)點(diǎn)變量的標(biāo)準(zhǔn)函數(shù)p=(ListNode*)malloc(sizeof(ListNode)；/函數(shù) malloc分配一個類型為ListNode的結(jié)點(diǎn)變量的空間, 并將其首地址放入指針變量p 中釋放結(jié)點(diǎn)變量空間的標(biāo)準(zhǔn)函數(shù)free(p)； / 釋放 p 所指的結(jié)點(diǎn)變量空間結(jié)點(diǎn)分量的訪問方法二： p- data 和 p- next指針變量 p 和結(jié)點(diǎn)變量 *p 的關(guān)系 : 指針變量 p 的值結(jié)點(diǎn)地址 , 結(jié)點(diǎn)變量 *p 的值結(jié)點(diǎn)內(nèi)容 7. 建立單鏈表 : 1 頭插法建表： 算法： p=(ListNode *)malloc(sizeof(ListNode); / 生

9、成新結(jié)點(diǎn)p->data=ch; /將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中p->next=head;head=p; 2 尾插法建表： 算法：p=(ListNode *)malloc(sizeof(ListNode); / 生成新結(jié)點(diǎn)p->data=ch; /將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中if (head=NULL)head=p;/新結(jié)點(diǎn)插入空表else rear->next=p;/ 將新結(jié)點(diǎn)插到*r 之后rear=p; / 尾指針指向新表尾 3 尾插法建帶頭結(jié)點(diǎn)的單鏈表：頭結(jié)點(diǎn)及作用：頭結(jié)點(diǎn)是在鏈表的開場結(jié)點(diǎn)之前附加一個結(jié)點(diǎn)。它具有兩個優(yōu)點(diǎn):由于開場結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的

10、指針域中, 所以在鏈表的第一個位置上的操作就和在表的其它位置上操作一致 , 無須進(jìn)展特殊處理;無論鏈表是否為空，其頭指針都是指向頭結(jié)點(diǎn)的非空指針空表中頭結(jié)點(diǎn)的指針域空，因此空表和非空表的處理也就統(tǒng)一了。頭結(jié)點(diǎn)數(shù)據(jù)域的陰影表示該局部不存儲信息。 在有的應(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;專業(yè)資料整理WORD

11、格式- 2 -專業(yè)資料整理WORD格式r->next=NULL;/終端結(jié)點(diǎn)的指針域置空，或空表的頭結(jié)點(diǎn)指針域置空以上三個算法的時間復(fù)雜度均為O(n) 。8. 單鏈表上的查找： 帶頭結(jié)點(diǎn) 1按結(jié)點(diǎn)序號查找：序號為0 的是頭結(jié)點(diǎn)。算法： p=head;j=0;/從頭結(jié)點(diǎn)開場掃描while(p->next&&j<i)/順指針向后掃描，直到p->next為 NULL或 i=j為止p=p->next;j+;if(i=j) return p;/找到了第i 個結(jié)點(diǎn)else return NULL;/當(dāng) i<0 或 i>0 時，找不到第i 個結(jié)點(diǎn)時間復(fù)

12、雜度：在等概率假設(shè)下，平均時間復(fù)雜度為：為n/2=O(n) 2按結(jié)點(diǎn)值查找：具體算法： 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;/假設(shè)p=NULL，那么查找失敗，否那么p 指向值為 key 的結(jié)點(diǎn)時間復(fù)雜度為：O(n)9. 插入運(yùn)算：插入運(yùn)算是將值為x 的新結(jié)點(diǎn)插入到表的第i 個結(jié)點(diǎn)的位置上，即插入到ai-1與 ai之間。s=(ListNode *)

13、malloc(sizeof(ListNode);s->data=x; s->next=p->next; p->next=s;算法的時間主要消耗在查找結(jié)點(diǎn)上，故時間復(fù)雜度亦為O(n) 。10. 刪除運(yùn)算r=p->next; / 使 r 指向被刪除的結(jié)點(diǎn) ai p->next=r->next ;/ 將 ai從鏈上摘下 free(r); / 釋放結(jié)點(diǎn) ai的空間給存儲池算法的時間復(fù)雜度也是O n.p 指向被刪除的前一個結(jié)點(diǎn)。鏈表上實(shí)現(xiàn)的插入和刪除運(yùn)算，無須移動結(jié)點(diǎn)，僅需修改指針。11. 單循環(huán)鏈表在單鏈表中，將終端結(jié)點(diǎn)的指針域NULL 改為指向表頭結(jié)點(diǎn)或開場

14、結(jié)點(diǎn)即可。判斷空鏈表的條件是head=head->next;12. 僅設(shè)尾指針的單循環(huán)鏈表:用尾指針rear 表示的單循環(huán)鏈表對開場結(jié)點(diǎn)a1和終端結(jié)點(diǎn)an查找時間都是O(1) 。而表的操作常常是在表的首尾位置上進(jìn)展，因此，實(shí)用中多采用尾指針表示單循環(huán)鏈表。判斷空鏈表的條件為rear=rear->next;13. 循環(huán)鏈表： 循環(huán)鏈表的特點(diǎn)是無須增加存儲量，僅對表的方式稍作改變，即可使得表處理更加方便靈活。假設(shè)在尾指針表示的單循環(huán)鏈表上實(shí)現(xiàn)，那么只需修改指針，無須遍歷，其執(zhí)行時間是O(1) 。專業(yè)資料整理WORD格式- 3 -專業(yè)資料整理WORD格式具體算法：LinkList Con

15、nect(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指針。涉及遍歷操作時，其終止條件就不再是像非循環(huán)鏈表那樣判別p 或 p- next 是否為空，而是判別它們是否等于某一指定指針，如頭指針或尾指針等。在單鏈表中，從一結(jié)點(diǎn)出發(fā)，只能訪問到該結(jié)點(diǎn)及其后續(xù)

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

17、stNode *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 自身的操作專業(yè)資料整理WORD格式- 4 -專業(yè)資料整理WORD格式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

18、;/free(p); /與單鏈表上的插入和刪除操作不同的是，在雙鏈表中插入和刪除必須同時修改兩個方向上的指針。上述兩個算法的時間復(fù)雜度均為 O(1) 。16. 順序表和鏈表比較時間性能： a、線性表：經(jīng)常性的查找；b 、鏈?zhǔn)酱鎯?gòu)造：經(jīng)常插入刪除操作；空間性能： a、對數(shù)據(jù)量大小事先能夠知道的用線性表；b 、數(shù)據(jù)量變化較大的用鏈?zhǔn)酱鎯?gòu)造。存儲密度越大，存儲空間的利用率越高。顯然，順序表的存儲密度是1，鏈表的存儲密度肯定小于1。第三章棧和隊列1. 棧稱為 后進(jìn)先出 Last In First Out的線性表，簡稱為LIFO 表。棧是運(yùn)算受限的線性表，順序棧也是用數(shù)組表示的。進(jìn)棧操作： 進(jìn)棧時，

19、需要將S- top 加 1， S- top=StackSize-1表示棧滿 " 上溢 " 現(xiàn)象 - 當(dāng)棧滿時，再做進(jìn)棧運(yùn)算產(chǎn)生空間溢出的現(xiàn)象。退棧操作： 退棧時，需將S- top 減 1，S- top<0 表示空棧 " 下溢 " 現(xiàn)象 - 當(dāng)?？諘r，做退棧運(yùn)算產(chǎn)生的溢出現(xiàn)象。下溢是正常現(xiàn)象，常用作程序控制轉(zhuǎn)移的條件?？諚r棧頂指針不能是0，只能是 -1 。兩個棧共享同一存儲空間:當(dāng)程序中同時使用兩個棧時，可以將兩個棧的棧底分別設(shè)在順序存儲空間的兩端，讓兩個棧頂各自向中間延伸。當(dāng)一個棧中的元素較多而棧使用的空間超過共享空間的一半時，只要另一個棧的元素

20、不多，那么前者就可以占用后者的局部存儲空間。當(dāng) Top1=Top2-1 時，棧滿2. 為了抑制順序存儲分配固定空間所產(chǎn)生的溢出和空間浪費(fèi)問題。可采用鏈?zhǔn)酱鎯?gòu)造來存儲棧。鏈棧是沒有附加頭結(jié)點(diǎn)的運(yùn)算受限的單鏈表。 棧頂指針就是鏈表的頭指針 。鏈棧中的結(jié)點(diǎn)是動態(tài)分配的，所以可以不考慮上溢，無須定義StackFull運(yùn)算棧的一個重要應(yīng)用是實(shí)現(xiàn)遞歸， 直接調(diào)用自己或間接調(diào)用自己的函數(shù)。3. 隊列 Queue是只允許在一端進(jìn)展插入，而在另一端進(jìn)展刪除的運(yùn)算受限的線性表。允許刪除的一端稱為隊頭 Front ，允許插入的一端稱為隊尾Rear，當(dāng)隊列中沒有元素時稱為空隊列， 隊列亦稱作先進(jìn)先出FirstIn

21、FirstOut的線性表，簡稱為FIFO表。 隊列的順序存儲構(gòu)造稱為順序隊列，順序隊列實(shí)際上是一個受限的線性表。順序隊列的根本操作入隊時：將新元素插入rear所指的位置，然后將rear 加 1。出隊時：刪去front所指的元素，然后將front加 1 并返回被刪元素。專業(yè)資料整理WORD格式- 5 -專業(yè)資料整理WORD格式當(dāng)頭尾指針相等時，隊列為空。在非空隊列里，頭指針始終指向隊頭元素，而隊尾指針始終指向隊尾元素的下一位置。而棧頂指針指向棧頂元素。4. 循環(huán)隊列：為充分利用數(shù)組空間，抑制上溢，可將數(shù)組空間想象為一個環(huán)狀空間，并稱這種環(huán)狀數(shù)組表示的隊列為循環(huán)隊列。循環(huán)隊列中進(jìn)展出隊、入隊操作時

22、，頭尾指針仍要加1，朝前移動。只不過當(dāng)頭尾指針指向向量上界QueueSize-1 時，其加1 操作的結(jié)果是指向向量的下界0。這種循環(huán)意義下的加1 操作可以描述為： 方法一：if(i+1=QueueSize) i=0;/i表示 front或 rearelse i+;方法二 - 利用"模運(yùn)算 "i=(i+1)%QueueSize；循環(huán)隊列中，由于入隊時尾指針向前追趕頭指針；出隊時頭指針向前追趕尾指針，造成隊空和隊滿時頭尾指針均相等。因此，無法通過條件 Q.front=Q.rear 來判別隊列是 " 空 " 還是 " 滿 " 。解決這個問題

23、的方法至少有三種： 另設(shè)一個標(biāo)志位以區(qū)別隊列是空還是滿； 設(shè)置一個計數(shù)器記錄隊列中元素的總數(shù)即隊列長度。少用一個元素的空間。約定入隊前，測試尾指針在循環(huán)意義下加1 后是否等于頭指針，假設(shè)相等那么認(rèn)為隊列滿即尾指針Q.rear所指的單元始終為空。5. 循環(huán)隊列的根本運(yùn)算 :置隊空 :Q->front=Q->rear=0;判隊空 :return Q->rear=Q->front;判隊滿 :return (Q->rear+1)%QueueSize=Q->front;入隊Q->dataQ->rear=x;/新元素插入隊尾Q->rear=(Q->

24、;rear+1)%QueueSize;出隊temp=Q->dataQ->front;Q->front=(Q->front+1)%QueueSize;/循環(huán)意義下的頭指針加1return temp;取隊頭元素return Q->dataQ->front;6. 隊列的鏈?zhǔn)酱鎯?gòu)造簡稱為鏈隊列。它是限制僅在表頭刪除和表尾插入的單鏈表。為了簡化處理，在隊頭結(jié)點(diǎn)之前附加一個頭結(jié)點(diǎn)，并設(shè)隊頭指針指向此結(jié)點(diǎn)。鏈隊列的根本運(yùn)算: 帶頭結(jié)點(diǎn)（ 1 構(gòu)造空隊： Q->rear=Q->front ；Q->rear->next=NULL;（ 2 判隊空： r

25、eturn Q->rear=Q->front;專業(yè)資料整理WORD格式- 6 -專業(yè)資料整理WORD格式 3 入隊： QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode);/申請新結(jié)點(diǎn)p->data=x;p->next=NULL;Q->rear->next=p;/*p鏈到原隊尾結(jié)點(diǎn)后Q->rear=p;/隊尾指針指向新的尾（ 4 出隊：當(dāng)隊列長度大于 1 時，只需修改頭結(jié)點(diǎn)指針，尾指針不變 s=Q->front->next; Q->front->next=s->next;x=

26、s->data;free(s); return x;當(dāng)隊列長度等于1 時，不僅要修改頭結(jié)點(diǎn)指針，還要修改尾指針s=Q->front->next; Q->front->next=NULL;Q->rear=Q->front;x=s->data;free(s); return x; 5 取隊頭元素： return Q->front->next->data;因?yàn)橛蓄^結(jié)點(diǎn)，所以用了next和鏈棧類似，無須考慮判隊滿的運(yùn)算及上溢。在出隊算法中，一般只需修改隊頭指針。但當(dāng)原隊中只有一個結(jié)點(diǎn)時，該結(jié)點(diǎn)既是隊頭也是隊尾，故刪去此結(jié)點(diǎn)時亦需修改尾指

27、針，且刪去此結(jié)點(diǎn)后隊列變空。7. 用計算機(jī)來處理計算算術(shù)表達(dá)式問題，首先要解決的問題是如何將人們習(xí)慣書寫的中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式。第四章多維數(shù)組和廣義表1. 數(shù)組的順序存儲方式 : 一般采用順序存儲方法表示數(shù)組。 1行優(yōu)先順序a 11,a 12, ,a 1n,a 21 ,a 22 , ,a 2n, ， am1,a m2, ， amn 2列優(yōu)先順序a 11,a 21, ,a m1,a 12 ,a 22 , ,a m2, ， a1n,a 2n , ， amnPascal 和 C 語言是按行優(yōu)先順序存儲的，而Fortran語言是按列優(yōu)先順序存儲的。按行優(yōu)先順序存儲的二維數(shù)組Amn地址計算公式LO

28、C(aij )=LOC(a11)+(i-1) ×n+j - 1 ×d ( 注：此公式下界為1，如下界為0，那么公式變?yōu)閕 ×n+j )按列優(yōu)先順序存儲的二維數(shù)組Amn地址計算公式LOC(aij )=LOC(a11)+(j-1) ×m+i - 1 ×d( 注：此公式下界為1，如下界為0，那么公式變?yōu)?j × m+i)按行優(yōu)先順序存儲的三維數(shù)組Amnp地址計算公式LOC(aijk )=LOC(a111)+(i-1) ×n×p+(j- 1) ×p+k - 1 ×d ( 注 ： 此 公 式 下 界 為1

29、 ， 如 下 界 為0 ， 那么 公 式 變 為i ×n× p+j × p+k)2. 為了節(jié)省存儲空間，可以對矩陣中有許多值一樣或值為零的元素的矩陣，采用壓縮存儲。特殊矩陣是指一樣值的元素或零元素在矩陣中的分布有一定的規(guī)律。常見的有對稱矩陣、三角矩陣。 1對稱矩陣在一個 n 階方陣 A 中，假設(shè)元素滿足下述性質(zhì)：a ij =aji0i ，j n-1稱為 n 階對稱矩陣，它的元素是關(guān)于主對角線對稱的，所以只需要存儲矩陣上三角或下三角元素即可，讓兩個對稱的元素共享一個存儲空間。矩陣元素 aij和數(shù)組元素 sa 【 k】之間的關(guān)系是k=i ×(i+1)/2+j

30、ij 0k<n(n+1)/2-1k=j×(j+1)/2+i i j0k<n(n+1) /2-1對稱矩陣的地址計算公式：LOC(aij )=LOC(sa0)+I×(I+1)/ 2+J ×d，其中 I=max(i,j) ， J=min(i,j) 2三角矩陣： 以主對角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣是指它的下三角( 不包括主角線 )中的元素均為常數(shù)c 或零；下三角矩陣的主對角線上方均為常數(shù)c 或零。一般情況，三角矩陣的常數(shù)c 均為零。三角矩陣的壓縮存儲： 三角矩陣中的重復(fù)元素c 可共享一個存儲空間，其余的元素正好有n×(n+1)/

31、2 個，因此，三角矩陣可壓縮存儲在一維數(shù)組san(n+1)/2+1中，其中 c 存放在數(shù)組的最后一個元素中。上三角矩陣中a和 sak之間的對應(yīng)關(guān)系ijk=i ×(2n -i+1)/2+j-i當(dāng) i jk=n×(n+1)/2當(dāng) i j下三角矩陣中aij和 sak之間的對應(yīng)關(guān)系k=i ×(i+1) /2+j當(dāng) i jk=n×(n+1)/2當(dāng) i j三角矩陣的壓縮存儲構(gòu)造是隨機(jī)存取構(gòu)造。3. 稀疏矩陣 : 設(shè)矩陣 Amn中有 s 個非零元素，假設(shè) s 遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)，那么稱A 為稀疏矩陣。為了節(jié)省存儲單元，可用壓縮存儲方法只存儲非零元素。由于非零元素的

32、分布一般是沒有規(guī)律的，因此在存儲非零元素的同時，還必須存儲非零元素所在的行、列位置，所以可用三元組(i ， j ，aij ) 來確定非零元素。稀疏矩陣進(jìn)展壓縮存儲通常有兩類方法：順序存儲 ( 三元組表 ) 和鏈?zhǔn)酱鎯?( 十字鏈表 ) 。稀疏矩陣的壓縮存儲會失去隨機(jī)存取功能。專業(yè)資料整理WORD格式- 7 -專業(yè)資料整理WORD格式4. 廣義表是線性表的推廣 , 又稱列表。廣義表 是 n(n 0) 個元素 a1， a2， ai， an的有限序列。其中ai或者是原子或者是一個廣義表。廣義表通常用圓括號括起來，用逗號分隔其中的元素。為了區(qū)分原子和廣義表，書寫時用大寫字母表示廣義表 ，用小寫字母表示

33、 原子 。假設(shè)廣義表 Ls 非空 (n 1) ，那么 al是 LS 的表頭，其余元素組成的表(a 1， a2， an ) 稱為 Ls 的表尾。廣義表具有遞歸和共享的性質(zhì)廣義表的深度：一個表展開后所含括號的層數(shù)稱為廣義表的深度。19. 廣義表是一種多層次的線性構(gòu)造，實(shí)際上這就是一種樹形構(gòu)造。廣義表的兩個特殊的根本運(yùn)算： 取表頭 head(Ls)和取表尾 tail(Ls).任何一個非空廣義表的表頭可以是原子，也可以是子表，而其表尾必定是子表。head=(a ， b)=a ，tail(a， b)=(b)對非空表 A 和 (y) ，也可繼續(xù)分解。注意 : 廣義表 () 和()不同。前者是長度為0的空表

34、，對其不能做求表頭和表尾的運(yùn)算；而后者是長度為l 的由空表作元素的廣義表，可以分解得到的表頭和表尾均是空表() 。廣義表是一種有層次的非線性構(gòu)造，通常采用鏈?zhǔn)酱鎯?gòu)造，每個元素用一個結(jié)點(diǎn)表示，結(jié)點(diǎn)由3 個域構(gòu)成，其中一個是 tag 標(biāo)志位，用來區(qū)分結(jié)點(diǎn)是原子還是子表，當(dāng)tag 為零時結(jié)點(diǎn)是子表，第二個域?yàn)閟link，用以存放子表的地址；當(dāng) tag 為 1 時結(jié)點(diǎn)是原子，第二個域?yàn)閐ata ，用以存放元素值。第五章 樹和二叉樹1. 樹的表示法：最常用的是樹形圖表示法；還有3 種嵌套集合、凹形、廣義表。樹構(gòu)造的根本術(shù)語 1結(jié)點(diǎn)的度 (Degree)樹中的一個結(jié)點(diǎn)擁有的子樹數(shù)稱為該結(jié)點(diǎn)的度 (Deg

35、ree)。一棵樹的 度是指該樹中結(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)又稱為 開場結(jié)點(diǎn) 。 2路徑 path 假設(shè)樹中存在一個結(jié)點(diǎn)序列k ，k ， k，使得 k是 ki+1的雙親 (1 i<j)，那么稱該結(jié)點(diǎn)序列是12ii從 kl到 kj的一條 路徑 (Path) 。一個結(jié)點(diǎn)的祖先是從根結(jié)點(diǎn)到該結(jié)點(diǎn)路徑上所經(jīng)過的所有結(jié)點(diǎn)，而一個結(jié)點(diǎn)的子孫那么是以該結(jié)點(diǎn)為根的子樹中的所有結(jié)點(diǎn)。結(jié)點(diǎn)的層數(shù) (Level)從根起算：根的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)等于其雙親結(jié)點(diǎn)的層數(shù)加1。雙親在同一

36、層的結(jié)點(diǎn)互為堂兄弟 。樹中結(jié)點(diǎn)的最大層數(shù)稱為樹的高度 (Height)或深度 (Depth) 。假設(shè)將樹中每個結(jié)點(diǎn)的各子樹看成是從左到右有次序的( 即不能互換 ) ，那么稱該樹為有序樹 (OrderedTree)；否那么稱為 無序樹 (UnoderedTree) 。假設(shè)不特別指明，一般討論的樹都是有序樹。森林 (Forest)是 m(m0) 棵互不相交的樹的集合。樹和森林的概念相近。刪去一棵樹的根，就得到一個森林；反之，加上一個結(jié)點(diǎn)作樹根，森林就變?yōu)橐豢脴洹?. 二叉樹與度數(shù)為 2 的有序樹不同： 在有序樹中，雖然一個結(jié)點(diǎn)的孩子之間是有左右次序的，但是假設(shè)該結(jié)點(diǎn)只有一個孩子，就無須區(qū)分其左右次

37、序。而在二叉樹中，即使是一個孩子也有左右之分。二叉樹的性質(zhì)：性質(zhì) 1二叉樹第 i 層上的結(jié)點(diǎn)數(shù)目最多為 2i-1 (i 1) 。例如 5層的二叉樹，第 5 層上的結(jié)點(diǎn)數(shù)目最多為 24=16性質(zhì) 2k5深度為 k 的二叉樹至多有 2 -1 個結(jié)點(diǎn) (k 1) 。例如深度為 5 的二叉樹，至多有 2 -1=31 個結(jié)點(diǎn)性質(zhì) 3在任意 - 棵二叉樹中，假設(shè)終端結(jié)點(diǎn)的個數(shù)為n0，度為 2的結(jié)點(diǎn)數(shù)為 n2，那么 no=n2+1。例如一棵深度為4 的二叉專業(yè)資料整理WORD格式- 8 -專業(yè)資料整理WORD格式樹 a，其終端結(jié)點(diǎn)數(shù)n0為 8, 度為 2 的結(jié)點(diǎn)樹為7，那么 8=7+1， no=n2+1 成

38、立 b其終端結(jié)點(diǎn)數(shù)n0為 6, 度為 2 的結(jié)點(diǎn)樹為5，那么 6=5+1， no=n2+1 成立滿二叉樹：一棵深度為k 且有 2k -1 個結(jié)點(diǎn)的二又樹稱為滿二叉樹。滿二叉樹的特點(diǎn)：（ 1每一層上的結(jié)點(diǎn)數(shù)都到達(dá)最大值。即對給定的高度，它是具有最多結(jié)點(diǎn)數(shù)的二叉樹。（ 2滿二叉樹中不存在度數(shù)為1 的結(jié)點(diǎn)，每個分支結(jié)點(diǎn)均有兩棵高度一樣的子樹，且樹葉都在最下一層上。完全二叉樹：假設(shè)一棵深度為k 的二叉樹，其前k-1 層是一棵滿二叉樹，而最下面一層上的結(jié)點(diǎn)都集中在該層最左邊的假設(shè)干位置上，那么此二叉樹稱為完全二叉樹。特點(diǎn)：（ 1 滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。（ 2 在滿二叉樹的最下

39、一層上，從最右邊開場連續(xù)刪去假設(shè)干結(jié)點(diǎn)后得到的二叉樹仍然是一棵完全二叉樹。（ 3 在完全二叉樹中，假設(shè)某個結(jié)點(diǎn)沒有左孩子，那么它一定沒有右孩子，即該結(jié)點(diǎn)必是葉結(jié)點(diǎn)。性質(zhì) 4具有 n 個結(jié)點(diǎn)的完全二叉樹的深度為。"logn "+1 或"log(n+1)"例，具有100 個結(jié)點(diǎn)的完全二叉樹的深度為: "lg100 "+1=7,2 6=64 2 7=128 所以 "lg100 "=6,"lg(100+1) "=74. 完全二叉樹的編號特點(diǎn)：完全二叉樹中除最下面一層外，各層都充滿了結(jié)點(diǎn)。每一層的結(jié)點(diǎn)個數(shù)

40、恰好是上一層結(jié)點(diǎn)個數(shù)的2 倍。從一個結(jié)點(diǎn)的編號就可推得其雙親，左、右孩子等結(jié)點(diǎn)的編號。編號從0 開場假設(shè) i=0 ，那么 qi為根結(jié)點(diǎn)，無雙親；否那么，qi的雙親編號為 "(i-1)/2"。假設(shè) 2i+1<n ，那么 qi的左孩子的編號是2i+1 ；否那么， qi無左孩子，即qi必定是葉子。假設(shè) 2i+2<n ，那么 qi的右孩子的編號是2i+2 ；否那么， qi無右孩子。對于完全二叉樹而言，使用順序存儲構(gòu)造既簡單又節(jié)省存儲空間。但對于一般二叉樹來說，采用順序存儲時，為了使用結(jié)點(diǎn)在數(shù)組中的相對位置來表示結(jié)點(diǎn)之間的邏輯關(guān)系，就必須增加一些虛結(jié)點(diǎn)使其成為完全二叉樹的

41、形式。5.鏈?zhǔn)酱鎯?gòu)造 : 二叉樹的每個結(jié)點(diǎn)最多有兩個孩子。 用方式存儲二叉樹時， 每個結(jié)點(diǎn)除了存儲結(jié)點(diǎn)本身的數(shù)據(jù)外，還應(yīng)設(shè)置兩個指針域 lchild 和 rchild ，分別指向該結(jié)點(diǎn)的左孩子和右孩子。結(jié)點(diǎn)的構(gòu)造為：二叉鏈表是一種常用的二叉樹存儲構(gòu)造。建立二叉鏈表方法：a、按廣義表方法，靠近左括號的結(jié)點(diǎn)是在左子樹上，而逗號右邊結(jié)點(diǎn)是在右子樹上。b、按完全二叉樹的層次順序建立結(jié)點(diǎn)。具有 n 個結(jié)點(diǎn)的二叉鏈表中，共有2n 個指針域。其中有 n-1 個用來指示結(jié)點(diǎn)的左、右孩子，其余的n+1 個為空。二叉樹遍歷算法中的遞歸終止條件是二叉樹為空。中序遍歷的遞歸算法定義：(1)遍歷左子樹；(2)訪問根結(jié)

42、點(diǎn)；(3)遍歷右子樹。先序遍歷的遞歸算法定義：(1)訪問根結(jié)點(diǎn)；(2)遍歷左子樹；(3)遍歷右子樹。后序遍歷得遞歸算法定義：(1)遍歷左子樹；(2)遍歷右子樹；(3)訪問根結(jié)點(diǎn)。遞歸工作棧中包括兩項：一項為哪一項遞歸調(diào)用的語句編號，另一項那么是指向根結(jié)點(diǎn)的指針。一棵二叉樹的前序和中序遍歷序列或中序和后序遍歷序列，可唯一確定一棵二叉樹。具體方法如下：首先根據(jù)前序或后序遍歷序列確定二叉樹的各子樹的的根，然后根據(jù)中序遍歷序列確定各子樹根的左右子樹。6. 線索二叉樹： n 個結(jié)點(diǎn)的二叉鏈表必定存在n+1 個空指針域，可以利用這些空指針域，存放指向結(jié)點(diǎn)在某種遍歷次序下的前趨和后繼結(jié)點(diǎn)的指針，這種指向前驅(qū)

43、和后繼結(jié)點(diǎn)的指針稱為" 線索 " ，這種加上線索的二叉鏈表稱為線索鏈表 ，相應(yīng)的二叉樹稱為線索二叉樹 (ThreadedBinaryTree)。線索鏈表的結(jié)點(diǎn)構(gòu)造：其中 :ltag 和 rtag 是增加的兩個標(biāo)志域，用來區(qū)分結(jié)點(diǎn)的左、右指針域是指向其左、右孩子的指針，還是指向其前趨或后繼的線索。專業(yè)資料整理WORD格式- 9 -專業(yè)資料整理WORD格式圖中的實(shí)線表示指針，虛線表示線索。線索二叉樹中，一個結(jié)點(diǎn)是葉結(jié)點(diǎn)的充要條件為：左、右標(biāo)志均是1。7. 二叉樹的線索化:把對一棵二叉線索鏈表構(gòu)造中所有結(jié)點(diǎn)的空指針域按照某種遍歷次序加線索的過程稱為線索化。和中序遍歷算法一樣，遞歸

44、過程中對每結(jié)點(diǎn)僅做一次訪問。因此對于n 個結(jié)點(diǎn)的二叉樹，線索化的算法時間復(fù)雜度為 O(n) 。8. 樹、森林到二叉樹的轉(zhuǎn)換： 樹中每個結(jié)點(diǎn)最多只有一個最左邊的孩子( 長子 ) 和一個右鄰的兄弟。將樹轉(zhuǎn)換成二叉樹 ： 在所有兄弟結(jié)點(diǎn)之間加一道連線；對每個結(jié)點(diǎn)，除了保存與其長子的連線外，去掉該結(jié)點(diǎn)與其它孩子的連線。由于樹根沒有兄弟，故樹轉(zhuǎn)化為二叉樹后，二叉樹的根結(jié)點(diǎn)的右子樹必為空。將一個森林轉(zhuǎn)換為二叉樹:專業(yè)資料整理WORD格式-10-專業(yè)資料整理WORD格式將森林中的每棵樹轉(zhuǎn)化成二叉樹，然后再將二叉樹的根節(jié)點(diǎn)看做兄弟連在一起，形成一棵二叉樹9. 二叉樹到樹、森林的轉(zhuǎn)換 :方式是：假設(shè)二叉樹中結(jié)點(diǎn)

45、x 是雙親 y 的左孩子，那么把x 的右孩子，右孩子的右孩子，都與y 用連線連起來，最后去掉所有雙親到右孩子的連線。10. 樹的存儲構(gòu)造：1. 雙親表示法： 雙親鏈表表示法利用樹中每個結(jié)點(diǎn)的雙親唯一性，在存儲結(jié)點(diǎn)信息的同時，為每個結(jié)點(diǎn)附設(shè)一個指向其雙親的指針parent ，惟一地表示任何- 棵樹。 1雙親鏈表表示法的實(shí)現(xiàn)分析： E 和 F 所在結(jié)點(diǎn)的雙親域是 1，它們的雙親結(jié)點(diǎn)在向量中的位置是 1，即 B 是它們的雙親。注意：根無雙親，其parent域?yàn)?-1 。 雙親鏈表表示法中指針 parent 向上， 適合求指定結(jié)點(diǎn)的雙親或祖先 ( 包括根 ) ；求指定結(jié)點(diǎn)的孩子或其它后代時，可能要遍歷

46、整個數(shù)組。2. 孩子鏈表法： 孩子鏈表表示法是為樹中每個結(jié)點(diǎn)設(shè)置一個孩子鏈表，并將這些結(jié)點(diǎn)及相應(yīng)的孩子鏈表的頭指針存放在一個向量中。專業(yè)資料整理WORD格式-11-專業(yè)資料整理WORD格式注意： 孩子結(jié)點(diǎn)的數(shù)據(jù)域僅存放了它們在向量空間的序號。 與雙親鏈表表示法相反，孩子鏈表表示便于實(shí)現(xiàn)涉及孩子及其子孫的運(yùn)算，但不便于實(shí)現(xiàn)與雙親有關(guān)的運(yùn)算。 將雙親鏈表表示法和孩子鏈表表示法結(jié)合起來，可形成雙親孩子鏈表表示法。3. 孩子兄弟表示法： 在存儲結(jié)點(diǎn)信息的同時，附加兩個分別指向該結(jié)點(diǎn)最左孩子和右鄰兄弟的指針域，即可得樹的孩子兄弟鏈表表示。注意：這種存儲構(gòu)造的最大優(yōu)點(diǎn)是：它和二叉樹的二叉鏈表表示完全一樣。

47、可利用二叉樹的算法來實(shí)現(xiàn)對樹的操作。11. 樹的遍歷：一般都只給出兩種次序遍歷樹的方法：前序( 先根次序 ) 遍歷和后序 ( 后根次序 ) 遍歷。 前序遍歷一棵樹等價于前序遍歷該樹對應(yīng)的二叉樹 后序遍歷一棵樹等價于中序遍歷該樹對應(yīng)的二叉樹。對下面 (a) 圖中所示的森林進(jìn)展前序遍歷和后序遍歷，那么得到該森林的前序序列和后序序列分別為ABCDEFIGJH和BDCAIFJGHE。而 (b) 圖所示二叉樹的前序序列和中序序列也分別為ABCDEFIGJH和 BDCAIFJGHE。前序遍歷森林等同于前序遍歷該森林對應(yīng)的二叉樹后序遍歷森林等同于中序遍歷該森林對應(yīng)的二叉樹12. 從根結(jié)點(diǎn)到某結(jié)點(diǎn)之間的路徑長

48、度與該結(jié)點(diǎn)上權(quán)的乘積稱為該結(jié)點(diǎn)的帶權(quán)路徑長度，樹種所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和稱為樹的帶權(quán)路徑長度。帶權(quán)路徑長度WPL最小的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹。哈夫曼樹不一定是二叉樹。哈夫曼樹又稱為最優(yōu)樹，是一類帶權(quán)路徑長度最短 的樹。完全二叉樹就是這種路徑長度最短 的二叉樹。 只有葉結(jié)點(diǎn)上的權(quán)值均一樣時，完全二叉樹一定是最優(yōu)二叉樹，否那么完全二叉樹不一定是最優(yōu)二叉樹。最優(yōu)二叉樹中，權(quán)越大的葉子離根越近。 最優(yōu)二叉樹的形態(tài)不唯一，WPL最小。13. 哈夫曼算法 :根本思想是：(1) 根據(jù)給定的n 個權(quán)值 wl， w2， wn構(gòu)成 n 棵二叉樹的森林F=T1， T2， Tn ，其中每棵二叉樹Ti中

49、都只有一個權(quán)值為wi的根結(jié)點(diǎn)，其左右子樹均空。(2) 在森林 F 中選出兩棵根結(jié)點(diǎn)權(quán)值最小的樹( 當(dāng)這樣的樹不止兩棵樹時，可以從中任選兩棵) ，將這兩棵樹合并成一棵新樹，為了保證新樹仍是二叉樹，需要增加一個新結(jié)點(diǎn)作為新樹的根，并將所選的兩棵樹的根分別作為新根的左右孩子 ( 誰左，誰右無關(guān)緊要 ) ，將這兩個孩子的權(quán)值之和作為新樹根的權(quán)值。(3) 對新的森林 F 重復(fù) (2) ，直到森林 F 中只剩下一棵樹為止。這棵樹便是哈夫曼樹。注意：初始森林中的 n 棵二叉樹，每棵樹有一個孤立的結(jié)點(diǎn)，它們既是根，又是葉子 n 個葉子的哈夫曼樹要經(jīng)過n-1 次合并，產(chǎn)生n-1 個新結(jié)點(diǎn)。最終求得的哈夫曼樹中共有2n-1 個結(jié)點(diǎn)。哈夫曼樹是嚴(yán)格的二叉樹，沒有度數(shù)為1 的分支結(jié)點(diǎn)。專業(yè)資料整理WORD格式-12-專業(yè)資料整理WORD格式14. 哈夫曼編碼：數(shù)據(jù)壓縮過程稱為編碼,