北邮数据结构实验报告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 void BiTree::Create(Node *&R,T* buf,int i)

{

if (buf[i-1]==0)

R = NULL;

else

{

R=new Node;

R->data = buf[i-1];

Create(R->lch, buf, 2*i);

Create(R->rch, buf, 2*i+1);

}

二：前序遍历二叉树： A. 自然语言描述： 1：建立栈

2：判断该栈是否为空并且根节点是否为空指针

3：如果根节点不是空指针，则输出它的data 域，并且是它入栈 4：入栈后将根节点指针指向它的左孩子 5：如果根节点是空指针

6：则根节点出栈，并且指向根节点的指针指向它的右孩子 B.代码详细分析：

template void BiTree::Preorder(Node *R) {

Stack*> 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 void BiTree::Inorder(Node *R)

{

Stack*> 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 void BiTree::Postorder(Node *R) { if (R!=NULL) { Postorder(R->lch); Postorder(R->rch); Print(R->data); } }

五：层序遍历二叉树： A.自然语言描述：

1：判断根节点是否为空 2：如果根节点不为空

} }

2

3

3：输出根节点的data 域

4：递归调用层续遍历函数，函数的参数改为根节点的左孩子 5：递归调用层序遍历函数，函数的参数改为跟结点的右孩子 B.代码详细分析：

template void BiTree::Levelorder(Node *R) {

Queue*> Q;

while(!Q.IsEmpty() || (R!=NULL)) {

if (R!=NULL) {

Print(R->data);

Q.EnQueue(R->lch); Q.EnQueue(R->rch); }

R=Q.DelQueue(); } }

六：求二叉树的深度：

A.自然语言描述：

1：判断根节点是否为空，如果根节点为空，返回0

2：如果根节点不为空但是根节点的左右孩子同时为空，返回1 3：如果以上两个条件都不成立

4：递归调用求二叉树的深度，函数的参数改为根节点的左孩子，并且深度初始化为1 5：递归调用求二叉树的深度，函数的参数改为跟结点的右孩子，并且深度初始化为0 6：返回4与5步中得出深度较大的那个数作为二叉树的深度数 B.代码详细分析：

template int BiTree::GetDepth(Node *R,int d) {

if (R==NULL) return d;

if ((R->lch==NULL) && (R->rch==NULL)) return d+1; else

}

2

3

{

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 void BiTree::Destroy(Node *R) {

if (R!=NULL) { Destroy(R->lch); Destroy(R->rch); delete R; } }

}

}

2

3

} 七 ：

2

3

八：求二叉树的叶子结点数： A.自然语言描述：

1：判断根节点是否为空，如果为空，返回0

2：如果根节点不为空，切根节点的左右孩子同时为空，返回1

3：递归调用求二叉树的叶子节点数函数，参数改为根节点的左孩子 4：递归调用求二叉树的叶子结点数函数，参数改为根节点的右孩子 5：返回根节点的左右子树的叶子结点数之和 B.代码详细分析：

template int BiTree::LeafNodeCount(Node *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.自然语言描述：

1：判断根节点是否为空，如果为空，返回0 2：如果根节点不为空

3：递归调用求二叉树的结点数的函数，参数改为根节点的左孩子 4：递归调用求二叉树的结点数的函数，参数改为根节点的右孩子 5：返回根节点的左右字数的结点数之和 B.代码详细分析：

template int BiTree::NodeCount(Node *R) {

if (R==NULL) return 0; else {

}

2

3

int m=NodeCount(R->lch); } }

int n=NodeCount(R->rch); return m+n+1;

2.3 其他

对二叉树的操作上，前序遍历与中序遍历采用了非递归算法，后续遍历，层序遍历，求二叉树深度，求二叉树叶子结点数，求二叉树结点数等函数采用了递归算法。为了提高运算性能，可以将它们改为非递归算法来实现，例如，后续遍历的非递归算法如下： template

