數(shù)據(jù)結(jié)構(gòu)復(fù)習

第一章定義數(shù)據(jù)結(jié)構(gòu)：相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。即數(shù)據(jù)的組織形式。數(shù)據(jù)結(jié)構(gòu)包括三個方面的內(nèi)容：邏輯結(jié)構(gòu)存儲結(jié)構(gòu)基本操作（運算）數(shù)據(jù)：計算機程序所加工處理的描述客觀事物的符號表示。數(shù)據(jù)元素：數(shù)據(jù)的基本單位，是數(shù)據(jù)集合中的一個個體。數(shù)據(jù)元素可由一個或若干個數(shù)據(jù)項所組成。數(shù)據(jù)項：是具有獨立意義的數(shù)據(jù)的最小單位。數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)元素的集合。邏輯結(jié)構(gòu)S={D,R}D表示數(shù)據(jù)元素的集合，R表示元素間關(guān)系的集合如：S={D,R},D={a,b,c,d,e,f,g}Rl={?}R2={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>}R3={<a,b>,<a,c>,<a,d>,<b,e>,<b,f>,<c,g>}R4={<a,e>,<b,c>,<c,a>,<e,f>,<f,g>,<c,f>}集合S2集合S2—線性結(jié)構(gòu)S3—樹型結(jié)構(gòu)：對特定問題求解步驟的一種描述，是指令的有限序列。有窮性(在有限的時間內(nèi)結(jié)束)確定性(每一步具有明確的含義)可行性(可讀，可理解，可執(zhí)行)輸入(零個或多個輸入)輸出(一個或多個輸出)算法的衡量標準正確性(無語法錯誤，對于合法的數(shù)據(jù)輸入能夠得到正確的輸出結(jié)果)可讀性健壯性(對于非法的數(shù)據(jù)輸入能夠給出相應(yīng)的反應(yīng))時間效率和存儲需求3算法分析算法分析方法算法分析的兩個主要方面時間復(fù)雜度：算法對時間的需求。T(n)=O(f(n))n:表示問題的規(guī)模。f(n):表示基本操作執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)。O表示T(n)的量級。嚴格的數(shù)學定義為，T(n)和f(n)是定義在正整數(shù)集合上的兩個函數(shù)，則存在正的常數(shù)C和nO,使得當n>=n0時，都滿足:第二章線性表定義：線性表是n個數(shù)據(jù)元素的有限序列,可記為：/=L7"Y- 小 !線性表的順序表示－隨機存取的存儲結(jié)構(gòu)，用一組連續(xù)的存儲單元依次存儲線性表中的數(shù)據(jù)元素。表中第一個元素的起始位置稱為順序表的基地址。線性表中任一數(shù)據(jù)元素的存儲位置為： s表示每個數(shù)據(jù)元素所占存儲空間大小。i表示數(shù)據(jù)元素的位序。順序表的特點：簡單直觀，容易理解；能夠?qū)崿F(xiàn)隨機存??；插入和刪除需要移動大量的數(shù)據(jù)元素；長度相對固定，易導(dǎo)致存儲空間的浪費；線性鏈表是一種動態(tài)存儲結(jié)構(gòu)，所占用的存儲空間是在程序的執(zhí)行過程中得到的，當線性鏈表要增加一個結(jié)點時，向系統(tǒng)申請一個存儲空間，刪除結(jié)點時要將空間釋放。線性鏈表的特點：根據(jù)實際需求來分配存儲空間；插入和刪除不需要移動大量的數(shù)據(jù)元素；只需要修改相應(yīng)的指針既可。適合存儲結(jié)構(gòu)多變或變化較大的情形。無法實現(xiàn)隨機存取，每次的查找過程均需從頭指針開始；插入刪除節(jié)點#include"stdio.h"#include"malloc.h"#defineERROR0;typedefintElemType;typedefstructLNode{ElemTypedata; /*結(jié)點的數(shù)據(jù)域*/structLNode*next;/*結(jié)點的指針域*/}LNode,*Llist;LlistInitList_l(LlistH){H=(LNode*)malloc(sizeof(LNode)); /*申請一個頭結(jié)點*/if(!H)returnERROR; /*申請失敗*/H->next=NULL; /*頭結(jié)點的指針域置空*/returnH;}LNode*create_list(intn){LNode*head,*p,*q;inti;p=(LNode*)malloc(sizeof(LNode));head=p;for(i=1;i<=n;i++){q=(LNode*)malloc(sizeof(LNode));q->data=i;q->next=NULL;p->next=q;p=q;}return(head);}intinsert_list(LNode*head,inti){LNode*p,*s;intj;p=head;j=0;while((p!=NULL)&&(j<i-1)){p=p->next;j++;}if(p==NULL)return(0);s=(LNode*)malloc(sizeof(LNode));s=p->next;p->next=s->next;free(s);return(1);}voidmain(){LNode*list=NULL,*p=NULL;intn,i;scanf("%d",&n);list=create_list(n);p=list->next;while(p!=NULL){printf("%d\t",p->data);p=p->next;}scanf("%d",&i);insert_list(list,i);p=list->next;while(p!=NULL){printf("%d\t",p->data);p=p->next;}}樹樹的基本術(shù)語樹結(jié)點樹中一個獨立單元。包含一個數(shù)據(jù)元素及若干指向其子樹的分支。樹根樹中唯一沒有前趨的結(jié)點。結(jié)點的度(Degree)結(jié)點擁有的子樹數(shù)，稱為結(jié)點的度。樹的度樹中各結(jié)點的度的最大值。樹葉(Leaf)度為0的結(jié)點。也稱葉結(jié)點。除根和葉子以外的其他結(jié)點稱為中間結(jié)點。雙親(Parent)和孩子(Child)我們把一個樹結(jié)點的直接前趨稱之為該結(jié)點的雙親;反之把一個樹結(jié)點的所有直接后趨稱為該結(jié)點的孩子。兄弟(Sibling)同一雙親的孩子之間互稱為兄弟。結(jié)點的層次(Level)從根算起，根為第一層，根的孩子為第二層，樹中任一結(jié)點的層次等于它的雙親的層次加1。樹的深度(Depth)樹中各結(jié)點層次的最大值稱為樹的深度或高度。有序樹和無序樹如果樹中結(jié)點的各子樹可看成從左至右是有次序的(即不能互換)，則稱該樹為有序樹。否則稱為無序樹。在有序樹的最左邊的子樹的根稱為第一孩子。最右邊稱為最后一個孩子。森林(Forest)m(m20)棵互不相交的樹的集合。對樹中每個結(jié)點而言，其子樹的集合即為森林。由此也可以以森林和樹的相互遞歸定義來描述樹。踐性結(jié)構(gòu)存在唯一的沒有前聽的才首元素"存在唯一的沒有罰馳的蔣在唯一的沒有后繼的“尾元索*存在多亍沒有后繼的卄葉子M其余兀素均存在唯一的"前馳元素"和唯一的"后繼元素"其余結(jié)點均存在唯一的"前呃嚴親)結(jié)點"和雪個"后継骸孑)結(jié)點「二叉樹的重要性質(zhì)性質(zhì)1在二叉樹的第i層上的結(jié)點數(shù)最多為2i—1。性質(zhì)2在深度為k的二叉樹中至多有2k-1個結(jié)點。性質(zhì)3對于任何一個二叉樹T,若其葉子結(jié)點(度為0)數(shù)為n0,度為2的結(jié)點數(shù)為n2,則n0=n2+1。

