第一篇：數(shù)據(jù)結(jié)構(gòu)C章節(jié)總結(jié)
第一章 緒論
數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)就是數(shù)據(jù)的組織形式，也可看成是包含數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)表，說明數(shù)據(jù)之間存在著一定的相互關(guān)系或約束。數(shù)據(jù)結(jié)構(gòu)被形式地定義為(D,R),其中D是數(shù)據(jù)元素的有限集合,R是D上的關(guān)系有限集合.數(shù)據(jù)類型：一個值的集合和定義在這個值集上的一組操作的總稱；數(shù)據(jù)運算：對數(shù)據(jù)施加的一種操作；數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個概念之間區(qū)別：簡單地說，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素。數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素，而且還在其上定義了一組操作。
邏輯結(jié)構(gòu)：我們把只表現(xiàn)元素之間邏輯關(guān)系，而不涉及它們在計算機中的表示，只是理論的、反映在紙面上的東西，這種抽象的數(shù)據(jù)結(jié)構(gòu)稱為邏輯結(jié)構(gòu)。
物理結(jié)構(gòu)：抽象的數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)的表示，也就是映射在存儲空間上的、具體的數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)表示，也就是映射在存儲空間上的、具體的數(shù)據(jù)結(jié)構(gòu)。
數(shù)據(jù)：是對客觀事物的符號表示，在計算機科學(xué)中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱；數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)的最小單位。
數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。
數(shù)據(jù)結(jié)構(gòu)：是相互之間一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性。數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)（線性結(jié)構(gòu)，如線性表，棧，隊，串，數(shù)組 和非線性結(jié)構(gòu)如 樹結(jié)構(gòu)、圖結(jié)構(gòu)）、物理（存儲）結(jié)構(gòu)（集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)）和數(shù)據(jù)運算如插入、刪除、修改、排序、查找。數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的數(shù)據(jù)叫邏輯結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指數(shù)據(jù)的存儲結(jié)構(gòu)
四大類存儲結(jié)構(gòu)：順序存儲、鏈?zhǔn)酱鎯Α⑺饕鎯蜕⒘写鎯?。順序存儲包括?shù)據(jù)存儲（把邏輯上相鄰的元素存儲在地址連續(xù)的存儲單位）和數(shù)據(jù)關(guān)系存儲（通過連續(xù)的物理地址體現(xiàn)關(guān)系）；鏈?zhǔn)酱鎯Π〝?shù)據(jù)存儲（把邏輯上相鄰的元素存放在物理地址隨意的存儲單元）和數(shù)據(jù)關(guān)系存儲（不僅存放數(shù)據(jù)本身還存放數(shù)據(jù)元素的物理地址）
抽象數(shù)據(jù)類型ADT：一個數(shù)學(xué)模型以及定義在該模型上的一組操作，包括_數(shù)據(jù)和操作_兩個部分 算法的特性：有窮性（執(zhí)行有窮步結(jié)束）、確定性（確切含義，不會產(chǎn)生二義性）、可行性、輸入（零個或多個輸入）和輸出（一個或多個輸出）
算法設(shè)計的要求：正確性、可讀寫、健壯性、效率與低存儲量需求。
2、數(shù)據(jù)的邏輯結(jié)構(gòu)是指圖形結(jié)構(gòu)_三種類型，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為非線性結(jié)構(gòu)_。數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)４種。
17_稱為存儲結(jié)構(gòu).1821、算法的執(zhí)行時間是
371、某算法的時間復(fù)雜度為O(n2),表明該算法的_____.2.算法分析的目的是問題規(guī)模之間的關(guān)系;算法分析的兩個主要方面是空間復(fù)雜度和時間復(fù)雜度
5．在決定選取何種存儲結(jié)構(gòu)時，一般不考慮
A.各結(jié)點的值如何B.結(jié)點個數(shù)的多少C.對數(shù)據(jù)有哪些運算D.編程語言實現(xiàn)這種結(jié)構(gòu)是否方便。
10．程序段i ＝ 0；while（i<=n）｛i = i * 3
12數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)的數(shù)據(jù)項的類型要一致 1.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的系和運算等的學(xué)科。數(shù)據(jù)結(jié)構(gòu)式相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。10.數(shù)據(jù)的運算最常用的有5-1-
第二章 線性表
1.線性表:一個線性表是n個類型相同的數(shù)據(jù)元素的有限序列。線性表的順序表示：用一組地址連
續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。順序存儲結(jié)構(gòu)的特點：優(yōu)，可隨機存取表中任一元素，方便快捷；缺，再插入或刪除時，需移動大量元素，數(shù)組的靜態(tài)空間分配。
2.線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點：線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是 一對一的，非線性結(jié)構(gòu)反
映結(jié)點間的邏輯關(guān)系是多對多的。
3.從一個具有n個節(jié)點的單鏈表中查找其值等于x結(jié)點時，在查找成功的情況下，需平均比較個結(jié)點,4.在一個單鏈表中，已知*q結(jié)點是*p結(jié)點的前驅(qū)結(jié)點，若在*q和*p之間插入*s結(jié)點，則執(zhí)行 5.對順序存儲的線性表，設(shè)其長度為n，在任何位置上插入或刪除操作都是等概率的，刪除一個
元素時大約要移動表中的(n-1)/2兩種情況下求平均個元素。
6.設(shè)單鏈表中指針p指著結(jié)點m，指針f指著將要插入的新結(jié)點x，當(dāng)x插在鏈表中最后一個結(jié)點
m之后時，只要先修改后修改p->link=f即可。
7.在一個長度為n的順序存儲的線性表中，刪除第i個元素(1<=i<=n)時，需要從前向后依次前移i個元素前插入元素需移動
存儲結(jié)構(gòu)需要分配較大空間，插入和刪除不需要移動元素的線性表
9、在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點時需修改指針p所指的結(jié)點的前趨結(jié)點（若存在）時需修改指針
1.在循環(huán)雙鏈表的p所指結(jié)點之前插入s所指結(jié)點的操作是12.若某表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點，則采用_結(jié)點的雙循環(huán)鏈表__存儲方式最節(jié)省運算時間；某線性表最常用的操作是在最后一個結(jié)點之后插
入一個結(jié)點或刪除第一個結(jié)點，故采用_僅有尾指針的單循環(huán)鏈表存儲方式最節(jié)省運算時間；對
于只在表的首、尾兩端進行插入操作的線性表,宜采用的存儲結(jié)構(gòu)為用尾指針表示的循環(huán)單鏈表
14.15.16.17、不帶頭結(jié)點的單鏈表head為空的判定條件是 帶頭結(jié)點的~是
19、帶頭結(jié)點的雙循環(huán)表L為空表的條件是。
20、非空的循環(huán)單鏈表head的尾結(jié)點(由p所指向)滿足21.在一個長度為n(n>1)操作與鏈表的長度有關(guān)；與單鏈表相比，雙鏈表的優(yōu)點之一是順序訪問相鄰結(jié)點更靈活
23線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過鏈接指針決定的。
24、從順序表中刪除第i個元素時，首先把第i個元素賦給_針開始向后的所有元素均前移一個位置，最后使線性表的長度減1。
25,26、循環(huán)單鏈表L為空的條件是
27、在以ＨＬ為表頭指針的帶表頭附加結(jié)點的單鏈表和循環(huán)單鏈表中，鏈表為空的條件分別為。
28、在線性表的單鏈接存儲中，若一個元素所在結(jié)點的地址為p，則其后繼結(jié)點的地址為，若p為一個數(shù)組a中的下標(biāo)，則其后繼結(jié)點的下標(biāo)的a[p].next。
29、在由數(shù)組a中元素結(jié)點構(gòu)成的單鏈表中，在下標(biāo)為i的結(jié)點的后面插入一個下標(biāo)為j的結(jié)點
時，需要進行的操作為a[j].next=a[i].next和a[i].next=j語句。
第三章 棧和隊列
1.棧：是限定僅在表尾進行插入或刪除操作的線性表。棧又稱為先進后出LIFO的線性表。
2.判定一個棧ST（最多元素為m0）為空的條件是
2.棧的兩種存儲方法：一是順序棧，即棧的順序存儲結(jié)構(gòu)是利用一組地址連續(xù)的存儲單元依次存
放自棧底到棧頂?shù)脑?；二是棧的鏈?zhǔn)奖硎尽?/p>
3.隊列：隊列是一種先進先出FIFO的線性表。允許插入的一端叫做隊尾rear，允許刪除的一段則
稱為隊頭front
4.鏈隊的出隊入隊操作：s入隊,rear->next=s;rear=s;p出隊：front->next=p->next
5.順序隊：插入元素：front不變，rear加1；刪除元素：rear不變，front加1。判定一個順序棧
st(最多元素為MaxSize)為空的條件是6.循環(huán)隊列:空隊滿隊都是rea=r=front為區(qū)分,規(guī)定循環(huán)隊列中剩一個元素即為滿隊,front=rear+1
7.8.9.向一個棧項指針為hs的鏈棧中插入一個*s結(jié)點時，則執(zhí)行。
10.在一個鏈隊列中，假定front和rear分別為隊首指針和隊尾指針，則進行插入*s結(jié)點的操作時
應(yīng)執(zhí)行rear->next=s;rear=s;
11.若己知一個棧的進棧序列是1,2,…,n,其輸出序列為p1,p2,p3,…,pn,若p1=n,則pi(1 23、判定一個環(huán)形隊列qu(最多元素為MaxSize)為空的條件是是(qu->rear+1)%MaxSize==qu->front 列的元素個數(shù)是(rear-front+MaxSize)%MaxSize。 24.從一個不帶頭結(jié)點的棧頂指針為1st的鏈棧中刪除一個結(jié)點時,用x保存被刪結(jié)點的值,則執(zhí)行5.棧頂指針 7.在鏈表qu中,判定只有一個結(jié)點的條件是設(shè)有一個順序棧S,元素s1,s2,s3,s4,s5,s6依次進棧,如果6個元素的出棧順序為s2,s3,s4,s6,s5,s1,則順序棧的容量至少應(yīng)為3。 9.設(shè)計一個判別表達(dá)式中左、右括號是否配對出現(xiàn)的算法，采用數(shù)據(jù)結(jié)構(gòu)最佳 例：設(shè)有編號為1，2，3，4的四輛列車，順序進入一個棧式結(jié)構(gòu)的車站，具體寫出這四輛 列車開出車站的所有可能的順序。 答：至少有14種①全進之后再出情況,只有1種：4，3，2，1②進3個之后再出的情況，有 3種，3,4,2,13,2,4,13,2,1,4③進2個之后再出的情況,有5種，2,4,3,12,3,4,12,1, 3,4 2,1,4,32,1,3,4④進1個之后再出的情況,有5種，1,4,3,21,3,2,41,3,4,21, 2,3,41,2,4,3 第四章 串 1.串：由零個或多個字符組成的有限序列；串中字符的數(shù)目n稱為串的長度，零個字符的串稱為 空串。包含子串的串相應(yīng)的稱為主串，通常稱字符在序列中的序號為該字符在串中的位置。 2．空串是，其長度等于度等于其包含的空格個數(shù)。組成串的數(shù)據(jù)元素只能是 單個字符。 4．一個字符串中稱為該串的子串。 5.若串S= ‘software’,其子串的數(shù)目是字符串長度為n的字串的個數(shù)計算公式 :[n+(n-1)+...+ 1+1]） 60．串是一種特殊的線性表，其特殊性體現(xiàn)在61．設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱為 串：1。KMP算法，求NEXT函數(shù)值等。時間：O(n+m)。其中，模式匹配為O（n）；預(yù)處理為 O（m）；求兩串的最長公共子串，時間為O（n）是不行的，至少要O（n2）。 第五章 數(shù)組（線性結(jié)構(gòu)，元素受限，操作不限）和廣義表 1.矩陣的壓縮存儲：是指為多個值相同的元只分配一個存儲空間，對零元不分配空間。 2.樹的存儲結(jié)構(gòu)： 一、雙親表示法：就是用一組連續(xù)空間存儲樹的結(jié)點，同時在每個結(jié)點中附設(shè) 一個指示器指示其雙親的結(jié)點在數(shù)組中位置。特點：找雙親容易，找孩子難； 二、孩子兄弟表示 法（又稱二叉樹和二叉鏈表表示法）鏈表結(jié)構(gòu)中的兩個鏈域分別指向該結(jié)點的的第一個孩子結(jié)點 和下一個兄弟結(jié)點。操作容易，破壞了樹的層次 第六章 樹和二叉樹 1.樹：樹是由n個類型相同的元素構(gòu)成的有限集。 2.二叉樹的性質(zhì)：在二叉樹的第i層上至多有2i-1個結(jié)點；深度為k的二叉樹最多有2k-1個結(jié)點； 葉子結(jié)點比度為2的結(jié)點個數(shù)多1。 3.遍歷二叉樹：先序遍歷（根左右）、中序遍歷（左根右）、后序遍歷（左右根）。前后序遍歷確定 跟，中序遍歷確定左右子樹，依次判斷，方法是：由前序先確定root，由中序可確定root的左、右子樹。然后由其左子樹的元素集合和右子樹的集合對應(yīng)前序遍歷序列中的元素集合，可繼 續(xù)確定root的左右孩子。將他們分別作為新的root，不斷遞歸，則所有元素都將被唯一確定.第七章圖 一、圖的定義和術(shù)語： 1、圖(Graph)——圖G是由兩個集合V(G)和E(G)組成的,記為G=(V,E) 其中：V(G)是頂點的非空有限集 E(G)是邊的有限集合，邊是頂點的無序?qū)蛴行驅(qū)?/p> 2、有向圖—有向圖G是由兩個集合V(G)和E(G)組成的其中：V(G)是頂點的非空有限集E(G)是有 向邊（也稱?。┑挠邢藜?，弧是頂點的有序?qū)?，記?v,w>，v,w是頂點，v為弧尾，w為弧頭 3、無向圖——無向圖G是由兩個集合V(G)和E(G)組成的其中：V(G)是頂點的非空有限集 E(G)是邊的有限集合，邊是頂點的無序?qū)?，記為（v,w）或（w,v），并且（v,w）=(w,v) 4、n個頂點的有向圖最大邊數(shù)是n(n-1)； n個頂點的無向圖最大邊數(shù)是n(n-1)/26、權(quán)——與圖的邊或弧相關(guān)的數(shù)叫~；簡單路徑——序列中頂點不重復(fù)出現(xiàn)的路徑叫~ 14、簡單回路——除了第一個頂點和最后一個頂點外，其余頂點不重復(fù)出現(xiàn)的回路叫~ 16、連通圖——圖中任意兩個頂點都是連通的叫~；連通分量——非連通圖的每一個連通部分叫~ 18、強連通圖——有向圖中，如果對每一對Vi,Vj?V, Vi1Vj,從Vi到Vj 和從Vj到 Vi都存在路徑 1、深度優(yōu)先搜索----從圖的某一頂點V0出發(fā)，訪問此頂點；然后依次從V0的未被訪問的鄰接點 出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點都被訪問到；若此時圖中尚有頂點未被 訪問，則另選圖中一個未被訪問的頂點作起點，重復(fù)上述過程，直至圖中所有頂點都被訪問為止 深度遍歷：V1-> V2->V4-> V8->V5->V3->V6->V72、廣度優(yōu)先遍歷(BFS)——方法：從圖的某一頂點V0出發(fā)，訪問此頂點后，依次訪問V0的各個 未曾訪問過的鄰接點；然后分別從這些鄰接點出發(fā)，廣度優(yōu)先遍歷圖，直至圖 中所有已被訪問的頂點的鄰接點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作 起點，重復(fù)上述過程，直至圖中所有頂點都被訪問為止 第九章 查找 1.靜態(tài)查找——拆半查找：確定待查記錄所在的范圍，然后逐步縮小范圍知道找到或找不到該記 錄為止。假設(shè)low和high分別為待查元素所在范圍的上下界，指針mid指示區(qū)域中間的位置，mid=[low+high]/2.此處low和high分別為位置而非數(shù)值。比較時與mid做比較，比mid大，low=mid+1，反之high=mid-1，mid重新計算。查找成功或失敗最多比較關(guān)鍵字個數(shù)不超過[log2n]+1 例：折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它 將依次與表中20，70，30，50 比較大小，查找結(jié)果是失敗。 2.靜態(tài)查找——順序查找：從表中最后一個記錄開始，逐個進行記錄的關(guān)鍵字和給定值的比較，相等則查找成功，反之失敗。平均查找長度：ASL=(n+1)/2 3.二叉排列樹：或是一棵空樹；或者是具有以下性質(zhì)的二叉樹：1.若它的左子樹不空，則左子樹 上所有結(jié)點的值均小于它的根結(jié)點的的值；2.若它的右子樹不空，則右子樹上所有借點得知均大 于它的根節(jié)點的值；3.它的左右子樹上也分別為二叉排列樹。 數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)（C++）——樹（總結(jié)） happycock（原作）CSDN 才剛開了個頭，就要說再見了——在樹這里，除了二叉樹，別的都還沒有講。為什么可以總結(jié)了呢？因為前面已經(jīng)涉及到了樹的兩個基本用途，而如果再講B＋、B－，就不能不提到搜索，如果是勝者樹就不能不提到排序。為此，把這部分放到后面。我前面所做的努力，只是讓你有個基本概念，什么時候記得用樹。樹的兩個基本用途，可以用物質(zhì)和精神來比喻。 一個用途是做為數(shù)據(jù)儲存，儲存具有樹結(jié)構(gòu)的數(shù)據(jù)——目錄、族譜等等。為了在實際上是線性的儲存載體上（內(nèi)存、磁盤）儲存非線性的樹結(jié)構(gòu)，必須有標(biāo)志指示出樹的結(jié)構(gòu)。因此，只要能區(qū)分根和子樹，樹可以采取各種方法來儲存——多叉鏈表、左子女－右兄弟二叉鏈表、廣義表、多維數(shù)組。由于操作的需求，儲存方法并不是隨意選取的。比如，在并查集的實現(xiàn)上，選取的是雙親鏈表。 一個用途是做為邏輯判斷，此時會常常聽到一個名詞——判定樹。最常用的結(jié)構(gòu)是二叉樹，一個孩子代表true，一個孩子代表false。關(guān)于多叉判定樹，有個例子是求8皇后的全部解——這個連高斯都算錯了（一共是92組解，高斯最開始說76組解），我們比不上高斯，但是我們會讓computer代勞。 就像哲學(xué)界到現(xiàn)在還糾纏于物質(zhì)和精神本源問題，實際上在樹這里也是如此。有些情況下，并不能區(qū)分是做為儲存來用還是做為判斷來用，比如搜索樹，既儲存了數(shù)據(jù)，還蘊涵著判斷。 和后面的圖相比，樹更基本，也更常用。你可以不知道最短路徑怎么求，卻每時每刻都在和樹打交道——看看你電腦里的文件夾吧。 最后，附帶一個求N皇后的全部解的程序。 #include #define N 8 int layout[N];//布局 int key = 0; int judge(int row, int col)//判斷能否在（row，col）放下 { int i;for(i = 0;i < row;i++){if(layout[i] == col)return 0;//同一列if(icol)return 0;//同一條主對角線} if(i + layout[i] == row + col)return 0;//同一條副對角線 return 1; } void lay(int row)//在row行上放Queen { int i;if(row == N)//放完N個Queen輸出布局 { }printf(“n%02d ”, ++key);for(i = 0;i < N;i++)printf(“%c%d ”, layout[i] + 'a', i + 1);} else {for(i = 0;i < N;i++)//在i列上放Queen} {} layout[row] = i;if(judge(row, i))lay(row + 1); int main() { } lay(0);return 0; c數(shù)據(jù)結(jié)構(gòu)實驗報告 數(shù)據(jù)結(jié)構(gòu)(C語言版)實驗報告;專業(yè)：計算機科學(xué)與技術(shù)、軟件工程;學(xué)號:____XX40703061_____;班級:_________軟件二班________;姓名:________朱海霞__________;指導(dǎo)教師:___劉遵仁_____________;青島大學(xué)信息工程學(xué)院;XX年10月;實驗1;實驗題目：順序存儲結(jié)構(gòu)線性表的插入和刪除;實驗?zāi)?/p> 數(shù)據(jù)結(jié)構(gòu)(C語言版)實驗報告 專業(yè)：計算機科學(xué)與技術(shù)、軟件工程 學(xué)號:____XX40703061___________________ 班級:_________軟件二班______________ 姓名:________朱海霞______________ 指導(dǎo)教師:___劉遵仁________________ 青島大學(xué)信息工程學(xué)院 XX年10月 實驗1 實驗題目：順序存儲結(jié)構(gòu)線性表的插入和刪除 實驗?zāi)康模?/p> 了解和掌握線性表的邏輯結(jié)構(gòu)和順序存儲結(jié)構(gòu)，掌握線性表的基本算法及相關(guān)的時間性能分析。 實驗要求： 建立一個數(shù)據(jù)域定義為整數(shù)類型的線性表，在表中允許有重復(fù)的數(shù)據(jù);根據(jù)輸入的數(shù)據(jù)，先找到相應(yīng)的存儲單元，后刪除之。 實驗主要步驟： 1、分析、理解給出的示例程序。 2、調(diào)試程序，并設(shè)計輸入一組數(shù)據(jù)(3，-5，6，8，2，-5，4，7，-9)，測試程序的如下功能：根據(jù)輸入的數(shù)據(jù)，找到相應(yīng)的存儲單元并刪除，顯示表中所有的數(shù)據(jù)。 程序代碼: #include #include #define OK 1 #define ERROR 0 #define OVERFLOW-2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct{ int* elem; int length; int listsize; }Sqlist; int InitList_Sq(Sqlist &L){ =(int*)malloc(LIST_INIT_SIZE*sizeof(int)); if(!)return-1; =0; =LIST_INIT_SIZE; return OK; } int ListInsert_Sq(Sqlist&L,int i,int e){ if(i+1)return ERROR; if(==){ int *newbase; newbase=(int*)realloc(,(+LISTINCREMENT)*sizeof(int)); if(!newbase)return-1; =newbase; +=LISTINCREMENT; } int *p,*q; q=&(); for(p=&();p>=q;--p) *(p+1)=*p; *q=e; ++; return OK; } int ListDelete_Sq(Sqlist &L,int i,int e){ int *p,*q; if(i)return ERROR; p=&(); e=*p; q=+; for(++p;p *(p-1)=*p; --; return OK; } int main(){ Sqlist L; InitList_Sq(L);//初始化 int i,a={3,-5,6,8,2,-5,4,7,-9}; for(i=1;i ListInsert_Sq(L,i,a); for(i=0;i printf(“ %d”,); printf(“ ”);//插入9個數(shù) ListInsert_Sq(L,3,24); for(i=0;i printf(“ %d”,); printf(“ ”);//插入一個數(shù) int e; ListDelete_Sq(L,2, e); for(i=0;i printf(“ %d”,);//刪除一個數(shù) printf(“ ”); return 0; } 實驗結(jié)果： 3，-5,6,8,2，-5,4,7，-9 3，-5,24,6,8,2，-5,4,7，-9 3,24,6,8,2，-5,4,7，-9 心得體會： 順序存儲結(jié)構(gòu)是一種隨機存取結(jié)構(gòu)，存取任何元素的時間是一個常數(shù)，速度快;結(jié)構(gòu)簡單，邏輯上相鄰的元素在物理上也相鄰;不使用指針，節(jié)省存儲空間;但是插入和刪除元素需要移動大量元素，消耗大量時間;需要一個連續(xù)的存儲空間;插入元素可能發(fā)生溢出;自由區(qū)中的存儲空間不能被其他數(shù)據(jù)共享 實驗2 實驗題目：單鏈表的插入和刪除 實驗?zāi)康模?/p> 了解和掌握線性表的邏輯結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，掌握單鏈表的基本算法及相關(guān)的時間性能分析。 實驗要求： 建立一個數(shù)據(jù)域定義為字符類型的單鏈表，在鏈表中不允許有重復(fù)的字符;根據(jù)輸入的字符，先找到相應(yīng)的結(jié)點，后刪除之。 實驗主要步驟： 3、分析、理解給出的示例程序。 4、調(diào)試程序，并設(shè)計輸入數(shù)據(jù)(如：A，C，E，F(xiàn)，H，J，Q，M)，測試程序的如下功能：不允許重復(fù)字符的插入;根據(jù)輸入的字符，找到相應(yīng)的結(jié)點并刪除。 5、修改程序： (1)增加插入結(jié)點的功能。 (2)建立鏈表的方法有“前插”、“后插”法。 程序代碼: #include #include #define NULL 0 #define OK 1 #define ERROR 0 typedef struct LNode{ int data; struct LNode *next; }LNode,*LinkList; int InitList_L(LinkList &L){ L=(LinkList)malloc(sizeof(LNode));L->next=NULL; return OK; } int ListInsert_L(LinkList &L,int i,int e){ LinkList p,s; int j; p=L;j=0; while(p&&j p=p->next;++j; } if(!p||j>i-1) return ERROR; s=(LinkList)malloc(sizeof(LNode));s->data=e; s->next=p->next; p->next=s; return OK; } int ListDelete_L(LinkList&L,int i,int &e){ LinkList p,q; int j; p=L;j=0; while(p->next&&j p=p->next;++j; } if(!(p->next)||j return ERROR; q=p->next;p->next=q->next;e=q->data;free(q); return OK; } int main(){ LinkList L,p; char a={'A','C','E','F','H','J','Q','U'};int i,j; InitList_L(L); for(i=1,j=0;i p=L->next; while(p!=NULL){ printf(“%c ”,p->data);p=p->next;}//插入八個字符 printf(“;實驗結(jié)果：;ACEFHJQU;ABCEFHJQU;ABEFHJQU;心得體會：;單鏈表是通過掃描指針P進行單鏈表的操作;頭指針唯;實驗3;實驗題目：棧操作設(shè)計和實現(xiàn);實驗?zāi)康模? 1、掌握棧的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，以便在實; 2、掌握棧的特點，即后進先出和先進先出的原則; 3、掌握棧的基本運算，如：入棧與出棧 } }//插入八個字符 printf(” “);i=2;int e;ListInsert_L(L,i,'B'); p=L->next;while(p!=NULL){ printf(”%c “,p->data);p=p->next;}//插入一個字符 printf(” “);i=3;ListDelete_L(L,i,e);p=L->next;while(p!=NULL){ printf(”%c “,p->data);p=p->next;} printf(” “);return 0; 實驗結(jié)果： A C E F H J Q U A B C E F H J Q U A B E F H J Q U 心得體會： 單鏈表是通過掃描指針P進行單鏈表的操作;頭指針唯一標(biāo)識點鏈表的存在;插入和刪除元素快捷，方便。 實驗3 實驗題目：棧操作設(shè)計和實現(xiàn) 實驗?zāi)康模?/p> 1、掌握棧的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，以便在實際中靈活應(yīng)用。 2、掌握棧的特點，即后進先出和先進先出的原則。 3、掌握棧的基本運算，如：入棧與出棧等運算在順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)上的實現(xiàn)。 實驗要求： 回文判斷：對于一個從鍵盤輸入的字符串，判斷其是否為回文。回文即正反序相同。如 “abba”是回文，而“abab”不是回文。 實驗主要步驟 (1)數(shù)據(jù)從鍵盤讀入; (2)輸出要判斷的字符串; (3)利用棧的基本操作對給定的字符串判斷其是否是回文，若是則輸出“Yes”，否則輸出“No”。 程序代碼: #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW-2 #define N 100 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{ int *base;// 在棧構(gòu)造之前和銷毀之后，base的值為NULL int *top;// 棧頂指針 int stacksize;// 當(dāng)前已分配的存儲空間，以元素為單位 } SqStack; int InitStack(SqStack &S) { // 構(gòu)造一個空棧S if(!(=(int *)malloc(STACK_INIT_SIZE*sizeof(int)))) exit(OVERFLOW);// 存儲分配失敗 =; =STACK_INIT_SIZE; return OK; } int StackEmpty(SqStack S) { // 若棧S為空棧，則返回TRUE，否則返回FALSE if(==) return TRUE; else return FALSE; } int Push(SqStack &S, int e) { // 插入元素e為新的棧頂元素 if(>=)// 棧滿，追加存儲空間 { =(int *)realloc(,(+STACKINCREMENT)*sizeof(int));if(!) exit(OVERFLOW);// 存儲分配失敗 =+; +=STACKINCREMENT; } *()++=e; return OK; } int Pop(SqStack &S,int &e) { // 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK;否則返回ERROR if(==) return ERROR; e=*--; return OK; } int main(){ SqStack s; int i,e,j,k=1; char ch = {0},*p,b = {0}; if(InitStack(s))// 初始化棧成功 { printf(”請輸入表達(dá)式: “); gets(ch); p=ch; while(*p)// 沒到串尾 Push(s,*p++); for(i=0;i if(!StackEmpty(s)){// 棧不空 Pop(s,e);// 彈出棧頂元素 b=e; } } for(i=0;i if(ch!=b) k=0; } if(k==0) printf(”NO!“); else printf(”輸出:“) printf(”YES!“); } return 0; } 實驗結(jié)果： 請輸入表達(dá)式： abcba 輸出：YES! 心得體會：棧是僅能在表尾驚醒插入和刪除操作的線性表，具有先進后出的性質(zhì)，這個固有性質(zhì)使棧成為程序設(shè)計中的有用工具。 實驗4 實驗題目：二叉樹操作設(shè)計和實現(xiàn) 實驗?zāi)康模?/p> 掌握二叉樹的定義、性質(zhì)及存儲方式，各種遍歷算法。 實驗要求： 采用二叉樹鏈表作為存儲結(jié)構(gòu)，完成二叉樹的建立，先序、中序和后序以及按層次遍歷的操作，求所有葉子及結(jié)點總數(shù)的操作。 實驗主要步驟： 1、分析、理解程序。 2、調(diào)試程序，設(shè)計一棵二叉樹，輸入完全二叉樹的先序序列，用#代表虛結(jié)點(空指針)，如ABD###CE##F##，建立二叉樹，求出先序、中序和后序以及按層次遍歷序列，求所有葉子及結(jié)點總數(shù)。 程序代碼: 實驗結(jié)果： 心得體會： 實驗5 實驗題目：圖的遍歷操作 實驗?zāi)康模?/p> 掌握有向圖和無向圖的概念;掌握鄰接矩陣和鄰接鏈表建立圖的存儲結(jié)構(gòu);掌握DFS及BFS對圖的遍歷操作;了解圖結(jié)構(gòu)在人工智能、工程等領(lǐng)域的廣泛應(yīng)用。 實驗要求： 采用鄰接矩陣和鄰接鏈表作為圖的存儲結(jié)構(gòu)，完成有向圖和無向圖的DFS和BFS操作。 實驗主要步驟： 設(shè)計一個有向圖和一個無向圖，任選一種存儲結(jié)構(gòu)，完成有向圖和無向圖的DFS(深度優(yōu)先遍歷)和BFS(廣度優(yōu)先遍歷)的操作。 1.鄰接矩陣作為存儲結(jié)構(gòu) #include”“ #include”“ #define MaxVertexNum 100 //定義最大頂點數(shù) typedef struct{ char vexs;//頂點表 int edges;//鄰接矩陣，可看作邊表 int n,e;//圖中的頂點數(shù)n和邊數(shù)e }MGraph;//用鄰接矩陣表示的圖的類型 //=========建立鄰接矩陣======= void CreatMGraph(MGraph *G) { int i,j,k; char a; printf(”Input VertexNum(n)and EdgesNum(e): “); scanf(”%d,%d“,&G->n,&G->e);//輸入頂點數(shù)和邊數(shù) scanf(”%c“,&a); printf(”Input Vertex string:“); for(i=0;in;i++) { scanf(”%c“,&a); G->vexs=a;//讀入頂點信息，建立頂點表 } for(i=0;in;i++) for(j=0;jn;j++) G->edges=0;//初始化鄰接矩陣 printf(”Input edges,Creat Adjacency Matrix “); for(k=0;ke;k++){ //讀入e條邊，建立鄰接矩陣 scanf(”%d%d“,&i,&j);//輸入邊(Vi，Vj)的頂點序號 G->edges=1;;G->edges=1;//若為;//=========定義標(biāo)志向 量，為 全 局 變 量=;typedefenum{FALSE,TRUE}B;Booleanvisited=1; G->edges=1;//若為無向圖，矩陣為對稱矩陣;若建立有向圖，去掉該條語句 } } //=========定義標(biāo)志向量，為全局變量======= typedef enum{FALSE,TRUE} Boolean; Boolean visited; //========DFS：深度優(yōu)先遍歷的遞歸算法====== void DFSM(MGraph *G,int i) { //以Vi為出發(fā)點對鄰接矩陣表示的圖G進行DFS搜索，鄰接矩陣是0，1矩陣 給出你的編碼 //===========BFS：廣度優(yōu)先遍歷======= void BFS(MGraph *G,int k) { //以Vk為源點對用鄰接矩陣表示的圖G進行廣度優(yōu)先搜索 給出你的編碼 //==========主程序main ===== void main() { int i; MGraph *G; G=(MGraph *)malloc(sizeof(MGraph));//為圖G請內(nèi)存空間 CreatMGraph(G);//建立鄰接矩陣 printf(”Print Graph DFS: “); DFS(G);//深度優(yōu)先遍歷 printf(” “); printf(”Print Graph BFS: “); BFS(G,3);//以序號為3的頂點開始廣度優(yōu)先遍歷 printf(” “); } 2.鄰接鏈表作為存儲結(jié)構(gòu) #include”“ #include”“ #define MaxVertexNum 50 //定義最大頂點數(shù) typedef struct node{ //邊表結(jié)點 int adjvex;//鄰接點域 struct node *next;//鏈域 申 }EdgeNode; typedef struct vnode{ //頂點表結(jié)點 char vertex;//頂點域 EdgeNode *firstedge;//邊表頭指針 }VertexNode; typedef VertexNode AdjList;//AdjList是鄰接表類型 typedef struct { AdjList adjlist;//鄰接表 int n,e;//圖中當(dāng)前頂點數(shù)和邊數(shù) } ALGraph;//圖類型 //=========建立圖的鄰接表======= void CreatALGraph(ALGraph *G) { int i,j,k; char a; EdgeNode *s;//定義邊表結(jié)點 printf(”Input VertexNum(n)and EdgesNum(e): “); scanf(”%d,%d“,&G->n,&G->e);//讀入頂點數(shù)和邊數(shù) scanf(”%c“,&a); printf(”Input Vertex string:“); for(i=0;in;i++)//建立邊表 { scanf(”%c“,&a); G->adjlist.vertex=a;//讀入頂點信息 G->adjlist.firstedge=NULL;//邊表置為空表 } printf(”Input edges,Creat Adjacency List “); for(k=0;ke;k++){ //建立邊表 scanf(”%d%d“,&i,&j);//讀入邊(Vi，Vj)的頂點對序號 s=(EdgeNode *)malloc(sizeof(EdgeNode));//生成邊表結(jié)點 s->adjvex=j;//鄰接點序號為j s->next=G->adjlist.firstedge; G->adjlist.firstedge=s;//將新結(jié)點*S插入頂點Vi的邊表頭部 s=(EdgeNode *)malloc(sizeof(EdgeNode)); s->adjvex=i;//鄰接點序號為i s->next=G->adjlist.firstedge; G->adjlist.firstedge=s;//將新結(jié)點*S插入頂點Vj的邊表頭部 } } //=========定義標(biāo)志向量，為全局變量======= typedef enum{FALSE,TRUE} Boolean; Boolean visited; //========DFS：深度優(yōu)先遍歷的遞歸算法====== void DFSM(ALGraph *G,int i) { //以Vi為出發(fā)點對鄰接鏈表表示的圖G進行DFS搜索 給出你的編碼 //==========BFS：廣度優(yōu)先遍歷========= void BFS(ALGraph *G,int k) { //以Vk為源點對用鄰接鏈表表示的圖G進行廣度優(yōu)先搜索 給出你的編碼 //==========主函數(shù)=========== void main() { int i; ALGraph *G; G=(ALGraph *)malloc(sizeof(ALGraph)); CreatALGraph(G); printf(”Print Graph DFS: “); DFS(G); printf(” “); printf(”Print Graph BFS: “); BFS(G,3); printf(” "); } 實驗結(jié)果： 1.鄰接矩陣作為存儲結(jié)構(gòu) 2.鄰接鏈表作為存儲結(jié)構(gòu) 心得體會： 實驗6 實驗題目：二分查找算法的實現(xiàn) 實驗?zāi)康模?/p> 掌握二分查找法的工作原理及應(yīng)用過程，利用其工作原理完成實驗題目中的內(nèi)容。 實驗要求： 編寫程序構(gòu)造一個有序表L，從鍵盤接收一個關(guān)鍵字key，用二分查找法在L中查找key，若找到則提示查找成功并輸出key所在的位置，否則提示沒有找到信息。 實驗主要步驟： 1.建立的初始查找表可以是無序的，如測試的數(shù)據(jù)為{3，7，11，15，17，21，35，42，50｝或者{11，21，7，3，15，50，42，35，17｝。 2.給出算法的遞歸和非遞歸代碼; 3.如何利用二分查找算法在一個有序表中插入一個元素x，并保持表的有序性? 程序代碼 實驗結(jié)果： 心得體會： 實驗7 實驗題目：排序 實驗?zāi)康模?/p> 掌握各種排序方法的基本思想、排序過程、算法實現(xiàn)，能進行時間和空間性能的分析，根據(jù)實際問題的特點和要求選擇合適的排序方法。 實驗要求： 實現(xiàn)直接排序、冒泡、直接選擇、快速、堆、歸并排序算法。比較各種算法的運行速度。 實驗主要步驟： 程序代碼 實驗結(jié)果： 心得體會： 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計題目(程序?qū)崿F(xiàn)采用C語言) 題目1：猴子選王（學(xué)時：3） 一堆猴子都有編號，編號是1，2，3...m，這群猴子（m個）按照1-m的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第n個，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。 要求：m及n要求從鍵盤輸入，存儲方式采用向量及鏈表兩種方式實現(xiàn)該問題求解。 //鏈表 #include typedef struct _RingNode { int pos; struct _RingNode *next;}RingNode, *RingNodePtr; // 創(chuàng)建約瑟夫環(huán)，pHead:鏈表頭指針，count:鏈表元素個數(shù) void CreateRing(RingNodePtr pHead, int count){ RingNodePtr pCurr = NULL, pPrev = NULL; int i = 1; pPrev = pHead; while(--count > 0) { pCurr =(RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead;// 構(gòu)成環(huán)狀鏈表 } void KickFromRing(RingNodePtr pHead, int n){ RingNodePtr pCurr, pPrev; int i = 1; // 計數(shù) pCurr = pPrev = pHead; while(pCurr!= NULL) { if(i == n) { // 踢出環(huán) printf(“n%d”, pCurr->pos); // 顯示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; pCurr = pCurr->next; if(pPrev == pCurr) { // 最后一個 printf(“nKing is %d”, pCurr->pos); // 顯示出圈循序 free(pCurr); break; } i++; } } int main(){ int n = 0, m = 0; RingNodePtr pHead = NULL; printf(“M(person count)= ”); scanf(“%d”, &m); printf(“N(out number)= ”); scanf(“%d”, &n); if(m <= 0 || n <= 0) { printf(“Input Errorn”); return 0; } // 建立鏈表 pHead =(RingNodePtr)malloc(sizeof(RingNode)); pHead->pos = 1; pHead->next = NULL; CreateRing(pHead, m);// 開始出圈 printf(“nKick Order: ”); KickFromRing(pHead, n); printf(“n”); system(“pause”); return 0;} //數(shù)組做： #include void SelectKing(int MonkeyNum, int CallNum); void main(){ int MonkeyNum; int CallNum; /* 輸入猴子的個數(shù) */ printf(“Monkey Num = ”); scanf(“%d”, &MonkeyNum); /* 輸入M的值 */ printf(“Call Num = ”); scanf(“%d”, &CallNum); SelectKing(MonkeyNum, CallNum); } void SelectKing(int MonkeyNum, int CallNum){ int *Monkeys;// 申請一個數(shù)組，表示所有的猴子； int counter = 0;//計數(shù)，當(dāng)計數(shù)為猴子個數(shù)時表示選到最后一個猴子了； int position = 0;// 位置，數(shù)組的下標(biāo)，輪流遍歷數(shù)組進行報數(shù)； int token = 0;// 令牌，將報數(shù)時數(shù)到M的猴子砍掉； // 申請猴子個數(shù)大小的數(shù)組，把桌子擺上。 Monkeys =(int *)malloc(sizeof(int)* MonkeyNum); if(NULL == Monkeys) { printf(“So many monkeys, system error.n”); return; } // 將數(shù)組的所有內(nèi)容初始化為0，被砍掉的猴子設(shè)置為1 memset(Monkeys, 0, sizeof(int)*MonkeyNum); // 循環(huán)，直到選中大王 while(counter!= MonkeyNum) { // 如果這個位置的猴子之前沒有砍掉，那么報數(shù)有效 if(Monkeys[position] == 0) { token++;// 成功報數(shù)一個，令牌+1，繼續(xù)報數(shù)直到等于M // 如果報數(shù)到M，那么將這個猴子砍去 if(token == CallNum) { Monkeys[position] = 1;// 設(shè)置為1，表示砍去 counter++;// 計數(shù)增加 token = 0;// 設(shè)置為0，下次重新報數(shù) // 如果是最后一個猴子，把它的位置打印，這個就是大王了 if(counter == MonkeyNum) { printf(“The king is the %d monkey.n”, position+1); } } } // 下一個猴子報數(shù) position =(position + 1)%MonkeyNum; } // 釋放內(nèi)存，開頭為所有猴子創(chuàng)建的桌子 free(Monkeys); return;} 題目2 ：字符逆轉(zhuǎn)（學(xué)時：3） 從鍵盤讀入一個字符串，把它存入一個鏈表（每個結(jié)點存儲1個字符），并按相反的次序?qū)⒆址敵龅斤@示屏。 #include struct node { struct node *prev; char c; struct node *next;};struct node *input(struct node *top);int main(void){ struct node T,*top=&T,*bottom=&T,*p=NULL;T.prev=NULL;T.next=NULL;T.c='
第二篇：數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)(C)樹(總結(jié))
第三篇：c數(shù)據(jù)結(jié)構(gòu)實驗報告
第四篇：數(shù)據(jù)結(jié)構(gòu)經(jīng)典題目及c語言代碼總結(jié)