数据结构实验报告六篇

第一篇 数据结构实验报告650字

一.实验内容：

实现哈夫曼编码的生成算法。

二.实验目的：

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['<

}

第二篇 北邮数据结构实验报告线性表1050字

北邮数据结构实验报告线性表

实验报告;课程名称：数据结构班级：软件工程实验成绩：;1206;实验名称：打印机队列模拟学号：20124848批;程序的设计;实验编号：实验一姓名：实验日期：2024年5月2;一、实验目的;对队列的理解;对stl中的queue的使用;实验仿真一个网络打印过程;二、实验内容与实验步骤流程图;这个任务队列的测试使用stl队列适配器;具体地说，每一行中包含的信息是

实 验 报 告

课程名称：数据结构 班级：软件工程实验成绩：

1206

实验名称：打印机队列模拟学号：20124848 批阅教师签字：

程序的设计

实验编号：实验一 姓名： 实验日期：2024年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;

}

五、实验结果总结

经测试，功能较为完整。代码流程简图如下：

通过这次实验，我了解了有关队列方面的知识。掌握了队列的逻辑结构，抽象数据类型，队列的存储方式等。运用先进先出表，仿真了网络打印队列。这都使我对数据结构的学习有了新的认识与帮助。在实验过程中，我也遇到了许多困难，从开始时对队列运算的不熟悉，到逐渐查找资料，从而完成了实验;六、附录;-《数据结构与算法分析》以及网上资料;

逐渐查找资料，从而完成了实验。在今后的学习中，我将继续努力，加强对堆栈，队列等知识的学习，以达到精益求精。

六、附录

-《数据结构与算法分析》以及网上资料

第三篇 数据结构实验报告实验五650字

数据结构实验报告 实验五

一.实验内容：

实现哈夫曼编码的生成算法。

二.实验目的：

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['<

}

第四篇 数据结构实验报告总结1450字

# include

# define ma__operator_num 100 //运算符栈数组长度

# define ma__data_num 100 //运算数栈数组长度

typedef struct opstack //定义运算符栈

{

char opstack[ma__operator_num];

int top;

}opstack， _popstack;

typedef struct datastack //定义运算数栈

{

double stack[ma__data_num];

int top;

}datastack， _pdatastack;

void initpopstack(popstack &postack) //初始化运算符栈

{

if( ！(postack = (popstack)malloc(sizeof(opstack)))) //为运算符栈分配空间

{

printf('分配内存空间失败！ ');

e_it(-1);

}

postack->;top = -1;

}

void initpdatastack(pdatastack &pdstack) //初始化运算数栈

{

if( ！(pdstack = (pdatastack)malloc(sizeof(datastack)))) //为运算数栈分配空间

{

printf('分配内存空间失败！ ');

e_it(-1);

}

pdstack->;top = -1;

}

void pushopstack(popstack &postack， char ch) //运算符进栈

{

postack->;opstack[++(postack->;top)] = ch;

}

void popopstack(popstack &postack， char &ch) //运算符出栈

{

ch = postack->;opstack[postack->;top];

postack->;top--;

}

void pushdatastack(pdatastack &pdstack， double d) //运算数进栈

{

++(pdstack->;top);

pdstack->;stack[pdstack->;top] = d;

}

void popdatastack(pdatastack &pdstack， double &d) //运算数出栈

{

d = pdstack->;stack[pdstack->;top];

pdstack->;top--;

}

void clearpopstack(popstack &postack) //清空运算符栈

{

postack->;top = -1;

}

void clearpdatastack(pdatastack &pdstack) //清空运算数栈

{

pdstack->;top = -1;

}

char gettoppopstack(popstack &postack) //获取运算符栈顶元素

{

return postack->;opstack[postack->;top];

}

double gettoppdatastack(pdatastack &pdstack) //获取运算数栈顶元素

{

return pdstack->;stack[pdstack->;top];

}

bool isop(char &ch) //区分 运算符 和 运算数 的函数，是运算符时返回true，否则返回false

{ //判断是否为符号

if ( (ch == '+') || (ch == '-') || (ch == '_') || (ch == '/') || (ch == '=') || (ch == 'a') || (ch == 's') || (ch == 'a') || (ch == 's') || (ch == '(') || (ch == ')') )

return true;

else

return false;

}

char precede(char op1， char op2) //参考《数据结构》(c语言版)第53页 3.2.5表达式求值 表 3.1

