自學考試數(shù)據(jù)結(jié)構(gòu)重點總結(jié)02331(2014整理)

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

2、是從邏輯關系上描述數(shù)據(jù)，與數(shù)據(jù)元素的存儲結(jié)構(gòu)無關，是獨立于計算機的。數(shù)據(jù)的邏輯結(jié)構(gòu)分類: 線性結(jié)構(gòu)和非線性結(jié)構(gòu)數(shù)據(jù)元素及其關系在計算機內(nèi)的存儲方式，稱為數(shù)據(jù)的存儲結(jié)構(gòu)（物理結(jié)構(gòu)）。數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)，它依賴于計算機語言。數(shù)據(jù)的運算。最常用的檢索、插入、刪除、更新、排序等。4.數(shù)據(jù)的四種基本存儲方法: 順序存儲、鏈接存儲、索引存儲、散列存儲（1）順序存儲：通常借助程序設計語言的數(shù)組描述。（2）鏈接存儲：通常借助于程序語言的指針來描述。（3）索引存儲：索引表由若干索引項組成。關鍵字是能唯一標識一個元素的一個或多個數(shù)據(jù)項的組合。（4）散列存儲：該方法的基本思想是：根據(jù)元素的關

3、鍵字直接計算出該元素的存儲地址。5.算法必須滿足5個準則：輸入，0個或多個數(shù)據(jù)作為輸入；輸出，產(chǎn)生一個或多個輸出；有窮性，算法執(zhí)行有限步后結(jié)束；確定性，每一條指令的含義都明確；可行性，算法是可行的。算法與程序的區(qū)別：程序必須依賴于計算機程序語言，而一個算法可用自然語言、計算機程序語言、數(shù)學語言或約定的符號語言來描述。目前常用的描述算法語言有兩類：類Pascal和類C。6.評價算法的優(yōu)劣：算法的"正確性"是首先要考慮的。此外，主要考慮如下三點： 執(zhí)行算法所耗費的時間，即時間復雜性； 執(zhí)行算法所耗費的存儲空間，主要是輔助空間，即空間復雜性； 算法應易于理解、易于編程，易于調(diào)試等

4、，即可讀性和可操作性。以上幾點最主要的是時間復雜性，時間復雜度常用漸進時間復雜度表示。7.算法求解問題的輸入量稱為問題的規(guī)模,用一個正整數(shù)n表示。8.常見的時間復雜度按數(shù)量級遞增排列依次為：常數(shù)階0(1)、對數(shù)階0(log2n)、線性階0(n)、線性對數(shù)階0(nlog2n)、平方階0(n2)立方階0(n3)、k次方階0(nk)、指數(shù)階0(2n)和階乘階0(n!)。9.一個算法的空間復雜度S(n)定義為該算法所耗費的存儲空間，它是問題規(guī)模n的函數(shù),它包括存儲算法本身所占的存儲空間、算法的輸入輸出數(shù)據(jù)所占的存儲空間和算法在運行過程中臨時占用的存儲空間。第二章 線性表1.數(shù)據(jù)的運算是定義在邏輯結(jié)構(gòu)上

5、的，而運算的具體實現(xiàn)是在存儲結(jié)構(gòu)上進行的。2.只要確定了線性表存儲的起始位置，線性表中任意一個元素都可隨機存取，所以順序表是一種隨機存取結(jié)構(gòu)。3.常見的線性表的基本運算:(1)置空表InitList（L） 構(gòu)造一個空的線性表L。(2)求表長ListLength（L）求線性表L中的結(jié)點個數(shù)，即求表長。(3)GetNode（L，i） 取線性表L中的第i個元素。(4)LocateNode（L，x）在L中查找第一個值為x 的元素，并返回該元素在L中的位置。若L中沒有元素的值為x ，則返回0值。(5)InsertList（L，i，x）在線性表L的第i個元素之前插入一個值為x 的新元素，表L的長度加1。(

6、6)DeleteList（L，i）刪除線性表L的第i個元素，刪除后表L的長度減1。4.順序存儲方法：把線性表的數(shù)據(jù)元素按邏輯次序依次存放在一組地址連續(xù)的存儲單元里的方法。順序表（Sequential List）：用順序存儲方法存儲的線性表稱為順序表。順序表是一種隨機存取結(jié)構(gòu),順序表的特點是邏輯上相鄰的結(jié)點其物理位置亦相鄰。5.順序表上實現(xiàn)的基本運算：（1）插入：該算法的平均時間復雜度是O(n)，即在順序表上進行插入運算，平均要移動一半結(jié)點（n/2）。（2）刪除：順序表上做刪除運算，平均要移動表中約一半的結(jié)點（n-1）/2，平均時間復雜度也是O(n)。6.采用鏈式存儲結(jié)構(gòu)可以避免頻繁移動大量元素

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

