《数据结构》课程设计_排序算法比较以及算术表达式求值

1、数据结构课程设计排序算法比较、表达式求值 XXXXX大学数据结构课程设计报告排序算法比较算术表达式求值 班 级： 学 号： 姓 名： 指导老师： 目 录一 课程设计1排序算法比较1、 需求分析2、 程序的主要功能3、 程序运行平台4、 数据结构5、 算法及时间复杂度6、 测试用例7、 程序源代码二 课程设计2算术表达式求值1、 需求分析2、 程序的主要功能3、 程序运行平台4、 数据结构5、 算法及时间复杂度6、 测试用例7、 程序源代码三 感想体会与总结排序算法比较一、需求分析利用随机函数产生N个随机整数（N = 500，1000，1500，2000，2500，,30000），利用直接插入排

2、序、折半插入排序，起泡排序、快速排序、选择排序、堆排序，基数排序七种排序方法（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的时间（统计为图表坐标形式）。二、程序的主要功能1.用户输入任意个数，产生相应的随机数2.用户可以自己选择排序方式（直接插入排序、折半插入排序、起泡排序、快速排序、选择排序、堆排序、基数排序）的一种3.程序给出原始数据、排序后从小到大的数据，并给出排序所用的时间。三、程序运行平台Visual C+ 6.0版本四、数据结构本程序的数据结构为线形表，线性顺序表、线性链表。1、结构体： typedef struct int *r; /r指向线形表的

