下载文档原格式
实验报告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个。
