《数据结构》课程设计报告

1、.课程设计报告-数据结构学院:软件学院班级:11级二班学号:54110211姓名：刘海鲸辅导老师：刘亚波老师数据结构课程设计报告姓名：刘海鲸学号：54110211实验室：座位号:提交日期：2013.3.13成绩：指导教师：刘亚波问题解析（对问题的分析、解题思路与解题方法）：实验目的为使我们学习完数据结构课程后，全面深入理解数据结构知识，掌握应用技巧，提高应用与分析能力，并培养学生综合运用所学理论知识求解问题的能力和协作精神。解题思路(分析)：题目要求独立编写程序，完成对起泡排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序6种内排序算法的比较，并且使用至少5组不同的输入数据（记录个数

2、不小于1000个，其中包括完全正序，完全逆序和无序情况）进行排序，比较各组记录与各种排序方法在关键字比较次数和关键字移动次数这两个指标上的差异。因此只需对文件进行排序并计算出两项指标针对某一组特定数据在不同排序方法中的值，既可以完成题目要求。编写正确的排序算法，使用程序读取不同文件，并定义变量，记录排序过程中两项指标的值，就是本题的解题思路。解题方法：使用Code:blocks作为本次实验的开发工具，使用C+完成程序。首先使用数据产生程序来产生所需的5个数据文件，使用了C+中cstdlib文件中的rand（）函数和srand（）函数共同产生3组伪随机数；在另一个工程中创建了data.h与con

3、trol.h两个头文件和main.cpp源文件，其中data.h定义了数据类型（模板类），包括主要的排序函数和数据成员，control.h定义了控制类，来完成界面控制，数据文件读取和排序功能的实现，main.cpp是对控制类对象的控制函数conmian（）的调用来完成整个程序。最后运行程序来完成对比较指标的统计并进行分析，对得出结果进行解释。任务分工：本实验由本人独立完成。进度安排：为第一次实验课将6个内排序算法完成并调试成功，周末之前完成界面控制并对排序结果进行分析，第二次实验之前完成课程设计报告，第二次试验对程序结果进行最后检查并提交实验报告。数据结构选择（包括改进或给出）：使用数组作为本

4、实验基本的数据结构，数据类中包含有数组的头指针head，在初始化时动态申请数组空间，此外还有count（整型）用于记录数组个数,同时可以对数组进行6种内排序及显示数组元素的操作。算法设计：借助课本与网络，使用C+编写算法，详细请看后面程序清单。编程与程序清单：1./头文件data.h2./文件数据类Data定义3. /起泡排序（升序）4. /直接插入排序（升序）5. /简单选择排序（升序）6. /快速排序(升序)7./快速排序的递归函数8./希尔排序 （升序）9./插入排序（升序）10. /堆排序（升序）11./控制类12. /功能选择13./主函数1./头文件data.h 1./头文件dat

5、a.h#ifndef DATA_H_INCLUDED#define DATA_H_INCLUDED#include<ctime>#include<iostream>using namespace std;2./文件数据类Data定义template<class T>class Data private: T *head; /数据数组指针，用于动态申请数组空间 int count; /数组大小 public: /构造函数，使指针为空 Data()head=NULL; /用已有数组构造数组元素，当前程序使用该函数来构造数据元素 void copy(T *h,in

6、t c=1000) if(head!=NULL) delete head; head=h;count=c; head=new Tcount; for(int i=0;i<count;i+) headi=hi; /手动输入各元素，当前程序未使用，调试程序时使用！ void set() if(head!=NULL) delete head; cout<<"请输入数据个数："<<endl; cin>>count; head=new Tcount; cout<<"请输入数据："<<endl; fo