8、loc(sizeof(ListNode);/生成新結(jié)點              p->data=ch;   /將讀入的數(shù)據(jù)放入新結(jié)點的數(shù)據(jù)域中              p->next=head;         &

9、#160;    head=p;（2） 尾插法建表：算法： p=(ListNode *)malloc(sizeof(ListNode); /生成新結(jié)點              p->data=ch;   /將讀入的數(shù)據(jù)放入新結(jié)點的數(shù)據(jù)域中           if (head=NULL)  

10、             head=p;/新結(jié)點插入空表           else               rear->next=p;/將新結(jié)點插到*r之后      

11、;        rear=p;/尾指針指向新表尾（3） 尾插法建帶頭結(jié)點的單鏈表：頭結(jié)點及作用：頭結(jié)點是在鏈表的開始結(jié)點之前附加一個結(jié)點。它具有兩個優(yōu)點:   由于開始結(jié)點的位置被存放在頭結(jié)點的指針域中,所以在鏈表的第一個位置上的操作就和在表的其它位置上操作一致,無須進行特殊處理;   無論鏈表是否為空，其頭指針都是指向頭結(jié)點的非空指針（空表中頭結(jié)點的指針域空），因此空表和非空表的處理也就統(tǒng)一了。頭結(jié)點數(shù)據(jù)域的陰影表示該部分不存儲信息。在有的應用中可用于存放表長等附加信息。具體算法：

12、r=head;    / 尾指針初值也指向頭結(jié)點          while(ch=getchar()!='n')              s=(ListNode *)malloc(sizeof(ListNode);/生成新結(jié)點       

13、0;      s->data=ch;   /將讀入的數(shù)據(jù)放入新結(jié)點的數(shù)據(jù)域中              r->next=s;              r=s;        

14、              r->next=NULL;/終端結(jié)點的指針域置空，或空表的頭結(jié)點指針域置空以上三個算法的時間復雜度均為O(n)。8.單鏈表上的查找：（帶頭結(jié)點）（1）按結(jié)點序號查找：序號為0的是頭結(jié)點。算法：p=head;j=0;/從頭結(jié)點開始掃描      while(p->next&&j<i)/順指針向后掃描，直到p->next為NULL或i=j為止  

15、;        p=p->next;          j+;              if(i=j)         return p;/找到了第i個結(jié)點      else r

16、eturn NULL;/當i<0或i>0時，找不到第i個結(jié)點   時間復雜度：在等概率假設下，平均時間復雜度為：為n/2=O(n)（2）按結(jié)點值查找：具體算法：ListNode *p=head->next;/從開始結(jié)點比較。表非空，p初始值指向開始結(jié)點        while(p&&p->data!=key)/直到p為NULL或p->data為key為止        

17、     p=p->next;/掃描下一結(jié)點         return p;/若p=NULL，則查找失敗，否則p指向值為key的結(jié)點時間復雜度為：O(n)9.插入運算：插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。        s=(ListNode *)malloc(sizeof(ListNode);     

18、60;   s->data=x;s->next=p->next;p->next=s;算法的時間主要耗費在查找結(jié)點上，故時間復雜度亦為O(n)。10.刪除運算         r=p->next;/使r指向被刪除的結(jié)點ai         p->next=r->next;/將ai從鏈上摘下       

19、60; free(r);/釋放結(jié)點ai的空間給存儲池算法的時間復雜度也是O（n）。 p指向被刪除的前一個結(jié)點。    鏈表上實現(xiàn)的插入和刪除運算，無須移動結(jié)點，僅需修改指針。11.單循環(huán)鏈表在單鏈表中，將終端結(jié)點的指針域NULL改為指向表頭結(jié)點或開始結(jié)點即可。判斷空鏈表的條件是head=head->next;12.僅設尾指針的單循環(huán)鏈表: 用尾指針rear表示的單循環(huán)鏈表對開始結(jié)點a1和終端結(jié)點an查找時間都是O(1)。而表的操作常常是在表的首尾位置上進行，因此，實用中多采用尾指針表示單循環(huán)鏈表。判斷空鏈表的條件為rear=rear->next;13.

20、循環(huán)鏈表：循環(huán)鏈表的特點是無須增加存儲量，僅對表的鏈接方式稍作改變，即可使得表處理更加方便靈活。若在尾指針表示的單循環(huán)鏈表上實現(xiàn)，則只需修改指針，無須遍歷，其執(zhí)行時間是O(1)。具體算法：LinkList Connect(LinkList A,LinkList B)  /假設A，B為非空循環(huán)鏈表的尾指針LinkList p=A->next;/保存A表的頭結(jié)點位置          A->next=B->next->next;/B表的開始結(jié)點鏈接到A表尾 

21、0;        free(B->next);/釋放B表的頭結(jié)點          B->next=p;/          return B;/返回新循環(huán)鏈表的尾指針循環(huán)鏈表中沒有NULL指針。涉及遍歷操作時，其終止條件就不再是像非循環(huán)鏈表那樣判別p或p-next是否為空，而是判別它們是否等于某一指定指針，如頭指針或尾指針等。在單鏈

22、表中，從一已知結(jié)點出發(fā)，只能訪問到該結(jié)點及其后續(xù)結(jié)點，無法找到該結(jié)點之前的其它結(jié)點。而在單循環(huán)鏈表中，從任一結(jié)點出發(fā)都可訪問到表中所有結(jié)點，這一優(yōu)點使某些運算在單循環(huán)鏈表上易于實現(xiàn)。14.雙向鏈表: 雙（向）鏈表中有兩條方向不同的鏈，即每個結(jié)點中除next域存放后繼結(jié)點地址外，還增加一個指向其直接前趨的指針域prior。雙鏈表由頭指針head惟一確定的。帶頭結(jié)點的雙鏈表的某些運算變得方便。將頭結(jié)點和尾結(jié)點鏈接起來，為雙（向）循環(huán)鏈表。15.雙向鏈表的前插和刪除本結(jié)點操作雙鏈表的前插操作void DInsertBefore(DListNode *p,DataType x)/在帶頭結(jié)點的雙鏈表中，

23、將值為x的新結(jié)點插入*p之前，設pNULL        DListNode *s=malloc(sizeof(DListNode);/        s->data=x;/        s->prior=p->prior;/        s->next=p;/  

24、60;     p->prior->next=s;/        p->prior=s;/       雙鏈表上刪除結(jié)點*p自身的操作void DDeleteNode(DListNode *p)      /在帶頭結(jié)點的雙鏈表中，刪除結(jié)點*p，設*p為非終端結(jié)點        &

25、#160; p->prior->next=p->next;/          p->next->prior=p->prior;/          free(p);/      與單鏈表上的插入和刪除操作不同的是，在雙鏈表中插入和刪除必須同時修改兩個方向上的指針。上述兩個算法的時間復雜度均為O(1)。16. 順序表和鏈表比較時間性

26、能：a、線性表：經(jīng)常性的查找； b、鏈式存儲結(jié)構(gòu)：經(jīng)常插入刪除操作；空間性能：a、對數(shù)據(jù)量大小事先能夠知道的用線性表； b、數(shù)據(jù)量變化較大的用鏈式存儲結(jié)構(gòu)。存儲密度越大，存儲空間的利用率越高。顯然，順序表的存儲密度是1，鏈表的存儲密度肯定小于1。第三章 棧和隊列1.棧稱為后進先出（Last In First Out）的線性表，簡稱為LIFO表。 棧是運算受限的線性表，順序棧也是用數(shù)組表示的。 進棧操作：進棧時，需要將S-top加1， S-top=StackSize-1表示棧滿"上溢"現(xiàn)象-當棧滿時，再做進棧運算產(chǎn)生空間溢出的現(xiàn)象。退棧操作：退棧時，需將S-top減1， S-

27、top<0表示空棧"下溢"現(xiàn)象-當?？諘r，做退棧運算產(chǎn)生的溢出現(xiàn)象。  下溢是正?，F(xiàn)象，常用作程序控制轉(zhuǎn)移的條件。空棧時棧頂指針不能是0，只能是-1。當程序中同時使用兩個棧時，可以將兩個棧的棧底分別設在順序存儲空間的兩端，讓兩個棧頂各自向中間延伸。當一個棧中的元素較多而棧使用的空間超過共享空間的一半時，只要另一個棧的元素不多，那么前者就可以占用后者的部分存儲空間。當Top1=Top2-1時，棧滿2.為了克服順序存儲分配固定空間所產(chǎn)生的溢出和空間浪費問題?？刹捎面準酱鎯Y(jié)構(gòu)來存儲棧。鏈棧是沒有附加頭結(jié)點的運算受限的單鏈表。棧頂指針就是鏈表的頭指針。鏈棧中的結(jié)點

28、是動態(tài)分配的，所以可以不考慮上溢，無須定義StackFull運算棧的一個重要應用是實現(xiàn)遞歸，直接調(diào)用自己或間接調(diào)用自己的函數(shù)。3.允許刪除的一端稱為隊頭（Front），允許插入的一端稱為隊尾（Rear），當隊列中沒有元素時稱為空隊列，隊列亦稱作先進先出（First In First Out）的線性表，簡稱為FIFO表。隊列的順序存儲結(jié)構(gòu)稱為順序隊列，順序隊列實際上是一個受限的線性表。順序隊列的基本操作入隊時：將新元素插入rear所指的位置，然后將rear加1。出隊時：刪去front所指的元素，然后將front加1并返回被刪元素。當頭尾指針相等時，隊列為空。在非空隊列里，頭指針始終指向隊頭元素，

29、而隊尾指針始終指向隊尾元素的下一位置。而棧頂指針指向棧頂元素。4. 循環(huán)隊列：為充分利用數(shù)組空間，克服上溢，可將數(shù)組空間想象為一個環(huán)狀空間，并稱這種環(huán)狀數(shù)組表示的隊列為循環(huán)隊列。循環(huán)隊列中進行出隊、入隊操作時，頭尾指針仍要加1，朝前移動。只不過當頭尾指針指向向量上界（QueueSize-1）時，其加1操作的結(jié)果是指向向量的下界0。這種循環(huán)意義下的加1操作可以描述為： 方法一：    if(i+1=QueueSize) /i表示front或rear        i=0;  &

30、#160; else        i+; 方法二-利用"模運算"    i=(i+1)%QueueSize；循環(huán)隊列中，由于入隊時尾指針向前追趕頭指針；出隊時頭指針向前追趕尾指針，造成隊空和隊滿時頭尾指針均相等。因此，無法通過條件Q.front=Q.rear來判別隊列是"空"還是"滿"。解決這個問題的方法至少有三種： 另設一個標志位以區(qū)別隊列是空還是滿； 設置一個計數(shù)器記錄隊列中元素的總數(shù)（即隊列長度）。 少用一個元素的空間。約定入隊

31、前，測試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等則認為隊列滿即尾指針Q.rear所指的單元始終為空。5.循環(huán)隊列的基本運算: 置隊空: Q->front=Q->rear=0; 判隊空: return Q->rear=Q->front; 判隊滿: return (Q->rear+1)%QueueSize=Q->front; 入隊 Q->dataQ->rear=x;               &

32、#160; /新元素插入隊尾 Q->rear=(Q->rear+1)%QueueSize;  出隊 temp=Q->dataQ->front; Q->front=(Q->front+1)%QueueSize;   /循環(huán)意義下的頭指針加1 return temp;取隊頭元素 return Q->dataQ->front;6. 隊列的鏈式存儲結(jié)構(gòu)簡稱為鏈隊列。它是限制僅在表頭刪除和表尾插入的單鏈表。 為了簡化處理，在隊頭結(jié)點之前附加一個頭結(jié)點，并設隊頭指針指向此結(jié)點。鏈隊列的基本運算:（帶頭結(jié)點）（1） 構(gòu)造空隊：Q-

33、>rear=Q->front；Q->rear->next=NULL;（2） 判隊空：return Q->rear=Q->front;（3） 入隊：QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode);/申請新結(jié)點             p->data=x;   p->next=NULL;      &

34、#160;      Q->rear->next=p;     /*p鏈到原隊尾結(jié)點后             Q->rear=p;           /隊尾指針指向新的尾（4） 出隊：當隊列長度大于1時，只需修改頭結(jié)點指針，尾指針不變  

35、          s=Q->front->next; Q->front->next=s->next; x=s->data; free(s); return x; 當隊列長度等于1時，不僅要修改頭結(jié)點指針，還要修改尾指針s=Q->front->next; Q->front->next=NULL; Q->rear=Q->front;x=s->data; free(s); return x;（5） 取隊頭元素：return

36、 Q->front->next->data; 因為有頭結(jié)點，所以用了next和鏈棧類似，無須考慮判隊滿的運算及上溢。在出隊算法中，一般只需修改隊頭指針。但當原隊中只有一個結(jié)點時，該結(jié)點既是隊頭也是隊尾，故刪去此結(jié)點時亦需修改尾指針，且刪去此結(jié)點后隊列變空。7.用計算機來處理計算算術表達式問題，首先要解決的問題是如何將人們習慣書寫的中綴表達式轉(zhuǎn)換成后綴表達式。第四章 多維數(shù)組和廣義表1.數(shù)組的順序存儲方式:一般采用順序存儲方法表示數(shù)組。（1）行優(yōu)先順序    a11,a12,a1n,a21,a22,a2n,，am1,am2,，amn（2）列優(yōu)先順序

37、    a11,a21,am1,a12,a22,am2,，a1n,a2n,，amn Pascal和C語言是按行優(yōu)先順序存儲的，而Fortran語言是按列優(yōu)先順序存儲的。2.為了節(jié)省存儲空間，可以對矩陣中有許多值相同或值為零的元素的矩陣，采用壓縮存儲。特殊矩陣是指相同值的元素或零元素在矩陣中的分布有一定的規(guī)律。常見的有對稱矩陣、三角矩陣。（1）對稱矩陣 在一個n階方陣A中，若元素滿足下述性質(zhì)：     aij=aji 0i，jn-1稱為n階對稱矩陣，它的元素是關于主對角線對稱的，所以只需要存儲矩陣上三角或下三角元素即可，讓兩個

38、對稱的元素共享一個存儲空間。矩陣元素aij和數(shù)組元素sa【k】之間的關系是k=i×(i+1)/2+j ij 0k<n(n+1)/2-1k=j×(j+1)/2+i ij 0k<n(n+1)/2-1（2）三角矩陣：以主對角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣是指它的下三角(不包括主角線)中的元素均為常數(shù)c或零；下三角矩陣的主對角線上方均為常數(shù)c或零。一般情況，三角矩陣的常數(shù)c均為零。三角矩陣的壓縮存儲：三角矩陣中的重復元素c可共享一個存儲空間，其余的元素正好有n×(n+1)/2個，因此，三角矩陣可壓縮存儲在一維數(shù)組san(n+1)/2+1中，其

39、中c存放在數(shù)組的最后一個元素中。三角矩陣的壓縮存儲結(jié)構(gòu)是隨機存取結(jié)構(gòu)。3.稀疏矩陣:設矩陣Amn中有s個非零元素，若s遠遠小于矩陣元素的總數(shù)，則稱A為稀疏矩陣。為了節(jié)省存儲單元，可用壓縮存儲方法只存儲非零元素。由于非零元素的分布一般是沒有規(guī)律的，因此在存儲非零元素的同時，還必須存儲非零元素所在的行、列位置，所以可用三元組(i，j，aij)來確定非零元素。稀疏矩陣進行壓縮存儲通常有兩類方法：順序存儲(三元組表)和鏈式存儲(十字鏈表)。稀疏矩陣的壓縮存儲會失去隨機存取功能。4.廣義表是線性表的推廣,又稱列表。廣義表是n(n0)個元素a1，a2，ai，an的有限序列。其中ai或者是原子或者是一個廣義

40、表。    廣義表通常用圓括號括起來，用逗號分隔其中的元素。    為了區(qū)分原子和廣義表，書寫時用大寫字母表示廣義表，用小寫字母表示原子。    若廣義表Ls非空(n1)，則al是LS的表頭，其余元素組成的表(a1，a2，an)稱為Ls的表尾。    廣義表具有遞歸和共享的性質(zhì)廣義表的深度：一個表展開后所含括號的層數(shù)稱為廣義表的深度。19.廣義表是一種多層次的線性結(jié)構(gòu)，實際上這就是一種樹形結(jié)構(gòu)。任何一個非空廣義表的表頭可以是原子，也可以是子表，而其表尾必定是子表。 

41、     head=(a，b)=a，tail(a，b)=(b)   對非空表A和(y)，也可繼續(xù)分解。  注意:廣義表()和()不同。前者是長度為0的空表，對其不能做求表頭和表尾的運算；而后者是長度為l的由空表作元素的廣義表，可以分解得到的表頭和表尾均是空表()。廣義表是一種有層次的非線性結(jié)構(gòu)，通常采用鏈式存儲結(jié)構(gòu)，每個元素用一個結(jié)點表示，結(jié)點由3個域構(gòu)成，其中一個是tag標志位，用來區(qū)分結(jié)點是原子還是子表，當tag為零時結(jié)點是子表，第二個域為slink，用以存放子表的地址；當tag為1時結(jié)點是原子，第二個域為data，用以

42、存放元素值。第五章 樹和二叉樹1.樹的表示法：最常用的是樹形圖表示法；還有3種嵌套集合、凹形、廣義表。樹結(jié)構(gòu)的基本術語 （1）結(jié)點的度(Degree)     樹中的一個結(jié)點擁有的子樹數(shù)稱為該結(jié)點的度(Degree)。一棵樹的度是指該樹中結(jié)點的最大度數(shù)。    度為零的結(jié)點稱為葉子(Leaf)或終端結(jié)點。度不為零的結(jié)點稱分支結(jié)點或非終端結(jié)點。    除根結(jié)點之外的分支結(jié)點統(tǒng)稱為內(nèi)部結(jié)點。根結(jié)點又稱為開始結(jié)點。（2）路徑（path）若樹中存在一個結(jié)點序列k1，k2，ki，使得ki是ki+

43、1的雙親(1i<j)，則稱該結(jié)點序列是從kl到kj的一條路徑(Path)。    一個結(jié)點的祖先是從根結(jié)點到該結(jié)點路徑上所經(jīng)過的所有結(jié)點，而一個結(jié)點的子孫則是以該結(jié)點為根的子樹中的所有結(jié)點。    結(jié)點的層數(shù)(Level)從根起算：根的層數(shù)為1，其余結(jié)點的層數(shù)等于其雙親結(jié)點的層數(shù)加1。    雙親在同一層的結(jié)點互為堂兄弟。    樹中結(jié)點的最大層數(shù)稱為樹的高度(Height)或深度(Depth)。    若將樹中每個結(jié)點的各子樹看成是從左到

44、右有次序的(即不能互換)，則稱該樹為有序樹(OrderedTree)；否則稱為無序樹(UnoderedTree)。若不特別指明，一般討論的樹都是有序樹。    森林(Forest)是m(m0)棵互不相交的樹的集合。樹和森林的概念相近。刪去一棵樹的根，就得到一個森林；反之，加上一個結(jié)點作樹根，森林就變?yōu)橐豢脴洹?.二叉樹與度數(shù)為2的有序樹不同：在有序樹中，雖然一個結(jié)點的孩子之間是有左右次序的，但是若該結(jié)點只有一個孩子，就無須區(qū)分其左右次序。而在二叉樹中，即使是一個孩子也有左右之分。二叉樹的性質(zhì)：性質(zhì)1 二叉樹第i層上的結(jié)點數(shù)目最多為2i-1(i1)。例如5層的二叉樹

45、，第5層上的結(jié)點數(shù)目最多為24=16性質(zhì)2 深度為k的二叉樹至多有2k-1個結(jié)點(k1)。例如深度為5的二叉樹，至多有25-1=31個結(jié)點性質(zhì)3 在任意-棵二叉樹中，若終端結(jié)點的個數(shù)為n0，度為2的結(jié)點數(shù)為n2，則no=n2+1。例如一棵深度為4的二叉樹（a），其終端結(jié)點數(shù)n0為8,度為2的結(jié)點樹為7，則8=7+1，no=n2+1成立（b）其終端結(jié)點數(shù)n0為6,度為2的結(jié)點樹為5，則6=5+1，no=n2+1成立滿二叉樹：一棵深度為k且有2k-1個結(jié)點的二又樹稱為滿二叉樹。滿二叉樹的特點：（1）每一層上的結(jié)點數(shù)都達到最大值。即對給定的高度，它是具有最多結(jié)點數(shù)的二叉樹。（2）滿二叉樹中不存在度數(shù)

46、為1的結(jié)點，每個分支結(jié)點均有兩棵高度相同的子樹，且樹葉都在最下一層上。完全二叉樹：若一棵深度為k的二叉樹，其前k-1層是一棵滿二叉樹，而最下面一層上的結(jié)點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。特點：  （1） 滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。  （2） 在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干結(jié)點后得到的二叉樹仍然是一棵完全二叉樹。  （3） 在完全二叉樹中，若某個結(jié)點沒有左孩子，則它一定沒有右孩子，即該結(jié)點必是葉結(jié)點。性質(zhì)4 具有n個結(jié)點的完全二叉樹的深度為。logn+1 或log(n+1)例，具有100個

47、結(jié)點的完全二叉樹的深度為:lg100+1=7,26=64 27=128所以lg100=6,lg(100+1)=74.完全二叉樹的編號特點：完全二叉樹中除最下面一層外，各層都充滿了結(jié)點。每一層的結(jié)點個數(shù)恰好是上一層結(jié)點個數(shù)的2倍。從一個結(jié)點的編號就可推得其雙親，左、右孩子等結(jié)點的編號。編號從0開始若i=0，則qi為根結(jié)點，無雙親；否則，qi的雙親編號為(i-1)/2。若2i+1<n，則qi的左孩子的編號是2i+1；否則，qi無左孩子，即qi必定是葉子。若2i+2<n，則qi的右孩子的編號是2i+2；否則，qi無右孩子。對于完全二叉樹而言，使用順序存儲結(jié)構(gòu)既簡單又節(jié)省存儲空間。但對于一

48、般二叉樹來說，采用順序存儲時，為了使用結(jié)點在數(shù)組中的相對位置來表示結(jié)點之間的邏輯關系，就必須增加一些虛結(jié)點使其成為完全二叉樹的形式。5.鏈式存儲結(jié)構(gòu): 二叉樹的每個結(jié)點最多有兩個孩子。用鏈接方式存儲二叉樹時，每個結(jié)點除了存儲結(jié)點本身的數(shù)據(jù)外，還應設置兩個指針域lchild和rchild，分別指向該結(jié)點的左孩子和右孩子。結(jié)點的結(jié)構(gòu)為：二叉鏈表是一種常用的二叉樹存儲結(jié)構(gòu)。建立二叉鏈表方法：a、按廣義表方法，靠近左括號的結(jié)點是在左子樹上，而逗號右邊結(jié)點是在右子樹上。b、按完全二叉樹的層次順序建立結(jié)點。具有n個結(jié)點的二叉鏈表中，共有2n個指針域。其中有n-1個用來指示結(jié)點的左、右孩子，其余的n+1個為

49、空。二叉樹遍歷算法中的遞歸終止條件是二叉樹為空。遞歸工作棧中包括兩項：一項是遞歸調(diào)用的語句編號，另一項則是指向根結(jié)點的指針。 已知一棵二叉樹的前序和中序遍歷序列或中序和后序遍歷序列，可唯一確定一棵二叉樹。具體方法如下： 首先根據(jù)前序或后序遍歷序列確定二叉樹的各子樹的的根，然后根據(jù)中序遍歷序列確定各子樹根的左右子樹。6.線索二叉樹：n個結(jié)點的二叉鏈表必定存在n+1個空指針域，可以利用這些空指針域，存放指向結(jié)點在某種遍歷次序下的前趨和后繼結(jié)點的指針，這種指向前驅(qū)和后繼結(jié)點的指針稱為"線索"，這種加上線索的二叉鏈表稱為線索鏈表，相應的二叉樹稱為線索二叉樹(Threaded

50、0;  BinaryTree)。線索鏈表的結(jié)點結(jié)構(gòu)：其中:ltag和rtag是增加的兩個標志域，用來區(qū)分結(jié)點的左、右指針域是指向其左、右孩子的指針，還是指向其前趨或后繼的線索。           圖中的實線表示指針，虛線表示線索。      線索二叉樹中，一個結(jié)點是葉結(jié)點的充要條件為：左、右標志均是1。7.二叉樹的線索化: 把對一棵二叉線索鏈表結(jié)構(gòu)中所有結(jié)點的空指針域按照某種遍歷次序加線索的過程稱為線索化。和中序遍歷算法一樣，遞歸過程中對每結(jié)點

51、僅做一次訪問。因此對于n個結(jié)點的二叉樹，線索化的算法時間復雜度為O(n)。8.樹、森林到二叉樹的轉(zhuǎn)換：樹中每個結(jié)點最多只有一個最左邊的孩子(長子)和一個右鄰的兄弟。將樹轉(zhuǎn)換成二叉樹：在所有兄弟結(jié)點之間加一道連線；對每個結(jié)點，除了保留與其長子的連線外，去掉該結(jié)點與其它孩子的連線。由于樹根沒有兄弟，故樹轉(zhuǎn)化為二叉樹后，二叉樹的根結(jié)點的右子樹必為空。將一個森林轉(zhuǎn)換為二叉樹:將森林中的每棵樹轉(zhuǎn)化成二叉樹，然后再將二叉樹的根節(jié)點看做兄弟連在一起，形成一棵二叉樹9.二叉樹到樹、森林的轉(zhuǎn)換: 方式是：若二叉樹中結(jié)點x是雙親y的左孩子，則把x的右孩子，右孩子的右孩子，都與y用連線連起來，最后去掉所有雙親到右孩

52、子的連線。10.樹的存儲結(jié)構(gòu)：1.雙親表示法：雙親鏈表表示法利用樹中每個結(jié)點的雙親唯一性，在存儲結(jié)點信息的同時，為每個結(jié)點附設一個指向其雙親的指針parent，惟一地表示任何-棵樹。（1）雙親鏈表表示法的實現(xiàn)分析：E和F所在結(jié)點的雙親域是1，它們的雙親結(jié)點在向量中的位置是1，即B是它們的雙親。  注意： 根無雙親，其parent域為-1。    雙親鏈表表示法中指針parent向上鏈接，適合求指定結(jié)點的雙親或祖先(包括根)；求指定結(jié)點的孩子或其它后代時，可能要遍歷整個數(shù)組。2.孩子鏈表法：孩子鏈表表示法是為樹中每個結(jié)點設置一個孩子鏈表，并將這些結(jié)點及相應

53、的孩子鏈表的頭指針存放在一個向量中。注意： 孩子結(jié)點的數(shù)據(jù)域僅存放了它們在向量空間的序號。    與雙親鏈表表示法相反，孩子鏈表表示便于實現(xiàn)涉及孩子及其子孫的運算，但不便于實現(xiàn)與雙親有關的運算。    將雙親鏈表表示法和孩子鏈表表示法結(jié)合起來，可形成雙親孩子鏈表表示法。3.孩子兄弟表示法：在存儲結(jié)點信息的同時，附加兩個分別指向該結(jié)點最左孩子和右鄰兄弟的指針域，即可得樹的孩子兄弟鏈表表示。注意：    這種存儲結(jié)構(gòu)的最大優(yōu)點是：它和二叉樹的二叉鏈表表示完全一樣?？衫枚鏄涞乃惴▉韺崿F(xiàn)對樹的操作。11.樹的

54、遍歷：一般都只給出兩種次序遍歷樹的方法：前序(先根次序)遍歷和后序(后根次序)遍歷。 前序遍歷一棵樹等價于前序遍歷該樹對應的二叉樹 后序遍歷一棵樹等價于中序遍歷該樹對應的二叉樹。對下面(a)圖中所示的森林進行前序遍歷和后序遍歷，則得到該森林的前序序列和后序序列分別為ABCDEFIGJH和BDCAIFJGHE。而(b)圖所示二叉樹的前序序列和中序序列也分別為ABCDEFIGJH和BDCAIFJGHE。 前序遍歷森林等同于前序遍歷該森林對應的二叉樹 后序遍歷森林等同于中序遍歷該森林對應的二叉樹12.從根結(jié)點到某結(jié)點之間的路徑長度與該結(jié)點上權(quán)的乘積稱為該結(jié)點的帶權(quán)路徑長度，樹種所有葉子結(jié)點的帶權(quán)路徑

55、長度之和稱為樹的帶權(quán)路徑長度。 帶權(quán)路徑長度WPL最小的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹。 哈夫曼樹不一定是二叉樹。 哈夫曼樹又稱為最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹。完全二叉樹就是這種路徑長度最短的二叉樹。 只有葉結(jié)點上的權(quán)值均相同時，完全二叉樹一定是最優(yōu)二叉樹，否則完全二叉樹不一定是最優(yōu)二叉樹。    最優(yōu)二叉樹中，權(quán)越大的葉子離根越近。 最優(yōu)二叉樹的形態(tài)不唯一，WPL最小。13.哈夫曼算法: 注意： 初始森林中的n棵二叉樹，每棵樹有一個孤立的結(jié)點，它們既是根，又是葉子    n個葉子的哈夫曼樹要經(jīng)過n-1次合并，產(chǎn)生n-1個新結(jié)點

56、。最終求得的哈夫曼樹中共有2n-1個結(jié)點。    哈夫曼樹是嚴格的二叉樹，沒有度數(shù)為1的分支結(jié)點。14.哈夫曼編碼：數(shù)據(jù)壓縮過程稱為編碼,反之，解壓縮的過程稱為解碼。設計一種長短不等的編碼，則必須保證任一字符的編碼都不是另一個字符編碼的前綴，這種編碼稱為前綴編碼。可以利用二叉樹來設計二進制的前綴編碼，其左分支表示字符0，右分支表示字符1，則以根結(jié)點到葉結(jié)點路徑上的分支字符組成的串作為該葉節(jié)點的字符編碼。因此設計電文總長最短的二進制前綴編碼，就是以n種字符出現(xiàn)的頻率作為權(quán)構(gòu)造一棵哈夫曼樹，由哈夫曼樹求得的編碼就是哈夫曼編碼。譯碼過程是從樹根結(jié)點出發(fā)，逐個讀入電文中的

57、二進制碼。第六章1.圖G由兩個集合構(gòu)成，頂點集合和邊集合，也可以圖G只有頂點而沒有邊。用尖括號表示圖的有向邊<vi,vj>,有向邊又稱為弧，起點稱為弧尾，終點稱為弧頭。無向圖的頂點對用圓括號表示(vi,vj)。在無向圖中，稱vi和vj相鄰接，在有向圖中稱頂點vi鄰接到vj，頂點vj鄰接于vi在無向圖中，n的取值范圍是0-n(n-1)/2，將具有n(n-1)/2條邊的無向圖稱為無向完全圖。在有向圖中，n的取值范圍是0-n(n-1)，將具有n(n-1)條邊的有向圖稱為有向完全圖。無向圖中，頂點的度定義為以該頂點為一個端點的邊的數(shù)目，有向圖的度等于出度和入度之和。在無向圖中，任意兩頂點都

58、有路徑，則稱兩頂點連通。若圖G中的任意兩個頂點都連通，稱G為連通圖。無向圖的極大連通子圖稱為連通分量，顯然，任何連通圖的連通分量只有一個，即其自身，而非連通的無向圖有多個連通分量。在有向圖中，圖G中任意兩頂點連通，稱為強連通圖，極大連通子圖稱為強連通分量。若在一個圖的每條邊上標上某種數(shù)值，該數(shù)值稱為該邊的權(quán)。邊上帶權(quán)的圖稱為帶權(quán)圖，帶權(quán)的連通圖稱為網(wǎng)絡。2.圖的存儲結(jié)構(gòu)：鄰接矩陣和鄰接表表示法。圖的頂點編號從0開始。 鄰接矩陣表示法：<vi,vj>或(vi,vj)是邊，則值為1，不是邊則值為0。無向圖的鄰接矩陣是按主對角線對稱的。若G是帶權(quán)圖，只要把1換成相應邊上的權(quán)值即可，0的位

59、置上可以不動或?qū)⑵鋼Q成無窮大表示。無向圖的鄰接矩陣表示法可以僅存儲主對角線以下的元素，時間復雜度為O(n2) 鄰接表表示法：鄰接表是圖的一種鏈式存儲結(jié)構(gòu)。將無向圖的鄰接表稱為邊表，將有向圖的鄰接表稱為出邊表，將鄰接表的表頭向量稱為頂點表。若無向圖有n個頂點和e條邊，則它的鄰接表共有n個頭結(jié)點和2e個表結(jié)點。建立鄰接表的時間復雜度是O(n+e)。圖的鄰接表表示不是唯一的,這是因為在每個頂點的鄰接表中，各邊結(jié)點的鏈接次序可以是任意的，其具體鏈接次序與邊的輸入次序和生成算法有關。3.圖的遍歷：遍歷圖的算法是求解圖的連通性、圖的拓撲排序等算法的基礎。圖的遍歷常用的是深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷兩

60、種方法。 深度優(yōu)先搜索遍歷(DFS)類似于前序(先根)遍歷。按訪問頂點的先后次序得到的頂點序列稱為圖的深度優(yōu)先遍歷序列，或簡稱為DFS序列。共需要搜索n2個矩陣元素，時間復雜度為鄰接矩陣O(n2)或鄰接表O(n+e)。 廣度優(yōu)先搜索遍歷(BFS)類似于樹的按層次遍歷，先被訪問的頂點，其鄰接點也先被訪問，就是先進先出。時間復雜度為鄰接矩陣O(n2)或鄰接表O(n+e)，空間復雜度都是O(n)。 4.生成樹是連通圖的包含圖中所有頂點的一個極小連通子圖，一個圖的極小連通子圖恰為一個無回路的連通圖，也就是說，若圖中任意添加一條邊，就會出現(xiàn)回路，若去掉任意一條邊，都會使之成為非連通圖。 因此，一個具有n

61、個頂點的生成樹有且僅有n-1條邊，但有n-1條邊的圖不一定是生成樹，同一個圖可以有不同的生成樹。 生成樹定義為：若從圖的某頂點出發(fā)，可以系統(tǒng)的訪問到圖的所有頂點，則遍歷時經(jīng)過的邊和圖的所有頂點所構(gòu)成的子圖，稱為該圖的生成樹。 最小生成樹：圖的生成樹不唯一，把權(quán)值最小的生成樹稱為最小生成樹（MST）。 構(gòu)造最小生成樹的算法：普里姆Prim算法的時間復雜度為O（n2）與網(wǎng)中邊數(shù)無關適于稠密圖。克魯斯卡爾Kruskal算法的時間復雜度為O（eloge），主要取決于邊數(shù)，較適合于稀疏圖。5.最短路徑：Dijkstra迪杰斯特拉算法，提出了按路徑長度遞增的順序產(chǎn)生諸頂點的最短路徑算法。拓撲排序：子工程稱

62、為活動，頂點代表活動，有向邊代表活動的先后關系。這樣的有向無環(huán)圖DAG稱為頂點活動網(wǎng)，簡稱為AOV網(wǎng)。 將有向無環(huán)圖G中所有頂點排成一個線性序列，若<u，v>E（G），則在線性序列u在v之前，這種線性序列稱為拓撲序列。由AOV網(wǎng)構(gòu)造拓撲序列的過程稱為拓撲排序。 檢測的方法是：對有向圖構(gòu)造其頂點的拓撲序列，若網(wǎng)中所有頂點都在他的拓撲序列中，則AOV網(wǎng)必定不存在環(huán)。 AOV網(wǎng)的拓撲序列不是唯一的。 拓撲排序的描述思想：a、在有向圖中選一個沒有前趨(入度為零)的頂點，且輸出之。b、從有向圖中刪除該頂點及其與該頂點有關的所有邊。c、重復上述步驟，直到全部頂點都已輸出或圖中剩余的頂點中沒有前

63、趨頂點為止。d、輸出剩余的無前趨結(jié)點。 拓撲排序?qū)嶋H上是對鄰接表表示的圖G進行遍歷的過程。時間復雜度是O(n+e)。第七章 排序1.如果待排序文件中存在多個關鍵字相同的記錄，經(jīng)過排序后，這些具有相同關鍵字的記錄之間的相對次序保持不變，該排序方法是穩(wěn)定的；反之，則是不穩(wěn)定的。排序在內(nèi)存中處理，不涉及數(shù)據(jù)的內(nèi)外存交換，稱為內(nèi)部排序，反之為外部排序。內(nèi)部排序又分為五類：插入、選擇、交換、歸并和分配排序。在排序過程中需進行兩種操作：比較兩個關鍵字的大小、改變指向記錄的指針或移動記錄本身，而待排序記錄的存儲形式一般有三種：順序結(jié)構(gòu)、鏈式結(jié)構(gòu)和輔助表。評價排序算法的標準：執(zhí)行算法需要的時間，以及算法所需要

