数据结构实验报告
实验名称:实验四排序
学生姓名:
班级:
班内序号:
学号:
日期:2012年12月21日
1、实验要求
题目2
使用链表实现下面各种排序算法,并进行比较。
排序算法:
1、插入排序
2、冒泡排序
3、快速排序
4、简单选择排序
5、其他
要求:
1、测试数据分成三类:正序、逆序、随机数据。
2、对于这三类数据,比较上述排序算法中关键字的比较次数和移动次数(其中关键字交换计为3次移动)。
3、对于这三类数据,比较上述排序算法中不同算法的执行时间,精确到微秒(选作)。
4、对2和3的结果进行分析,验证上述各种算法的时间复杂度。编写测试main()函数测试线性表的正确性。
2、程序分析
存储结构
说明:本程序排序序列的存储由链表来完成。
其存储结构如下图所示。
(1)单链表存储结构:
(2)结点结构
struct Node
{
int data;
Node * next;
};
示意图:
关键算法分析
一:关键算法
(一)直接插入排序 void LinkSort::InsertSort()
直接插入排序是插入排序中最简单的排序方法,其基本思想是:依次将待排序序列中的每一个记录插入到一个已排好的序列中,直到全部记录都排好序。
(1)算法自然语言
1.将整个待排序的记录序列划分成有序区和无序区,初始时有序区为待排序记录序列中的第一个记录,无序区包括所有剩余待排序的记录;
2.将无须去的第一个记录插入到有序区的合适位置中,从而使无序区减少一个记录,有序区增加一个记录;
3.重复执行2,直到无序区中没有记录为止。
(2)源代码
void
2.
3.
4.重复执行2和3
直接插入排序过程
(2)源代码
void LinkSort::BubbleSort()
{
Node * P = front->next;
while
较的基准)
2.
3.
(2)源代码
void LinkSort::Qsort()
{
Node * End = front;
while(End->next)
{
End = End->next;
}
Partion(front, End);
}
void LinkSort::Partion(Node * Start, Node * End)
{ Array
if
2.使得有序区扩展
了一个记录,而无序区减少了一个记录。 3.不断重复2,直到无序区之剩下一个记录为止。
(2)源代码
void LinkSort::SelectSort() { Node * S = front; while (S->next->next) { Node * P = S;
Node * Min = P;
while (P->next) 入。 比较次数:" << setw(3)
<< CompareCount << "; 移动次数:" << setw(3) << MoveCount << "; 时间: " << TimeCount <<"us"<< endl;
CompareCount = 0; MoveCount = 0; TimeCount = 0;
QueryPerformanceCounter(&time_start); 泡。 比较次数:" <<
setw(3) << CompareCount << "; 移动次数:" << setw(3) << MoveCount <<
"; 时间: " << TimeCount << "us"< CompareCount = 0; MoveCount = 0; TimeCount = 0; QueryPerformanceCounter(&time_start); 速。 比较次数:" << setw(3) << CompareCount << "; 移动次数:" << setw(3) << MoveCount << "; 时间: " << TimeCount << "us"< 初始键值序列 [49 27 65 97 76 13 38] 第一趟排序结果 13 [27 65 97 76 49 38] 第二趟排序结果 13 27 [65 97 76 49 38] 第三趟排序结果 13 27 38 [97 76 49 65] 第四趟排序结果 13 27 38 49 [76 97 65] 第五趟排序结果 13 27 38 49 65 [97 76] CompareCount = 0; MoveCount = 0; TimeCount = 0; QueryPerformanceCounter(&time_start); 择。比较次数:" << setw(3) << CompareCount << "; 移动次数:" << setw(3) << MoveCount << "; 时间: " << TimeCount << "us"< } (3)时间和空间复杂度 时间复杂度O(1)(因为不包含循环体)。 其他 3、程序运行结果 (1)程序流程图 (2)测试条件 规模为10个数字,在正序、逆序和乱序的条件下进行测试,未出现问题。(3)运行结果: (4)说明:各函数运行正常,没有出现bug。 四、总结 1、调试时出现的问题及解决方法 由于经过一种排序后,原始数据改变,导致后面的排序所用的数据全为排好后的数据。将数据在排序前重新初始化后,该问题被排除。还有就是因为编程时没有注意格式,所以在调试错误时花费了不少时间。 2、心得体会 这是最后一次编程实验。这次试验,我觉得主要目的还是在掌握好课本知识的基础上,对代码进行相应的优化,以达到时间复杂度和空间复杂度的最佳。 其次,本次实验是经过借鉴课本上的程序进行编写,是基于课本完成的。考虑到若完全由自己编写,则又可能限于自己能力问题,将较简单的算法编写的过于麻烦,造成关键码的比较次数和移动次数比一些复杂算法还多,从而影响结果。 基于课本编写,最大好处是可以借鉴、仔细研读书上的优秀例子,开拓以后编写程序的思路。基于课本编写,最大坏处是自己独立思考、独立编写、修改程序的能力未得到锻炼。 对于正序序列,直接插入、起泡排序法有较高的效率。 对于逆序序列,简单选择排序效率较高。 对于在随机序列,快速排序法的效率比较高。 程序的优化是一个艰辛的过程,如果只是实现一般的功能,将变得容易很多,当加上优化,不论是效率还是结构优化,都需要精心设计。这次做优化的过程中,遇到不少阻力。由于优化中用到很多类的封装和访问控制方面的知识,而这部分知识恰好是大一一年学习的薄弱点。因而以后要多花力气学习C++编程语言,必须要加强这方面的训练,这样才能在将编程思想和数据结构转换为代码的时候能得心应手。 数据结构实验报告 实验名称:实验四排序 学生姓名: 班级: 班内序号: 学号: 日期:2012年12月21日 1、实验要求 题目2 使用链表实现下面各种排序算法,并进行比较。 排序算法: 1、插入排序 2、冒泡排序 3、快速排序 4、简单选择排序 5、其他 要求: 1、测试数据分成三类:正序、逆序、随机数据。 2、对于这三类数据,比较上述排序算法中关键字的比较次数和移动次数(其中关键字交换计为3次移动)。 3、对于这三类数据,比较上述排序算法中不同算法的执行时间,精确到微秒(选作)。 4、对2和3的结果进行分析,验证上述各种算法的时间复杂度。编写测试main()函数测试线性表的正确性。 2、程序分析 存储结构 说明:本程序排序序列的存储由链表来完成。 其存储结构如下图所示。 (1)单链表存储结构: (2)结点结构 struct Node { int data; Node * next; }; 示意图: 关键算法分析 一:关键算法 (一)直接插入排序 void LinkSort::InsertSort() 直接插入排序是插入排序中最简单的排序方法,其基本思想是:依次将待排序序列中的每一个记录插入到一个已排好的序列中,直到全部记录都排好序。 (1)算法自然语言 1.将整个待排序的记录序列划分成有序区和无序区,初始时有序区为待排序记录序列中的第一个记录,无序区包括所有剩余待排序的记录; 2.将无须去的第一个记录插入到有序区的合适位置中,从而使无序区减少一个记录,有序区增加一个记录; 3.重复执行2,直到无序区中没有记录为止。 (2)源代码 void 2. 3. 4.重复执行2和3 直接插入排序过程 《数据结构》实验报告排序实验题目: 输入十个数,从插入排序,快速排序,选择排序三类算法中各选一种编程实现。 实验所使用的数据结构内容及编程思路: 1. 插入排序:直接插入排序的基本操作是,将一个记录到已排好序的有序表中,从而得到一个新的,记录增一得有序表。 一般情况下,第i 趟直接插入排序的操作为:在含有i-1 个记录的有序子序列r[1..i-1 ]中插入一个记录r[i ]后,变成含有i 个记录的有序子序列r[1..i ];并且,和顺序查找类似,为了在查找插入位置的过程中避免数组下标出界,在r [0]处设置哨兵。在自i-1 起往前搜索的过程中,可以同时后移记录。整个排序过程为进行n-1 趟插入,即:先将序列中的第一个记录看成是一个有序的子序列,然后从第2 个记录起逐个进行插入,直至整个序列变成按关键字非递减有序序列为止。 2. 快速排序:基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。 假设待排序的序列为{L.r[s] ,L.r[s+1],…L.r[t]}, 首先任意选取一个记录 (通常可选第一个记录L.r[s])作为枢轴(或支点)(PiVOt ),然后按下述原则重新排列其余记录:将所有关键字较它小的记录都安置在它的位置之前,将所有关键字较大的记录都安置在它的位置之后。由此可以该“枢轴”记录最后所罗的位置i 作为界线,将序列{L.r[s] ,… ,L.r[t]} 分割成两个子序列{L.r[i+1],L.[i+2], …,L.r[t]}。这个过程称为一趟快速排序,或一次划分。 一趟快速排序的具体做法是:附设两个指针lOw 和high ,他们的初值分别为lOw 和high ,设枢轴记录的关键字为PiVOtkey ,则首先从high 所指位置起向前搜索找到第一个关键字小于PiVOtkey 的记录和枢轴记录互相交换,然后从lOw 所指位置起向后搜索,找到第一个关键字大于PiVOtkey 的记录和枢轴记录互相 交换,重复这两不直至low=high 为止。 具体实现上述算法是,每交换一对记录需进行3 次记录移动(赋值)的操作。而实际上, 数据结构与算法设计 实验报告 (2016 — 2017 学年第1 学期) 实验名称: 年级: 专业: 班级: 学号: 姓名: 指导教师: 成都信息工程大学通信工程学院 一、实验目的 验证各种简单的排序算法。在调试中体会排序过程。 二、实验要求 (1)从键盘读入一组无序数据,按输入顺序先创建一个线性表。 (2)用带菜单的主函数任意选择一种排序算法将该表进行递增排序,并显示出每一趟排序过程。 三、实验步骤 1、创建工程(附带截图说明) 2、根据算法编写程序(参见第六部分源代码) 3、编译 4、调试 四、实验结果图 图1-直接输入排序 图2-冒泡排序 图3-直接选择排序 五、心得体会 与哈希表的操作实验相比,本次实验遇到的问题较大。由于此次实验中设计了三种排序方法导致我在设计算法时混淆了一些概念,设计思路特别混乱。虽然在理清思路后成功解决了直接输入和直接选择两种算法,但冒泡 排序的算法仍未设计成功。虽然在老师和同学的帮助下完成了冒泡排序的算法,但还需要多练习这方面的习题,平时也应多思考这方面的问题。而且,在直接输入和直接选择的算法设计上也有较为复杂的地方,对照书本做了精简纠正。 本次实验让我发现自己在算法设计上存在一些思虑不周的地方,思考问题过于片面,逻辑思维能力太过单薄,还需要继续练习。 六、源代码 要求:粘贴个人代码,以便检查。 #include 《排序问题求解》实验报告 一、算法的基本思想 1、直接插入排序算法思想 直接插入排序的基本思想是将一个记录插入到已排好序的序列中,从而得到一个新的, 记录数增1 的有序序列。 直接插入排序算法的伪代码称为InsertionSort,它的参数是一个数组A[1..n],包含了n 个待排序的数。用伪代码表示直接插入排序算法如下: InsertionSort (A) for i←2 to n do key←A[i] //key 表示待插入数 //Insert A[i] into the sorted sequence A[1..i-1] j←i-1 while j>0 and A[j]>key do A[j+1]←A[j] j←j-1 A[j+1]←key 2、快速排序算法思想 快速排序算法的基本思想是,通过一趟排序将待排序序列分割成独立的两部分,其中一 部分记录的关键字均比另一部分记录的关键字小,则可对这两部分记录继续进行排序,以达到整个序列有序。 假设待排序序列为数组A[1..n],首先选取第一个数A[0],作为枢轴(pivot),然后按照下述原则重新排列其余数:将所有比A[0]大的数都排在它的位置之前,将所有比A[0]小的数都排在它的位置之后,由此以A[0]最后所在的位置i 作为分界线,将数组A[1..n]分成两个子数组A[1..i-1]和A[i+1..n]。这个过程称作一趟快速排序。通过递归调用快速排序,对子数组A[1..i-1]和A[i+1..n]排序。 一趟快速排序算法的伪代码称为Partition,它的参数是一个数组A[1..n]和两个指针low、high,设枢轴为pivotkey,则首先从high 所指位置起向前搜索,找到第一个小于pivotkey 的数,并将其移到低端,然后从low 所指位置起向后搜索,找到第一个大于pivotkey 的数,并将其移到高端,重复这两步直至low=high。最后,将枢轴移到正确的位置上。用伪代码表示一趟快速排序算法如下: Partition ( A, low, high) A[0]←A[low] //用数组的第一个记录做枢轴记录 privotkey←A[low] //枢轴记录关键字 while low 动态查找表实验报告 一. 1 、实验概要 实验项目名称: 抽象数据类型的实现 实验项目性质: 设计性实验 所属课程名称: 数据结构 实验计划学时: 6 2、实验目的 对某个具体的抽象数据类型,运用课程所学的知识和方法,设计合理的数据结构,并在此基础上实现该抽象数据类型的全部基本操作。通过本设计性实验,检验所学知识和能力,发现学习中存在的问题。进而达到熟练地运用本课程中的基础知识及技术的目的。 实验要求如下: 1.参加实验的学生应首先了解设计的任务,然后根据自己的基础和能力从中选择一题。一般来说,选择题目应以在规定的时间内能完成,并能得到应有的锻炼为原则。若学生对教材以外的相关题目较感兴趣,希望选作实验的题目时,应征得指导教师的认可,并写出明确的抽象数据类型定义及说明。 2. 实验前要作好充分准备,包括:理解实验要求,掌握辅助工具的使用,了解该抽象数据类型的定义及意义,以及其基本操作的算法并设计合理的存储结构。 3. 实验时严肃认真,要严格按照要求独立进行设计,不能随意更改。注意观察并记录各种错误现象,纠正错误,使程序满足预定的要求,实验记录应作为实验报告的一部分。 4. 实验后要及时总结,写出实验报告,并附所打印的问题解答、程序清单,所输入的数据及相应的运行结果。 所用软件环境或工具:DEV-C++5可视化编程环境. 3.动态查找表的抽象数据类型 ADT DynamicSearchTable { 数据对象D:D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字,可唯一 标识数据元素。 数据关系R:数据元素同属一个集合。 基本操作P: InitDSTable(&DT); 操作结果:构造一个空的动态查找表DT。 DestroyDSTable(&DT); 初始条件:动态查找表DT存在; 操作结果:销毁动态查找表DT。 SearchDSTable(DT, key); 初始条件:动态查找表DT存在,key为和关键字类型相同的给定值; 操作结果:若DT中存在其关键字等于key的数据元素,则函数值为该元素的值或在表中的 《数据结构与算法统计》 实验报告 ——实验四 学院: 班级: 学号: 姓名: 一、实验目的 1、熟悉VC 环境,学会使用C 语言利用顺序表解决实际问题。 2、通过上机、编程调试,加强对线性表的理解和运用的能力。 3、锻炼动手编程,独立思考的能力。 二、实验内容 从键盘输入10个数,编程实现分别用插入排序、交换排序、选择排序算法进行排序,输出排序后的序列。 三、程序设计 1、概要设计 为了实现排序的功能,需要将输入的数字放入线性表中,进行进一步的排序操作。 (1)抽象数据类型: ADT SqList{ 数据对象:D={|,1,2,,,0}i i a a Elem Set i n n ∈=≥ 数据关系:R1=11{,|,,1,2,,}i i i i a a a a D i n --<>∈= 基本操作: InPut(SqList &L) 操作结果:构造一个线性表L 。 OutPut(SqList L) 初始条件:线性表L 已存在。 操作结果:按顺序在屏幕上输出L 的数据元素。 InsertSort(SqList &L) 初始条件:线性表L 已存在。 操作结果:对L 的数据元素进行插入排序。 QuickSort(SqList &L) 初始条件:线性表L 已存在。 操作结果:对L 的数据元素进行快速排序。 SelectSort(SqList &L) 初始条件:线性表L 已存在。 操作结果:对L 的数据元素进行选择排序。 }ADT SqList ⑵主程序流程 由主程序首先调用InPut(L)函数创建顺序表,调用InsertSort(L)函数进行插入排序,调用OutPut(L)函数显示排序结果。 再由主程序首先调用InPut(L)函数创建顺序表,调用QuickSort(L)函数进行交换排序,调用OutPut(L)函数显示排序结果。 再由主程序首先调用InPut(L)函数创建顺序表,调用SelectSort(L)函数进行选择排序,调用OutPut(L)函数显示排序结果。 ⑶模块调用关系 电子科技大学实验报告 课程名称:数据结构与算法 学生姓名: 学号: 点名序号: 指导教师: 实验地点:基础实验大楼 实验时间: 5月20日 2014-2015-2学期 信息与软件工程学院实验四-排序-实验报告
《数据结构》实验报告——排序.docx
排序操作实验报告
算法排序问题实验报告
动态查找表实验报告材料
北京理工大学数据结构实验报告4
实验报告-排序与查找