数据结构课程设计——排序与查找

1、北京信息科技大学课程设计报告课程名称 数据结构课程设计 题 目 排序与查找 指导教师 赵 庆 聪 设计起止日期 设计地点 系 别 信息管理学院 专 业 _信息管理与信息系统_姓名/学号_鲁丹2012012108_1. 课程实践目的：通过本实践使学生对各类排序算法有更深入的了解，在实际应用中学会使用排序算法解决具体问题。2. 课程实践内容：a) 随机产生20个0100之间的整数，允许有重复b) 分别利用直接插入排序、直接选择排序、快速排序、双向起泡排序对这20个数进行排序（递增递减均可），并统计在各种排序方法中关键字的比较次数，最后输出各类排序方法的排序结果及关键字的比较次数。提示：双向起泡排序

2、是对标准起泡排序算法的改进，该方法第一次自上而下进行“起泡”，使最大元素“下沉”到底，第二次自下而上进行“起泡”，使最小元素“上浮”到顶，之后又重复上述过程，每趟起泡后都会相应缩小下一趟的起泡排序区间，直至排序完成。起泡期间可以通过对某趟“起泡”的“最后交换位置”进行记忆，以尽可能快地缩短下一趟的“起泡”区间。c) 用折半查找法在前面的已排好序的数据表上查找，是否有此数，如有，输出其序号。如没有，在屏幕给出提示信息。3. 实践步骤：#include<stdio.h>#include<stdlib.h>#include<time.h>#define N 100

3、#define OK 1#define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef structElemType *elem;int length; int listsize; List;Status InitList(List &L)L.elem=(ElemType * ) malloc(LIST_INIT_SIZE * sizeof(Ele

