廣州大學學生實驗報告

開課實驗室：計算機科學與工程實驗（電子樓418A）
學院 計算機科學與網絡工程學院
實驗課程 數據結構實驗
實驗項目 實驗四 查找和排序算法實現

• 一、實驗目的：
  1、各種排序算法的實現
  2、各種查找算法實現
  • 順序查找
  • 折半查找
  • 二叉查找樹
• 二、使用儀器、器材
  微機一臺
  操作系統：WinXP
  編程軟件：C++
• 三、實驗內容及原理
  1、各種排序算法的實現 （返回目錄🖱）
  用隨機函數生成16個2位正整數（10~99），實現插入排序、選擇排序、冒泡排序、雙向冒泡、快速排序、二路歸并排序等多種排序算法，輸出排序中間過程、統計關鍵字的比較次數和記錄的移動次數。

代碼說明：各排序算法在同一個cpp文件中，老師要檢查某個算法時可以把main函數中的相應排序算法的注釋符號“//”去掉即可；

#include<iostream> #include<ctime> using namespace std;const int maxnum = 1000; //數組結構 typedef struct sqlist {int l[maxnum];int length; }sqlist;//------插入排序-----（采用“從后向前比較”策略） void InsertSort(sqlist list, int length) {int compare_count = 0; //關鍵字比較次數int remove_count = 0; //關鍵字移動次數int process = 1; //第n次中間過程for (int i = 2; i <= list.length; i++) {compare_count++; //關鍵字比較次數+1if (list.l[i] < list.l[i - 1]) {list.l[0] = list.l[i]; // list.l[0]: 人稱“哨兵”list.l[i] = list.l[i - 1]; //將list.[i]后移int j = 0;for (j = i - 2; list.l[0] < list.l[j]; j--) {list.l[j + 1] = list.l[j]; //將記錄逐個后移} list.l[j + 1] = list.l[0]; //將“哨兵”插入到正確的位置remove_count++; //關鍵字移動次數+1}//中間過程輸出cout << "第" << process++ << "次中間過程輸出:" << endl;for (int i = 1; i <= list.length; i++) {cout << list.l[i] << ' ';}cout << endl;}//輸出關鍵字比較次數和關鍵字移動次數cout << "關鍵字比較次數：" << compare_count << "\t"<< "關鍵字移動次數：" << remove_count << endl; }//-----選擇排序----- void SelectSort(sqlist& list) {int k = 0;int process = 1; //第n次中間過程int compare_count = 0; //關鍵字比較次數int remove_count = 0; //關鍵字移動次數for (int i = 1; i < list.length; i++) {k = i;for (int j = i + 1; j <= list.length; j++) {compare_count++; //關鍵字比較次數+1if (list.l[j] < list.l[k]) k = j; //尋找數組剩余未排序元素中的值最小元素的下標if (k != i) {remove_count++; //關鍵字移動次數+1int temp = list.l[i];list.l[i] = list.l[k];list.l[k] = temp;}}//中間過程輸出cout << "第" << process++ << "次中間過程輸出:" << endl;for (int i = 1; i <= list.length; i++) {cout << list.l[i] << ' ';}cout << endl;}//輸出關鍵字比較次數和關鍵字移動次數cout << "關鍵字比較次數：" << compare_count << "\t"<< "關鍵字移動次數：" << remove_count << endl;}//-----冒泡排序----- void BubbleSort(sqlist& list) {int n = list.length; //作為結束循環的條件之一int flag = 1; //是否排序完成的標記int process = 1; //第n次中間過程int compare_count = 0; //關鍵字比較次數int remove_count = 0; //關鍵字移動次數//設置兩重循環while (n--&&flag) {flag = 0;for (int j = 1; j < list.length; j++) {compare_count++; //關鍵字比較次數+1if (list.l[j] > list.l[j + 1]) {remove_count++; //關鍵字移動次數+1flag = 1;int temp = list.l[j];list.l[j] = list.l[j + 1];list.l[j + 1] = temp;}}//中間過程輸出cout << "第" << process++ << "次中間過程輸出:" << endl;for (int i = 1; i <= list.length; i++) {cout << list.l[i] << ' ';}cout << endl;}//輸出關鍵字比較次數和關鍵字移動次數cout << "關鍵字比較次數：" << compare_count << "\t"<< "關鍵字移動次數：" << remove_count << endl; }//-----雙向冒泡---- void TwowaybubbleSort(sqlist& list) {int n = list.length;int flag = 1;int process = 1; //第n次中間過程int compare_count = 0; //關鍵字比較次數int remove_count = 0; //關鍵字移動次數int left= 1; //初始化待排序數組的最左端元素序號int right= list.length; //初始化待排序數組的最右端元素序號int temp_right = 0; //暫存待更新待排序數組的最右端元素序號int temp_left = 0; //暫存待更新待排序數組的最左端元素序號//設置兩重循環while (n--&&flag) {flag = 0;for ( int j = left; j < right; j++) {compare_count++; //關鍵字比較次數+1if (list.l[j] > list.l[j + 1]) {flag = 1;remove_count++; //關鍵字移動次數+1int temp = list.l[j];list.l[j] = list.l[j + 1];list.l[j + 1] = temp;temp_right = j;}}right = temp_right; //更新待排序數組的最右端元素序號for (int j = right; j >left; j--) {compare_count++; //關鍵字比較次數+1if (list.l[j] < list.l[j-1]) {flag = 1;remove_count++; //關鍵字移動次數+1int temp = list.l[j];list.l[j] = list.l[j - 1];list.l[j - 1] = temp;temp_left = j;}}left = temp_left; //更新待排序數組的最左端元素序號//中間過程輸出cout << "第" << process++ << "次中間過程輸出:" << endl;for (int i = 1; i <= list.length; i++) {cout << list.l[i] << ' ';}cout << endl;cout << "left,right：" << left << ' ' << right << endl;}//輸出關鍵字比較次數和關鍵字移動次數cout << "關鍵字比較次數：" << compare_count << "\t"<< "關鍵字移動次數：" << remove_count << endl; }//-----快速排序----- int QSort_process = 1; //第n次中間過程 int QSort_compare_count = 0; //關鍵字比較次數 int QSort_remove_count = 0; //關鍵字移動次數 void QSort(sqlist& list,int low, int high) {int i, j, pivotkey;i = low;j = high;if (low < high){pivotkey = list.l[low]; //設置樞軸while (i != j){while (j > i&& list.l[j] >= pivotkey){--j;QSort_compare_count++; //關鍵字比較次數+1}if (i < j){list.l[i] = list.l[j]; //交換++i;QSort_remove_count++; //關鍵字移動次數+1}while (i < j && list.l[i] <= pivotkey){++i;QSort_compare_count++; //關鍵字比較次數+1}if (i < j){list.l[j] = list.l[i]; //交換--j;QSort_remove_count++; //關鍵字移動次數+1}}list.l[i] = pivotkey; //樞軸記錄到位//中間過程輸出cout << "第" << QSort_process++ << "次中間過程輸出:" << endl;for (int n = 1; n <= list.length; n++) {cout << list.l[n] << ' ';}cout << endl;//遞歸QSort(list, low, i - 1);QSort(list, i + 1, high);} }//-----二路歸并排序----- int MSort_process = 1; //第n次中間過程 int MSort_compare_count = 0; //關鍵字比較次數 int MSort_remove_count = 0; //關鍵字移動次數 void Merge(sqlist &list, int low, int mid, int high) {int len = high - low + 1;int* temp = new int[len];int i = low; int j = mid + 1; //i,j分別為兩個子序列的下標int k = 0; //新合并的數組的下標while (i <= mid && j <= high) {if (list.l[i] <= list.l[j]) {MSort_compare_count++; //關鍵字比較次數+1MSort_remove_count++; //關鍵字移動次數+1temp[k] = list.l[i];i++;k++;}else {MSort_compare_count++; //關鍵字比較次數+1MSort_remove_count++; //關鍵字移動次數+1temp[k] = list.l[j];j++;k++;}}while (i <= mid) {temp[k] = list.l[i];i++;k++;}while (j <= high) {temp[k] = list.l[j];j++;k++;}for (int i = 0; i < len; i++) {list.l[low+i] = temp[i];} }void MSort(sqlist &list,int low,int high) {if (low < high) {int mid = (low + high) / 2;//遞歸MSort(list, low, mid);MSort(list, mid + 1, high);//合并左右序列（子樹）Merge(list, low, mid, high);}//中間過程輸出cout << "第" << MSort_process++ << "次中間過程輸出:" << endl;for (int n = 1; n <= list.length; n++) {cout << list.l[n] << ' ';}cout << endl; }int main() {/*-----------------------------------------說明：隨機生成數組首元素下標為 1-----------------------------------------*/// 生成隨機數組srand(unsigned(time));sqlist list;list.length = 0;cout << "請輸入生成數組的長度：";cin >> list.length; //輸入數組的長度cout << "生成的數組為：";for (int i = 1; i <=list.length; i++){ list.l[i] =(int) rand() % 90 + 10;cout << list.l[i]<<' ';}cout << endl;//-----插入排序-----//InsertSort(list,list.length);//-----選擇排序-----//SelectSort(list);//-----冒泡排序-----//BubbleSort(list);//-----雙向冒泡-----//TwowaybubbleSort(list);//-----快速排序-----//QSort(list, 1, list.length);//輸出關鍵字比較次數和關鍵字移動次數//cout << "關鍵字比較次數：" << QSort_compare_count << "\t"// << "關鍵字移動次數：" << QSort_remove_count << endl;//-----歸并排序-----//MSort(list, 1, list.length);//輸出關鍵字比較次數和關鍵字移動次數//cout << "關鍵字比較次數：" << MSort_compare_count << "\t"//<< "關鍵字移動次數：" << MSort_remove_count << endl; }