{

char tab[9][10]; //定义字符串的二维数组来存放运算符优先级的关系

strcpy( tab[0]， '>;>;<<;<;' );

strcpy( tab， '>;>;<<;<;' );

strcpy( tab， '>;;<;' );

strcpy( tab[3]， '>;;<;' );

strcpy( tab[4]， '<<<<<=<

strcpy( tab[5]， '>;e>;' );

strcpy( tab[6]， '>;;' );

strcpy( tab[7]， '>;;' );

strcpy( tab[8]， '<<<<

printf(' | ___欢迎您的下次使用！谢谢！___ | '); //退出使用

printf(' |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| ');

}

double operate(double a， char theta， double b) //对出栈的运算符和运算数进行计算

{

double s;

switch(theta)

{

case '+':

s = a + b;

break;

case '-':

s = a - b;

break;

case '_':

s = a _ b;

break;

case '/':

if ( b ！= 0 ) //判断除数是否为0，若为0，退出程序

{

s = a/b;

break;

}

else

{

printf(' #### 除数为0，非法运算。程序终止！ #### ');

e_it_e; //打印结束菜单

e_it(-1);

}

case 'a':

s = fabs(b); //调用fabs函数

break;

case 's':

if( b >;= 0) //判断被开方数是否为0，若为0，退出程序

{

s = sqrt(b); //调用sqrt函数

break;

}

else

{

printf(' #### 求负数的平方根是非法运算。程序终止！ #### ');

e_it_e; //打印结束菜单

e_it(-1);

}

}

return s;

}

char changechar(char &c) //通过changechar函数来把a、s的小写字母改为大写的

{

if( c == 'a' )

c = 'a';

else if( c == 's' )

c = 's';

return c;

}

//参考《数据结构》(c语言版)第53页 3.2.5表达式求值算法3.4 evaluatee_pression_r函数

void evaluatee_pression_r //计算函数：读入表达式，并计算结果

{

popstack postack; //声明运算符栈

pdatastack pdstack; //声明运算数栈

double result; //存运算的结果

char _， theta， c; //c存放读取的字符，_、theta存放运算符栈的栈顶元素

int flag， data; //标识符，用来读入连续的数字

double s;

double getd; //存放gettop___的结果

double a， b， cc; //a，b存放数据栈出栈的栈顶元素， c存放运算结果

flag = 0; //初始化标识符，用来判断字符串中的连续数字

data = 0; //

initpopstack(postack); //初始化运算符栈

initpdatastack(pdstack); //初始化运算数栈

pushopstack(postack， '='); //在运算符栈底放入'='

printf(' &请输入表达式以'='结束：');

c = get); //读入字符

changechar(c); //通过调用函数来实现把小写的a、s改为大写的a、s

while( c ！= '=' || gettoppopstack(postack) ！= '=')

{

if( ！isop(c) ) //不是运算符进栈

{

s = c - '0'; //把字符转化为数字

if ( flag == 1 )

{

popdatastack(pdstack， getd);

s = getd_10 + s;

}

pushdatastack(pdstack， s);

flag = 1;

c = get);

changechar(c);

}

else

{

flag = 0;

switch( precede(gettoppopstack(postack)， c) ) //输入元素和运算符栈顶元素比较

{

case '<': //栈顶元素优先级低

pushopstack(postack， c);

c = get);

changechar(c);

break;

case '=': //托括号并接受下一个字符

popopstack(postack， _);

c = get);

changechar(c);

break;

case '>;': //退栈并将运算结果进栈

popopstack(postack， theta);

popdatastack(pdstack， b);

popdatastack(pdstack， a);

cc = operate(a， theta， b);

pushdatastack(pdstack， cc);

break;

}//switch

}//else

}//while

result = gettoppdatastack(pdstack); //运算结束时，运算数栈的栈底元素就是计算结果

clearpopstack(postack); //清空运算符栈

clearpdatastack(pdstack); //清空运算数栈

printf(' ->;计算结果为：%.2f '， result); //输出运算结果

return ;

}

void print_user //欢迎界面

{

printf(' 欢迎使用c语言版模拟计算器 ');

printf('________________________________________________________________________ ');

printf(' |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| ');

printf(' | 模拟计算器使用说明 | ');

printf(' | 作者：谢先斌 | ');

printf(' | 本程序包括对'+'、'-'、'_'、'/'、''的运算 | ');

printf(' | 本程序中abs算用a替代、sqrt运算用s代替 | ');

printf(' | 本程序中的一切字母均不区分大小写 | ');

printf(' 正确的表达式如：1+a(7-8)+s(9_8)= ');

printf(' | 输入'='表示表达式输入结束！ | ');

printf(' | 欢迎使用！-->;-->; | ');

printf(' |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| ');

printf('________________________________________________________________________ ');

}

int main //主函数

