數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)重點知識點總結(jié)

第一章緒論一、數(shù)據(jù)結(jié)構(gòu)包括：邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運算（操作）三方面內(nèi)容。二、線性結(jié)構(gòu)特點是一對一。樹特點是一對多 圖特點是多對多數(shù)據(jù)結(jié)構(gòu)的四種存儲結(jié)構(gòu)：順序存儲、鏈?zhǔn)酱鎯?、索引存儲、散列存儲順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的區(qū)別？線性結(jié)構(gòu)的順序存儲結(jié)構(gòu)是一種隨機(jī)存取的存儲結(jié)構(gòu)。線性結(jié)構(gòu)的鏈?zhǔn)酱鎯κ且环N順序存取的存儲結(jié)構(gòu)。邏輯結(jié)構(gòu)分類：集合線性樹圖，各自的特點?；蛘叻譃榫€性結(jié)構(gòu)和非線性結(jié)構(gòu)。算法的特征P13五、時間復(fù)雜度(1)i=1;k=0;

while(i<n)

{k=k+10*i;i++;

}

分析：

i=1;//1

k=0;//1

while(i<n)//n

{k=k+10*i;//n-1

i++;//n-1

}

由以上列出的各語句的頻度，可得該程序段的時間消耗：

T(n)=1+1+n+(n-1)+(n-1)=3n

可表示為T(n)=O(n)

