?

第一章 數(shù)據(jù)結(jié)構(gòu)概述

?

基本概念與術(shù)語(yǔ)

1．數(shù)據(jù)：數(shù)據(jù)是對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序所處理的符號(hào)的總稱。

?

2.數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，是數(shù)據(jù)這個(gè)集合中的個(gè)體，也稱之為元素，結(jié)點(diǎn)，頂點(diǎn)記錄。

??（補(bǔ)充：一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。）

?

3．?dāng)?shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。（有時(shí)候也叫做屬性。）

?

4．數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

（1）數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間存在的固有邏輯關(guān)系，常稱為數(shù)據(jù)結(jié)構(gòu)。

數(shù)據(jù)的邏輯結(jié)構(gòu)是從數(shù)據(jù)元素之間存在的邏輯關(guān)系上描述數(shù)據(jù)與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。

依據(jù)數(shù)據(jù)元素之間的關(guān)系，可以把數(shù)據(jù)的邏輯結(jié)構(gòu)分成以下幾種：

1.集合：數(shù)據(jù)中的數(shù)據(jù)元素之間除了“同屬于一個(gè)集合“的關(guān)系以外，沒(méi)有其他關(guān)系。

2.線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在“一對(duì)一“的關(guān)系。若結(jié)構(gòu)為非空集合，則除了第一個(gè)元素之外，和最后一個(gè)元素之外，其他每個(gè)元素都只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。

3.樹(shù)形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在“一對(duì)多“的關(guān)系。若數(shù)據(jù)為非空集，則除了第一個(gè)元素（根）之外，其它 ??????每個(gè)數(shù)據(jù)元素都只有一個(gè)直接前驅(qū)，以及多個(gè)或零個(gè) ??直接后繼。

4.圖狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素存在“多對(duì)多”的關(guān)系。若結(jié)構(gòu)為非空集，折每個(gè)數(shù)據(jù)可有多個(gè)（或零個(gè)）直接后繼。

?

（2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)內(nèi)的表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。

想要計(jì)算機(jī)處理數(shù)據(jù)，就必須把數(shù)據(jù)的邏輯結(jié)構(gòu)映射為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。邏輯結(jié)構(gòu)可以映射為以下兩種存儲(chǔ)結(jié)構(gòu)：

1.順序存儲(chǔ)結(jié)構(gòu)：把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理位置也相鄰的存儲(chǔ)單元中，借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)之間的邏輯關(guān)系。

2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：借助指針表達(dá)數(shù)據(jù)元素之間的邏輯關(guān)系。不要求邏輯上相鄰的數(shù)據(jù)元素物理位置上也相鄰。

?

5.時(shí)間復(fù)雜度分析：1.常量階：算法的時(shí)間復(fù)雜度與問(wèn)題規(guī)模n無(wú)關(guān)系T(n)=O(1)

??????????????????2.線性階：算法的時(shí)間復(fù)雜度與問(wèn)題規(guī)模n成線性關(guān)系T(n)=O(n)

??????????????????3.平方階和立方階：一般為循環(huán)的嵌套，循環(huán)體最后條件為i++

時(shí)間復(fù)雜度的大小比較：

O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n )<O(n!)<O(n n)

?

6.算法與程序：

（1）算法的5個(gè)特性

1、 輸入：有零個(gè)或多個(gè)輸入

2、 輸出：有一個(gè)或多個(gè)輸出

3、有窮性：要求序列中的指令是有限的；每條指令的執(zhí)行包含有限的工作量；整個(gè)指令序列的執(zhí)行在有限的時(shí)間內(nèi)結(jié)束。（程序與算法的區(qū)別在于，程序不需要有有窮性）

4、確定性：算法中的每一個(gè)步驟都必須是確定的，而不應(yīng)當(dāng)含糊、模棱兩可。沒(méi)有歧義。

5、可行性：算法中的每一個(gè)步驟都應(yīng)當(dāng)能被有效的執(zhí)行，并得到確定的結(jié)果。

（2）.算法設(shè)計(jì)的要求：

???????????????1、正確性（達(dá)到預(yù)期效果，滿足問(wèn)題需求）

???????????????2、健壯性（能處理合法數(shù)據(jù)，也能對(duì)不合法的數(shù)據(jù)作出反應(yīng)，不會(huì)產(chǎn)生不可預(yù)期的后果）