64、的附加空間。還有算法本身的復雜度。排序的時間開銷，一般情況下可用算法中關鍵字的比較次數(shù)和記錄的移動次數(shù)來衡量。2.插入排序：每次將一個待排序記錄按其關鍵字大小插入到前面已排好序的文件中的適當位置。 直接插入排序：每次從無序區(qū)取出第一個元素把它插入到有序區(qū)的適當位置，使之成為新的有序區(qū)，經(jīng)過n-1次插入后完成。算法中R0作用：保存Ri副本，監(jiān)視數(shù)組下標變量j是否越界。所以R0稱為哨兵。每次的比較是從后往前比較的。時間復雜度最好是O(n)，最壞是O(n2)，所以是O(n2)。空間復雜度O(1)，所以是就地排序。 是穩(wěn)定的算法。初始情況是有序區(qū)中只有一個元素R1，無序區(qū)中R2.n。希爾排序(縮小增量

65、排序)：算法不穩(wěn)定。記錄的總比較次數(shù)和總移動次數(shù)都要比直接插入排序少得多，特別是當n越大越明顯。希爾排序的時間依賴于增量序列，最后一個增量必須是1，盡量避免增量互為倍數(shù)的情況。3.交換排序：兩兩比較待排序記錄的關鍵字，如果發(fā)現(xiàn)兩個記錄的次序相反時即進行交換，直到?jīng)]有反序位置。 冒泡排序(起泡排序)：通過相鄰元素之間比較和交換，使較小移向頂部，從后往前兩兩比較。時間復雜度最好是O(n)，最壞是O(n2)，所以是O(n2)。是穩(wěn)定的排序算法。 快速排序(劃分交換排序)：是冒泡排序的改進。比較和交換從兩端向中間進行。一趟快速排序步驟：設兩個指針i和j，初值分別為low和high，基準為x=Ri，首先