3、第一个结点。 r0闲置，不同的算法有不同的用处，如用作哨兵等。 int length; /顺序表的总长度Sqlist;2、空线性表Status InitSqlist(Sqlist &L)L.r=(int *)malloc(MAXSIZE*sizeof(int); /分配存储空间if(!L.r) printf("存储分配失败！");exit(0); /存储分配失败L.length=0;/初始长度为0return OK;五、算法及时间复杂度（一）各个排序是算法思想：（1）直接插入排序：将一个记录插入到已排好的有序表中，从而得到一个新的，记录数增加1的有序表。（2）折半插

4、入排序：插入排序的基本插入是在一个有序表中进行查找和插入，这个查找可利用折半查找来实现，即为折半插入排序。（3）起泡排序：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直到第N-1和第N个记录的关键字进行过比较为止。上述为第一趟排序，其结果使得关键字的最大纪录被安排到最后一个记录的位置上。然后进行第二趟起泡排序，对前N-1个记录进行同样操作。一共要进行N-1趟起泡排序。（4）快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序

5、，已达到整个序列有序。（5）选择排序：通过N-I次关键字间的比较，从N-I+1个记录中选出关键字最小的记录，并和第I（1<=I<=N）个记录交换。（6）堆排序：在堆排序的算法中先建一个大顶堆，既先选得一个关键字作为最大的记录并与序列中最后一个记录交换，然后对序列中前N-1记录进行选择，重新将它调整成一个大顶堆，如此反复直到排序结束。（7）基数排序：按最低位优先法先对低位关键字进行排序，直到对最高位关键字排序为止，经过若干次分配和收集来实现排序（二）时间复杂度分析排序算法 最差时间时间复杂度 是否稳定？插入排序 O(n2)O(n2) 稳定 冒泡排序O(n2)O(n2) 稳定 快速排序

6、O(n2)O(n*log2n) 不稳定 选择排序O(n2)O(n2) 稳定 堆排序O(n*log2n) O(n*log2n) 不稳定 基数排序O(n*log2n)O(n2)稳定10000个数据的时间比较：算法名称用时直接插入排序0.25折半插入排序0.219起泡排序0.704快速排序0.016选择排序0.39堆排序0.0001基数排序0.016六、测试用例1、首先选择需要排序的数字个数，比如输入5000。2、系统显示出随机产生的随机数。 用户选择排序方式，比如选择1.直接插入排序3、 系统将随机数排序后整齐的显示出来。4、 用户可以选择继续排序或者退出系统。七、程序源代码/*第六题：排序算法比

7、较设计要求：利用随机函数产生N个随机整数（N = 500，1000，1500，2000，2500，,30000），利用直接插入排序、折半插入排序，起泡排序、快速排序、|选择排序、堆排序，基数排序七种排序方法（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的时间（统计为图表坐标形式）。*/#include "stdio.h"#include "stdlib.h"#include "time.h"/计时#define ERROR 0#define OK 1#define OVERFLOW -2#define

8、MAXSIZE 100000 /用户自己规定排序的数字的长度typedef int Status;typedef struct int *r; / r0闲置 int length; /顺序表的总长度Sqlist;/构造一个空线性表Status InitSqlist(Sqlist &L)L.r=(int *)malloc(MAXSIZE*sizeof(int); /分配存储空间if(!L.r) printf("存储分配失败！");exit(0); /存储分配失败L.length=0;/初始长度为0return OK;/输入随机数并显示在界面上Status ScanfS

9、qlist(int &N,Sqlist &L)int i;printf("请输入要排序的元素个数N: ");scanf("%d",&N);for(i=1;i<=N;i+)L.ri=rand(); /随机产生样本整数printf("nn");printf(" 随机产生了%d个随机数，它们是：n",N);for(i=1;i<=N;i+)printf("%7.2d ",L.ri);printf("n");L.length=N; /存储线性表的长度

10、return OK;/输出排序之后的数据Status PrintfSqlist(int N,Sqlist L)int i;printf("数据个数：");/输出数据个数printf("%dn",L.length);printf("排序后的数据：(从左向右依次增大)n");/输出数据for(i=1;i<=N;i+)printf("%7.2d ",L.ri);printf("n"); return OK;/*/ 直接插入排序/*Status InsertSort(Sqlist &L)/

11、参考书P265算法10.1int i,j;if(L.length=0)printf("要排序的数据为空！");return ERROR;for(i=2;i<=L.length;i+)if(L.ri<L.ri-1) /将L.ri插入有序子表L.r0=L.ri; /复制为监视哨L.ri=L.ri-1; for(j=i-2;L.r0<L.rj;j-)L.rj+1=L.rj; /记录后移L.rj+1=L.r0; /插入到正确位置return OK;/*/ 折半插入排序/*Status BInsertSort(Sqlist &L) /参考书P267算法10.

12、2int i,j,mid,low,high;if(L.length=0)printf("要排序的数据为空！");return ERROR;for(i=2;i<=L.length;i+)L.r0=L.ri; /将L.ri暂存在L.r0low=1;high=i-1;while(low<=high) /在rlow.high中折半查找有序插入的位置mid=(low+high)/2;if(L.r0<L.rmid) /插入点在低半区 high=mid-1;else low=mid+1; /插入点在高半区/whilefor(j=i-1;j>=high+1;j-)

13、/插入点后的数据后移L.rj+1=L.rj; L.rhigh+1=L.r0; /将数据插入/forreturn OK;/* 希尔排序*/ /参考书P272算法10.4及10.5/*Status ShellInsert(Sqlist &L,int dk)/希尔插入排序 int i,j;/前后位置的增量是dkfor(i=dk+1;i<=L.length;i+)/r0只是暂存单元，不是哨兵，if(L.ri<L.ri-dk)/将L.ri插入有序增量子表L.r0=L.ri;/暂存L.r0for(j=i-dk;j>0 && L.r0<L.rj;j-=dk)L

14、.rj+dk=L.rj;/记录后移,查找插入位置L.rj+dk=L.r0;/插入return OK;Status ShellSort(Sqlist &L,int dlta5,int t) /希尔排序 int i;if(L.length=0)printf("要排序的数据为空！");return ERROR;for(i=0;i<t;i+)ShellInsert(L,dltai);/一趟增量为dltak的插入排序return OK;*/*/ 起泡排序/*Status BubbleSort(Sqlist &L)int i,j,t;if(L.length=0)p

15、rintf("要排序的数据为空！");return ERROR;for(i=1;i<=L.length-1;i+)for(j=1;j<=L.length-i;j+)if(L.rj>L.rj+1) /前面的数据>后面数据时t=L.rj+1;L.rj+1=L.rj;L.rj=t; /将元素交换return OK;/*/ 快速排序/*int Partition(Sqlist &L, int low, int high) /交换顺序表中子表L.rlow.high的记录，使得枢轴记录到位，并返回其所在位置，此时在它之前（后）的记录均不大于它int pi

16、votkey; /记录关键字L.r0=L.rlow; /用子表的第一个纪录作枢轴纪录 pivotkey=L.rlow; /用枢轴纪录关键字 while (low<high) while(low<high && L.rhigh>=pivotkey) high-;L.rlow= L.rhigh; /将比枢轴记录小的记录移到低端while(low<high && L.rlow<=pivotkey) low+;L.rhigh=L.rlow; /将比枢轴记录大的数移到高端 L.rlow=L.r0; /枢轴记录到位 return low;/Pa

17、rtition函数void Qsort (Sqlist &L,int low, int high) int pivotloc;if (low<high) /长度大于1，可以进行 pivotloc=Partition(L, low ,high);Qsort(L,low,pivotloc-1); /对低子表递归排序，pivotloc是枢轴位置Qsort(L,pivotloc+1,high); /对高子表递归排序/Qsort函数Status QuickSort (Sqlist &L) if(L.length=0)printf("要排序的数据为空！");ret

18、urn ERROR;Qsort(L,1,L.length);return OK;/QuickSort/*/ 选择排序/*Status ChooseSort(Sqlist &L)int i,j,k,t;if(L.length=0)printf("没有数据！");return ERROR;for(i=1;i<=L.length;i+) /排序的趟数k=i;for(j=i+1;j<=L.length;j+) /比较第i个元素以及其后的数据中最小的 if(L.rj<L.rk)k=j;if(i!=j) /将最小数据赋值给L.rit=L.ri;L.ri=L.r

19、k;L.rk=t;return OK;/*/ 堆排序/*Status HeapAdjust(Sqlist &L,int s,int m) /调整L.rs的关键字,使L.rsm成大顶堆int i;L.r0=L.rs;for(i=2*s;i+1<=m;i*=2) /沿数据较大的孩子结点向下筛选if(i<m && L.ri<L.ri+1) /i为数据较大的记录下标i+;if(L.r0>=L.ri) /L.r0插入在S位置上break;L.rs=L.ri;s=i;L.rs=L.r0; /插入新数据 return OK;Status HeapSort(Sq

20、list &L) /堆排序int i,t;if(L.length=0)printf("没有数据！");return ERROR;for(i=L.length/2;i>0;i-)HeapAdjust(L,i,L.length);for(i=L.length;i>1;i-)t=L.r1; /将堆顶记录和当前未经排序的子序列L.r1.i中最后一个记录互换L.r1=L.ri;L.ri=t;HeapAdjust(L,1,i-1); /将L.r1.i-1重新调整为大顶堆return OK;/*/ 基数排序/*typedef struct node int key;

21、node *next; RecType; Status RadixSort(Sqlist L) int t,i,j,k,d,n=1,m; RecType *p,*s,*q,*head10,*tail10; /定义各链队的首尾指针 for(i=1;i<=L.length;i+) /将顺序表转化为链表 s=(RecType*)malloc(sizeof(RecType); s->key=L.ri; if(i=1) /当为第一个元素时 q=s; p=s; t+; else q->next=s; /将链表连接起来q=s; t+; q->next=NULL; d=1;while(

22、n>0) /将每个元素分配至各个链队for(j=0;j<10;j+) /初始化各链队首、尾指针 headj = NULL;tailj = NULL; while(p!=NULL) /对于原链表中的每个结点循环 k=p->key/d; k=k%10; if(headk=NULL) /进行分配 headk=p; tailk=p; else tailk->next=p; tailk=p; p=p->next; /取下一个待排序的元素 p=NULL; /用于收集第一个元素时的判断for(j=0;j<10;j+) /对每一个链队循环， 搜集每一个元素 if(headj

23、!=NULL) /进行搜集 if(p=NULL) p=headj; q=tailj; else q->next=headj; q=tailj; q->next=NULL; /最后一个结点的next置为空 d=d*10; n=0;m=1;while(m<=L.length) /判断当L中的元素都除d后是不是都为零了if(L.rm/d)!=0)n+;m+;elsem+; i=1; while(p!=NULL) /将链表转换为顺序表 L.ri=p->key; i+; p=p->next;return OK;/*/ 主函数/*void main()Sqlist L;Sql

24、ist L0;InitSqlist(L); /初始化LInitSqlist(L0); int m,i; char choice='z'clock_t start, finish; /定义clock_t用于计时double duration; /向L中输入元素printf("n n");printf(" n");printf(" 算法排序比较系统 n");printf(" n");printf(" n"); printf(" 以下是各个排序算法的代号：nn");

25、printf(" 1、直接插入排序 n");printf(" 2、折半插入排序 n");printf(" 3、起泡排序 n");printf(" 4、快速排序n");printf(" 5、选择排序n");printf(" 6、堆排序n");printf(" 7、基数排序n"); printf(" 8、退出该系统nn");ScanfSqlist(m,L0);printf("n");printf(" 1、直接插

26、入排序 n");printf(" 2、折半插入排序 n");printf(" 3、起泡排序 n");printf(" 4、快速排序n");printf(" 5、选择排序n");printf(" 6、堆排序n");printf(" 7、基数排序n"); printf(" 8、退出该系统nn");printf("n请选择排序的方式,数字1-7: ");scanf("%d",&choice); /选择排序

27、方式赋值choice，用于后面的函数选择while(choice<1|choice>8)printf("输入方式有误。n请输入1-7选择排序方式，或者选择8退出系统");scanf("%d",&choice);while(choice!=8)for(i=1;i<=L0.length;i+)L.ri=L0.ri;L.length=L0.length;switch(choice)case 1:/直接插入排序start = clock(); InsertSort(L);finish = clock();break;case 2:/折半

28、插入排序start = clock();BInsertSort(L); finish = clock(); break;case 3:/起泡排序start = clock();BubbleSort(L);finish = clock(); break;case 4:/快速排序start = clock();QuickSort(L); finish = clock(); break;case 5:/选择排序start = clock();ChooseSort(L);finish = clock(); break;case 6:/堆排序start = clock();HeapSort(L);fin

29、ish = clock(); break;case 7:/基数排序start = clock();RadixSort(L);finish = clock(); break;case 8:/直接退出break;PrintfSqlist(m,L); /输出数据和L的长度duration = (double)(finish - start) / CLOCKS_PER_SEC; /输出算术时间printf("n本次排序运算所用的时间是：%lf secondsn",duration); printf(" 本次排序结束。n");printf(" _n&qu

30、ot;); printf(" 继续本系统吗？nn"); printf(" 以下是各个排序算法的代号：n"); printf(" 1、直接插入排序n"); printf(" 2、折半插入排序n"); printf(" 3、起泡排序n"); printf(" 4、快速排序n"); printf(" 5、选择排序n"); printf(" 6、堆排序n"); printf(" 7、基数排序n"); printf("

31、; 8、退出该系统n");printf("n请请输入1-7选择排序方式，或者选择8退出系统:");scanf("%d",&choice);while(choice<1|choice>8)printf("输入方式有误。n请输入1-7选择排序方式，或者选择8退出系统");scanf("%d",&choice);算术表达式求值一、需求分析一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等

32、四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。二、程序的主要功能（1） 从键盘读入一个合法的算术表达式，输出正确的结果。（2） 显示输入序列和栈的变化过程。三、程序运行平台Visual C+ 6.0版本四、数据结构本程序的数据结构为栈。（1）运算符栈部分：struct SqStack /定义栈 char *base; /栈底指针 char *top; /栈顶指针 int stacksize; /栈的长度;int InitStack (SqStack &s) /建

33、立一个空栈S if (!(s.base = (char *)malloc(50 * sizeof(char) exit(0); s.top=s.base; s.stacksize=50; return OK; char GetTop(SqStack s,char &e) /运算符取栈顶元素 if (s.top=s.base) /栈为空的时候返回ERROR printf("运算符栈为空!n"); return ERROR; else e=*(s.top-1); /栈不为空的时候用e做返回值，返回S的栈顶元素，并返回OK return OK; int Push(SqSt

34、ack &s,char e) /运算符入栈 if (s.top-s.base >= s.stacksize) printf("运算符栈满!n"); s.base=(char*)realloc (s.base,(s.stacksize+5)*sizeof(char) ); /栈满的时候，追加5个存储空间 if(!s.base) exit (OVERFLOW); s.top=s.base+s.stacksize; s.stacksize+=5;*(s.top)+=e; /把e入栈return OK; int Pop(SqStack &s,char &

35、;e) /运算符出栈if (s.top=s.base) /栈为空栈的时候，返回ERROR printf("运算符栈为空!n"); return ERROR; elsee=*-s.top; /栈不为空的时候用e做返回值，删除S的栈顶元素，并返回OKreturn OK; int StackTraverse(SqStack &s) /运算符栈的遍历 char *t;t=s.base ;if (s.top=s.base) printf("运算符栈为空!n"); /栈为空栈的时候返回ERROR return ERROR;while(t!=s.top) pr

36、intf(" %c",*t); /栈不为空的时候依次取出栈内元素 t+; return ERROR;（2） 数字栈部分： struct SqStackn /定义数栈 int *base; /栈底指针 int *top; /栈顶指针 int stacksize; /栈的长度;int InitStackn (SqStackn &s) /建立一个空栈S s.base=(int*)malloc(50*sizeof(int); if(!s.base)exit(OVERFLOW); /存储分配失败 s.top=s.base; s.stacksize=50; return OK;

37、 int GetTopn(SqStackn s,int &e) /数栈取栈顶元素 if (s.top=s.base) printf("运算数栈为空!n"); /栈为空的时候返回ERROR return ERROR; else e=*(s.top-1); /栈不为空的时候，用e作返回值，返回S的栈顶元素，并返回OK return OK; int Pushn(SqStackn &s,int e) /数栈入栈 if (s.top-s.base >=s.stacksize)printf("运算数栈满!n"); /栈满的时候，追加5个存储空间

38、 s.base=(int*)realloc (s.base,(s.stacksize+5)*sizeof(int) ); if(!s.base) exit (OVERFLOW); s.top=s.base+s.stacksize; /插入元素e为新的栈顶元素 s.stacksize+=5;*(s.top)+=e; /栈顶指针变化return OK; int Popn(SqStackn &s,int &e) /数栈出栈if (s.top=s.base) printf(" 运算符栈为空!n"); /栈为空栈的视时候，返回ERROR return ERROR; e

39、lsee=*-s.top; /栈不空的时候，则删除S的栈顶元素，用e返回其值，并返回OKreturn OK; int StackTraversen(SqStackn &s) /数栈遍历 int *t;t=s.base ;if (s.top=s.base) printf(" 运算数栈为空!n"); /栈为空栈的时候返回ERROR return ERROR;while(t!=s.top) printf(" %d",*t); /栈不为空的时候依次输出 t+; return ERROR;五、算法及时间复杂度1、算法：建立两个不同类型的空栈，先把一个# 压

40、入运算符栈。输入一个算术表达式的字符串（以#结束），从第一个字符依次向后读，把读取的数字放入数字栈，运算符放入运算符栈。判断新读取的运算符和运算符栈顶得运算符号的优先级，以便确定是运算还是把运算符压入运算符栈。最后两个#遇到一起则运算结束。数字栈顶的数字就是要求的结果。2、时间复杂度：O(n)数据压缩存储栈，其操作主要有：建立栈int Push(SeqStack *S, char x)入栈int Pop(SeqStack *S, char x)出栈。以上各操作运算的平均时间复杂度为O(n)，其主要时间是耗费在输入操作。6、 测试用例如图所示。最终结果如图所示：7、 源代码/*第七题 算术表达式求值问题描述一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。基本要求（1） 从键盘读入一个合法的算术表达式，输出正确的结果。