数据结构课程设计报告

姓名：学号：班级：专业：辅导老师：

实践日期：2011-6-19

.二叉树。.哈夫曼树。

.纸牌游戏。

.一元多项式。

一、需求分析。

.哈夫曼树需求分析：

①初始化功能模块。

此模块的功能为从键盘接收字符集大小n,以及n个字符和n个权值。

②建立哈夫曼树的功能模块。

此模块功能为使用1中得到的数据按照教材中的构造哈夫曼树的算法构造哈夫曼树，即将huffnode数组中的各个位置的各个域都填上相关的值，并将这个结构体数组存于文件中。

③建立哈弗曼编码的功能模块。

此模块功能是从文件中读入相关的字符信息进行哈弗曼编码，然后将结果存入中，同时将字符与0和1**串的一一对应关系显示到屏幕上。

④打印哈夫曼树的功能模块。

此模块功能为从huffnode数组中读入相关的结点信息，以图形的方式将各个结点以及叶子结点的权值和左分支上的0和右分支上的1画出来。

ⅱ.二叉树需求分析：

1 功能：建立二叉树，并进行遍历。

2 输入要求：使用按数组标号法输入的方法。

3 测试数据：用三种递归和非递归的方法输出遍历结果。

纸牌需求分析：

用函数node按照题目要求的规则，用几个循环体来实现。

ⅳ.一元多项式需求分析：

1 输入并建立多项式的功能模块：此模块要求按照指数递增的顺序和一定的输入格式输入各个系数不为0的子项的“系数—指数对”，输入一个子项建立一个相关结点，当遇到输入结束的标志时停止输入，而转去执行程序下面的部分。

2 多项式相加的功能模块：此模块根据在1中建立的两个多项式进行相加运算，并存放在以c为头指针的一个新链表中。

3 多项式显示的功能模块：此模块用于多项式的显示，程序可以使用图形界面，用“系数—指数对”的形式表示表达式。

二、概要设计。

ⅰ.哈夫曼树概要设计：

模块分为5个，即初始化哈夫曼树、输入权值、选择两个权最小的根结点、构造哈夫曼树、求出哈夫曼树编码表。在构造哈夫曼树时，设计一个结构体数组huffnode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组huffnode的大小设置为2n-1，描述结点的数据类型为：

typedef struct

int data;

int weight;

int flag;

int parent;

int lchild;

int rchild;

hnodetype;

求哈夫曼编码时使用一堆结构数组huffcode作为哈夫曼编码信息的存储。设计如下数据类型：

#define maxbit 10

typedef struct

int bit[maxbit];

int start;

hcodetype;

ⅱ.二叉树概要设计：

模块分为八个，即①用数组表示输入法构造二叉链表；②递归先序、中序、后序遍历3个模块；③非递归先序、中序、后序遍历3个模块；④主函数。

ⅲ.纸牌概要设计：

1、数据输入；2、数据统计；3、数据输出；4、查找、修改、删除。

ⅳ.一元多项式概要设计：

分析任意一元多项式的描述方法可知，一个一元多项式的每一个子项都由“系数—指数”两部分组成，所以可以将它抽象成一个由“系数—指数对”构成的线性表，由于对多项式中系数为0的子项可以不记录它的指数值，对于这样的情况就不再付出存储空间来存放它了。具体数据类型定义为：

typedef struct polynode

for(i=0;i

void outputhaffman(hnodetype huffnode,hcodetype huffcode,int n)

int i,j;

printf("%d个叶节点对应编码为：",n);

for(i=0;i

void haffman(hnodetype huffnode,hcodetype huffcode,int n)

int i,j,m1,m2,x1,x2,c,p;

hcodetype cd;

for(i=0;i

for(j=

//for//end of haffman

void main2()

hnodetype huffnode[maxnode];

hcodetype huffcode[maxleaf];

int n;

printf("输入叶子节点个数n:");

scanf("%d",&n);

inithaffman(huffnode,huffcode,n);

haffman(huffnode,huffcode,n);

outputhaffman(huffnode,huffcode,n);

二叉树详细设计：

#include ""

#define maxsize 255

typedef struct binode

char data;

struct binode *lchild;

struct binode *rchild;

bitree;

bitree *creatbitreepre(char *str)

bitree *bt,*stack[maxsize],*p=null;

int top=-1,k,j=0; char ch;

bt=null; ch=str[j];

while(ch!='0')

case')'

case','

default:

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

p->data=ch;p->lchild=p->rchild=null;

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

其他用户还读了