数据结构实验报告

数据结构实验报告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]ht=HT[s1]ht+HT[s2]ht;中的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]nt!=0)i++;

//下面选出权值最小的结点，用s1指向其序号

s1=i;

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

{

if(HT[i]nt==0&&HT[i]ht

}

//下面选出权值次小的结点，用s2指向其序号

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

{

if(HT[i]nt==0&&i!=s1)break;

}

s2=i;

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

{

if(HT[i]nt==0&&i!=s1&&HT[i]ht

}

}

//构造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]nt=i;

HT[s2]nt=i;

HT[i]ld=s1;

HT[i]ld=s2;

HT[i]ht=HT[s1]ht+HT[s2]ht;

}

//从叶子到根逆向求每个字符的郝夫曼编码

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]nt;f!=0;c=f,f=HT[f]nt) //从叶子到根逆向求编码

{

if(HT[f]ld==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)

{

=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));

if(!)

return ERROR;

=;

ksize=STACK_INIT_SIZE;

return OK;

}

Status DestoryStack(SqStack &S)

{

free();

return OK;

}

Status ClearStack(SqStack &S)

{

=;

return OK;

}

Status StackEmpty(SqStack S)

{

if(==)

return OK;

return ERROR;

}

int StackLength(SqStack S)

{

return ;

}

Status GetTop(SqStack S,ElemType &e)

{

if(>=ksize)

{

=(ElemType *)realloc(,(ksize+STACKINCREMENT)*sizeof(ElemType));

if(!) return ERROR;

=+ksize;

ksize+=STACKINCREMENT;

}

*++=e;

return OK;

}

Status Push(SqStack &S,ElemType e)

{

if(>=ksize)

{

=(ElemType *)realloc(,(ksize+STACKINCREMENT)*sizeof(ElemType));

if(!)

return ERROR;

=+ksize;

ksize+=STACKINCREMENT;

}

*++=e;

return OK;

}

Status Pop(SqStack &S,ElemType &e)

{

if(==)

return ERROR;

e=*;

return OK;

}

Status StackTraverse(SqStack S)

{

ElemType *p;

p=(ElemType *)malloc(sizeof(ElemType));

if(!p) return ERROR;

p=;

while(p!=)//上面一个...

{

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)

{

t ==

(QueuePtr)malloc(sizeof(QNode));

if (!t) return ERROR;

t->next = NULL;

return OK;

}

Status DestoryQueue(LinkQueue &Q)

{

while(t)

{

=t->next;

free(t);

t=;

}

return OK;

}

Status QueueEmpty(LinkQueue &Q)

{

if(t->next==NULL)

return OK;

return ERROR;

}

Status QueueLength(LinkQueue Q)

{

int i=0;

QueuePtr p,q;

p=t;

while(p->next)

{

i++;

p=t;

q=p->next;

p=q;

}

return i;

}

Status GetHead(LinkQueue Q,ElemType &e)

{

QueuePtr p;

p=t->next;

if(!p)

return ERROR;

e=p->data;

return e;

}

Status ClearQueue(LinkQueue &Q)

{

QueuePtr p;

while(t->next )

{

p=t->next;

free(t);

t=p;

}

t->next=NULL;

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

->next = p;

=p; //p->next 为空

return OK;

}

Status DeQueue(LinkQueue &Q,ElemType &e)

{

QueuePtr p;

if (t == )

return ERROR;

p = t->next;

e = p->data;

t->next = p->next;

if ( == p)

= t; //只有一个元素时(不存在指向尾指针)

free (p);

return OK;

}

Status QueueTraverse(LinkQueue Q)

{

QueuePtr p,q;

if( QueueEmpty(Q)==OK)

{

printf("这是一个空队列! ");

return ERROR;

}

p=t->next;

while(p)

{

q=p;

printf("%d<- ",q->data);

q=p->next;

p=q;

}

return OK;

}

循环队列：

Status InitQueue(SqQueue &Q)

{

=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));

if(!)

exit(OWERFLOW);

t==0;

return OK;

}

Status EnQueue(SqQueue &Q,QElemType e)

{

if((+1)%MAXQSIZE==t)

return ERROR;

[]=e;

=(+1)%MAXQSIZE;

return OK;

}

Status DeQueue(SqQueue &Q,QElemType &e)

{

if(t==)

return ERROR;

e=[t];

t=(t+1)%MAXQSIZE;

return OK;

}

int QueueLength(SqQueue Q)

{

return(t+MAXQSIZE)%MAXQSIZE;

}

Status DestoryQueue(SqQueue &Q)

{

free();

return OK;

}

Status QueueEmpty(SqQueue Q) //判空

{

if(t ==)

return OK;

return ERROR;

}

Status QueueTraverse(SqQueue Q)

{

if(t==)

printf("这是一个空队列!");

while(t%MAXQSIZE!=)

{

printf("%d<- ",[t]);

t++;

}

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；

实验测试结果及结果分析

（一）测试结果

（二）结果分析

（略）

实验总结

（略）