六、數(shù)據(jù)項和數(shù)據(jù)元素的概念。第二章線性表一、線性表有兩種存儲結(jié)構(gòu)：順序存儲和鏈?zhǔn)酱鎯Γ髯缘膬?yōu)、缺點。線性表的特點。三、順序表的插入、思想、時間復(fù)雜度o(n)、理解算法中每條語句的含義。（1）插入的條件：不管是靜態(tài)實現(xiàn)還是動態(tài)實現(xiàn)，插入的過程都是從最后一個元素往后挪動，騰位置。靜態(tài)是利用數(shù)組實現(xiàn)，動態(tài)是利用指針實現(xiàn)。不管靜態(tài)還是動態(tài)，在表中第i個位置插入，移動次數(shù)都是n-i+1。四、順序表的刪除、思想、時間復(fù)雜度o(n)、理解算法中每條語句的含義。（1）刪除的條件：不管是靜態(tài)實現(xiàn)還是動態(tài)實現(xiàn)，刪除的過程都是從被刪元素的下一位置向前挪動。靜態(tài)是利用數(shù)組實現(xiàn)，動態(tài)是利用指針實現(xiàn)。不管靜態(tài)還是動態(tài)，刪除表中第i個元素，移動次數(shù)都是n-i。五、順序表的優(yōu)缺點？為什么要引入鏈表？答：順序表的優(yōu)點是可以隨機(jī)存取，缺點是前提必須開辟連續(xù)的存儲空間且在第一位置做插入和刪除操作時，數(shù)據(jù)的移動量特別大。如果有一個作業(yè)是100k，但是內(nèi)存最大的連續(xù)存儲空間是99K，那么這個作業(yè)就不能采用順序存儲方式，必須采用鏈?zhǔn)酱鎯Ψ绞?。六、順序表和鏈表合并七、帶頭結(jié)點不為空的單鏈表的條件是什么？L->next!=NULL;帶頭結(jié)點為空的條件是什么？L->next==NULL;不帶頭結(jié)點不為空的單鏈表的條件是什么？L!=NULL;不帶頭結(jié)點為空的單鏈表的條件是什么？L==NULL;帶頭結(jié)點的雙循環(huán)鏈表為空的條件是？L->next==L->prior==L頭指針、頭結(jié)點、首元結(jié)點（第一個結(jié)點）的概念單鏈表中插入、刪除相關(guān)操作。雙鏈表的插入和刪除。第三章棧和隊列一、棧和隊列的特點、相同點和不同點。舉例說明其不同點。棧的特點：先進(jìn)后出或后進(jìn)先出。隊列特點：先進(jìn)先出。棧和隊列的相同點是只允許在端點處插入和刪除元素不同點：二、循環(huán)隊列的相關(guān)操作。1、置空隊列Voidinitqueue(cirqueue*q){q->front=q->rear=0;q->count=0;}2、判空intqueueempty(cirqueue*q){if(q->count==0)return(1);elsereturn(0);}3、判隊滿intqueuefull(cirqueue*q)｛retuenq->count=maxsize;｝4、入隊voidenqueue（cirqueue*q,datatypex）{if(q->count==m)//判隊滿{printf(“overflow“);exit(0);}q->data[q->rear]=x;q->rear=(q->rear+1)%M;q->count++;}5、出隊datatypedequeue(cirqueue*q){if(q->count==0)//判隊空{(diào)printf(“queuenull“);exit(0);}Temp=q->data[q->font]q->count--;q->front=(q->front+1)%m;//刪除隊頭元素}6、取隊頭元素datatypegetqueue(cirqueue*q)｛if(q->count==0){printf(“queuenull“);exit(0);}returnq->data[q->font];}三、理解順序表、順序棧、順序隊的區(qū)別？順序表：可以在任意合法的位置上做插入和刪除。順序棧：只可以在順序表的同一端上做插入和刪除。順序隊：在順序表的一端做插入，另一端做刪除。理解鏈表、鏈棧、鏈隊的區(qū)別？鏈表：可以在任意合法的位置上做插入和刪除。鏈棧：只可以在鏈表的首結(jié)點位置做插入和刪除。鏈隊：在鏈表的首結(jié)點位置做刪除，尾結(jié)點后做插入。四、(題)若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前的rear和front的值分別為2和5，當(dāng)從隊列中刪除一個元素，再插入兩個元素后，rear和front的值分別為__2__、__4__。五、(題)設(shè)環(huán)形隊列數(shù)組的下標(biāo)是0～N-1,其頭尾指針分別為f和r，則其元素個數(shù)為:（r-f+N）%N第五章數(shù)組一、數(shù)組不能做插入和刪除，只能做取值和賦值操作。二、數(shù)組只能采取順序存儲（行優(yōu)先和列優(yōu)先）三、數(shù)組行優(yōu)先計算公式（下標(biāo)從0和1開始）（假設(shè)每個數(shù)據(jù)元素占L個存儲單元，則數(shù)組A中任一元素aij的存儲位置為：）LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*LLOC(aij)=LOC(a00)+[i*n+j]*L數(shù)組列優(yōu)先計算公式（下標(biāo)從0和1開始）LOC(aij)=LOC(a11)+[(j-1)*m+i-1]*LLOC(aij)=LOC(a00)+[j*m+i]*L四、為什么要對特殊矩陣進(jìn)行壓縮存儲？答：主要為了節(jié)省存儲空間。對稱矩陣和三角矩陣各長什么樣？（對稱矩陣以對角線是對稱的三角矩陣是非零數(shù)組成三角形）六、對稱矩陣的壓縮存儲所需存儲空間至少n(n+1)/2。三角矩陣的壓縮存儲所需存儲空間至少n(n+1)/2+1。七、對稱矩陣的壓縮存儲可以存其下三角上的元素公式八、（題）廣義表取表頭和取表尾第六章樹一、（二叉樹）樹的四個性質(zhì)性質(zhì)1：二叉樹的第i層上至多有2i-1（i31）個結(jié)點。性質(zhì)2：深度為k的二叉樹中至多2k-1個結(jié)點。性質(zhì)3：對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0＝n2＋1。性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度k為└log2n┘+1。二、滿二叉樹和完全二叉樹的區(qū)別是什么？滿二叉樹一定是完全二叉樹，但是完全二叉樹不一定是滿二叉樹。深度為k的二叉樹，最少有k個結(jié)點，最多有2k-1深度為k的完全二叉樹，最少有2k-1-1k-1層全是滿的+1個結(jié)點,最多有2k-1k-1層全是滿的二叉樹的遍歷？（128頁）四、樹.森林和二叉樹的相互轉(zhuǎn)換（138頁）五、樹、森林的遍歷（138頁）六、赫夫曼樹（又稱最優(yōu)二叉樹或哈夫曼樹）、赫夫曼樹編碼1.赫夫曼樹中，權(quán)越大的葉子離根越近，其形態(tài)不唯一，但是WPL帶權(quán)路徑長度一定是最小。2.一定要會構(gòu)造赫夫曼樹，在構(gòu)造好的赫夫曼樹上會構(gòu)造赫夫曼編碼。（認(rèn)真看題目要求）（146頁）七、遞歸算法設(shè)計題1．已知二叉樹中的結(jié)點類型用BiTNode表示，被定義描述為：TypedefstructBiTNode{TElemTypedata;structBiTNode*LChild,*RChild;}BiTNode,*BiTree;其中data為結(jié)點值域，LChild和RChild分別為指向左、右孩子結(jié)點的指針域，編寫出求一棵二叉樹高度的算法。IntBTreeHeight(BiTreeBT){if(BT==NULL)return0;else{h1=BTreeHeight(BT->LChild);h2=BTreeHeight(BT->RChild);if(h1>h2)return(h1+1);elsereturn(h2+1);}}2．已知二叉樹中的結(jié)點類型用BiTNode表示，被定義描述為：TypedefstructBiTNode{TElemTypedata;structBiTNode*LChild,*Rchild；}BiTNode,*BiTree；BiTreeT；其中data為結(jié)點值域，LChild和RChild分別為指向左、右孩子結(jié)點的指針域，編寫算法，求出二叉樹中2度結(jié)點個數(shù)。intdegree2nodenum(BiTreeT){if(T){if(T->lchild！=NULL&&T->child！=NULL)count++;leafnodenum(l->lchild);leafnodenum(l->rchild);}returncount;}3．已知二叉樹中的結(jié)點類型用BiTNode表示，被定義描述為：TypedefstructBiTNode{TElemTypedata;structBiTNode*LChild,*RChild;}BiTNode,*BiTree;BiTreeT；其中data為結(jié)點值域，LChild和RChild分別為指向左、右孩子結(jié)點的指針域，寫一算法，求出二叉樹中的葉子結(jié)點個數(shù)。voidBTreeLeaf(BiTreeBT){if(BT){if(BT->LChild==NULL&&BT->RChild==NULL)count++;BTreeLeaf(BT->LChild);//訪問左子樹BTreeLeaf(BT->RChild);//訪問右子樹}}或下面算法均可編寫遞歸算法，計算二叉樹中葉子結(jié)點的數(shù)目。intLeafCount_BiTree(BitreeT)//求二叉樹中葉子結(jié)點的數(shù)目

{

if(!T)return0;//空樹沒有葉子

elseif(!T->lchild&&!T->rchild)return1;//葉子結(jié)點

elsereturnLeaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子樹的葉子數(shù)加上右子樹的葉子數(shù)

}//LeafCount_BiTreePPT上的三種遍歷遞歸算法和課本上P131先序遞歸創(chuàng)建二叉鏈表。先序遍歷的遞歸算法：voidNLR(BinTreeT){if(T!=null){printf("%c",T->data);NLR(T->Lchild);NLR(T->Rchild);}}中序遍歷的遞歸算法：voidLNR(BinTreeT){if(T!=null){NLR(T->Lchild);printf("%c",T->data);NLR(T->Rchild);}}后序遍歷的遞歸算法：voidNLR(BinTreeT){if(T!=null){NLR(T->Lchild);NLR(T->Rchild);printf("%c",T->data);}}5.給定一棵二叉樹，其根指針為root。試寫出求二叉樹結(jié)點數(shù)目的算法（遞歸算法或非遞歸算法）。 【提示】采用遞歸算法實現(xiàn)。intcount(BiTreet){if(t==NULL)return0;elsereturncount(t->lchild)+count(t->rchild)+1;}6.以二叉鏈表為存儲結(jié)構(gòu)，寫一算法交換各結(jié)點的左右子樹?！痉治觥恳李}意，設(shè)t為一棵用二叉鏈表存儲的二叉樹，則交換各結(jié)點的左右子樹的運算基于后序遍歷實現(xiàn)：交換左子樹上各結(jié)點的左右子樹；交換右子樹上各結(jié)點的左右子樹；再交換根結(jié)點的左右子樹。【算法】voidExchg(BiTree*t){BinNode*p;if(t){P=(*t)->lchild;(*t)->lchild=(*t)->rchild;(*t)->rchild=p;Exchg(&((*t)->lchild));Exchg(&((*t)->rchild));}}7.已知一棵二叉樹采用二叉鏈表結(jié)構(gòu)存儲，每個結(jié)點的值為整數(shù)類型。要求：給出相應(yīng)的語言描述，在此基礎(chǔ)上設(shè)計計算二叉樹中所有結(jié)點值之和的算法。typedefstructlink{intdata;structlink*lchild;structlink*rchild;}bitnode,*bitree;voidsum(bitree*bt,int&s){ if(bt!=0){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);} }第七章圖一、圖的相關(guān)概念，公式圖是一種較線性表和樹更為復(fù)雜的數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)。公式：G(V,E)二、連通、連通圖、強(qiáng)連通、強(qiáng)連通圖的概念、連通分量、強(qiáng)連通分量連通、連通圖、連通分量◆連通：無向圖中，若vi到vj有一條路徑，則稱vi,vj連通?！暨B通圖：無向圖中若對于任意兩個不同的頂點vi和vj都連通，稱G為連通圖。例：無向圖G3和無向圖G4都是連通圖◆連通分量：無向圖中G的最大連通子圖稱為G的連通分量。任何連通圖的連通分量只有一個，即是其自身。

非連通的無向圖有多個連通分量。◆強(qiáng)連通：有向圖中,vi–vj及vj—vi都有路徑，則vi,vj強(qiáng)連通。◆強(qiáng)連通圖：有向圖中若對于任意兩個不同的頂點vi和vj都存在從vi到vj及vj到vi的路徑，則稱G是強(qiáng)連通圖?！魪?qiáng)連通分量：有向圖的極大強(qiáng)連通子圖稱為G的強(qiáng)連通分量。任何強(qiáng)連通圖的強(qiáng)連通分量只有一個，即是其自身。非強(qiáng)連通的有向圖有多個強(qiáng)連通分量。三、圖有兩種存儲結(jié)構(gòu)：鄰接矩陣和鄰接表。1.給出一個圖，必須會寫出其鄰接矩陣和鄰接表。2.要會在鄰接矩陣和鄰接表上進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷。3．各自特點。4．兩種存儲結(jié)構(gòu)上會做遍歷四、最小生成樹第九章查找一、折半查找為什么不適用于鏈表存儲結(jié)構(gòu)？從折半查找過程看，以表的中點為比較對象，并以中點將表分割為兩個子表，對定位到的子表繼續(xù)這種操作。所以，對表中每個數(shù)據(jù)元素的查找過程，可用二叉樹來描述，稱這個描述查找過程的二叉樹為判定樹。二、折半查找的過程、判定樹、成功平均查找長度？過程：先確定待查記錄所在的范圍（區(qū)間），然后逐步縮小范圍直到找到或找不到該記錄為止。三、堆積、沖突、同義詞的概念同義詞：k1≠k2，但H（k1）＝H（k2），即映射到同一哈希地址上的關(guān)鍵碼k1和k2為同義詞。沖突：k1≠k2，但H（k1）＝H（k2），將不同的關(guān)鍵碼映射到同一個哈希地址上，即同義詞之間發(fā)生地址爭奪的現(xiàn)