北邮数据结构实验报告

数据结构实验报告实验名称：实验四排序（题目1）学生姓名：班级：班内序号：学号：日期：2013年12月19日1．实验要求实验目的：学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。

实验内容：使用简单数组实现下面各种排序算法，并进行比较。

排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序7、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对2的结果进行分析，验证上述各种算法的时间复杂度。

编写测试main()函数测试线性表的正确性。

2. 程序分析2.1 存储结构程序采用的存储机构是顺序存储，如下图所示：2.2 关键算法分析2.2.1 插入排序插入排序的基本方法是寻找一个指定元素在待排序元素中的位置，然后插入。

一趟直接插入排序的C++描述过程如下：①将待插入纪录赋值给哨兵r[0]：r[0]=r[i];②从后向前进行顺序查找：for(j=i-1;r[0]<r[j];j--);③元素后插：r[j+1]=r[j];④插入记录：r[j+1]=r[j];性能分析：原序列正序时直接插入排序达到最好的时间性能，比较次数为n-1，移动次数为0。

原序列逆序时直接插入排序达到最差时间性能，比较次数为，移动次数为。

直接插入排序的平均时间复杂度为，空间复杂度为。

直接插入排序是一种稳定的排序算法，特别适合于待排序集合基本有序的情况。

2.2.2 希尔排序希尔排序的基本方法是将待排序的元素集分成多个子集，分别对这些子集进行直接插入排序，待整个序列基本有序时，再对元素进行一次直接插入排序。

希尔排序的整个过程如下：for(int d=n/2;d>=1;d=d/2) //以d为增量//在子序列中进行插入排序{for(int i=d+1;i<=n;i++) //一趟希尔排序{if(r[i]<r[i-d]){r[0]=r[i];for(int j=i-d;j>0&&r[0]<r[j];j=j-d)//每隔d个记录，进行一次比较和移动，d=1时即是最后一趟直接插入排序r[j+d]=r[j];r[j+d]=r[0];}}}性能分析：希尔排序的时间复杂度在和之间，空间复杂度为，是一种不稳定的排序算法。

数据结构欧阳学文实验报告实验名称：哈夫曼树学生姓名：袁普班级：211125班班内序号：14号学号：210681日期：12月1.实验目的和内容利用二叉树结构实现哈夫曼编/解码器。

基本要求：1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树2、建立编码表(CreateTable)：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。

3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。

