- 目录
篇一 数据结构实验报告实验五
数据结构实验报告 实验五
一.实验内容：
实现哈夫曼编码的生成算法。
二.实验目的：
1、使学生熟练掌握哈夫曼树的生成算法。
2、熟练掌握哈夫曼编码的方法。
三.问题描述：
已知n个字符在原文中出现的频率，求它们的哈夫曼编码。
1、读入n个字符，以及字符的.权值，试建立一棵huffman树。
2、根据生成的huffman树，求每个字符的huffman编码。并对给定的待编码字符序列进行编码，并输出。
四.问题的实现
(1)郝夫曼树的存储表示
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}htnode,*huffmantree; //动态分配数组存储郝夫曼树
郝夫曼编码的存储表示
typedef char* *huffmancode;//动态分配数组存储郝夫曼编码
(2)主要的实现思路：
a.首先定义郝夫曼树的存储形式，这里使用了数组
b.用select遍历n个字符，找出权值最小的两个
c.构造郝夫曼树ht，并求出n个字符的郝夫曼编码hc
总结
1.基本上没有什么太大的问题，在调用select这个函数时，想把权值最小的两个结点的序号带回huffmancoding，所以把那2个序号设置成了引用。
2.在编程过程中，在什么时候分配内存，什么时候初始化花的时间比较长
3.最后基本上实现后，发现结果仍然存在问题，经过分步调试，发现了特别低级的输入错误。把ht[i].weight=ht[s1].weight+ht[s2].weight;中的s2写成了i
附：
//动态分配数组存储郝夫曼树
typedef struct{
int weight; //字符的权值
int parent,lchild,rchild;
}htnode,*huffmantree;
//动态分配数组存储郝夫曼编码
typedef char* *huffmancode;
//选择n个(这里是k=n)节点中权值最小的两个结点
void select(huffmantree &ht,int k,int &s1,int &s2)
{ int i;
i=1;
while(i<=k && ht[i].parent!=0)i++;
//下面选出权值最小的结点，用s1指向其序号
s1=i;
for(i=1;i<=k;i++)
{
if(ht[i].parent==0&&ht[i].weight
}
//下面选出权值次小的结点，用s2指向其序号
for(i=1;i<=k;i++)
{
if(ht[i].parent==0&&i!=s1)break;
}
s2=i;
for(i=1;i<=k;i++)
{
if(ht[i].parent==0&&i!=s1&&ht[i].weight
}
}
//构造huffman树，求出n个字符的编码
void huffmancoding(huffmantree &ht,huffmancode &hc,int *w,int n)
{
int m,c,f,s1,s2,i,start;
char *cd;
if(n<=1)return;
m=2*n-1; //n个叶子n-1个结点
ht=(huffmantree)malloc((m+1)*sizeof(htnode)); //0号单元未用，预分配m+1个单元
huffmantree p=ht+1;
w++; //w的号单元也没有值，所以从号单元开始
for(i=1;i<=n;i++,p++,w++)
{
p->;weight=*w;
p->;parent=p->;rchild=p->;lchild=0;
}
for(;i<=m;++i,++p)
{
p->;weight=p->;parent=p->;rchild=p->;lchild=0;
}
for(i=n+1;i<=m;i++)
{
select(ht,i-1,s1,s2); //选出当前权值最小的
ht[s1].parent=i;
ht[s2].parent=i;
ht[i].lchild=s1;
ht[i].rchild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
}
//从叶子到根逆向求每个字符的郝夫曼编码
hc=(huffmancode)malloc((n+1)*sizeof(char*)); //分配n个字符编码的头指针变量
cd=(char*)malloc(n*sizeof(char)); //分配求编码的工作空间
cd[n-1]='';//编码结束符
for(i=1;i<=n;i++) //逐个字符求郝夫曼编码
{
start=n-1; //编码结束符位置
for(c=i,f=ht[i].parent;f!=0;c=f,f=ht[f].parent) //从叶子到根逆向求编码
{
if(ht[f].lchild==c)cd[--start]='0';
else
cd[--start]='1';
}
hc[i]=(char*)malloc((n-start)*sizeof(char)); //为第i个字符编码分配空间
strcpy(hc[i],&cd[start]);//从cd复制编码到hc
}
free(cd); //释放工作空间
}
void main
{ int n,i;
int* w; //记录权值
char* ch; //记录字符
huffmantree ht;
huffmancode hc;
cout<<'请输入待编码的字符个数n=';
cin>;>;n;
w=(int*)malloc((n+1)*sizeof(int)); //记录权值，号单元未用
ch=(char*)malloc((n+1)*sizeof(char));//记录字符，号单元未用
cout<<'依次输入待编码的字符data及其权值weight'<
for(i=1;i<=n;i++)
{
cout<<'data['<
}
篇二 北邮数据结构实验报告线性表
北邮数据结构实验报告线性表
实验报告;课程名称：数据结构班级：软件工程实验成绩：;1206;实验名称：打印机队列模拟学号：20124848批;程序的设计;实验编号：实验一姓名：实验日期：2014年5月2;一、实验目的;对队列的理解;对stl中的queue的使用;实验仿真一个网络打印过程;二、实验内容与实验步骤流程图;这个任务队列的测试使用stl队列适配器;具体地说,每一行中包含的信息是
实 验 报 告
课程名称：数据结构 班级：软件工程实验成绩：
1206
实验名称：打印机队列模拟学号：20124848 批阅教师签字：
程序的设计
实验编号：实验一 姓名： 实验日期：2014年5 月 24 日
一、实验目的
对队列的理解
对stl中的queue的使用
实验仿真一个网络打印过程
二、实验内容与实验步骤流程图
这个任务队列的测试使用stl队列适配器。程序要求完成模拟的实现共享打印机。这个打印机使用先进先出队列。仿真是通过读取和处理事件数据文件的列表。一个有效的数据文件中的每一行包含信息打印作业和提交这份工作的时间。
具体地说,每一行中包含的信息是提交工作的时间(以秒为单位),和在页面的工作长及工作的计算机的名称。在模拟的开始,每个这些事件的每一个应该被程序所读，存储在继承工作负载队列。程序应该通过循环递增计数器或while-loop模拟时间的流逝。程序应该将计数器初始化为零,然后依次增加1秒。当模拟等于当前时间的打印作业的提交时间在工作队列的前面，一个打印作业完成。当这一切发生的时候,从工作队列取出这个事件,然后把它放在另一个队列对象。这个队列对象存储已完成的打印作业。当程序仿真其他的打印工作的时候，这些工作在队列等待。
win8，visual c++ 6.0
四、实验过程与分析
(1)实验主要函数及存储结构
main.cpp 包括主函数和主要的功能
simulator.h 仿真类的声明
simulator.cpp 仿真类的定义
event.h 事件类的声明
event.cpp - 事件类的定义
job.h 作业类的声明
job.cpp 作业类的.定义
arbitrary.run 包括任意打印作业数的数据文件
arbitrary.out 输出 arbitrary.run
bigfirst.run 包括打印较大作业的数据文件
bigfirst.out 输出 bigfirst.run
(2)实验代码
#ifndef fifo_h //fifo.h
#define fifo_h
#include 'simulator.h'
class fifo:public simulator{
protected:
queue waiting;
priority_queue priority_waiting;
public:
fifo(int seconds_per_page);
void simulate(string file);
};
bool operator < (event evtleft,event evtright);
#endif
#include 'fifo.h' //fifo.cpp
#include
using namespace std;
fifo::fifo(int seconds_per_page):simulator(seconds_per_page){ }
void fifo::simulate(string file){
int finish_time = 0;
float agg_latency = 0;
int totaljob =0;
event evt;
if(file.find('arbitrary')!= string::npos){
string outfile ='arbitrary.out';
ofstream osf(outfile.c_str);
loadworkload(file);
osf<<'fifo simulation '<
for(int time =1;!waiting.empty||!workload.empty;time++){ while(!workload.empty && time ==
workload.front.arrival_time){
evt= workload.front;
osf<<' arriving: '<
workload.pop;
}
if(!waiting.empty && time >;= finish_time){
totaljob ++;
evt = waiting.front;
agg_latency += time - evt.arrival_time;
osf<<' servicing: '<
finish_time = time + evt.getjob.getnumpages * seconds_per_page;
}
}
osf<<' total job '<
osf<<' aggregate latency: '<
osf<<' mean latency : '<
return;
}
if(file.find('bigfirst') != string::npos){
string outfile = 'bigfirst.out';
ofstream osf(outfile.c_str);
loadworkload(file);
osf<<'fifo simulation '<
for(int time
=1;!priority_waiting.empty||!workload.empty;time++){
while(!workload.empty && time ==
workload.front.arrival_time){
evt= workload.front;
osf<<' arriving: '<
workload.pop;
}
if(!priority_waiting.empty && time >;= finish_time){
totaljob ++;
evt = priority_waiting.top;
agg_latency += time - evt.arrival_time;
osf<<' servicing: '<
finish_time = time + evt.getjob.getnumpages * seconds_per_page; }
}
osf<<' total job '<
osf<<' aggregate latency: '<
osf<<' mean latency : '<
return;
}
cerr<<'the program don't know what algorithm to use'<
cerr<<'you should specify the file name with arbitrary or bigfirst'<
bool operator < (event evtleft,event evtright){
return evtleft.getjob.getnumpages <
evtright.getjob.getnumpages;
}
五、实验结果总结
经测试，功能较为完整。代码流程简图如下：
通过这次实验，我了解了有关队列方面的知识。掌握了队列的逻辑结构，抽象数据类型，队列的存储方式等。运用先进先出表，仿真了网络打印队列。这都使我对数据结构的学习有了新的认识与帮助。在实验过程中，我也遇到了许多困难，从开始时对队列运算的不熟悉，到逐渐查找资料，从而完成了实验;六、附录;-《数据结构与算法分析》以及网上资料;
逐渐查找资料，从而完成了实验。在今后的学习中，我将继续努力，加强对堆栈，队列等知识的学习，以达到精益求精。
六、附录
-《数据结构与算法分析》以及网上资料
篇三 c数据结构实验报告
c数据结构实验报告
数据结构(c语言版)实验报告;专业：计算机科学与技术、软件工程;学号:____201240703061_____;班级:_________软件二班________;姓名:________朱海霞__________;指导教师:___刘遵仁_____________;青岛大学信息工程学院;2013年10月;实验1;实验题目：顺序存储结构线性表的插入和删除;实验目
数据结构(c语言版) 实验报告
专业：计算机科学与技术、软件工程
学号:____201240703061___________________
班级:_________软件二班______________
姓名:________朱海霞______________
指导教师:___刘遵仁________________
青岛大学信息工程学院
2013年10月
实验1
实验题目：顺序存储结构线性表的插入和删除
实验目的：
了解和掌握线性表的逻辑结构和顺序存储结构，掌握线性表的基本算法及相关的时间性能分析。
实验要求：
建立一个数据域定义为整数类型的线性表，在表中允许有重复的数据;根据输入的数据，先找到相应的存储单元，后删除之。
实验主要步骤：
1、分析、理解给出的示例程序。
2、调试程序，并设计输入一组数据(3，-5，6，8，2，-5，4，7，-9)，测试程序的如下功能：根据输入的数据，找到相应的存储单元并删除，显示表中所有的数据。
程序代码:
#include
#include
#define ok 1
#define error 0
#define overflow -2
#define list_init_size 100
#define listincrement 10
typedef struct{
int* elem;
int length;
int listsize;
}sqlist;
int initlist_sq(sqlist &l){
l.elem=(int*)malloc(list_init_size*sizeof(int));
if(!l.elem) return -1;
l.length=0;
l.listsize=list_init_size;
return ok;
}
int listinsert_sq(sqlist&l,int i,int e){
if(i<1||i>;l.length+1) return error;
if(l.length==l.listsize){
int *newbase;
newbase=(int*)realloc(l.elem,(l.listsize+listincrement)*sizeof(int));
if(!newbase) return -1;
l.elem=newbase;
l.listsize+=listincrement;
}
int *p,*q;
q=&(l.elem[i-1]);
for(p=&(l.elem[l.length-1]);p>;=q;--p)
*(p+1)=*p;
*q=e;
++l.length;
return ok;
}
int listdelete_sq(sqlist &l,int i,int e){
int *p,*q;
if(i<1||i>;l.length)return error;
p=&(l.elem[i-1]);
e=*p;
q=l.elem+l.length-1;
for(++p;p<=q;++p)
*(p-1)=*p;
--l.length;
return ok;
}
int main{
sqlist l;
initlist_sq(l);//初始化
int i,a[]={3,-5,6,8,2,-5,4,7,-9};
for(i=1;i<10;i++)
listinsert_sq(l,i,a[i-1]);
for(i=0;i<9;i++)
printf(' %d',l.elem[i]);
printf(' ');//插入9个数
listinsert_sq(l,3,24);
for(i=0;i<10;i++)
printf(' %d',l.elem[i]);
printf(' ');//插入一个数
int e;
listdelete_sq(l,2, e);
for(i=0;i<9;i++)
printf(' %d',l.elem[i]);//删除一个数
printf(' ');
return 0;
}
实验结果：
3，-5,6,8,2，-5,4,7，-9
3，-5,24,6,8,2，-5,4,7，-9
3,24,6,8,2，-5,4,7，-9
心得体会：
顺序存储结构是一种随机存取结构，存取任何元素的时间是一个常数，速度快;结构简单，逻辑上相邻的元素在物理上也相邻;不使用指针，节省存储空间;但是插入和删除元素需要移动大量元素，消耗大量时间;需要一个连续的存储空间;插入元素可能发生溢出;自由区中的存储空间不能被其他数据共享 实验2
实验题目：单链表的插入和删除
实验目的：
了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。
实验要求：
建立一个数据域定义为字符类型的单链表，在链表中不允许有重复的字符;根据输入的字符，先找到相应的结点，后删除之。
实验主要步骤：
3、分析、理解给出的示例程序。
4、调试程序，并设计输入数据(如：a，c，e，f，h，j，q，m)，测试程序的如下功能：不允许重复字符的插入;根据输入的字符，找到相应的结点并删除。
5、修改程序：
(1) 增加插入结点的功能。
(2) 建立链表的方法有“前插”、“后插”法。
程序代码:
#include
#include
#define null 0
#define ok 1
#define error 0
typedef struct lnode{
int data;
struct lnode *next;
}lnode,*linklist;
int initlist_l(linklist &l){
l=(linklist)malloc(sizeof(lnode)); l->;next=null;
return ok;
}
int listinsert_l(linklist &l,int i,int e){ linklist p,s;
int j;
p=l;j=0;
while(p&&j
p=p->;next;++j;
}
if(!p||j>;i-1)
return error;
s=(linklist)malloc(sizeof(lnode)); s->;data=e;
s->;next=p->;next;
p->;next=s;
return ok;
}
int listdelete_l(linklist&l,int i,int &e){ linklist p,q;
int j;
p=l;j=0;
while(p->;next&&j
p=p->;next;++j;
}
if(!(p->;next)||j
return error;
q=p->;next;p->;next=q->;next; e=q->;data;free(q);
return ok;
}
int main{
linklist l,p;
char a[8]={'a','c','e','f','h','j','q','u'}; int i,j;
initlist_l(l);
for(i=1,j=0;i<=8,j<8;i++,j++) listinsert_l(l,i,a[j]);
p=l->;next;
while(p!=null){
printf('%c ',p->;data); p=p->;next;
}//插入八个字符printf(' ;实验结果：;acefhjqu;abcefhjqu;abefhjqu;心得体会：;单链表是通过扫描指针p进行单链表的操作;头指针唯;实验3;实验题目：栈操作设计和实现;实验目的：;1、掌握栈的顺序存储结构和链式存储结构，以便在实;2、掌握栈的特点，即后进先出和先进先出的原则;3、掌握栈的'基本运算，如：入栈与出栈
}
}//插入八个字符 printf(' '); i=2; int e; listinsert_l(l,i,'b'); p=l->;next; while(p!=null){ printf('%c ',p->;data); p=p->;next; }//插入一个字符 printf(' '); i=3; listdelete_l(l,i,e); p=l->;next; while(p!=null){ printf('%c ',p->;data); p=p->;next; } printf(' '); return 0;
实验结果：
a c e f h j q u
a b c e f h j q u
a b e f h j q u
心得体会：
单链表是通过扫描指针p进行单链表的操作;头指针唯一标识点链表的存在;插入和删除元素快捷，方便。
实验3
实验题目：栈操作设计和实现
实验目的：
1、掌握栈的顺序存储结构和链式存储结构，以便在实际中灵活应用。
2、掌握栈的特点，即后进先出和先进先出的原则。
3、掌握栈的基本运算，如：入栈与出栈等运算在顺序存储结构和链式存储结构上的实现。
实验要求：
回文判断：对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如
“abba”是回文，而“abab”不是回文。
实验主要步骤
(1)数据从键盘读入;
(2)输出要判断的字符串;
(3)利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“yes”，否则输出“no”。
程序代码:
#include
#include
#define true 1
#define false 0
#define ok 1
#define error 0
#define overflow -2
#define n 100
#define stack_init_size 100
#define stackincrement 10
typedef struct{
int *base; // 在栈构造之前和销毁之后，base的值为null int *top; // 栈顶指针
int stacksize; // 当前已分配的存储空间，以元素为单位
} sqstack;
int initstack(sqstack &s)
{ // 构造一个空栈s
if(!(s.base=(int *)malloc(stack_init_size*sizeof(int))))
exit(overflow); // 存储分配失败
s.top=s.base;
s.stacksize=stack_init_size;
return ok;
}
int stackempty(sqstack s)
{ // 若栈s为空栈，则返回true，否则返回false
if(s.top==s.base)
return true;
else
return false;
}
int push(sqstack &s, int e)
{ // 插入元素e为新的栈顶元素
if(s.top-s.base>;=s.stacksize) // 栈满，追加存储空间
{
s.base=(int *)realloc(s.base,(s.stacksize+stackincrement)*sizeof(int)); if(!s.base)
exit(overflow); // 存储分配失败
s.top=s.base+s.stacksize;
s.stacksize+=stackincrement;
}
*(s.top)++=e;
return ok;
}
int pop(sqstack &s,int &e)
{ // 若栈不空，则删除s的栈顶元素，用e返回其值，并返回ok;否则返回error if(s.top==s.base)
return error;
e=*--s.top;
return ok;
}
int main{
sqstack s;
int i,e,j,k=1;
char ch[n] = {0},*p,b[n] = {0};
if(initstack(s)) // 初始化栈成功
{
printf('请输入表达式: ');
gets(ch);
p=ch;
while(*p) // 没到串尾
push(s,*p++);
for(i=0;i
if(!stackempty(s)) {// 栈不空
pop(s,e); // 弹出栈顶元素
b[i]=e;
}
}
for(i=0;i
if(ch[i]!=b[i])
k=0;
}
if(k==0)
printf('no!');
else
printf('输出:')
printf('yes!');
}
return 0;
}
实验结果：
请输入表达式：
abcba
输出：yes!
心得体会：栈是仅能在表尾惊醒插入和删除操作的线性表，具有先进后出的性质，这个固有性质使栈成为程序设计中的有用工具。
实验4
实验题目：二叉树操作设计和实现
实验目的：
掌握二叉树的定义、性质及存储方式，各种遍历算法。
实验要求：
采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。
实验主要步骤：
1、分析、理解程序。
2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点(空指针)，如abd###ce##f##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。
程序代码:
实验结果：
心得体会：
实验5
实验题目：图的遍历操作
实验目的：
掌握有向图和无向图的概念;掌握邻接矩阵和邻接链表建立图的存储结构;掌握dfs及bfs对图的遍历操作;了解图结构在人工智能、工程等领域的广泛应用。
实验要求：
采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的dfs和bfs操作。
实验主要步骤：
设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的dfs(深度优先遍历)和bfs(广度优先遍历)的操作。
1. 邻接矩阵作为存储结构
#include'stdio.h'
#include'stdlib.h'
#define maxvertexnum 100 //定义最大顶点数
typedef struct{
char vexs[maxvertexnum]; //顶点表
int edges[maxvertexnum][maxvertexnum]; //邻接矩阵，可看作边表 int n,e; //图中的顶点数n和边数e
}mgraph; //用邻接矩阵表示的图的类型
//=========建立邻接矩阵=======
void creatmgraph(mgraph *g)
{
int i,j,k;
char a;
printf('input vertexnum(n) and edgesnum(e): ');
scanf('%d,%d',&g->;n,&g->;e); //输入顶点数和边数
scanf('%c',&a);
printf('input vertex string:');
for(i=0;in;i++)
{
scanf('%c',&a);
g->;vexs[i]=a; //读入顶点信息，建立顶点表
}
for(i=0;in;i++)
for(j=0;jn;j++)
g->;edges[i][j]=0; //初始化邻接矩阵
printf('input edges,creat adjacency matrix ');
for(k=0;ke;k++) { //读入e条边，建立邻接矩阵
scanf('%d%d',&i,&j); //输入边(vi，vj)的顶点序号
g->;edges[i][j]=1;;g->;edges[j][i]=1;//若为;//=========定义标志向量，为全局变量=;typedefenum{false,true}b;booleanvisited[maxvertex;//========dfs：深度优先遍历的递归算;voiddfsm(mgraph*g,inti);{//以vi为出发点
g->;edges[i][j]=1;
g->;edges[j][i]=1; //若为无向图，矩阵为对称矩阵;若建立有向图，去掉该条语句 }
}
//=========定义标志向量，为全局变量=======
typedef enum{false,true} boolean;
boolean visited[maxvertexnum];
//========dfs：深度优先遍历的递归算法======
void dfsm(mgraph *g,int i)
{ //以vi为出发点对邻接矩阵表示的图g进行dfs搜索，邻接矩阵是0，1矩阵
给出你的编码
//===========bfs：广度优先遍历=======
void bfs(mgraph *g,int k)
{ //以vk为源点对用邻接矩阵表示的图g进行广度优先搜索
给出你的编码
//==========主程序main =====
void main
{
int i;
mgraph *g;
g=(mgraph *)malloc(sizeof(mgraph)); //为图g申请内存空间
creatmgraph(g); //建立邻接矩阵
printf('print graph dfs: ');
dfs(g); //深度优先遍历
printf(' ');
printf('print graph bfs: ');
bfs(g,3); //以序号为3的顶点开始广度优先遍历
printf(' ');
}
2. 邻接链表作为存储结构
#include'stdio.h'
#include'stdlib.h'
#define maxvertexnum 50 //定义最大顶点数
typedef struct node{ //边表结点
int adjvex; //邻接点域
struct node *next; //链域
}edgenode;
typedef struct vnode{ //顶点表结点
char vertex; //顶点域
edgenode *firstedge; //边表头指针
}vertexnode;
typedef vertexnode adjlist[maxvertexnum]; //adjlist是邻接表类型 typedef struct {
adjlist adjlist; //邻接表
int n,e; //图中当前顶点数和边数
} algraph; //图类型
//=========建立图的邻接表=======
void creatalgraph(algraph *g)
{
int i,j,k;
char a;
edgenode *s; //定义边表结点
printf('input vertexnum(n) and edgesnum(e): ');
scanf('%d,%d',&g->;n,&g->;e); //读入顶点数和边数
scanf('%c',&a);
printf('input vertex string:');
for(i=0;in;i++) //建立边表
{
scanf('%c',&a);
g->;adjlist[i].vertex=a; //读入顶点信息
g->;adjlist[i].firstedge=null; //边表置为空表
}
printf('input edges,creat adjacency list ');
for(k=0;ke;k++) { //建立边表
scanf('%d%d',&i,&j); //读入边(vi，vj)的顶点对序号
s=(edgenode *)malloc(sizeof(edgenode)); //生成边表结点
s->;adjvex=j; //邻接点序号为j
s->;next=g->;adjlist[i].firstedge;
g->;adjlist[i].firstedge=s; //将新结点*s插入顶点vi的边表头部
s=(edgenode *)malloc(sizeof(edgenode));
s->;adjvex=i; //邻接点序号为i
s->;next=g->;adjlist[j].firstedge;
g->;adjlist[j].firstedge=s; //将新结点*s插入顶点vj的边表头部
}
}
//=========定义标志向量，为全局变量=======
typedef enum{false,true} boolean;
boolean visited[maxvertexnum];
//========dfs：深度优先遍历的递归算法======
void dfsm(algraph *g,int i)
{ //以vi为出发点对邻接链表表示的图g进行dfs搜索
给出你的编码
//==========bfs：广度优先遍历=========
void bfs(algraph *g,int k)
{ //以vk为源点对用邻接链表表示的图g进行广度优先搜索
给出你的编码
//==========主函数===========
void main
{
int i;
algraph *g;
g=(algraph *)malloc(sizeof(algraph));
creatalgraph(g);
printf('print graph dfs: ');
dfs(g);
printf(' ');
printf('print graph bfs: ');
bfs(g,3);
printf(' ');
}
实验结果：
1. 邻接矩阵作为存储结构
2. 邻接链表作为存储结构
心得体会：
实验6
实验题目：二分查找算法的实现
实验目的：
掌握二分查找法的工作原理及应用过程，利用其工作原理完成实验题目中的内容。。
实验要求：
编写程序构造一个有序表l，从键盘接收一个关键字key，用二分查找法在l中查找key，若找到则提示查找成功并输出key所在的位置，否则提示没有找到信息。。
实验主要步骤：
1. 建立的初始查找表可以是无序的，如测试的数据为{3，7，11，15，17，21，35，42，50｝或者{11，21，7，3，15，50，42，35，17｝。
2. 给出算法的递归和非递归代码;
3. 如何利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性?
程序代码
实验结果：
心得体会：
实验7
实验题目：排序
实验目的：
掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。
实验要求：
实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。
实验主要步骤：
程序代码
实验结果：
心得体会：
篇四 数据结构实验报告
数据结构实验报告
数据结构实验报告1
一.实验内容：
实现哈夫曼编码的生成算法。
二.实验目的：
1、使学生熟练掌握哈夫曼树的生成算法。
2、熟练掌握哈夫曼编码的方法。
三.问题描述：
已知n个字符在原文中出现的频率，求它们的哈夫曼编码。
1、读入n个字符，以及字符的权值，试建立一棵huffman树。
2、根据生成的huffman树，求每个字符的huffman编码。并对给定的待编码字符序列进行编码，并输出。
四.问题的实现
(1)郝夫曼树的存储表示
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}htnode,*huffmantree; //动态分配数组存储郝夫曼树
郝夫曼编码的存储表示
typedef char* *huffmancode;//动态分配数组存储郝夫曼编码
(2)主要的实现思路：
a.首先定义郝夫曼树的存储形式，这里使用了数组
b.用select遍历n个字符，找出权值最小的两个
c.构造郝夫曼树ht，并求出n个字符的郝夫曼编码hc
总结
1.基本上没有什么太大的问题，在调用select这个函数时，想把权值最小的两个结点的序号带回huffmancoding，所以把那2个序号设置成了引用。
2.在编程过程中，在什么时候分配内存，什么时候初始化花的时间比较长
3.最后基本上实现后，发现结果仍然存在问题，经过分步调试，发现了特别低级的输入错误。把ht[i].weight=ht[s1].weight+ht[s2].weight;中的s2写成了i
附：
//动态分配数组存储郝夫曼树
typedef struct{
int weight; //字符的.权值
int parent,lchild,rchild;
}htnode,*huffmantree;
//动态分配数组存储郝夫曼编码
typedef char* *huffmancode;
//选择n个(这里是k=n)节点中权值最小的两个结点
void select(huffmantree &ht,int k,int &s1,int &s2)
{ int i;
i=1;
while(i<=k && ht[i].parent!=0)i++;
//下面选出权值最小的结点，用s1指向其序号
s1=i;
for(i=1;i<=k;i++)
{
if(ht[i].parent==0&&ht[i].weight
}
//下面选出权值次小的结点，用s2指向其序号
for(i=1;i<=k;i++)
{
if(ht[i].parent==0&&i!=s1)break;
}
s2=i;
for(i=1;i<=k;i++)
{
if(ht[i].parent==0&&i!=s1&&ht[i].weight
}
}
//构造huffman树，求出n个字符的编码
void huffmancoding(huffmantree &ht,huffmancode &hc,int *w,int n)
{
int m,c,f,s1,s2,i,start;
char *cd;
if(n<=1)return;
m=2*n-1; //n个叶子n-1个结点
ht=(huffmantree)malloc((m+1)*sizeof(htnode)); //0号单元未用，预分配m+1个单元
huffmantree p=ht+1;
w++; //w的号单元也没有值，所以从号单元开始
for(i=1;i<=n;i++,p++,w++)
{
p->weight=*w;
p->parent=p->rchild=p->lchild=0;
}
for(;i<=m;++i,++p)
{
p->weight=p->parent=p->rchild=p->lchild=0;
}
for(i=n+1;i<=m;i++)
{
select(ht,i-1,s1,s2); //选出当前权值最小的
ht[s1].parent=i;
ht[s2].parent=i;
ht[i].lchild=s1;
ht[i].rchild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
}
//从叶子到根逆向求每个字符的郝夫曼编码
hc=(huffmancode)malloc((n+1)*sizeof(char*)); //分配n个字符编码的头指针变量
cd=(char*)malloc(n*sizeof(char)); //分配求编码的工作空间
cd[n-1]='';//编码结束符
for(i=1;i<=n;i++) //逐个字符求郝夫曼编码
{
start=n-1; //编码结束符位置
for(c=i,f=ht[i].parent;f!=0;c=f,f=ht[f].parent) //从叶子到根逆向求编码
{
if(ht[f].lchild==c)cd[--start]='0';
else
cd[--start]='1';
}
hc[i]=(char*)malloc((n-start)*sizeof(char)); //为第i个字符编码分配空间
strcpy(hc[i],&cd[start]);//从cd复制编码到hc
}
free(cd); //释放工作空间
}
void main
{ int n,i;
int* w; //记录权值
char* ch; //记录字符
huffmantree ht;
huffmancode hc;
cout<<'请输入待编码的字符个数n=';
cin>>n;
w=(int*)malloc((n+1)*sizeof(int)); //记录权值，号单元未用
ch=(char*)malloc((n+1)*sizeof(char));//记录字符，号单元未用
cout<<'依次输入待编码的字符data及其权值weight'<
for(i=1;i<=n;i++)
{
cout<<'data['<
}
数据结构实验报告2
一、实验目的及要求
1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。
本实验训练的要点是“栈”和“队列”的观点;
二、实验内容
1) 利用栈，实现数制转换。
2) 利用栈，实现任一个表达式中的语法检查(选做)。
3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列);
三、实验流程、操作步骤或核心代码、算法片段
顺序栈：
status initstack(sqstack &s)
{
s.base=(elemtype*)malloc(stack_init_size*sizeof(elemtype));
if(!s.base)
return error;
s.top=s.base;
s.stacksize=stack_init_size;
return ok;
}
status destorystack(sqstack &s)
{
free(s.base);
return ok;
}
status clearstack(sqstack &s)
{
s.top=s.base;
return ok;
}
status stackempty(sqstack s)
{
if(s.base==s.top)
return ok;
return error;
}
int stacklength(sqstack s)
{
return s.top-s.base;
}
status gettop(sqstack s,elemtype &e)
{
if(s.top-s.base>=s.stacksize)
{
s.base=(elemtype *)realloc(s.base,(s.stacksize+stackincrement)*sizeof(elemtype));
if(!s.base) return error;
s.top=s.base+s.stacksize;
s.stacksize+=stackincrement;
}
*s.top++=e;
return ok;
}
status push(sqstack &s,elemtype e)
{
if(s.top-s.base>=s.stacksize)
{
s.base=(elemtype *)realloc(s.base,(s.stacksize+stackincrement)*sizeof(elemtype));
if(!s.base)
return error;
s.top=s.base+s.stacksize;
s.stacksize+=stackincrement;
}
*s.top++=e;
return ok;
}
status pop(sqstack &s,elemtype &e)
{
if(s.top==s.base)
return error;
e=*--s.top;
return ok;
}
status stacktraverse(sqstack s)
{
elemtype *p;
p=(elemtype *)malloc(sizeof(elemtype));
if(!p) return error;
p=s.top;
while(p!=s.base)//s.top上面一个...
{
p--;
printf('%d ',*p);
}
return ok;
}
status compare(sqstack &s)
{
int flag,ture=ok,false=error;
elemtype e,x;
initstack(s);
flag=ok;
printf('请输入要进栈或出栈的元素：');
while((x= getchar)!='#'&&flag)
{
switch (x)
{
case '(':
case '[':
case '{':
if(push(s,x)==ok)
printf('括号匹配成功! ');
break;
case ')':
if(pop(s,e)==error || e!='(')
{
printf('没有满足条件 ');
flag=false;
}
break;
case ']':
if ( pop(s,e)==error || e!='[')
flag=false;
break;
case '}':
if ( pop(s,e)==error || e!='{')
flag=false;
break;
}
}
if (flag && x=='#' && stackempty(s))
return ok;
else
return error;
}
链队列：
status initqueue(linkqueue &q)
{
q.front =q.rear=
(queueptr)malloc(sizeof(qnode));
if (!q.front) return error;
q.front->next = null;
return ok;
}
status destoryqueue(linkqueue &q)
{
while(q.front)
{
q.rear=q.front->next;
free(q.front);
q.front=q.rear;
}
return ok;
}
status queueempty(linkqueue &q)
{
if(q.front->next==null)
return ok;
return error;
}
status queuelength(linkqueue q)
{
int i=0;
queueptr p,q;
p=q.front;
while(p->next)
{
i++;
p=q.front;
q=p->next;
p=q;
}
return i;
}
status gethead(linkqueue q,elemtype &e)
{
queueptr p;
p=q.front->next;
if(!p)
return error;
e=p->data;
return e;
}
status clearqueue(linkqueue &q)
{
queueptr p;
while(q.front->next )
{
p=q.front->next;
free(q.front);
q.front=p;
}
q.front->next=null;
q.rear->next=null;
return ok;
}
status enqueue(linkqueue &q,elemtype e)
{
queueptr p;
p=(queueptr)malloc(sizeof (qnode));
if(!p)
return error;
p->data=e;
p->next=null;
q.rear->next = p;
q.rear=p; //p->next 为空
return ok;
}
status dequeue(linkqueue &q,elemtype &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; //只有一个元素时(不存在指向尾指针)
free (p);
return ok;
}
status queuetraverse(linkqueue q)
{
queueptr p,q;
if( queueempty(q)==ok)
{
printf('这是一个空队列! ');
return error;
}
p=q.front->next;
while(p)
{
q=p;
printf('%d<- ',q->data);
q=p->next;
p=q;
}
return ok;
}
循环队列：
status initqueue(sqqueue &q)
{
q.base=(qelemtype*)malloc(maxqsize*sizeof(qelemtype));
if(!q.base)
exit(owerflow);
q.front=q.rear=0;
return ok;
}
status enqueue(sqqueue &q,qelemtype e)
{
if((q.rear+1)%maxqsize==q.front)
return error;
q.base[q.rear]=e;
q.rear=(q.rear+1)%maxqsize;
return ok;
}
status dequeue(sqqueue &q,qelemtype &e)
{
if(q.front==q.rear)
return error;
e=q.base[q.front];
q.front=(q.front+1)%maxqsize;
return ok;
}
int queuelength(sqqueue q)
{
return(q.rear-q.front+maxqsize)%maxqsize;
}
status destoryqueue(sqqueue &q)
{
free(q.base);
return ok;
}
status queueempty(sqqueue q) //判空
{
if(q.front ==q.rear)
return ok;
return error;
}
status queuetraverse(sqqueue q)
{
if(q.front==q.rear)
printf('这是一个空队列!');
while(q.front%maxqsize!=q.rear)
{
printf('%d<- ',q.base[q.front]);
q.front++;
}
return ok;
}
数据结构实验报告3
《数据结构与算法》实验报告
专业 班级 姓名 学号
实验项目
实验一 二叉树的应用
实验目的
1、进一步掌握指针变量的含义及应用。
2、掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。
3、掌握用指针类型描述、访问和处理二叉树的运算。
实验内容
题目1:编写一个程序，采用一棵二叉树表示一个家谱关系。要求程序具有如下功能：
（1）用括号表示法输出家谱二叉树，
（2）查找某人的所有儿子，
（3）查找某人的所有祖先。
算法设计分析
（一）数据结构的定义
为了能够用二叉树表示配偶、子女、兄弟三种关系，特采用以下存储关系，则能在二叉树上实现家谱的各项运算。
二叉树型存储结构定义为：
typedef struct snode
{char name[max]; //人名
struct snode *left;//指向配偶结点
struct snode *right; //指向兄弟或子女结点
}fnode;
（二）总体设计
实验由主函数、家谱建立函数、家谱输出函数、儿子查找函数、祖先查找函数、结点定位函数、选择界面函数七个函数共同组成。其功能描述如下：
（1）主函数：统筹调用各个函数以实现相应功能
void main
（2）家谱建立函数：与用户交互建立家族成员对应关系
void initialfamily(fnode *&head) //家谱建立函数
（3）家谱输出函数：用括号表示法输出家谱
输出形式为：父和母（子1和子妻1（孙1），子2和子妻2（孙2））
void printfamily(fnode *head) //家谱输出函数
（4）儿子查找函数：在家谱中查找到某人所有的子女并输出，同时也能辨别出其是否为家族成员与是否有子女
void findson(fnode *b,char p[]) //儿子查找函数
（5）祖先查找函数：在家谱中查找到某人所有的祖先并输出，同时也能辨别出其是否为家族中成员。
int findancestor(fnode *head,char son[ ]) //祖先查找函数
（6）结点定位函数：在家谱中找到用户输入人名所对应的结点。
fnode *findnode(fnode *b,char p[]) //结点定位函数
（7）选择界面函数：为便于编写程序，将用户选择部分独立为此函数。
void print(int &n)
（三）各函数的详细设计：
void initialfamily(fnode *&head) //家谱建立函数
1：首先建立当前人的信息，将其左右结点置为空，
2：然后让用户确定其是否有配偶，如果没有配偶，则当前程序结束，
3：如果有则建立其配偶信息，并将配偶结点赋给当前人的左结点；
4：再让用户确定其是否有子女，如果有则递归调用家谱建立函数建立子女结点，并将其赋给配偶结点的下一个右结点。
5：如无，则程序结束
void printfamily(fnode *head) //家谱输出函数
1：首先判断当前结点是否为空，如果为空则结束程序；
2：如果不为空，则输出当前结点信息，
3：然后判断其左结点（配偶结点）是否为空，如不为空则输出“和配偶信息。
4：再判断配偶结点的右结点是否为空，如不为空则递归调用输出其子女信息，最后输出“）”；
5：当配偶结点为空时，则判断其右结点（兄弟结点）是否为空
6：如果不为空，则输出“，”，并递归调用输出兄弟信息
7程序结束
fnode *findnode(fnode *b,char p[]) //结点定位函数
1：当前结点是否为空，为空则返回空；
2：如果和查找信息相同，则返回当前结点；
3：如不然，则先后递归访问其左结点，再不是则递归访问右结点
void findson(fnode *b,char p[]) //儿子查找函数
1：在家谱中定位到要查找的结点，如无则输出“查找不到此人”
2：判断其配偶结点与子女结点是否为空，为空则输出“无子女”
3：不为空则输出其配偶结点的所有右结点（子女结点）。
int findancestor(fnode *head,char son[ ]) //祖先查找函数
1：先在家谱中定位到要查找的结点，如为空输出“不存在此人”，程序结束
2：先将父母结点入栈，当栈为空时程序结束，
3：栈不为空时，判断栈顶元素是否已访问过，
4：访问过，再判断是否为查找结点，如是则输出栈中保存的其祖先结点，并滤过其兄弟结点不输出；不是查找结点，则退栈一个元素
5：未访问过，则取当前栈顶元素，置访问标志——1，同时取其右结点
6：栈不为空或当前所取结点不为空时，转到2；
实验测试结果及结果分析
（一）测试结果
（二）结果分析
（略）
实验总结
（略）
数据结构实验报告
篇五 北邮数据结构实验报告
北邮数据结构实验报告
北京邮电大学信息与通信工程学院
2009级数据结构实验报告
实验名称： 实验三哈夫曼编/解码器的实现
学生姓名：陈聪捷
日 期： 2010年11月28日
1.实验要求
一、实验目的：
了解哈夫曼树的思想和相关概念;
二、实验内容：
利用二叉树结构实现哈夫曼编/解码器
1.初始化：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树。
2.建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。
3.编码：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。
4.译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。
5.打印：以直观的方式打印哈夫曼树。
6.计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈夫曼编码的压缩效果。
7.用户界面可以设计成“菜单”方式，能进行交互，根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。
2. 程序分析
2.1 存储结构
二叉树
template
class bitree
{
public:
bitree; //构造函数，其前序序列由键盘输入
~bitree(void); //析构函数
binode* getroot; //获得指向根结点的指针
protected:
binode *root; //指向根结点的头指针
};
//声明类bitree及定义结构binode
data：
二叉树是由一个根结点和两棵互不相交的左右子树构成
哈夫曼树类的数据域，继承节点类型为int的二叉树 class huffmantree:public bitree
data:
hcode* hcodetable;//编码表
int tsize; //编码表中的总字符数
二叉树的节点结构
template
struct binode //二叉树的结点结构 {
t data; //记录数据
t lchild; //左孩子
t rchild; //右孩子
t parent; //双亲
};
编码表的节点结构
struct hcode
{
char data; //编码表中的字符
char code[100]; //该字符对应的编码
};
待编码字符串由键盘输入，输入时用链表存储，链表节点为 struct node
{
char character; //输入的字符
unsigned int count;//该字符的权值
bool used; //建立树的时候该字符是否使用过
node* next; //保存下一个节点的地址
};
示意图：
2.2 关键算法分析
1.初始化函数(void huffmantree::init(string input))
算法伪代码：
1.初始化链表的头结点
2.获得输入字符串的第一个字符，并将其插入到链表尾部,n=1(n记录的是链表
中字符的个数)
3.从字符串第2个字符开始，逐个取出字符串中的字符
3.1 将当前取出的字符与链表中已经存在的字符逐个比较，如果当前取出
的字符与链表中已经存在的某个字符相同，则链表中该字符的权值加1。
3.2 如果当前取出的字符与链表中已经存在的字符都不相同，则将其加入
到链表尾部，同时n++
4.tsize=n(tsize记录链表中字符总数，即哈夫曼树中叶子节点总数)
5.创建哈夫曼树
6.销毁链表
源代码：
void huffmantree::init(string input)
{
node *front=new node; //初始化链表的头结点
if(!front)
throw exception('堆空间用尽');
front->;next=null;
front->;character=null;
front->;count=0;
node *pfront=front;
char ch=input[0]; //获得第一个字符
node* new1=new node;
if(!new1)
throw exception('堆空间用尽');
new1->;character=ch; //将第一个字符插入链表
new1->;count=1;
new1->;next=pfront->;next;
pfront->;next=new1;
bool replace=0; //判断在已经写入链表的字符中是否有与当前读出的字符相同的字符 int n=1; //统计链表中字符个数
for(int i=1;i
{
ch=input[i]; //获得第i个字符
do
{
pfront=pfront->;next;
if((int)pfront->;character == (int)ch) //如果在链表中有与当前字符相同的字符，
该字符权值加1
{
pfront->;count++;
replace=1;
break;
}
}while(pfront->;next);
if(!replace) //如果在链表中没找到与当前字符相同的字符，则将该字符作为新成 员插入链表
{
node* new=new node;
if(!new)
throw exception('堆空间用尽');
new->;character=ch;
new->;count=1;
new->;next=pfront->;next;
pfront->;next=new;
n++;
}
pfront=front; //重置pfront和replace变量为默认值 replace=0;
}
tsize=n; //tsize记录的是编码表中字符个数
createhtree(front,n); //创建哈夫曼树
pfront=front;
while(pfront) //销毁整个链表
{
front=pfront;
pfront=pfront->;next;
front;
}
时间复杂度：
若输入的字符串长度为n，则时间复杂度为o(n)
2.创建哈夫曼树(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]; //初始化哈夫曼树
node *front=p->;next;
if(n==0)
throw exception('没有输入字符');
for(int i=0;i
root[i].data=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); //从0~i中选出两个权值最小的结点
root[new1].parent=root[new2].parent=i; //用两个权值最小的结点生成新结点，
新节点为其双亲
root[i].data=root[new1].data+root[new2].data;//新结点的权值为其孩子的权值的和 root[i].lchild=new1;
root[i].rchild=new2;
root[i].parent=-1;
}
createcodetable(p); //创建编码表
}
时间复杂度：
在选取两个权值最小的结点的函数中要遍历链表，时间复杂度为o(n),故该函数
的时间复杂度为o(n^2)
3.创建编码表(void huffmantree::createcodetable(node *p))
算法伪代码：
1.初始化编码表
2.初始化一个指针，从链表的头结点开始，遍历整个链表
2.1 将链表中指针当前所指的结点包含的字符写入编码表中
2.2 得到该结点对应的哈夫曼树的叶子结点及其双亲
2.3 如果哈夫曼树只有一个叶子结点，将其字符对应编码设置为0
2.4 如果不止一个叶子结点，从当前叶子结点开始判断
2.4.1 如果当前叶子结点是其双亲的左孩子，则其对应的编码为0，否
则为1
2.4.2 child指针指向叶子结点的双亲，parent指针指向child指针的双亲，
重复2.4.1的操作
2.5 将已完成的编码倒序
2.6 取得链表中的下一个字符
3.输出编码表
源代码：
void huffmantree::createcodetable(node *p)
{
hcodetable=new hcode[tsize]; //初始化编码表
node *front=p->;next;
for(int i=0;i
{
hcodetable[i].data=front->;character; //将第i个字符写入编码表
int child=i; //得到第i个字符对应的叶子节点
int parent=root[i].parent; //得到第i个字符对应的叶子节点的双亲
int k=0;
if(tsize==1) //如果文本中只有一种字符，它的.编码为0
{
hcodetable[i].code[k]='0';
k++;
}
while(parent!=-1) //从第i个字符对应的叶子节点开始，寻找它到根结点的路径
{
if(child==root[parent].lchild) //如果当前结点为双亲的左孩子，则编码为0，
否则编码为1
hcodetable[i].code[k]='0';
else
hcodetable[i].code[k]='1';
k++;
child=parent;
parent=root[child].parent;
}
hcodetable[i].code[k]='';
reverse(hcodetable[i].code); //将编码逆置
front=front->;next; //得到下一个字符
}
cout<<'编码表为：'<
for(i=0;i
{
cout<
parent=root[parent].lchild;
else //编码为1则寻找右孩子
parent=root[parent].rchild;
i++;
}
if(tsize==1) //如果编码表只有一个字符，则根结点即为叶子结点 i++;
d.append(1,hcodetable[parent].data);//将叶子节点对应的字符追加到解码串中 }
cout<
}
时间复杂度：
设待解码串长度为n，则复杂度为o(n)
8. 计算哈夫曼编码的压缩比(void huffmantree::calculate(string s1,string s2)) 算法伪代码：
1. 获得编码前字符串的长度，即其占用的字节数
2. 获得编码后的字符串的长度，将其除以8然后向上取整，得到其占用的字
节数
3. 压缩比将两个相除
源代码：
void huffmantree::calculate(string s1,string s2)
{
int cal1=s1.length;
int cal2=s2.length;
cal2=ceill((float)cal2/8); //将编码串的比特数转化为字节数 cout<<'编码前的字符串长度：'<
cout<<'编码后的字符串长度：'<
cout<<'压缩比为：'<<((double)cal2/(double)cal1)*100<<'%'<
}
时间复杂度：
o(1)
9. 打印哈夫曼树(void huffmantree::printtree(int treenode,int layer) ) 算法伪代码：
1. 如果待打印结点为空，则返回
2. 递归调用函数打印当前结点的右子树
3. 根据当前结点所在的层次确定其前面要输出多少空格，先输出空格，在打
印当前结点的权值
4. 递归调用函数打印当前结点的左子树
源代码：
void huffmantree::printtree(int treenode,int layer)
{
if(treenode==-1) //如果待打印结点为空，则返回 return;
else
{
printtree(root[treenode].rchild,layer+1); //先打印该结点的右子树，layer记录
的是该结点所在的层次
for(int i=0;i
空格
cout<<' ';
cout<
printtree(root[treenode].lchild,layer+1); //打印该结点的左子树
}
}
时间复杂度：
中序遍历哈夫曼树，复杂度为o(n)
10. 菜单函数(void huffmantree::menu)
算法伪代码：
1. 逐一读取键盘缓存区中的字符，并将它们逐一追加到记录输入字符串的
string变量中，直到读到回车输入符为止
2. 删除string变量末尾的回车输入符
3.利用string变量创建哈夫曼树，初始化编码表。
4. 直观打印哈夫曼树
5. 对输入的字符串进行编码
6. 对编码后的字符串进行解码
7. 计算编码前后的压缩比并输出
源代码：
void huffmantree::menu
{
cout<<'请输入你要编码的文本,按回车键确定输入'<
string input;
char letter;
do //将字符逐个读入input变量中
{
letter=cin.get;
input.append(1,letter);
}while(letter!=' ');
input.erase(input.length-1,1); //去掉input末尾的回车符
init(input); //根据输入的字符串创建哈夫曼树及其编码表 cout<<'直观打印哈夫曼树'<
printtree(2*tsize-1-1,1); //打印哈夫曼树
cout<<' '<<' ';
string d1,d2;
cout<<'编码后的字符串为'<
encode(input,d1); //编码并打印编码串
cout<<'解码后的字符串为'<
decode(d1,d2); //解码并打印解码串
cout<<'ascii码编码与huffman编码的比较'<
calculate(input,d1); //计算编码前后的压缩比
}
2.3 其他
1.由于题目要求能输入任意长的字符串，所以本程序采用了string变量来记录输入
的字符串，并采用string类的类成员函数来完成各项任务
2.打印哈夫曼树时采用了递归函数，且采用了凹凸表的形式打印哈夫曼树。
3.为了输入空格，输入时采取逐个字符输入的方式
3. 程序运行结果
主函数流程图：
运行结果：
各函数运行正常，没有出现bug
4. 总结
经过这次实验，我了解了哈夫曼树的创建过程，了解了一种不等长编码的方法，用设断点调试的方法更加熟练，同时熟悉了stl中string类型的用法，对c++更加熟悉
