第一篇：數據結構C章節總結
第一章 緒論
數據結構：數據結構就是數據的組織形式，也可看成是包含數據結構的數據表，說明數據之間存在著一定的相互關系或約束。數據結構被形式地定義為(D,R),其中D是數據元素的有限集合,R是D上的關系有限集合.數據類型：一個值的集合和定義在這個值集上的一組操作的總稱；數據運算：對數據施加的一種操作；數據結構和數據類型兩個概念之間區別：簡單地說，數據結構定義了一組按某些關系結合在一起的數組元素。數據類型不僅定義了一組帶結構的數據元素，而且還在其上定義了一組操作。
邏輯結構：我們把只表現元素之間邏輯關系，而不涉及它們在計算機中的表示，只是理論的、反映在紙面上的東西，這種抽象的數據結構稱為邏輯結構。
物理結構：抽象的數據結構在計算機內的表示，也就是映射在存儲空間上的、具體的數據結構在計算機內表示，也就是映射在存儲空間上的、具體的數據結構。
數據：是對客觀事物的符號表示，在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱；數據元素：數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。一個數據元素可以由若干個數據項組成。數據項是數據的最小單位。
數據對象：性質相同的數據元素的集合，是數據的一個子集。
數據結構：是相互之間一種或多種特定關系的數據元素的集合。根據數據元素之間關系的不同特性。數據結構包括邏輯結構（線性結構，如線性表，棧，隊，串，數組 和非線性結構如 樹結構、圖結構）、物理（存儲）結構（集合、線性結構、樹形結構和圖狀結構或網狀結構）和數據運算如插入、刪除、修改、排序、查找。數據結構中，與所使用的計算機無關的數據叫邏輯結構，數據結構在計算機內存中的表示是指數據的存儲結構
四大類存儲結構：順序存儲、鏈式存儲、索引存儲和散列存儲。順序存儲包括數據存儲（把邏輯上相鄰的元素存儲在地址連續的存儲單位）和數據關系存儲（通過連續的物理地址體現關系）；鏈式存儲包括數據存儲（把邏輯上相鄰的元素存放在物理地址隨意的存儲單元）和數據關系存儲（不僅存放數據本身還存放數據元素的物理地址）
抽象數據類型ADT：一個數學模型以及定義在該模型上的一組操作，包括_數據和操作_兩個部分 算法的特性：有窮性（執行有窮步結束）、確定性（確切含義，不會產生二義性）、可行性、輸入（零個或多個輸入）和輸出（一個或多個輸出）
算法設計的要求：正確性、可讀寫、健壯性、效率與低存儲量需求。
2、數據的邏輯結構是指圖形結構_三種類型，樹形結構和圖形結構合稱為非線性結構_。數據的邏輯結構被分為集合結構、線性結構、樹形結構、圖形結構４種。
17_稱為存儲結構.1821、算法的執行時間是
371、某算法的時間復雜度為O(n2),表明該算法的_____.2.算法分析的目的是問題規模之間的關系;算法分析的兩個主要方面是空間復雜度和時間復雜度
5．在決定選取何種存儲結構時，一般不考慮
A.各結點的值如何B.結點個數的多少C.對數據有哪些運算D.編程語言實現這種結構是否方便。
10．程序段i ＝ 0；while（i<=n）｛i = i * 3
12數據項的個數要相同，而且對應的數據項的類型要一致 1.數據結構是一門研究非數值計算的程序設計問題中計算機的系和運算等的學科。數據結構式相互之間存在一種或多種特定關系的數據元素的集合。10.數據的運算最常用的有5-1-
第二章 線性表
1.線性表:一個線性表是n個類型相同的數據元素的有限序列。線性表的順序表示：用一組地址連
續的存儲單元依次存儲線性表的數據元素。順序存儲結構的特點：優，可隨機存取表中任一元素，方便快捷；缺，再插入或刪除時，需移動大量元素，數組的靜態空間分配。
2.線性結構與非線性結構的不同點：線性結構反映結點間的邏輯關系是 一對一的，非線性結構反
映結點間的邏輯關系是多對多的。
3.從一個具有n個節點的單鏈表中查找其值等于x結點時，在查找成功的情況下，需平均比較個結點,4.在一個單鏈表中，已知*q結點是*p結點的前驅結點，若在*q和*p之間插入*s結點，則執行 5.對順序存儲的線性表，設其長度為n，在任何位置上插入或刪除操作都是等概率的，刪除一個
元素時大約要移動表中的(n-1)/2兩種情況下求平均個元素。
6.設單鏈表中指針p指著結點m，指針f指著將要插入的新結點x，當x插在鏈表中最后一個結點
m之后時，只要先修改后修改p->link=f即可。
7.在一個長度為n的順序存儲的線性表中，刪除第i個元素(1<=i<=n)時，需要從前向后依次前移i個元素前插入元素需移動
存儲結構需要分配較大空間，插入和刪除不需要移動元素的線性表
9、在雙向鏈表存儲結構中，刪除p所指的結點時需修改指針p所指的結點的前趨結點（若存在）時需修改指針
1.在循環雙鏈表的p所指結點之前插入s所指結點的操作是12.若某表最常用的操作是在最后一個結點之后插入一個結點或刪除最后一個結點，則采用_結點的雙循環鏈表__存儲方式最節省運算時間；某線性表最常用的操作是在最后一個結點之后插
入一個結點或刪除第一個結點，故采用_僅有尾指針的單循環鏈表存儲方式最節省運算時間；對
于只在表的首、尾兩端進行插入操作的線性表,宜采用的存儲結構為用尾指針表示的循環單鏈表
14.15.16.17、不帶頭結點的單鏈表head為空的判定條件是 帶頭結點的~是
19、帶頭結點的雙循環表L為空表的條件是。
20、非空的循環單鏈表head的尾結點(由p所指向)滿足21.在一個長度為n(n>1)操作與鏈表的長度有關；與單鏈表相比，雙鏈表的優點之一是順序訪問相鄰結點更靈活
23線性表的鏈接存儲中，元素之間的邏輯關系是通過鏈接指針決定的。
24、從順序表中刪除第i個元素時，首先把第i個元素賦給_針開始向后的所有元素均前移一個位置，最后使線性表的長度減1。
25,26、循環單鏈表L為空的條件是
27、在以ＨＬ為表頭指針的帶表頭附加結點的單鏈表和循環單鏈表中，鏈表為空的條件分別為。
28、在線性表的單鏈接存儲中，若一個元素所在結點的地址為p，則其后繼結點的地址為，若p為一個數組a中的下標，則其后繼結點的下標的a[p].next。
29、在由數組a中元素結點構成的單鏈表中，在下標為i的結點的后面插入一個下標為j的結點
時，需要進行的操作為a[j].next=a[i].next和a[i].next=j語句。
第三章 棧和隊列
1.棧：是限定僅在表尾進行插入或刪除操作的線性表。棧又稱為先進后出LIFO的線性表。
2.判定一個棧ST（最多元素為m0）為空的條件是
2.棧的兩種存儲方法：一是順序棧，即棧的順序存儲結構是利用一組地址連續的存儲單元依次存
放自棧底到棧頂的元素；二是棧的鏈式表示。
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.循環隊列:空隊滿隊都是rea=r=front為區分,規定循環隊列中剩一個元素即為滿隊,front=rear+1
7.8.9.向一個棧項指針為hs的鏈棧中插入一個*s結點時，則執行。
10.在一個鏈隊列中，假定front和rear分別為隊首指針和隊尾指針，則進行插入*s結點的操作時
應執行rear->next=s;rear=s;
11.若己知一個棧的進棧序列是1,2,…,n,其輸出序列為p1,p2,p3,…,pn,若p1=n,則pi(1 23、判定一個環形隊列qu(最多元素為MaxSize)為空的條件是是(qu->rear+1)%MaxSize==qu->front 列的元素個數是(rear-front+MaxSize)%MaxSize。 24.從一個不帶頭結點的棧頂指針為1st的鏈棧中刪除一個結點時,用x保存被刪結點的值,則執行5.棧頂指針 7.在鏈表qu中,判定只有一個結點的條件是設有一個順序棧S,元素s1,s2,s3,s4,s5,s6依次進棧,如果6個元素的出棧順序為s2,s3,s4,s6,s5,s1,則順序棧的容量至少應為3。 9.設計一個判別表達式中左、右括號是否配對出現的算法，采用數據結構最佳 例：設有編號為1，2，3，4的四輛列車，順序進入一個棧式結構的車站，具體寫出這四輛 列車開出車站的所有可能的順序。 答：至少有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.串：由零個或多個字符組成的有限序列；串中字符的數目n稱為串的長度，零個字符的串稱為 空串。包含子串的串相應的稱為主串，通常稱字符在序列中的序號為該字符在串中的位置。 2．空串是，其長度等于度等于其包含的空格個數。組成串的數據元素只能是 單個字符。 4．一個字符串中稱為該串的子串。 5.若串S= ‘software’,其子串的數目是字符串長度為n的字串的個數計算公式 :[n+(n-1)+...+ 1+1]） 60．串是一種特殊的線性表，其特殊性體現在61．設有兩個串p和q，求q在p中首次出現的位置的運算稱為 串：1。KMP算法，求NEXT函數值等。時間：O(n+m)。其中，模式匹配為O（n）；預處理為 O（m）；求兩串的最長公共子串，時間為O（n）是不行的，至少要O（n2）。 第五章 數組（線性結構，元素受限，操作不限）和廣義表 1.矩陣的壓縮存儲：是指為多個值相同的元只分配一個存儲空間，對零元不分配空間。 2.樹的存儲結構： 一、雙親表示法：就是用一組連續空間存儲樹的結點，同時在每個結點中附設 一個指示器指示其雙親的結點在數組中位置。特點：找雙親容易，找孩子難； 二、孩子兄弟表示 法（又稱二叉樹和二叉鏈表表示法）鏈表結構中的兩個鏈域分別指向該結點的的第一個孩子結點 和下一個兄弟結點。操作容易，破壞了樹的層次 第六章 樹和二叉樹 1.樹：樹是由n個類型相同的元素構成的有限集。 2.二叉樹的性質：在二叉樹的第i層上至多有2i-1個結點；深度為k的二叉樹最多有2k-1個結點； 葉子結點比度為2的結點個數多1。 3.遍歷二叉樹：先序遍歷（根左右）、中序遍歷（左根右）、后序遍歷（左右根）。前后序遍歷確定 跟，中序遍歷確定左右子樹，依次判斷，方法是：由前序先確定root，由中序可確定root的左、右子樹。然后由其左子樹的元素集合和右子樹的集合對應前序遍歷序列中的元素集合，可繼 續確定root的左右孩子。將他們分別作為新的root，不斷遞歸，則所有元素都將被唯一確定.第七章圖 一、圖的定義和術語： 1、圖(Graph)——圖G是由兩個集合V(G)和E(G)組成的,記為G=(V,E) 其中：V(G)是頂點的非空有限集 E(G)是邊的有限集合，邊是頂點的無序對或有序對 2、有向圖—有向圖G是由兩個集合V(G)和E(G)組成的其中：V(G)是頂點的非空有限集E(G)是有 向邊（也稱弧）的有限集合，弧是頂點的有序對，記為 3、無向圖——無向圖G是由兩個集合V(G)和E(G)組成的其中：V(G)是頂點的非空有限集 E(G)是邊的有限集合，邊是頂點的無序對，記為（v,w）或（w,v），并且（v,w）=(w,v) 4、n個頂點的有向圖最大邊數是n(n-1)； n個頂點的無向圖最大邊數是n(n-1)/26、權——與圖的邊或弧相關的數叫~；簡單路徑——序列中頂點不重復出現的路徑叫~ 14、簡單回路——除了第一個頂點和最后一個頂點外，其余頂點不重復出現的回路叫~ 16、連通圖——圖中任意兩個頂點都是連通的叫~；連通分量——非連通圖的每一個連通部分叫~ 18、強連通圖——有向圖中，如果對每一對Vi,Vj?V, Vi1Vj,從Vi到Vj 和從Vj到 Vi都存在路徑 1、深度優先搜索----從圖的某一頂點V0出發，訪問此頂點；然后依次從V0的未被訪問的鄰接點 出發，深度優先遍歷圖，直至圖中所有和V0相通的頂點都被訪問到；若此時圖中尚有頂點未被 訪問，則另選圖中一個未被訪問的頂點作起點，重復上述過程，直至圖中所有頂點都被訪問為止 深度遍歷：V1-> V2->V4-> V8->V5->V3->V6->V72、廣度優先遍歷(BFS)——方法：從圖的某一頂點V0出發，訪問此頂點后，依次訪問V0的各個 未曾訪問過的鄰接點；然后分別從這些鄰接點出發，廣度優先遍歷圖，直至圖 中所有已被訪問的頂點的鄰接點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作 起點，重復上述過程，直至圖中所有頂點都被訪問為止 第九章 查找 1.靜態查找——拆半查找：確定待查記錄所在的范圍，然后逐步縮小范圍知道找到或找不到該記 錄為止。假設low和high分別為待查元素所在范圍的上下界，指針mid指示區域中間的位置，mid=[low+high]/2.此處low和high分別為位置而非數值。比較時與mid做比較，比mid大，low=mid+1，反之high=mid-1，mid重新計算。查找成功或失敗最多比較關鍵字個數不超過[log2n]+1 例：折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它 將依次與表中20，70，30，50 比較大小，查找結果是失敗。 2.靜態查找——順序查找：從表中最后一個記錄開始，逐個進行記錄的關鍵字和給定值的比較，相等則查找成功，反之失敗。平均查找長度：ASL=(n+1)/2 3.二叉排列樹：或是一棵空樹；或者是具有以下性質的二叉樹：1.若它的左子樹不空，則左子樹 上所有結點的值均小于它的根結點的的值；2.若它的右子樹不空，則右子樹上所有借點得知均大 于它的根節點的值；3.它的左右子樹上也分別為二叉排列樹。 數據結構學習（C++）——樹（總結） happycock（原作）CSDN 才剛開了個頭，就要說再見了——在樹這里，除了二叉樹，別的都還沒有講。為什么可以總結了呢？因為前面已經涉及到了樹的兩個基本用途，而如果再講B＋、B－，就不能不提到搜索，如果是勝者樹就不能不提到排序。為此，把這部分放到后面。我前面所做的努力，只是讓你有個基本概念，什么時候記得用樹。樹的兩個基本用途，可以用物質和精神來比喻。 一個用途是做為數據儲存，儲存具有樹結構的數據——目錄、族譜等等。為了在實際上是線性的儲存載體上（內存、磁盤）儲存非線性的樹結構，必須有標志指示出樹的結構。因此，只要能區分根和子樹，樹可以采取各種方法來儲存——多叉鏈表、左子女－右兄弟二叉鏈表、廣義表、多維數組。由于操作的需求，儲存方法并不是隨意選取的。比如，在并查集的實現上，選取的是雙親鏈表。 一個用途是做為邏輯判斷，此時會常常聽到一個名詞——判定樹。最常用的結構是二叉樹，一個孩子代表true，一個孩子代表false。關于多叉判定樹，有個例子是求8皇后的全部解——這個連高斯都算錯了（一共是92組解，高斯最開始說76組解），我們比不上高斯，但是我們會讓computer代勞。 就像哲學界到現在還糾纏于物質和精神本源問題，實際上在樹這里也是如此。有些情況下，并不能區分是做為儲存來用還是做為判斷來用，比如搜索樹，既儲存了數據，還蘊涵著判斷。 和后面的圖相比，樹更基本，也更常用。你可以不知道最短路徑怎么求，卻每時每刻都在和樹打交道——看看你電腦里的文件夾吧。 最后，附帶一個求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數據結構實驗報告 數據結構(C語言版)實驗報告;專業：計算機科學與技術、軟件工程;學號:____XX40703061_____;班級:_________軟件二班________;姓名:________朱海霞__________;指導教師:___劉遵仁_____________;青島大學信息工程學院;XX年10月;實驗1;實驗題目：順序存儲結構線性表的插入和刪除;實驗目 數據結構(C語言版)實驗報告 專業：計算機科學與技術、軟件工程 學號:____XX40703061___________________ 班級:_________軟件二班______________ 姓名:________朱海霞______________ 指導教師:___劉遵仁________________ 青島大學信息工程學院 XX年10月 實驗1 實驗題目：順序存儲結構線性表的插入和刪除 實驗目的： 了解和掌握線性表的邏輯結構和順序存儲結構，掌握線性表的基本算法及相關的時間性能分析。 實驗要求： 建立一個數據域定義為整數類型的線性表，在表中允許有重復的數據;根據輸入的數據，先找到相應的存儲單元，后刪除之。 實驗主要步驟： 1、分析、理解給出的示例程序。 2、調試程序，并設計輸入一組數據(3，-5，6，8，2，-5，4，7，-9)，測試程序的如下功能：根據輸入的數據，找到相應的存儲單元并刪除，顯示表中所有的數據。 程序代碼: #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個數 ListInsert_Sq(L,3,24); for(i=0;i printf(“ %d”,); printf(“ ”);//插入一個數 int e; ListDelete_Sq(L,2, e); for(i=0;i printf(“ %d”,);//刪除一個數 printf(“ ”); return 0; } 實驗結果： 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 心得體會： 順序存儲結構是一種隨機存取結構，存取任何元素的時間是一個常數，速度快;結構簡單，邏輯上相鄰的元素在物理上也相鄰;不使用指針，節省存儲空間;但是插入和刪除元素需要移動大量元素，消耗大量時間;需要一個連續的存儲空間;插入元素可能發生溢出;自由區中的存儲空間不能被其他數據共享 實驗2 實驗題目：單鏈表的插入和刪除 實驗目的： 了解和掌握線性表的邏輯結構和鏈式存儲結構，掌握單鏈表的基本算法及相關的時間性能分析。 實驗要求： 建立一個數據域定義為字符類型的單鏈表，在鏈表中不允許有重復的字符;根據輸入的字符，先找到相應的結點，后刪除之。 實驗主要步驟： 3、分析、理解給出的示例程序。 4、調試程序，并設計輸入數據(如：A，C，E，F，H，J，Q，M)，測試程序的如下功能：不允許重復字符的插入;根據輸入的字符，找到相應的結點并刪除。 5、修改程序： (1)增加插入結點的功能。 (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(“;實驗結果：;ACEFHJQU;ABCEFHJQU;ABEFHJQU;心得體會：;單鏈表是通過掃描指針P進行單鏈表的操作;頭指針唯;實驗3;實驗題目：棧操作設計和實現;實驗目的：; 1、掌握棧的順序存儲結構和鏈式存儲結構，以便在實; 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; 實驗結果： 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進行單鏈表的操作;頭指針唯一標識點鏈表的存在;插入和刪除元素快捷，方便。 實驗3 實驗題目：棧操作設計和實現 實驗目的： 1、掌握棧的順序存儲結構和鏈式存儲結構，以便在實際中靈活應用。 2、掌握棧的特點，即后進先出和先進先出的原則。 3、掌握棧的基本運算，如：入棧與出棧等運算在順序存儲結構和鏈式存儲結構上的實現。 實驗要求： 回文判斷：對于一個從鍵盤輸入的字符串，判斷其是否為回文。回文即正反序相同。如 “abba”是回文，而“abab”不是回文。 實驗主要步驟 (1)數據從鍵盤讀入; (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;// 在棧構造之前和銷毀之后，base的值為NULL int *top;// 棧頂指針 int stacksize;// 當前已分配的存儲空間，以元素為單位 } SqStack; int InitStack(SqStack &S) { // 構造一個空棧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(”請輸入表達式: “); 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; } 實驗結果： 請輸入表達式： abcba 輸出：YES! 心得體會：棧是僅能在表尾驚醒插入和刪除操作的線性表，具有先進后出的性質，這個固有性質使棧成為程序設計中的有用工具。 實驗4 實驗題目：二叉樹操作設計和實現 實驗目的： 掌握二叉樹的定義、性質及存儲方式，各種遍歷算法。 實驗要求： 采用二叉樹鏈表作為存儲結構，完成二叉樹的建立，先序、中序和后序以及按層次遍歷的操作，求所有葉子及結點總數的操作。 實驗主要步驟： 1、分析、理解程序。 2、調試程序，設計一棵二叉樹，輸入完全二叉樹的先序序列，用#代表虛結點(空指針)，如ABD###CE##F##，建立二叉樹，求出先序、中序和后序以及按層次遍歷序列，求所有葉子及結點總數。 程序代碼: 實驗結果： 心得體會： 實驗5 實驗題目：圖的遍歷操作 實驗目的： 掌握有向圖和無向圖的概念;掌握鄰接矩陣和鄰接鏈表建立圖的存儲結構;掌握DFS及BFS對圖的遍歷操作;了解圖結構在人工智能、工程等領域的廣泛應用。 實驗要求： 采用鄰接矩陣和鄰接鏈表作為圖的存儲結構，完成有向圖和無向圖的DFS和BFS操作。 實驗主要步驟： 設計一個有向圖和一個無向圖，任選一種存儲結構，完成有向圖和無向圖的DFS(深度優先遍歷)和BFS(廣度優先遍歷)的操作。 1.鄰接矩陣作為存儲結構 #include”“ #include”“ #define MaxVertexNum 100 //定義最大頂點數 typedef struct{ char vexs;//頂點表 int edges;//鄰接矩陣，可看作邊表 int n,e;//圖中的頂點數n和邊數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);//輸入頂點數和邊數 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;//若為;//=========定義標志向 量，為 全 局 變 量=;typedefenum{FALSE,TRUE}B;Booleanvisited=1; G->edges=1;//若為無向圖，矩陣為對稱矩陣;若建立有向圖，去掉該條語句 } } //=========定義標志向量，為全局變量======= typedef enum{FALSE,TRUE} Boolean; Boolean visited; //========DFS：深度優先遍歷的遞歸算法====== void DFSM(MGraph *G,int i) { //以Vi為出發點對鄰接矩陣表示的圖G進行DFS搜索，鄰接矩陣是0，1矩陣 給出你的編碼 //===========BFS：廣度優先遍歷======= void BFS(MGraph *G,int k) { //以Vk為源點對用鄰接矩陣表示的圖G進行廣度優先搜索 給出你的編碼 //==========主程序main ===== void main() { int i; MGraph *G; G=(MGraph *)malloc(sizeof(MGraph));//為圖G請內存空間 CreatMGraph(G);//建立鄰接矩陣 printf(”Print Graph DFS: “); DFS(G);//深度優先遍歷 printf(” “); printf(”Print Graph BFS: “); BFS(G,3);//以序號為3的頂點開始廣度優先遍歷 printf(” “); } 2.鄰接鏈表作為存儲結構 #include”“ #include”“ #define MaxVertexNum 50 //定義最大頂點數 typedef struct node{ //邊表結點 int adjvex;//鄰接點域 struct node *next;//鏈域 申 }EdgeNode; typedef struct vnode{ //頂點表結點 char vertex;//頂點域 EdgeNode *firstedge;//邊表頭指針 }VertexNode; typedef VertexNode AdjList;//AdjList是鄰接表類型 typedef struct { AdjList adjlist;//鄰接表 int n,e;//圖中當前頂點數和邊數 } ALGraph;//圖類型 //=========建立圖的鄰接表======= void CreatALGraph(ALGraph *G) { int i,j,k; char a; EdgeNode *s;//定義邊表結點 printf(”Input VertexNum(n)and EdgesNum(e): “); scanf(”%d,%d“,&G->n,&G->e);//讀入頂點數和邊數 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));//生成邊表結點 s->adjvex=j;//鄰接點序號為j s->next=G->adjlist.firstedge; G->adjlist.firstedge=s;//將新結點*S插入頂點Vi的邊表頭部 s=(EdgeNode *)malloc(sizeof(EdgeNode)); s->adjvex=i;//鄰接點序號為i s->next=G->adjlist.firstedge; G->adjlist.firstedge=s;//將新結點*S插入頂點Vj的邊表頭部 } } //=========定義標志向量，為全局變量======= typedef enum{FALSE,TRUE} Boolean; Boolean visited; //========DFS：深度優先遍歷的遞歸算法====== void DFSM(ALGraph *G,int i) { //以Vi為出發點對鄰接鏈表表示的圖G進行DFS搜索 給出你的編碼 //==========BFS：廣度優先遍歷========= void BFS(ALGraph *G,int k) { //以Vk為源點對用鄰接鏈表表示的圖G進行廣度優先搜索 給出你的編碼 //==========主函數=========== 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(” "); } 實驗結果： 1.鄰接矩陣作為存儲結構 2.鄰接鏈表作為存儲結構 心得體會： 實驗6 實驗題目：二分查找算法的實現 實驗目的： 掌握二分查找法的工作原理及應用過程，利用其工作原理完成實驗題目中的內容。 實驗要求： 編寫程序構造一個有序表L，從鍵盤接收一個關鍵字key，用二分查找法在L中查找key，若找到則提示查找成功并輸出key所在的位置，否則提示沒有找到信息。 實驗主要步驟： 1.建立的初始查找表可以是無序的，如測試的數據為{3，7，11，15，17，21，35，42，50｝或者{11，21，7，3，15，50，42，35，17｝。 2.給出算法的遞歸和非遞歸代碼; 3.如何利用二分查找算法在一個有序表中插入一個元素x，并保持表的有序性? 程序代碼 實驗結果： 心得體會： 實驗7 實驗題目：排序 實驗目的： 掌握各種排序方法的基本思想、排序過程、算法實現，能進行時間和空間性能的分析，根據實際問題的特點和要求選擇合適的排序方法。 實驗要求： 實現直接排序、冒泡、直接選擇、快速、堆、歸并排序算法。比較各種算法的運行速度。 實驗主要步驟： 程序代碼 實驗結果： 心得體會： 《數據結構》課程設計題目(程序實現采用C語言) 題目1：猴子選王（學時：3） 一堆猴子都有編號，編號是1，2，3...m，這群猴子（m個）按照1-m的順序圍坐一圈，從第1開始數，每數到第n個，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。 要求：m及n要求從鍵盤輸入，存儲方式采用向量及鏈表兩種方式實現該問題求解。 //鏈表 #include typedef struct _RingNode { int pos; struct _RingNode *next;}RingNode, *RingNodePtr; // 創建約瑟夫環，pHead:鏈表頭指針，count:鏈表元素個數 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;// 構成環狀鏈表 } void KickFromRing(RingNodePtr pHead, int n){ RingNodePtr pCurr, pPrev; int i = 1; // 計數 pCurr = pPrev = pHead; while(pCurr!= NULL) { if(i == 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;} //數組做： #include void SelectKing(int MonkeyNum, int CallNum); void main(){ int MonkeyNum; int CallNum; /* 輸入猴子的個數 */ printf(“Monkey Num = ”); scanf(“%d”, &MonkeyNum); /* 輸入M的值 */ printf(“Call Num = ”); scanf(“%d”, &CallNum); SelectKing(MonkeyNum, CallNum); } void SelectKing(int MonkeyNum, int CallNum){ int *Monkeys;// 申請一個數組，表示所有的猴子； int counter = 0;//計數，當計數為猴子個數時表示選到最后一個猴子了； int position = 0;// 位置，數組的下標，輪流遍歷數組進行報數； int token = 0;// 令牌，將報數時數到M的猴子砍掉； // 申請猴子個數大小的數組，把桌子擺上。 Monkeys =(int *)malloc(sizeof(int)* MonkeyNum); if(NULL == Monkeys) { printf(“So many monkeys, system error.n”); return; } // 將數組的所有內容初始化為0，被砍掉的猴子設置為1 memset(Monkeys, 0, sizeof(int)*MonkeyNum); // 循環，直到選中大王 while(counter!= MonkeyNum) { // 如果這個位置的猴子之前沒有砍掉，那么報數有效 if(Monkeys[position] == 0) { token++;// 成功報數一個，令牌+1，繼續報數直到等于M // 如果報數到M，那么將這個猴子砍去 if(token == CallNum) { Monkeys[position] = 1;// 設置為1，表示砍去 counter++;// 計數增加 token = 0;// 設置為0，下次重新報數 // 如果是最后一個猴子，把它的位置打印，這個就是大王了 if(counter == MonkeyNum) { printf(“The king is the %d monkey.n”, position+1); } } } // 下一個猴子報數 position =(position + 1)%MonkeyNum; } // 釋放內存，開頭為所有猴子創建的桌子 free(Monkeys); return;} 題目2 ：字符逆轉（學時：3） 從鍵盤讀入一個字符串，把它存入一個鏈表（每個結點存儲1個字符），并按相反的次序將字符串輸出到顯示屏。 #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='
主站蜘蛛池模板：
国产女女做受ⅹxx高潮|
在线观看国产丝袜控网站|
老司机午夜福利试看体验区|
男ji大巴进入女人的视频|
午夜福利啪啪片|
人人妻人人爽日日人人|
亚洲人成在线观看影院牛大爷|
日本熟妇厨房xxxxx乱|
欧美黑人性暴力猛交喷水黑人巨大|
欧美高清性色生活片免费观看|
大肉大捧一进一出好爽视色大师|
国产a√无码专区亚洲av|
亚洲精品乱码久久久久久蜜桃图片|
狠狠色丁香婷婷久久综合五月|
国产精品无码av在线一区|
亚洲妇女行蜜桃av网网站|
国产精品亚洲片夜色在线|
久久精品女人天堂av麻|
国产成人手机高清在线观看网站|
国产亚洲精品久久777777|
馬与人黃色毛片一部|
久久国产精品波多野结衣av|
国产成人av一区二区三区无码|
在线看片免费人成视频电影|
久久免费的精品国产v∧|
中文字幕一区二区三区久久网站|
日韩在线精品成人av|
亚洲另类欧美在线电影|
色 综合 欧美 亚洲 国产|
2021国产精品香蕉在线观看|
国产青草视频在线观看|
男生白内裤自慰gv白袜男同|
色婷婷久久一区二区三区麻豆|
一区二区久久久久草草|
9999国产精品欧美久久久久久|
亚洲精品无码成人a片在|
97无码视频在线看视频|
精品一区二区三区在线观看|
亚洲精品乱码久久久久久日本麻豆|
国产美女精品一区二区三区|
精品少妇一区二区三区视频|
第二篇：數據結構學習(C)樹(總結)
第三篇：c數據結構實驗報告
第四篇：數據結構經典題目及c語言代碼總結