北邮数据结构实验报告排序

数据结构实验报告

实验名称：实验四——排序

学生姓名：

班级：

班内序号：

学号：

日期：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、希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，

待整个序列基本有序时，再对全体记录进行一次直接插入排序。

3、冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。

4、快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则

大于基准，然后对两部分重复上述过程，直至整个序列排序完成。

5、选择排序：从待排序的记录序列中选择关键码最小（或最大）的记录并将它与序列中

的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止。

2.3 其他

时间复杂度与空间复杂度

理论分析可以得出各种排序算法的时间复杂度和空间复杂度，如下表所示：

排序方法平均情况最好情况

辅助空间

最坏情况

直接插入排序O(n2) O(n) O(n2) O(1)

希尔排序O(nlog2n)~O(n2) O(n1.3) O(n2) O(1)

起泡排序O(n2) O(n) O(n2) O(1)

快速排序O(nlog2n) O(nlog2n) O(n2) O(log2n)~O(n2) 简单选择排O(n2) O(n2) O(n2) O(1)

3. 程序运行结果程序运行框图：

实际测试和分析：

实际运行结果如下：

1．正序排序

2．倒序排序

3．乱序排序

4. 总结

1、在初期构思代码的时候，首先构造了各种算法的基本实现代码，封装成类，已经能够实现七种排序的基本功能，并且测试无误。后来考虑能否优化本程序，首先考虑到测试算法的需求，需要大量随机数，因为增添了随机函数发生器，满足各种测试条件的需求。之后考虑如何能简化代码以实现多达七种排序算法的简单调用、乱序和顺序以及逆序数据的分别排序和性能指标统计、算法移动次数和比较次数的精确统计。如果设计不合理，将使得主调函数的调用代码冗长，可读性变差。因而采用了函数指针数组和统一的接口函数，采用二维数组存储移动次数和比较次数，调用精确的系统函数实现时间的统计。此外还添加了一些列优化，特别是函数封装的方法，使得程序的结构变得更加合理，版面风格也变得好看，可读性增强。

2、程序的优化是一个艰辛的过程，如果只是实现一般的功能，将变得容易很多，当加上优化，不论是效率还是结构优化，都需要精心设计。这次做优化的过程中，遇到不少阻力。由于优化中用到很多类的封装和访问控制方面的知识，而这部分知识恰好是大一一年学习的薄弱点。因而以后要多花力气学习C++编程语言，必须要加强这方面的训练，这样才能在将编程思想和数据结构转换为代码的时候能得心应手。

3、改进：本程序代码设计时运用了递归的调用方式，效率还可以通过将其转换为栈模拟的方式得以提高。在实现类的封装的时候为了共享数据采用了友元函数的方式，考虑能否使用其他方式使得类的封装更加完善。

数据结构实验8实验报告

暨南大学本科实验报告专用纸 课程名称数据结构实验成绩评定 实验项目名称习题6.37 6.38 6.39 指导教师孙世良 实验项目编号实验8 实验项目类型实验地点实验楼三楼机房学生姓名林炜哲学号2013053005 学院电气信息学院系专业软件工程 实验时间年月日午～月日午温度℃湿度(一)实验目的 熟悉和理解二叉树的结构特性； 熟悉二叉树的各种存储结构的特点及适用范围； 掌握遍历二叉树的各种操作及其实现方式。 理解二叉树线索化的实质是建立结点与其在相应序列中的前去或后继之间的直接联系，熟练掌握二叉树的线索化的过程以及在中序线索化树上找给定结点的前驱和后继的方法。 (二)实验内容和要求 6.37试利用栈的基本操作写出先序遍历的非递归形式的算法。 6.38同题6.37条件，写出后序遍历的非递归算法（提示：为分辨后序遍 历时两次进栈的不同返回点需在指针进栈时同时将一个标志进栈）。 6.39假设在二叉链表的结点中增设两个域：双亲域以指示其双亲结点； 标志域以区分在遍历过程中到达该结点时应继续向左或向右或访问该节点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。(三)主要仪器设备 实验环境：Microsoft Visual Studio 2012 (四)源程序

