用任意方法对给定的数组排序 数据结构.doc

数据结构实验报告学院：数学科学学院专业： 信息与计算科学实验名称用任意方法对给定的数组排序成绩姓名年级2011学号201110701160一、 实验目的：1熟悉并掌握各种排序方法的设计思路。2掌握在计算机上实现的各种具体排序操作。二、 实验内容1实现插入排序操作（插入排序基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的序列中的适当位置，直到全部记录插入完成为止）。2实现交换排序操作（交换排序基本思想：在待排序的序列中，找到不满足有序性的两个关键字，交换位置，以满足有序性，重复整个过程直到该序列中的所有关键字都有序为止）。3实现选择排序操作（选择排序基本思想：每一趟从待排序的记录中选出关键字最小的记录，并顺序放在已排好序的序列的最后，直到全部记录排序好为止。三、 实验步骤：采用的数据描述为：#define MAXSIZE 100/*数组的最大长度*/typedef int keytypetypedef struct keytype key;/*关键字项*/ infotype otherinfo;/*其它数据项*/redtype;typedef struct redtype rMAXSIZE+1;/*存放记录中各个数据项的数组*/ int length;/*数组长度*/ Sqlist;1对给定的数组，用直接插入排序（插入排序的一种）对它进行排序，观察数组在排序前后的变化情况。2对给定的数组，用起泡排序（交换排序的一种）对它进行排序，观察数组在排序前后的变化情况。3对给定的数组，用直接选择排序（选择排序的一种）对它进行排序，观察数组在排序前后的变化情况。四、 程序流程：（1）直接插入排序：#define MAXSIZE 100#define N 10typedef int keytype;typedef structkeytype key;redtype;typedef structredtype rMAXSIZE+1;int length;Sqlist;Sqlist insertsort(Sqlist L)/*直接插入排序函数*/ int i,j; L.length=N; for (i=2;i=L.length;+i) if (L.ri.keyL.ri-1.key) L.r0=L.ri; /*L.r0具有监视哨的作用*/ for(j=i-1;L.r0.keyL.rj.key;-j) L.rj+1=L.rj; /*记录后移*/ L.rj+1=L.r0; return L;main()/*主函数*/Sqlist L;int i; printf(please input 10 data:n);/*请求输入10个数据*/ for(i=1;i=N;i+) scanf(%d,&L.ri.key); L=insertsort(L);/*调用直接插入排序函数*/ printf(after insert sort data is:n);/*输出排序后的序列*/ for(i=1;i=N;i+) printf(%5d,L.ri.key); （2）起泡排序：#include#define MAXSIZE 100#define N 10typedef int keytype;typedef structkeytype key;redtype;typedef structredtype rMAXSIZE+1;int length;Sqlist;Sqlist bubblesort(Sqlist L)/*起泡排序函数*/int i,j; redtype temp; L.length=N; for (i=1;i=L.length-1;+i) for(j=1;j=L.length-i;+j) if (L.rj+1.keyL.rj.key) temp=L.rj; L.rj=L.rj+1; L.rj+1=temp; /*数据交换*/return L;main()/*主函数*/Sqlist L; int i;printf(please input 10 data:n);/*请求输入10个数据*/for(i=1;i=N;i+) scanf(%d,&L.ri.key);L=bubblesort(L);/*调用起泡排序函数*/printf(after bubblesort data is:n);/*输出排序后的序列*/for(i=1;i=N;i+) printf(%5d,L.ri.key);（3）直接选择排序:#define MAXSIZE 100#define N 10typedef int keytype;typedef structkeytype key;redtype;typedef structredtype rMAXSIZE+1;int length;Sqlist;Sqlist selectsort(Sqlist L)/*直接选择排序函数*/ int i,j,k; redtype temp; L.length=N; for(i=1;i=L.length-1;+i) k=i; for(j=i+1;j=L.length;+j) if (L.rj.keyL.rk.key) k=j; /* k始终“指向”关键字最小的记录*/ if (k!=i) temp=L.ri; L.ri=L.rk; L.rk=temp; return L;main()/*主函数*/Sqlist L;int i; printf(please input 10 data:n);/*请求输入10个数据*/ for(i=1;i=N;i+) scanf(%d,&L.ri.key);/*调用直接选择排序函数*/ L=selectsort(L); printf(after selectsort