理工類專業(yè)課復(fù)習(xí)資料-數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)要點(diǎn)(整理版)

結(jié)構(gòu)概述 的邏輯結(jié)構(gòu)是從數(shù)據(jù)元素之間存在的邏輯關(guān)系上描述數(shù)據(jù)與數(shù)據(jù)的存儲無關(guān)，是沒有其他關(guān)系。直接后繼。多個(或零個)直接后繼。(2)數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計算機(jī)內(nèi)的表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)。i++OOlogn)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)(1)算法的5個特性序不需要有有窮性)(2).算法設(shè)計的要求：1、正確性(達(dá)到預(yù)期效果，滿足問題需求)不3、可讀性(要求算法易于理解，便于分析)可擴(kuò)展性5、高效率(較好的時空性能)據(jù)存儲結(jié)構(gòu)一般有兩種類型，它們分別是順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)情況下，一個算法的時間復(fù)雜度是問題規(guī)模的函數(shù)指數(shù)階O(2^n)。通常認(rèn)為，具有常數(shù)階量級的算法是好算法，而具有指數(shù)階量級的算法是線性表單鏈表(1)鏈表結(jié)點(diǎn)結(jié)構(gòu)(2)鏈表操作算法：初始化、插入、輸出、刪除、遍歷Pnextqnext;free(q);平均需要移動(N-1)/2個元素。插入一個元素或刪除最后一個元素，則采用個元素)的地址=a[0]+12*3)typedefintdatatype;typedefstructnode{pedatadenext//結(jié)點(diǎn)結(jié)構(gòu)//雙向鏈表還應(yīng)加上*previousLnodepointer點(diǎn)指針類型typedefpointerlklist;//單鏈表類型，即頭指針類型lklistinitlist(){pointerhead;ofLnodeCLLheadnextheadreturnhead}adintinsertlklistheaddatatypexinti){pointerq,s;{return0;}desnextqnext//新點(diǎn)的后繼是原第i個點(diǎn)xtsreturn1;}//插入成功intdelete(lklisthead,inti){pointerp,q;urnp=q->next;nextpnextepreturn1;//保存待刪點(diǎn)地址//修改前趨的后繼指針ep//刪除成A.head=NULLB.head->next=NULLC.head->next=headD.head!=NULLA.head=NULLB.head->next=NULLC.head->next=headD.head!=NULLA.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;Ap->next=p->next->next;B.p=p->next;p->next=p->next->next;C.p->next=p->nextDp=p->next->next平均比較(B)個結(jié)點(diǎn)。6.給定有n個元素的向量，建立一個有序單鏈表的時間復(fù)雜度(B)nextp->next=(p->next->next);qsnextp->next)(1))；在給定值為x的結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)的時間復(fù)雜度是(O(n))。表示各有哪些主要優(yōu)缺點(diǎn)?隊列(1)棧的結(jié)構(gòu)與定義typedefstructlist{istsizeistheadistbase}//棧的容量//棧頂指針//棧底指針(3)鏈棧的結(jié)構(gòu)與定義2.隊列(1)隊列的定義------------------------------------------------------------------------------------------------------ABCDE是(B)A.BCDAEB.EDACBC.BCADED.AEDCB2、棧的順序表示中，用TOP表示棧頂元素，那么?？盏臈l件是(D)ATOPSTACKSIZEBTOPCTOP0D.TOP==-1、允許在一端插入，在另一端刪除的線性表稱為隊列。插入的一端為表頭，刪除的一端為、對于棧和隊列，無論他們采用順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu)，進(jìn)行插入和刪除操作的)明顯的優(yōu)點(diǎn)是：(D)A操作比較容易B.刪除操作比較容易C情況D.不會出現(xiàn)棧滿的情況typedefstructQNodeteQNodenexttypedefstructtrfrontPtrrearLinkQueueInitQueueLinkQueueQ){QfrontQrearQueuePtrmallocsizeofQNode));rontnextNULLreturnQ);}LinkQueueEnQueueLinkQueueQinte){PtrppQueuePtr)malloc(sizeof(QNode));p->date=e;p->next=NULL;xtppreturnQ);}LinkQueueDeQueueLinkQueueQ){ntePtrpp=Q.front->next;terontpnextprintf"%d",e);ifQrearpQrearQfront=NULL;returnQ);}listcreat{listppstructlist*)malloc(LEN);p>next=NULL;returnp;}structlistpushstructlistheadinta{ctlistppstructlist*)malloc(LEN);p>num=a;p->next=head;returnp;}ructlistpopstructlisthead{listpp=head->next;adreturnp;}ntlistemptystructlisthead{ifheadnextreturn0;elsereturn1;}3.將特殊矩陣中的元素按相應(yīng)的換算方式存入數(shù)組中。這些矩陣包括：對稱矩陣，三角矩ypedefstructjtypedefstruct/元素行下標(biāo)及列下標(biāo)//元素值unutuaMAXSIZE//矩陣的行數(shù)、列數(shù)、非零元素個數(shù)typedefstructOLNode{ij/元素行下標(biāo)及列下標(biāo)//元素值structOLNoderightdown行的后繼以及列的后繼typedefstructunutuinkrheadchead//矩陣的行數(shù)、列數(shù)、非零元素個數(shù)//行和列的表頭指針組的首地址CrossListCreat(CrossListM){tscanfdddmnt;MmumMnunM.tu=t;MrheadOLink)malloc((m+1)*sizeof(OLink));McheadOLinkmalloc((n+1)*sizeof(OLink));MrheadMchead[]=NULL;}//開辟行表頭指針組//開辟行列頭指針組//初始化接下來就是賦值和入鏈(1)樹的概念及術(shù)語⑵當(dāng)n＞1時，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成m(m>0)個互不相交的有限集合(2)結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹的個數(shù)。(3)葉子結(jié)點(diǎn)：度為0的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。(4)孩子、雙親：樹中某結(jié)點(diǎn)的子樹的根結(jié)點(diǎn)稱為這個結(jié)點(diǎn)的孩子結(jié)點(diǎn)，這個結(jié)點(diǎn)稱為它(6)祖先、子孫：在樹中，如果有一條路徑從結(jié)點(diǎn)x到結(jié)點(diǎn)y，那么x就稱為y的祖先，(7)結(jié)點(diǎn)所在層數(shù)：根結(jié)點(diǎn)的層數(shù)為1；對其余任何結(jié)點(diǎn)，若某結(jié)點(diǎn)在第k層，則其孩子 (8)層序編號：將樹中結(jié)點(diǎn)按照從上層到下層、同層從左到右的次序依次給他們編以從1(9)有序樹、無序樹：如果一棵樹中結(jié)點(diǎn)的各子樹從左到右是有次序的，稱這棵樹為有序樹。數(shù)據(jù)結(jié)構(gòu)中討論的一般都是有序樹 (10)樹通常有前序(根)遍歷、后序(根)遍歷和層序(次)遍歷三種方式(樹，(1)二叉樹的定義：二叉樹是n(n≥0)個結(jié)點(diǎn)的有限集合，該集合或者為空集(稱為空叉樹)，或者由一個根結(jié)點(diǎn)和兩棵互不相交的、分別稱為根結(jié)點(diǎn)的左子樹和右子樹的二叉全二叉樹。(3)二叉樹的性質(zhì)：號為i(1≤i≤n)的結(jié)點(diǎn)(簡稱為結(jié)點(diǎn)i)，有：ii雙親結(jié)點(diǎn)的序號為i/2；如果i＝1，則結(jié)點(diǎn)i是根結(jié)點(diǎn)，無雙iinii(1)先序遍歷anXuBiTreeTTprintfcTdata//先訪問XianXuTlchild//再繼續(xù)遍歷}}(2)中序遍歷(3)后序遍歷森林與二叉樹的轉(zhuǎn)換(1)同級以左為親，即左一結(jié)點(diǎn)的右孩子是與它同級的右一結(jié)點(diǎn)(2)只認(rèn)最左路線為親子路線，即結(jié)點(diǎn)的左孩子是它下一級結(jié)點(diǎn)的最左的元素哈夫曼樹(1)哈夫曼樹的基本概念：第七章圖(2)哈夫曼樹的特點(diǎn)：2.只有度為0(葉子結(jié)點(diǎn))和度為2(分支結(jié)點(diǎn))的結(jié)點(diǎn)，不存在度為1的結(jié)點(diǎn).(3)哈夫曼樹的構(gòu)造算法思想及構(gòu)造過程(森林與哈夫曼編碼)乘之后疊加的最小值。------------------------------------------------------------------------------------------------------------1、已知一棵完全二叉樹有47個結(jié)點(diǎn)，則該二叉樹有(C)個葉子結(jié)點(diǎn)。A.6B.12C.24D.4831=16=16+8=24n叉樹的前序序列ABCDEFG和中序序列CBEDAFG，那么是下面哪棵樹(C)。A↘BF↘CDG↙E4、完全二叉樹必須滿足的條件為:：一棵具有n個結(jié)點(diǎn)的二叉樹，它的結(jié)構(gòu)與滿二叉樹的路徑長度=葉結(jié)點(diǎn)的權(quán)值*路徑長度)最后一個頂點(diǎn)相同的路徑叫做回路或環(huán)出現(xiàn)的路徑叫簡單路徑若圖中任意兩個頂點(diǎn)之間存在路徑(不一定是直接相連)，則稱作連通圖VR圖的遍歷(1)深度優(yōu)先遍歷與其有關(guān)未被訪問的所有鄰接頂點(diǎn)，并從該頂點(diǎn)開始進(jìn)行訪問(2)廣度優(yōu)先遍歷