7、r(int i=0;i<count;i+) cin>>headi; /析构函数，回收空间 Data()delete head;3. /起泡排序（升序） void bSort() if(isEmpty()cout<<" 文件中无记录，无法排序！"<<endl;return; int compareTime=0; /关键词比较次数 int moveTime=0; /关键词移动次数 int bound=count; int start,finish; /记录程序运行时间 T temp; cout<<" 正在排序.&q

8、uot;<<endl; start=clock(); /记录初始时间 /算法主体 while(bound!=0) int t=0; for(int i=0;i<bound-1;i+) compareTime+; if(headi>headi+1) temp=headi; headi=headi+1; headi+1=temp; t=i+1; moveTime+=3; /记录交换一次移动次数加3 bound=t; finish=clock(); cout<<" >>排序后结果为："<<endl; display();

9、 /输出排序后序列 cout<<endl<<" *-"<<endl <<" *关键词比较次数："<<compareTime<<endl <<" *记录移动次数："<<moveTime<<endl <<" *排序执行时间："<<finish-start<<"ms"<<endl <<" *-"<<end

10、l<<endl; 4. /直接插入排序（升序） void iSort() if(isEmpty()cout<<" 文件中无记录，无法排序！"<<endl; int compareTime=0; int moveTime=0; long start,finish; T temp; cout<<" 正在排序."<<endl; start=clock(); for(int i=1;i<count;i+) int j; j=i-1; temp=headi; moveTime+; /无记录交换，仅有

11、向辅存中移动，故移动次数加1 while(j>=0&&headj>temp) compareTime+; headj+1=headj; moveTime+; /记录向后移一位，移动次数加1 j-; compareTime+; /跳出循环后比较次数要再加1 headj+1=temp; moveTime+; finish=clock(); cout<<" >>排序后结果为："<<endl; display(); cout<<endl<<" *-"<<endl

12、<<" *关键词比较次数："<<compareTime<<endl <<" *记录移动次数："<<moveTime<<endl <<" *排序执行时间："<<(finish-start)<<"ms"<<endl <<" *-"<<endl<<endl; 5. /简单选择排序（升序） void sSort() if(isEmpty()cout&

13、lt;<" 文件中无记录，无法排序！"<<endl; int compareTime=0; int moveTime=0; long start,finish; T temp; cout<<" 正在排序."<<endl; start=clock(); for(int i=0;i<count-1;i+) int j=i; for(int k=i+1;k<count;k+) compareTime+; if(headj>headk) j=k; /标记当前最大的记录下标 if(i!=j) temp=h

14、eadi; headi=headj; headj=temp; moveTime+=3; finish=clock(); cout<<" >>排序后结果为："<<endl; display(); cout<<endl<<" *-"<<endl <<" *关键词比较次数："<<compareTime<<endl <<" *记录移动次数："<<moveTime<<endl <

15、;<" *排序执行时间："<<(finish-start)<<"ms"<<endl <<" *-"<<endl<<endl; 6. /快速排序(升序) void qqSort() if(isEmpty()cout<<" 文件中无记录，无法排序！"<<endl; long start,finish; int times2=0,0; /要调用函数，故使用数组来记录关键词的比较次数和移动次数，直接进行计数 start=c

16、lock(); cout<<" 正在排序."<<endl; qSort(head,0,count,times); /一趟快速排序函数 finish=clock(); cout<<" >>排序后结果为："<<endl; display(); cout<<endl<<" *-"<<endl <<" *关键词比较次数："<<times0<<endl <<" *记录移动次

17、数："<<times1<<endl <<" *排序执行时间："<<(finish-start)<<"ms"<<endl <<" *-"<<endl<<endl; 7./快速排序的递归函数 void qSort(T *head,int m,int n,int *times) int i=m,j=n; T temp=headm,t=m; if(m<n) /递归出口（m>=n） while(i<j) i=i

18、+1; while(headi<temp&&i!=n)times0+;i+; j=j-1; while(headj>temp&&j!=m)times0+;j-; if(i<j) t=headi; headi=headj; headj=t; times1+=3; if(m!=j) t=headm; headm=headj; headj=t; times1+=3; qSort(head,m,j,times); qSort(head,j+1,n,times); 8./希尔排序 （升序） void shell() if(isEmpty()cout<

19、;<" 文件中无记录，无法排序！"<<endl; int times2=0,0; int seq8=701,301,132,57,23,10,4,1; /依据课本得到希尔排序最优的增量递减序列 long start,finish; cout<<" 正在排序."<<endl; start=clock(); int n; for(int i=0;i<8;i+) n=seqi; insert(n,times); /调用插入排序算法对同组数据进行排序 finish=clock(); cout<<&quo

20、t; >>排序后结果为："<<endl; display(); cout<<endl<<" *-"<<endl <<" *关键词比较次数："<<times0<<endl <<" *记录移动次数："<<times1<<endl <<" *排序执行时间："<<(finish-start)<<"ms"<<endl

21、<<" *-"<<endl<<endl; 9./插入排序（被希尔排序shell函数调用） void insert(int n,int * times) /增量为n带来一系列程序的改动 for(int k=0;k+n<count;k+) T temp; for(int i=k+n;i<count;i+=n) int j; j=i-n; temp=headi; times1+; while(j>=k&&headj>temp) times0+; headj+n=headj; times1+; j-=n;

22、times0+; headj+n=temp; times1+; 10. /堆排序（升序） void hSort() /堆为完全二叉树，故可用数组构造堆，且不会造成空间的浪费 if(isEmpty()cout<<" 文件中无记录，无法排序！"<<endl; int times2=0,0; T temp; long start,finish; cout<<" 正在排序."<<endl; start=clock(); /初始建堆 for(int i=count/2;i>0;i-) restore(i,cou

23、nt,times); /排序及重建堆 for(int i=count;i>1;i-) temp=head0; head0=headi-1; headi-1=temp; times1+=3; restore(1,i-1,times); finish=clock(); cout<<" >>排序后结果为："<<endl; display(); cout<<endl<<" *-"<<endl <<" *关键词比较次数："<<times0<

24、;<endl <<" *记录移动次数："<<times1<<endl <<" *排序执行时间："<<(finish-start)<<"ms"<<endl <<" *-"<<endl<<endl; /重建堆算法（被堆排序hSort函数调用） void restore(int a,int b,int * times) int mark,j=a; T temp; while(j<=b/2)

25、if(2*j<b&&head2*j-1<head2*j) mark=2*j; times0+; else mark=2*j-1; times0+; if(headmark>headj-1) temp=headmark; headmark=headj-1; headj-1=temp; j=mark+1; times0+; times1+=3; else j=b; /人为改变j的值，跳出循环，退出程序 times0+; /输出记录序列（升序） void display() for(int i=0;i<count;i+) cout<<headi&l

26、t;<" " cout<<endl; /判断数据是否为空 bool isEmpty()constreturn head=NULL; /获得头指针，本程序未使用！ T *getHead()return head; /获得数组元素个数，本程序未使用！ int getCount ()constreturn count;#endif / DATA_H_INCLUDED/头文件control.h#ifndef CONTROL_H_INCLUDED#define CONTROL_H_INCLUDED#include"data.h"#include&

27、lt;iostream>#include<sstream> /含有istringstream类#include<fstream>using namespace std;11./控制类，进行界面管理,记录文件读取，调用排序函数等操作class Control public: void conmain() /控制函数 cout<<"#" <<"#【数据结构课程设计（一）：内排序算法比较】#" <<"#" cout<<"#使用说明：运行程序，请输入数据文

28、件名（a.txt,b.txt,c.txt均为无序数据，d.txt为完#" <<"#全正序数据，e.txt为完全逆序文件，均存放在当前目录下），之后请按照用户个人需求 #" <<"#选择相应功能！ #" <<"#" <<" #"<<endl <<" #>>功能列表 #"<<endl <<" #"<<endl <<" # 1.起泡

29、排序 （升序） #"<<endl <<" # 2.直接插入排序（升序） #"<<endl <<" # 3.简单选择排序 （升序） #"<<endl <<" # 4.快速排序（升序） #"<<endl <<" # 5.希尔排序（升序） #"<<endl <<" # 6.堆排序（升序） #"<<endl <<" # 0.退出 #"

30、;<<endl <<" #"<<endl;/定义选择变量及辅助变量int opt1,a,i=0;/数组存储数据int data1000;/定义Data类对象Data<int> temp;/文件名string file; /读取文件,从输入的文件名中读取数据，a.txt,b.txt,c.txt为随机数据，e.txt为正序，e.txt为逆序cout<<endl<<" >>请输入目标数据文件：" cin>>file; ifstream in(file.c_str()

31、; /string类转换为字符串且在末尾加'0' for(string s;getline(in,s);) /读取文件，读取整行，使用istringstream类读出数字（可自动忽略数字间的空格） for(istringstream sin(s);sin>>a;); datai+=a; 12. /功能选择cout<<endl<<" >>请选择功能（输入对应功能的序号）："cin>>opt1;while(opt1)switch(opt1) /调用起泡排序函数case 1:temp.copy(data)

32、;temp.bSort();break; /调用直接插入排序函数case 2:temp.copy(data);temp.iSort();break; /调用简单选择排序函数case 3:temp.copy(data);temp.sSort();break; /调用快速排序函数 case 4:temp.copy(data);temp.qqSort();break; /调用Shell排序函数 case 5:temp.copy(data);temp.shell();break; /调用堆排序函数 case 6:temp.copy(data);temp.hSort();break; <<&

33、quot; |<您的输入有误，请再次输入！>|"<<endl <<" -"<<endl; cout<<" #"<<endl <<" #>>功能列表 #"<<endl <<" #"<<endl <<" # 1.起泡排序 （升序） #"<<endl <<" # 2.直接插入排序（升序） #"<<

34、;endl <<" # 3.简单选择排序 （升序） #"<<endl <<" # 4.快速排序（升序） #"<<endl <<" # 5.希尔排序（升序） #"<<endl <<" # 6.堆排序（升序） #"<<endl <<" # 0.退出 #"<<endl <<" #"<<endl;cout<<endl<<

35、;" >>请选择功能（输入对应功能的序号）："cin>>opt1;cout<<"#"<<"#"<<"#"<<endl; ;#endif / CONTROL_H_INCLUDED/源文件main.cpp#include"data.h"#include"control.h"#include<iostream>using namespace std;12./主函数int main() Control

36、 a; /控制类Control类对象 a.conmain(); /控制函数 return 0;测试方法：使用排序程序前，先使用数据产生程序generator产生所需数据（整型，1000个记录），包括3组无序数据（用rand（）与srand（）函数产生），一组完全正序数据和一组完全逆序数据，并分别存储于5个不同的文本文件中。在排序程序中依次读取5个数据文件并按照程序的提示对数据进行排序，观测输出的排序序列并对关键词比较次数和关键词移动次数进行分析。测试数据：由数据产生程序generator产生，存储于文件由数据产生程序generator产生，存储于文件a.txt,b.txt,c.txt,d.tx

37、t,e.txt(前三个为无序记录文件，第四个为完全正序文件，第五个为完全逆序文件)中，记录为整型数据， 规模为1000数量级。测试结果：起泡排序数据组别比较次数/次移动次数/次排序时间/ms理论值（最好，最坏，平均）O（n），O(n2)，O(n2)0，O(n2)，O(n2)-a49729676015212b49713975650716c49559674349912d99901e499500149850014直接插入排序数据组别比较次数/次移动次数/次排序时间/ms理论值（最好，最坏，平均）O（n），O(n2)，O(n2)O（n），O(n2)，O(n2)-a2543832553825b25316

38、82541676c2488322498315d99919981e50049950149811简单选择排序数据组别比较次数/次移动次数/次排序时间/ms理论值（最好，最坏，平均）O(n2)，O(n2)，O(n2)0，O(n)，O(n)-a49950029856b49950029766c49950029736d49950007e49950015009快速排序数据组别比较次数/次移动次数/次排序时间/ms理论值（最好，最坏，平均）O(n·log2n)，O(n·log2n)，O(n·log2n)0，O(n·log2n)，O(n·log2n)-a834182953b663983764c759382232d49950005e49950015006Shell排序数据组别比较次数/次移动次数/次排序时间/ms理论值（最好，最坏，平均）O(n·（log2n）2)O(n·（log2n）2)-a714181142199923b714136142195422c714210142202821d707818141563622e710908141872621堆