4、mType); L.length = 0; L.listsize=LIST_INIT_SIZE; return OK;/InitListvoid Create(List &L, int n) int i; srand(time(NULL); for(i=0;i<n;i+) L.elemi=rand()%N; L.length+; printf("%d ",L.elemi); printf("n");int InsertSort(List L)int i,j,t,m;m=0;for(i=1;i<L.length;i+)t=L.elemi

5、;j=i-1;if(t>=L.elemj) m+;else m+;while(j>=0)&&(t<L.elemj)L.elemj+1=L.elemj;j-;L.elemj+1=t;return m;int SelectSort(List L)int i,j,k,min,t=0;for(i=0;i<L.length;i+)min=i;for(j=i+1;j<L.length;j+)if(L.elemj<L.elemmin)min=j;t+;else t+;if(min!=i)k=L.elemi;L.elemi=L.elemmin;L.elemm

6、in=k;return t;int QuickSort(List L,int s,int t) int i=s,j=t,count4=0; if(s<t) L.elem0=L.elems; do while(j>i&&L.elemj>=L.elem0)j-;count4+; if(i<j) L.elemi=L.elemj; i+; while(i<j&&L.elemi<=L.elem0)i+;count4+; if(i<j) L.elemj=L.elemi; j-; while(i<j); L.elemi=L.el

7、em0; QuickSort(L,s,j-1); QuickSort(L,j+1,t); return count4; int BubbleSort(List L)int flag,i,j;int t=0;flag=1;while(flag=1)flag=0;i=0;for(j=L.length-i;j>i;j-)if(L.elemj-1>L.elemj)flag=1;int m;m=L.elemj;L.elemj=L.elemj-1;L.elemj-1=m;t+;else t+;return t; void display(List L)int i;for(i=0;i<L.

8、length;i+) printf("%d ",L.elemi); printf("n");void main() List L;int low,high,a,b,c,d; InitList(L);printf("请将随机产生的0-100间的20个数输出:n");Create(L,20);printf("n直接插入法排序输出的顺序表为:n"); a=InsertSort(L); display(L); printf("此排序法关键字比较的次数为:%dn",a); printf("n直接

9、选择法排序输出的顺序表为:n");b=SelectSort(L);display(L);printf("此排序法关键字比较的次数为:%dn",b); printf("n快速排序输出的顺序表为:n");c=QuickSort(L,1,20);display(L);printf("此排序法关键字比较的次数为:%dn",c);printf("n双向起泡法排序输出的顺序表为:n");d=BubbleSort(L);display(L);printf("此排序法关键字比较的次数为:%dn",d)

10、;1. #include "stdio.h"   2. #include "stdlib.h"   3. #include "string.h"   4. #include "time.h"   5. #include "limits.h"   6. #define MAXITEM

11、0;1000   7. typedef int KeyType,ElemType;   8. int count1=0,count2=0,count3=0,count4=0,count5=0,count6=0;   9. int swap1=0,swap2=0,swap3=0,swap4=0,swap5=0,swap6=0;   10. typedef struct rec   11.

12、   12.     KeyType key;   13.     ElemType data;   14. sqlistMAXITEM;   15.    16. void gennum(sqlist r,sqlist t,int n)   17.   &#

13、160;18.     int i;   19.     srand(unsigned)time(NULL);   20.     for(i=1;i<=n;i+)   21.        ti.key=rand()%100;   22.   

14、0;     ri.key=ti.key;   23.        24.    25.    26. void ini(sqlist r,sqlist t,int n)   27.    28.     int i; 

15、0; 29.     for(i=1;i<=n;i+)   30.         ri.key=ti.key;   31.    32.    33. void BubbleSort(sqlist r,int n)/起泡法r1rn   34.    3

16、5.     int i,j;   36.     struct rec w;   37.     for(i=1;i<=n-1;i+)   38.        for(j=n;j>=i+1;j-)   39.    

17、;       40.           if(rj.key<rj-1.key)   41.              42.            &

18、#160; w=rj;   43.              rj=rj-1;   44.              rj-1=w;   45.         

19、;     swap1+;   46.              47.           count1+;   48.           49. 

20、0;  50.    51.    52.    53. void InsertSort(sqlist r,int n)/直接插入排序r1rn   54.    55.     int i,j;   56.     for(i=2;i<=n;i+)  &

21、#160;57.        58.         count2+;   59.         r0=ri;   60.         j=i-1;   61.   

22、60;     while(r0.key<rj.key)   62.            63.             rj+1=rj;   64.         &#

23、160;   j-;   65.             count2+;   66.             swap2+;   67.         &#

24、160;  68.         rj+1=r0;   69.         swap2+;   70.        71.    72.    73. void  SelectSort(sqlist&#

25、160;r,int n)/简单选择排序r1rn   74.    75.     int i,j,k;   76.     struct rec temp;   77.     for(i=1;i<=n-1;i+)   78.     

26、0;  79.         k=i;   80.         for(j=i+1;j<=n;j+)   81.             if(rj.key<rk.key)k=j;count3+;  &

27、#160;82.         if(i!=k)   83.            84.             temp=ri;   85.        

28、;     ri=rk;   86.             rk=temp;   87.             swap3+;   88.       &#

29、160;    89.        90.    91.    92. void QuickSort(sqlist r,int s,int t)/快速排序rsrt,r0空出   93.    94.     int i=s,j=t;   95. &

30、#160;   if(s<t)   96.        97.         r0=rs;swap4+;   98.         do   99.        &#

31、160;   100.             while(j>i&&rj.key>=r0.key)j-;count4+;   101.             if(i<j)   102.    

32、0;           103.                 ri=rj;   104.                 i+;

33、60;  105.                 swap4+;   106.                107.           

34、;  while(i<j&&ri.key<=r0.key)i+;count4+;   108.             if(i<j)   109.                110.   &

35、#160;             rj=ri;   111.                 j-;   112.            

36、     swap4+;   113.                114.         while(i<j);   115.         ri=r0; 

37、  116.         swap4+;   117.         QuickSort(r,s,j-1);   118.         QuickSort(r,j+1,t);   119.     &

38、#160;  120.    121.    122. void ShellSort(sqlist r,int n)/希尔排序r1rn   123.    124.     int i,j,gap;   125.     struct rec x;   126

39、.     gap=n/2;   127.     while(gap>0)   128.        129.         for(i=gap+1;i<=n;i+)   130.       

40、0;    131.    132.             j=i-gap;   133.             while(j>0)   134.       

41、;        if(rj.key>rj+gap.key)   135.                  136.                 x

42、=rj;   137.                 rj=rj+gap;   138.                 rj+gap=x;   139.   

43、0;             j=j-gap;   140.                 count5+;   141.           &#

44、160;     swap5+;   142.                  143.               else   144.    

45、              145.                 j=0;count5+;   146.              &#

46、160;   147.            148.         gap=gap/2;   149.        150.    151.    152. void sift(sqlist r

47、,int l,int m)   153.    154.     int i,j;   155.     struct rec x;   156.     i=l;   157.     j=2*i;   15

48、8.     x=ri;   159.     while(j<=m)   160.        161.         if(j<m&&rj.key<rj+1.key)j+;count6+;   162.    

49、;     if(x.key<rj.key)   163.            164.             ri=rj;   165.          &

50、#160;  i=j;   166.             j=2*i;   167.             count6+;   168.         

51、0;   swap6+;   169.            170.         else j=m+1;count6+;   171.        172.     ri=x; &#

52、160; 173.    174. void HeapSort(sqlist r,int n)/堆排序r1rn   175.    176.     int i;   177.     struct rec m;   178.     for(i=n/2;i&

53、gt;=1;i-)sift(r,i,n);   179.        for(i=n;i>=2;i-)   180.           181.           m=ri;   182.    &

54、#160;      ri=r1;   183.           r1=m;   184.           swap6+;   185.         

55、0; sift(r,1,i-1);   186.           187.    188.    189. void main()   190.    191.        192.     int k,

56、n,a;   193.     sqlist r,t;   194.     printf("                 *n");   195.     printf("&

57、#160;                *                                 

58、    *n");   196.     printf("                 *      * 内部排序算法的性能分析 *     *n");&#

59、160;  197.     printf("                 *                       &

60、#160;             *n");   198.     printf("                 *nn");   199.   

61、; 200.     printf("-*-*-n");   201.     printf("*是否执行程序*n");   202.     printf("(是) 按 1 键,   (否) 按 0 键n");   203. &

62、#160;   printf(" 按键为：");   204.     scanf("%d",&a);   205.     printf("-*-*-n");   206.    207.     while(a=1)  

63、0;208.     printf("*请输入要排序的数据的个数：");   209.      scanf("%d",&n);   210.        211.      gennum(r,t,n);   212.   

64、60;  printf("n");   213.    214.      printf("*随机产生的最初顺序是:n");   215.      for(k=1;k<=n;k+)   216.        printf("%3d

65、",tk.key);   217.         if(k%20=0)   218.             printf("n");   219.        220.    

66、;  printf("n");   221.      BubbleSort(r,n);   222.      printf("n*排序之后的顺序是:n");   223.      for(k=1;k<=n;k+)   224.   

67、60;    printf("%3d",rk.key);   225.         if(k%20=0)   226.             printf("n");   227.    

68、60;   228.      printf("nn");   229.      printf("-*分析结果*-nn");   230.      printf("            

69、;                  *起泡排序*n");   231.      printf("                  &#

70、160;  比较的次数是: %d,移动的次数是: %dnn",count1,swap1);   232.        233.      ini(r,t,n);   234.      InsertSort(r,n);   235.     

71、60;printf("                              *直接插入*n");   236.      printf("    

72、;                 比较的次数是: %d,移动的次数是: %dnn",count2,swap2);   237.        238.      ini(r,t,n);   239.  

73、60;   SelectSort(r, n);   240.      printf("                            *简单选择排序*n"); 

74、  241.      printf("                     比较的次数是: %d,移动的次数是: %dnn",count3,swap3);   242.        243.      ini(r,t,n);   244.      QuickSort(r,1,n);   245.      printf("