6.37： #include #include #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define TRUE 1 #define FALSE 0 typedef struct bitnode{ char data; struct bitnode *lchild,*rchild; }bitnode,*bitree; void create(bitree &T){ char t; t=getchar(); if(t==' ') T=NULL; else{ if( !( T=(bitnode*)malloc(sizeof(bitnode)) ) ) exit(0); T->data=t; create(T->lchild); create(T->rchild); } } typedef struct{ bitree *base; bitree *top; int stacksize; }sqstack; void initstack(sqstack &S){ S.base=(bitree*)malloc(STACK_INIT_SIZE *sizeof(bitree)); if(!S.base) exit(0); S.top=S.base; S.stacksize=STACK_INIT_SIZE; } void Push(sqstack &s,bitree e){ if(s.top - s.base >= s.stacksize){ s.base =

北邮信通院数据结构实验报告三哈夫曼编码器之欧阳光明创编

数据结构实验报告 欧阳光明（2021.03.07） 实验名称：实验三树——哈夫曼编/解码器 学生姓名： 班级： 班内序号： 学号： 日期： 2014年12月11日 1．实验要求 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统 计，统计每个字符的频度，并建立赫夫曼树 2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编 码，并将每个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并 将编码后的字符串输出。 4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符 串进行译码，并输出译码结果。 5、打印(Print)：以直观的方式打印赫夫曼树（选作） 6、计算输入的字符串编码前和编码后的长度，并进行分析， 讨论赫夫曼编码的压缩效果。 测试数据： I love data Structure, I love Computer。I will try my best to study

data Structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现的次数统计频度，对没有 出现的 字符一律不用编码。 2. 程序分析 2.1 存储结构 Huffman树 给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，其中带权路径长度最小的二叉树称为Huffman树，也叫做最优二叉树。

weight lchild rchildparent 2-1-1-1 5-1-1-1 6-1-1-1 7-1-1-1 9-1-1-1 weight lchild rchild parent

数据结构实验五-查找与排序的实现

实验报告 课程名称数据结构实验名称查找与排序的实现 系别专业班级指导教师11 学号实验日期实验成绩 一、实验目的 (1)掌握交换排序算法（冒泡排序）的基本思想； (2)掌握交换排序算法（冒泡排序）的实现方法； (3)掌握折半查找算法的基本思想； (4)掌握折半查找算法的实现方法； 二、实验内容 1.对同一组数据分别进行冒泡排序，输出排序结果。要求： 1)设计三种输入数据序列：正序、反序、无序 2)修改程序： a)将序列采用手工输入的方式输入 b)增加记录比较次数、移动次数的变量并输出其值，分析三种序列状态的算法时间复杂 性 2.对给定的有序查找集合，通过折半查找与给定值k相等的元素。 3.在冒泡算法中若设置一个变量lastExchangeIndex来标记每趟排序时经过交换的最后位置， 算法如何改进？ 三、设计与编码 1.本实验用到的理论知识 2.算法设计