滿二叉樹：一棵深度為k的二叉樹，若其有2k-1個結(jié)點，則稱為滿二叉樹。完全二叉樹：一個深度為k的二叉樹，其結(jié)點數(shù)n<2k-1,并且這n個結(jié)點所構(gòu)成的二叉樹，與一個深度為k的滿二叉樹前n個結(jié)點位置相同，則該樹為一棵深度為k的完全二叉樹。其前k-1層是滿二叉樹，最后k層的結(jié)點依次排在左邊的位置上。完全二叉樹的兩個性質(zhì)：性質(zhì)4具有n個結(jié)點完全二叉樹的深度為性質(zhì)5如果對一棵有n個結(jié)點完全二叉樹的結(jié)點按順序標號，標號的順序從根開始，按層次自上而下，自左至右，對于標號為i的結(jié)點有以下特性：i<>1時，i的雙親結(jié)點是.；2i<=n，則i的左孩子是標號為2i的結(jié)點；2i+l<二n，則i的右孩子是標號為2i+1的結(jié)點，若2i+l>n,則該結(jié)點不存在右孩子。二叉樹命令CreateBitree(BiTreeT)PreOrder(BiTreeT)InOrder(BiTreeT)PostOrder(BiTreeT)LevelOrder(BiTreeT)//構(gòu)造二叉鏈表表示的二叉樹CreateBitree(BiTreeT)PreOrder(BiTreeT)InOrder(BiTreeT)PostOrder(BiTreeT)LevelOrder(BiTreeT)//先序遍歷二叉樹//中序遍歷二叉樹//后序遍歷二叉樹DesTroyBiTree(BiTreeT)//銷毀二叉樹BiTreeEmpty(BiTreeT)DesTroyBiTree(BiTreeT)//銷毀二叉樹BiTreeEmpty(BiTreeT)//二叉樹是否為空BiTreeDepth(BiTreeT)//求二叉樹的深度先序根左右；中序左根右；后序左右根例子；寫岀二叉樹的三種基本遍歷序列先序序列二BCDEGF中序序列；CBEGDF后序序列：CGEFDB