???????????????3、可讀性（要求算法易于理解，便于分析）

???????????????4、可修改可擴(kuò)展性

???????????????5、高效率（較好的時(shí)空性能 ）

?

?

補(bǔ)充內(nèi)容：

1、名詞解釋：數(shù)據(jù)結(jié)構(gòu)、二元組

數(shù)據(jù)結(jié)構(gòu)就是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

二元組就是一種用來(lái)表示某個(gè)數(shù)據(jù)對(duì)象以及各個(gè)元素之間關(guān)系的有限集合。

2、根據(jù)數(shù)據(jù)元素之間關(guān)系的不同，數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為集合、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)四種類型。

3、常見(jiàn)的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)一般有兩種類型，它們分別是順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

6.在一般情況下，一個(gè)算法的時(shí)間復(fù)雜度是問(wèn)題規(guī)模的函數(shù)

?

7.常見(jiàn)時(shí)間復(fù)雜度有：常數(shù)階O（1）、線性階O（n）、對(duì)數(shù)階O（log 2 n）、平方階O(n^2)、指數(shù)階O(2^n)。通常認(rèn)為，具有常數(shù)階量級(jí)的算法是好算法，而具有指數(shù)階量級(jí)的算法是差算法。

?

第二章 線性表

定義：線性表是n個(gè)數(shù)據(jù)元素的有限序列。 ?一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。

?

1. 順序表結(jié)構(gòu)

線性表的順序存儲(chǔ)是指在內(nèi)存中用地址連續(xù)的一塊存儲(chǔ)空間順序存放線性表的各元素，用這種存儲(chǔ)形式存儲(chǔ)的線性表稱為順序表。

?

2. 單鏈表

（1） 鏈表結(jié)點(diǎn)結(jié)構(gòu)

線性表中的數(shù)據(jù)元素可以用任意的一組存儲(chǔ)單元來(lái)存儲(chǔ)，用指針表示邏輯關(guān)系邏輯相鄰的兩元素的存儲(chǔ)空間可以是不連續(xù)的。

?

（2） 鏈表操作算法：初始化、插入、輸出、刪除、遍歷

初始化：p=(struct student *)malloc(sizeof(struct student));

插入： p->next=head->next; ?head->next=p;

輸出：printf(“%d”,p->data);

刪除：q=p->next; ?p->next = q->next ; ?free(q);

結(jié)點(diǎn)遍歷： for(p=head;p;p=p->next);

?

補(bǔ)充內(nèi)容：

1、線性表中，第一個(gè)元素沒(méi)有直接前驅(qū)，最后一個(gè)元素沒(méi)有直接后驅(qū)。

2、在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)是q所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，則刪除結(jié)點(diǎn)q的操作語(yǔ)句為

??P->next = q->next ; ?free(q);

3、在長(zhǎng)度為N的順序表中，插入一個(gè)新元素平均需要移動(dòng)表中N/2個(gè)元素，刪除一個(gè)元素平均需要移動(dòng)（N-1）/2個(gè)元素。

4、若線性表的主要操作是在最后一個(gè)元素之后插入一個(gè)元素或刪除最后一個(gè)元素，則采用順序表存儲(chǔ)結(jié)構(gòu)最節(jié)省運(yùn)算時(shí)間。

5、已知順序表中每個(gè)元素占用3個(gè)存儲(chǔ)單元，第13個(gè)元素的存儲(chǔ)地址為336，則順序表的首地址為300。（第n個(gè)元素的地址即首地址+(n-1)*每個(gè)元素的存儲(chǔ)空間，如a[12]（第13個(gè)元素）的地址=a[0]+12*3）

6、設(shè)有一帶頭結(jié)點(diǎn)單鏈表L，請(qǐng)編寫(xiě)該單鏈表的初始化，插入、輸出和刪除函數(shù)。（函數(shù)名自定義）

結(jié)點(diǎn)定義：

typedef int datatype; //結(jié)點(diǎn)數(shù)據(jù)類型，假設(shè)為int

typedef struct node { ? //結(jié)點(diǎn)結(jié)構(gòu)

???datatype data;

??struct node *next;???????????//雙向鏈表還應(yīng)加上*previous

} Lnode, * pointer ; //結(jié)點(diǎn)類型,結(jié)點(diǎn)指針類型