3.编码 package sort_search; import java.util.Scanner; public class Sort_Search { //冒泡排序算法 public void BubbleSort(int r[]){ int temp; int count=0,move=0; boolean flag=true; for(int i=1;ir[j+1]){ temp=r[j]; r[j]=r[j+1]; r[j+1]=temp; move++; flag=true; } } } System.out.println("排序后的数组为："); for(int i=0;i

数据结构实验报告

数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include #include #include #include "Stack.h"//栈的头文件，没有用上 typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree; intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL) { T = (BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1; } else if(keydata){ InsertBST(T->lChild,key); } else if(key>T->data){ InsertBST(T->rChild,key); } else return 0; } BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL; inti=0; while(i

北邮数据结构实验3哈夫曼编码

数据结构实验报告 实验名称：实验3——哈夫曼编码 学生姓名： 班级： 班内序号： 学号： 日期：2013年11月24日 1．实验要求 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个 字符的频度，并建立赫夫曼树 2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每 个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的 字符串输出。 4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译 码，并输出译码结果。 5、打印(Print)：以直观的方式打印赫夫曼树（选作） 6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼 编码的压缩效果。 2. 程序分析 2.1存储结构： struct HNode { char c;//存字符内容 int weight; int lchild, rchild, parent; }; struct HCode

{ char data; char code[100]; }; //字符及其编码结构 class Huffman { private: HNode* huffTree; //Huffman树 HCode* HCodeTable; //Huffman编码表 public: Huffman(void); void CreateHTree(int a[], int n); //创建huffman树 void CreateCodeTable(char b[], int n); //创建编码表 void Encode(char *s, string *d); //编码 void Decode(char *s, char *d); //解码 void differ(char *,int n); char str2[100];//数组中不同的字符组成的串 int dif;//str2[]的大小 ~Huffman(void); }; 结点结构为如下所示： 三叉树的节点结构： struct HNode//哈夫曼树结点的结构体 { int weight;//结点权值 int parent;//双亲指针 int lchild;//左孩子指针 int rchild;//右孩子指针 char data;//字符 }; 示意图为： int weight int parent int lchild int rchild Char c 编码表节点结构：

北邮 大数据结构 哈夫曼树报告材料

数据结构 实 验 报 告 实验名称：哈夫曼树

学生：袁普 班级：2013211125班班序号：14号 学号：2013210681 日期：2014年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; //被编码的字符

数据结构-实验五-图

数据结构与算法课程实验报告实验五：图的相关算法应用 姓名：cll 班级： 学号：

【程序运行效果】 一、实验内容： 求有向网络中任意两点之间的最短路 实验目的： 掌握图和网络的定义，掌握图的邻接矩阵、邻接表和十字链表等存储表示。掌握图的深度和广度遍历算法，掌握求网络的最短路的标号法和floyd算法。 二、问题描述： 对于下面一张若干个城市以及城市间距离的地图，从地图中所有可能的路径中求出任意两个城市间的最短距离及路径，给出任意两个城市间的最短距离值及途径的各个城市。 三、问题的实现： 3.1数据类型的定义 #define MAXVEX 50 //最大的顶点个数 #define MAX 100000 typedef struct{ char name[5]; //城市的名称

}DataType; //数据结构类型 typedef struct{ int arcs[MAXVEX][MAXVEX]; //临接矩阵 DataType data[MAXVEX]; //顶点信息 int vexs; //顶点数 }MGraph,*AdjMetrix; //邻接矩阵表示图 3.2主要的实现思路： 用邻接矩阵的方法表示各城市直接路线的图，之后用Floyd算法求解两点直接的最短距离，并用递归的方法求出途经的城市。 主要源程序代码： #include #include #define MAXVEX 50 #define MAX 100000 typedef struct{ char name[5]; //城市的名称 }DataType; //数据结构类型 typedef struct{ int arcs[MAXVEX][MAXVEX]; //临接矩阵 DataType data[MAXVEX]; //顶点信息 int vexs; //顶点数 }MGraph,*AdjMetrix; //创建临接矩阵 void CreatGraph(AdjMetrix g,int m[][MAXVEX],DataType d[],int n){ /*g表示邻接矩阵，m[][MAXVEX]表示输入的邻接矩阵，d[]表示各城市的名称，n表示城市数目*/ int i,j; g->vexs = n; for(i=0;i < g->vexs;i++){ g->data[i] = d[i]; for(j=0;jvexs;j++){ g->arcs[i][j] = m[i][j]; } } } //求最短路径 void Floyd(AdjMetrix g,int F[][10],int path[][10]){ int i,j,k; for(i=0;ivexs;i++){ for(j=0;jvexs;j++){

北邮数据结构第四次实验题目一排序

数据结构实验报告实验名称：实验四排序（题目1） 姓名： 班级： 班内序号： 学号：

1．实验要求 实验目的：学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。实验内容：使用简单数组实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 要求： 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+1]=r[j];move++; comp++;} //循环中移动计数器++ comp++; //比较计数器++ r[j+1]=r[0];move++; //移动计数器++ } comp++; //比较计数器++ } cout<<"本次直接插入排序数据长度为："<=1;d=d/2) //以d 为增量在子序列中进行插入排序 { for(int i=d+1;i<=n;i++) //一趟希尔排序 { if(r[i]0&&r[0]