{

char in;

bool b; //标识符，用来标识是否结束程序

b = true; //初始化，不结束

print_user; //打印欢迎界面

printf(' _请确认使用计算器y/n:');

while(1)

{

scanf('%c'， &in); //确认是否继续操作

get); //吃掉会车，避免干扰

switch(in)

{

case 'y':

case 'y':

{

evaluatee_pression_r; //进入计算函数：读入表达式，并计算结果

break;

}

case 'n':

case 'n':

{

e_it_e;

b = false;

break;

}

//default:

// printf(' __输入错误，请重新输入y/n:');

// break;

}

if(b==false) //如果 b==false ，退出整个程序

break;

printf(' _您确定要继续使用计算机y/n:');

get); //用getchar吃掉回车，避免对后续输入中in的干扰

}

return 0;

}

第五篇 c数据结构实验报告4350字

c数据结构实验报告

数据结构(c语言版)实验报告;专业：计算机科学与技术、软件工程;学号:____201240703061_____;班级:_________软件二班________;姓名:________朱海霞__________;指导教师:___刘遵仁_____________;青岛大学信息工程学院;2024年10月;实验1;实验题目：顺序存储结构线性表的插入和删除;实验目

数据结构(c语言版) 实验报告

专业：计算机科学与技术、软件工程

学号:____201240703061___________________

班级:_________软件二班______________

姓名:________朱海霞______________

指导教师:___刘遵仁________________

青岛大学信息工程学院

2024年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 _ne_t;

}lnode，_linklist;

int initlist_l(linklist &l){

l=(linklist)malloc(sizeof(lnode)); l->;ne_t=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->;ne_t;++j;

}

if(！p||j>;i-1)

return error;

s=(linklist)malloc(sizeof(lnode)); s->;data=e;

s->;ne_t=p->;ne_t;

p->;ne_t=s;

return ok;

}

int listdelete_l(linklist&l，int i，int &e){ linklist p，q;

int j;

p=l;j=0;

while(p->;ne_t&&j

p=p->;ne_t;++j;

}

if(！(p->;ne_t)||j

return error;

q=p->;ne_t;p->;ne_t=q->;ne_t; 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->;ne_t;

while(p！=null){

printf('%c '，p->;data); p=p->;ne_t;

}//插入八个字符printf(' ;实验结果：;acefhjqu;abcefhjqu;abefhjqu;心得体会：;单链表是通过扫描指针p进行单链表的操作;头指针唯;实验3;实验题目：栈操作设计和实现;实验目的：;1、掌握栈的顺序存储结构和链式存储结构，以便在实;2、掌握栈的特点，即后进先出和先进先出的原则;3、掌握栈的'基本运算，如：入栈与出栈

}

}//插入八个字符 printf(' '); i=2; int e; listinsert_l(l，i，'b'); p=l->;ne_t; while(p！=null){ printf('%c '，p->;data); p=p->;ne_t; }//插入一个字符 printf(' '); i=3; listdelete_l(l，i，e); p=l->;ne_t; while(p！=null){ printf('%c '，p->;data); p=p->;ne_t; } 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))))

e_it(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)

e_it(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 ma_verte_num 100 //定义最大顶点数

typedef struct{

char ve_s[ma_verte_num]; //顶点表

int edges[ma_verte_num][ma_verte_num]; //邻接矩阵，可看作边表 int n，e; //图中的顶点数n和边数e

}mgraph; //用邻接矩阵表示的图的类型

//=========建立邻接矩阵=======

void creatmgraph(mgraph _g)

{

int i，j，k;

char a;

printf('input verte_num(n) and edgesnum(e): ');

scanf('%d，%d'，&g->;n，&g->;e); //输入顶点数和边数

scanf('%c'，&a);

printf('input verte_ string:');

for(i=0;in;i++)

{

scanf('%c'，&a);

g->;ve_s[i]=a; //读入顶点信息，建立顶点表

}

for(i=0;in;i++)

for(j=0;jn;j++)

g->;edges[i][j]=0; //初始化邻接矩阵

printf('input edges，creat adjacency matri_ ');

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[ma_verte_;//========dfs：深度优先遍历的递归算;voiddfsm(mgraph_g，inti);{//以vi为出发点

g->;edges[i][j]=1;

g->;edges[j][i]=1; //若为无向图，矩阵为对称矩阵;若建立有向图，去掉该条语句 }

}

//=========定义标志向量，为全局变量=======

typedef enum{false，true} boolean;

boolean visited[ma_verte_num];

//========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 ma_verte_num 50 //定义最大顶点数

typedef struct node{ //边表结点

int adjve_; //邻接点域

struct node _ne_t; //链域

}edgenode;

typedef struct vnode{ //顶点表结点

char verte_; //顶点域

edgenode _firstedge; //边表头指针

}verte_node;

typedef verte_node adjlist[ma_verte_num]; //adjlist是邻接表类型 typedef struct {

adjlist adjlist; //邻接表

int n，e; //图中当前顶点数和边数

} algraph; //图类型

//=========建立图的邻接表=======

void creatalgraph(algraph _g)

{

int i，j，k;

char a;

edgenode _s; //定义边表结点

printf('input verte_num(n) and edgesnum(e): ');

scanf('%d，%d'，&g->;n，&g->;e); //读入顶点数和边数

scanf('%c'，&a);

printf('input verte_ string:');

for(i=0;in;i++) //建立边表

{

scanf('%c'，&a);

g->;adjlist[i].verte_=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->;adjve_=j; //邻接点序号为j

s->;ne_t=g->;adjlist[i].firstedge;

g->;adjlist[i].firstedge=s; //将新结点_s插入顶点vi的边表头部

s=(edgenode _)malloc(sizeof(edgenode));

s->;adjve_=i; //邻接点序号为i

s->;ne_t=g->;adjlist[j].firstedge;

g->;adjlist[j].firstedge=s; //将新结点_s插入顶点vj的边表头部

}

}

//=========定义标志向量，为全局变量=======

typedef enum{false，true} boolean;

boolean visited[ma_verte_num];

//========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. 如何利用二分查找算法在一个有序表中插入一个元素_，并保持表的有序性？

程序代码

实验结果：

心得体会：

实验7

实验题目：排序

实验目的：

掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。

实验要求：

实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。

实验主要步骤：

程序代码

实验结果：

心得体会：

第六篇 北邮数据结构实验报告2150字

北邮数据结构实验报告

北京邮电大学信息与通信工程学院

2009级数据结构实验报告

实验名称： 实验三哈夫曼编/解码器的实现

学生姓名：陈聪捷

日 期： 2024年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_ ne_t; //保存下一个节点的地址

};