void BiTreee::Postorder (Node *R) {

Stack*> S; SNode *p; do {

while (R!=NULL) {

p->ptr=R; p->tag=1；S.Push(p); R=R->lch; }

while(!S.IsEmpty() && S.GetTop()->tag==2) {

p=S.Pop(); cout<ptr->data; }

if(!S.IsEmpty()) {

S.GetTop()->tag=2; R=S.GetTop()->ptr->rch; }

} while(!S.IsEmpty()) 3. 程序运行结果 主函数流程图如下：

}

2

3

程序运行截图如下：

4. 总结

1）出现的问题及解决方法

在编写程序时，遇到了一个程序保存后编译正确，但在求深度时运行的结果总是少一个，找了很久发现是返回值返回错误，改正后就好了。

2）心得体会

对二叉树的操作上，前序遍历与中序遍历采用了非递归算法，后续遍历，层序遍历，求二叉树深度，求二叉树叶子结点数，求二叉树结点数等函数采用了递归算法。为了提高运算性能，可以将它们改为非递归算法来实现，对于比较复杂的算法，递归和非递归的运算时间复杂度差别较大，从性能考虑，应当优先采用非递归算法。此外，这几个子函数的名称都是边看着书边写的，还没有完全脱离书本，真正变成自己建的东西。还要加强记忆。

代码

#include

#include

using namespace std;

template

struct binode

{

T data;

binode*lchild;

binode*rchild;

};

template

class bitree

{

public:

void create(binode*&r,T data[],int i);//创建二叉树void release(binode*r);//释放二叉树

bitree(T data[]);

void preorder (binode*r);//前序遍历

void inorder (binode*r);//中序遍历

void postorder (binode*r);//后序遍历

void levelorder (binode*r);//层序遍历

int getdepth (binode *r,int d) ;//深度

int LeafNodeCount(binode *r);//得出叶子结点总数~bitree(){release(root);} //析构函数

bitree():root(NULL){}

binode*& Root();

void findLength(binode* r,T ch);//寻找路径private:

binode*root;//定义根结点

};

template

void bitree ::create(binode*&r,T data[],int i)

{

if(data[i-1]!=0)

{

r=new binode ;

r->data =data[i-1];

create(r->lchild,data,2*i);

create(r->rchild,data,2*i+1);

}

else

r=NULL;

}

template

void bitree ::preorder(binode*r)

{

if(r!=NULL)

{

cout<data;//访问节点

preorder(r->lchild);//遍历左子树

preorder(r->rchild);//遍历右子树

}

}

template

void bitree ::inorder(binode*r)

{

if(r!=NULL)

{

inorder(r->lchild);//遍历左子树

cout<data;//访问节点

inorder(r->rchild);//遍历右子树

}

}

template

void bitree ::postorder(binode*r)

{

if(r!=NULL)

{

postorder(r->lchild);//遍历左子树

postorder(r->rchild);//遍历右子树

cout<data;//访问节点

}

}

template

void bitree ::levelorder(binode* r)

{

binode* queue[100];

int f=0, i=0;//初始化空队列

if(r!=NULL)

queue[++i]=r;

while (f!=i)

{

binode*p=queue[++f];//队头元素出头

cout<data;//出队打印

if(p->lchild!=NULL)

queue[++i]=p->lchild;

if(p->rchild!=NULL)

queue[++i]=p->rchild;

}

}

template

void bitree::release(binode*r)

{

if(r!=NULL)

{

release(r->lchild);

release(r->rchild);

delete r;

}

}

template

int bitree::getdepth(binode *r,int d) {

if (r==NULL) return d;

if ((r->lchild==NULL) && (r->rchild==NULL))

return d+1;

else

{

int m = getdepth(r->lchild,d+1);

int n = getdepth(r->rchild,d+1);

return n>m? n:m;

}

}

template

int bitree::LeafNodeCount(binode *r)

{

if (r==NULL) return 0;

if ((r->lchild==NULL) && (r->rchild==NULL))

return 1;

else

{

int n=LeafNodeCount(r->lchild);

int m=LeafNodeCount(r->rchild);

return m+n+1;

}

}

template