typedef pointer lklist; //單鏈表類型，即頭指針類型

?

?

1.初始化：

lklist initlist() {

???pointer head;

???head=new node;//這是C++做法

???//head=(?pointer)malloc(sizeof(Lnode)); ??????這是C語(yǔ)言做法

???head->next=NULL;??????????????//循環(huán)鏈表則是head->next=head;

//雙向鏈表應(yīng)加上head->previos=NULL;

???return head;

}

2.插入：（C語(yǔ)言中需要把head轉(zhuǎn)化為全局變量才能實(shí)現(xiàn)此程序）

int insert(lklist head,datatype x,int i){

??pointer q,s;

??q=get(head,i-1); //找第i-1個(gè)點(diǎn)

??if(q==NULL) ?? //無(wú)第i-1點(diǎn)，即i<1或i>n+1時(shí)

{

cout<<”非法插入位置!\n”; //這是C++做法，即C語(yǔ)言中的 ?printf(“非法插入位置!\n”);

return 0;

}

??s=new node;//生成新結(jié)點(diǎn) ??即C語(yǔ)言中的 ?s=(?pointer)malloc(sizeof(Lnode));

??s->data=x;

??s->next=q->next; ?//新點(diǎn)的后繼是原第i個(gè)點(diǎn)

??q->next=s; ?//原第i-1個(gè)點(diǎn)的后繼是新點(diǎn)

??return 1; ?//插入成功

}

3.刪除：（C語(yǔ)言中需要把head轉(zhuǎn)化為全局變量才能實(shí)現(xiàn)此程序）

int delete(lklist head,int i) {

??pointer p,q;

??q=get(head,i-1); ? //找待刪點(diǎn)的直接前趨

??if(q==NULL || q->next==NULL) //即i<1或i>n時(shí)

????{cout<<”非法刪除位置!\n”;return 0;}

??p=q->next; ? ?//保存待刪點(diǎn)地址

??q->next=p->next; ? //修改前趨的后繼指針

??delete p; ? ?//釋放結(jié)點(diǎn) ????即C語(yǔ)言中的 free(p);

??return 1; ? ?//刪除成

?

1. 不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是(A )

A. ?head=NULL ?B. ?head->next=NULL ?C. ?head->next=head ??D. ?head!=NULL

2. 帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是(B )

A. ?head=NULL ?B. ?head->next=NULL ?C. ?head->next=head ?D. ?head!=NULL

3. 在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行(B )

A. ?s->next=p; ?p->next=s; ???B. ?s->next=p->next; ?p->next=s;

C. ?s->next=p->next; ?p=s; ???D. ?p->next=s; ?s->next=p;

4. 在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行(A )

A. ?p->next=p->next->next;

B. ?p=p->next; ?p->next=p->next->next;

C. ?p->next=p->next

D. ?p=p->next->next

5. 從一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較（B ）個(gè)結(jié)點(diǎn)。

A. n ????B. n/2 ???C. (n-1)/2 ?????D. O(n㏒2n) ???

6. 給定有n個(gè)元素的向量，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度（B）

A.O(1) ?B.O(n) ??C.O(n2) ???D.O(n㏒2n)

7.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是(B)

A.O(1) ?B.O(n) ??C.O(n2) ???D.O(n㏒2n)

8. 在一個(gè)單鏈表中刪除q所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行如下操作：

q=p->next; ???

p->next=( p->next->next ); ??

free(q);//這種題目靠一根指針是沒(méi)有辦法完成的，必須要借助第二根指針。

9. 在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行：

s->next=( p->next )

?p->next=(s)操作。

10. 對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的單鏈表 ,在已知所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是(O（1）)；在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是（O(n)）。

11.問(wèn)答題

線性表可用順序表或鏈表存儲(chǔ)。試問(wèn)：

?

(1) 兩種存儲(chǔ)表示各有哪些主要優(yōu)缺點(diǎn)?

順序表的存儲(chǔ)效率高，存取速度快。但它的空間大小一經(jīng)定義，在程序整個(gè)運(yùn)行期間不會(huì)發(fā)生改變，因此，不易擴(kuò)充。同時(shí)，由于在插入或刪除時(shí)，為保持原有次序，平均需要移動(dòng)一半(或近一半)元素，修改效率不高。

鏈接存儲(chǔ)表示的存儲(chǔ)空間一般在程序的運(yùn)行過(guò)程中動(dòng)態(tài)分配和釋放，且只要存儲(chǔ)器中還有空間，就不會(huì)產(chǎn)生存儲(chǔ)溢出的問(wèn)題。同時(shí)在插入和刪除時(shí)不需要保持?jǐn)?shù)據(jù)元素原來(lái)的物理順序，只需要保持原來(lái)的邏輯順序，因此不必移動(dòng)數(shù)據(jù)，只需修改它們的鏈接指針，修改效率較高。但存取表中的數(shù)據(jù)元素時(shí)，只能循鏈順序訪問(wèn)，因此存取效率不高。