假設(shè)某樹先序遍歷序列為ABCDEFGH；中序遍歷序列為CDBAFEHG,試畫出此樹。結(jié)論：給定結(jié)點的先序和中序序列,可唯一確定一棵二叉樹1哈夫曼樹定義：帶權(quán)路徑最短的樹。路徑：由從樹的根結(jié)點到其余結(jié)點的分支構(gòu)成一條路徑。路徑長度：路徑上的分支數(shù)目稱路徑長度。樹的路徑長度：指的是從樹根到樹中其余每個結(jié)點的路徑長度之和。記做PL。結(jié)點的帶權(quán)路徑：從根到帶權(quán)結(jié)點之間的路徑長度與結(jié)點的權(quán)值的乘積。樹的帶權(quán)路徑：樹中所有帶權(quán)結(jié)點的帶權(quán)路徑長度之和。記做WPL。長度WPL取最小的二叉樹,稱該二叉樹為最優(yōu)二叉樹也稱哈夫曼樹。（注意：最優(yōu)二叉樹中只有度為0和度為2的結(jié)點）??0最優(yōu)二叉樹：假設(shè)有n個權(quán)值｛w1,w2,?長度WPL取最小的二叉樹,稱該二叉樹為最優(yōu)二叉樹也稱哈夫曼樹。（注意：最優(yōu)二叉樹中只有度為0和度為2的結(jié)點）??0WPL=7X3+9X3+5X2+6X2+2X2=74WPL=2X1+6X3+7X4+9X44-5X2=94WPL=6X2+7X2+5X3+2X34-9X2=65WPL=2X1+5X3+7X3+9X3+6X3=83設(shè)給定權(quán)集w=｛2,3,4,7,8,9｝，試構(gòu)造關(guān)于w的一棵哈夫曼樹，并求其WPL。哈夫曼編碼約定左分支表示字符‘0'，右分支表示字符‘1'，則以由從根到葉子的路徑上的分支表示的字符組成的字符串作為該葉子結(jié)點字符的編碼。若以字符出現(xiàn)的次數(shù)為權(quán)，構(gòu)造一棵赫夫曼樹，由此得到的二進制前綴編碼便為“最優(yōu)前綴編碼”（哈夫曼編碼）。

已知在一份電文中只使用了7個字符A、B、C、D、E、F、G,其頻率分別為5,29,7,8,14，20，17。試寫出每個字符所對應(yīng)的哈夫曼編碼。樹的編程書中p圖鄰接矩陣與深度廣度遍歷鄰接矩陣(AdjacencyMatrix)是表示頂點之間相鄰關(guān)系的矩陣。EB20oB02D33E2A3EB20oB02D33E2A3A的鄰接謝［1下所示:紐盤M4科:V1->V2->V3->V4->V5深度優(yōu)先搜索：VA->VE->VC->VD->VB按照一個節(jié)點的方向一個一個搜索aecdb廣度優(yōu)先搜索：VA->VE->VB->VC->VD一層一層搜索一層結(jié)束后下一層繼續(xù)aebcd

深度優(yōu)先搜索：廣度優(yōu)先搜索：深度優(yōu)先搜索：廣度優(yōu)先搜索：V0->V1->V3->V7->V4->V2->V5->V6V0->V1->V2->V3->V4->V5->V6->V7最小生成樹圖的生成樹是不唯一的，從不同的頂點出發(fā)得到的生成樹是不同的，但是如果圖是帶權(quán)圖，則權(quán)值最小的生成樹是稱為最小生成樹。V0->V1->V3->V7->V4->V2->V5->V6V0->V1->V2->V3->V4->V5->V6->V7最小生成樹圖的生成樹是不唯一的，從不同的頂點出發(fā)得到的生成樹是不同的，但是如果圖是帶權(quán)圖，則權(quán)值最小的生成樹是稱為最小生成樹。5a關(guān)鍵路徑關(guān)鍵路徑：在AOE網(wǎng)中，從源點到匯點的帶權(quán)路徑長度最長的路徑稱為關(guān)鍵路徑。a->b->e->g->k(17) >k(IB)a.->c->e->g->k(15} a->c->e->h—>k(16)a->d->f->h->k (15)最短路徑求某源點到其余各頂點的最短路徑－單源最短路徑從圖中的某一個頂點出發(fā)，到圖中其余各個頂點的最短路徑，稱為單源最短路徑問題(Dijkstra算法)二叉排序樹對于每一個結(jié)點，若其左子樹非空，則左子樹的所有結(jié)點的關(guān)鍵值都小于該結(jié)點的關(guān)鍵值哈希表書上p快速排序交換排序之冒泡排序基本思想為：依次比較相鄰兩個記錄的關(guān)鍵字，若和所期望的相反，則互換這兩個記錄。關(guān)鍵字值較小(大)的元素就會像水中的氣泡一樣逐層浮起，直至完成