4、译码(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。

5、打印(Print)：以直观的方式打印哈夫曼树（选作）6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。

7、可采用二进制编码方式（选作）测试数据：I love data Structure, I love Computer。

I will try my best to study data Structure.提示：1、用户界面可以设计为“菜单”方式：能够进行交互。

2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码2. 程序分析2.1 存储结构用struct结构类型来实现存储树的结点类型struct HNode{int weight; //权值int parent; //父节点int lchild; //左孩子int rchild; //右孩子};struct HCode //实现编码的结构类型{char data; //被编码的字符char code[100]; //字符对应的哈夫曼编码};2.2 程序流程2.3算法1：void Huffman::Count()[1] 算法功能：对出现字符的和出现字符的统计，构建权值结点，初始化编码表[2] 算法基本思想：对输入字符一个一个的统计，并统计出现次数，构建权值数组，[3] 算法空间、时间复杂度分析：空间复杂度O（1），要遍历一遍字符串，时间复杂度O（n）[4] 代码逻辑：leaf=0; //初始化叶子节点个数int i,j=0;int s[128]={0}; 用于存储出现的字符for(i=0;str[i]!='\0';i++) 遍历输入的字符串s[(int)str[i]]++; 统计每个字符出现次数for(i=0;i<128;i++)if(s[i]!=0){data[j]=(char)i; 给编码表的字符赋值weight[j]=s[i]; 构建权值数组j++;}leaf=j; //叶子节点个数即字符个数for(i=0;i<leaf;i++)cout<<data[i]<<"的权值为："<<weight[i]<<endl;算法2：void Init();[1] 算法功能：构建哈弗曼树[2] 算法基本思想：根据哈夫曼树构建要求，选取权值最小的两个结点结合，新结点加入数组，再继续选取最小的两个结点继续构建。

北邮数据结构实验报告摘要：本报告基于北邮数据结构实验，通过实际操作和实验结果的分析，总结和讨论了各实验的目的、实验过程、实验结果以及相关的问题和解决方法。

本报告旨在帮助读者了解数据结构实验的基本原理和应用，并为今后的学习和研究提供参考。

1. 实验一：线性表的操作1.1 实验目的本实验旨在掌握线性表的基本操作以及对应的算法实现，包括插入、删除、查找、修改等。

1.2 实验过程我们使用C++语言编写了线性表的相关算法，并在实际编程环境下进行了测试。

通过插入元素、删除元素、查找元素和修改元素的操作，验证了算法的正确性和效率。

1.3 实验结果经过测试，我们发现线性表的插入和删除操作的时间复杂度为O(n)，查找操作的时间复杂度为O(n)，修改操作的时间复杂度为O(1)。

这些结果与预期相符，并反映了线性表的基本特性。

1.4 问题与解决方法在实验过程中，我们遇到了一些问题，例如插入操作的边界条件判断、删除操作时的内存释放等。

通过仔细分析问题，我们优化了算法的实现，并解决了这些问题。

2. 实验二：栈和队列的应用2.1 实验目的本实验旨在掌握栈和队列的基本原理、操作和应用，并进行实际编程实现。

2.2 实验过程我们使用C++语言编写了栈和队列的相关算法，并在实际编程环境下进行了测试。

通过栈的应用实现表达式求值和逆波兰表达式的计算，以及队列的应用实现图的广度优先遍历，验证了算法的正确性和效率。

2.3 实验结果经过测试，我们发现栈的应用可以实现表达式的求值和逆波兰表达式的计算，队列的应用可以实现图的广度优先遍历。

这些结果证明了栈和队列在实际应用中的重要性和有效性。

2.4 问题与解决方法在实验过程中，我们遇到了一些问题，例如中缀表达式转后缀表达式的算法设计、表达式求值的优化等。

通过查阅资料和与同学的讨论，我们解决了这些问题，并完善了算法的实现。

3. 实验三：串的模式匹配3.1 实验目的本实验旨在掌握串的基本操作和模式匹配算法，并进行实际编程实现。

数据结构实验报告实验名称：实验三——栈和队列学生姓名：班级：班内序号：学号：日期：1.实验要求1.1 实验目的通过选择下面两个题目之一进行实现，掌握如下内容：➢掌握二叉树基本操作的实现方法➢了解赫夫曼树的思想和相关概念➢学习使用二叉树解决实际问题的能力1.2 实验内容根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。

二叉树的基本功能：1、二叉树的建立2、前序遍历二叉树3、中序遍历二叉树4、后序遍历二叉树5、按层序遍历二叉树6、求二叉树的深度7、求指定结点到根的路径8、二叉树的销毁9、其他：自定义操作编写测试main()函数测试线性表的正确性2. 程序分析2.1 二叉链表2.2 二叉树的二叉链表存储示意图2.3 关键算法分析2.3.1算法1：void create(Binode<T> *&R, T data[], int i);[1] 算法功能：创建一个二叉树[2] 算法基本思想：通过构造函数创建一个二叉树，构造函数通过调用函数create()创建二叉树，关于函数create()的伪代码：1.定义根指针，输入节点储存的data，若输入“#”，则该节点为空；2.申请一个新节点，判断它的父结点是否不为空，如果不为空在判断其为左或者右孩子，并把地址付给父结点，把data写入。

[3] 算法空间、时间复杂度：O（n）[4] 代码逻辑（可用伪代码描述）：if(data[i-1]!=0){R = new Binode<T>;R->data= data[i-1];R->lch = R->rch = NULL;create(R->lch, data,2*i);create(R->rch, data, 2*i+1);}2.3.2算法2：void Destroy(Binode<T> *R);[1] 算法功能：二叉树的销毁[2] 算法基本思想：采用后序遍历的方法，释放节点。

北邮数据结构实验-约瑟夫环数据结构实验报告实验名称：实验1——约瑟夫环学生姓名：班级：班内序号：学号：日期：1．实验要求实验目的：通过利用循环链表实现约瑟夫问题的求解进行实现，掌握如下内容：1.熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法2.学习指针、模板类、异常处理的使用3.掌握线性表的操作的实现方法4.学习使用线性表解决实际问题的能力实验内容：利用循环链表实现约瑟夫问题的求解。

约瑟夫问题如下：已知n个人（n>=1）围坐一圆桌周围，从1开始顺序编号。

从序号为1的人开始报数，顺时针数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规则重复下去，直到所有人全部出列。

请问最后一个出列的人的编号。

2. 程序分析2.1 存储结构首先构建结点的结构体，包括结点的编号number和指向后继元素的指针*next。

然后构建循环链表储存每一个结点。

2.2 关键算法分析1、关键算法：插入：用尾插法构建循环链表，建立一个尾指针r用来保存最后一个结点的地址，插入每一个节点后，r指向新插入的结点。

用for循环来给每一个结点的number赋值。

插入的步骤：1.建立新指针s；2.在for循环中给s赋值；3.将r指针指向s；4.修改尾指针r=s5.在全部结点插入后，将终端结点指向第一个指针，r->next=front->next。

约瑟夫环算法实现：1.因为每次循环都有一个人出列，最后只剩一个人，因此要进行n-1次循环，用for循环实现。

2.同时定义一个指针p=front->next，每次循环front和p均后移m-1个，使p指向每次循环的第m个人，front指向第m-1个人。

并输出出列的人的number，即p->number。

3.让front->next=p->next，删除p。

4.继续进行循环2、代码详细分析：约瑟夫环算法步骤：①定义一个指针p=front->next，每次循环front和p均后移m-1个，使p指向每次循环的第m个人，front指向第m-1个人。

2009级数据结构实验报告实验名称：实验四——排序学生姓名：班级：班内序号：学号：日期：2010/12/171．实验要求实验目的：通过选择下面两个题目之一，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。

实验内容：使用简单数组实现下面各种排序算法，并进行比较。

排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序7、归并排序8、基数排序（选作）9、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性。

2. 程序分析2.1 存储结构使用最简单的一维数组存储待排序的数据。

共使用两个数组，一个用来存储原始数据，一个用来存储待排序数据。

每次排序完毕，用原始数据更新一次待排序数据，保证每一次都对同一组数据排序。

（图略）2.2 关键算法分析1.直接插入的改进：在一般的直接插入中，关键码每移动一次就需要比较一次。

在移动的方面，优化是比较困难的，因为对静态线性表的插入必然要带来大量的移动。

但是，我们可以在比较上进行一些优化。

在查找技术一张曾学过的“折半查找法”，在这里就可以照葫芦画瓢地运用。

一趟排序的伪代码如下：1.如果该元素大于处于其左侧相邻的元素则跳过该元素；2.low=0，high=i；3.循环直至low==high3.1 mid=(low+high)/2；3.2如果当前元素大于中值high=mid；3.3否则low=mid+1；4.当前元素赋值给临时变量；5.将有序区中处于low位置及其右侧的元素右移；6.临时变量置于low位置简单说一下这里的折半查找与一般查找算法的区别。

这里的查找，尤其是对无重复数据和大量数据的处理中，更多的时候是找不到完全相等的项的。

数据结构实验报告实验名称：哈夫曼树学生姓名：袁普班级：2013211125班班内序号：14号学号：2013210681日期：2014年12月实验目的和内容利用二叉树结构实现哈夫曼编/解码器。

基本要求：1、初始化(Init)：能够对输入的任意长度的字符串 s进行统计，统计每个字符的频度，并建立哈夫曼树2、建立编码表(CreateTable)：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。

3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。

4、译码(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。

5、打印(Print)：以直观的方式打印哈夫曼树（选作）6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。

7、可采用二进制编码方式（选作）测试数据：I love data Structure, I love Computer。

I will try my best to studydata Structure.提示：1、用户界面可以设计为“菜单”方式：能够进行交互。

2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码2. 程序分析2.1 存储结构用struct结构类型来实现存储树的结点类型struct HNode{int weight; //权值int parent; //父节点int lchild; //左孩子int rchild; //右孩子};struct HCode //实现编码的结构类型{char data; //被编码的字符char code[100]; //字符对应的哈夫曼编码};2.2 程序流程2.3 关键算法分析算法1：void Huffman::Count()[1] 算法功能：对出现字符的和出现字符的统计，构建权值结点，初始化编码表[2] 算法基本思想：对输入字符一个一个的统计，并统计出现次数，构建权值数组，[3] 算法空间、时间复杂度分析：空间复杂度O（1），要遍历一遍字符串，时间复杂度O（n）[4] 代码逻辑：leaf=0; //初始化叶子节点个数int i,j=0;int s[128]={0}; 用于存储出现的字符for(i=0;str[i]!='\0';i++) 遍历输入的字符串s[(int)str[i]]++; 统计每个字符出现次数for(i=0;i<128;i++)if(s[i]!=0){data[j]=(char)i; 给编码表的字符赋值weight[j]=s[i]; 构建权值数组j++;}leaf=j; //叶子节点个数即字符个数for(i=0;i<leaf;i++)cout<<data[i]<<"的权值为："<<weight[i]<<endl;算法2：void Init();[1] 算法功能：构建哈弗曼树[2] 算法基本思想：根据哈夫曼树构建要求，选取权值最小的两个结点结合，新结点加入数组，再继续选取最小的两个结点继续构建。

北邮数据结构实验报告-排序北邮数据结构实验报告-排序一、实验目的本实验旨在掌握常见的排序算法，包括冒泡排序、插入排序、选择排序、快速排序、归并排序等，并通过实际编程实现对数字序列的排序。

二、实验内容1.冒泡排序冒泡排序是一种简单的排序算法，其基本思想是依次比较相邻的两个元素，并按照从小到大或从大到小的顺序交换。

具体步骤如下：- 从待排序序列的第一个元素开始，依次比较相邻的两个元素；- 如果前面的元素大于后面的元素，则交换这两个元素的位置；- 重复上述步骤，直到整个序列有序。

2.插入排序插入排序是一种简单且直观的排序算法，其基本思想是将待排序序列分为已排序和未排序两部分，每次从未排序部分中选择一个元素插入到已排序部分的合适位置。

具体步骤如下：- 从待排序序列中选择一个元素作为已排序部分的第一个元素；- 依次将未排序部分的元素插入到已排序部分的合适位置，使得已排序部分保持有序；- 重复上述步骤，直到整个序列有序。

3.选择排序选择排序是一种简单且直观的排序算法，其基本思想是每次选择未排序部分中的最小（或最大）元素，并将其放在已排序部分的末尾。

具体步骤如下：- 在未排序部分中选择最小（或最大）的元素；- 将选择的最小（或最大）元素与未排序部分的第一个元素交换位置；- 重复上述步骤，直到整个序列有序。

4.快速排序快速排序是一种高效的排序算法，其基本思想是通过一趟排序将待排序序列分割成两部分，其中一部分的元素都比另一部分的元素小。

具体步骤如下：- 选择一个枢轴元素（一般选择第一个元素）；- 将待排序序列中小于枢轴元素的元素放在枢轴元素的左侧，大于枢轴元素的元素放在枢轴元素的右侧；- 对枢轴元素左右两侧的子序列分别进行递归快速排序；- 重复上述步骤，直到整个序列有序。

5.归并排序归并排序是一种高效的排序算法，其基本思想是将待排序序列划分成足够小的子序列，然后对这些子序列进行两两合并，最终形成有序的序列。

具体步骤如下：- 将待排序序列递归地划分成足够小的子序列；- 对每个子序列进行归并排序；- 合并相邻的子序列，直到整个序列有序。

北邮数据结构实验报告北邮数据结构实验报告一、引言数据结构是计算机科学中的重要基础知识，对于计算机程序的设计和性能优化起着至关重要的作用。

本报告旨在总结北邮数据结构实验的相关内容，包括实验目的、实验设计、实验过程和实验结果等。

二、实验目的本次实验旨在通过实践操作，加深对数据结构的理解和应用能力。

具体目的如下：1. 掌握线性表、栈和队列等基本数据结构的实现方法；2. 熟悉二叉树、图等非线性数据结构的构建和遍历算法；3. 学会使用递归和非递归算法解决实际问题；4. 培养编程实践能力和团队合作意识。

三、实验设计本次实验包括以下几个部分：1. 线性表实验：设计一个线性表类，实现线性表的基本操作，如插入、删除和查找等。

通过实验，了解线性表的顺序存储和链式存储结构的特点和应用场景。

2. 栈和队列实验：设计栈和队列类，实现栈和队列的基本操作，如入栈、出栈、入队和出队等。

通过实验，掌握栈和队列的应用，如括号匹配、迷宫求解等。

3. 二叉树实验：设计二叉树类，实现二叉树的创建、遍历和查找等操作。

通过实验，熟悉二叉树的前序、中序和后序遍历算法，并了解二叉树的应用，如表达式求值等。

4. 图实验：设计图类，实现图的创建、遍历和最短路径等操作。

通过实验，掌握图的邻接矩阵和邻接表表示方法，并了解图的深度优先搜索和广度优先搜索算法。

四、实验过程1. 线性表实验：根据实验要求，首先选择线性表的存储结构，然后设计线性表类，实现插入、删除和查找等基本操作。

在实验过程中，遇到了一些问题，如边界条件的处理和内存管理等，通过团队合作，最终解决了这些问题。

2. 栈和队列实验：根据实验要求，设计栈和队列类，实现入栈、出栈、入队和出队等基本操作。

在实验过程中，我们发现了栈和队列在实际应用中的重要性，如括号匹配和迷宫求解等，通过实验加深了对栈和队列的理解。

3. 二叉树实验：根据实验要求，设计二叉树类，实现二叉树的创建、遍历和查找等操作。

在实验过程中，我们发现了二叉树在表达式求值和排序等方面的应用，通过实验加深了对二叉树的理解。

数据结构实验报告实验名称：实验4——题目4——哈夫曼树学生姓名：班级：班内序号：学号：日期：2017年1月6日1．实验要求利用二叉树结构实现哈夫曼编/解码器。

基本要求：1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。

3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。

4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。

5、打印(Print)：以直观的方式打印赫夫曼树（选作）6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。

2. 程序分析2.1 存储结构本实验的存储结构为哈夫曼树与哈夫曼编码表哈夫曼树：存储结构：struct HNode//哈夫曼树的结点结构{int weight;//结点权值int parent;//双亲指针int LChild;//左孩子指针int RChild;//右孩子指针};哈夫曼编码表：struct HCode//编码表的结点结构{char data;//字符char code[10];//编码int k;//码长};存储结构：2.2 关键算法分析一、初始化：步骤：1、设立数组，记录每一个字符出现的次数与字符对应的ASCII码2、以字符不是回车或换行遍历输入的字符数组3、将存储出现次数大于0的字符存储进叶子节点数组4、相对应的，存储叶子结点的数据域字符出现的次数。

时间复杂度：O（n）空间复杂度：O（n）二、创建哈夫曼树步骤：1、创建2n-1个数节点2、将权值数组依次赋值进0到n-1的权值节点中3、从0到i-1（最开始等于n-1）选择两个权值最小的节点x、y，将其连接为i节点的左右孩子，改变x、y的双亲指针为i节点4、I++，循环步骤4直到2n-1时间复杂度：O（n^2）空间复杂度 O（n）三、创建哈夫曼编码表步骤：1、创建n个编码表节点2、依次将叶子节点的字符放入编码表节点数据域中3、对每个编码表对应的树结点，向根节点开始回溯（为父节点的左孩子编码值为0，右孩子为1，不断上移，直到根节点）4、进行倒置时间复杂度O（n）空间复杂度 O（n）四、编码步骤：1、新建编码数组2、从源码第一个字符开始在编码表中寻找到相应字符后将编码复制进编码数组3、计算压缩比时间复杂度O（n+e） n为源码 e为编码数组长度空间复杂度O（n）五、解码步骤：1、从根节点开始，按照编码串寻找（0为左子树，1为右子树）2、直到该节点无子树，将该节点（也就是叶子节点）字符放入解码串中3、重复步骤1、2直到编码串结束时间复杂度O（n） n为编码串长度空间复杂度O（e） e为原串长度六、打印哈夫曼树步骤：1、从根节点开始第m层前方空m个格2、叶子结点先输出数据域再在下一行输出权值3、重复输出，递归调用，直到叶子。

数据结构实验报告实验名称：实验三——树题目一学生姓名：申宇飞班级：2012211103班内序号：03学号：2012210064日期：2013年12月3日1．实验要求掌握二叉树基本操作的实现方法根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。

二叉树的基本功能：1、二叉树的建立2、前序遍历二叉树3、中序遍历二叉树4、后序遍历二叉树5、按层序遍历二叉树6、求二叉树的深度7、求指定结点到根的路径8、二叉树的销毁9、其他：自定义操作编写测试main()函数测试线性表的正确性2. 程序分析2.1 存储结构采用二叉树的存储结构，其中每个二叉树的结点定义了一个结构体，该结构体包含三个元素，分别是一个T类型的数据域data，一个指向T类型的指针左孩子，一个指向T 类型的指针右孩子，示意图如图所示。

采用了队列的存储结构。

示意图如图所示：对于二叉树中每个结点的data 域的赋值，我们事先把这些data 储存在一个数组中，通过对数组元素的调用事先对二叉树中每个结点的data 域的赋值。

2.2 关键算法分析 一：二叉树的建立： A ． 自然语言描述：1首先判断调用的数组是否为空，如果为空，直接将一个已经初始化好的根节点置为空。

2 如果该数组不为空，则把调用的数组的第一个元素的赋给根节点的data 域。

3 采用递归的思想，分别将根节点的左右孩子作为根节点，递归调用该函数。

完成对左右子树的赋值。

B ． 代码详细分析：template <class T> void BiTree<T>::Create(Node<T> *&R,T* buf,int i) {if (buf[i-1]==0) R = NULL; else {R=new Node<T>; R->data = buf[i-1];Create(R->lch, buf, 2*i); Create(R->rch, buf, 2*i+1); }lchdata rchlchdata rchlchdata rchlchdata rchlchdata rchlchdata rchlch data rchA[2*i]A[2*i+1] lch data rch lch data rch二：前序遍历二叉树：A. 自然语言描述：1：建立栈2：判断该栈是否为空并且根节点是否为空指针3：如果根节点不是空指针，则输出它的data域，并且是它入栈4：入栈后将根节点指针指向它的左孩子5：如果根节点是空指针6：则根节点出栈，并且指向根节点的指针指向它的右孩子B.代码详细分析：template <class T> void BiTree<T>::Preorder(Node<T> *R){Stack<Node<T>*> S;while(!S.IsEmpty() || (R!=NULL)){if (R!=NULL){Print(R->data);S.Push(R);R=R->lch;}else{R=S.Pop();R=R->rch;}}}三：中序遍历二叉树：A.自然语言描述：1：建立栈2：判断该栈是否为空并且根节点是否为空指针3：如果根节点不是空指针，将它入栈4：入栈后将根节点指针指向它的左孩子5：如果根节点是空指针6：则根节点出栈，输出该节点的data域，并且指向根节点的指针指向它的右孩子B. 代码详细分析：template <class T> void BiTree<T>::Inorder(Node<T> *R){Stack<Node<T>*> S;while(!S.IsEmpty() || (R!=NULL)){if (R!=NULL){S.Push(R);R=R->lch;}else{R=S.Pop();Print(R->data);R=R->rch;}}}四：后序遍历二叉树：A.自然语言描述：1：判断根节点是否为空2：如果根节点不为空3：递归调用后续遍历函数，函数的参数改为根节点的左孩子 4：递归调用后续遍历函数，函数的参数改为根节点的右孩子 5：输出根节点的data域B.代码详细分析：template <class T> void BiTree<T>::Postorder(Node<T> *R) {if (R!=NULL) {Postorder(R->lch);Postorder(R->rch);Print(R->data);}}}}123五：层序遍历二叉树：A.自然语言描述：1：判断根节点是否为空2：如果根节点不为空3：输出根节点的data域4：递归调用层续遍历函数，函数的参数改为根节点的左孩子5：递归调用层序遍历函数，函数的参数改为跟结点的右孩子B.代码详细分析：template <class T> void BiTree<T>::Levelorder(Node<T> *R){Queue<Node<T>*> Q;while(!Q.IsEmpty() || (R!=NULL)){if (R!=NULL){Print(R->data);Q.EnQueue(R->lch);Q.EnQueue(R->rch);}R=Q.DelQueue();}}}123六：求二叉树的深度：A.自然语言描述：1：判断根节点是否为空，如果根节点为空，返回02：如果根节点不为空但是根节点的左右孩子同时为空，返回13：如果以上两个条件都不成立4：递归调用求二叉树的深度，函数的参数改为根节点的左孩子，并且深度初始化为1 5：递归调用求二叉树的深度，函数的参数改为跟结点的右孩子，并且深度初始化为0 6：返回4与5步中得出深度较大的那个数作为二叉树的深度数B.代码详细分析：template <class T> int BiTree<T>::GetDepth(Node<T> *R,int d){if (R==NULL) return d;if ((R->lch==NULL) && (R->rch==NULL))return d+1;else{int m = GetDepth(R->lch,d+1); int n = GetDepth(R->rch,d+1); return n>m? n:m; } }七：二叉树的销毁 A.自然语言描述：1：判断根节点是否为空 2：如果根节点不为空3：递归调用二叉树的销毁函数，参数改为根节点的左孩子 4：递归调用二叉树的销毁函数，参数改为根节点的右孩子 5：释放根节点指向的内存 B.代码详细分析：template <class T> void BiTree<T>::Destroy(Node<T> *R) {if (R!=NULL) { Destroy(R->lch); Destroy(R->rch); delete R; } }}：123八：求二叉树的叶子结点数： A.自然语言描述：1：判断根节点是否为空，如果为空，返回02：如果根节点不为空，切根节点的左右孩子同时为空，返回13：递归调用求二叉树的叶子节点数函数，参数改为根节点的左孩子 4：递归调用求二叉树的叶子结点数函数，参数改为根节点的右孩子 5：返回根节点的左右子树的叶子结点数之和 B.代码详细分析：template <class T> int BiTree<T>::LeafNodeCount(Node<T> *R) {if (R==NULL) return 0;if ((R->lch==NULL) && (R->rch==NULL)) return 1; else {int n=LeafNodeCount(R->lch); int m=LeafNodeCount(R->rch); return m+n; } }九：求二叉树的结点数： A.自然语言描述：} }123}1231：判断根节点是否为空，如果为空，返回02：如果根节点不为空3：递归调用求二叉树的结点数的函数，参数改为根节点的左孩子4：递归调用求二叉树的结点数的函数，参数改为根节点的右孩子5：返回根节点的左右字数的结点数之和B.代码详细分析：template <class T> int BiTree<T>::NodeCount(Node<T> *R){if (R==NULL) return 0;else{int m=NodeCount(R->lch);}}int n=NodeCount(R->rch); return m+n+1;}1232.3 其他对二叉树的操作上，前序遍历与中序遍历采用了非递归算法，后续遍历，层序遍历，求二叉树深度，求二叉树叶子结点数，求二叉树结点数等函数采用了递归算法。

