数据结构实验指导书(2016)(5)

flushall(); f=getchar();

if(f=='C')q=initqueue_hc(); else if(f=='N')

{cshqueue_hc(q);printqueue_hc(q);} else if(f=='I')

{printf(\输入要的入队的元素:\flushall();e=getchar();

enqeue_hc(q,e);printqueue_hc(q);} else if(f=='D')

{deqeue_hc(q);printqueue_hc(q);} }while(f!='E');

hc_sqqueue *initqueue_hc() {hc_sqqueue *q;

q=(hc_sqqueue*)malloc(sizeof(hc_sqqueue)); if(!q)exit(ERROR); return(q);}

int cshqueue_hc(hc_sqqueue *q) {char e;

int enqeue_hc(hc_sqqueue *q,char e);

q->base=(char*)malloc(MAXQSIZE*sizeof(char)); if(!q->base)exit(ERROR);

q->front=q->rear=0;q->length=0; printf(\输入元素以#结束:\\n\flushall(); e=getchar(); while(e!='#') {enqeue_hc(q,e);

if(q->length==MAXQSIZE)return(ERROR); else {flushall();e=getchar();}} return(OK);}

int enqeue_hc(hc_sqqueue *q,char e)

{if(q->length==MAXQSIZE)return(ERROR); q->base[q->rear]=e;

q->rear=(q->rear+1)%MAXQSIZE; q->length++; return(OK);}

int deqeue_hc(hc_sqqueue *q) {if(q->length==0)return (ERROR);

printf(\出队的元素为:%c\\n\

第18页 /共58页

q->front=(q->front+1)%MAXQSIZE;q->length--; return (OK);}

int printqueue_hc(hc_sqqueue *q) {int t=q->front;

if(q->length==0){printf(\队空!\\n\if(q->length==MAXQSIZE)printf(\队满!\\n\printf(\当前队列中元素为:\\n\do{printf(\

t=(t+1)%MAXQSIZE;}while(t!=q->rear); return(OK);}

实验六二叉树建立及遍历操作

实验预备知识：

1．熟练指针进行数据访问。

2．掌握二叉树的存储结构和处理方法。 3．掌握二叉树三种遍历的算法。

一、实验目的

1．熟悉二叉树的存贮结构及遍历方式，掌握有关算法的实现。 2．能够利用二叉树解决具体问题。

二、实验环境

⒈ 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； ⒉ 软件：DOS或Windows操作系统+Turbo C；

三、实验要求

1．要求采用二叉链表作为存贮结构，完成二叉树的建立、先序、中序、和后序遍历的操作。其中先序遍历和后序遍历采用递归算法，中序遍历采用非递归算法。

2．输入数据：树中每个结点的数据类型设定为字符型。

四、实验内容

1．在自己的U盘的“姓名+学号”文件夹中创建“实验6”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2．实现如下二叉树处理函数。 建树子函数 先序遍历子函数 中序遍历子函数 后序遍历子函数

第19页 /共58页

#include //头文件 #include typedef struct BiTNode {

char data;

struct BiTNode *lchild,*rchild; }

BiTNode,*BiTree;//定义结点类型 BiTree CreateBiTree()//创建树 {

char p;BiTree T; scanf(\ if(p==' ')

T=NULL; else {

T=(BiTNode *)malloc(sizeof(BiTNode));//为结点开辟空间 T->data=p;

T->lchild=CreateBiTree(); T->rchild=CreateBiTree(); }

return (T); }

void PreOrder(BiTree T)//先序 {

if(T!=NULL) {

printf(\ PreOrder(T->lchild); PreOrder(T->rchild);

} }

void InOrder(BiTree T)//中序 {

if(T!=NULL) {

InOrder(T->lchild); printf(\ InOrder(T->rchild);

} }

void PostOrder(BiTree T)//后序

第20页 /共58页

{

if(T!=NULL) {

PostOrder(T->lchild); PostOrder(T->rchild); printf(\ } }

void main()//主函数 {

BiTree Ta;

Ta=CreateBiTree(); printf(\先序遍历:\ printf(\ PreOrder(Ta); printf(\

printf(\中序遍历:\ printf(\ InOrder(Ta); printf(\

printf(\后序遍历:\ printf(\ PostOrder(Ta); }

实验七二叉树的应用程序设计

实验预备知识：

2．掌握二叉树的创建和遍历算法。 3．掌握霍夫曼编码原理。

一、实验目的

1．进一步掌握二叉树的存储结构和相应算法。 2．掌握霍夫曼树树的创建和霍夫曼编码。

二、实验环境

⒈ 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； ⒉ 软件：DOS或Windows操作系统+Turbo C；

三、实验要求

1．要求采用二叉链表作为存贮结构，完成霍夫曼树的创建。

第21页 /共58页

2．输出对应数据的霍夫曼编码，并求出平均编码长度。

四、实验内容

1．在自己的U盘的“姓名+学号”文件夹中创建“实验7”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2．现在某电报公司假设有10字符进行编码，这10个字符的使用频率如下表所示，请创建霍夫曼树。

A 19 B 18 C 16 D 14 E 12 F 8 G 6 H 4 I 2 J 1 3.编写函数求出A~J的霍夫曼编码。

五、报告要求

1．认真书写实验报告，字迹清晰，格式规范。报告中应写清姓名、学号、实验日期、实验题目、实验目的、实验要求、实验原理（系统主要工作流程图）。

2．报告中应书写主要源程序，且源程序中要有注释。 3．报告最后包含实验总结和体会。

4．如未调试通过或结果不正确，试分析原因，利用课余时间独立完成，完成后方可书写实验报告。

#include #include #include

typedef char* HuffmanCode; typedef struct {char data;

unsigned int weight ;

unsigned int parent, LChild,RChild ; }HTNode, * HuffmanTree; //选出权值最小的两个//

void select(HuffmanTree *ht,int n, int *s1, int *s2) {int i;

int min1=0,min2=0;

(*ht)[min1].weight=(*ht)[min2].weight=101; for(i=1;i<=n;i++)

{if((*ht)[i].weight < (*ht)[min1].weight&&(*ht)[i].parent == 0) min1=i;} for(i=1;i<=n;i++)

{if((*ht)[i].weight < (*ht)[min2].weight&&(*ht)[i].parent == 0&&min1!=i) min2=i;}

*s1=min2;*s2=min1; }

第22页 /共58页