前言

這是數據結構的實驗四的題目。
為了自己能在繁雜的文件中順利、快速地找到自己熟悉的排序、查找算法代碼，故借CSDN平臺存放本人寫的代碼。另外，還請有緣看到此文章的同行們能多多指點。
非常感謝。

---

1 各種排序算法的實現

用隨機函數生成16個2位正整數（10~99），實現 插入排序、 選擇排序、 冒泡排序、 雙向冒泡、 快速排序、 二路歸并排序 等多種排序算法，輸出排序中間過程、統計關鍵字的比較次數和記錄的移動次數。

1.1 代碼

代碼說明：
各排序算法在同一個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; }

1.2 運行結果

• 插入排序
  
• 選擇排序
  
• 冒泡排序
  
• 雙向冒泡排序
  
• 快速排序
  
• 歸并排序

2 各種查找算法的實現

2.1 順序查找

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

2.1.1 代碼

#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.1.2 運行結果

• 查找成功
  
• 查找失敗
  

2.2 折半查找

用數組實現，查找前元素先排序。計算比較次數。分別用查找成功、不成功進行測試。

2.2.1 代碼

#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); }

2.2.2 運行結果

• 查找成功
  
• 查找失敗
  

2.3 二叉查找樹

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

2.3.1 代碼

#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;} }

2.3.2 運行結果

查找成功和失敗都在同一張截圖里了。

總結

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

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