C语言（数据结构）复习资料

　　2019年9月
　　目 录
　　实验一 顺序表与链表基本操作实现及应用 1
　　实验二 栈和队列综合应用 4
　　实验三 二叉树的构造与应用 7
　　实验四 用图搜索方法求解迷宫问题 11
　　实验五 计算各种排序算法的绝对执行时间 16
　　实验一 顺序表与链表基本操作实现及应用
　　一、实验目的
　　1.复习应用VC++ 6.0程序开发环境编写、运行和调试C/C++应用程序的相关内容；
　　2.通过实验，掌握应用数据结构理论知识解决实际问题的一般方法和过程；
　　3.掌握线性表顺序存储结构和链式存储结构的程序实现方法及应用场合；
　　4.掌握顺序表和单链表基本运算的实现方法及结构特点；
　　5.应用线性表的相关知识解决一般的应用问题
　　二、实验任务及要求
　　Part Ⅰ（2学时）
　　1、复习、预习并完成以下内容
　　（1）复习VC++ 6.0开发环境的使用，创建Win32控制台项目，使用常用的IO函数编写一个简单的程序，进行编译、运行和调试。测试实验教材P2-1.1-验证实验。
　　（2）预习实验教材P10-2.1-实验题1，编写调试实验题1的源程序，课前编辑通过，将源程序拷贝到U盘或上传到校ftp服务器，上机时作为基本函数使用。具体包括线性表以下基本运算的实现。
　　为了方便起见，结点数值类型ElemType可定义为整数或者字符型
　　void InitList(SqList *&L); //初始化线性表
　　void DestroyList(SqList * L); //销毁线性表
　　bool ListEmpty(SqList * L); // 判断线性表是否为空
　　int ListLength(SqList * L); //求线性表的长度
　　void DispList(SqList * L); //显示线性表数据结点的值
　　bool GetElem(SqList *L,int i,ElemType &e);
　　//获取表L中指定位置的结点值
　　int LocateElem(SqList *L, ElemType e);
　　//查找表L中值为e的第1个结点的序号
　　bool ListInsert(SqList *&L,int i, ElemType e);
　　//在表L的第i个位置插入值为e的新结点
　　bool ListDelete(SqList *&L,int i, ElemType &e);
　　//删除表L中第i个元素。
　　（3）提前准备上机实验内容的代码，课堂调试运行。
　　2、上机实验内容
　　（1）在顺序表基本运算中增加以下基本功能
　　①替换顺序表中指定位置上的节点元素的值
　　②获取顺序表中指定节点的前驱节点
　　③获取顺序表中指定节点的后继节点
　　④删除结点数值在[X,Y]之间的数据，X,Y为用户输入的结点数值。
　　（2）设计一个高效算法，将顺序表L中的所有元素逆置，要求算法的空间复杂度为O(1)。应用前面实现的一些基本运算实现，在该工程主函数中对该算法进行验证。
　　算法设计提示：扫描顺序表L的前半部分，对元素L->data[i]（0<=ilength/2），将其与后半部分对应元素L->data[length-i-1]进行对换。
　　Part Ⅱ（2学时）
　　1、预习内容
　　（1）完成实验教材P13-2.1-实验题2，保存代码备用。主要包括以下基本运算：
　　void InitList(LinkNode *&L); //初始化单链表
　　void DestroyList(LinkNode *L); //释放链表所占内存
　　bool ListEmpty(LinkNode *L); //判断链表是否为空
　　int ListLength(LinkNode *L); //获取链表的长度
　　void DispList(LinkNode *L); //显示链表结点的值
　　bool GetElem(LinkNode *L, int i, ElemType &e);
　　//获取链表指定结点的值
　　int LocateElem(LinkNode *L, ElemType e);
　　//获取值为e的第1个结点的序号
　　bool ListInsert(LinkNode *&L, int i, ElemType e);
　　//在链表的指定位置插入值为e的结点
　　bool ListDelete(LinkNode *&L, int i, ElemType e);
　　//删除指定位置的结点并返回其值
　　（2）思考并初步编写上机实验内容的实现代码。
　　2、上机实验内容
　　题目：有一个递增单链表（允许出现值域重复的节点），设计一个算法删除值域重复的节点。选择使用部分单链表基本运算，设计并实现该算法，在工程主函数中对该算法进行验证。
　　算法设计提示：由于是有序表，所以相同值域的节点都是相邻的，用p扫描递增单链表，若*p节点的值域等于其后节点的值域，则删除后者（可参考授课PPT中的例子）。
　　三、实验步骤
　　1、在开发环境中编辑上机实验内容，实现题目要求，并自拟测试数据，测试程序功能，将运行结果进行截图保存。
　　2、对程序进行边界测试，并增加交互性功能，对程序功能进一步完善。
　　3、程序完成后，找指导老师确认做好记录。
　　四、思考与提高
　　1、线性表的顺序存储结构和链式存储结构各有哪些优缺点？各适用于什么应用场合？
　　2、在顺序存储实现中，为什么采用结构指针而不是结构变量的形式？
　　3、单链表的头结点的结构类型一定要与数据结点相同吗？
　　4、线性表的长度在基本运算和应用算法中经常要使用，但在链式存储中求取线性表长度的时间复杂度为O(n),如何设计链表的头结点结构使其时间复杂度降为O(1)？，哪些基本运算需要做相应改变？如何改变？
　　实验二 栈和队列综合应用
　　一、实验目的
　　1.通过实验操作，了解栈和队列的逻辑结构设计、存储结构设计以及基本运算的实现方法；
　　2.通过编写和调试栈与队列基本算法的实现程序，进一步理解和掌握其运行机制；
　　3.应用栈和队列数据结构解决较为简单的实际问题；
　　4.加深理解应用数据结构解决实践问题的一般方法和过程。
　　二、实验任务及要求
　　Part Ⅰ（2学时）
　　1、预习并完成以下内容
　　（1）预习实验教材P58-3.1-实验题1，编写调试实验题1的源程序，课前编辑通过，将源程序拷贝到U盘或上传到校ftp服务器，上机时作为基本函数使用。 为了方便后续实验内容，结点数值类型ElemType采用类型定义的方式，即：
　　typedef char ElemType;
　　实验过程中如果需要用到整数栈，直接将char换为int，则基本运算就可以直接使用。编写和调试实验题1时，需要定义为char。
　　采用结构指针形式构建顺序栈，即定义栈结构类型为：
　　typedef struct
　　{
　　ElemType data[MaxSize];
　　int top;
　　} SqStack;
　　SqStack *s; //s为指向栈的存储结构的指针
　　实现以下基本运算：
　　void InitStack(SqStack *&s) //初始化顺序栈
　　void DestroyStack(SqStack *&s) //销毁顺序栈
　　bool StackEmpty(SqStack *s) //判断栈是否为空
　　bool Push(SqStack *&s,ElemType e) //进栈
　　bool Pop(SqStack *&s,ElemType &e) //出栈
　　bool GetTop(SqStack *s,ElemType &e) //取栈顶元素
　　（2）提前准备上机实验内容的代码，课堂调试运行。
　　2、上机实验内容
　　（1）应用栈数据结构设计一个算法，实现十进制数转换成十六进制数。
　　提示：
　　栈存储数组采用整数类型；
　　将十进制数以16为模做取模运算，余数进栈，继续对除数取模；
　　除数为0进栈结束；
　　栈不空，开始出栈，显示为十六进制数，以0x开头，大于等于10的余数转换为ABCDEF（55+e）。
　　（2）应用栈数据结构设计一个算法，判断表达式中单括号是否匹配，例如：表达式为char exp[]=＂(1+2*(5+3)/2)＂,其小括号是匹配的，输出＂括号匹配＂，若小括号不匹配，则输出＂括号不匹配＂。
　　Part Ⅱ（2学时）
　　1、预习内容
　　（1）完成实验教材P63-3.1-实验题3，保存代码备用。主要包括以下基本运算：
　　void InitQueue(SqQueue *&q) //初始化队列q
　　void DestroyQueue(SqQueue *&q) //销毁队列q
　　bool QueueEmpty(SqQueue *q) //判断队q是否空
　　bool enQueue(SqQueue *&q,ElemType e) //进队
　　bool deQueue(SqQueue *&q,ElemType &e) //出队
　　（2）思考并初步编写上机实验内容的实现代码。
　　2、上机实验内容
　　题目：设计一个算法，将一个环形队列（容量为n，元素下标0 n-1）的元素倒置，例如下图中，图(a)为倒置前的队列，图(b)为倒置后的队列。
　　提示：
　　环形队列能够存储的最大元素数为容量-1，即9个字符。
　　可综合应用栈和队列数据结构，先建立一个临时栈st，先将队列qu中的所有元素出队，并将其依次进栈st，直到队列为空，然后初始化队列qu（队列清空），再出栈st的所有元素并将其进队qu，最后销毁栈st。
　　注意队列为空和队列满的判断条件。
　　三、实验步骤
　　1、在开发环境中编辑上机实验内容，实现题目要求，并自拟测试数据，测试程序功能，将运行结果进行截图保存。
　　2、对程序进行边界测试，并增加交互性功能，对程序功能进一步完善。
　　3、程序完成后，找指导老师确认做好记录。
　　四、思考与提高
　　1、栈和队列在数据操作方面各具有哪些特点？各适用于什么场合？
　　2、环形队列主要解决了队列哪方面不足？环形队列在应用方面有哪些局限性？
　　3、用栈和队列都可以求解迷宫问题，利用这两种数据结构求出的路径有什么不同？原因是什么？
　　4、课后上机自学链栈和链队的基本运算实现方法。
　　实验三 二叉树的构造与应用
　　一、实验目的
　　1.通过实验操作，加深对二叉树数据结构特性的理解；
　　2.掌握二叉链表存储结构和二叉树各种基本运算的算法设计；
　　3.掌握二叉树遍历算法的设计原理与运行机制；
　　4.领会二叉树的构造过程及构造二叉树的算法设计；
　　5.应用二叉树的构造、遍历以及基本算法解决较为简单的二叉树应用问题；
　　6.掌握Huffman树的构造过程及Huffman编码的生成过程；
　　7.加深理解应用数据结构解决实践问题的一般方法和过程。
　　二、实验任务及要求
　　Part Ⅰ（2学时）
　　1、预习并完成以下内容
　　（1）预习实验教材P140-7.1-实验题1，编写调试实验题1的源程序，课前编辑通过，将源程序拷贝到U盘或上传到校ftp服务器，上机时作为基本函数使用。
　　自己参考教材中关于二叉树数据结构的相关知识，用树形结构表示法画出一棵二叉树，转换成符合括号表示法要求的字符串表达式，用于程序测试。
　　实现以下基本运算：
　　void CreateBTree(BTNode * &b,char *str) //创建二叉树
　　void DestroyBTree(BTNode *&b) //销毁二叉树
　　BTNode *FindNode(BTNode *b,ElemType x) //查找值为x的结点，若找到
　　//则返回指向该结点的指针
　　BTNode *LchildNode(BTNode *p) //返回结点p的左孩子指针
　　BTNode *RchildNode(BTNode *p) //返回结点p的右孩子指针
　　void DispBTree(BTNode *b) //输出括号表示法格式的二叉树字符串
　　（2）提前准备上机实验内容的代码，课堂调试运行。
　　2、上机实验内容
　　（1）在开发环境下创建Win32 Console Application项目，将预习完成的二叉树基本运算函数加入项目主程序中，并用自己定义的二叉树进行测试，参考实验教材的相关内容，编写和调试通过实现下述功能要求的函数或过程：
　　输出某个结点的左、右孩子的值；
　　计算二叉树的高度；
　　求二叉树结点的个数。
　　（2）设计算法判断结点E是否为结点E1和E2的共同祖先。
　　提示：
　　①结点祖先的定义：从根结点到达某个结点的路径上经过的所有结点（除自身以外），称为该结点的祖先结点。
　　②应用基本运算FindNode（）。
　　Part Ⅱ（2学时）
　　1、预习内容
　　（1）完成实验教材P143-7.1-实验题2，二叉树的遍历算法是其他算法实现的重要基础，不仅要会书写代码而且还要深刻理解其运行机制。自己需要分解程序的运行过程，将递归算法与非递归算法进行对比。程序调试运行无误后保存代码备用。主要包括以下基本运算：
　　void PreOrder(BTNode *b) //先序遍历的递归算法
　　void PreOrder1(BTNode *b) //先序非递归遍历算法
　　void InOrder(BTNode *b) //中序遍历的递归算法
　　void InOrder1(BTNode *b) //中序非递归遍历算法
　　void PostOrder(BTNode *b) //后序遍历的递归算法
　　void PostOrder1(BTNode *b) //后序非递归遍历算法
　　void TravLevel(BTNode *b) //层次遍历
　　（2）思考并初步编写上机实验内容的实现代码。
　　2、上机实验内容
　　设计实现算法：二叉树采用二叉链表结构存储，根结点为b，设计一个算法把二叉树的左右子树进行交换，要求不破坏原二叉树。
　　提示：①递归模型建立
　　大问题：f(*b，*&b1) 将b的左子树作为b1的右子树；b的右子树作为b1的左子树。
　　小问题（递归调用）：f(b->lchild，b1->rchild)，f(b->rchild，b1->lchild)。
　　递归调用结束条件：b==NULL，（b1==NULL）。
　　递归操作：
　　b1=(BTNode *) malloc(sizeof(BTNode));
　　b1->data= b->data;
　　Part Ⅲ（2学时）
　　1、预习内容
　　（1）完成实验教材P153-7.1-实验题5，应用教材提供的测试数据进行程序测试，并将调试好的程序代码保存备用。主要包括以下基本运算：
　　void CreateHT(HTNode ht[],int n) //由ht的叶子结点构造完整的哈夫曼树
　　void CreateHCode(HTNode ht[],HCode hcd[],int n) //由哈夫曼树ht构造哈
　　//夫曼编码hcd
　　void DispHCode(HTNode ht[],HCode hcd[],int n) //输出哈夫曼编码
　　（2）思考并初步编写上机实验内容的实现代码。
　　2、上机实验内容
　　题目：给定五个字符a f，它们的权值集W {2,3,4,7,8,9}，试构造关于W的一棵哈夫曼树，求其带权路径长度WPL和各个字符的哈夫曼编码。
　　用预习内容中编写的程序，求解上述问题。
　　三、实验步骤
　　1、在开发环境中编辑上机实验内容，实现题目要求，并自拟测试数据，测试程序功能，将运行结果进行截图保存。
　　2、对程序进行边界测试，并增加交互性功能，对程序功能进一步完善。
　　3、程序完成后，找指导老师确认做好记录。
　　四、思考与提高
　　1、从树的定义和结构角度分析，为什么树适合于表达和处理层次化结构的数据？
　　2、树有哪些常用的存储结构？各有什么优缺点？
　　3、二叉树与2次树有哪些区别？
　　4、二叉链式表存储结构有哪些优缺点？
　　5、二叉树的遍历方法有哪几种？在采用非递归方法进行算法实现中重点要解决哪些问题？
　　6、二叉树的构造方法有哪两种？其原理是什么？
　　7、Huffman树的主要作用是什么？
　　实验四 用图搜索方法求解迷宫问题
　　一、实验目的
　　1.通过实验实训，进一步加深对栈、队列、图等数据结构的理解；
　　2.通过编写迷宫问题的求解程序，熟悉栈、图的DFS以及BFS遍历等基本运算的应用方式；
　　3.通过应用多种方式求解同一问题的训练场景，结合实验数据分析，进一步理解栈、队列、图的搜索等数据结构及基本运算的运行机制。
　　4.通过编程求解较为复杂的实际问题的训练，提高程序设计、调试以及算法应用等实践能力。
　　二、实验任务及要求
　　Part Ⅰ（2学时）
　　1、预习并完成以下内容
　　（1）预习实验教材P69-3.2-实验题5，编写调试实验题5的源程序，课前编辑程序代码，将源程序拷贝到U盘或上传到校ftp服务器，做好上机调试、运行准备。
　　（2）自己预先画一个6 6的迷宫图形（不含围墙，也就是说在程序中应用数组mg[8][8]进行存储），根据图中设置的通路和障碍，写出存储矩阵。设置入口和出口，构造时在入口与出口之间尽量含有多条通路，作为程序调试备用。
　　2、预习提示及导引
　　（1）教材中应用栈求解迷宫问题时，采用的是贪婪算法和深度优先搜索的思想，即在当前方块的某个方向上（按0：上 1：右 2：下 3：左）找到一个可以通行的方块后，继续前进，如果下一个方块不可通过，则退回到上一个方块，从上个方块的下一个方向搜索，一直找到出口，找到通路，程序结束，这时只是找到了一条路径。
　　（2）本次实验题目，在教材算法的基础上进一步扩展，可以找到所有路径，其思想是，找到出口后，将出口恢复为可行，再从其上一个方块的下一个方向找是否有通路能够到达出口，不存在的情况下再将路径上的上一个方块置为可行，从其下一个方向找到达出口的路径，这样不断回溯回去，能够找到从入口到出口的所有路径。
　　（3）程序包含的主要模块
　　①全局变量定义
　　int mg[M+2][N+2]，是全局变量，为了防止当前方块在搜索可行路径时找到路径中的上一个方块，上一个方块进栈时的状态要置-1。如果当前方块不可行，则要将其恢复为0，也就是说其他路径有可能用到这个方块，回溯查找其他路径。
　　struct {
　　int i,j;
　　int di;
　　} St[MaxSize]，Path[MaxSize];
　　int top=-1;
　　这里定义了一个轻量级栈，如果程序中只用到了较少的栈操作，没有必要将栈数据结构的所有运算都嵌入到程序中，这里只用到了进栈、出栈和取栈顶元素三种操作，并且空间没有浪费太多，结合栈顶指针就可以实现进栈出栈操作。
　　Path数组用于存储找到的最短路径，程序每找到一条路径，在输出的同时会记录其长度，如果长度比上一条路径短，就将栈中保存的路径存储到数组中，最后输出Path数组，即为最短路径，这种操作只将第一条最短路径存储在Path数组中，后面的路径长度与其相等时不更新Path数组。
　　②void dispapath()
　　输出一条路径，并求最短路径。栈中保存的是从入口到出口经过的所有方块的坐标，所以只需要从栈的第0个位置到栈顶指针依次输出方块坐标即为一条路径，比较路径长度，将最短的一条存储到Path数组，本程序只记录第一条最短的，如果出现第二条最短的，不会更新Path数组。
　　③void dispminpath（）
　　输出第一条最短路径。
　　④void mgpath(int xi, int yi, int xe, int ye)
　　从入口开始，从其4个方向查找到达出口的所有路径。
　　⑤int main()
　　指定入口、出口，查找路径。
　　3、上机实验内容
　　（1）在开发环境下创建Win32 Console Application项目，将预习完成的程序加入项目中，进行程序运行调试，运行成功后，分析解答下列问题。
　　①在输出第一条路径后，程序是如何找到第二条路径的，画图分析程序执行过程。
　　②如果要找到所有最短路径，程序如何修改？
　　提示：存储所有路径及其长度，即需要二维数组Path[COUNT][MaxSize]、PathLength[COUNT],再用路径条数变量count，将最短的所有路径输出。
　　③程序在查找路径时，总是从0 1 2 3四个方向的顺序查找可行方块，将程序改为按3 2 1 0的顺序进行路径搜索，输出运行结果，并与前面得到的运行结果进行对比分析。
　　Part Ⅱ（2学时）
　　1、预习内容
　　（1）完成实验教材P222-8.3-实验题14，编辑实验指导书中的程序，了解程序的基本模块结构，熟悉每个模块的基本功能。
　　使用Part Ⅰ中设计的迷宫图形，阅读程序模块void CreateAdj(ALGraph, *&G, int mg[][N+2]); 将迷宫存储数组转换为邻接表G,画出邻接表G的结构。
　　2、预习提示与导引
　　（1）迷宫图形到图数据结构的映射。将每一个可行方块作为图的一个顶点，从入口到出口的路径，即为从图的一个顶点到另一个顶点的路径。即将寻径问题转化为查找图中顶点之间的路径。
　　（2）为了实现上述映射，需要扩展教材中邻接表的结构，原来顶点链表头结点数组是一维数组，即图的编号从0 n-1，为了与迷宫中方块的坐标相对应，将其定义为二维数组adjlist[i][j],包含表头指针，指向该方块四周各行方块组成的链表。查找下一个相邻可行方块的操作，转变为搜索该方块对应的单链表。
　　（3）程序中有两个全局变量
　　visited[M+2][N+2]用于记录某个方块是否被遍历过，1为已经访问，0为未访问，回溯时需要将其由1改为0，这样能够查找到从入口出发的所有路径。
　　count用于对路径条数进行计数。
　　（3）程序模块说明
　　void CreateAdj(ALGraph, *&G, int mg[][N+2])
　　由迷宫存储数组建立对应的邻接表G。每个顶点一个表头指针，如果周围4个方向均无可行方块，则该单链表只有表头，其firstarc指针域为空。
　　DispAdj(ALGraph *G)
　　输出邻接表G，显示所有可行方块对应的单链表，包括围墙。将二维数组存储的迷宫转换为邻接表结构后，用该模块检查转换是否正确。
　　DestroyAdj(ALGraph *&G)
　　释放邻接表占用的空间。
　　FindPath(ALGraph *G, int xi, int yi, int xe, int ye, PathType path)
　　从入口(xi, yi)到出口(xe, ye)找一条路径并存储在path中。
　　3、上机实验内容
　　（1）按自己设计的迷宫，先构造数组存储格式，按行列确定每个方块的坐标，1为可通行，0为不可通行。运行程序将其转换为邻接表存储结构，并将结果进行显示。
　　观察一个邻接表不为空的方块，其链表中元素的位置是按什么顺序排列的，结合程序说明原因。
　　（2）如何修改程序，使其能够找到最短路径？
　　（3）如何修改程序，使其能够找到所有最短路径？
　　（4）如果要使搜索顺序由0 1 2 3，改为3 2 1 0，如何修改程序实现该要求？
　　（5）将程序运行结果与Part Ⅰ实验内容的运行结果进行对比分析。
　　三、实验步骤
　　1、在开发环境中编辑上机实验内容，实现题目要求，要求每个同学自己构造一个迷宫，然后应程序进行求解，并将设计过程及说明写入实验报告。测试程序功能，将运行结果进行截图保存；
　　2、完成上机实验任务中的各项要求；
　　3、对程序进行边界测试，并增加交互性功能，对程序功能进一步完善；
　　4、程序完成后，找指导老师确认做好记录。
　　四、思考与提高
　　1、用栈、DFS算法求解迷宫问题具有一定的相似性，从栈的运行特点以及DFS算法的工作机制分析这种相似性。
　　2、如果用队列和BFS求解迷宫问题，为什么找到的一定是最短路径？
　　3、递归求解迷宫问题，与实验中采用的两种方法有哪些区别和联系？
　　4、栈和队列都是临时存放需要特定操作数据的数据结构，从实验程序的设计实现过程中对栈的用法进行总结，说明在算法实现中如何灵活使用栈、队列等数据结构？（提示：栈和队列经过某些操作后存储的数据的利用？改变数据的访问顺序？存储相邻数据结点之间的关系？实现深度和广度搜索？轻量级栈和队列的实现？等等）。
　　实验五 计算各种排序算法的绝对执行时间
　　一、实验目的
　　1.通过上机实现各种常用内排序算法，结合实验过程数据和最终排序结果，进一步理解各种排序算法的基本实现思想；
　　2.掌握各种内排序算法代码实现的基本模式；
　　3.通过选择不同规模的测试数据，统计各种内排序算法的执行时间，对内排序算法的性能和应用场合进行对比分析；
　　4.通过实验实训，学会应用各种内排序算法解决实际问题。
　　二、实验任务及要求
　　Part 0程序模块简要说明
　　①数据源存储数组
　　KeyType R[MaxSize]
　　程序中KeyType与int类型等价，R[]数组用于存储随机产生的50000个整数，MaxSize常量为50001，数组最后一个元素为空。
　　KeyType R1[MaxSize]
　　程序中各种排序算法对R1[]数组中的数据进行排序，一种排序算法运行结束后，将R[]中的源数据重新复制到R1[]数组，避免每次都要产生新的随机整数序列，便于比较算法的执行时间。堆排序算法需要使用数组存储完全二叉树，下标从1开始，所以在堆排序时，R1[]数组第一个元素（下标为0）为空。
　　②公共函数
　　void swap(KeyType &x, KeyType &y)
　　交换x与y的值并返回。
　　void initial(int R[], int low, int high)
　　生成范围在1 99之间的整数，为R[low] R[high-1]赋值。注意main函数中调用格式为initial(R,0,n-1)，n=50000时实际上只能产生49999个符合要求的整数，注意修改程序中的错误。
　　void copy(int R[], int R1[], int n)
　　将R[]中的n个元素复制到R1[]中，下标均从0开始。
　　void copy1(int R[], int R1[], int n)
　　将R[]中下标为0 n-1的元素值复制到R1[]中，下标范围改为1 n。
　　void test(KeyType R[], int low, int high)
　　检查数组R[]中，下标为low high之间的数组元素是否按升序排列，注意观察程序代码，实际上存在检查不完备的地方，修改之。
　　③排序函数
　　每一种排序算法都设计了两个函数，一个用于对源数据排序，另一个用于估算排序时间。
　　void InsertSort(KeyType R[],int n)
　　插入排序。
　　void InsertSortTime(KeyType R[],int n)
　　估算插入排序时间。
　　void BinInsertSort（KeyType R[], int n）
　　折半插入排序。
　　void BinInsertSortTime（KeyType R[], int n）
　　估算折半插入排序时间。
　　void ShellSort(KeyType R[], int n）
　　希尔排序。
　　void ShellSortTime(KeyType R[], int n）
　　估算希尔排序时间。
　　void BubbleSort(KeyType R[], int n）
　　冒泡排序。
　　void BubbleSortTime(KeyType R[], int n）
　　估算冒泡排序时间。
　　int partition(KeyType R[], int s, int t)
　　快速排序的一趟划分，即以R[s]为基准，对R[]中的数据进行划分，小于R[s]的放在R[s]的左边，大于R[s]的放右边。
　　void QuickSort(KeyType R[], int s, int t)
　　对R[]中下标区间为s t的元素进行快速排序。
　　void QuickSortTime(KeyType R[], int n)
　　估算快速排序的时间。
　　void SelectSort(KeyType R[], int n)
　　简单选择排序。
　　void SelectSortTime(KeyType R[], int n)
　　估算简单选择排序的时间。
　　void sift(KeyType R[], int low, int high)
　　对分支结点为low，结点数为high的完全二叉树进行大根堆筛选构造，即：将以low为根结点的子树筛选调整为大根堆。
　　void HeapSort(KeyType R[], int n)
　　堆排序。
　　void HeapSortTime(KeyType R[], int n)
　　估算堆排序时间。
　　void Merge(KeyType R[], int low, int mid, int high)
　　对R[]中，下标为low mid，mid+1 high两段数据进行归并排序。
　　void MergePass(KeyType R[], int length, int n)
　　将R[]中，长度为length的各段数据进行归并排序。
　　void MergeSort(KeyType R[], int n)
　　对含有n个元素的R[]进行归并排序。
　　void MergeSortTime(KeyType R[], int n)
　　估算二路归并排序的时间。
　　Part Ⅰ（2学时）
　　1、预习并完成以下内容
　　（1）预习实验教材P291-10.3-实验题13，分析程序的主体框架，修改main函数和选用直接插入排序、折半插入排序以及希尔排序三种排序算法的公共程序模块，按实验教材提供的算法实现、测试方法编写调试相关源程序，课前编辑程序代码，将源程序拷贝到U盘或上传到校ftp服务器，做好上机调试、运行准备。
　　（2）预习并思考上机实验内容要求，确定解决问题的思路和方法。
　　2、预习提示及导引
　　（1）排序算法执行时间的估算
　　实验中使用了clock_t数据类型、clock()计时函数以及CLOCKS_PER_SEC常量（1秒包含的毫秒数）。每次计时需要调用clock()函数两次，返回值之差就是两次调用期间代码执行占用CPU的时间，即约为执行时间，精度为ms级。使用时需要包含头文件＂time.h＂。
　　在估算排序算法的执行时间时，尽量使待排序的数据量大一些，使比较结果更为明显。
　　（2）随机数的产生
　　程序的测试数据为50000个（可以适当增大）1 99的整数，其中用到了srand()函数和rand()函数，rand()函数在产生随机数前，需要提供生成伪随机数序列的种子，如果种子没有变化，每次调用rand()函数生成的伪随机数序列都是一样的。程序中使用了time()函数产生种子，保证了测试数据的随机性，调用形式在initial()函数中。使用时需要包含头文件＂stdlib.h＂。
　　3、上机实验内容
　　（1）在开发环境下创建Win32 Console Application项目，将预习完成的程序加入项目中，进行程序运行调试，运行成功后，分析解答下列问题。
　　（2）实验过程及思考题
　　①参考实验程序进行修改，产生10个1 99范围内的整数作为排序数据，编写一个显示排序数据的函数，将其放在排序程序的适当位置，显示出每一趟插入排序执行后的数据排列情况。并将显示结果进行截图保存。
　　②根据①中的排序结果分析三种插入排序的原理及排序过程。
　　③插入排序还有一种算法，如下所示：
　　void insert_sort(int R[],int length)
　　{
　　int i ,j,k;
　　for( i = 1 ; ifor( j = 0; j j ; k--)
　　R[k] = R[k-1]; //插入待排序元素
　　R[j] = key;
　　}
　　}
　　}
　　将上述函数加入到程序中，与插入排序一起对同一数据源进行排序，显示每趟排序结果，进行对比分析，这两种算法相比哪一种效率更好一些？
　　④修改程序，每种排序算法运行10次，计算其平均排序时间，并在算法间进行比较。
　　Part Ⅱ（2学时）
　　1、预习内容
　　（1）预习实验教材P291-10.3-实验题13中与交换排序和选择排序相关的内容，包括交换排序的冒泡排序算法、快速排序；选择排序中的选择排序算法，按实验教材提供的算法实现、测试方法编写调试相关源程序，课前编辑程序代码，将源程序拷贝到U盘或上传到校ftp服务器，做好上机调试、运行准备。
　　（2）预习并思考上机实验内容要求，确定解决问题的思路和方法。
　　2、预习提示与导引
　　（1）本次实验的排序算法包括：交换排序和部分选择排序算法，这些排序算法与插入排序算法相比均不需要元素移动，交换排序更是减少了元素交换操作。
　　（2）快速排序适合于数据量较大情况。
　　3、上机实验内容
　　（1）在开发环境下创建Win32 Console Application项目，将预习完成的程序加入项目中，进行程序运行调试，运行成功后，分析解答下列问题。
　　（2）实验过程及思考题
　　①参考实验程序进行修改，产生10个1 99范围内的整数作为排序数据，编写一个显示排序数据的函数，将其放在排序程序的适当位置，显示出各种排序算法每一趟排序执行后的数据排列情况。并将显示结果进行截图保存。
　　②根据①中的排序结果分析2种交换排序和1种选择排序算法的原理及排序过程。
　　③修改程序，将每种排序算法按数据量为100、500、1000、5000、10000、30000、50000、100000估算排序时间，观察各种算法适用于哪些排序场合。
　　④修改程序，固定排序数据长度，各运行10次，计算其平均排序时间，并在算法间进行比较。
　　Part Ⅲ（2学时）
　　1、预习内容
　　（1）预习实验教材P291-10.3-实验题13中与选择排序和归并排序的相关内容，包括堆排序和二路归并排序算法，按实验教材提供的算法实现、测试方法编写调试相关源程序，课前编辑程序代码，将源程序拷贝到U盘或上传到校ftp服务器，做好上机调试、运行准备。
　　（2）预习并思考上机实验内容要求，确定解决问题的思路和方法。
　　2、预习提示与导引
　　（1）本次实验的排序算法包括：堆排序和归并排序算法，这2种排序算法均适用于数据量较大的情况。
　　（2）堆排序中的筛选算法，区分两种情况，一种是建堆时是自下向上筛选，这其中如果有分支结点调整，则由其子结点开始向下调整，直到以其为根结点的子树符合大根堆的要求。在每一次排序结束后，即将根结点与最后一个结点交换，则筛选过程是自上而下进行的。
　　3、上机实验内容
　　（1）在开发环境下创建Win32 Console Application项目，将预习完成的程序加入项目中，进行程序运行调试，运行成功后，分析解答下列问题。
　　（2）实验过程及思考题
　　①参考实验程序进行修改，产生10个1 99范围内的整数作为排序数据，编写一个显示排序数据的函数，将其放在排序程序的适当位置，显示出2种排序算法每一趟排序执行后的数据排列情况。并将显示结果进行截图保存。
　　②根据①中的排序结果分析堆排序和二路归并排序算法的原理及排序过程。
　　③修改程序，将2种排序算法按数据量为100、500、1000、5000、10000、30000、50000、100000估算排序时间，对每一种排序算法的执行时间进行横向比较，分析同一种算法针对于不同规模的数据，其排序时间的变化情况，在归一化坐标中画出曲线。纵向比较堆排序算法和二路归并排序算法的执行时间。
　　④修改程序，固定排序数据长度，各运行10次，计算其平均排序时间，并在算法间进行比较。
　　三、实验步骤
　　1、在开发环境中编辑上机实验内容，实现题目要求，要求同学们在理解各种算法机理的基础上，掌握排序算法实现的基本结构，尽量做到掌握每一种内排序算法的代码实现；
　　2、在实验过程中，将实验结果进行截图保存，课后对照实验数据分析各种排序算法的实现原理，并将分析过程写在实验报告中。
　　3、完成上机实验任务中的各项要求；
　　4、对程序进行边界测试，并增加交互性功能，对程序功能进一步完善；
　　5、程序完成后，找指导老师确认做好记录。
　　四、思考与提高
　　1、插入排序、交换排序、选择排序以及归并排序算法的主要区别有哪些方面？
　　2、如果要提高排序算法的效率，即降低时间复杂度，应该从哪些方面进行改善和提高？
　　3、堆排序中使用了完全二叉树这种数据结构，主要应用了完全二叉树的哪些性质？
　　4、折半插入排序与折半查找之间有什么关系？
　　5、希尔排序与直接插入排序之间有什么关系？
　　6、实验中所用的各种内排序算法中，哪些是稳定的？哪些是不稳定的？稳定性排序算法适用于哪些场合？举例说明排序算法稳定性的重要性。
　　7、简单排序算法和复杂排序算法在使用中如何根据排序数据的不同情况进行选择？