北邮数据结构实验四-链表排序

数据结构实验报告 实验名称：实验四——链表的排序 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 [内容要求] 使用链表实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、冒泡排序 3、快速排序 4、简单选择排序 5、其他 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其 中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒 （选作） 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度 编写测试main()函数测试线性表的正确性 代码要求 1、必须要有异常处理，比如删除空链表时需要抛出异常； 2、保持良好的编程的风格： 代码段与段之间要有空行和缩近 标识符名称应该与其代表的意义一致 函数名之前应该添加注释说明该函数的功能 关键代码应说明其功能 3、递归程序注意调用的过程，防止栈溢出

2. 程序分析 2.1 存储结构 [内容要求] 存储结构：双链表 2.2 关键算法分析 [内容要求] 定义类： template class LinkList { public: LinkList(){front = new Node ;front->next=rear;front->prior=NULL;rear=new Node;rear->next=NULL;rear->prior=front;} LinkList(T a[],int n); void BackLinkList(T a[]);//恢复原链表 ~LinkList();//析构函数 void PrintList();//打印数列 void InsertSort();//插入排序 void BubbleSort();//冒泡排序 Node * Partion(Node *i,Node *j);//快速排序中寻找轴值的函数 void Qsort(Node *i,Node *j);//快速排序 void SelectSort();//选择排序 Node*front; Node*rear; }; 成员函数包括：构造函数：单链表，打印单链表，插入排序，快速排序，冒泡排序，选择排序，析构函数 公有成员：头指针和尾指针 1、构造函数： LinkList::LinkList(T a[],int n) { front=new Node; rear=new Node; front->prior=NULL;front->next=rear; rear->next=NULL;rear->prior=front; Node *s; for (int i=n-1;i>=0;i--) {

北邮信通院数据结构实验报告三哈夫曼编码器

北京邮电大学电信工程学院 数据结构实验报告 实验名称：实验三树 ----- 哈夫曼编/解码器 学生姓名： 班级： 班内序号： 学号： 日期：2014年12月11日 1. 实验要求 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init):能够对输入的任意长度的字符串s进行统计，统计每个 字符的频度，并建立赫夫曼树 2、建立编码表(CreateTable)利用已经建好的赫夫曼树进行编码，并将每 个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的 字符串输出。 4、译码(Decoding)：禾U用已经建好的赫夫曼树对编码后的字符串进行译 码，并输出译码结果。 5、打印(Print):以直观的方式打印赫夫曼树(选作) 6计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。 测试数据： I love data Structure, I love Computer。I will try my best to study data Structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符 一律不用编码。

2. 程序分析 2.1存储结构 Huffman 树给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，其中带权路径 长度最小的二叉树称为Huffman 树，也叫做最优二叉树 哈夫虽树示意图 root 孩子双亲表示法 _____________________ JL________________ weight Ichild rchild pare nt

数据结构课程实验报告-实验5

数据结构课程实验报告-实验5

HUNAN UNIVERSITY 课程实习报告 题目：四则运算表达式求值 学生姓名康小雪 学生学号 20090810310 专业班级计科三班 指导老师李晓鸿 完成日期2010-10-24