2、各種查找算法實現（返回目錄🖱）
（1） 順序查找（返回目錄🖱）：使用數組或鏈表結構。用隨機函數生成16個不重復的字母（’a’~’z’），鍵盤輸入待查找的字母，返回查找成功與否，若成功則返回該字母所在的位置（序號），并計算比較次數。

#include<iostream> #include<ctime> using namespace std;//-----順序查找----- void Search_Seq(char* s) {cout << "請輸入想尋找的字母：";char x;cin >> x; //輸入想找的字母int index = 0;int count = 0; //比較次數,初始化為0while (s[index] != '\0') {++count;if (s[index++] == x) {cout << "已找到字母 " << x << " ,它的下標為：" << index - 1 << endl;break;}}if (count == 17) {cout << "沒有找到該字母,共比較了：" << count-1 << " 次"<< endl;}else cout << "共比較了：" << count << " 次"; }int main() {/*-----------------------------------------說明：隨機生成數組首元素下標為 0-----------------------------------------*/// 生成隨機數組srand(unsigned(time));char* s=new char[17]; //字符數組for (int i = 0; i < 16; i++) s[i] = '\0';cout << "生成的數組為：";int k = 0;while (k != 16) {int flag = 0; //用于檢測是否有相同的字母出現s[k] = 'a' + (rand() % 26);for (int i = 0; i < 16; i++) {if (k != i) {if (s[k] == s[i]) flag = 1; //若flag=1，則重新加入一個字母}}if (flag == 0) ++k; //若flag=0，往數組下一個位置添加字母}for (int i = 0; i < 16; i++) cout << s[i] << " "; //打印隨機生成的字符數組s[16] = '\0'; //字符串的最后一位是'\0'cout << endl;//-----順序查找-----Search_Seq(s); }

