第一篇：數據結構 實驗一 圖[推薦]
北京郵電大學信息與通信工程學院
數據結構實驗報告
實驗名稱： 實驗二——圖 學生姓名： 佘晨陽 班
級： 2014211117 班內序號： 20 學
號： 2014210491 日
期： 2015年12月05日
1．實驗要求
根據圖的抽象數據類型的定義，使用鄰接矩陣或鄰接表實現一個圖。圖的基本功能：
1、圖的建立
2、圖的銷毀
3、深度優先遍歷圖
4、廣度優先遍歷圖
5、使用普里姆算法生成最小生成樹
6、使用克魯斯卡爾算法生成最小生成樹
7、求指定頂點到其他各頂點的最短路徑
8、其他：比如連通性判斷等自定義操作
編寫測試main()函數測試圖的正確性
2.程序分析
本實驗要求掌握圖基本操作的實現方法，了解最小生成樹的思想和相關概念，了解最短路徑的思想和相關概念，學習使用圖解決實際問題的能力。
2.1 存儲結構
存儲結構：1.不帶權值的無向圖鄰接矩陣
2.帶權值的無向圖鄰接矩陣
3.帶權值的有向圖鄰接矩陣
1．不帶權值的無向圖鄰接矩陣
第1頁 北京郵電大學信息與通信工程學院
2帶權值的無向圖鄰接矩陣.3.帶權值的有向圖鄰接矩陣
[備注]：
1.在使用打印元素、BFS、DFS 采用無權值的無向圖鄰接矩陣存儲方式 2.在使用PRIM、KRUSKAL、3.在使用最短路徑的算法時采用具有權值的有向圖鄰接矩陣存儲方式
2.2 關鍵算法分析
第2頁 北京郵電大學信息與通信工程學院
一．圖的鄰接矩陣構造函數：
1.關鍵算法： template
//帶權值的圖的構造函數 { int i, j, k, height;f s1, s2;vnum = n;arcnum = e;for(k = 0;k < n;k++){ vertex[k] = a[k];}
//初始化頂點
for(k = 0;k for(i = 0;i < n;i++) { arc[k][i] =-1; if(i == k)arc[k][i] = 0; //初始化權值的大小 } visited[k] = 0;} cout << endl;for(k = 0;k //初始化邊 { cout << “請輸入線性鏈接節點:”; cin >> s1 >> s2 >> height; arc[convert(s1)][convert(s2)] = height; arc[convert(s2)][convert(s1)] = arc[convert(s1)][convert(s2)];//采用無向圖帶權值的鄰接矩陣 } cout << endl;cout << “所得鄰接矩陣為：” << endl; for(k = 0;k for(i = 0;i < n;i++) { if(arc[k][i] ==-1) cout << “∞” << “ ”; else cout << arc[k][i] << “ ”; //打印鄰接矩陣的格式 } cout << endl; } cout << endl 2.算法的時間復雜度 第3頁 北京郵電大學信息與通信工程學院 有構造可知，初始化時其時間復雜度：O(n2) 二．深度優先便利DFS: 1.關鍵算法 ①從某頂點v出發并訪問 ②訪問v的第一個未訪問的鄰接點w，訪問w的第一個未訪問的鄰接點u，…… ③若當前頂點的所有鄰接點都被訪問過，則回溯，從上一級頂點的下一個未訪問過的頂點開始深度優先遍歷 ④直到所有和v路徑相通的頂點都被訪問到； 2.代碼圖解： 深度優先遍歷示意圖 3.代碼詳解： template for(int j = 0;j < vnum;j++) //連通圖 if((visited[j] == 0)&&(arc[v][j] >= 1))DFS(j);//當存在回路時，則連通深一層遍歷 } 4.時間復雜度 時間復雜度：O(n2) 空間復雜度：棧的深度O(n) 輔助空間O(n) 第4頁 北京郵電大學信息與通信工程學院 三．廣度遍歷BFS 1.關鍵算法 ①訪問頂點v ②依次訪問v的所有未被訪問的鄰接點v1,v2,v3… ③分別從v1,v2,v3…出發依次訪問它們未被訪問的鄰接點 ④反復①②③，直到所有和v路徑相通的頂點都被訪問到； 2.代碼圖解 3.代碼詳解 1.初始化隊列Q 2.訪問頂點v，visited[v]=1 3.while(隊列非空) 3.1 v=隊頭元素出隊 3.2 訪問隊頭元素的所有未訪問的鄰接點 4.時間復雜度 時間復雜度：O(n2) 空間復雜度：輔助空間O(n) 四.最小生成樹——普里姆算法 1,關鍵思路 一般情況下，假設n個頂點分成兩個集合：U(包含已落在生成樹上的結點)和V-U(尚未落在生成樹上的頂點)，則在所有連通U中頂點和V-U中頂點的邊中選取權值最小的邊。主數據結構： 鄰接矩陣 輔助數據結構： int adjvex[MAXSIZE];// U集中的頂點序號 第5頁 北京郵電大學信息與通信工程學院 int lowcost[MAXSIZE]; // U?(V-U)的最小權值邊 2.代碼圖解 第6頁 北京郵電大學信息與通信工程學院 第7頁 北京郵電大學信息與通信工程學院 3;代碼詳解 template //輔助數組存儲所有到的V0邊 { adjvex[i] = 0;lowcost[i] = arc[0][i]; } lowcost[0] = 0;for(int j = 1;j < vnum;j++) //循環n-1次 { int k = Mininum(lowcost); //求下一個頂點 cout << vertex[adjvex[k]] << “->” << vertex[k] << endl; lowcost[k] = 0; //U=U+{Vk} for(int j = 0;j < vnum;j++) //設置輔助數組 { if((lowcost[j]!= 0 && arc[k][j] < lowcost[j])) { lowcost[j] = arc[k][j]; adjvex[j] = k; } } 第8頁 北京郵電大學信息與通信工程學院 } } 4,時間復雜度： 時間復雜度O(n2)，適合稠密圖 五.最小生成樹----克魯斯卡爾算法 1,關鍵思路 先構造一個只含n個頂點的子圖SG，然后從權值最小的邊開始，若它的添加不使SG中產生回路，則在SG上加上這條邊，如此重復，直至加上n-1條邊為止。2.代碼圖解： 3.代碼詳解 template //最小生成樹—kruskal算法 { cout<<“Krusal算法結果為：”< int k = 0, j = 0; while(k < vnum-1){ int m = vedgelist[j].fromv, n = vedgelist[j].endv; int sn1 = vset[m]; int sn2 = vset[n]; //兩個頂點分屬 第9頁 北京郵電大學信息與通信工程學院 不同的集合 if(sn1!= sn2) { cout << vertex[m] << “->” << vertex[n] << endl; k++; for(int i = 0;i < vnum;i++) { if(vset[i] == sn2) vset[i] = sn1; //集合sn2全部改成sn1 } } j++;} } 4.時間復雜度 時間復雜度O(nlogn)，適合稀疏圖 六．最短路徑——Dijkstra算法 1.關鍵代碼 ? 按路徑長度遞增的次序產生源點到其余各頂點的最短路徑。? 1)設置集合s存儲已求得的最短路徑的頂點，? 2)初始狀態：s=源點v ? 3)疊代算法： ? 直接與v相連的最近頂點vi,加入s ? 從v經過vi可以到達的頂點中最短的，加入s …… 2.代碼圖解 第10頁 北京郵電大學信息與通信工程學院 3.代碼詳解 emplate //關于最短路徑的初始化 { int v=convert(x); for(int i = 0;i < vnum;i++) //初始化路徑和點 { s[i]=0; disk[i] = arc[v][i]; if(disk[i]!= maxs)path[i] = v; else path[i] =-1;} s[v] = 1;disk[v] = 0;path[v]=-1;for(int i = 0;i < vnum;i++) //反復經過從該點到其他點的路徑 { if((v = FindMin())==-1)continue; s[v] = 1; for(int j = 0;j < vnum;j++) if(!s[j] &&(disk[j]>arc[v][j] + disk[v])) { 第11頁 北京郵電大學信息與通信工程學院 disk[j] = arc[v][j] + disk[v]; path[j] = v; } } Print(); //打印路徑長度和遍歷 } 4.時間復雜度 時間復雜度為：n^2 七．判斷連通圖算法 template { cout<<“該圖為連通圖！*******輸入成功！”< return false; } else { cout<<“該圖不為連通圖！*******請重新輸入”< return true; } } 時間復雜度：n^2 3.程序運行結果 1.測試主函數流程： 第12頁 北京郵電大學信息與通信工程學院 函數流程圖： 1.輸入圖的連接邊并打印 構造下面所示圖的鄰接矩陣： 第13頁 北京郵電大學信息與通信工程學院 2.判斷圖連通是否成功 3.BFS DFS PRIM算法的實現 第14頁 北京郵電大學信息與通信工程學院 4.克魯斯卡爾算法實現過程 4.有向圖鄰接矩陣的構建 第15頁 北京郵電大學信息與通信工程學院 插入V0位置后打印距離并開始回溯 總結 1.調試時出現的問題及解決的方法 問題一：prim算法中 解決方法：調整循環條件，修正函數體注意有無Next的區別 第16頁 北京郵電大學信息與通信工程學院 問題二：BFS和DFS同時在一個類里作用時會輸出錯誤 解決方案：每次BFS/DFS使用時都把visited數組初始化一遍 問題三：在最短路徑，經常出現了停止輸入的情況 解決方法：改return為continue，并修改打印算法 2.心得體會 通過本次實驗，基本熟練掌握了c++基本語句，尤其對圖的結構及應用有了較深了解；調試代碼時盡量做到完成一個代碼段調試一次，可以最快檢測出錯誤所在；類的封裝和調用，類的共有成員和私有成員的設置。 3.下一步的改進 第一，設置增加圖節點和邊的函數 第二，實現圖形化輸出圖的路徑的功能 第三，主函數設計簡單，不要過于累贅 4.程序中出現的亮點 1)利用dfs算法衍生生成判斷是否為連通圖的連通算法 2)采用graph類實現所有圖的所有算法，所需的數據類型均在私有成員內，封裝 3)利用convert函數采取象意輸入，采用ABCD的節點輸入方式而并非轉化成01234再輸入。 4)BFS中采用c++標準庫的。 5)打印鄰接矩陣時，打印出非鏈接的∞符號和與自身路徑的0距離 6)判斷圖為非連通圖后，提示輸入錯誤，重新輸入圖元素 第17頁 數據結構上機實驗六 實驗內容:圖的基本操作 實驗要求: 1)圖的遍歷與基本操作要作為函數被調用.2)把自己使用的圖結構明確的表達出來.3)基本上實現每個實驗題目的要求.分組要求：可單獨完成，也可兩人一組。 實驗目的: 1)熟悉C/C++基本編程,培養動手能力.2)通過實驗,加深對圖的理解.評分標準： 1)只完成第一和第二題，根據情況得4，5分； 2）完成前3題，根據情況得5至7分； 3）在2）基礎上，選做四）中題目，根據情況得8至10分。 題目: 一)建立一個無向圖+遍歷+插入 (1)以數組表示法作為存儲結構，從鍵盤依次輸入頂點數、弧數與各弧信息建立一個無向圖； (2)對（1）中生成的無向圖進行廣度優先遍歷并打印結果； (3)向（1）中生成的無向圖插入一條新弧并打印結果； 二)建立一個有向圖+遍歷+插入+刪除 (1)以鄰接表作為圖的存儲結構，從鍵盤輸入圖的頂點與弧的信息建立一個有向圖； (2)對（1）中生成的有向圖進行深度優先遍歷并打印結果； (3)在（1）中生成的有向圖中，分別插入與刪除一條弧并打印其結果； (4)在（1）中生成的有向圖中，分別插入與刪除一個頂點并打印結果； (5)在（1）中生成的有向圖中,各頂點的入度與出度并打印結果； 三）基本應用題 （1）編寫算法，判斷圖中指定的兩個頂點是否連通。 （2）編寫算法，判斷圖的連通性。如果不連通，求連通分量的個數 （3）編寫算法，判斷圖中任意兩個頂點的連通性 （4）編寫算法，判斷圖中是否存在回路。 （5）實現圖的廣度優先搜索算法。 四）高級應用題 （1）實現Prim算法 （2）實現Kruskal算法 （3）實現迪杰斯特拉算法 （4）實現拓撲排序算法 （5）實現關鍵路徑算法 實驗五：圖的應用 班級學號姓名 一、實驗預備知識復習C++中的全局變量的概念。復習圖的鄰接矩陣和鄰接表兩種存儲方式。復習圖的兩種遍歷方法和求圖的最小生成樹的方法。 二、實驗目的掌握圖的鄰接矩陣和鄰接表兩種存儲方法。掌握有關圖的操作算法并用高級語言實現。熟悉圖的構造算法，了解實際問題的求解效率與采用何種存儲結構與算法有著密切聯系。掌握圖的兩種搜索路徑的遍歷算法。掌握求圖的最小生成樹的普里姆算法和克魯斯卡爾算法。 三、實驗內容創建給定的圖，從鄰接表和鄰接矩陣兩種存儲方式中選擇一種。對所創建的圖進行深度和廣度優先搜索遍歷，給出遍歷過程中的頂點序列。3 求圖的最小生成樹，按構造順序輸出邊的序列。編寫一個主函數，將上面函數連在一起，構成一個完整程序。將實驗源程序調試并運行。 四、實驗要求 所建立的圖為： ? 用鄰接表存儲結構時，所創建的單鏈表以結點的從小到大排列。? 注意標志數組visited[n+1] 的定義和賦值。 ? 將頂點1作為起點。 五、實驗結果 給出源程序及輸入、輸出結果。 六、實驗總結 實驗過程中遇到的問題及解決方法，收獲。 《數據結構》實驗(訓)指導書 電氣與信息工程學院實驗中心 前 言 《數據結構》是計算機相關專業的一門核心基礎課程，也是很多高校研究生入學考試專業課必考課程之一。它主要介紹線性結構、樹型結構、圖形結構三種邏輯結構元素的存儲實現，在此基礎上介紹一些典型算法及時、空效率分析。這門課程的主要任務是培養學生的算法分析、設計能力及良好的程序設計習慣。通過學習，要求學生能夠掌握典型算法的設計思想及程序實現，能夠根據實際問題選取合適的存儲方案，設計出簡潔、高效、實用的算法，為后續課程的學習及軟件開發打下良好的基礎。學習這門課程，習題和實驗是兩個關鍵環節。學生理解算法的最佳途徑是上機實驗。因此，實驗環節的好壞是學生能否學好《數據結構》的關鍵。為了更好地配合學生實驗，特編寫該實驗指導書。 一、實驗目的、要求和任務 計算機編程中加工處理的對象是數據，而數據具有一定的組織結構，所以學習編寫計算機程序僅僅了解計算機語言是不夠的，還必須掌握數據組織、存儲和運算的一般方法，這是數據結構課程中學習和研究的內容。由于數據結構的原理和算法較抽象，而該課程一般在本科低年級開設，對于計算機程序設計知識的初學者，理解和掌握其中的原理就顯得較為困難。 1.熟練掌握C語言的編輯、編譯、調試程序。2.會書寫類C語言的算法，并將算法轉變為程序實現。 3.正確理解各種數據結構的邏輯特性和存儲表示和基本操作的算法實現。4.有較強的邏輯分析能力。 5.針對問題的不同選擇合適的數據結構，提高算法設計的能力和動手實驗的技能。 6.學會分析研究計算機加工的數據結構的特性，以便為應用設計的數據選擇適當的邏輯結構、存儲結構及其相應的算法，并初步掌握算法的時間分析和空間分析的技術。 7.本課程的學習過程也是復雜程序設計的訓練過程，要求學生編寫的程序結構清楚、正確易讀，符合軟件過程的規范，從而培養學生的數據抽象能力。 8.通過若干數據結構應用實例，引導學生學習數據類型的使用，為今后學習面向對象的程序做一些鋪墊。 二、實驗基本內容及學時分配 為了達到實驗目的，本課程安排了4個實驗單元，訓練的重點在于基本的數據結構，而不是強調面面俱到。各實驗單元與教科書的各章只具有粗略的對應關系，一個實驗題常常涉及到幾部分教學內容。總學時：8學時。 1、線性表（2學時） （1）熟悉線性表的基本運算在兩種存儲結構（順序結構和鏈式結構）上的實現；（2）以線性表的各種操作（建立、插入、刪除等）的實現為重點； （3）通過本次實驗幫助學生提高C語言的編程能力（特別是函數參數、指針類型、鏈表的使用）。 2、數組和廣義表（2學時）（1）掌握稀疏矩陣的壓縮存儲 （2）掌握稀疏矩陣的轉置算法 3、樹與二叉樹（2學時） 常見的二叉樹遍歷算法有先序遍歷，中序遍歷和后序遍歷算法。實現簡單的先序遍歷，中序遍歷和后序遍歷算法。 4、排序（2學時） 常見的內部排序算法，插入類排序算法，如直接插入排序和希爾排序；交換類排序算法，如冒泡排序和快速排序；選擇類排序算法，如簡單選擇排序、樹形選擇類排序和堆排序。實冒泡排序或者直接插入排序算法。 三、說明 該課程采用理論與實踐相結合的教學方法，集知識性與趣味性于一體，達到良好的教學效果。硬件要求：在多媒體教室講解及演示。為保證教學順利進行，要求實驗室提供電腦等設備。學生每次上機實驗都必須遵守實驗室的有關規定。 四、實驗報告規范 實驗報告的內容包括： 1、實驗目的：說明實驗所驗證的知識點。 2、需求分析：以無歧義的陳述說明程序設計的任務、約束條件、輸入輸出要求、對功能的規定及模型。 3、邏輯設計：說明本程序中用到的所有抽象的數據類型的定義、主程序的流程以及各程序模塊之間的層次調用關系。 4、詳細設計：邏輯設計中定義的所有數據類型的實現，核心算法的設計描述、人機界面設計、函數之間調用關系的描述，主要功能的算法框架，測試數據設計。 5、測試分析：測試結果的分析與討論，測試過程中遇到的主要問題及采取的解決措施。 6、心得：軟件設計與實現過程中的經驗與體會，進一步改進的設想。 7、程序清單：源程序中應有足夠的注釋。如果提交源程序軟盤，列出程序文件名。 五、如何提高上機效率 為了提高上機的效率，真正達到實驗目的，要求同學做好實驗前的準備工作，寫好實驗預習報告，即實驗報告規范中的1）、2）、3）、4）部分，編寫好程序，并用一組測試數據手工執行程序靜態檢查程序是否有錯，通過閱讀、執行程序或給別人講解自己的程序而深入全面地理解程序邏輯，提高程序的正確性。對C語言程序不熟悉的同學，上機時最好帶上C語言程序設計的教材，以備查閱。調試中遇到問題，應認真分析，確定可疑點，設置調試斷點或輸出斷點處變量的值，以便發現問題，迅速排除問題，加快調試速度。 實驗室要求： 不能曠課，不遲到，不穿拖鞋進實驗室 實驗需預習報告（不能單純抄寫，預習程序代碼）實驗報告（總結，注釋，實驗結果） 目 錄 實驗一 線性表實驗（設計性實驗）..........................................4 實驗二 數組和廣義表實驗（設計性實驗）....................................6 實驗三 樹與二叉樹（設計性實驗）..........................................8 實驗四 排序（設計性實驗）................................................9 實驗一 線性表實驗（設計性實驗） 一、實驗目的 1.熟悉C語言的上機環境，進一步掌握C語言的結構特點。2.掌握線性表的順序存儲結構的定義及C語言實現。 3.掌握線性表的鏈式存儲結構——單鏈表的定義及C語言實現。4.掌握線性表在順序存儲結構即順序表中的各種基本操作。5.掌握線性表在鏈式存儲結構——單鏈表中的各種基本操作。 二、實驗內容 1.順序線性表的建立、插入及刪除。2.鏈式線性表的建立、插入及刪除。 三、實驗儀器設備與器材 上機電腦 四、實驗步驟 1.建立含n個數據元素的順序表并輸出該表中各元素的值及順序表的長度。 2.利用前面的實驗先建立一個順序表L={21，23，14，5，56，17，31}，然后在第i個位置插入元素68。 3.建立一個帶頭結點的單鏈表，結點的值域為整型數據。要求將用戶輸入的數據按尾插入法來建立相應單鏈表。 五、實驗提示 1.由于C語言的數組類型也有隨機存取的特點，一維數組的機內表示就是順序結構。因此，可用C語言的一維數組實現線性表的順序存儲。 在此，我們利用C語言的結構體類型定義順序表： #define MAXSIZE 1024 typedef int elemtype;/* 線性表中存放整型元素 */ typedef struct { elemtype vec[MAXSIZE];int len;/* 順序表的長度 */ }sequenlist;將此結構定義放在一個頭文件sqlist.h里，可避免在后面的參考程序中代碼重復書寫，另外在該頭文件里給出順序表的建立及常量的定義。 2.注意如何取到第i個元素，在插入過程中注意溢出情況以及數組的下標與位序（順序表中元素的次序）的區別。 3.單鏈表的結點結構除數據域外，還含有一個指針域。用C語言描述結點結構如下： typedef int elemtype;typedef struct node { elemtype data;//數據域 struct node *next;//指針域 }linklist; 注意結點的建立方法及構造新結點時指針的變化。構造一個結點需用到C語言的標準函數malloc()，如給指針變量p分配一個結點的地址： p=(linklist *)malloc(sizeof(linklist));該語句的功能是申請分配一個類型為linklist的結點的地址空間，并將首地址存入指針變量p 中。當結點不需要時可以用標準函數free(p)釋放結點存儲空間，這時p為空值（NULL）。 六、實驗總結與思考 1.如果按由表尾至表頭的次序輸入數據元素，應如何建立順序表。2.在main函數里如果去掉L=&a語句，會出現什么結果？ 實驗二 數組和廣義表實驗（設計性實驗） 一、實驗目的 1.掌握稀疏矩陣的壓縮存儲 2.掌握稀疏矩陣的轉置算法 二、實驗內容 1.實現上三角陣的壓縮存儲。 2.用三元組順序表存儲稀疏矩陣，并實現矩陣的轉置。 三、實驗儀器設備與器材 上機電腦 四、實驗步驟 1.創建一個數組。2.輸入數據 3.給定矩陣任一元素的下標，4.打印給定下標所對應的數據。5.創建三元組順序表。?a22 7.A輸出對應的矩陣。?? 21五、實驗提示 ?aaa6.輸入矩陣中的數據。?11?a11??a?313233a2122?1.對于如下對稱矩陣： ??A?aaa?4243?41?a31a32a33??1個位置，a21存入到第二個位置，?將它們存入到一個線性數組中B，不存非零元素，a11存入到第a41a42aija44????aij的位則aij能存到第幾個位置，我們要以用梯形公式算面積。置是它上面的元素之和再加上左邊的元素之和。 它上面的元素之和為((1+(i-1))×(i-1)/2，左邊的元素為(j-1)所以這個元素存儲的位置為k=i(i-1)/2+j-1。 因為矩陣A為對稱矩陣，(另一部分沒有寫出)，所以另一部分的元素為 k=j(j-1)/2+i-1.所以存在關系k=i(i-1)/2+j-1(i>j)和k=j(j-1)/2+i-1(i 2.結點結構 struct triple{ int i,j;//非零元的行下標和列下標 elemtype e;//非零元數據} 三元組順序表存儲類型 struct tsmatrix{ triple data[12500];aa?????a44?? int mu,nu,tu;} 三元順序表的轉置 方法：(1)將矩陣行列互換，(2)重排矩陣 六、實驗總結與思考 1.如何存儲三對角陣？ 2.如何用行邏輯鏈接順序表及十字鏈表存儲稀疏矩陣？ 實驗三 樹與二叉樹（設計性實驗） 一、實驗目的 1.掌握稀疏矩陣的壓縮存儲 2.掌握稀疏矩陣的轉置算法 二、實驗內容 1.練習二叉樹的建立與存儲 2.練習二叉樹的遍歷 三、實驗儀器設備與器材 上機電腦 四、實驗步驟 1.建立自己的頭文件BT.H，內容包括二叉鏈表的結構描述、二叉樹的建立、二叉樹的先序、中序與后序遍歷算法。 2.建立二叉樹,并通過調用函數,，輸出先序遍歷、中序遍歷與后序遍歷的結果。 五、實驗提示 建立二叉樹的代碼如下： BTCHINALR * createbt(){ BTCHINALR *q;struct node1 *s[30];int j,i,x;printf(“建立二叉樹，輸入結點對應的編號和值,編號和值之間用逗號隔開nn”);printf(“i,x = ”);scanf(“%d,%c”,&i,&x);while(i!= 0 && x!= '$') {q =(BTCHINALR*)malloc(sizeof(BTCHINALR));/*建立一個新結點q*/ q->data = x;q->lchild = NULL;q->rchild = NULL; s[i] = q;/*q新結點地址存入s指針數組中*/ if(i!= 1)/*i = 1，對應的結點是根結點*/ {j = i / 2;/*求雙親結點的編號j*/ if(i % 2 == 0)s[j]->lchild = q;/*q結點編號為偶數則掛在雙親結點j的左邊*/ else s[j]->rchild = q;} /*q結點編號為奇數則掛在雙親結點j的右邊*/ printf(“i,x = ”); scanf(“%d,%c”,&i,&x);} return s[1];/*返回根結點地址*/ } 六、實驗總結與思考 1.如何用孩子兄弟表示法存儲樹？ 2.熟悉及難赫夫曼樹。 實驗四 排序（設計性實驗） 一、實驗目的 1.掌握常用的排序方法，并掌握用高級語言實現排序算法的方法； 2.深刻理解排序的定義和各種排序方法的特點，并能加以靈活應用； 3.了解各種方法的排序過程及其時間復雜度的分析方法。 二、實驗內容 統計成績 給出n個學生的考試成績表，每條信息由姓名和分數組成，試設計一個算法： （1）按分數高低次序，打印出每個學生在考試中獲得的名次，分數相同的為同一名次；（2）按名次列出每個學生的姓名與分數。 三、實驗儀器設備與器材 上機電腦 四、實驗步驟 1.定義結構體。2.定義結構體數組。 3.定出主程序，對數據進行排序。 五、實驗提示 #define n 30 typedef struct student { char name[8];int score;} student R[n];main(){ int num, i, j, max, temp;printf(“n請輸入學生成績: n”);for(i=0;i if(max!=i){ temp = R[max];R[max]=R[i];R[i]= temp;} if((i>0)&&(R[i].score 六、實驗總結與思考 1.快速排序算法解決本問題。2.較各種排序算法的優缺點及。 3.使用其它排序算法實現該問題（直接插入排序、希爾排序、簡單選擇排序、堆排序等）。 數 據 結 構 實 驗 指 導 書 南京工程學院 信息管理與信息系統教研室 2014年3月 實驗一 線性表操作 一、實驗目的 1.熟悉C語言的上機環境，進一步掌握C語言的結構特點。2.掌握線性表的順序存儲結構的定義及C語言實現。 3.掌握線性表的鏈式存儲結構——單鏈表的定義及C語言實現。4.掌握線性表在順序存儲結構即順序表中的各種基本操作。5.掌握線性表在鏈式存儲結構——單鏈表中的各種基本操作。 二、實驗內容 1.順序線性表的建立、插入及刪除。 2.鏈式線性表的建立、插入及刪除。 三、實驗步驟 1.建立含n個數據元素的順序表并輸出該表中各元素的值及順序表的長度。2.利用前面的實驗先建立一個順序表L={21，23，14，5，56，17，31}，然后在第i個位置插入元素68。 3.建立一個帶頭結點的單鏈表，結點的值域為整型數據。要求將用戶輸入的數據按尾插入法來建立相應單鏈表。 四、實現提示 1.由于C語言的數組類型也有隨機存取的特點，一維數組的機內表示就是順序結構。因此，可用C語言的一維數組實現線性表的順序存儲。 在此，我們利用C語言的結構體類型定義順序表： #define MAXSIZE 1024 typedef int elemtype;/* 線性表中存放整型元素 */ typedef struct { elemtype vec[MAXSIZE];int len;/* 順序表的長度 */ }sequenlist;將此結構定義放在一個頭文件sqlist.h里，可避免在后面的參考程序中代碼重復書寫，另外在該頭文件里給出順序表的建立及常量的定義。 2.注意如何取到第i個元素，在插入過程中注意溢出情況以及數組的下標與位序（順序表中元素的次序）的區別。 3.單鏈表的結點結構除數據域外，還含有一個指針域。用C語言描述結點結構如下： typedef int elemtype;typedef struct node { elemtype data;//數據域 struct node *next;//指針域 }linklist;注意結點的建立方法及構造新結點時指針的變化。構造一個結點需用到C語言的標準函數malloc()，如給指針變量p分配一個結點的地址： p=(linklist *)malloc(sizeof(linklist));該語句的功能是申請分配一個類型為linklist的結點的地址空間，并將首地址存入指針變量p 中。當結點不需要時可以用標準函數free(p)釋放結點存儲空間，這時p為空值（NULL）。 五、思考與提高 1.如果按由表尾至表頭的次序輸入數據元素，應如何建立順序表。2.在main函數里如果去掉L=&a語句，會出現什么結果？ 實驗二 棧和隊列的應用 一、實驗目的 1.掌握棧的順序表示和實現 2.掌握隊列的鏈式表示和實現 二、實驗內容 1.編寫一個程序實現順序棧的各種基本運算。2.實現隊列的鏈式表示和實現。 三、實驗步驟 1.順序棧(1)初始化順序棧;(2)插入元素(3)刪除棧頂元素(4)取棧頂元素(5)遍歷順序棧(6)置空順序棧 2.鏈隊列 (1)初始化并建立鏈隊列(2.)入鏈隊列(3)出鏈隊列(4)遍歷鏈隊列 四、實現提示 1./*定義順序棧的存儲結構*/ typedef struct { ElemType stack[MAXNUM];int top;}SqStack; /*初始化順序棧函數*/ void InitStack(SqStack *p) {q=(SqStack*)malloc(sizeof(SqStack));/*申請空間*/} /*入棧函數*/ void Push(SqStack *p,ElemType x){if(p->top SqStack S; ElemType e; int N; /*初始化順序棧*/ /*入棧*/ /*出棧*/ /*遍歷順序棧*/ getch();} 2./*定義鏈隊列*/ typedef struct Qnode { ElemType data;struct Qnode *next;}Qnodetype;typedef struct { Qnodetype *front;Qnodetype *rear;}Lqueue; /*初始化并建立鏈隊列函數*/ void creat(Lqueue *q) { h=(Qnodetype*)malloc(sizeof(Qnodetype));/*初始化申請空間*/ h->next=NULL;q->front=h;q->rear=h;for(i=1;i<=n;i++)*利用循環快速輸入數據*/ { scanf(“%d”,&x);Lappend(q,x);} /*利用入鏈隊列函數快速輸入數據*/ } /*入鏈隊列函數*/ void Lappend(Lqueue *q,int x){ s->data=x;s->next=NULL;q->rear->next=s;q->rear=s;} /*出鏈隊列函數*/ ElemType Ldelete(Lqueue *q){ p=q->front->next;q->front->next=p->next;if(p->next==NULL)q->rear=q->front;x=p->data;free(p);} /*釋放空間*/ /*遍歷鏈隊列函數*/ void display(Lqueue *q){ while(p!=NULL)/*利用條件判斷是否到隊尾*/ { printf(“%d-->”,p->data);p=p->next;} } 可參考如下代碼： #include “stdio.h” #define MaxSize 100 typedef int ElemType;main(){ LinkQueue Q; ElemType e; /*初始化并建立鏈隊列*/ /*入鏈隊列*/ /*出鏈隊列*/ *遍歷鏈隊列*/ } DestoryQueue(&Q); getch();} 五、思考與提高 1.讀棧頂元素的算法與退棧頂元素的算法有何區別？ 試寫一個算法，判別讀入的一個以‘@’為結束符的字符序列是否是?回文?。實驗三 樹操作 一、實驗目的 1.通過實驗，掌握二叉樹的建立與存儲 2.通過實驗，掌握二叉樹的遍歷方法 二、實驗內容 1.練習二叉樹的建立與存儲 2.練習二叉樹的遍歷 三、實驗步驟 1.建立二叉鏈表的結構描述、二叉樹的建立、二叉樹的先序、中序與后序遍歷算法。 2.建立二叉樹,并通過調用函數, 輸出先序遍歷、中序遍歷與后序遍歷的結果。 四、實現提示 1.采用遞歸方法建立二叉樹： 首先建立二叉樹的根 結點，然后建立其左右子樹，直到空子樹為止。 2.先序遍歷、中序遍歷與后序遍歷二叉樹。#include BiTree CreateBiTree(BiTree &T){ } /*先序遍歷*/ Status PreOrderTraverse(BiTree T){ } /*中序遍歷*/ Status InOrderTraverse(BiTree T){ } /*后序遍歷*/ Status PostOrderTraverse(BiTree T){ } int main(){ BiTree T;CreateBiTree(T);PreOrderTraverse(T);printf(“n”);/*先序遍歷*/ InOrderTraverse(T);printf(“n”);/*中序遍歷*/ PostOrderTraverse(T);printf(“n”);/*后序遍歷*/ return 0;} 五、思考與提高 編寫遞歸算法，計算二叉樹中葉子結點的數目。第二篇：數據結構上機實驗--圖
第三篇：北化航天工業學院~數據結構~實驗5圖
第四篇：《數據結構》實驗指導書
第五篇：《數據結構》實驗指導書
![下載數據結構 實驗一 圖[推薦]word格式文檔](http://static.xiexiebang.com/skin/default/images/icon_word.png){kind=icon}
點擊咨詢 