数据结构实验报告实验名称：实验———线性表学生姓名：班级：班内序号：学号：日期：实验要求1.1 实验目的通过选择下面四个题目之一进行实现，掌握如下内容：➢熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法➢学习指针、模板类、异常处理的使用➢掌握线性表的操作的实现方法➢学习使用线性表解决实际问题的能力1.2 实验内容利用线性表实现一个通讯录管理，通信录的数据格式如下：struct DataType{int ID; //编号char name[10];//姓名char ch;//性别char phone[13];//电话char addr[31];//地址};1.3具体要求➢实现通讯录的建立、增加、删除、修改、查询等功能➢能够实现简单的菜单交互，即可以根据用户输入的命令，选择不同的操作。

➢能够保存每次更新的数据（选作）➢能够进行通讯录分类，比如班级类、好友类、黑名单等等（选作）➢编写测试main()函数测试线性表的正确性2. 程序分析通过编程完成通讯录管理系统，实现建立、增加、修改、查找、删除、输出等一般功能，每个数据元素包含成员的ID 、姓名、电话、住址等基本信息。

本程序使用链表的功能，以C++语言为基础编写。

对于本通讯录管理系统的建立，需要了解并掌握链表的算法与设计方法，综合运用所学知识完成。

2.1 存储结构节点结构:2.2 关键算法分析通讯录系统图2.2.1 通讯录的建立 伪代码：1. 在堆栈中申请新的节点2. 新节点的数据为a[i]3. 将新节点添加到链表4. 修改尾指针5.全部插入后最后一个节点的指针域设为空代码实现：ContactBook::ContactBook(DataType a[],int n){front=new Node;rear=new Node;rear=front;for(int i=0;i<n;i++) //尾插法{Node* p=new Node;p->data=a[i];rear->next=p;rear=p;}rear->next=NULL;}时间复杂度=o(n)2.2.2 添加新成员伪代码：与通讯录的建立类似，通过尾插法实现代码实现：void ContactBook::Add(DataType a){Node* p=new Node;p->data=a;rear->next=p;rear=p;rear->next=NULL;}时间复杂度=o(1)2.2.3 查找成员伪代码：1.初始化指针p指向头指针2.循环直到匹配到ID或为p为空3.找到则返回p的位置4.找不到则返回空指针代码实现：DataType* ContactBook::Get(int i)Node* p=front;while(p){if(p->data.ID==i) //ID匹配模式查找return &p->data; //找到则返回p的地址p=p->next;}return NULL; //找不到则返回空}时间复杂度=o(n)2.2.4 删除成员伪代码：1.初始化指针p指向头指针2.循环匹配ID找到要删除的成员的前一个节点3.初始化指针q指向要删除的成员4.保存q的数据5.p指向q的下一节点6.释放q节点代码实现：DataType ContactBook::Delete(int i){Node* p=front;while(p){if(p->next->data.ID==i)break;p=p->next;}Node* q=p->next;//q指针指向要删除的成员if(q){DataType x=q->data;//保存成员数据p->next=q->next;//p的next指向q的nextdelete q;cout<<"删除成功！"<<endl;return x;}else{cout<<"该成员不存在！"<<endl;}}时间复杂度=o(n)2.2.5 修改成员先调用查询模块，找到并打印用户信息，然后依次修改成员信息代码实现：void ContactBook::Modify(DataType a,int i){DataType* p=Get(i);*p=a;}时间复杂度=o(n)2.2.6 打印成员依次打印成员信息代码实现：void ContactBook::printList(){cout<<"您的通讯录成员如下："<<endl;cout<<"********************"<<endl;Node* p=front->next;while(p){cout<<p->data.ID<<" "<<p-><<" "<<p->data.ch<<" "<<p->data.phone<<" "<<p->data.addr<<endl;cout<<"********************"<<endl;p=p->next;}}时间复杂度=o(n)3. 程序运行结果3.1 主程序流程图图2 流程图示意图3.2 测试截图3.2.1 建立通讯录3.2.2 增加成员3.3.3 查找成员3.3.4 修改成员3.3.5 删除成员3.3.6 打印成员3.3.7 退出4. 总结通过本实验，巩固了我对链表的理解，学会了使用线性表解决一些实际的问题。

数据结构实验报告实验名称：实验一——线性表学生姓名：班级：班内序号：学号：日期：1．实验要求实验目的熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法学习指针、模板类、异常处理的使用掌握线性表的操作的实现方法学习使用线性表解决实际问题的能力实验内容利用循环链表实现约瑟夫问题的求解。

约瑟夫问题如下：已知n个人（n>=1）围坐一圆桌周围，从1开始顺序编号。

从序号为1的人开始报数，顺时针数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规则重复下去，直到所有人全部出列。

请问最后一个出列的人的编号。

2. 程序分析2.1 存储结构采用单循环链表实现约瑟夫问题的求解单循环链表存储结构示意图2.2 关键算法分析基本思想：首先，应该确定构造链表时所用的插入方法。

当数到m的那个人就出列，也即删除这个节点，同时建立这个节点的前节点与后节点的联系。

由于是循环计数，所以才采用循环列表方式。

其次还要考虑输入值异常的情况。

之后，就是关于出列节点的逻辑判断。

依次找到待删结点的直接前驱，便于删除结点后修改它的直接后继，如此循环直到最后一个人出列。

关键算法：1.最后一个数据指向头指针，形成循环链表head=new Node; //确定头结点p=head;for(i=1;i<=n-1;i++) //赋初值{p->data=i;p->next=new Node; //为下一个新建内存p=p->next;}p->data=n; //最后一个单独处理p->next=head; //指向头，形成循环链表p=head;2.输入值异常的情况cout<<"请输入环内总人数n:";cin>>n;if (n<1) //考虑n输入错误的情况{cout<<"n值输入错误"<<endl;}cout<<"请输入起始人号码:";cin>>k;if (k<1||k>n) //考虑k输入异常的情况{cout<<"k值输入错误"<<endl;}cout<<"请输入m值:";cin>>m;if (m<1) //考虑m输入异常的情况{cout<<"m值输入错误"<<endl;}3.在约瑟夫环中实现逐个出环并找出最后一个出环的序号while(p!=p->next){for(i=1;i<m-1;i++) //查找q的节点p=p->next;q=p->next;cout<<"第"<<s<<"个出环的人编号是："<<q->data<<endl;p->next=q->next;p=p->next;delete q; //释放q的空间s++;}cout<<"最后环内留下的人编号是："<<p->data<<endl;delete p;算法步骤：①从第一个结点开始，查找第i-1个元素，设为p指向该结点；②设q指向第i个元素：q = p->next;，输出q元素的数据；③摘链，即将q元素从链表中摘除：p->next = q->next;p=p->next;delete q;3. 程序运行结果1、测试主函数流程：流程图如图所示2、程序运行结果3、输入错误运行结果4. 总结在调试程序过程中，虽然没有编译错误，但是运行结果总是和准确值差1，最后发现是把i=1写成i=0，才造成的错误，改过之后就没有问题了。

数据结构实验报告实验名称：实验一线性表——题目1学生：申宇飞班级：信通3班班序号： 03学号： 2012210064日期： 2013年11月4日1.实验要求实验目的：熟练掌握线性表的基本操作，包括：创建、插入、删除、查找、输出、求长度、合并等运算，以及各类操作在顺序存储结构和链式存储结构上的实现。

实验容：根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。

线性表存储结构（五选一）：1、带头结点的单链表2、不带头结点的单链表3、循环链表4、双链表5、静态链表线性表的基本功能：1、构造：使用头插法、尾插法两种方法2、插入：要求建立的链表按照关键字从小到大有序3、删除4、查找5、获取链表长度6、销毁7、其他：可自行定义编写测试main()函数测试线性表的正确性。

2.程序分析2.1 存储结构链表的具体存储表示为：① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）② 链表中结点的逻辑次序和物理次序不一定相同。

为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址信息（称为指针）链表的结点结构┌──┬──┐│data│next│└──┴──┘data 域--存放结点值的数据域next 域--存放结点的直接后继的地址（位置）的指针域（链域）地址 存单元1000H头指针 1020H 1080H 10C0H2.2 关键算法分析1、关键算法：1：头插法自然语言描述：a:在堆中建立新结点b:将a[i]写入到新结点的数据域c:修改新结点的指针域d:修改头结点的指针域。

将新结点加入链表中伪代码描述a:Node <T> * s=new Node <T>b:s->data=a[i]c:s->next=front->next;d:front->next=s2：尾插法自然语言描述：a:在堆中建立新结点：b:将a[i]写入到新结点的数据域：c:将新结点加入到链表中d:修改修改尾指针伪代码描述a:Node <T> * s=new Node <T>b:s->data=a[i]c:r->next=s;d:r=s3：析构/删除函数自然语言描述：a:新建立一个指针，指向头结点b:判断要释放的结点是否存在，c:暂时保存要释放的结点d:移动a中建立的指针e:释放要释放的指针伪代码描述a:Node <T> * p=frontb:while(p)c:front=pd:p=p->nexte:delete front4：按位查找函数自然语言描述：a:初始化工作指针p和计数器j，p指向第一个结点，j=1b:循环以下操作，直到p为空或者j等于1b1：p指向下一个结点b2：j加1c:若p为空，说明第i个元素不存在，抛出异常d:否则，说明p指向的元素就是所查找的元素，返回元素地址伪代码描述a:Node <T> * p=front->next;j=1;b:while(p&&j!=1)b1:p=p->nextb2:j++c:if(!p) throw ”error”d:return p5：按位查找函数自然语言描述：a:初始化工作指针p和计数器j，p指向第一个结点，j=1b:循环以下操作，找到这个元素或者p指向最后一个结点 b1：判断p 指向的结点是不是要查找的值，如果是，返回j，否则p指向下一个结点，并且j 的值加一c:如果找到最后一个结点还没有找到要查找的元素，返回查找失败信息伪代码描述a:Node <T> * p=front->next;j=1;b:while(p)b1: if(p->next==x) return jp=p->nextj++c:return “error”6：插入函数自然语言描述：a:在堆中建立新结点b:将要插入的结点的数据写入到新结点的数据域c:修改新结点的指针域d:修改前一个指针的指针域，使其指向新插入的结点的位置伪代码描述a:Node <T> * s=new Node <T>;b:s-data=p->datac:s->next=p->nextd:p->next=se:p->data=x7：删除函数自然语言描述：a:从第一个结点开始，查找要删除的位数i前一个位置i-1的结点b:设q指向第i个元素c:将q元素从链表中删除d:保存q元素的数据e:释放q元素伪代码描述a:q=p->nextb:p->next=q->nextc:x=q->datad:delete q8：遍历打印函数自然语言描述：a:判断该链表是否为空链表，如果是，报错b:如果不是空链表，新建立一个temp指针c:将temp指针指向头结点d:打印temp指针的data域e:逐个往后移动temp指针，直到temp指针的指向的指针的next域为空伪代码描述If front->next==NULLThrow ”an empty list ”Node<T>* temp=front->next;while(temp->next){ cout<<temp->data<<" ";temp=temp->next;}9：获取链表长度函数自然语言描述：a:判断该链表是否为空链表，如果是，输出长度0b:如果不是空链表，新建立一个temp指针，初始化整形数n为0c:将temp指针指向头结点d:判断temp指针指向的结点的next域是否为空，如果不是，n加一，否则return n e: 使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next域为0，返回n 伪代码描述int n=0if ront->next==NULLn=0;else{ Node<T>* temp=front->next;while(temp->next)n++;temp=temp->next;}return n;2、代码详细分析：（1）从第一个结点开始，查找节点，使它的数据比x大，设p指向该结点：while (x>p->data) { p=p->next;}（2）新建一个节点s，把p的数据赋给s：s->data=p->data;（3）把s加到p后面：s->next=p->next; p->next=s;（4）p节点的数据用x替换：p->data=x;示意图如图所示3、关键算法的时间复杂度：O（1)3.程序运行结果程序截图1. 流程图：开始初始化一个对象2.测试条件：插入、删除元素的位置一定要在链表的长度围之。

数据结构实验报告实验名称：实验四——排序学生姓名：班级：班内序号：学号：日期：2014年12月19日1．实验要求实验目的通过实现下述实验内容，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。

实验内容使用简单数组实现下面各种排序算法，并进行比较。

排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性。

2. 程序分析首先，题目要求测试不同的数据，所以可以手动输入待排序元素。

其次，由于对一组数据要求用不同的排序算法来处理，所以需要一个复制函数把排序前的无序数组寄存出去，为下一次排序做准备。

再次，由于每次排序后都需要把排序后的结果打印出来，代码是一样的，根据相同的代码可以封装成一个函数的思想，所以还需增加一个打印函数。

2.1 存储结构本程序采用简单数组来储存输入的待排序数组2.2 关键算法分析核心算法思想：1. 利用教材讲述的基本算法思想，实现七种排序算法，统计其运行相关数据。

2. 将七种排序函数入口地址作为函数指针数组，实现快速调用和统计。

使得程序代码可读性增、结构更加优化。

关键算法思想描述和实现：关键算法1：实现七种算法的基本排序功能。

1、插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。

插入排序的思想是：每次从无序区取一元素将其添加到有序区中。

2、希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。

北邮数据结构实验报告图一、实验报告规范实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下七个内容：1.需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么?明确规定：(1)输入的形式和输入值的范围;(2)输出的形式;(3)程序所能达到的功能;(4)测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。

2.概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。

3.详细设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法;对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序);画出函数的调用关系图。