binode*& bitree::Root()

{

return root;

}

template

void bitree::findLength(binode* r,T ch)

{

typedef enum {FALSE,TRUE}boolean;

binode* stack[100];

int tag[100];

int i,top=0;//初始化队列

boolean find=FALSE;

binode* s=r;

do{

while(s!=NULL)

{//扫描左子树

top++;

stack[top]=s;

tag[top]=0;

s=s->lchild;

}

if(top>0)

{

s=stack[top];

if(tag[top]==1)

{

if(s->data==ch)

{

for(i=1;i<=top;i++)

cout<data<<" ";

find = TRUE;

}

else

top--;

s=stack[top];

}

}

if(!find&&top>0)

{

if(tag[top]!=1)

{//扫描右子树

s=s->rchild;

tag[top]=1;

}

else

s=NULL;

}

}while(!find && top!=0);

}

int main()

{

char a[100]={'a','b','d',NULL,'c','e','f',NULL,NULL,NULL,NULL,NULL,NULL,'g'};

bitree bi;

bi.create(bi.Root(),a,1);

cout<<"前序遍历为:"<

bi.preorder (bi.Root());

cout<

bi.inorder (bi.Root());

cout<

bi.postorder (bi.Root());

cout<

bi.levelorder (bi.Root());

cout<

cout<<"二叉树结点总数为"<

cout<

char b;

cin>>b;

bi.findLength(bi.Root(),b); }

数据结构实验报告格式

《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时）

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

数据结构实验报告 欧阳光明（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

(完整版)数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include// 库头文件------ 动态分配内存空间 typedef int elemtype;// 定义数据域的类型 typedef struct linknode// 定义结点类型 { elemtype data;// 定义数据域 struct linknode *next;// 定义结点指针 }nodetype; 2）创建单链表

nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"<> d; if(d==0) break;// 以0 表示输入结束 if(i==1)// 建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));// 表示指针h h->data=d;h->next=NULL;t=h;//h 是头指针 } else// 建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t 始终指向生成的单链表的最后一个节点

数据结构实验报告图实验

图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10;

template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif MGraph.cpp

#include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) {

数据结构实验报告

数据结构实验报告 一．题目要求 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 编码表节点结构：

数据结构图的遍历实验报告

实验项目名称：图的遍历 一、实验目的 应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。 二、实验容 问题描述：建立有向图，并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。 三、实验仪器与设备 计算机，Code::Blocks。 四、实验原理 用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索，并输出遍历的结果。 五、实验程序及结果 #define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include #include #include #include

typedef struct ArCell{ int adj; }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char name[20]; }infotype; typedef struct { infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; int LocateVex(MGraph *G,char* v) { int c = -1,i; for(i=0;ivexnum;i++) if(strcmp(v,G->vexs[i].name)==0) { c=i; break;} return c;} MGraph * CreatUDN(MGraph *G)//初始化图，接受用户输入{ int i,j,k,w; char v1[20],v2[20]; printf("请输入图的顶点数,弧数:"); scanf("%d%d",&G->vexnum,&G->arcnum);

数据结构实验报告[3]

云南大学 数据结构实验报告 第三次实验 学号： 姓名： 一、实验目的 1、复习结构体、指针； 2、掌握链表的创建、遍历等操作； 3、了解函数指针。 二、实验内容 1、（必做题）每个学生的成绩信息包括：学号、语文、数学、英语、总分、加权平均分；采用链表存储若干学生的成绩信息；输入学生的学号、语文、数学、英语成绩；计算学生的总分和加权平均分（语文占30%，数学占50%，英语占20%）；输出学生的成绩信息。 三、算法描述 （采用自然语言描述） 首先创建链表存储n个学生的成绩信息，再通过键盘输入学生的信息，创建指针p所指结点存储学生的成绩信息，从键盘读入学生人数，求出学生的总分和加权平均分，输出结果。 四、详细设计 （画出程序流程图）

五、程序代码 （给出必要注释） #include #include typedef struct score {int number; int chinese; int math; int english; int total; float average; struct score *next; } student; //创建链表存储n个学生的信息，通过键盘输入信息student*input_score(int n) {int i; student*stu,*p; for(i=0,stu=NULL;inumber);

数据结构实验报告模板

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);//重载赋

