数据结构实验(共4页).doc

《数据结构实验(共4页).doc》由会员分享，可在线阅读，更多相关《数据结构实验(共4页).doc（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上数据结构实验报告4（一）题目1. 按下述原则编写快排的非递归算法：(1) 一趟排序之后，若子序列已有序(无交换)，则不参加排序，否则先对长度较短的子序列进行排序，且将另一子序列的上、下界入栈保存；(2) 若待排记录数right时返回true，否则返回falsevoid sort(int *arr, int left, int right)给三个或三个以下的序列排序arr为等排序的数组；left为下界；right为下界。void qsort(int *arr, int left, int right)快速排序同上（四）源码#include #define MAX_SEQ

2、 100using namespace std;typedef struct _stackint left;/lowerbound int right;/upperboundstruct _stack *next;qstack; /to store the child sequences left and rightvoid sort(int *arr, int left, int right) /sort child sequence less than 3for(int i = left; i = right; i+)int k = i;for(int j = i+1; j arrj)k

3、= j;if(k != i)int t;t = arrk;arrk = arri;arri = t;bool sorted(int *arr, int left, int right)for(int i = left; i arri+1)return false;return true;void qsort(int *arr, int left, int right)qstack *head;head = new qstack;head-left = left;head-right = right;head-next = NULL;qstack *p;while(head != NULL)if

4、(head-right - head-left left, head-right);p = head;head = head-next;delete p; else /generally, separate the sequenceint ml = head-left, mr = head-right;int mm = ml;int k = arrmm;/find the position, the key part of quick sortwhile(ml = k)mr-;elsearrmm = arrmr;mm = mr;if(mm = mr)if(arrml k)arrmm = arr

5、ml;mm = ml;elseml+;arrmm = k;bool l = sorted(arr, head-left, mm-1);bool r = sorted(arr, mm+1, head-right);if(!l & r)/left child sequence isnt sorted, then change the tophead-right = mm - 1;else if(l & !r)/right child sequence isnt sorted, then change the tophead-left = mm + 1;else if(!l & !r)/both s

6、equences arent sorted, then change the top one /to the longer sequence, push the shorter one to the stackp = new qstack;if(mm - head-left head-right - mm)p-left = mm + 1;p-right = head-right;head-right = mm - 1;elsep-left = head-left;p-right = mm - 1;head-left = mm + 1;p-next = head;head = p;else /b

7、oth sequences are sorted, then pophead = head-next;int main()int arrayMAX_SEQ;int n;while(cout n)cout input n numbersn;for(int i = 0; i arrayi;qsort(array, 0, n-1);cout after quick sorted:n;for(int i = 0; i n; i+)cout arrayi ;cout endl;return 0;（五）实验结果（六）心得体会本实验通过对栈的使用，实现了快速排序的非递归算法，加深了对快速排序与递归的理解，更熟悉了栈的操作。而在实验中犯的大部分错误都在于栈的使用过程中，对于栈的使用熟练度还需要加强。专心-专注-专业