数据结构设计报告

计算机与软件工程学院课程设计说明书课程名称:数据结构与算法设计课程代码:106086329题目二:查找、内排序算法的时间复杂度分析年级/专业/班:2014/计科学生姓名:杜柳磊学号:3120140901102开始时间:2016年4月1日完成时间:2016年5月1日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总分（100）指导教师签名：年月日跳舞搭配问题数据结构与算法设计实践任务书学院名称：计算机学院课程代码：_106086329________专业：计算机科学与技术年级：14一、设计题目查找、内排序算法的时间复杂度分析二、主要内容现通过随机输入多组不同个数的数据，对各种算法的关键字比较次数、移动次数及执行时间进行比较，以求得实验理论。三、具体要求及基本要求•随机产生n=100，200，300，1000，2000个整数并存于数组A[1..n]中。对主要查找算法（顺序查找、插入排序、归并排序、堆排序、快速排序）进行实验比较，计算出平均比较次数、平均移动次数及执行时间。、由程序自动计算，由手工计时。•对实验结果数据进行对比分析提交的材料四、推荐参考资料1.冯博琴等编著，《软件技术基础》（修改版），西安交通大学出版社，19972.严蔚敏等著，《数据结构》，清华大学出版社，20033.李芸芳等著，《软件技术基础》（第二版），清华大学出版社，20004.徐孝凯等著，《数据结构（C语言描述）》，清华大学出版社，2004指导教师签名日期年月日系主任审核日期年月日目录摘要………………………………………………………………………………11引言……………………………………………………………………………22设计方案………………………………………………………………………32.1整体设计方案………………………………………………………………32.1.1对初始数据的计算及代码………………………………………………42.1.2进一步对数据分析及代码………………………………………………63程序代码………………………………………………………………………114程序演示………………………………………………………………………14总结……………………………………………………………………………20致谢………………………………………………………………………………21参考文献…………………………………………………………………………22-1-摘要各种查找、内排序算法的时间复杂度分析是从理论上给出了算法执行时间关于数据个数n的阶。现通过随机输入多组不同个数的数据，对各种算法的关键字比较次数、移动次数及执行时间进行比较，以求得实验理论。•基本要求•随机产生n=100，200，300，1000，2000个整数并存于数组A[1..n]中。对主要查找算法（顺序查找、插入排序、归并排序、堆排序、快速排序）进行实验比较，计算出平均比较次数、平均移动次数及执行时间。、由程序自动计算，由手工计时。•对实验结果数据进行对比分析跳舞搭配问题-2-1引言1.1问题的提出以前的操作系统等系统软件主要是由汇编语言编写的（包括ＵＮＩＸ操作系统在内）。由于汇编语言依赖于计算机硬件，程序的可读性和可移植性都比较差。为了提高可读性和可移植性，最好改用高级语言，但一般高级语言难以实现汇编语言的某些功能（汇编语言可以直接对硬件进行操作，例如，对内存地址的操作、位操作等）。人们设想能否找到一种既具有一般高级语言特性，又具有低级语言特性的语言，集它们的优点于一身。于是，Ｃ语言就在这种情况下应运而生了。1.2C语言C语言既有高级语言的特点，又具有汇编语言的特点；既是一个成功的系统设计语言，有时一个使用的程序设计语言；既能用来编写不依赖计算机硬件的应用程序，又能用来编写各种系统程序；是一种受欢迎、应用广泛的程序设计语言。1.3C语言发展过程1973年，美国贝尔实验室的D.M.RITCHIE在B语言的基础上最终设计出了一种新的语言，他取了BCPL的第二个字母作为这种语言的名字，这就是C语言。1977年DennisM.Ritchie发表了不依赖于具体机器系统的C语言编译文本《可移植的C语言编译程序》。1978年BrianW.Kernighian和DennisM.Ritchie出版了名著《TheCProgrammingLanguage》，从而使C语言成为目前世界上流行最广泛的高级程序设计语言。跳舞搭配问题-3-2设计方案#includestdio.h#defineMAX30000/*函数声明区*/intSequenceSearch(inte[],intlen,intkey);intBinarySearch(inte[],intlen,intkey);voidStraightInsertSort(inte[],intlen);voidQuickSort(inte[],intfirst,intend);voidMergeSort(inte[],inta[],intfirst,intend);voidHeapSort(inte[],intlen);voidPrint(inte[],intlen,intcols);/*全局变量区*/longcompare;/*比较次数*/longmove;/*移动次数*/voidmain(){inti;intn;inttable[MAX],table1[MAX];intkey;intpos;intchoice;intcols=10;system(cls);printf(***********************************************************\n);printf(INITIALIZETABLE\n);printf(n=);scanf(%d,&n);srand(time(NULL));for(i=0;in;i++){table[i]=rand();table1[i]=table[i];}while(1){system(cls);printf(***********************************************************\n);printf(ORIGINTABLE(%d):\n,n);Print(table,n,cols);跳舞搭配问题-4-printf(***********************************************************\n);printf(ORDERTABLE(%d):\n,n);StraightInsertSort(table1,n);Print(table1,n,cols);printf(***********************************************************\n);printf(ALGORITHANALYSISSYSTEM\n\n);printf(1.SEQUENCESEARCHING\n);printf(2.BINARYSEARCHING\n);printf(3.STRAIGHTINSERTSORTING\n);printf(4.MERGESORTING\n);printf(5.HEAPSORTING\n);printf(6.QUICKSORTING\n);printf(0.EXITSYSTEM\n\n);printf(***********************************************************\n\n);printf(YOURCHOICE:);scanf(%d,&choice);switch(choice){case0:return;case1:{/***********************************************************************//*执行顺序查找*/printf(\t\tkey=);scanf(%d,&key);compare=0;pos=SequenceSearch(table,n,key);printf(\t\tSequenceSearching\n);printf(----------------------------------------\n);printf(Analysisdetails:\n);if(pos==-1){printf(\tsearch%dfail.\n,key);printf(\tcompare:%ldtimes.,compare);}else{printf(\tsearch%dsuccess.\n,key);printf(\tcompare:%ldtimes.,compare);}printf(\n\n);/***********************************************************************/break;跳舞搭配问题-5-}case2:{/***********************************************************************//*执行二分查找*/printf(\t\tkey=);scanf(%d,&key);compare=0;pos=BinarySearch(table1,n,key);printf(\t\tBinarySearching\n);printf(----------------------------------------\n);printf(Analysisdetails:\n);if(pos==-1){printf(\tsearch%dfail.\n,key);printf(\tcompare:%ldtimes.,compare);}else{printf(\tsearch%dsuccess.\n,key);printf(\tcompare:%ldtimes.,compare);}printf(\n\n);/***********************************************************************/break;}case3:{/***********************************************************************//*执行直接插入排序*/for(i=0;in;i++)table1[i]=table[i];compare=move=0;StraightInsertSort(table1,n);printf(\t\tStraightInsertSorting\n);printf(----------------------------------------\n);printf(Analysisdetails:\n);printf(\tcompare:%ldtimes.\n,compare);printf(\tmove:%ldtimes.\n\n,move);/***********************************************************************/break;跳舞搭配问题-6-}case4:{/***********************************************************************//*执行归并排序*/for(i=0;in;i++)table1[i]=table[i];compare=move=0;MergeSort(table1,table,0,n-1);printf(\t\tMergeSorting\n);printf(----------------------------------------\n);printf(Analysisdetails:\n);prin