数据结构实验报告图实验

邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template class MGraph { public: MGraph（DataType a[], int n, int e）; ~MGraph（）{ void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; }

int vertexNum, arcNum; }; #endif MGraph.cpp #include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << "Please enter two vertexs number of edge: " cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } }

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

数据结构实验报告 实验名称：实验四——链表的排序 学生姓名： 班级： 班内序号： 学号： 日期： 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--) {

数据结构实验报告

南京工程学院实验报告 操作的函数程序清单，分别用顺序表和链表结构完成，并在首页上表明团队名称、成员及个人的工作（函数），未来的成绩评定时将包含这一部分的团队成绩及个人的工作成绩。 一、实验目的 1.熟悉上机环境，进一步掌握语言的结构特点。 2.掌握线性表的顺序存储结构的定义及实现。 3.掌握线性表的链式存储结构——单链表的定义及实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、程序主要语句及作用（main函数程序清单） 程序1的主要代码(附简要注释) #include #define MAXSIZE 1024 typedef int elemtype; typedef struct{ elemtype vec[MAXSIZE]; int len; }sequenlist; elemtype geti(sequenlist s, int i); elemtype deli(sequenlist *s,int i); elemtype insi(sequenlist *s,int i,int b); int main(int argc, char *argv[]){ int i,n,x; sequenlist a; printf("输入n(n>3)："); scanf("%d",&n);

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

数据结构实验报告 实验名称：实验三树——哈夫曼编/解码器 学生姓名： 班级： 班内序号： 学号： 日期：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

数据结构实验报告无向图

《数据结构》实验报告 ◎实验题目: 无向图的建立与遍历 ◎实验目的：掌握无向图的邻接链表存储，熟悉无向图的广度与深度优先遍历。 ◎实验内容：对一个无向图以邻接链表存储，分别以深度、广度优先非递归遍历输出。 一、需求分析 1.本演示程序中，输入的形式为无向图的邻接链表形式，首先输入该无向图的顶点数和边数，接着输入顶点信息，再输入每个边的顶点对应序号。 2.该无向图以深度、广度优先遍历输出。 3.本程序可以实现无向图的邻接链表存储，并以深度、广度优先非递归遍历输出。 4.程序执行的命令包括：（1）建立一个无向图的邻接链表存储（2）以深度优先遍历输出（3）以广度优先遍历输出（4）结束 5.测试数据： 顶点数和边数：6,5 顶点信息：a b c d e f 边的顶点对应序号： 0,1 0,2 0,3 2,4 3,4 深度优先遍历输出： a d e c b f 广度优先遍历输出： a d c b e f 二概要设计 为了实现上述操作，应以邻接链表为存储结构。 1.基本操作： void createalgraph(algraph &g) 创建无向图的邻接链表存储 void dfstraverseal(algraph &g,int v)

以深度优先遍历输出 void bfstraverseal(algraph &g,int v) 以广度优先遍历输出 2.本程序包含四个模块： （1）主程序模块 （2）无向图的邻接链表存储模块 （3）深度优先遍历输出模块 （4）广度优先遍历输出模块 3.模块调用图： 三详细设计 1.元素类型，结点类型和指针类型：typedef struct node { int adjvex; struct node *next; }edgenode; typedef struct vnode { char vertex; edgenode *firstedge; }vertxnode; typedef vertxnode Adjlist[maxvernum]; typedef struct { Adjlist adjlist; int n,e; }algraph; edgenode *s; edgenode *stack[maxvernum],*p; 2.每个模块的分析： （1）主程序模块 int main()

数据结构实验报告.

实验目的 （1）学会用先序创建一棵二叉树。 （2）学会采用递归算法对二叉树进行先序、中序、后序遍历。 （3）学会打印输出二叉树的遍历结果。 实验内容 【问题描述】建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。 【基本要求】 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。 【测试数据】 ABCффDEфGффFффф(其中ф表示空格字符) 则输出结果为先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA 【选作内容】 采用非递归算法实现二叉树遍历。 实验步骤 （一）需求分析 1、在这个过程中，接受遍历的二叉树是从键盘接受输入（先序），以二叉链表作为存储结构，建立的二叉树。因此，首先要创建一棵二叉树，而这棵二叉树是先序二叉树。本演示程序中，集合的元素设定为大写字母ABCDEFG，输出的先序，中序，后序遍历分别为ABCDEGF,CBEGDFA,CGBFDBA。二叉树可以表示为：

接受的输入数据在进行递归的先序，中序，后序遍历后，分别将结果打印出来。 2、在程序运行的过程中可以看到，以计算机提示用户执行的方式进行下去，即在计算机终端上提示“输入二叉树的先序序列”后，由用户在键盘上输入ABC##DE#G##F###，之后相应的选择遍历及遍历结果显示出来。 3、程序执行的命令包括：首先是二叉树的先序序列被创建输入，其次是对输入进去的先序序列有次序的进行先序，中序，后序遍历。最后是打印出二叉树的遍历结果。 4、测试数据 （1）在键盘上输入的先序序列ABC##DE#G##F### （2）先序遍历结果ABCDEGF

数据结构实验报告及心得体会

2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨

实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。

三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1; } for(i=0;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1;

数据结构实验报告图实验

图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif #include using namespace std; #include "" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0;

北邮数据结构实验 第四次实验 哈夫曼树

数据结构实验报告 1．实验要求 本实验为可选实验，用于提高同学们使用数据结构解决实际问题的能力。通过选择下面3个题目之一进行实现，掌握如下内容： 栈和递归地深度应用 了解Huffman的思想和算法实现 矩阵和相关算法在BMP图像中的应用 进一步提高编程能力 利用二叉树结构实现哈夫曼编/解码器。 基本要求： 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存储结构： （1）三叉树： class Huffman { private: HNode*HTree;//哈夫曼树结点 HCode*HCodeTable;//哈夫曼编码表 char b[1000];//记录所有输入内容被编码后的结果 char c[127]; char letter[1000];//输入内容的保存 void SelectMin(int &x,int &y,int k);//求最小权重的字符node*count;//计算各个字符出现次数 int n;//输入字符的种类（个数） int l; public: Huffman(); void CreateHTree();//创建哈夫曼树 void CreateCodeTable();//创建哈夫曼编码表 void Encode();//编码 void Decode();//解码 }; 结点结构为如下所示： 三叉树的节点结构： struct HNode//哈夫曼树结点的结构体 { int weight;//结点权值 int parent;//双亲指针 int lchild;//左孩子指针 int rchild;//右孩子指针 char data;//字符 }; 示意图为：

数据结构实验报告

本科实验报告 课程名称：数据结构（C语言版） 实验项目：线性表、树、图、查找、内排序实验地点：明向校区实验楼208 专业班级：学号： 学生姓名： 指导教师：杨永强 2019 年 1 月10日

#include #include #include #define OK 1 typedef struct{//项的表示，多项式的项作为LinkList的数据元素float coef;//系数 int expn;//指数 }term,ElemType; typedef struct LNode{ //单链表节点结构 ElemType data; struct LNode *next; }LNode, *LinkList; typedef LinkList polynomial; int CreatLinkList(polynomial &P,int n){ //创建多项式P = (polynomial)malloc(sizeof(LNode)); polynomial q=P; q->next=NULL; polynomial s; for(int i = 0; i < n; i++){ s = (polynomial)malloc(sizeof(LNode)); scanf("%f%d",&(s->data.coef),&(s->data.expn)); q->next = s; s->next = NULL; q=q->next; } return OK; } 运行结果 2. void PrintfPolyn(polynomial P){ polynomial q; for(q=P->next;q;q=q->next){ if(q->data.coef!=1) printf("%g",q->data.coef);