数据结构课程设计报告排序算法的性能分析.doc

数据结构课程设计报告教学计划编制问题内部排序算法的性能分析 学院（系）： 数学与统计学院 班 级： 110010101 学生姓名： 杨晓格 学 号： 11001010129 指导教师： 韩逢庆 时 间： 从2011年12月31日 到2012年1月 6日一、课程设计概述：本次数据结构课程设计共完成二个题：a.教学计划编制问题b.内部排序算法的性能分析使用语言：C编译环境：TC3.0 / VC6.0二、课程设计题目一实验内容 教学计划编制问题问题描述答学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序 需求分析 （1） 输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。（2） 允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。（3） 若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。 概要设计md init() /*初始化教学计划*/void select (int quee,int i,int j,md a) /*使课程集中在前面*/void arrage(md a) /*教学计划函数*/流程图初始化教学课程数学期数学分上限输入后续课程教学计划函数 详细设计#include<stdio.h>#include <stdlib.h>#define NULL 0#define maxsize 100typedef struct stuint number;int score;struct stu *next;node;typedef structint vex_num;int vex_sco;int have;node *first;sd;typedef structsd arrymaxsize;int max_class;int max_term;int score_limit;md;md init()int i,x,c;md a;node *p;printf("enter class total:");scanf("%d",&a.max_class);printf("enter term total:");scanf("%d",&a.max_term);printf("enter score limit:");scanf("%d",&a.score_limit);printf("enter class arrange n");for (i=1;i<=a.max_class;i+)a.arryi.first=NULL;for(i=1;i<=a.max_class;i+)printf("enter %i class number and score:",i);scanf("%d %d",&a.arryi.vex_num,&a.arryi.vex_sco);printf("enter %i prior class:",i);c=0;doscanf("%d",&x);if (x>0)p=(node *)malloc(sizeof(node);p->number=a.arryi.vex_num;p->next=a.arryx.first;a.arryx.first=p;c+;while(x>0);a.arryi.have=c;return a;/*void disp(md a)node *p;int i;for (i=1;i<=a.max_class;i+) printf("%d",a.arryi.vex_num); p=a.arryi.first; while(p!=NULL) printf("%d",a.arryp->number.vex_num); p=p->next; printf("n"); */void select (int quee,int i,int j,md a)int k,temp,min;min=i;for(k=i+1;k<=j;k+)if (a.arryqueek.vex_sco<a.arryqueemin.vex_sco)min=k;if(min!=i)temp=queei;queei=queemin;queemin=temp;void arrage(md a)int queemaxsize,front,bare,i,j,total_score;node *p;front=bare=0;j=1;for(i=1;i<=a.max_class;i+)if (a.arryi.vex_num!=0&&a.arryi.have=0)quee+bare=a.arryi.vex_num;printf("n %d term study:",j+);total_score=0;while(front!=bare)select(quee,front+1,bare,a);if (total_score+a.arryqueefront+1.vex_sco<=a.score_limit)printf("%d",a.arryqueefront.vex_num);a.arryqueefront.vex_num=0;total_score+=a.arryqueefront.vex_sco;p=a.arryqueefront.first;while(p!=NULL)a.arryp->number.have-;if (a.arryp->number.have=0)quee+bare=a.arryp->number.vex_num;p=p->next;elsetotal_score=0;printf(" n%d term study:",j+);main()md h;h=init();arrage(h); 调试分析问题：现象：最后结果存在问题，无法提供内存原因：函数的参数没有写正确： 运行结果及分析课程设计题目二实验内容 内部排序算法的性能分析问题描述。设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受 需求分析 (1)对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较；(2)待排序表的表长不小于100，表中数据随机产生，至少用5组不同数据作比较，比较指标有：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）；(3)输出比较结果。 概要设计main()SqList L; addlist(L); qipao(L); InsertSort(L);SelectSort(L); QuickSort(L); addlist(L); MergeSort(L); 流程图输入数字冒泡排序直插排序希尔排序选择排序归并排序快速排序移动次数和比较次数 详细设计 #include<stdio.h> #include<stdlib.h>#include<string.h>#include<time.h>#define LIST_INIT_SIZE 50000int bj1,yd1,n;clock_t start_t,end_t;typedef struct int key; ElemType;typedef struct ElemType *elem; int length;SqList;void addlist(SqList &L) int i;a: printf("请输入你要输入的个数:"); scanf("%d",&n); if(n>50000) printf("超出范围重新输入!n"); goto a; L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem)exit(0); L.length=0; for(i=1;i<n+1;i+) b: L.elemi.key=rand(); if(L.elemi.key>30000)goto b; +L.length; void SelectSort(SqList &L)/选择 start_t=clock(); int i,j,k,bj=0,yd=0; for(i=1;i<L.length;i+) k=i; for(j=i+1;j<L.length;j+) bj+; if(L.elemj.key<L.elemk.key)k=j; if(i!=k) L.elem0.key=L.elemi.key; L.elemi.key=L.elemk.key; L.elemk.key=L.elem0.key; yd+=3; end_t=clock(); printf("比较次数为 %d移动次数为 %dn",bj,yd); printf("排序用时为 %fn",float(end_t-start_t)/CLK_TCK);void qipao(SqList &L)/起泡 start_t=clock(); int i=1,j,bj=0,yd=0; while(i<L.length) for(j=1;j<L.length;j+) bj+; if(L.elemj.key>L.elemj+1.key) L.elem0.key=L.elemj.key; L.elemj.key=L.elemj+1.key; L.elemj+1.key=L.elem0.key; yd+=3; i+; end_t=clock(); printf("比较次数为 %d移动次数为 %dn",bj,yd); printf("排序用时为 %fn",float(end_t-start_t)/CLK_TCK);void InsertSort(SqList &L)/直接插入 start_t=clock(); int i,j,yd=0,bj=0; for(i=2;i<=L.length;i+) if(L.elemi.key<L.elemi-1.key) L.elem0.key=L.elemi.key; yd+; j=i-1; bj+; while(L.elem0.key<L.elemj.key) L.elemj+1.key=L.elemj.key; j-; yd+; bj+; L.elemj+1.key=L.elem0.key; yd+; end_t=clock(); printf("比较次数为 %d移动次数为 %dn",bj,yd); printf("排序用时为 %fn",float(end_t-start_t)/CLK_TCK);void xier(SqList &L)/希尔 start_t=clock(); int i,d=L.length/2,j,w=0,k,yd=0,bj=0; while(w<d) w=1; for(i=w;i<L.length;i=i+d) k=i; for(j=i+d;j<L.length;j=j+d) if(L.elemi.key>L.elemj.key) k=j; bj+; if(i!=k) L.elem0.key=L.elemi.key; L.elemi.key=L.elemk.key; L.elemk.key=L.elem0.key; yd+=3; w+; d=d/2; w=1; end_t=clock(); printf("比较次数为 %d移动次数为 %dn",bj,yd); printf("排序用时为 %fn",float(end_t-start_t)/CLK_TCK);void BeforeSort() yd1=0,bj1=0;void display(int m,int n) printf("比较次数为 %d移动次数为 %dn",m,n);int Partition(SqList &L,int low,int high)/快速排序 int pivotkey; L.elem0=L.elemlow; yd1+; pivotkey=L.elemlow.key; while (low<high) yd1+; while(low<high&&L.elemhigh.key>=pivotkey) -high; L.elemlow=L.elemhigh; bj1+; yd1+; while (low<high&&L.elemlow.key<=pivotkey) +low; L.elemhigh=L.elemlow; bj1+; yd1+; L.elemlow=L.elem0; yd1+; return low;void QSort(SqList &L,int low,int high) int pivotloc; if(low<high) pivotloc=Partition(L,low,high); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high); void QuickSort(SqList &L) start_t=clock(); BeforeSort(); QSort(L,1,L.length); display(yd1,bj1); end_t=clock(); printf("排序用时为 %fn",float(end_t-start_t)/CLK_TCK);void Merge(ElemType R,ElemType R1,int low,int m,int high)/归并 int i=low, j=m+1, k=low; while(i<=m&&j<=high) if(Ri.key<=Rj.key) bj1+; R1k=Ri; yd1+; i+; k+; else bj1+; R1k=Rj; yd1+; j+; k+; while(i<=m) R1k=Ri; yd1+; i+; k+; while(j<=high) R1k=Rj; yd1+; j+; k+; void MergePass(ElemType R,ElemType R1,int length, int n) int i=0,j; while(i+2*length-1<n) Merge(R,R1,i,i+length-1,i+2*length-1); i=i+2*length; if(i+length-1<n-1) Merge(R,R1,i,i+length-1,n-1); else for(j=i;j<n;j+) R1j=Rj;void MSort(ElemType R,ElemType R1,int n) int length=1; while (length<n) MergePass(R,R1,length,n); length=2*length; MergePass(R1,R,length,n); length=2*length; void MergeSort(SqList &L) start_t=clock(); BeforeSort(); MSort(L.elem,L.elem,L.length); display(yd1,bj1); end_t=clock(); printf("排序用时为 %fn",float(end_t-start_t)/CLK_TCK);void main() SqList L; addlist(L); printf("起泡排序: n"); qipao(L); addlist(L); printf("直插排序: n"); InsertSort(L); addlist(L); printf("选择排序: n"); SelectSort(L); addlist(L); printf("希尔排序: n"); xier(L); addlist(L); printf("快速排续: n"); QuickSort(L); addlist(L); printf("归并排序: n"); MergeSort(L);运行结果及分析四、课程设计心得 一周的课程设计结束了，从课程设计的学习过程结束了，一开始，我并不知道要学这门课，我一直打算复习好考试的科目的，所以说是实话，我刚开始的时候，真的是很懊恼，很纠结。可是仔细想想不管我愿意或者不愿意，我都必须学习，这是我的责任，我不可推卸。我唯一可以做的就是好好学习，更好的安排好我的学习时间，更加有计划的利用好我的时间。有句话说的好，时间是挤出来的。而且渐渐地我明白了一个道理，环境一直在改变，没有人知道未来的自己会遭遇什么样的事情，惟有发展好自己才是最根本的，最有效的办法。还有就是，课程设计这门课，让我体会到会编写有用的程序是多么的充实，内心会得到满足。程序这个东西，其实呢，并没有我们想象的那么难，那么复杂，我们只要认认真真的去学习，没有什么事情是可以难倒我们的。所以，我很高兴自己可以上这门课，也很开心我可以明白这个道理。16 / 16文档可自由编辑打印