?

?(2) 若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素，這時(shí)，應(yīng)采用哪種存儲(chǔ)表示？為什么？

應(yīng)采用順序存儲(chǔ)表示。因?yàn)轫樞虼鎯?chǔ)表示的存取速度快，但修改效率低。若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素，這時(shí)采用順序存儲(chǔ)表示較好。

?

第三章 棧和隊(duì)列

?

1. 棧

（1） 棧的結(jié)構(gòu)與定義

定義：限定僅在表尾進(jìn)行插入或刪除操作的線性表。

結(jié)構(gòu)：

typedef ?struct list{

?????int listsize; ?????????//棧的容量

?????struct list *head; ????//棧頂指針

?????struct list *base; ????//棧底指針

}

?

（2） 順序棧操作算法：入棧、出棧、判斷?？盏龋ㄟ@個(gè)是使用數(shù)組進(jìn)行操作的，具體內(nèi)容參照書(shū)本P46-47）

（3） 鏈棧的結(jié)構(gòu)與定義

2. 隊(duì)列

（1） 隊(duì)列的定義

定義：只允許在表的一端進(jìn)行插入，而在另一端刪除元素。

----------------------------------------------------------------------------------------------------------------

補(bǔ)充內(nèi)容：

1、一個(gè)棧的入棧序列為“ABCDE”，則以下不可能的出棧序列是（B）

A. BCDAE ? B. EDACB ? C. BCADE ? D. AEDCB

2、棧的順序表示中，用TOP表示棧頂元素，那么?？盏臈l件是（D）

A. TOP==STACKSIZE ?B. TOP==1 ?C. TOP==0 ?D. TOP==-1

3、允許在一端插入，在另一端刪除的線性表稱為隊(duì)列。插入的一端為表頭，刪除的一端為表尾。

4、棧的特點(diǎn)是先進(jìn)后出，隊(duì)列的特點(diǎn)是先進(jìn)先出。

5、對(duì)于棧和隊(duì)列，無(wú)論他們采用順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，進(jìn)行插入和刪除操作的時(shí)間復(fù)雜度都是O(1)（即與已有元素N無(wú)關(guān)）。

6、已知鏈棧Q，編寫(xiě)函數(shù)判斷?？眨绻麠？談t進(jìn)行入棧操作，否則出棧并輸出。（要求判斷?？铡⒊鰲?、入棧用函數(shù)實(shí)現(xiàn)）（詳看考點(diǎn)2）

7.出隊(duì)與取隊(duì)頭元素的區(qū)別：出隊(duì)就是刪除對(duì)頭的數(shù)據(jù)元素，取隊(duì)頭元素是獲取對(duì)頭的數(shù)據(jù)元素值，不需要?jiǎng)h除。

8.鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是：（D）

A.插入操作比較容易 ??????????B.刪除操作比較容易 ??

C.不會(huì)出現(xiàn)?？盏那闆r ????????D.不會(huì)出現(xiàn)棧滿的情況

?

考點(diǎn)1：隊(duì)列的編程：

結(jié)構(gòu)：

typedef struct QNode{

????????int date;

????????struct QNode *next;

????????}QNode,*QueuePtr;

typedef struct{

????????QueuePtr front;

????????QueuePtr rear;

????????}LinkQueue;

?

創(chuàng)建：

LinkQueue InitQueue(LinkQueue Q)

{

???????Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

???????Q.front->next=NULL;

???????return (Q);

}

入隊(duì)：

LinkQueue EnQueue(LinkQueue Q,int e)