4.调试分析内容包括：(1)调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析;(2)算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想;(3)经验和体会等。

5.用户使用说明说明如何使用你编写的程序，详细列出每一步的操作步骤。

6.测试结果列出你的测试结果，包括输入和输出。

这里的测试数据应该完整和严格，最好多于需求分析中所列。

7.附录带注释的源程序。

如果提交源程序软盘，可以只列出程序文件名的清单。

值得注意的是，实习报告的各种文档资料，如：上述中的前三部分要在程序开发的过程中逐渐充实形成，而不是最后补写(当然也可以应该最后用实验报告纸誊清或打印)。

数据结构实验报告;实验名称：实验一线性表实现一个多项式;学生姓名：黄锦雨;班级：XX211109;班内序号：20;学号：XX210263;日期：XX年10月31日;实验目的：;1.熟悉C++语言的基本编程方法，掌握集成编译环;2.学习指针、模板类、异常处理的使用;3.掌握线性表的操作的实现方法;4.学习使用线性表解决实际问题的能力;实验内容：;数据结构实验报告实验名称：实验一线性表实现一个多项式学生姓名：黄锦雨班级：XX211109班内序号： 20学号： XX210263日期： XX年10月31日实验目的：1.熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法2.学习指针、模板类、异常处理的使用3.掌握线性表的操作的实现方法4.学习使用线性表解决实际问题的能力实验内容：利用线性表实现一个一元多项式Polynomialf(x) = a0 + a1x + a2x2 + a3x3 + … + anxn要求：1. 能够实现一元多项式的输入和输出2. 能够进行一元多项式相加3. 能够进行一元多项式相减4. 能够计算一元多项式在x处的值5. 能够计算一元多项式的导数(选作)6. 能够进行一元多项式相乘(选作)7. 编写测试main()函数测试线性表的正确性2. 程序分析由于多项式是线性结构，故选择线性表来实现，在这个程序中我采用的是单链表结构，每个结点代表一个项，多项式的每一项可以用其系数和指数唯一的表示。