（2） 折半查找（返回目錄🖱）：用數組實現，查找前元素先排序。計算比較次數。分別用查找成功、不成功進行測試。

#include<iostream> #include<ctime> using namespace std;//-----順序查找-----void TwowaybubbleSort(char* s) {int n = 16;int flag = 1; //檢測是否已排序完成int left = 1; //初始化待排序數組的最左端元素序號int right = 15; //初始化待排序數組的最右端元素序號int temp_right = 0; //暫存待更新待排序數組的最右端元素序號int temp_left = 0; //暫存待更新待排序數組的最左端元素序號//設置兩重循環while (n-- && flag) {flag = 0; for (int j = left; j < right; j++) {if (s[j] > s[j + 1]) {flag = 1;int temp = s[j];s[j] =s[j + 1];s[j + 1] = temp;temp_right = j;}}right = temp_right; //更新待排序數組的最右端元素序號for (int j = right; j > left; j--) {if (s[j] < s[j - 1]) {flag = 1;int temp = s[j];s[j] = s[j - 1];s[j - 1] = temp;temp_left = j;}}} } void Search_Bin(char* s) {TwowaybubbleSort(s); //先使用雙向冒泡進行排序int compare_count = 0; //記錄比較次數cout << "請輸入想尋找的字母：";char x;cin >> x; //輸入待尋找的字母int low = 0; int high = 15;int mid = 0;while (low <= high) {mid = (low + high) / 2;if (x == s[mid]) {compare_count++;cout << "已找到字母 " << x << endl;break;}else if (x < s[mid]) {compare_count++;high = mid - 1;}else {compare_count++;low = mid + 1;}}if(low>high&&x!=s[low]) cout<< "未找到該字母，總共比較了 " << compare_count << " 次" << endl;else cout << "總共比較了 " << compare_count << " 次" << endl; }int main() {/*-----------------------------------------說明：隨機生成數組首元素下標為 0-----------------------------------------*/// 生成隨機數組srand(unsigned(time));char* s = new char[17]; //字符數組for (int i = 0; i < 16; i++) s[i] = '\0';cout << "生成的數組為：";int k = 0;while (k != 16) {int flag = 0; //用于檢測是否有相同的字母出現s[k] = 'a' + (rand() % 26);for (int i = 0; i < 16; i++) {if (k != i) {if (s[k] == s[i]) flag = 1; //若flag=1，則重新加入一個字母}}if (flag == 0) ++k; //若flag=0，往數組下一個位置添加字母}for (int i = 0; i < 16; i++)cout << s[i] << " "; //打印隨機生成的字符數組s[17] = '\0'; //字符串的最后一位是'\0'cout << endl;//-----折半查找-----Search_Bin(s);}

