第八次数据结构上机实验报告.docx

1、第八次数据结构上机实验报告一、调试成功程序及说明1、题目：2实现快速排序算法 算法思想：1.设置两个变量i、j，排序开始的时候：i=0，j=N-1；2.以第一个数组元素作为关键数据，赋值给key，即key=A0；3.从j开始向前搜索，即由后开始向前搜索(j-)，找到第一个小于key的值Aj，将Aj和Ai互换；4.从i开始向后搜索，即由前开始向后搜索(i+)，找到第一个大于key的Ai，将Ai和Aj互换；5.重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中Aj不小于key,4中Ai不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，

2、进行交换的时候i， j指针位置不变。另外，i=j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。源程序：#include #include void swap(int *x,int *y) int temp; temp = *x; *x = *y; *y = temp;int choose_pivot(int i,int j ) return(i+j) /2);void quicksort(int list,int m,int n) int key,i,j,k; if( m n) k = choose_pivot(m,n); swap(&listm,&listk); key = li

3、stm; i = m+1; j = n; while(i = j) while(i = n) & (listi = m) & (listj key) j-; if( i j) swap(&listi,&listj); / 交换两个元素的位置 swap(&listm,&listj); / 递归地对较小的数据序列进行排序 quicksort(list,m,j-1); quicksort(list,j+1,n); void printlist(int list,int n) int i; for(i=0;in;i+) printf(%dt,listi);void main() const int M

4、AX_ELEMENTS = 10; int listMAX_ELEMENTS; int i = 0; printf(请输入十位排序的数字，按enter终止输入：); for(i = 0; i MAX_ELEMENTS; i+ ) scanf(%d,&listi); printf(排序前的序列:n); printlist(list,MAX_ELEMENTS); / sort the list using quicksort quicksort(list,0,MAX_ELEMENTS-1); / print the result printf(使用快速排序算法进行排序之后的序列:n); print

5、list(list,MAX_ELEMENTS);运行结果：2、题目：3实现堆排序算法；算法思想：1. 先将初始文件R1.n建成一个大根堆，此堆为初始的无序区2. 再将关键字最大的记录R1（即堆顶）和无序区的最后一个记录Rn交换，由此得到新的无序区R1.n-1和有序区Rn，且满足R1.n-1.keysRn.key3.由于交换后新的根R1可能违反堆性质，故应将当前无序区R1.n-1调整为堆。然后再次将R1.n-1中关键字最大的记录R1和该区间的最后一个记录Rn-1交换，由此得到新的无序区R1.n-2和有序区Rn-1.n，且仍满足关系R1.n-2.keysRn-1.n.keys，同样要将R1.n-2

6、调整为堆。源程序：#include #define SUCCESS 0#define ERROR -1/* * 调整堆 * index 是数组下标，从0开始 */int HeapSort_adjust(int * piBuffer, const unsigned int uiSize, const unsigned int uiIndex) int * piTmp = piBuffer; unsigned int i = uiIndex; unsigned int uiChild = i; int iTmpValue = 0; if (NULL = piTmp) | (uiSize = uiS

7、ize) /* 入参判断 */ return ERROR; for (i = uiIndex; i uiSize ; i = uiChild) uiChild = 2 * i + 1; /* 找到子结点中较大的 */ if (uiChild piBufferuiChild) uiChild+; /* 判断较大的子结点是否比父结点大 */ if (uiChild piBufferi) iTmpValue = piBufferi; piBufferi = piBufferuiChild; piBufferuiChild = iTmpValue; else /* 如果左右子结点都比父结点小，那么可以

8、肯定这是一个大根堆了，可以结束循环了 */ break; return SUCCESS;/* * 堆排序，这里使用大根堆，按照从小到大排序 * uiSize 是数组大小，从1开始 */int HeapSort(int * piBuffer, const unsigned int uiSize) int * piTmp = piBuffer; int i = (uiSize - 2)/2; int iTmpValue = 0; if (NULL = piTmp) | (uiSize = 0; i-) /* 数组下标从0开始，所以i的初始值为(uiSize - 2)/2 */ HeapSort_a

9、djust(piBuffer, uiSize, i); /* 把第0个元素与最后一个元素对调，重新调整堆 */ for (i = uiSize - 1; i 0; i-) iTmpValue = piBufferi; piBufferi = piBuffer0; piBuffer0 = iTmpValue; HeapSort_adjust(piBuffer, i, 0); /* 每次只需要调整前i个元素即可 */ return SUCCESS;/* * 打印数组内容 */int HeapSort_print(int * piBuffer, const unsigned int uiSize)

10、int * piTmp = piBuffer; int i = 0; if (NULL = piTmp) /* 入参判断 */ return ERROR; /* 打印数组内容，中间以逗号隔开 */ for (i = 0; i uiSize; i+) if (0 = i) printf(%d, piTmpi); else printf( %d, piTmpi); printf(n); return SUCCESS;int main(int argc, char * argv) int i,array10; printf(输入用于堆排序的十个数:n); for(i=0;i10;i+) scanf(%d,&arrayi); printf(排序后为:n); HeapSort(array, sizeof(array)/sizeof(array0); /* 堆排序 */ HeapSort_print(array, sizeof(array)/sizeof(array0); /* 第二个参数是数组中元素个数，所以不能简单的用sizeof */ return SUCCESS;运行结果：