排序综合实验报告
数据结构 排序算法综合实验报告 姓名: xx x x 班级: 10电信1 学号: xxx 指导老师:胡圣荣 日期: 2012.12.15~2013.1.5 华南农业大学工程学院
算法基本思想: 1、插入排序:每次将一个待排序的记录,按其关键字大小插入到前面已经排序好的序列中的适当位置,直到全部记录插入完毕为止。 (1)直接插入排序:在排序过程中,每次都讲无序区中第一条记录插入到有序区中适当位置,使其仍保持有序。初始时,取第一条记录为有序区,其他记录为无序区。显然,随着排序过程的进行,有序区不断扩大,无序区不断缩小。最终无序区变为空,有序区中包含了所有的记录,排序结束。 (2)希尔排序:将排序表分成若干组,所有相隔为某个“增量”的记录为一组,在各组进行直接插入排序;初始时增量d1较大,分组较多(每组的记录数少),以后增量逐渐减少,分组减少(每组的记录数增多),直到最后增量为1(d1>d2>...>dt=1),所有记录放为一组,再整体进行一次直接插入排序。 2、交换排序:每次比较两个待排序的记录,如果发现他们关键字的次序与排序要求相反时就交换两者的位置,直到没有反序的记录为止。 (1)冒泡排序:设想排序表R[1]到R[n]垂直放置,将每个记录R[i]看作是重量为R[i].key 的气泡;根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R,凡违反本原则的轻气泡,就使其向上“漂浮”,如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。 (2)快速排序:在待排序的n个记录中任取一个作为“基准”,将其与记录分为两组,第一组中个记录的键值均小于或等于基准的键值,第二组中个记录的键值均大于或等于基准的键值,而基准就排在这两组中间(这也是该记录的最终位置),这称为一趟快速排序(或一次划分)。对所分成的两组重复上述方法,直到所有记录都排在适当位置为止。 3、选择排序:每次从待排序的记录中选出关键字最小(或最大)的记录,顺序放在已排好序的子序列的后面(或最前),直到全部记录排序完毕。 (1)直接选择排序:首先,所有记录组成初始无序区R[1]到R[n],从中选出键值最小的记录,与无序区第一个记录R[1]交换;新的无序区为R[2]到R[n],从中再选出键值最小的记录,与无序区第一个记录R[2]交换;类似,第i趟排序时R[1]到R[i-1]是有序区,无序区为R[i]到R[n],从中选出键值最小的记录,将它与无序区第一个记录R[i]交换,R[1]到R[i]变为新的有序区。因为每趟排序都使有序区中增加一个记录,所以,进行n-1趟排序后,整个排序表就全部有序了。 (2)堆排序:利用小根堆(或大根堆)来选取当前无序区中关键字最小(或最大)的记录来实现排序的。下面介绍利用大根堆来排序。首先,将初始无序区调整为一个大根堆,输出关键字最大的堆顶记录后,将剩下的n-1个记录在重建为堆,于是便得到次小值。如此反复执行,知道全部元素输出完,从而得到一个有序序列。 4、并归排序:指将若干个已排序的子表合成一个有序表。 (1)二路并归排序:开始时,将排序表R[1]到R[n]看成n个长度为1的有序子表,把这些子表两两并归,便得到n/2个有序的子表(当n为奇数时,并归后仍是有一个长度为1的子表);然后,再把这n/2个有序的子表两两并归,如此反复,直到最后得到一个程度为n的
查找与排序实验报告
实验四:查找与排序 【实验目的】 1.掌握顺序查找算法的实现。 2.掌握折半查找算法的实现。 【实验内容】 1.编写顺序查找程序,对以下数据查找37所在的位置。 5,13,19,21,37,56,64,75,80,88,92 2.编写折半查找程序,对以下数据查找37所在的位置。 5,13,19,21,37,56,64,75,80,88,92 【实验步骤】 1.打开VC++。 2.建立工程:点File->New,选Project标签,在列表中选Win32 Console Application,再在右边的框里为工程起好名字,选好路径,点OK->finish。 至此工程建立完毕。 3.创建源文件或头文件:点File->New,选File标签,在列表里选C++ Source File。给文件起好名字,选好路径,点OK。至此一个源文件就被添加到了你刚创建的工程之中。 4.写好代码 5.编译->链接->调试 #include "stdio.h" #include "malloc.h" #define OVERFLOW -1 #define OK 1 #define MAXNUM 100 typedef int Elemtype; typedef int Status; typedef struct {
Elemtype *elem; int length; }SSTable; Status InitList(SSTable &ST ) { int i,n; ST.elem = (Elemtype*) malloc (MAXNUM*sizeof (Elemtype)); if (!ST.elem) return(OVERFLOW); printf("输入元素个数和各元素的值:"); scanf("%d\n",&n); for(i=1;i<=n;i++) { scanf("%d",&ST.elem[i]); } ST.length = n; return OK; } int Seq_Search(SSTable ST,Elemtype key) { int i; ST.elem[0]=key; for(i=ST.length;ST.elem[i]!=key;--i); return i; } int BinarySearch(SSTable ST,Elemtype key) { int low,high,mid; low=1; high=ST.length;
排序操作实验报告
数据结构与算法设计 实验报告 (2016 — 2017 学年第1 学期) 实验名称: 年级: 专业: 班级: 学号: 姓名: 指导教师: 成都信息工程大学通信工程学院
一、实验目的 验证各种简单的排序算法。在调试中体会排序过程。 二、实验要求 (1)从键盘读入一组无序数据,按输入顺序先创建一个线性表。 (2)用带菜单的主函数任意选择一种排序算法将该表进行递增排序,并显示出每一趟排序过程。 三、实验步骤 1、创建工程(附带截图说明) 2、根据算法编写程序(参见第六部分源代码) 3、编译 4、调试 四、实验结果图 图1-直接输入排序
图2-冒泡排序 图3-直接选择排序 五、心得体会 与哈希表的操作实验相比,本次实验遇到的问题较大。由于此次实验中设计了三种排序方法导致我在设计算法时混淆了一些概念,设计思路特别混乱。虽然在理清思路后成功解决了直接输入和直接选择两种算法,但冒泡
排序的算法仍未设计成功。虽然在老师和同学的帮助下完成了冒泡排序的算法,但还需要多练习这方面的习题,平时也应多思考这方面的问题。而且,在直接输入和直接选择的算法设计上也有较为复杂的地方,对照书本做了精简纠正。 本次实验让我发现自己在算法设计上存在一些思虑不周的地方,思考问题过于片面,逻辑思维能力太过单薄,还需要继续练习。 六、源代码 要求:粘贴个人代码,以便检查。 #include #define MAXSIZE 100 typedef int KeyType; typedef int DataType; typedef struct{ KeyType key; DataType data; }SortItem,SqList[MAXSIZE]; /*******直接插入顺序表*******/ void InsertSort(SqList L,int n) { int i,j,x; SortItem p; for(i=1;i顺序表的查找、插入与删除实验报告
《数据结构》实验报告一 学院:班级: 学号:姓名: 日期:程序名 一、上机实验的问题和要求: 顺序表的查找、插入与删除。设计算法,实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求: 1.从键盘输入10个整数,产生顺序表,并输入结点值。 2.从键盘输入1个整数,在顺序表中查找该结点的位置。若找到,输出结点的位置;若找 不到,则显示“找不到”。 3.从键盘输入2个整数,一个表示欲插入的位置i,另一个表示欲插入的数值x,将x插 入在对应位置上,输出顺序表所有结点值,观察输出结果。 4.从键盘输入1个整数,表示欲删除结点的位置,输出顺序表所有结点值,观察输出结果。 二、源程序及注释: #include #include /*顺序表的定义:*/ #include #define ListSize 100 /*表空间大小可根据实际需要而定,这里假设为100*/ typedef int DataType; /*DataType可以是任何相应的数据类型如int, float或char*/ typedef struct { DataType data[ListSize]; /*向量data用于存放表结点*/ int length; /*当前的表长度*/ }SeqList; void main() { SeqList L; int i,x; int n=10; /*欲建立的顺序表长度*/ L.length=0; void CreateList(SeqList *L,int n); void PrintList(SeqList L,int n); int LocateList(SeqList L,DataType x); void InsertList(SeqList *L,DataType x,int i); void DeleteList(SeqList *L,int i);
数据结构实验报告-排序
本章共8道实验题目。 一、直接插入排序 1. 定义顺序表的存储结构 2. 初始化顺序表为空表 3. 输入10个元素创建含有10个元素的顺序表 4. 输出顺序表 5. 对顺序表进行直接插入排序(InsertSort) 6. 输出排序后的顺序表 例如: 11 938 669 507 117 261 708 343 300 602 11 938 669 507 117 261 708 343 300 602 11 117 261 300 343 507 602 669 708 938 程序: #include #include using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; #define MAXSIZE 100 typedef int KeyType; typedef char InfoType[256]; typedef struct { KeyType key; InfoType otherinfo; }RedType; typedef struct { RedType r[MAXSIZE+1]; int length; }SqList; //此处定义直接插入排序函数 int a[20]; int main()
{ int InsertSort; for (int i = 0; i < 10; ++i) { cin >> a[i]; cout << a[i] << " "; } cout << endl; sort(a, a+10); for (int i = 0; i < 10; ++i) cout << a[i] << " "; return 0; } 二、折半插入排序 1. 定义顺序表的存储结构 2. 初始化顺序表为空表 3. 输入10个元素创建含有10个元素的顺序表 4. 输出顺序表 5. 对顺序表进行折半插入排序(BInsertSort) 6. 输出排序后的顺序表 例如: 11 938 669 507 117 261 708 343 300 602 11 938 669 507 117 261 708 343 300 602 11 117 261 300 343 507 602 669 708 938 程序: #include #include using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; #define MAXSIZE 100 typedef int KeyType; typedef char InfoType[256];
河南工业大学实验报告——查找和排序(排序)——张伟龙
河南工业大学实验报告 课程名称数据结构实验项目实验三查找和排序(二)——排序院系信息学院计科系专业班级计科1203 姓名张伟龙学号 201216010313 指导老师范艳峰日期 2013.6.5 批改日期成绩 一实验目的 掌握希尔排序、快速排序、堆排序的算法实现。 二实验内容及要求 实验内容:1.实现希尔排序。 2.实现快速排序。 3. 实现堆排序。 (三选一) 实验要求:1. 根据所选题目,用C语言编写程序源代码。 2. 源程序必须编译调试成功,独立完成。 三实验过程及运行结果 选择第三题: Source Code: #include #include using namespace std; void HeapAdjust(int *a,int i,int size) //调整堆 { int lchild=2*i; //i的左孩子节点序号
int rchild=2*i+1; //i的右孩子节点序号 int max=i; //临时变量 if(i<=size/2) //如果i是叶节点就不用进行调整 { if(lchild<=size&&a[lchild]>a[max]) { max=lchild; } if(rchild<=size&&a[rchild]>a[max]) { max=rchild; } if(max!=i) { swap(a[i],a[max]); HeapAdjust(a,max,size); //避免调整之后以max为父节点的子树不是堆 } } } void BuildHeap(int *a,int size) //建立堆 { int i; for(i=size/2;i>=1;i--) //非叶节点最大序号值为size/2 { HeapAdjust(a,i,size); } }
排序问题实验报告
2010级数据结构实验报告 实验名称:排序 姓名:袁彬 班级: 2009211120 班内序号: 09 学号: 09210552 日期: 2010 年12 月19 日 1.实验要求 试验目的: 通过选择试验内容中的两个题目之一,学习、实现、对比各种排序的算法,掌握各种排序算法的优缺点,以及各种算法使用的情况。 试验内容: 题目一: 使用简单数组实现下面各种排序算法,并进行比较。 排序算法如下: ①插入排序; ②希尔排序 ③冒泡排序; ④快速排序; ⑤简单选择排序; ⑥堆排序 ⑦归并排序 ⑧基数排序 ⑨其他。 具体要求如下: ①测试数据分为三类:正序,逆序,随机数据。 ②对于这三类数据,比较上述排序算法中关键字的比较次数和移动次数(其中关键字交换记为三次移动)。 ③对于这三类数据,比较上述排序算法中不同算法的执行时间,精确到微妙。 ④对②和③的结果进行分析,验证上述各种算法的时间复杂度。 ⑤编写main()函数测试各种排序算法的正确性。 题目二: 使用链表实现下面各种排序算法,并进行比较。 排序算法如下: ①插入排序; ②冒泡排序; ③快速排序;
④简单选择排序; ⑤其他。 具体要求如下: ①测试数据分为三类:正序,逆序,随机数据。 ②对于这三类数据,比较上述排序算法中关键字的比较次数和移动次数(其中关键字交换记为三次移动)。 ③对于这三类数据,比较上述排序算法中不同算法的执行时间,精确到微妙(选作) ④对②和③的结果进行分析,验证上述各种算法的时间复杂度。 ⑤编写main()函数测试各种排序算法的正确性。 2. 程序分析 2.1 存储结构 程序中每一个算法均是用一个类来表示的,类中有自己的构造函数、排序函数。 程序的储存结构采用数组。数组的第一个位置不存储数据。数据从第二个位置开始。数组中的相对位置为数组的下标。 2.2 关键算法分析 ㈠、关键算法: 1、插入排序函数:Insert s ort(int n) ①、从2开始做循环,依次和前面的数进行比较:for(int i=2;i<=n;i++) ②、如果后面的比前面的小,则进行前移:if(number[i]=1;d=d/2) ②、在自己的间隔中进行简单插入排序,进行循环:for(int i=d+1;i<=n;i++) ③、如果后面的数据比前面的小,进行前移:if(number[i]0;j=j-d) ⑥、大的数据后移:number[j+d]=number[j]; ⑦、哨兵归位:number[j+d]=number[0]; 3、冒泡排序函数:Bubble s ort(int n) ①、设置有序无序的边界点:int pos=n; ②、当边界点不为空进行循环:while(pos!=0) ③、边界点传递给bound:int bound=pos; ④、从开始到边界点进行循环:for(int i=1;inumber[i+1]) ⑥、交换:number[0]=number[i];number[i]=number[i+1];number[i+1]=number[0]; ⑦、从小设置边界点:pos=i; 4、一趟快速排序函数:partion(int first,int end) ①、传递设置整个数据的起点和终点:int i=first;int j=end; ②、设置中轴:number[0]=number[i]; ③、当end大于first进行循环:while(i《数据结构》实验报告查找
实验四——查找 一、实验目的 1.掌握顺序表的查找方法,尤其是折半查找方法; 2.掌握二叉排序树的查找算法。 二、实验内容 1.建立一个顺序表,用顺序查找的方法对其实施查找; 2.建立一个有序表,用折半查找的方法对其实施查找; 3.建立一个二叉排序树,根据给定值对其实施查找; 4.对同一组数据,试用三种方法查找某一相同数据,并尝试进行性能分析。 三、实验预习内容 实验一包括的函数有:typedef struct ,创建函数void create(seqlist & L),输出函数void print(seqlist L),顺序查找int find(seqlist L,int number),折半查找int halffind(seqlist L,int number) 主函数main(). 实验二包括的函数有:结构体typedef struct,插入函数void insert(bnode * & T,bnode * S),void insert1(bnode * & T),创建函数void create(bnode * & T),查找函数bnode * search(bnode * T,int number),主函数main(). 四、上机实验 实验一: 1.实验源程序。 #include<> #define N 80 typedef struct { int number; umber; for(i=1;[i].number!=0;) { cin>>[i].name>>[i].sex>>[i].age; ++; cout<>[++i].number; } } umber<<"\t"<<[i].name<<"\t"<<[i].sex<<"\t"<<[i].age<查找排序实验报告
《编程实训》 实验报告书 专业:计算机科学与技术 班级:151班 学号: 姓名: 指导教师: 日期:2016年6月30日
目录 一、需求分析 (3) 1.任务要求 (3) 2.软件功能分析 (3) 3.数据准备 (3) 二、概要设计 (3) 1.功能模块图 (4) 2.模块间调用关系 (4) 3.主程序模块 (5) 4.抽象数据类型描述 (5) 三、详细设计 (6) 1.存储结构定义 (6) 2.各功能模块的详细设计 (7) 四、实现和调试 (7) 1.主要的算法 (7) 2.主要问题及解决 (8) 3.测试执行及结果 (8) 五、改进 (9) 六、附录 (9) 1.查找源程序 (9) 2.排序源程序 (9)
目录 1 需求分析 1.1 任务要求 对于从键盘随机输入的一个序列的数据,存入计算机内,给出各种查找算法的实现; 以及各种排序算法的实现。 1.2 软件功能分析 任意输入n个正整数,该程序可以实现各类查找及排序的功能并将结果输出。 1.3 数据准备 任意输入了5个正整数如下: 12 23 45 56 78 2 概要设计(如果2,3合并可以省略2.4) 2.1 功能模块图(注:含功能说明) 2.2 模块间调用关系 2.3 主程序模块 2.4 抽象数据类型描述 存储结构:数据结构在计算机中的表示(也称映像)叫做物理结构。又称为存储结构。数据类型(data type)是一个“值”的集合和定义在此集合上的一组操作的总称。 3 详细设计 3.1 存储结构定义 查找: typedef int ElemType ; //顺序存储结构 typedef struct { ElemType *elem; //数据元素存储空间基址,建表时按实际长度分配,号单元留空 int length; //表的长度
各种排序实验报告
【一】需求分析 课程题目是排序算法的实现,课程设计一共要设计八种排序算法。这八种算法共包括:堆排序,归并排序,希尔排序,冒泡排序,快速排序,基数排序,折半插入排序,直接插入排序。 为了运行时的方便,将八种排序方法进行编号,其中1为堆排序,2为归并排序,3为希尔排序,4为冒泡排序,5为快速排序,6为基数排序,7为折半插入排序8为直接插入排序。 【二】概要设计 1.堆排序 ⑴算法思想:堆排序只需要一个记录大小的辅助空间,每个待排序的记录仅占有一个存储空间。将序列所存储的元素A[N]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。算法的平均时间复杂度为O(N log N)。 ⑵程序实现及核心代码的注释: for(j=2*i+1; j<=m; j=j*2+1) { if(j=su[j]) break; su[i]=su[j]; i=j; } su[i]=temp; } void dpx() //堆排序 { int i,temp; cout<<"排序之前的数组为:"<=0; i--) { head(i,N); } for(i=N-1; i>0; i--) {
temp=su[i]; su[i]=su[0]; su[0]=temp; head(0,i-1); } cout<<"排序之后的数组为:"<数据结构内排序实验报告
一、实验目的 1、了解内排序都是在内存中进行的。 2、为了提高数据的查找速度,需要对数据进行排序。 3、掌握内排序的方法。 二、实验内容 1、设计一个程序e xp10—1.cpp实现直接插入排序算法,并输出{9,8,7,6,5,4,3,2,1,0}的排序 过程。 (1)源程序如下所示: //文件名:exp10-1.cpp #include #define MAXE 20 //线性表中最多元素个数 typedef int KeyType; typedef char InfoType[10]; typedef struct //记录类型 { KeyType key; //关键字项 InfoType data; //其他数据项,类型为InfoType } RecType; void InsertSort(RecType R[],int n) //对R[0..n-1]按递增有序进行直接插入排序 { int i,j,k; RecType temp; for (i=1;i=0 && temp.key二叉排序树实验报告
二叉排序树的实现 实验内容与要求 1) 实现二叉排序树,包括生成、插入,删除; 2) 对二叉排序树进行先根、中根、和后根非递归遍历; 3) 每次对树的修改操作和遍历操作的显示结果都需要在屏 幕上用树的形状表示出来。 实验方案 1. 选择链表的方式来构造节点,存储二叉排序树的节点。// 树的结构struct BSTNode { // 定义左右孩子指针 struct BSTNode *lchild,*rchild; // 节点的关键字 TElemType key; }; int depth=0; // 定义一个struct BSTNode 类型的指针typedef BSTNode *Tree; 2. 对树的操作有如下方法: // 创建二叉排序树 Tree CreatTree(Tree T) ; // 二叉树的深度,返回一个int 值为该树的深度 int TreeDepth(Tree T) // 树状输出二叉树,竖向输出 void PrintTree(Tree T , int layer) ; // 查找关键字,如果关键字存在则返回所在节点的父节点,如果关键字不存在则返回叶子所在的节点 Status SearchBST(Tree T , TElemType key , Tree f,Tree &p) ; // 向树中插入节点 Status InsertBST(Tree &T , TElemType e) ; // 删除节点 Status Delete(Tree &T) ;
// 删除指定节点,调用Delete(Tree &T) 方法 Status DeleteData(Tree &T , TElemType key) ; // 非递归先序遍历void x_print(Tree T); // 非递归中序遍历 Void z_print(Tree T ); // 非递归后序遍历 void h_print(Tree T); 3. 对二叉排序树非递归先根、中根、后根遍历,采用栈来存储一次遍历过的节点的形式来辅助实现 // 自定义类型以SElemType 作为栈中指针返回的值的类型 // 也就是要返回一个节点的指针 typedef Tree SElemType; // 栈的结构 struct Stack { // 栈底指针SElemType *base; // 栈顶指针SElemType *top; // 栈的容量 int stacksize; }; 4. 栈的操作方法: // 创建一个空栈 Status InitStack(Stack &S) // 获取栈顶元素并删除栈中该位置的元素SElemType Pop(Stack &S,SElemType &elem) // 获取栈顶元素返回栈顶元素不对栈做任何修改SElemType getTop(Stack S,SElemType &elem) // 删除栈顶元素 Status DeleteTop(Stack &S) // 往栈中压入数据 Status Push(Stack &S,SElemType elem) // 判断栈是否为空 Status IsEmpty(Stack S) 三、代码实现 #include #include using namespace std;