数据结构实验报告实验名称：实验四——排序学生姓名：1．实验要求实验目的：通过选择实验内容中的两个题目之一，学习、实现、对比、各种排序的算法，掌握各种排序算法的优劣，以及各种算法使用的情况。

题目2：使用简单数组实现下面各种排序算法，并进行比较。

排序算法如下：1、插入排序；2、希尔排序；3、冒泡排序；4、快速排序；5、简单选择排序；6、堆排序；7、归并排序；8、基数排序（选作）；9、其他。

具体要求如下：1、测试数据分成三类：正序、逆序、随机数据。

2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙。

4、对2和3的结果进行分析，验证上述各种算法的时间复杂度。

5、编写main（）函数测试各种排序算法的正确性。

2. 程序分析2.1 存储结构2.2 关键算法分析一、关键算法：1、插入排序a、取排序的第二个数据与前一个比较b、若比前一个小，则赋值给哨兵c、从后向前比较，将其插入在比其小的元素后d、循环排序2、希尔排序a、将数组分成两份b、将第一份数组的元素与哨兵比较c、若其大与哨兵，其值赋给哨兵d、哨兵与第二份数组元素比较，将较大的值赋给第二份数组e、循环进行数组拆分3、对数据进行编码a、取数组元素与下一个元素比较b、若比下一个元素大，则与其交换c、后移，重复d、改变总元素值，并重复上述代码4、快速排序a、选取标准值b、比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后指针前移，重新比较c、否则后面元素赋给前面元素d、若后指针元素小于标准值，前指针后移，重新比较e、否则前面元素赋给后面元素5、简单选择排序a、从数组中选择出最小元素b、若不为当前元素，则交换c、后移将当前元素设为下一个元素6、堆排序a、生成小顶堆b、将堆的根节点移至数组的最后c、去掉已做过根节点的元素继续生成小顶堆d、数组倒置7、归并排序a、将数组每次以1/2拆分，直到为最小单位b、小相邻单位数组比较重排合成新的单位c、循环直至完成排序二、代码详细分析：1、插入排序关键代码：①取排序的第二个数据与前一个比较：if(r[i]<r[i-1])②若比前一个小，则赋值给哨兵：r[0]=r[i];③从后向前比较，将其插入在比其小的元素后：for(j=i-1;r[0]<r[j];j--){r[j+1]=r[j];a++;} r[j+1]=r[0];④循环排序2、希尔排序关键代码：①将数组分成两份：d=n/2②将第一份数组的元素与哨兵比较：for(int i=d+1;i<=n;i++)③若其大与哨兵，其值赋给哨兵：if(r[0]<r[i-d]){ r[0]=r[i];}④哨兵与第二份数组元素比较，将较大的值赋给第二份数组：for(j=i-d;j>0&&r[0]<r[j];j=j-d) {r[j+d]=r[j]; }⑤循环进行数组拆分：for(int;d>=1;d=d/2)3、冒泡排序关键代码：①取数组元素与下一个元素比较： for(int i=1;i<bound;i++)if(r[i]>r[i+1])②若比下一个元素大，则与其交换： r[0]=r[i]; r[i]=r[i+1]; r[i+1]=r[0];③后移，重复：for(int i=1;i<bound;i++)④改变总元素值，并重复上述代码：int bound=pos;4、快速排序关键代码：①选取标准值：r[0]=r[i]②比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后指针前移，重新比较：while(i<j&&r[j]>=flag) {j--;}③否则后面元素赋给前面元素：r[i]=r[j];④若后指针元素小于标准值，前指针后移，重新比较：while(i<j&&r[i]<=flag){i++;}⑤否则前面元素赋给后面元素：r[j]=r[i];5、简单选择排序关键代码：①从数组中选择出最小元素： for(int j=i+1;j<=n;j++)②{if(r[j]<r[index]) index=j; }③若不为当前元素，则交换：if(index!=i) {r[0]=r[i]; r[i]=r[index];r[index]=r[0];}④后移将当前元素设为下一个元素：for(int i=1;i<n;i++)6、堆排序关键代码：①生成小顶堆：while(j<=m) {if(j<m&&r[j]>r[j+1]) {j++;}②if(r[i]<r[j]) {break; }③else{ int x; x=r[i]; r[i]=r[j]; r[j]=x; i=j; j=2*i; }}④将堆的根节点移至数组的最后： x=r[1]; r[1]=r[n-i+1]; r[n-i+1]=x;⑤去掉已做过根节点的元素继续生成小顶堆：sift(r,1,n-i,x,y);⑥数组倒置输出: for(int i=n;i>0;i--)cout<<r[i]<<" ";7、归并排序关键代码：①将数组每次以1/2拆分，直到为最小单位：mid=(low+high)/2;②小相邻单位数组比较重排合成新的单位：while(i<=m&&j<=high)if(L.r[i]<=L.r[j]) t[k++]=L.r[i++];else t[k++]=L.r[j++];while(i<=m) t[k++]=L.r[i++];while(j<=high) t[k++]=L.r[j++];for(i=low,k=0;i<=high;i++,k++) L.r[i]=t[k];三、计算关键算法的时间、空间复杂度插入排序O（n2）希尔排序O（n2）冒泡排序O（n2）快速排序O（nlog2n）简单选择排序O（n2）堆排序O（nlog2n）归并排序O（nlog2n）3. 程序运行结果1、测试主函数流程：流程图如图所示流程图示意图程序运行结果图如下：2、测试条件：按题目要求分别输入同组数据的正序、逆序、随机序列进行测试。

