數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題要點(diǎn)(整理版)(存儲版)
【正文】 []=[]=NULL。 （5）路徑： 如果樹的結(jié)點(diǎn)序列n1, n2, …, nk有如下關(guān)系：結(jié)點(diǎn)ni是ni+1的雙親（1=ik），則把n1, n2, …, nk稱為一條由n1至nk的路徑；路徑上經(jīng)過的邊的個(gè)數(shù)稱為路徑長度。滿二叉樹：在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子都在同一層上。深度為k且具有2k1個(gè)結(jié)點(diǎn)的二叉樹一定是滿二叉樹性質(zhì)3：在一棵二叉樹中，如果葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則有: n0＝n2＋1。 }}（2） 中序遍歷（3） 后序遍歷4. 森林與二叉樹的轉(zhuǎn)換 （1）同級以左為親，即左一結(jié)點(diǎn)的右孩子是與它同級的右一結(jié)點(diǎn) （2）只認(rèn)最左路線為親子路線，即結(jié)點(diǎn)的左孩子是它下一級結(jié)點(diǎn)的最左的元素 5. 哈夫曼樹（1）哈夫曼樹的基本概念：哈夫曼樹：給定一組具有確定權(quán)值的葉子結(jié)點(diǎn)，帶權(quán)路徑長度最小的二叉樹。（構(gòu)建哈夫曼樹，很簡單，從小開始，計(jì)算相加，然后把所有葉子結(jié)點(diǎn)乘以等級數(shù)字然后相加。 技術(shù)資料 專業(yè)分享。哈夫曼樹不存在度為1的結(jié)點(diǎn)。 //先訪問 XianXu(Tlchild)。（3）二叉樹的性質(zhì)：性質(zhì)1：二叉樹的第i層上最多有2i1個(gè)結(jié)點(diǎn)（i≥1）。數(shù)據(jù)結(jié)構(gòu)中討論的一般都是有序樹 （10）樹通常有前序（根）遍歷、后序（根）遍歷和層序（次）遍歷三種方式（樹，不是二叉樹，沒中序遍歷。分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。 =( OLink *)malloc((m+1)*sizeof(OLink))。CrossList Creat（CrossList M）{ int m,n,t。 //矩陣包含的三元組表，data[0]未用 }TSMatrix。這些矩陣包括：對稱矩陣，三角矩陣，具有某種特點(diǎn)的稀疏矩陣等。}判斷?？眨篿nt listempty(struct list *head){if(headnext)return 0。 p=(struct list *)malloc(LEN)。 if(==p)==NULL。 =p。創(chuàng)建：LinkQueue InitQueue(LinkQueue Q){ ==(QueuePtr)malloc(sizeof(QNode))。已知鏈棧Q，編寫函數(shù)判斷?？?，如果?？談t進(jìn)行入棧操作，否則出棧并輸出。結(jié)構(gòu)：typedef struct list{ int listsize。同時(shí)，由于在插入或刪除時(shí)，為保持原有次序，平均需要移動(dòng)一半(或近一半)元素，修改效率不高。 pnext=( pnextnext )。 p=s。 //修改前趨的后繼指針 delete p。 //新點(diǎn)的后繼是原第i個(gè)點(diǎn) qnext=s。 q=get(head,i1)。 //單鏈表類型，即頭指針類型：lklist initlist() { pointer head。若線性表的主要操作是在最后一個(gè)元素之后插入一個(gè)元素或刪除最后一個(gè)元素，則采用順序表存儲結(jié)構(gòu)最節(jié)省運(yùn)算時(shí)間。 free(q)。1. 順序表結(jié)構(gòu)線性表的順序存儲是指在內(nèi)存中用地址連續(xù)的一塊存儲空間順序存放線性表的各元素，用這種存儲形式存儲的線性表稱為順序表。可行性：算法中的每一個(gè)步驟都應(yīng)當(dāng)能被有效的執(zhí)行，并得到確定的結(jié)果。（2）數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)內(nèi)的表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)是從數(shù)據(jù)元素之間存在的邏輯關(guān)系上描述數(shù)據(jù)與數(shù)據(jù)的存儲無關(guān)，是獨(dú)立于計(jì)算機(jī)的。WORD文檔 可編輯第一章 數(shù)據(jù)結(jié)構(gòu)概述基本概念與術(shù)語1．?dāng)?shù)據(jù)：數(shù)據(jù)是對客觀事物的符號表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序所處理的符號的總稱。（1）數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間存在的固有邏輯關(guān)系，常稱為數(shù)據(jù)結(jié)構(gòu)。若結(jié)構(gòu)為非空集，折每個(gè)數(shù)據(jù)可有多個(gè)（或零個(gè)）直接后繼。沒有歧義。 一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。 pnext = qnext 。在長度為N的順序表中，插入一個(gè)新元素平均需要移動(dòng)表中N/2個(gè)元素，刪除一個(gè)元素平均需要移動(dòng)（N1）/2個(gè)元素。 //結(jié)點(diǎn)類型,結(jié)點(diǎn)指針類型typedef pointer lklist。} ：（C語言中需要把head轉(zhuǎn)化為全局變量才能實(shí)現(xiàn)此程序）int insert(lklist head,datatype x,int i){ pointer q,s。 snext=qnext。 //保存待刪點(diǎn)地址 qnext=pnext。C. snext=pnext。A. n B. n/2 C. (n1)/2 D. O(n㏒2n) 6. 給定有n個(gè)元素的向量，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度（B）(1) (n) (n2) (n㏒2n)(B)(1) (n) (n2) (n㏒2n)8. 在一個(gè)單鏈表中刪除q所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行如下操作：q=pnext。但它的空間大小一經(jīng)定義，在程序整個(gè)運(yùn)行期間不會(huì)發(fā)生改變，因此，不易擴(kuò)充。第三章 棧和隊(duì)列1. 棧（1） 棧的結(jié)構(gòu)與定義定義：限定僅在表尾進(jìn)行插入或刪除操作的線性表。對于棧和隊(duì)列，無論他們采用順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu)，進(jìn)行插入和刪除操作的時(shí)間復(fù)雜度都是O(1)（即與已有元素N無關(guān)）。 }LinkQueue。
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1