（3）二叉查找樹（返回目錄🖱）：手工輸入10個字母，生成一棵二叉查找樹，用遞歸算法打印樹結構或分別輸出先序和中序遍歷序列以確認其結構。鍵盤輸入待查找的字母，計算比較次數。分別用查找成功、不成功進行測試。

#include<iostream> using namespace std;//二叉查找樹結構 typedef struct BSTNode {char data;BSTNode* lchild, * rchild; }BSTNode,*BSTree;//二叉排序樹的插入 void InsertBST(BSTree& T, char x) {if (!T) {BSTNode* new_tree = new BSTNode; //生成新結點new_tree->data = x;new_tree->lchild = new_tree->rchild = NULL;T = new_tree;}else if (x < T->data) InsertBST(T->lchild, x);else if (x > T->data) InsertBST(T->rchild, x); } //二叉排序樹的創建 void CreatBST(BSTree& T) {T = NULL;char x;cin >> x;int i = 0; //用于提示已經輸入了多少個字母while (x != '#') {InsertBST(T, x);cout << "這是輸入的第 " << ++i << " 個字母" << endl;cin >> x;} } //二叉樹的先序遍歷 void Preorder(BSTree T)//前序遍歷（遞歸實現） {if (T != NULL){cout << T->data << " ";Preorder(T->lchild);Preorder(T->rchild);} } //二叉樹的中序遍歷 void Mreorder(BSTree T)//前序遍歷（遞歸實現） {if (T != NULL){Mreorder(T->lchild);cout << T->data << " ";Mreorder(T->rchild);} }//-----二叉查找樹----- int compare_count = 0; //全局變量。記錄比較次數 BSTree SearchBST(BSTree T, char x) {compare_count++;if (!T|| x == T->data) {if (!T)cout << "查詢失敗,共查找了 " << compare_count << " 次\n";elsecout << "已找到字母 " << T->data << " ,共查找了 " << compare_count << " 次\n";return T;}else if (x < T->data) return SearchBST(T->lchild, x);else if (x >= T->data) return SearchBST(T->rchild, x); }int main() {//創建二叉查找樹BSTree T = new BSTNode;cout << "請輸入十個字母(輸入#結束): " << endl;CreatBST(T); cout<<"輸入完成\n";//中序遍歷二叉查找樹cout << "\n先序遍歷輸出：";Preorder(T);//中序遍歷二叉查找樹cout << "\n中序遍歷輸出(按照各字母的ASCⅡ碼大小)："; Mreorder(T);//輸入待查找字母cout << "\n請輸入想查詢的字母(如果想退出查找，請輸入$) ";char letter;cin >> letter; //查找字母while (1 && letter != '$') {SearchBST(T, letter);cout << "\n請輸入想查詢的字母(如果想退出查找，請輸入$) ";cin >> letter;} }

四、實驗過程原始數據記錄
1、 各種排序算法的實現
1） 插入排序
2） 選擇排序
3） 冒泡排序
4） 雙向冒泡排序
5） 快速排序
6） 歸并排序

2、各種查找算法實現
（1）順序查找
1） 查找成功的情況

2）查找不成功的情況

（2）折半查找
1）查找成功的情況

2）查找不成功的情況

（3） 二叉查找樹

五、實驗結果及分析
（代碼已寫注釋。）
插入排序、選擇排序、冒泡排序等實現簡單，并且在待排序的元素總量較小的時候與快速排序、歸并排序等速度相差不大，但是當待排序元素總量較大時，快速排序和二路歸并排序的優勢就非常明顯了（我嘗試了對900個元素進行排序）。所以在元素總量較小時，各種排序方法的差距不會太大，但當元素總量大時，為了提高效率，還是應該選擇實現過程較復雜的但效率高的算法。
查找算法：在順序查找、折半查找、二叉查找樹查找中算法中，順序查找是效率最低的；對于折半查找、二叉查找樹查找來說，這兩種查找算法的時間復雜度在一般情況下是相同的，但二叉查找樹是鏈式結構，插入和刪除都只需要修改指針，這是非常方便的。

總結

以上是生活随笔為你收集整理的实验四 查找和排序算法实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。