{

???????QueuePtr p;

???????p=(QueuePtr)malloc(sizeof(QNode));

???????

???????p->date=e;

???????p->next=NULL;

???????Q.rear->next=p;

???????Q.rear=p;

???????return (Q);

???????}

出隊(duì)：

LinkQueue DeQueue(LinkQueue Q)

{

???????int e;

???????QueuePtr p;

???????

???????p=Q.front->next;

???????e=p->date;

???????Q.front=p->next;

???????printf("%d",e);

???????if(Q.rear==p)Q.rear=Q.front=NULL;

???????free(p);

???????return (Q);

}

???????

考點(diǎn)2：棧的編程：

創(chuàng)建：

struct list *creat()

{

???struct list *p;

???p=(struct list *)malloc(LEN);

???p->next=NULL;

???return(p);

}

?

入棧：

struct list *push(struct list *head,int a)

{

??struct list *p;

??p=(struct list *)malloc(LEN);

??p->num=a;

??p->next=head;

??return(p);

}

?

出棧：

struct list *pop(struct list *head)

{

???struct list *p;

???p=head->next;

???free(head);

???return(p);

}

?

判斷棧空：

int listempty(struct list *head)

{

if(head->next)return 0;

else return 1;

}

?

?

第四章 串 （不是重點(diǎn)內(nèi)容）

1.串是由零個(gè)或多個(gè)字符組成的有限序列

2.串的賦值：x=’abc’;或x[ ]=’abc’;

?

?

第五章 數(shù)組和廣義表 （不是重點(diǎn)內(nèi)容）

1. 多維數(shù)組中某數(shù)組元素的position求解。一般是給出數(shù)組元素的首元素地址和每個(gè)元素占用的地址空間并組給出多維數(shù)組的維數(shù)，然后要求你求出該數(shù)組中的某個(gè)元素所在的位置。

2. 明確按行存儲(chǔ)和按列存儲(chǔ)的區(qū)別和聯(lián)系，并能夠按照這兩種不同的存儲(chǔ)方式求解1中類型的題。

3. 將特殊矩陣中的元素按相應(yīng)的換算方式存入數(shù)組中。這些矩陣包括：對(duì)稱矩陣，三角矩陣，具有某種特點(diǎn)的稀疏矩陣等。熟悉稀疏矩陣的三種不同存儲(chǔ)方式：三元組，帶輔助行向量的二元組，十字鏈表存儲(chǔ)。掌握將稀疏矩陣的三元組或二元組向十字鏈表進(jìn)行轉(zhuǎn)換的算法。

?

補(bǔ)充內(nèi)容：

三元組：

結(jié)構(gòu)：

typedef struct{

????????int i,j; ?????//元素行下標(biāo)及列下標(biāo)

????????int e; ??????//元素值

????????}Triple;

typedef struct{

????????int mu,nu,tu; ?????????????????//矩陣的行數(shù)、列數(shù)、非零元素個(gè)數(shù)

????????Triple data[MAXSIZE+1]; ??????//矩陣包含的三元組表，data[0]未用

????????}TSMatrix;

?

十字鏈表：

typedef struct?OLNode{

????????int i,j; ?????//元素行下標(biāo)及列下標(biāo)

????????int e; ??????//元素值

????????struct?OLNode *right,*down; ?//行的后繼以及列的后繼

????????}?OLNode，*OLink;

typedef struct{

????????int mu,nu,tu; ?????????????????//矩陣的行數(shù)、列數(shù)、非零元素個(gè)數(shù)

????????OLink ?*rhead,*chead; ??????//行和列的表頭指針組的首地址

????????}CrossList;

?

CrossList Creat（CrossList M）{

????????int m,n,t;

????????scanf(“%d%d%d”,&m,&n,&t);

????????M.mu=m;M.nu=n;M.tu=t;

????????M.rhead=( OLink *)malloc((m+1)*sizeof(OLink)); ??//開(kāi)辟行表頭指針組

????????M.chead=( OLink *)malloc((n+1)*sizeof(OLink)); ??//開(kāi)辟行列頭指針組

????????M.rhead[]=M.chead[]=NULL; ??????????????????//初始化

????????…… ??????????????????????????????????????//接下來(lái)就是賦值和入鏈

｝

?

第六章 樹(shù)和二叉樹(shù)

?

1． 樹(shù)

（1） 樹(shù)的概念及術(shù)語(yǔ)

樹(shù)：n（n≥0）個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n＝0時(shí)，稱為空樹(shù)；任意一棵非空樹(shù)滿足以下條件：

⑴ 有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；

⑵ 當(dāng)n＞1時(shí)，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成m（m>0）個(gè)互不相交的有限集合T1,T2,… ,Tm，其中每個(gè)集合又是一棵樹(shù)，并稱為這個(gè)根結(jié)點(diǎn)的子樹(shù)。

（2） ???結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)。

