数据结构设计性实验报告
课程名称_____ ____ 题目名称
学生学院
专业班级
学号
学生姓名
指导教师
2010 年 7 月 6 日
抽象数据类型:树的实现
一.需求分析
树形结构是一类重要的非线性数据结构,其中以树和二叉树最为常用,直观来看,树是以分支关系定义的内部结构。树的结构在客观世界广泛存在,如人类社会的族谱和各种社会组织机构都可以用树来形象表示。树在计算机领域中也得广泛应用,如在编译程序中,可用树来表示源程序的语法结构,又如在数据库系统中,树形结构也是信息的重要组织形式之一。
二.实验目的
对某个具体的抽象数据类型,运用课程所学的知识和方法,设计合理的数据结构,并在此基础上实现该抽象数据类型的全部基本操作。通过本设计性实验,检验所学知识和能力,发现学习中存在的问题。进而达到熟练地运用本课程中的基础知识及技术的目的。
三.实验环境
1、硬件:PC机
2、软件:Microsoft Visual C++ 6.0
四.设计说明
本程序采用树的二叉链表(孩子指针-兄弟指针-双亲指针)存储表示,以下是树的结构定义和基本操作:
ADT Tree{
数据对象D:D是具有相同特性的数据元素的集合。
数据关系R:
若D为空集,则称为空树;
若D仅含有一个数据元素,则R为空集,否则R={H},H是如下二元关系:
(1) 在D中存在唯一的称为根的数据元素root,它在关系H下无前驱;
(2) 若D-{root}≠NULL,则存在D-{root}的一个划分D1,D2,D3, …,Dm(m>0),对于任意j ≠k(1≤j,k≤m)有Dj∩Dk=NULL,且对任意的i(1≤i≤m),唯一存在数据元素xi∈Di有
(3) 对应于D-{root}的划分,H-{
基本操作P:
InitTree(&T);
操作结果:构造空树T。
DestroyTree(&T);
初始条件:树T存在。
操作结果:销毁树T。
CreateTree(&T,definition);
初始条件:definition给出树T的定义。
操作结果:按definition构造树T。
ClearTree(&T);
初始条件:树T存在。
操作结果:将树T清为空树。
TreeEmpty(T);
初始条件:树T存在。
操作结果:若T为空树,则返回TRUE,否则返回FALSE。
TreeDepth(T);
初始条件:树T存在。
操作结果:返回T的深度。
Root(T);
初始条件:树T存在。
操作结果:返回T的根。
Value(T,cur_e);
初始条件:树T存在,cur_e是T中某个结点。
操作结果:返回cur_e的值。
Assign(T,cur_e,value);
初始条件:树T存在,cur_e是T中某个结点。
操作结果:结点cur_e赋值为value。
Parent(T,cur_e);
初始条件:树T存在,cur_e是T中某个结点。
操作结果:若cur_e是T的非根结点,则返回它的双亲,否则函数值为“空”。
LeftChild(T,cur_e);
初始条件:树T存在,cur_e是T中某个结点。
操作结果:若cur_e是T的非叶子结点,则返回它的最左孩子,否则返回“空”。RightSibling(T,cur_e);
初始条件:树T存在,cur_e是T中某个结点。
操作结果:若cur_e有右兄弟,则返回它的右兄弟,否则返回“空”。
InsertChild(&T,&p,I,c);
初始条件:树T存在,p指向T中某个结点,1≤i≤p指结点的度+1,非空树c与T不相交。
操作结果:插入c为T中p指结点的第i棵子树。
DeleteChild(&T,&p,i);
初始条件:树T存在,p指向T中某个结点,1≤i≤p指结点的度。
操作结果:删除T中p所指结点的第i棵子树。
TraverseTree(T,visit());
初始条件:树T存在,visit是对结点操作的应用函数。
操作结果:按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit()失败,则操作失败。
CSTree Search(CSTree T,TElemType cur_e);
初始条件:树T存在,cur_e可能是树T中某一个结点的值。
操作结果:在树T中查找值为cur_e的结点,找到返回指向这个结点的指针,否则返回空指针。
这个函数的作用是为了几个基本操作而服务的。
void LevelOrderTraverseTree(CSTree T,void (* visit)(TElemType));
初始条件:树T存在,visit是对结点操作的应用函数。
操作结果:按层次次序对T的每一个结点调用函数visit()一次且至多一次。
void PreOrderTraverseTree(CSTree T,void(*visit)(TElemType));
初始条件:树T存在,visit是对结点操作的应用函数。
操作函数:按先序次序(先根遍历)对T的每一个结点调用函数visit()一次且至多一次。函数的功能实现是递归实现的。
void PostOrderTraverseTree(CSTree T,void (*visit)(TElemType));
初始条件:树T存在,visit是对结点操作的应用函数。
操作结果:按后根遍历对T的每一个结点调用函数visit()一次且至多一次。
函数的功能实现是递归实现的。
void visit_print(CSTree p);
初始条件:树T存在,visit_print是对结点操作的应用函数。
操作函数:对T的每一个结点调用函数visit_print()一次且至多一次。
与visit函数不一样的是,visit函数只是输出一个结点的值,而visit_print还输出其结点,第一个孩子,其右兄弟和双亲的值
void Print(CSTree T,void (*visit)(CSTree));
附加函数:用于显示树的所有内容。
初始条件:树T存在;
操作结果:将树T的所有结点显示出来。
}ADT Tree
五.数据处理
转化后树的二叉链表存储:
以下为数据样本测试:
●操作:判断树书否为空?
结果:不为空
●返回树T的深度?
结果:4
●返回树T的根结点?
结果:A
●返回树F结点的值?
结果:F
●将树根节点重新赋值为W ?
结果:A<—>W
●求出结点A的双亲?
结果:W
●求出结点A的第一个孩子结点?
结果:D
●求出G的第一个兄弟结点?
结果:H
●插入子树C至A
结果:
●删除树结点为R的第三颗子树?
结果:
●多种遍历方式遍历树
前序遍历树:W-A-D-X-Y-Z-E-B
层次序遍历树:W-A-B-D-X-E-Y-Z
后序遍历树:D-Y-Z-X-E-A-B-W
以下为运行EXE程序测试过程:
X Y
Z B
A
D
E
W
选择1:
选择14:
选择15:
选择16:
选择4:
选择5:
选择6:
选择7:
选择8:
选择9:
选择10:
选择11:
选择12:
选择13:
选择14:
选择15:
选择16:
选择2:
六.程序清单解读
/**************************抽象数据类型树-源码*********************************/ #include
#include
using namespace std;
const int TRUE=1;
const int FALSE=0;
const int OK=1;
const int ERROR=0;
const int OVERFLOW=1;
const int MAX=30;
const char NIL=' ';
/*****************树的二叉链表孩子-兄弟-双亲存储表示***************************/
typedef struct CSnode
{
char data;
CSnode *firstchild,*nextsibling,*parent;
/*最左孩子指针、下一个兄弟指针、双亲指针*/
}CSNode,*CSTree;
/********************树的辅助队列结构定义和操作******************************/ typedef struct QNode
{
CSTree data;
QNode *next;
}QNode,*QueuePtr; /*队列的单链式存储结构*/
typedef struct LinkQueue
{
QueuePtr front,rear; /*队头、队尾指针*/
}LinkQueue;
/*******************************队列定义**************************************/ /*构造一个空队列*/
int InitQueue (LinkQueue &Q)
{
if(!(Q.front=Q.rear=new QNode))
exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}
/*销毁队列Q*/
int DestroyQueue(LinkQueue &Q)
{
while(Q.front){
Q.rear=Q.front->next;
delete Q.front;
Q.front=Q.rear;
}
return OK;
}
/*将Q清为空队列*/
int ClearQueue (LinkQueue &Q)
{
QueuePtr p,q;
Q.rear=Q.front;
p=Q.front->next;
Q.front->next=NULL;
while(p){
q=p;
p=p->next;
delete q;
}
return OK;
}
/*若队列Q为空队列则返回TRUE,否则返回FALSE*/
int QueueEmpty( LinkQueue Q)
{
if(Q.front==Q.rear) return TRUE;
else return FALSE;
}
/* 插入元素e为Q的新的队尾元素*/
int EnQueue(LinkQueue &Q, CSTree e)
{
QueuePtr p;
if(!(p=new QNode)) exit(OVERFLOW);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}
/*若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR*/
int DeQueue(LinkQueue &Q,CSTree &e)
{
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;
delete p;
return OK;
}
/*****************************************************************************/
/***********************树的二叉链表孩子-兄弟-双亲存储定义*********************/ /*操作结果: 构造空树T*/
int InitTree(CSTree &T)
{
T=NULL;
return OK;
}
/*初始条件: 树T存在*/
/*操作结果: 销毁树T*/
void DestroyTree(CSTree &T)
{
if(T)
{
if(T->firstchild) DestroyTree(T->firstchild);
if(T->nextsibling) DestroyTree(T->nextsibling);
delete T;
}
}
/*初始条件:树T存在*/
/*操作结果:按层次次序创建树T*/
int CreateTree(CSTree &T)
{
char c[MAX];
CSTree p,p1,temp;
LinkQueue q;
InitQueue(q);
cout<<"请输入根节点,空格代表跟为空:";
fflush(stdin);
c[0]=getche();
if(c[0]!=NIL) /*非空树*/ {
T=new CSNode;
T->data=c[0];
T->nextsibling=NULL;
T->parent=NULL;
EnQueue(q,T);
while(!QueueEmpty(q))
{
DeQueue(q,p);
cout<<"\n请输入"<
gets(c);
if(strlen(c)) /*树有孩子*/
{
p1=p->firstchild=new CSNode; /*建立长子节点*/
temp=p; /*保存该根节点*/
p1->parent=temp;/*建立双亲域*/
p1->data=c[0];
EnQueue(q,p1); /*第一个孩子节点入队列*/
for(int i=1;i { p1->nextsibling=new CSNode; /*建立下一个兄弟节点*/ p1->nextsibling->data=c[i]; /* 下一个兄弟节点赋值*/ p1->nextsibling->parent=temp; /*建立下一个兄弟节点双亲域*/ EnQueue(q,p1->nextsibling); /*各兄弟入队*/ p1=p1->nextsibling; } p1->nextsibling=NULL; /*最后的兄弟结点的nextsibling指针置为空*/ } else /*树无孩子只有根节点*/ { p->firstchild=NULL; } } } else T=NULL; /*空树*/ return OK; } /*初始条件:树T存在*/ /*操作结果:将树T清为空树*/ void ClearTree(CSTree &T) { if(T) { if(T->firstchild) DestroyTree(T->firstchild); if(T->nextsibling) DestroyTree(T->nextsibling); delete T; T=NULL; } } /*初始条件:树T存在*/ /*操作结果:若T为空树,则返回TRUE,否则返回FALSE*/ int TreeEmpty(CSTree T) { if(T==NULL) return TRUE; else return FALSE; } /*初始条件:树T存在*/ /*操作条件:返回T的深度*/ int TreeDepth(CSTree T) { CSTree p; int depth,max=0; if(!T)return 0; if(!T->firstchild)return 1; for(p=T->firstchild;p;p=p->nextsibling) { depth=TreeDepth(p); /*递归求深度*/ if(depth>max) max=depth; } return max+1; /*返回深度要加上根节点*/ } /*初始条件: 树T存在*/ /*操作结果: 返回T的根*/ char Root(CSTree T) { if(T) return T->data; else { cout<<"\n树空,无根节点!"; return NIL; } } /*初始条件:树T存在,cur_e可能是树T中某一个结点的值。*/ /*操作结果:在树T中查找值为cur_e的结点,找到返回指向这个结点的指针,否则返回空指针。*/ CSTree Search(CSTree T,char cur_e) { LinkQueue q; CSTree a; if(T) { InitQueue(q); /*队列初始化*/ EnQueue(q,T); while(!QueueEmpty(q)){ DeQueue(q,a); if(a->data==cur_e) return a; if(a->firstchild) EnQueue(q,a->firstchild); if(a->nextsibling) EnQueue(q,a->nextsibling); } } return NULL; } /*初始条件:树T存在,cur_e可能是树T中某个结点*/ /*操作结果:返回cur_e的值*/ char Value(CSTree T, char cur_e) { CSTree p; if(T) { p=Search(T,cur_e); if(p) return p->data; else { cout<<"\n在树中找不到值为"< return NIL; } } else { cout<<"\n树空,无值为"< return NIL; } } /*初始条件:树T存在,cur_e可能是T中的某个结点*/ /*操作结果:若cur_e是T的非根结点,则返回它的双亲,否则函数值为空*/ char Parent(CSTree T,char cur_e) { CSTree p; if(T) { p=Search(T,cur_e); if(!p) { cout<<"\n在树中找不到值为"< return NIL; } else if(!p->parent) { cout<<"\n值为"< return NIL; } else return p->parent->data; } else { cout<<"\n树空,无节点"; return NIL; } } /*初始条件: 树T存在,cur_e是树T中结点的值*/ /*操作结果: 改cur_e为value*/ int Assign(CSTree &T,char cur_e,char value) { CSTree p; if(T) { p=Search(T,cur_e); if(p) { cout<<"\n找到节点"< p->data=value; return OK; } else { cout<<"\n找不到节点"< return ERROR; } } else { cout<<"\n树为空,操作无法完成"; return ERROR; } } /*初始条件:树T存在,cur_e可能是T中某个结点*/ /*操作结果:若cur_e是T的非叶子结点,则返回它的最左孩子,否则返回函数值为空。*/ char LeftChild(CSTree T,char cur_e) { CSTree p; if(T) { p=Search(T,cur_e); if(!p) { cout<<"\n找不到值为"< return NIL; } else { if(!p->firstchild) { cout<<"\n无左孩子"; return NIL; } else { return p->firstchild->data; } } } else { cout<<"\n树空,不存在值为"< return NIL; } } /*初始条件:树T存在,cur_e可能是T中的某个结点*/ /*操作结果:若cur_e有右兄弟,则返回它的右兄弟,否则返回函数值为空*/ char RightSibling(CSTree T,char cur_e) { CSTree p; if(T) { p=Search(T,cur_e); if(!p) { cout<<"\n找不到值为"< return NIL; } else { if(!p->nextsibling) { cout<<"\n无兄弟"; return NIL; } else { return p->nextsibling->data; } } } else { cout<<"\n树空,不存在值为"< return NIL; } } /*初始条件:树T存在,p指向T中某个结点,1<=i<=p所指结点的度+1,非空树c与T不相交*/ /*操作结果:插入c为T中p指结点的第i棵子树*/ int InsertChild(CSTree &T,CSTree p,int i,CSTree c) { CSTree temp=p; /*保存根节点*/ int j; if(!c) { cout<<"\n子树为空,不执行操作"; return OK; } if(i<1) { cout<<"\n插入地址选择出错,不执行操作"; return ERROR; } if(!p) { cout<<"\n在树中找不到指向节点,不执行操作"; return ERROR; } if(!p->firstchild&&i>1) { cout<<"\n输入数据矛盾,请检查"; return ERROR; } if(T) /*T不空*/ { if(i==1) /*插到第一个孩子上*/ { c->nextsibling=p->firstchild; p->firstchild=c; c->parent=p; } else { p=p->firstchild; j=2; while(p&&j { p=p->nextsibling; j++; } if(j==i) /*找到插入位置*/ { c->nextsibling=p->nextsibling; p->nextsibling=c; c->parent=temp; /*设置双亲节点*/ } else /*找不到插入位置*/ { cout<<"\n插入节点错误"; return ERROR; } } return OK; } else /*树空*/ { cout<<"\n树空,操作不执行"; return ERROR; } } /*初始条件:树T存在,p指向T中的某个结点,1<=i<=p所指结点的度*/ /*操作结果:删除T中p所指结点的第i棵子树*/ int DeleteChild(CSTree &T,CSTree p,int i) { CSTree q; int j; if(!T) { cout<<"\n树为空,不执行操作"; return OK; } if(i<1) { cout<<"\n插入地址选择出错,不执行操作"; return ERROR; } if(!p) { cout<<"\n在树中找不到指向节点,不执行操作"; return ERROR; } 2013-2014-1学期 《数据结构》实验报告 专业:信息管理与信息系统 班级: 姓名: 学号: 完成日期:2013.12.01 实验名称:二叉树的创建与遍历 一、实验目的 建立一棵二叉树,并对其进行遍历(先序、中序、后序),打印输出遍历结果。 二、实验要求 1、建立一棵用二叉链表方式存储的二叉树,并对其进行遍历(先序、中序和后序),打印输出遍历结果。 2、从键盘接受扩展先序序列,以二叉链表作为存储结构,建立二叉树,并将遍历结果打印输出。 三、实验步骤(包括所选择的二叉树的创建算法和常用三种遍 历算法的说明、完整的程序代码及必要的注释。) 1、用二叉链表创建二叉树: ①输入根结点值;②若左子树不空,则输入左子树,否则输入一个结束符‘#’;③若右子树不空,则输入右子树,否则输入一个结束符‘#’。 2、遍历该二叉树 (1) 先序遍历(DLR) 若二叉树为空,则结束返回。否则:①访问根结点;②先序遍历左子树;③先序遍历右子树。 (2) 中序遍历(LDR) 若二叉树为空,则结束返回。否则:①中序遍历左子树;②访问根结点;③中序遍历右子树。 (3) 后序遍历(LRD) 若二叉树为空,则结束返回。否则:①后序遍历 左子树;②后序遍历右子树;③访问根结点。 3、程序代码: #include 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程,是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法,介绍了常用的多种查找和排序技术,并做了性能分析和比较,内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因,使得掌握这门课程具有较大的难度: (1)内容丰富,学习量大,给学习带来困难; (2)贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点; (3)所用到的技术多,而在此之前的各门课程中所介绍的专业性知识又不多,因而加大了学习难度; (4)隐含在各部分的技术和方法丰富,也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性,设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练,突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时,觉得无从下手,做起来特别费劲。实验中的内容和教科书的内容是密切相关的,解决题目要求所需的各种技术大多可从教科书中找到,只不过其出现的形式呈多样化,因此需要仔细体会,在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程,理解和掌握算法设计所需的技术,为整个专业学习打好基础,要求运用所学知识,上机解决一些典型问题,通过分析、设计、编码、调试等各环节的训练,使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法,如算法设计的构思方法,动态链表,算法的编码,递归技术,与特定问题相关的技术等,要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上,掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时,要求完成以下六个题目: 实习一约瑟夫环问题(2学时) 计算机科学与技术学院数据结构实验报告 班级2014级计算机1班学号20144138021 姓名张建华成绩 实验项目简单哈夫曼编/译码的设计与实现实验日期2016.1.5 一、实验目的 本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构,进一步提高使用理论知识指导解决实际问题的能力。 二、实验问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码,此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能: 1、接收原始数据。 从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmtree.dat中。 2、编码。 利用已建好的哈夫曼树(如不在内存,则从文件hfmtree.dat中读入),对文件中的正文进行编码,然后将结果存入文件codefile.dat中。 3、译码。 利用已建好的哈夫曼树将文件codefile.dat中的代码进行译码,结果存入文件textfile.dat中。 4、打印编码规则。 即字符与编码的一一对应关系。 5、打印哈夫曼树, 将已在内存中的哈夫曼树以直观的方式显示在终端上。 三、实验步骤 1、实验问题分析 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时,设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息,根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有2n-1个结点,所以数组HuffNode的大小设置为2n-1,描述结点的数据类型为: Typedef strcut { Int weight;/*结点权值*/ Int parent; Int lchild; Int rchild; }HNodeType; 2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。 求哈夫曼编码,实质上就是在已建立的哈夫曼树中,从叶子结点开始,沿结点的双亲链域回退到根结点,没回退一步,就走过了哈夫曼树的一个分支,从而得到一位哈夫曼码值,由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列,因此先得到的分支代码为所求编码的低位码,后得到的分支代码位所求编码的高位码,所以设计如下数据类型: 数据结构实验报告 一.题目要求 1)编程实现二叉排序树,包括生成、插入,删除; 2)对二叉排序树进行先根、中根、和后根非递归遍历; 3)每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4)分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率,并说明在什么情况下二叉排序树效率高,为什么? 二.解决方案 对于前三个题目要求,我们用一个程序实现代码如下 #include 实验二二叉树的遍历及霍夫曼编码 班级:计科1101班 学号:0909101605 姓名:杜茂鹏 2013年5月22日 一、实验目的 掌握二叉树的建立及遍历操作,霍夫曼编码基本操作及存储结构表示 二、实验内容 1. 系统要求包含以下功能 1)初始化:从终端读入字符集大小n,以及n个字符和n个权值(或者读入字符集和频度数据文件),建立哈夫曼树,并将哈夫曼树存入到文件HfmTree 中。 2)编码:利用已建好的哈夫曼树(如果不在内存中,则从文件中读入),从文件ToBeTran中读入原文,对原文进行编码,将编码后的结果存入文件CodeFile 中。 3)译码:利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。 4)打印:打印输出哈夫曼树,显示ToBeTran, TextFile和CodeFile文件的内容。 三、实验要求 1.在上机前写出全部源程序; 2.能在机器上正确运行程序; 3.用户界面友好。 四、概要设计 1)首先动态分配数组存储霍夫曼树及存储霍夫曼编码表,然后从终端或文件读入霍夫曼树的字符变量及其频度,初始化建立霍夫曼树并将其写入文件HfmTree.txt中。 2)从指定的文件succe.txt中读入原文,利用已经编好的霍夫曼树对其编码,将编码结果写入文件Coding.txt保存。 3)利用已建好的哈夫曼树将文件Coding.txt中的代码进行译码,结果存入文件decoding.txt中。 五、测试数据: 2.原文内容“THIS IS MY PROGRAM” 六、详细设计 实验内容(原理、操作步骤、程序代码) //建立霍夫曼树,对原文进行编码、译码 #include 数据结构实验报告全集 实验一线性表基本操作和简单程序 1.实验目的 (1)掌握使用Visual C++ 6.0上机调试程序的基本方法; (2)掌握线性表的基本操作:初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2.实验要求 (1)认真阅读和掌握和本实验相关的教材内容。 (2)认真阅读和掌握本章相关内容的程序。 (3)上机运行程序。 (4)保存和打印出程序的运行结果,并结合程序进行分析。 (5)按照你对线性表的操作需要,重新改写主程序并运行,打印出文件清单和运行结果 实验代码: 1)头文件模块 #include iostream.h>//头文件 #include nodetype *create()//建立单链表,由用户输入各结点data域之值,//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"< 一、需求分析 1、本演示程序实现Haffman编/译码器的作用,目的是为信息收发站提供一个编/译系统, 从而使信息收发站利用Haffman编码进行通讯,力求达到提高信道利用率,缩短时间,降低成本等目标。系统要实现的两个基本功能就是:①对需要传送的数据预先编码; ②对从接收端接收的数据进行译码; 2、本演示程序需要在终端上读入n个字符(字符型)及其权值(整形),用于建立Huffman 树,存储在文件hfmanTree.txt中;如果用户觉得不够清晰还可以打印以凹入表形式显示的Huffman树; 3、本演示程序根据建好的Huffman树,对文件的文本进行编码,结果存入文件CodeFile 中;然后利用建好的Huffman树将文件CodeFile中的代码进行译码,结果存入文件TextFile中;最后在屏幕上显示代码(每行50个),同时显示对CodeFile中代码翻译后的结果; 4、本演示程序将综合使用C++和C语言; 5、测试数据: (1)教材例6-2中数据:8个字符,概率分别是0.05,0.29,0.07,0.08,0.14,0.23,0.03, 0.11,可将其的权值看为5,29,7,8,14,23,3,11 (2)用下表给出的字符集和频度的实际统计数据建立Haffman树,并实现以下报文的编码和 一、概要设计 1、设定哈夫曼树的抽象数据类型定义 ADT Huffmantree{ 数据对象:D={a i| a i∈Charset,i=1,2,3,……n,n≥0} 数据关系:R1={< a i-1, a i >| a i-1, a i∈D, i=2,3,……n} 基本操作: Initialization(&HT,&HC,w,n,ch) 操作结果:根据n个字符及其它们的权值w[i],建立Huffman树HT,用字符数组ch[i]作为中间存储变量,最后字符编码存到HC中; Encodeing(n) 操作结果:根据建好的Huffman树,对文件进行编码,编码结果存入到文件CodeFile 中 Decodeing(HT,n) 操作结果:根据已经编译好的包含n个字符的Huffman树HT,将文件的代码进行翻译,结果存入文件TextFile中 } ADT Huffmantree 实验报告 实验原理: 霍夫曼编码(Huffman Coding)是一种编码方式,是一种用于无损数据压缩的熵编码(权编码)算法。1952年,David A. Huffman在麻省理工攻读博士时所发明的。 在计算机数据处理中,霍夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之出现机率低的则使用较长的编码,这便使编码之后的字符串的平均长度、期望值降低,从而达到无损压缩数据的目的。 例如,在英文中,e的出现机率最高,而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时,e极有可能用一个比特来表示,而z则可能花去25个比特(不是26)。用普通的表示方法时,每个英文字母均占用一个字节(byte),即8个比特。二者相比,e使用了一般编码的1/8的长度,z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算,就可以大幅度提高无损压缩的比例。 霍夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和,记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln),N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,...n)。 可以证明霍夫曼树的WPL是最小的。 实验目的: 本实验通过编程实现赫夫曼编码算法,使学生掌握赫夫曼树的构造方法,理解树这种数据结构的应用价值,并能熟练运用C语言的指针实现构建赫夫曼二叉树,培养理论联系实际和自主学习的能力,加强对数据结构的原理理解,提高编程水平。 实验内容: (1)实现输入的英文字符串输入,并设计算法分别统计不同字符在该字符串中出现的次数,字符要区分大小写; 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 [内容要求] 1、存储结构:顺序表、单链表或其他存储结构,需要画示意图,可参考书上P59 页图2-9 2.2 关键算法分析 结点类: template 哈夫曼树实验报告 Company number:【0089WT-8898YT-W8CCB-BUUT-202108】 计算机科学与技术学院数据结构实验报告 班级 2014级计算机1班学号姓名张建华成绩 实验项目简单哈夫曼编/译码的设计与实现实验日期一、实验目的 本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构,进一步提高使用理论知识指导解决实际问题的能力。 二、实验问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码,此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能: 1、接收原始数据。 从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件中。 2、编码。 利用已建好的哈夫曼树(如不在内存,则从文件中读入),对文件中的正文进行编码,然后将结果存入文件中。 3、译码。 利用已建好的哈夫曼树将文件中的代码进行译码,结果存入文件中。 4、打印编码规则。 即字符与编码的一一对应关系。 5、打印哈夫曼树, 将已在内存中的哈夫曼树以直观的方式显示在终端上。 三、实验步骤 1、实验问题分析 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时,设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息,根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有2n-1个结点,所以数组HuffNode的大小设置为2n-1,描述结点的数据类型为: Typedef strcut { Int weight;/*结点权值*/ Int parent; Int lchild; Int rchild; }HNodeType; 2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。 求哈夫曼编码,实质上就是在已建立的哈夫曼树中,从叶子结点开始,沿结点的双亲链域回退到根结点,没回退一步,就走过了哈夫曼树的一个分支,从而得到一位哈夫曼码值,由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路 《用哈夫曼编码实现文件压缩》 实验报告 课程名称数据结构 实验学期2015至2016学年第一学期 学生所在系部计算机学院 年级2014专业班级物联B142班 学生姓名杨文铎学号201407054201 任课教师白磊 实验成绩 用哈夫曼编码实现文件压缩 1、了解文件的概念。 2、掌握线性表的插入、删除的算法。 3、掌握Huffman树的概念及构造方法。 4、掌握二叉树的存储结构及遍历算法。 5、利用Haffman树及Haffman编码,掌握实现文件压缩的一般原理。 微型计算机、Windows系列操作系统、Visual C++6.0软件 根据ascii码文件中各ascii字符出现的频率情况创建Haffman树,再将各字符对应的哈夫曼编码写入文件中,实现文件压缩。 本次实验采用将字符用长度尽可能短的二进制数位表示的方法,即对于文件中出现的字符,无须全部都用S为的ascii码进行存储,根据他们在文件中出现的频率不同,我们利用Haffman算法使每个字符能以最短的二进制数字符进行存储,已达到节省存储空间,压缩文件的目的,解决了压缩需要采用的算法,程序的思路已然清晰: 1、统计需压缩文件中的每个字符出现的频率 2、将每个字符的出现频率作为叶子节点构建Haffman树,然后将树中结点引向 其左孩子的分支标“0”,引向其右孩子的分支标“1”;每个字符的编码 即为从根到每个叶子的路径上得到的0、1序列,这样便完成了Haffman 编码,将每个字符用最短的二进制字符表示。 3、打开需压缩文件,再将需压缩文件中的每个ascii码对应的haffman编码按bit 单位输出。 4、文件压缩结束。 (1)构造haffman树的方法一haffman算法 构造haffman树步骤: I.根据给定的n个权值{w1,w2,w3…….wn},构造n棵只有根结点的二叉 树,令起权值为wj。 II.在森林中选取两棵根结点权值最小的树作左右子树,构造一棵新的二叉树,置新二叉树根结点权值为其左右子树根结点权值之和。 III.在森林中删除这两棵树,同时将得到的二叉树加入森林中。 IV.重复上述两步,知道只含一棵树为止,这棵树即哈夫曼树。 对于haffman的创建算法,有以下几点说明: a)这里的Haffman树采用的是基于数组的带左右儿子结点及父结点下标作为 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;i 数据结构实验报告 实验名称:实验三哈夫曼树 学生姓名: 班级: 班内序号: 学号: 日期: 程序分析: 存储结构:二叉树 程序流程: template 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. 根据哈夫曼树创建编码表 电子科技大学 实验报告 课程名称:数据结构与算法 学生姓名:陈*浩 学号:************* 点名序号: *** 指导教师:钱** 实验地点:基础实验大楼 实验时间: 2014-2015-2学期 信息与软件工程学院 实验报告(二) 学生姓名:陈**浩学号:*************指导教师:钱** 实验地点:科研教学楼A508实验时间:一、实验室名称:软件实验室 二、实验项目名称:数据结构与算法—树 三、实验学时:4 四、实验原理: 霍夫曼编码(Huffman Coding)是一种编码方式,是一种用于无损数据压缩的熵编码(权编码)算法。1952年,David A. Huffman在麻省理工攻读博士时所发明的。 在计算机数据处理中,霍夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之出现机率低的则使用较长的编码,这便使编码之后的字符串的平均长度、期望值降低,从而达到无损压缩数据的目的。 例如,在英文中,e的出现机率最高,而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时,e极有可能用一个比特来表示,而z则可能花去25个比特(不是26)。用普通的表示方法时,每个英文字母均占用一个字节(byte),即8个比特。二者相比,e使用了一般编码的1/8的长度,z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算,就可以大幅度提高无损压缩的比例。 霍夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和,记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln),N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,...n)。 可以证明霍夫曼树的WPL是最小的。 图实验 一,邻接矩阵的实现 1.实验目的 (1)掌握图的逻辑结构 (2)掌握图的邻接矩阵的存储结构 (3)验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 (1)建立无向图的邻接矩阵存储 (2)进行深度优先遍历 (3)进行广度优先遍历 3.设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template 哈夫曼树实验报告 需求分析: 从终端读入一串字符,利用建立好的哈夫曼树对其进行编码,储存到文件当中去,然后从文件读入哈夫曼编码,针对每个字母对其进行译码,翻译为原来的信息。 二、概要设计 程序分为以下几个模块: 1、从终端读入字符集大小,n个字符和n个权值,建立哈夫曼树,写入文件hfmTree中去。 2、对hfmTree进行编码,建立hfm编码表。 3、从文件ToTran读入信息,根据hfm编码表对其进行hfm编码,将编码后的信息写入文件Codefile 中去 4、对Codefile文件反向译码,结果储存在Textfile中去。 5、将建立的hfmTree打印在终端上,并储存于相应的Treeprint文件中去。 抽象的数据定义如下: 哈夫曼树结构 typedef struct //定义哈夫曼树的结构 { int weight; //权值 int parent; //双亲 int lchild; //左孩子 int rchild; //右孩子 }htnode,huffmantree[M+1]; 建立哈夫曼树 void crthuffmantree(huffmantree ht,int w[],int n) //初始化哈夫曼树 { int i,s1,s2,m; for(i=1;i<=n;i++) { ht[i].weight=w[i]; ht[i].parent=0; ht[i].lchild=0; ht[i].rchild=0; } m=2*n-1; for(i=n+1;i<=m;i++) { ht[i].weight=0; ht[i].parent=0; ht[i].lchild=0; ht[i].rchild=0; } for(i=n+1;i<=m;i++) { select(ht,i-1,&s1,&s2); ht[i].weight=ht[s1].weight+ht[s2].weight; ht[s1].parent=i; 数据结构实验报告实验题目:Huffman编码与解码 姓名: 学号: 院系: 实验名称: Huffman编码与解码实验 问题描述: 本实验需要以菜单形式完成以下功能: 1.输入电文串 2.统计电文串中各个字符及其出现的次数 3.构造哈弗曼树 4.进行哈弗曼编码 5.将电文翻译成比特流并打印出来 6.将比特流还原成电文 数据结构的描述: 逻辑结构: 本实验可用二叉树实现,其逻辑结构为一对二的形式,即一个结点对应两个结点。在实验过程中我们也应用到了栈的概念。 存储结构: 使用结构体来对数据进行存储: typedef struct { int weight; int parent,lc,rc; }HTNode,*HuffmanTree; typedef struct LNode { char *elem; int stacksize; int top; }SqStack; 在main函数里面定义一个哈弗曼树并实现上述各种功能。 程序结构的描述: 本次实验一共构造了10个函数: 1.void HuffTree(HuffmanTree &HT,int n[],int mun); 此函数根据给定的mun个权值构建哈弗曼树,n[]用于存放num个权值。 2.void Select(HuffmanTree &HT,int n,int i,int &s1,int &s2); 此函数用于在HT[1,i-1]中选择parent为0且weight为最小的两个结点,其下标分别为s1,s2. 3.void HuffmanCoding(HuffmanTree HT,char **&HC,int n); 此函数从哈弗曼树HT上求得n 个叶子结点的哈弗曼编码并存入数组HC中。 4.void Coding(HuffmanTree HT,char **HC,int root,SqStack &S); 此函数用于哈弗曼编码,先序遍历哈弗曼树HT,求得每个叶子结点的编码字符串,存入数组HC,S为一个顺序栈,用来记录遍历路径,root是哈弗曼数组HT中根结点的位置下标。 5.void InitStack(SqStack &S); 此函数用于初始化一个栈。 6.void Pop(SqStack &S,char e); 此函数为出栈操作。 7.void Push(SqStack &S,char e); 此函数为进栈操作。 8.int StackLength(SqStack S); 此函数用于求栈长,返回一个int型的值。 9.int Find(char a,char s[],int num); 此函数用于查找字符a在电文串中的位置。 10.int Recover(HuffmanTree HT,char **HC,char string[],char a[],char b[],int n); 此函数用于将比特流还原成电文。 调试分析: 输入任意一个字符串,如输入welcometoustc:运行结果如下: . . 河南工程学院 理学院学院 实验报告 (数据结构与算法) 学期: 课程: 专业: 班级: 学号: 姓名: 指导教师: . . 目录 实验一线性表1(顺序表及单链表的合并) (1) 实验二线性表2(循环链表实现约瑟夫环) (1) 实验三栈和队列的应用(表达式求值和杨辉三角) (1) 实验四赫夫曼编码 实验五最小生成树 (1) 实验六排序算法 . . 实验一线性表1 一、实验学时:2学时 二、实验目的 1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系。在计算机中 表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。 2.熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储 结构上的实现。 三、实验内容 1. 编写程序,实现顺序表的合并。 2. 编写程序,实现单链表的合并。 四、主要仪器设备及耗材 硬件:计算机一台 软件:VC++ 6.0,MSDN2003或者以上版本 五、算法设计 1. 顺序表合并的基本思想 程序流程图: 2. 单链表合并的基本思想 程序流程图 六、程序清单 . 七、实现结果 . . 八、实验体会或对改进实验的建议. . . 实验二线性表2 一、实验学时:2学时 二、实验目的 1.了解双向循环链表的逻辑结构特性,理解与单链表的区别与联系。 2.熟练掌握双向循环链表的存储结构以及基本操作。 三、实验内容 编写程序,采用循环链表实现约瑟夫环。 设有编号为1,2,……,n的n(n>0)个人围成一个圈,从第1个人开始报数,报到m时停止报数,报m的人出圈,再从他的下一个人起重新报数,报到m时停止报数,报m的出圈,……,如此下去,直到所有人全部出圈为止。当任意给定n和m后,设计算法求n个人出圈的次序。 四、主要仪器设备及耗材 硬件:计算机一台 软件:VC++ 6.0,MSDN2003或者以上版本 五、算法设计 约瑟夫环实现的基本思想 程序流程图: 六、程序清单 数据结构(C语言版) 实验报告 专业班级学号姓名 实验1 实验题目:单链表的插入和删除 实验目的: 了解和掌握线性表的逻辑结构和链式存储结构,掌握单链表的基本算法及相关的时间性能分析。 实验要求: 建立一个数据域定义为字符串的单链表,在链表中不允许有重复的字符串;根据输入的字符串,先找到相应的结点,后删除之。 实验主要步骤: 1、分析、理解给出的示例程序。 2、调试程序,并设计输入数据(如:bat,cat,eat,fat,hat,jat,lat,mat,#),测试程序 的如下功能:不允许重复字符串的插入;根据输入的字符串,找到相应的结点并删除。 3、修改程序: (1)增加插入结点的功能。 (2)将建立链表的方法改为头插入法。 程序代码: #include"stdio.h" #include"string.h" #include"stdlib.h" #include"ctype.h" typedef struct node //定义结点 { char data[10]; //结点的数据域为字符串 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自定义LinkList单链表类型 LinkList CreatListR1(); //函数,用尾插入法建立带头结点的单链表 LinkList CreatList(void); //函数,用头插入法建立带头结点的单链表 ListNode *LocateNode(); //函数,按值查找结点 void DeleteList(); //函数,删除指定值的结点 void printlist(); //函数,打印链表中的所有值 void DeleteAll(); //函数,删除所有结点,释放内存数据结构实验报告
数据结构实验报告格式
哈夫曼树 实验报告
数据结构实验报告
霍夫曼树实验报告
数据结构实验报告全集
哈夫曼树的实验报告1
赫夫曼树实验报告
数据结构实验报告模板
哈夫曼树实验报告
数据结构实验报告
数据结构实验报告及心得体会
哈夫曼树实验报告
哈夫曼树及其操作-数据结构实验报告(2)
数据结构实验报告图实验
哈夫曼树实验报告(付原C语言程序)
数据结构实验报告(哈夫曼树)
数据结构与算法实验报告册
数据结构实验报告 - 答案汇总