示意图：

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 e_ception('堆空间用尽');

front->;ne_t=null;

front->;character=null;

front->;count=0;

node _pfront=front;

char ch=input[0]; //获得第一个字符

node_ new1=new node;

if(！new1)

throw e_ception('堆空间用尽');

new1->;character=ch; //将第一个字符插入链表

new1->;count=1;

new1->;ne_t=pfront->;ne_t;

pfront->;ne_t=new1;

bool replace=0; //判断在已经写入链表的字符中是否有与当前读出的字符相同的字符 int n=1; //统计链表中字符个数

for(int i=1;i

{

ch=input[i]; //获得第i个字符

do

{

pfront=pfront->;ne_t;

if((int)pfront->;character == (int)ch) //如果在链表中有与当前字符相同的字符，

该字符权值加1

{

pfront->;count++;

replace=1;

break;

}

}while(pfront->;ne_t);

if(！replace) //如果在链表中没找到与当前字符相同的字符，则将该字符作为新成 员插入链表

{

node_ new=new node;

if(！new)

throw e_ception('堆空间用尽');

new->;character=ch;

new->;count=1;

new->;ne_t=pfront->;ne_t;

pfront->;ne_t=new;

n++;

}

pfront=front; //重置pfront和replace变量为默认值 replace=0;

}

tsize=n; //tsize记录的是编码表中字符个数

createhtree(front，n); //创建哈夫曼树

pfront=front;

while(pfront) //销毁整个链表

{

front=pfront;

pfront=pfront->;ne_t;

front;

}

时间复杂度：

若输入的字符串长度为n，则时间复杂度为o(n)

2.创建哈夫曼树(void huffmantree::createcodetable(node _p))

算法伪代码：

1. 创建一个长度为2_tsize-1的三叉链表

2. 将存储字符及其权值的链表中的字符逐个写入三叉链表的前tsize个结点

的data域，并将对应结点的孩子域和双亲域赋为空

3. 从三叉链表的第tsize个结点开始，i=tsize

3.1 从存储字符及其权值的链表中取出两个权值最小的结点_，y，记录其

下标_，y。

3.2 将下标为_和y的哈夫曼树的结点的双亲设置为第i个结点

3.3 将下标为_的结点设置为i结点的左孩子，将下标为y的结点设置为

i结点的右孩子，i结点的权值为_结点的权值加上y结点的权值，i

结点的双亲设置为空

4. 根据哈夫曼树创建编码表

源代码：

void huffmantree::createhtree(node _p，int n)

{

root= new binode[2_n-1]; //初始化哈夫曼树

node _front=p->;ne_t;

if(n==0)

throw e_ception('没有输入字符');

for(int i=0;i

root[i].data=front->;count;

root[i].lchild=-1;

root[i].rchild=-1;

root[i].parent=-1;

front=front->;ne_t;

}

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->;ne_t;

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->;ne_t; //得到下一个字符

}

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++更加熟悉