樹(shù)的度：樹(shù)中所有結(jié)點(diǎn)的度的最大值。

（3） ??葉子結(jié)點(diǎn)：度為0的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。

分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。

（4）孩子、雙親：樹(shù)中某結(jié)點(diǎn)的子樹(shù)的根結(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)稱為它孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)；

兄弟： ?????具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱為兄弟。

（5）路徑： 如果樹(shù)的結(jié)點(diǎn)序列n1, n2, …, nk有如下關(guān)系：結(jié)點(diǎn)ni是ni+1的雙親（1<=i<k），則把n1, n2, …, nk稱為一條由n1至nk的路徑；路徑上經(jīng)過(guò)的邊的個(gè)數(shù)稱為路徑長(zhǎng)度。

（6）祖先、子孫：在樹(shù)中，如果有一條路徑從結(jié)點(diǎn)x到結(jié)點(diǎn)y，那么x就稱為y的祖先，而y稱為x的子孫。

（7）結(jié)點(diǎn)所在層數(shù)：根結(jié)點(diǎn)的層數(shù)為1；對(duì)其余任何結(jié)點(diǎn)，若某結(jié)點(diǎn)在第k層，則其孩子結(jié)點(diǎn)在第k+1層。

樹(shù)的深度： ????樹(shù)中所有結(jié)點(diǎn)的最大層數(shù)，也稱高度。

（8）層序編號(hào)：將樹(shù)中結(jié)點(diǎn)按照從上層到下層、同層從左到右的次序依次給他們編以從1開(kāi)始的連續(xù)自然數(shù)。

（9）有序樹(shù)、無(wú)序樹(shù)：如果一棵樹(shù)中結(jié)點(diǎn)的各子樹(shù)從左到右是有次序的，稱這棵樹(shù)為有序樹(shù)；反之，稱為無(wú)序樹(shù)。數(shù)據(jù)結(jié)構(gòu)中討論的一般都是有序樹(shù)

（10）樹(shù)通常有前序（根）遍歷、后序（根）遍歷和層序（次）遍歷三種方式（樹(shù)，

不是二叉樹(shù)，沒(méi)中序遍歷。)

?

2． 二叉樹(shù)

（1）二叉樹(shù)的定義：二叉樹(shù)是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集（稱為空二叉樹(shù)），或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。

?

滿二叉樹(shù)：在一棵二叉樹(shù)中，如果所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子都在同一層上。

（滿二叉樹(shù)的特點(diǎn)：葉子只能出現(xiàn)在最下一層；只有度為0和度為2的結(jié)點(diǎn)。）

???

完全二叉樹(shù)：對(duì)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)按層序編號(hào)，如果編號(hào)為i（1≤i≤n）的結(jié)點(diǎn)與同樣深度的滿二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)在二叉樹(shù)中的位置完全相同。

完全二叉樹(shù)的特點(diǎn)：

1.在滿二叉樹(shù)中，從最后一個(gè)結(jié)點(diǎn)開(kāi)始，連續(xù)去掉任意個(gè)結(jié)點(diǎn)，即是一棵完全二叉樹(shù)。

2.葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層，且最下層的葉子結(jié)點(diǎn)都集中在二叉樹(shù)的左部；

3. 完全二叉樹(shù)中如果有度為1的結(jié)點(diǎn)，只可能有一個(gè)，且該結(jié)點(diǎn)只有左孩子。

4. 深度為k的完全二叉樹(shù)在k-1層上一定是滿二叉樹(shù)。

?

（3）二叉樹(shù)的性質(zhì)：

性質(zhì)1：二叉樹(shù)的第i層上最多有2i-1個(gè)結(jié)點(diǎn)（i≥1）。

