教學單位資訊工程系
學生學號 0143017541
題目課程設計彙總
學生姓名
專業名稱軟體工程
指導教師葉從歡
2023年5月31日
目錄資料結構課程設計彙總 1
課程設計
一、多項式的基本運算 3
實驗目的： 3
實驗內容： 3
解題思路： 3
實驗小結： 8
課程設計
二、棧的應用—逆波蘭式求值 8
實驗目的： 8
實驗內容： 9
解題思路： 9
實驗小結： 12
課程設計
三、圖的應用—簡易的社交網路圖 13
實驗目的： 13
實驗內容： 13
解題思路： 14
實驗小結： 22
課程設計
四、哈夫曼編碼 23
實驗目的： 23
實驗內容： 23
解題思路： 23
實驗小結： 28
課程設計
五、雜湊表的相關運算 29
實驗目的： 29
實驗內容： 29
解題思路： 29
實驗小結： 33
課程設計六、 廣義表的建立與遍歷 33
實驗目的： 33
實驗內容： 33
思路分析： 34
實驗總結： 40
課程設計
七、排序方法 40
實驗目的： 40
實驗內容： 40
解題思路： 41
實驗小結： 48
掌握線性表的鏈式儲存結構和線性表的典型應用—多項式求和、差運算，通過實驗進一步加深對線性表的儲存結構的理解與熟悉。
鏈式儲存結構的實現：
已知：f(x)=100x＾100+5x＾50-30x＾10+10,
g(x)=150x＾90-5x＾50+40x＾20+20x＾10+3x,
求和與差。
定義乙個結構體陣列，p儲存係數,q儲存指數。分別輸出兩次輸入的多項式。將兩次輸入的多項式的指數按從大到小的順序進行排列，同時相應的係數要進行交換。
輸出時如果進行如果當前該項與下一項的的係數相同，將兩項係數相加後輸出，並跳過下一項，如果不相等，直接輸出。輸出時需注意的問題：當係數為0時，該項不輸出當係數為負數時，不要再在前面輸出+。
程式如下：
結果驗證：
1. 掌握棧的特點及其描述方法；
2. 掌握棧的各種基本操作；
3. 掌握棧的乙個經典應用-逆波蘭式求值問題。
從鍵盤敲入乙個整數表示式，先將其轉化為逆波蘭表示式，再計算值。
逆波蘭式又叫字尾表示式，規定把運算符號放在兩個運算元的後面。在字尾表示式中，不存在運算子的優先順序問題，也不存在任何括號。字尾表示式求值的步驟：
1.初始化乙個空運算元棧:
2.從前到後讀取字尾表示式字元。如果是運算元直接入棧。如果讀到乙個操作符@，彈出棧頂元素a和新的棧頂元素b，執行b @ a，將結果壓入棧中；
3.最後棧中只剩下乙個元素，即表示式的值。
源**如下：
實驗結果驗證：
（1） 掌握圖的幾種儲存方法（鄰接矩陣、鄰接表等）；
（2） 掌握圖的連通和圖中各節點的聯絡。
給出如圖所示的簡易社交連通圖：
要求：輸入a,b,c,d,e,f處的人名，計算某兩人之間的陌生度（即權值的大小之和）與連通兩人的通路（權值在下面的**中已給出）。
直接相連的兩個節點間邊的權值就是兩節點間的親密度（陌生度），權值越小，節點間越親密；通過鄰接矩陣給出的數值可以求出兩節點間的親密度；通過迪克斯特卡演算法可以求出不相鄰的兩節點間的權值之和和經過的節點，從而達到解決問題的目的。
程式**如下：
執行結果：
用所學的知識構造一棵哈夫曼樹並以英文本母出現的次數做權值，遍歷哈夫曼樹同時輸出每個字母的哈夫曼編碼。
從txt檔案讀入一段英文，統計其中每個字母出現的頻率，並輸出其哈夫曼編碼。
構造哈夫曼編碼的方法如下：
第一步定義乙個結點的結構體，包括結點的權值，結點的雙親結點，左孩子，右孩子。
並定義兩個htnode,*huffmantree為該型別的名字。
第二步建立乙個select函式用來選擇結點較小的結點權值和下標。實現方法主要利用兩個for迴圈實現。首先判斷是否是單個結點如果是跳出for迴圈如果不是定義p和s記錄當前結點的權值和記錄當前結點的下標。
接著通過乙個for迴圈進行選擇把結點權值最小的1 4結點權值和下標記錄分別記錄在p和s中。
第三步構造哈夫曼樹和求每個字元的哈夫曼編碼。先判斷結點個數n是否小於等於1如果是則返回如果大於1則計算出哈夫曼樹中共有m=2n-1個結點。然後建立乙個htnode型別的陣列ht儲存結點個數（結點的相關資訊），再定義乙個huffmantree型別的指標p用來指向陣列ht。
將ht中前n個單元儲存輸入的結點資訊，後m-n個單元儲存為空結點。接著構造哈夫曼樹，其實現方法為首先利用select函式選擇權值最小的兩個結點s1
和s2再將將s1和s2合併從而得到這兩個結點的雙親結點儲存為i，且雙親結點的權值為s1,s2權值之和。接著從葉子到根逆向求每個字元的哈夫曼編碼。其實現方法為：
首先建立乙個字元指標陣列hc和乙個字元型指標陣列cd用來儲存"0"和"1"。定義c表示結點序號，f表示c結點的雙親結點序號，接著通過乙個for迴圈將建立好的哈夫曼樹的左邊賦值為0右邊賦值1，再為每乙個結點建立乙個長度為n-start的字元陣列用來儲存哈夫曼編碼。最後把從cd位址開始且含有null結束符的字串賦值到以hc開始的位址空間。
第四步main函式的實現。首先定義乙個huffmantree型別的ht初始化為空。接著輸入哈夫曼權值的個數判斷個數是否小於等於1如果小於等於1則輸出"輸入錯誤,哈夫曼權值的個數要大於1"。
如果大於1則建立乙個w指標陣列用來儲存結點權值，最後通過呼叫huffmancoding函式輸出每個結點的哈夫曼編碼。
程式如下：
結果驗證：
建立乙個雜湊表，完成其插入、刪除、查詢等相關基本運算，在實驗的過程中加深對相關知識點的理解和掌握。
資料結構課程設計
指導書山東建築大學 電腦科學與技術學院 二 六年十二月 課程設計基本情況 課程名稱 資料結構課程設計 相關課程 c語言程式設計 visual c 程式設計 資料結構 適合專業 電腦科學與技術 網路工程 軟體工程 設計週數 2周 學分 2學分 開課學期 第4學期 開課單位 電腦科學與技術學院 一 課程...
資料結構課程設計
總結報告 專業軟體工程 班級軟體1007 學號 20103540 姓名 日期 2012.9.17 東北大學軟體學院 第一章需求分析 問題定義 實現乙個網上拍賣系統，根據需求描述和附加的框架 完成乙個網上拍賣系統。分析 整個系統執行於windows平台，是基於b s結構的商業應用程式，程式為使用者提供...
資料結構課程設計
環境與測繪學院 1 c 物件導向程式設計基礎 實驗簡介 學會用演算法語言c 描述抽象資料型別。理解資料結構的組成分為兩部分，第一部分是資料集 資料元素 第二部分是在此資料集上的操作。從物件導向的觀點看，這兩部分代表了物件的屬性和方法。掌握用c 描述資料結構的基本方法，即通過建立類來描述抽象資料型別。...