《資料結構》
實驗報告
專業13物聯網
年級大二
姓名繆思婷
學號1317443007
指導老師黃河
實驗室使用日期
實驗三演算法的時間複雜度
一、實驗目的
1、幫助讀者複習c語言程式設計中的知識。
2、通過本實驗加深對時間複雜度的理解。
二、實驗內容
[問題描述]
1. 背景知識：
● 時間複雜度：
在電腦科學中，演算法的時間複雜度是乙個函式，它定量描述了該演算法的執行時間。這是乙個關於代表演算法輸入值的字串的長度的函式。
● 氣泡排序
氣泡排序是一種簡單的排序演算法。它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。
這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。
● 氣泡排序演算法的運作如下：
1) 比較相鄰的元素。如果第乙個比第二個大，就交換他們兩個。
2) 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。這步做完後，最後的元素會是最大的數。
3) 針對所有的元素重複以上的步驟，除了最後乙個。
4) 持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。
詳細演算法可以參見以下鏈結：
● 選擇排序
選擇排序是一種簡單直觀的排序演算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。
以此類推，直到所有元素均排序完畢。
可以參見以下鏈結：
2. 實驗內容：
生成8個整數陣列，分別使用冒泡法，選擇法進行排序，並比較排序所消耗的時間。
● 8個陣列分為4組，長度為10，100,1000,10000。
● 每組資料中其中乙份陣列中資料為隨機排列，另乙份陣列中資料為逆序排列（例如）。
[基本要求]
（1） 使用c或c++編寫程式完成上述實驗
（2） 可以使用clock函式獲取計算機的當前時間。
clock（）函式獲得當前程式消耗時間（時鐘週期），所以兩次clock之間的差除以clocks_per_sec即可獲得當前時間消耗的時間（秒），詳細可以參見clock.cpp檔案。
三、設計思路
用rand()函式，隨機生成所需要的數，用系統核心內定時器的頻率來計算所經過的時間。
4、源**
void setrand(int size);
void setsequence(int size);
void bubble_sort(int a,int n);
void select_sort(int r, int n);
large_integer start;
large_integer end;
large_integer freq;
int ar[10000];
int size;
int main()
}} 五、測試結果
6、心得體會
本次實驗，用clock（）函式對排序時間測定的，我對於各種排序全都了然於心，運用更加熟練。
資料結構實驗報告
實驗報告 實驗課程 資料結構 實驗專案實驗 專業 電腦科學與技術 姓名於凡 學號 10703070328 指導教師汪林林 實驗時間 2008 12 7 重慶工學院計算機學院 實驗一線性表 1.實驗要求 掌握資料結構中線性表的基本概念。熟練掌握線性表的基本操作 建立 插入 刪除 查詢 輸出 求長度及合...
資料結構實驗報告
實驗一線性表的基本操作 1 實驗目的2 2 實驗環境2 3 實驗內容，主要 除錯與執行 2 4 總結14 實驗二棧的基本操作 1 實驗目的15 2 實驗環境15 3 實驗內容，主要 除錯與執行 15 4 總結18 實驗三赫夫曼樹 1 實驗目的18 2 實驗環境18 3 實驗內容，主要 除錯與執行 1...
資料結構實驗報告
實驗題目 計算機與通訊工程學院 2014 實驗一線性表的應用 實驗目的 1 掌握線性表的邏輯結構定義 2 掌握線性表的兩種儲存結構 順序和鏈式 3 掌握順序表和煉表的定義及基本操作 實驗內容 通過程式設計完成具有一定實際意義的課題，加深對線性表應用的理解和掌握。參考題目如下所示。學生可在完成以下題目...