66、從j位置開始向前搜索第一個小于基準x.key的記錄存入i所指位置上，i自增1，然后從i所指位置向后搜索找到第一個大于基準x.key的記錄存入j所指位置上，j自減1，重復直至i=j為止?？焖倥判蚴遣环€(wěn)定的。有非常好的時間復雜度，優(yōu)于其他各種排序算法，O(nlog2n)，但是當記錄關鍵字有序或基本有序時復雜度反而大了使之轉(zhuǎn)變成冒泡排序為O(n2)?？焖倥判蚴沁f歸的，需要一個?？臻g，空間復雜度O(log2n)。4.選擇排序：每一趟在待排序的記錄中選出關鍵字最小的記錄，依次存放在已排序好的記錄序列的最后。 直接選擇排序：初始時，R1.n為無序區(qū)，R1為空；第一趟是在R1.n中選出最小的記錄與R1交換，R1為有序區(qū)；第二趟是在R2.n中選出最小的記錄與R2交換，R1.2為有序區(qū)。時間復雜度O(n2)，是不穩(wěn)定的。初始情況是有序區(qū)為空，無序區(qū)中R1.n，第一趟從R1.n選擇最小記錄與R1交換。 堆排序：是對直接選擇排序的改進，是一種樹形選擇排序?；舅枷耄涸谂判蜻^程中，將記錄數(shù)組R1.n看成是一棵完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關系，在當前無序區(qū)中選擇關鍵字最大或最小記錄。每一趟排序