数据构造实验报告1．实验要求〔1〕实验目的通过选择下面5个题目之一进展实现，掌握如下内容：➢掌握图根本操作的实现方法➢了解最小生成树的思想和相关概念➢了解最短路径的思想和相关概念➢学习使用图解决实际问题的能力(2)实验内容根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。

图的根本功能：1、图的建立2、图的销毁3、深度优先遍历图4、广度优先遍历图5、使用普里姆算法生成最小生成树6、使用克鲁斯卡尔算法生成最小生成树7、求指定顶点到其他各顶点的最短路径8、其他：比方连通性判断等自定义操作编写测试main()函数测试图的正确性2. 程序分析2.1 存储构造图：(1)带权值的无向图V09 6V1 2 V2(2)带权值的有向图V063 9 4V1 2 V2 2.2 关键算法分析〔1〕深度优先遍历int visited[MAXSIZE]={false};template<class T>void MGraph<T>::DFS(int v){cout<<vertex[v];visited[v]=true;for(int j=0;j<vNum;j++)if(arc[v][j]==1&&!visited[j])DFS(j);}时间复杂度：O(n²)〔2〕广度优先遍历int queue[MAXSIZE];int f=0,r=0;cout<<vertex[v];visit[v]=true;queue[++r]=v;while(f!=r){v=queue[++f];for(int j=0;j<vNum;j++){if(arc[v][j]==1&&!visit[j]){cout<<vertex[j];visit[j]=true;queue[++r]=j;}时间复杂度：O〔n²〕〔3〕普利姆算法int adjvex[MAXSIZE];int lowcost[MAXSIZE];int MAX=10000;template<class T>int mininum(MGraph<T> G,int a[]){int min=MAX;int k=0;for(int i=0;i<G.vNum;i++){if(a[i]!=0&&a[i]<min)//寻找U-{V-U}中边权值最小的顶点{min=a[i];k=i;}}return k;}template<class T>void MGraph<T>:: Prim(MGraph G){for(int i=0;i<G.vNum;i++){adjvex[i]=0;lowcost[i]=G.arcs[0][i];}lowcost[0]=0;//初始化U={vo}for(int i=1;i<G.vNum;i++){int k=mininum(G,lowcost);//求下一个边权值最小的邻接点 cout<<'V'<<adjvex[k]<<"->V"<<k<<endl;lowcost[k]=0;for(int j=0;j<G.vNum;j++){if(lowcost[j]!=0&&G.arcs[k][j]<lowcost[j]){lowcost[j]=G.arcs[k][j];adjvex[j]=k;}}}}时间复杂度：O(n²)〔4〕克鲁斯卡尔算法template<class T>void GenSortEdge(MGraph<T> G,VEdge E[])//获取EdgeList{int k=0,i,j;for(i=0;i<G.vNum;i++)//边赋值for(j=i;j<G.vNum;j++)if(G.arcs[i][j]!=MAX){E[k].fromV=i;E[k].endV=j;E[k].weight=G.arcs[i][j];k++;}for(i=0;i<G.arcNum-1;i++){for(j=i+1;j<G.arcNum;j++)if(E[i].weight>E[j].weight){VEdge t=E[i];E[i]=E[j];E[j]=t;}}}const int MAX_VERTEXT=20;template<class T>void MGraph<T>:: Kruskal(VEdge E[],int n,int e){int vset[MAX_VERTEXT];for(int i=0;i<n;i++) vset[i]=i;//初始化vsetint k=0,j=0;while(k<n-1){int m=E[j].fromV,n=E[j].endV;int sn1=vset[m];//m所属的集合int sn2=vset[n];//n所属的集合if(sn1!=sn2){cout<<'V'<<m<<"->V"<<n<<endl;k++;for(int i=0;i<n;i++){if(vset[i]==sn2)//集合编号为sn2的全部改为sn1vset[i]=sn1;时间复杂度：O(n²)〔5〕求最短路径，连通性判断int dist[MAXSIZE][MAXSIZE];int path[MAXSIZE][MAXSIZE];template<class T>void Floyd(MGraph<T> G){for(int i=0;i<G.vNum;i++) //寻找最短路径for(int j=0;j<G.vNum;j++){dist[i][j]=G.arcs[i][j];if(dist[i][j]!=MAX_VALUE)path[i][j]=i;elsepath[i][j]=-1;}for(int k=0;k<G.vNum;k++)for(int i=0;i<G.vNum;i++)for(int j=0;j<G.vNum;j++)if(dist[i][k]+dist[k][j]<dist[i][j])//更新迭代数组Disk[][]{dist[i][j]=dist[i][k]+dist[k][j];path[i][j]=k;}cout<<"任意两点间的最短路径长度(以矩阵表示〕："<<endl;int l=1;for(int i=0;i<G.arcNum;i++)for(int j=0;j<G.arcNum;j++){cout<<dist[i][j]<<" ";l++;if(l>G.arcNum) {cout<<endl;l=1;}}}时间复杂度：O(n³)3. 程序运行结果〔1〕流程图：初始化带权值的无向图深度优先遍历，广度优先遍历用普利姆算法求最小生成树用克鲁斯卡尔算法求最小生成树初始化带权值的有向图用Floyd算法求任意两点间最短路径，并判断连通性删除图〔2〕本程序所用的图带权值的无向图V09 6V1 2 V2带权值的有向图V063 9 4V1 2 V2〔3〕程序结果4. 总结〔1〕遇到的问题：私有数据访问权的问题，在编程时应该注意〔2〕心得体会：通过这次实验，我掌握了图根本操作的实现方法，了解最小生成树的思想和相关概念，了解最短路径的思想和相关概念等等。