拓扑排序 [基本要求] 用邻接表建立一个有向图的存储结构。利用拓扑排序算法输出该图的拓扑排序序列。 [编程思路] 首先图的创建，采用邻接表建立，逆向插入到单链表中，特别注意有向是不需要对称插入结点，且要把输入的字符在顶点数组中定位（LocateVex(Graph G,char *name)，以便后来的遍历操作，几乎和图的创建一样，图的顶点定义时加入int indegree，关键在于indegree 的计算，而最好的就是在创建的时候就算出入度，（没有采用书上的indegree【】数组的方法，那样会增加一个indegree算法，而是在创建的时候假如一句计数的代码(G.vertices[j].indegree)++;）最后调用拓扑排序的算法，得出拓扑序列。 [程序代码] 头文件： #define MAX_VERTEX_NUM 30 #define STACKSIZE 30 #define STACKINCREMENT 10 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define TRUE 1 #define FALSE 0 typedef int Status; typedef int InfoType; typedef int Status; typedef int SElemType; /* 定义弧的结构*/ typedef struct ArcNode{ int adjvex; /*该边所指向的顶点的位置*/ struct ArcNode *nextarc; /*指向下一条边的指针*/ InfoType info; /*该弧相关信息的指针*/
算法设计与分析基础 实验报告 应用数学学院 二零一六年六月
实验一插入排序算法 一、实验性质设计 二、实验学时14学时 三、实验目的 1、掌握插入排序的方法和原理。 2、掌握java语言实现该算法的一般流程。 四、实验内容 1、数组的输入。 2、输入、输出的异常处理。 3、插入排序的算法流程。 4、运行结果的输出。 五、实验报告 Ⅰ、算法原理 从左到右扫描有序的子数组，直到遇到一个大于（或小于）等于A[n-1]的元素，然后就把A[n-1]插在该元素的前面（或后面）。 插入排序基于递归思想。 Ⅱ、书中源代码 算法InsertionSort（A[0..n-1]） //用插入排序对给定数组A[0..n-1]排序 //输入：n个可排序元素构成的一个数组A[0..n-1] //输出：非降序排列的数组A[0..n-1] for i ←1 to n-1 do v ← A[i] j ← i-1 while j ≥0and A[j] > v do A[j+1] ← A[j] j ← j-1 A[j+1] ← v
Ⅲ、Java算法代码： import java.util.*; public class Charu { public static void main(String[] args) { int n = 5; int a[] = new int[n]; int s = a.length; int i = 0, j = 0, v = 0; System.out.println("请输入若干个数字："); Scanner sc = new Scanner(System.in); try { while (i < s) { a[i] = sc.nextInt(); i++; } for (i = 1; i
《数据结构》实验报告排序实验题目： 输入十个数，从插入排序，快速排序，选择排序三类算法中各选一种编程实现。 实验所使用的数据结构内容及编程思路： 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 次记录移动(赋值)的操作。而实际上，
算法与数据结构 实验报告 系（院）：计算机科学学院 专业班级：软工11102 姓名：潘香杰 学号： 201104449 班级序号： 18 指导教师：詹泽梅老师 实验时间：2013.6.17 - 2013.6.29 实验地点：4号楼5楼机房
目录 1、课程设计目的．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 2、设计任务．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 3、设计方案．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 4、实现过程．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 5、测试．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 6、使用说明．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 7、难点与收获．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 8、实现代码．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 9、可改进的地方．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．
算法与数据结构课程设计是在学完数据结构课程之后的实践教学环节。本实践教学是培养学生数据抽象能力，进行复杂程序设计的训练过程。要求学生能对所涉及问题选择合适的数据结构、存储结构及算法，并编写出结构清楚且正确易读的程序，提高程序设计基本技能和技巧。 一．设计目的 1．提高数据抽象能力。根据实际问题，能利用数据结构理论课中所学到的知识选择合适的逻辑结构以及存储结构，并设计出有效解决问题的算法。 2．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3．初步了解开发过程中问题分析、整体设计、程序编码、测试等基本方法和技能。二．设计任务 设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。内容如下： ①创建无向图的邻接表 ②无向图的深度优先遍历 ③无向创建无向图的邻接矩阵 ④无向图的基本操作及应用 ⑤图的广度优先遍历 1．有向图的基本操作及应用 ①创建有向图的邻接矩阵 ②创建有向图的邻接表 ③拓扑排序 2．无向网的基本操作及应用 ①创建无向网的邻接矩阵 ②创建无向网的邻接表 ③求最小生成树 3．有向网的基本操作及应用 ①创建有向网的邻接矩阵 ②创建有向网的邻接表 ③关键路径 ④单源最短路径 三．设计方案 第一步：根据设计任务，设计DOS菜单，菜单运行成果如图所示：
《排序问题求解》实验报告 一、算法的基本思想 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 电子科技大学实验报告 课程名称：数据结构与算法 学生姓名： 学号： 点名序号： 指导教师： 实验地点：基础实验大楼 实验时间： 5月20日 2014-2015-2学期 信息与软件工程学院 实验报告（二） 学生姓名学号：指导教师： 实验地点：基础实验大楼实验时间：5月20日 一、实验室名称：软件实验室 二、实验项目名称：数据结构与算法—排序与查找 三、实验学时：4 四、实验原理： 快速排序的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是： 1）设置两个变量I、J，排序开始的时候I：=1，J：=N 2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]； 3）从J开始向前搜索，即（J：=J-1），找到第一个小于X的值，两者交换； 4）从I开始向后搜索，即（I：=I+1），找到第一个大于X的值，两者交换； 5）重复第3、4步，直到I=J。 二分法查找（折半查找）的基本思想： （1）确定该区间的中点位置：mid=（low+high）/2 min代表区间中间的结点的位置，low代表区间最左结点位置，high代表区间最右结点位置（2）将待查a值与结点mid的关键字（下面用R[mid].key）比较，若相等，则查找成功，否则确定新的查找区间： A)如果R[mid].key>a，则由表的有序性可知，R[mid].key右侧的值都大于a，所以等于a的关键字如果存在，必然在R[mid].key左边的表中,这时high=mid-1; B)如果R[mid].key 《离散数学》 课程设计 学院计算机学院 学生姓名 学号 指导教师 评阅意见 提交日期 2011 年 11 月 25 日 引言 《离散数学》是现代数学的一个重要分支，也是计算机科学与技术，电子信息技术，生物技术等的核心基础课程。它是研究离散量（如整数、有理数、有限字母表等）的数学结构、性质及关系的学问。它一方面充分地描述了计算机科学离散性的特点，为学生进一步学习算法与数据结构、程序设计语言、操作系统、编译原理、电路设计、软件工程与方法学、数据库与信息检索系统、人工智能、网络、计算机图形学等专业课打好数学基础；另一方面，通过学习离散数学课程，学生在获得离散问题建模、离散数学理论、计算机求解方法和技术知识的同时，还可以培养和提高抽象思维能力和严密的逻辑推理能力，为今后爱念族皮及用计算机处理大量的日常事务和科研项目、从事计算机科学和应用打下坚实基础。特别是对于那些从事计算机科学与理论研究的高层次计算机人员来说，离散数学更是必不可少的基础理论工具。 实验一、编程判断一个二元关系的性质（是否具有自反性、反自反性、对称性、反对称性和传递性） 一、前言引语：二元关系是离散数学中重要的内容。因为事物之间总是可以根据需要确定相应的关系。从数学的角度来看，这类联系就是某个集合中元素之 间存在的关系。 二、数学原理：自反、对称、传递关系 设A和B都是已知的集合，R是A到B的一个确定的二元关系，那么集合R 就是A×B的一个合于{()∈A×}的子集合 设R是集合A上的二元关系： 自反关系：对任意的x∈A,都满足<>∈R，则称R是自反的，或称R具有自反性，即R在A上是自反的?(?x)((x∈A)→(<>∈R))=1 对称关系：对任意的∈A，如果<>∈R，那么<>∈R，则称关系R是对称的，或称R具有对称性，即R在A上是对称的? (?x)(?y)((x∈A)∧(y∈A)∧(<>∈R)→(<>∈R))=1 传递关系：对任意的∈A，如果<>∈R且<>∈R，那么<>∈R，则称关系R是传递的，或称R具有传递性，即R在A上是传递的? (?x)(?y)(?z)[(x∈A)∧(y∈A)∧(z ∈A)∧((<>∈R)∧(<>∈R)→(<>∈R))]=1 三、实验原理：通过二元关系与关系矩阵的联系，可以引入N维数组，以数组的运算来实现二元关系的判断。 图示： 数据结构 排序算法综合实验报告 姓名： 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、学会比较各种排序与查找算法的优劣。 3、学会针对所给问题选用最适合的算法。 4、掌握利用常用的排序与选择算法的思想来解决一般问题的方法和技巧。 二、实验内容 [问题描述] 对学生的基本信息进行管理。 [基本要求] 设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能：1．总成绩要求自动计算； 2．查询：分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）； 3．排序：分别按学生的学号、成绩1、成绩2、总成绩进行排序（要求至少用两种排序算法实现）。 [测试数据] 由学生依据软件工程的测试技术自己确定。 三、实验前的准备工作 1、掌握哈希表的定义，哈希函数的构造方法。 2、掌握一些常用的查找方法。 1、掌握几种常用的排序方法。 2、掌握直接排序方法。 四、实验报告要求 1、实验报告要按照实验报告格式规范书写。 2、实验上要写出多批测试数据的运行结果。 3、结合运行结果，对程序进行分析。 五、算法设计 a、折半查找 设表长为n，low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值。初始时，令low=1,high=n,mid=(low+high)/2，让key与mid指向的记录比较， 若key==r[mid].key，查找成功 若key 数据结构与算法设计 实验报告 （2016 — 2017 学年第1 学期） 实验名称： 年级： 专业： 班级： 学号： 姓名： 指导教师： 成都信息工程大学通信工程学院 一、实验目的 验证各种简单的排序算法。在调试中体会排序过程。 二、实验要求 （1）从键盘读入一组无序数据，按输入顺序先创建一个线性表。 （2）用带菜单的主函数任意选择一种排序算法将该表进行递增排序，并显示出每一趟排序过程。 三、实验步骤 1、创建工程（附带截图说明） 2、根据算法编写程序（参见第六部分源代码） 3、编译 4、调试 四、实验结果图 图1-直接输入排序 图2-冒泡排序 图3-直接选择排序 五、心得体会 与哈希表的操作实验相比，本次实验遇到的问题较大。由于此次实验中设计了三种排序方法导致我在设计算法时混淆了一些概念，设计思路特别混乱。虽然在理清思路后成功解决了直接输入和直接选择两种算法，但冒泡 排序的算法仍未设计成功。虽然在老师和同学的帮助下完成了冒泡排序的算法，但还需要多练习这方面的习题，平时也应多思考这方面的问题。而且，在直接输入和直接选择的算法设计上也有较为复杂的地方，对照书本做了精简纠正。 本次实验让我发现自己在算法设计上存在一些思虑不周的地方，思考问题过于片面，逻辑思维能力太过单薄，还需要继续练习。 六、源代码 要求：粘贴个人代码，以便检查。 #include 《数据结构》实验报告一 学院：班级： 学号：姓名： 日期：程序名 一、上机实验的问题和要求： 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： 1.从键盘输入10个整数，产生顺序表，并输入结点值。 2.从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找 不到，则显示“找不到”。 3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插 入在对应位置上，输出顺序表所有结点值，观察输出结果。 4.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。 二、源程序及注释： #include 实验六图的应用及其实现 一、实验目的 1．进一步功固图常用的存储结构。 2．熟练掌握在图的邻接表实现图的基本操作。 3．理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。 二、实验内容 [题目一]：从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网的类型定义和基本操作,完成上述功能。 测试数据：教材图7.28 [题目二]：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。 测试数据：教材图7.29 三、实验步骤 ㈠、数据结构与核心算法的设计描述 基本数据结构： #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; /* Status 是函数的类型,其值是函数结果状态代码，如OK 等*/ #define INFINITY INT_MAX //定义无穷大∞ #define MAX_VERTEX_NUM 20 typedef int V ertexType; typedef int InfoType; typedef struct ArcNode // 表结点定义 { InfoType info; int adjvex; //邻接点域，存放与V i邻接的点在表头数组中的位置ArcNode *nextarc; //链域，指示依附于vi的下一条边或弧的结点， }ArcNode; typedef struct VNode //表头结点 { int data; //存放顶点信息 struct ArcNode *firstarc; //指示第一个邻接点 }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct { //图的结构定义 本章共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 { 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 实验四：查找与排序 【实验目的】 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; 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.掌握顺序表的查找方法，尤其是折半查找方法； 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< 《编程实训》 实验报告书 专业：计算机科学与技术 班级：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 temp=su[i]; su[i]=su[0]; su[0]=temp; head(0,i-1); } cout<<"排序之后的数组为："<实验报告-排序与查找
离散数学实验报告四个实验
排序综合实验报告
(完整word版)查找、排序的应用 实验报告
排序操作实验报告
顺序表的查找、插入与删除实验报告
图的应用的实验报告
数据结构实验报告-排序
查找与排序实验报告
排序问题实验报告
《数据结构》实验报告查找
查找排序实验报告
各种排序实验报告
相关主题
文本预览