實驗名稱： 實驗四——題目二
學生姓名：
班級：班內序號：
學號：日期： 2023年12月16日
1．實驗要求
使用鍊錶實現下面各種排序演算法，並進行比較。
排序演算法：
1、插入排序
2、氣泡排序
3、快速排序
4、簡單選擇排序
5、其他
要求：1、測試資料分成三類：正序、逆序、隨機資料
2、對於這三類資料，比較上述排序演算法中關鍵字的比較次數和移動次數（其中關鍵字交換計為3次移動）。
3、對於這三類資料，比較上述排序演算法中不同演算法的執行時間，精確到微秒（選作）
4、對2和3的結果進行分析，驗證上述各種演算法的時間複雜度
編寫測試main()函式測試線性表的正確性
2. 程式分析
2.1 儲存結構
含頭指標的單鏈表為主要資料結構。單鏈表、結點結構示意圖如下圖一：
頭指標 ……
圖一單鏈表示意圖結點結構
2.2 關鍵演算法分析
關鍵演算法：
1.頭插法建立單鏈表
演算法步驟：
1． 通過對話介面輸入資料個數count;
2． 用頭插法建立單鏈表
2.1.用k接受輸入的資料 ，申請乙個新記憶體空間，將k賦值給他的data
2.2.將first的next所指向的節點賦給s的next指標，將s賦給first的next指標
2.3利用pre將s與first及s後的節點聯絡起來
2.4.每迴圈一次迴圈控制標量a減一
3． 用乙個迴圈將資料按原順序賦給data陣列，以便重新進行新排序
時間複雜度為o（n），空間複雜度為o（n）；
2、插入排序演算法
演算法步驟：
1. 將q和p 放在鍊錶的前兩個節點；
2. 迴圈開始，q從第二個節點開始移動；
3. 將p從第乙個節點一直移動到q的第乙個節點，比較值，找到適合的位置就插入；
4. 如果q與其前面的比較完畢，就把q後移；
當指標移到鍊錶末尾時，排序結束。
時間複雜度為o（n2）
3、氣泡排序演算法
1. 將p和q指標分別放在鍊錶的開始兩個位置；
2. 比較p和q 的值：
如果p->data大於q->data，就交換；
否則繼續往後走；
到p和q走完一次迴圈，然後再重複，找出第二大的。
時間複雜度為o（n2）
4、簡單選擇排序演算法
1. 將p指標的q指標放在鍊錶的前兩個位置；
2. 將p從頭開始移動；
3. 將q從p後的第乙個指標開始移動，然後每一次比較最小值；
4. 將最小值與p交換，p後移，直至結束。
時間複雜度為o（n2）
5、快速排序演算法
1. 用top與end分別表示頭指標和為指標
2. 進入迴圈，用於找到左邊第乙個數的位置
2.1 設定temp變數，做值交換是暫存資料的作用
進入迴圈，如果p指向資料小於q的且p和q不相等，則q右移；否則跳出迴圈並將p和q指向數值交換，然後p右移乙個節點
進入另乙個迴圈，如果p指向資料小於q的且p和q不相等，則p右移乙個節點；否則跳出迴圈並將q和p指向數值交換，然後q右移乙個節點
如果p和q不等，則繼續迴圈
3. p和q 相等跳出迴圈，排好了乙個數，遞迴呼叫該函式
3.1.如果top和p不相等且top不是p的前指標，則以top和p->pre為頭為指標進入迴圈
3.2若果end和q不相等且end不是q的後指標，則以end和q->next為頭尾指標進入迴圈。
時間複雜度為o（nlog2n）
3.程式執行結果
1.測試主函式流程：
繼續排序則
重新建立鍊錶
繼續不繼續2、測試結論
4. 總結
在這次實驗中，複習了鍊錶的有關知識，進一步加深了對各種排序方式的理解，注意了異常處理，在程式設計中採用選擇的方式，這並沒有必要，同時也沒有將各種排序演算法安排在同一介面進行比較，需要進一步改進。在以後，也需要多多加強實踐，進一步提高程式設計能力。
實驗報告四資料結構
寧波大學科學技術學院 資料結構實驗報告 實驗名稱資料查詢 實驗者 08信計肖勤偉 一實驗名稱 順序表的查詢演算法比較分析 二實驗目的 熟悉靜態查詢的相關演算法 三實驗內容 1.實現順序表的查詢演算法 2.實現有序表的折半查詢演算法 四實驗步驟 1需求分析 需要建立乙個線性表 2演算法概要 建立乙個表...
資料結構課內實驗四
實驗四排序的基本操作與實現 一 實驗目的 1 複習c語言中指標 結構體 子程式呼叫等基礎知識 2 掌握常用的排序方法，並掌握用c語言實現排序演算法的方法 3 深刻理解排序的定義和各種排序方法的特點，並能加以靈活應用 4 了解各種方法的排序過程及其時間複雜度的分析方法。二 實驗裝置 微機三 預習要求 ...
資料結構上機實驗四
實驗內容 廣義表的基本操作 實驗要求 1 廣義表的建立與顯示要作為函式被呼叫.2 把自己使用的廣義表結構明確的表達出來.3 基本上實現每個實驗題目的要求.分組要求 可單獨完成，也可兩人一組。實驗目的 1 熟悉c c 基本程式設計,培養動手能力.2 通過實驗,加深對廣義表的理解.評分標準 1 只完成第...