性質(zhì)2： 一棵深度為k的二叉樹(shù)中，最多有2k-1個(gè)結(jié)點(diǎn)，最少有k個(gè)結(jié)點(diǎn)。深度為k且具有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)一定是滿二叉樹(shù)

性質(zhì)3：在一棵二叉樹(shù)中，如果葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則有: n0＝n2＋1。（一個(gè)結(jié)點(diǎn)的度就是指它放出的射線）

性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 log2n ?+1。

性質(zhì)5： 對(duì)一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中從1開(kāi)始按層序編號(hào)，則對(duì)于任意的序號(hào)為i（1≤i≤n）的結(jié)點(diǎn)（簡(jiǎn)稱為結(jié)點(diǎn)i），有：

（1）如果i＞1，則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)的序號(hào)為 ?i/2；如果i＝1，則結(jié)點(diǎn)i是根結(jié)點(diǎn)，無(wú)雙

親結(jié)點(diǎn)。

（2）如果2i≤n，則結(jié)點(diǎn)i的左孩子的序號(hào)為2i；如果2i＞n，則結(jié)點(diǎn)i無(wú)左孩子。

（3）如果2i＋1≤n，則結(jié)點(diǎn)i的右孩子的序號(hào)為2i＋1；如果2i＋1＞n，則結(jié)點(diǎn) i無(wú)右孩子。

?

???????????????????

3． 二叉樹(shù)的遍歷（遞歸調(diào)用與訪問(wèn)的順序不同而產(chǎn)生不同的遍歷方法）

（1） 先序遍歷

void XianXu(BiTree T){

??if(T){

?????printf("%c",T->data);????????//先訪問(wèn)

?????XianXu(T->lchild);?????????//再繼續(xù)遍歷

?????XianXu(T->rchild);

??}

}

（2） 中序遍歷

（3） 后序遍歷

4. 森林與二叉樹(shù)的轉(zhuǎn)換

??（1）同級(jí)以左為親，即左一結(jié)點(diǎn)的右孩子是與它同級(jí)的右一結(jié)點(diǎn)

??（2）只認(rèn)最左路線為親子路線，即結(jié)點(diǎn)的左孩子是它下一級(jí)結(jié)點(diǎn)的最左的元素

5. 哈夫曼樹(shù)

（1）哈夫曼樹(shù)的基本概念：

哈夫曼樹(shù)：給定一組具有確定權(quán)值的葉子結(jié)點(diǎn)，帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)。

（2）哈夫曼樹(shù)的特點(diǎn)：

1. 權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。

2. 只有度為0（葉子結(jié)點(diǎn)）和度為2（分支結(jié)點(diǎn)）的結(jié)點(diǎn)，不存在度為1的結(jié)點(diǎn).

（3）哈夫曼樹(shù)的構(gòu)造算法思想及構(gòu)造過(guò)程（森林與哈夫曼編碼）

就是求各權(quán)值和路徑相乘之后疊加的最小值。

----------------------------------------------------------------------------------------------------------------------

?

1、已知一棵完全二叉樹(shù)有47個(gè)結(jié)點(diǎn)，則該二叉樹(shù)有（C）個(gè)葉子結(jié)點(diǎn)。

A. 6 ?B. 12 C. 24 D.48

解法如下：

1+2+4+8+16=31 ??????????????計(jì)算從第一層到n-1層的結(jié)點(diǎn)個(gè)數(shù)

47-31=16 ????????????????????計(jì)算第n層的葉子結(jié)點(diǎn)個(gè)數(shù)

16-16/2=8 ???????????????????計(jì)算第n-1層的葉子結(jié)點(diǎn)個(gè)數(shù)

所以，葉子結(jié)點(diǎn)數(shù)=16+8=24 ???計(jì)算第n層和第n-1層的總?cè)~子結(jié)點(diǎn)數(shù)

2、已知遍歷一棵二叉樹(shù)的前序序列ABCDEFG和中序序列CBEDAFG，那么是下面哪棵樹(shù)（C ）。

C圖如下：

????????????????????????????????????????A

????????????????????????????????????↙??????↘

??????????????????????????????????B ???????????F

??????????????????????????????↙?????↘????????????↘

????????????????????????????C ?????????D ????????????G

?????????????????????????????????????↙

??????????????????????????????????E

????????????????????????????????????????????????????

?

