下载文档原格式
实验报告3实验名称：数据结构与软件设计实习题目：内部排序算法比较专业：生物信息学班级：01 姓名：学号：实验日期：2010.07.24一、实验目的：比较冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序；二、实验要求：待排序长度不小于100，数据可有随机函数产生，用五组不同输入数据做比较，比较的指标为关键字参加比较的次数和关键字移动的次数；对结果做简单的分析，包括各组数据得出结果的解释；设计程序用顺序存储。
三、实验内容对各种内部排序算法的时间复杂度有一个比较直观的感受，包括关键字比较次数和关键字移动次数。
将排序算法进行合编在一起，可考虑用顺序执行各种排序算法来执行，最后输出所有结果。
四、实验编程结果或过程：1. 数据定义typedef struct { KeyType key; }RedType; typedef struct { RedType r[MAXSIZE+1]; int length;}SqList;2. 函数如下，代码详见文件“排序比较.cpp”int Create_Sq(SqList &L)void Bubble_sort(SqList &L)//冒泡排序void InsertSort(SqList &L)//插入排序void SelectSort(SqList &L) //简单选择排序int Partition(SqList &L,int low,int high) void QSort(SqList &L,int low,int high)//递归形式的快速排序算法void QuickSort(SqList &L)void ShellInsert(SqList &L,int dk)//希尔排序void ShellSort(SqList &L,int dlta[ ])3. 运行测试结果，运行结果无误，如下图语速个数为20元素个数为100错误调试无。
数据结构课程设计—内部排序算法比较在计算机科学领域中，数据的排序是一项非常基础且重要的操作。
内部排序算法作为其中的关键部分，对于提高程序的运行效率和数据处理能力起着至关重要的作用。
本次课程设计将对几种常见的内部排序算法进行比较和分析，包括冒泡排序、插入排序、选择排序、快速排序和归并排序。
冒泡排序是一种简单直观的排序算法。
它通过重复地走访要排序的数列，一次比较两个数据元素，如果顺序不对则进行交换，并一直重复这样的走访操作，直到没有要交换的数据元素为止。
这种算法的优点是易于理解和实现，但其效率较低，在处理大规模数据时性能不佳。
因为它在最坏情况下的时间复杂度为 O(n²)，平均时间复杂度也为O(n²)。
插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，直到整个序列有序。
插入排序在数据量较小时表现较好，其平均时间复杂度和最坏情况时间复杂度也都是 O(n²)，但在某些情况下，它的性能可能会优于冒泡排序。
选择排序则是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。
以此类推，直到全部待排序的数据元素排完。
选择排序的时间复杂度同样为O(n²)，但它在某些情况下的交换操作次数可能会少于冒泡排序和插入排序。
快速排序是一种分治的排序算法。
它首先选择一个基准元素，将数列分成两部分，一部分的元素都比基准小，另一部分的元素都比基准大，然后对这两部分分别进行快速排序。
快速排序在平均情况下的时间复杂度为 O(nlogn)，最坏情况下的时间复杂度为 O(n²)。
然而，在实际应用中，快速排序通常表现出色，是一种非常高效的排序算法。
归并排序也是一种分治算法，它将待排序序列分成若干个子序列，每个子序列有序，然后将子序列合并成一个有序序列。
数据结构课程设计报告几种排序算法的演示1、需求分析:运行环境:Microsoft Visual Studio 20052、程序实现功能:3、通过用户键入的数据, 经过程序进行排序, 最后给予数据由小到大的输出。
排序的方式包含教材中所介绍的几种常用的排序方式：直接插入排序、折半插入排序、冒泡排序、快速排序、选择排序、堆排序、归并排序。
每种排序过程中均显示每一趟排序的细节。
程序的输入:输入所需排序方式的序号。
输入排序的数据的个数。
输入具体的数据元素。
程序的输出:输出排序每一趟的结果, 及最后排序结果1、设计说明:算法设计思想:a交换排序（冒泡排序、快速排序）交换排序的基本思想是: 对排序表中的数据元素按关键字进行两两比较, 如果发生逆序（即排列顺序与排序后的次序正好相反）, 则两者交换位置, 直到所有数据元素都排好序为止。
b插入排序（直接插入排序、折半插入排序）插入排序的基本思想是: 每一次设法把一个数据元素插入到已经排序的部分序列的合适位置, 使得插入后的序列仍然是有序的。
开始时建立一个初始的有序序列, 它只包含一个数据元素。
然后, 从这个初始序列出发不断插入数据元素, 直到最后一个数据元素插到有序序列后, 整个排序工作就完成了。
c选择排序（简单选择排序、堆排序）选择排序的基本思想是: 第一趟在有n个数据元素的排序表中选出关键字最小的数据元素, 然后在剩下的n-1个数据元素中再选出关键字最小（整个数据表中次小）的数据元素, 依次重复, 每一趟（例如第i趟, i=1, …, n-1）总是在当前剩下的n-i+1个待排序数据元素中选出关键字最小的数据元素, 作为有序数据元素序列的第i个数据元素。
等到第n-1趟选择结束, 待排序数据元素仅剩下一个时就不用再选了, 按选出的先后次序所得到的数据元素序列即为有序序列, 排序即告完成。
d归并排序（两路归并排序）1、两路归并排序的基本思想是: 假设初始排序表有n个数据元素, 首先把它看成是长度为1的首尾相接的n个有序子表（以后称它们为归并项）, 先做两两归并, 得n/2上取整个长度为2的归并项（如果n为奇数, 则最后一个归并项的长度为1）；再做两两归并, ……, 如此重复, 最后得到一个长度为n的有序序列。
数据结构实验报告本文是范文，仅供参考写作，禁止抄袭本文内容上传提交，违者取消写作资格，成绩不合格！实验名称：排序算法比较提交文档学生姓名：提交文档学生学号：同组成员名单：指导教师姓名：排序算法比较一、实验目的和要求1、设计目的1．掌握各种排序的基本思想。
2．掌握各种排序方法的算法实现。
3．掌握各种排序方法的优劣分析及花费的时间的计算。
4．掌握各种排序方法所适应的不同场合。
2、设计内容和要求利用随机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间二、运行环境（软、硬件环境）软件环境：Vc6.0编程软件运行平台： Win32硬件：普通个人pc机三、算法设计的思想1、冒泡排序：bubbleSort()基本思想: 设待排序的文件为r[1..n]第1趟(遍)：从r[1]开始,依次比较两个相邻记录的关键字r[i].key和r[i+1].key,若r[i].key>r[i+1].key，则交换记录r[i]和r[i+1]的位置；否则,不交换。
(i=1,2,...n-1)第1趟之后,n个关键字中最大的记录移到了r[n]的位置上。
第2趟：从r[1]开始,依次比较两个相邻记录的关键字r[i].key和r[i+1].key,若r[i].key>r[i+1].key，则交换记录r[i]和r[i+1]的位置；否则,不交换。
(i=1,2,...n-2)第2趟之后,前n-1个关键字中最大的记录移到了r[n-1]的位置上，作完n-1趟,或者不需再交换记录时为止。
2、选择排序：selSort()每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
选择排序不像冒泡排序算法那样先并不急于调换位置，第一轮（k=1）先从array[k]开始逐个检查，看哪个数最小就记下该数所在的位置于minlIndex中，等一轮扫描完毕，如果找到比array[k-1]更小的元素，则把array[minlIndex]和a[k-1]对调，这时array[k]到最后一个元素中最小的元素就换到了array[k-1]的位置。
实验报告3实验名称：数据结构与软件设计实习题目：内部排序算法比较专业：生物信息学班级：01 姓名：学号：实验日期：2010.07.24一、实验目的：比较冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序；二、实验要求：待排序长度不小于100，数据可有随机函数产生，用五组不同输入数据做比较，比较的指标为关键字参加比较的次数和关键字移动的次数；对结果做简单的分析，包括各组数据得出结果的解释；设计程序用顺序存储。
三、实验内容对各种内部排序算法的时间复杂度有一个比较直观的感受，包括关键字比较次数和关键字移动次数。
将排序算法进行合编在一起，可考虑用顺序执行各种排序算法来执行，最后输出所有结果。
四、实验编程结果或过程：1. 数据定义typedef struct { KeyType key; }RedType; typedef struct { RedType r[MAXSIZE+1]; int length;}SqList;2. 函数如下，代码详见文件“排序比较.cpp”int Create_Sq(SqList &L)void Bubble_sort(SqList &L)//冒泡排序void InsertSort(SqList &L)//插入排序void SelectSort(SqList &L) //简单选择排序int Partition(SqList &L,int low,int high) void QSort(SqList &L,int low,int high)//递归形式的快速排序算法void QuickSort(SqList &L)void ShellInsert(SqList &L,int dk)//希尔排序void ShellSort(SqList &L,int dlta[ ])3. 运行测试结果，运行结果无误，如下图语速个数为20元素个数为100错误调试无。
《数据结构与算法》实验报告一、需求分析问题描述：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。
试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
基本要求：（l）对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。
（2）待排序表的表长不小于100000；其中的数据要用伪随机数程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。
（3）最后要对结果作简单分析，包括对各组数据得出结果波动大小的解释。
数据测试：二．概要设计1.程序所需的抽象数据类型的定义：typedef int BOOL; //说明BOOL是int的别名typedef struct StudentData { int num; //存放关键字}Data; typedef struct LinkList { int Length; //数组长度Data Record[MAXSIZE]; //用数组存放所有的随机数} LinkList int RandArray[MAXSIZE]; //定义长度为MAXSIZE的随机数组void RandomNum() //随机生成函数void InitLinkList(LinkList* L) //初始化链表BOOL LT(int i, int j,int* CmpNum) //比较i和j 的大小void Display(LinkList* L) //显示输出函数void ShellSort(LinkList* L, int dlta[], int t,int* CmpNum, int* ChgNum) //希尔排序void QuickSort (LinkList* L, int* CmpNum, int* ChgNum) //快速排序void HeapSort (LinkList* L, int* CmpNum, int* ChgNum) //堆排序void BubbleSort(LinkList* L, int* CmpNum, int* ChgNum) //冒泡排序void SelSort(LinkList* L, int* CmpNum, int* ChgNum) //选择排序void Compare(LinkList* L,int* CmpNum, int* ChgNum) //比较所有排序2 .各程序模块之间的层次（调用）关系：二、详细设计typedef int BOOL; //定义标识符关键字BOOL别名为int typedef struct StudentData //记录数据类型{int num; //定义关键字类型}Data; //排序的记录数据类型定义typedef struct LinkList //记录线性表{int Length; //定义表长Data Record[MAXSIZE]; //表长记录最大值}LinkList; //排序的记录线性表类型定义int RandArray[MAXSIZE]; //定义随机数组类型及最大值/******************随机生成函数********************/void RandomNum(){int i; srand((int)time(NULL)); //用伪随机数程序产生伪随机数for(i=0; i小于MAXSIZE; i++) RandArray[i]<=(int)rand(); 返回;}/*****************初始化链表**********************/void InitLinkList(LinkList* L) //初始化链表{int i;memset(L,0,sizeof(LinkList));RandomNum();for(i=0; i小于<MAXSIZE; i++)L->Record[i].num<=RandArray[i]; L->Length<=i;}BOOL LT(int i, int j,int* CmpNum){(*CmpNum)++; 若i<j) 则返回TRUE; 否则返回FALSE;}void Display(LinkList* L){FILE* f; //定义一个文件指针f int i;若打开文件的指令不为空则//通过文件指针f打开文件为条件判断{ //是否应该打开文件输出“can't open file”;exit(0); }for (i=0; i小于L->Length; i++)fprintf(f,"%d\n",L->Record[i].num);通过文件指针f关闭文件;三、调试分析1.调试过程中遇到的问题及经验体会:在本次程序的编写和调试过程中，我曾多次修改代码，并根据调试显示的界面一次次调整代码。
数据结构课程设计题目以下7个题目任选其一。
1．排序算法比较利用随机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序，并且（1）统计每一种排序上机所花费的时间。
（2）统计在完全正序，完全逆序情况下记录的比较次数和移动次数。
（3）比较的指标为关键字的比较次数和记录的移动次数(一次记录交换计为3次移动)。
（4）对结果作简单分析，包括对各组数据得出结果波动大小的解释。
2．图的深度遍历对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用堆栈的五种基本运算（清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现图的深度优先搜索遍历。
画出搜索顺序示意图。
3．图的广度遍历对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度优先搜索遍历。
画出搜索顺序示意图。
4．二叉树的遍历对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。
画出搜索顺序示意图。
5．链表操作利用链表的插入运算建立线性链表，然后利用链表的查找、删除、计数、输出等运算反复实现链表的这些操作（插入、删除、查找、计数、输出单独写成函数的形式），并能在屏幕上输出操作前后的结果。
画出搜索顺序示意图。
6．一元稀疏多项式简单计数器（1）输入并建立多项式（2）输出多项式，输出形式为整数序列：n，c1，e1，c2，e2……cn，en，其中n是多项式的项数，ci，ei分别为第i项的系数和指数。
序列按指数降序排列。
（3）多项式a和b相加，建立多项式a+b，输出相加的多项式。
（4）多项式a和b相减，建立多项式a-b，输出相减的多项式。
用带头结点的单链表存储多项式。
测试数据：（1）(2x+5x8-3.1x11)+(7-5x8+11x9)（2）(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15)（3）(x+x2+x3)+0（4）(x+x3)-(-x-x-3)7．实现两个链表的合并基本功能要求：（1）建立两个链表A和B，链表元素个数分别为m和n个。
数据结构课程设计题⽬《数据结构》课程设计题⽬1. 排序算法的性能分析问题描述设计⼀个测试程序，⽐较⼏种内部排序算法的关键字⽐较次数和移动次数以取得直观感受。
基本要求（1）对冒泡排序、直接排序、选择排序、箱⼦排序、堆排序、快速排序及归并排序算法进⾏⽐较。
（2）待排序表的表长不⼩于100，表中数据随机产⽣，⾄少⽤5组不同数据作⽐较，⽐较指标：关键字参加⽐较次数和关键字的移动次数（关键字交换记为3次移动）。
（3）输出⽐较结果。
选做内容（1）对不同表长进⾏⽐较。
（2）验证各算法的稳定性。
（3）输出界⾯的优化。
2. 排序算法思想的可视化演⽰—1基本要求排序数据随机产⽣，针对随机案例，对冒泡排序、箱⼦排序、堆排序、归并算法，提供排序执⾏过程的动态图形演⽰。
3. 排序算法思想的可视化演⽰—2基本要求排序数据随机产⽣，针对随机案例，，对插⼊排序、选择排序、基数排序、快速排序算法，提供排序执⾏过程的动态图形演⽰。
4. 线性表的实现与分析基本要求①设计并实现线性表。
②线性表分别采取数组（公式化描述）、单链表、双向链表、间接寻址存储⽅式③针对随机产⽣的线性表实例，实现线性表的插⼊、删除、搜索操作动态演⽰(图形演⽰)。
5. 等价类实现及其应⽤问题描述：某⼯⼚有⼀台机器能够执⾏n个任务，任务i的释放时间为r i（是⼀个整数），最后期限为d i（也是整数）。
在该机上完成每个任务都需要⼀个单元的时间。
⼀种可⾏的调度⽅案是为每个任务分配相应的时间段，使得任务i的时间段正好位于释放时间和最后期限之间。
⼀个时间段不允许分配给多个任务。
基本要求：使⽤等价类实现以上机器调度问题。
等价类分别采取两种数据结构实现。
6. ⼀元稀疏多项式计算器问题描述设计⼀个⼀元稀疏多项式简单计算器。
基本要求⼀元稀疏多项式简单计算器的基本功能是：（1）输⼊并建⽴多项式；（2）输出多项式，输出形式为整数序列：n，c1，e1，c2，e2，…,c n，e n，其中n是多项式的项数，c i，e i，分别是第i项的系数和指数，序列按指数降序排序；（3）多项式a和b相加，建⽴多项式a+b；（4）多项式a和b相减，建⽴多项式a-b；（5）计算多项式在x处的值；（6）计算器的仿真界⾯（选做）7. 长整数的代数计算问题描述应⽤线性数据结构解决长整数的计算问题。
数据结构课程设计选题数据结构课程设计选题题⽬选题⼀：迷宫与栈问题【问题描述】以⼀个mXn的长⽅阵表⽰迷宫，0和1分别表⽰迷宫中的通路和障碍。
设计⼀个程序，对任意设定的迷宫，求出⼀条从⼊⼝到出⼝的通路，或得出没有通路的结论。
【任务要求】1)⾸先实现⼀个以链表作存储结构的栈类型，然后编写⼀个求解迷宫的⾮递归程序。
求得的通路以三元组（i，j，d）的形式输出。
其中：（i，j）指⽰迷宫中的⼀个坐标，d表⽰⾛到下⼀坐标的⽅向。
如，对于下列数据的迷宫，输出⼀条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），…。
2)编写递归形式的算法，求得迷宫中所有可能的通路。
3)以⽅阵形式输出迷宫及其通路。
【测试数据】迷宫的测试数据如下：左上⾓（0，1）为⼊⼝，右下⾓（8，9）为出⼝。
出⼝出⼝选题⼆：算术表达式与⼆叉树【问题描述】⼀个表达式和⼀棵⼆叉树之间，存在着⾃然的对应关系。
写⼀个程序，实现基于⼆叉树表⽰的算术表达式的操作。
【任务要求】假设算术表达式Expression内可以含有变量（a～z）、常量（0～9）和⼆元运算符（+，-，*，/，^(乘幂)）。
实现以下操作：1)ReadExpre(E)—以字符序列的形式输⼊语法正确的前缀表达式并构造表达式E。
2)WriteExpre(E)—⽤带括弧的中缀表达式输出表达式E。
3)Assign(V,c)—实现对变量V的赋值（V=c），变量的初值为0。
4)Value(E)—对算术表达式E求值。
5)CompoundExpr（P，E1，E2）--构造⼀个新的复合表达式（E1）P（E2）【测试数据】1)分别输⼊0；a；-91；+a*bc；+*5^x2*8x；+++*3^x3*2^x2x6并输出。
2)每当输⼊⼀个表达式后，对其中的变量赋值，然后对表达式求值。
选题三：银⾏业务模拟与离散事件模拟【问题描述】假设某银⾏有4个窗⼝对外接待客户，从早晨银⾏开门（开门9：00am，关门5：00pm）起不断有客户进⼊银⾏。
数据结构课程设计[排序综合]学生姓名：学生学号：院（系）：计算机科学与信息技术学院年级专业：指导教师：付丹丹二〇一一年十二月2- 3 - 3摘要数据结构是由数据元素依据某种逻辑联系组织起来的。
对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。
在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。
许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。
许多时候，确定了数据结构后，算法就容易得到了。
有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。
不论哪种情况，选择合适的数据结构都是非常重要的。
排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，其中包含冒泡排序，直接插入排序，简单选择排序，希尔排序，快速排序，堆排序等，各有其特点。
对排序算法比较的分析可以遵循若干种不同的准则，通常以排序过程所需要的算法步数作为度量，有时也以排序过程中所作的键比较次数作为度量。
特别是当作一次键比较需要较长时间，例如，当键是较长的字符串时，常以键比较次数作为排序算法计算时间复杂性的度量。
当排序时需要移动记录，且记录都很大时，还应该考虑记录的移动次数。
究竟采用哪种度量方法比较合适要根据具体情况而定。
在下面的讨论中我们主要考虑用比较的次数作为复杂性的度量。
41概要1.1设计目的数据结构与算法课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。
数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。
学习数据结构与算法是为了将实际问题中涉及的对象在计算机中表示出来并对它们进行处理。