一、需求分析 1．该程序可以从通过从键盘输入一个中缀表达式，判断该表达式是否合法，若合法将 其转化为后缀表达式，并计算其结果，否则说明该表达式错误 2．.输入的表达式包含数字和运算符及括号，之间用空格隔开 3．数字可以为整数和小数 4．运算结果保留两位小数 输入输出举例 输入：21+23*（12-6） 输出：21 23 12 6 -*+ 二、概要设计 在表达式中每个运算符应对应两个操作数，与二叉树中非叶子结点和叶子结点之间的关系刚好相同，于是，本题可采用二叉树来将中缀表达式变为后缀表达式。 最后用堆栈来实现后缀表达式的计算。 抽象数据类型 二叉树 ADT BiTree {

数据对象D：D是具有相同特性的数据元素集合 数据关系R： 若D为空集，则R为空集，则称BinaryTree 为空二叉树； 若D不为空集，否则R={H}，H是如下二元关系： （1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； （2）若D-{root}≠空集，则存在D-{root}的一个划分{D1,Dr} 且D1∩Dr=空集； （3）若D1≠空集，则D1中存在唯一元素x1，∈H,且存在D1shang de guanxi H1=H;ruo Dr≠空集，则Dr中存 在唯一的元素，xr，∈H，且 存在Dr上的关系Hr∈ H;H={,,H1,Hr}; （4）(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树，(Dr，{Hr})是一棵 符合本定义的二叉树，称为根的右子树基本操作P: InitBiTree（&T）

北邮信通院数据结构实验报告三哈夫曼编码器

数据结构实验报告 实验名称：实验三树——哈夫曼编/解码器 学生姓名： 班级： 班内序号： 学号： 日期：2014年12月11日 1．实验要求 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个 字符的频度，并建立赫夫曼树 2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每 个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的 字符串输出。 4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译 码，并输出译码结果。 5、打印(Print)：以直观的方式打印赫夫曼树（选作） 6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼 编码的压缩效果。 测试数据： I love data Structure, I love Computer。I will try my best to study data Structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的 字符一律不用编码。

2. 程序分析 2.1 存储结构 Huffman树 给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，其中带权路径长度最小的二叉树称为Huffman树，也叫做最优二叉树。 weight lchild rchild parent

2-1-1-1 5-1-1-1 6-1-1-1 7-1-1-1 9-1-1-1 weight lchild rchild parent 2-1-15 5-1-15 6-1-16 7-1-16 9-1-17 7017

数据结构实验报告模板

2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList&List) //单链表排序 ListClear(&L); //将单链表L中的所有元素删除，使单链表变为空表 ListDestroy(&L);//将单链表销毁 }ADT List 其他函数： 主函数； 结点类; 约瑟夫函数 2.1 存储结构

[内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template class CirList;//声明单链表类 template class ListNode{//结点类定义； friend class CirList;//声明链表类LinkList为友元类； Type data;//结点的数据域； ListNode*next;//结点的指针域； public: ListNode():next(NULL){}//默认构造函数； ListNode(const Type &e):data(e),next(NULL){}//构造函数 Type & GetNodeData(){return data;}//返回结点的数据值； ListNode*GetNodePtr(){return next;}//返回结点的指针域的值； void SetNodeData(Type&e){data=e;}//设置结点的数据值； void SetNodePtr(ListNode*ptr){next=ptr;} //设置结点的指针值； }; 单循环链表类： templateclass CirList { ListNode*head;//循环链表头指针 public: CirList(){head=new ListNode();head->next=head;}//构造函数，建立带头节点的空循环链表 ~CirList(){CirListClear();delete head;}//析构函数，删除循环链表 void Clear();//将线性链表置为空表 void AddElem(Type &e);//添加元素 ListNode *GetElem(int i)const;//返回单链表第i个结点的地址 void CirListClear();//将循环链表置为空表 int Length()const;//求线性链表的长度 ListNode*ListNextElem(ListNode*p=NULL);//返回循环链表p指针指向节点的直接后继，若不输入参数，则返回头指针 ListNode*CirListRemove(ListNode*p);//在循环链表中删除p指针指向节点的直接后继，且将其地址通过函数值返回 CirList&operator=(CirList&List);//重载赋

数据结构上机实验5

数据结构上机实验（五）递归 班级：学号：姓名： 上机时间：地点： 一、实验目的 1.理解递归的定义和递归模型。 2.掌握递归设计的一般方法，能用递归算法解决一些较复杂应用问题。 二、实验内容 1．编写程序求解皇后问题 要求：（1）皇后的个数n由用户输入，其值不能超过20； （2）采用递归方法求解。 2．编写一个程序求解背包问题 三、实验过程 1．了解常用函数所在的头文件 stdlib.h stdlib 头文件里包含了C语言的一些函数 该文件包含了的C语言标准库函数的定义 stdlib.h里面定义了五种类型、一些宏和通用工具函数。类型例如size_t、wchar_t、div_t、ldiv_t和lldiv_t；宏例如EXIT_FAILURE、EXIT_SUCCESS、RAND_MAX 和MB_CUR_MAX等等；常用的函数如malloc()、calloc()、realloc()、free()、system()、atoi()、atol()、rand()、srand()、exit()等等。具体的内容你自己可以打开编译器的include目录里面的stdlib.h头文件看看。 conio.h conio.h不是C标准库中的头文件。 conio是Console Input/Output（控制台输入输出）的简写，其中定义了通过控制台进行数据输入和数据输出的函数，主要是一些用户通过按键盘产生的对应操作，比如getch()函数等等。 &表示引用传递。在函数参数表中，出现带&这个的形参，表示引用传递。2．程序实现（以下代码仅起参考作用） （1）求解皇后问题 #include #include const int N=20; //最多皇后个数 int q[N]; //存放各皇后所在的行号 int cont=0; //存放解个数 void print(int n) //输出一个解 { cont++; int i; printf(" 第%d个解：",cont);

北邮数据结构实验 第三次实验 排序

数据结构实验报告 1．实验要求 (1)实验目的 通过选择下面两个题目之一，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。 (2)实验内容 使用简单数组实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序（选作） 7、归并排序（选作） 8、基数排序（选作） 9、其他 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其 中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒 （选作） 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度 编写测试main()函数测试排序算法的正确性。 2. 程序分析 2.1 存储结构 顺序表: 示意图： 2.2 关键算法分析 （1）测试数据的产生：正序、逆序、随机数据 用两个数组实现乱序、顺序以及逆序数据的排序。 基本思想为：随机序列产生一个指定长度的乱序序列，然后通过memcpy()函数拷贝到第

二个数组里，第二个数组作为乱序序列的保存数组，每次对第一个数组进行排序，之后拷贝第二个数组中的乱序序列到第一个数组，实现各次乱序排列。只要算法正确（第一步可以检验），之后顺序排列只需反复对第一个数组进行操作即可，再后用第二个数组保存逆序数组，然后同样在每次排序之后复制第二数组存储的乱序序列到第一组，对第一组反复排序即可。 <1> pRandom1=new long int[Max+1];pRandom2=new long int[Max+1]; <2> srand((unsigned)time(NULL)); for(int i = 1; i <= Max;i++ ) pRandom2[i]=rand(); <3> memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long int)); （2）排序算法： <1>插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。 /1/int j=0; /2/ for(int i =2; i <= Max;i++) parray[0]=parray[i];comparetimes[0]++; /4/parray[j+1]=parray[0];movetimes[0]+=2; 示意图： r1,r2,r3,…,ri-1,ri,ri+1,…,rn 有序区待插入无序区 <2>希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。 int Sort::ShellSort(long int parray[]) {int j=0; for(int d=Max/2;d>=1;d/=2) {for(int i=d+1;i<=Max;i++) { parray[0]=parray[i]; comparetimes[1]++; for(j=i-d;j>0 && parray[0]冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。 int Sort::BubbleSort(long int parray[])

数据结构实验5 (1)

《数据结构》实验报告 实验序号：5 实验项目名称：队列的操作学号姓名专业、班 实验地点指导教师实验时间 一、实验目的及要求 1. 熟悉队列的基本概念； 2. 掌握队列的链式表存储结构； 3．掌握队列的应用。 二、实验设备（环境）及要求 微型计算机； windows 操作系统； Microsoft Visual Studio 6.0集成开发环境。 三、实验内容与步骤 1.C++的库函数中已经实现了队列，引用方法为#include ，请上网查阅资料，完成习题。 ①创建一个队列。 ②将a、b、c、d、e、f依次入队。 ③若队列不为空，将元素出队并打印输出。 2.以下的链式队列采用队头指针和队尾指针分别跟踪队列的头尾两端，请删除队尾指针，只使用队头指针实现队列的初始化、入队、出队和销毁队列。 #include #include #define ERROR 1 #define OK 0 #define OVERFLOW 1 typedef int QElemType; typedef int Status;

//用 e 返回其值，并返回OK；否则返回ERROR QueuePtr p; if (Q.front == Q.rear) return ERROR; p = Q.front->next; e = p->data; Q.front->next = p->next; if (Q.rear == p) Q.rear = Q.front; free (p); return OK; } int main() { int i,n=10; QElemType e; LinkQueue Q; InitQueue(Q); //初始化队列 printf("元素入队"); for(i=0;i #include #define ERROR 1 #define OK 0

北京邮电大学信通院数据结构实验三——哈夫曼树实验报告

2009级数据结构实验报告 实验名称：实验三——哈夫曼编/解码器的实现 学生姓名：陈聪捷 日期：2010年11月28日 1．实验要求 一、实验目的： 了解哈夫曼树的思想和相关概念； 二、实验内容： 利用二叉树结构实现哈夫曼编/解码器 1.初始化：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树。 2.建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。 3.编码：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。 4.译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。 5.打印：以直观的方式打印哈夫曼树。 6.计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈夫曼编码的压缩效果。 7.用户界面可以设计成“菜单”方式，能进行交互，根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。 2. 程序分析 存储结构 二叉树 template class BiTree { 算法伪代码： 1.初始化链表的头结点 2.获得输入字符串的第一个字符，并将其插入到链表尾部,n=1(n记录的是链表 中字符的个数) 3.从字符串第2个字符开始，逐个取出字符串中的字符 将当前取出的字符与链表中已经存在的字符逐个比较，如果当前取出的 字符与链表中已经存在的某个字符相同，则链表中该字符的权值加1。

如果当前取出的字符与链表中已经存在的字符都不相同，则将其加入到 链表尾部，同时n++ =n(tSize记录链表中字符总数，即哈夫曼树中叶子节点总数) 5.创建哈夫曼树 6.销毁链表 源代码： void HuffmanTree::Init(string Input) { Node *front=new Node; 建哈夫曼树（void HuffmanTree::CreateCodeTable(Node *p)）算法伪代码： 1.创建一个长度为2*tSize-1的三叉链表 2.将存储字符及其权值的链表中的字符逐个写入三叉链表的前tSize个结点 的data域，并将对应结点的孩子域和双亲域赋为空 3.从三叉链表的第tSize个结点开始，i=tSize 3.1从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其下 标x,y。 3.2将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点 3.3将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为i 结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i结 点的双亲设置为空 4. 根据哈夫曼树创建编码表 源代码： void HuffmanTree::CreateHTree(Node *p,int n) { root= new BiNode[2*n-1]; ata=front->count; root[i].lchild=-1; root[i].rchild=-1; root[i].parent=-1; front=front->next; } front=p; int New1,New2; for(i=n;i<2*n-1;i++) { SelectMin(New1,New2,0,i); arent=root[New2].parent=i; ata=root[New1].data+root[New2].data;child=New1; root[i].rchild=New2; root[i].parent=-1; } CreateCodeTable(p); 始化编码表 2.初始化一个指针，从链表的头结点开始，遍历整个链表 将链表中指针当前所指的结点包含的字符写入编码表中 得到该结点对应的哈夫曼树的叶子结点及其双亲 如果哈夫曼树只有一个叶子结点，将其字符对应编码设置为0