4、完全二叉樹(shù)必須滿足的條件為: ：一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，它的結(jié)構(gòu)與滿二叉樹(shù)的前n個(gè)結(jié)點(diǎn)的的結(jié)構(gòu)相同。

?

5、哈夫曼樹(shù)不存在度為1的結(jié)點(diǎn)。

?

6、有5個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為2，5，3，7，11，根據(jù)哈夫曼算法構(gòu)建該樹(shù)，并計(jì)算該樹(shù)的帶權(quán)路徑長(zhǎng)度。（構(gòu)建哈夫曼樹(shù)，很簡(jiǎn)單，從小開(kāi)始，計(jì)算相加，然后把所有葉子結(jié)點(diǎn)乘以等級(jí)數(shù)字然后相加。也即是：帶權(quán)路徑長(zhǎng)度=葉結(jié)點(diǎn)的權(quán)值*路徑長(zhǎng)度）

?

7.試找出分別滿足下列條件的所有二叉樹(shù)：

⑴ 前序序列和中序序列相同：只有右子樹(shù)

⑵ 中序序列和后序序列相同：只有左子樹(shù)

⑶ 前序序列和后序序列相同：只有根，空二叉樹(shù)

?

?

第七章 圖

?

1.?圖的基本概念：圖的基本術(shù)語(yǔ)及推論

圖的結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)。

設(shè)圖有n個(gè)頂點(diǎn)，則：

有1/2 n(n-1)條邊的無(wú)向圖稱為完全圖

有n（n-1）條弧的有向圖稱為有向完全圖

元素被多少條弧的箭頭所指，它的入度就為多少；反之，出度。

第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑叫做回路或環(huán)

頂點(diǎn)不重復(fù)出現(xiàn)的路徑叫簡(jiǎn)單路徑

若圖中任意兩個(gè)頂點(diǎn)之間存在路徑（不一定是直接相連），則稱作連通圖

?

2.?鄰接矩陣：

????????????????????????????Wi,j ?????<Vi，Vj> ∈VR

鄰接矩陣的定義： A[i][j]={????

0 ??????即VR中不存在<Vi，Vj>時(shí)

?

3. 圖的遍歷

（1）深度優(yōu)先遍歷

????????步驟：1.從任意頂點(diǎn)開(kāi)始訪問(wèn)。

2.訪問(wèn)后把該元素對(duì)應(yīng)的訪問(wèn)標(biāo)志賦值為1表示已訪問(wèn)該數(shù)據(jù)元素

??????????????3.尋找與其有關(guān)未被訪問(wèn)的所有鄰接頂點(diǎn)，并從該頂點(diǎn)開(kāi)始進(jìn)行訪問(wèn)

??????????????4. 重復(fù)2、3步驟直到該連通圖的所有頂點(diǎn)均已訪問(wèn)完畢

?

（2）廣度優(yōu)先遍歷

?????????步驟：1.從任意頂點(diǎn)開(kāi)始訪問(wèn)。

2.訪問(wèn)后把該元素對(duì)應(yīng)的訪問(wèn)標(biāo)志賦值為1表示已訪問(wèn)該數(shù)據(jù)元素

???????????????3.尋找與其有關(guān)未被訪問(wèn)的鄰接頂點(diǎn)，并按順序入列直到所有鄰接頂點(diǎn)均已訪問(wèn)完畢

???????????????4.把最先入列的頂點(diǎn)出列，以它為頂點(diǎn)開(kāi)始訪問(wèn)

???????????????5. 重復(fù)2、3、4步驟直到該連通圖的所有頂點(diǎn)均已訪問(wèn)完畢

?

?

第八九十章

?

查找表

是由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合

?

對(duì)查找表的操作有：

（1）?查詢某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中；

（2）?檢索某個(gè)“特定的”數(shù)據(jù)元素的各種屬性

（3）?在查找表中插入一個(gè)數(shù)據(jù)元素；

（4）?從查找表中刪去某個(gè)特定元素

?

靜態(tài)查找表

只進(jìn)行前兩種“查找”操作的查找表為靜態(tài)查找表

?

動(dòng)態(tài)查找表

若在查找過(guò)程中同時(shí)插入查找表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已存在的某個(gè)數(shù)據(jù)元素，則成為動(dòng)態(tài)查找表

?

排序

其功能是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。

?