数据结构课程设计报告

数据结构。

课程设计报告。

设计题目：题目1：

题目2：专业。

班级。学生。

学号。指导教师。

目录。一、具体任务。

二、软件环境。

三、算法设计思想及流程图。

四、主要变量、函数介绍。

五、运行结果。

六、收获及体会。

参考文献。一、具体任务。

1、链表应用：设计程序以实现任意两个高次多项式的加法和减法运算。

要求：（1）所设计的数据结构应尽可能节省存储空间；

2）程序的运行时间尽可能少。

2、哈夫曼树应用：设计程序以实现构造哈夫曼树的哈夫曼算法。

要求：（1）从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并保存，并将哈夫曼树以直观的方式（比如树）显示在终端上；利用已经建好的哈夫曼树构造哈夫曼编码，并输出结果；

2）求解所构造的哈夫曼树的带权路径长度。

二、软件环境。

microsoft visual c++ 6.0

二、算法设计思想及流程图。

设计思想：1、链表应用。

1)建立高次多项式：先为多项式链表分配空间，再输入其中一项的系数和指数，构建多项式链表。

2)高次多项式加法运算：从两个多项式的头部开始，当两个。

多项式的指数相等时，系数就相加；当前一个多项式中的。

某一项的指数与后一个中的某项指数不等时，就应该把小。

指数那一项的节点复制到多项式中；当一个多项式为空，另一个不为空时，应将不为空的那个多项式用新节点产。

生。3)高次多项式减法运算：与高次多项式加法运算相似。

当两个多项式指数相等时，系数相减；当前一个多项式中的某一项指数与后一个中某项指数不等时，就应该把后一个多项式中的那项节点复制到多项式中，同时，前一项也复制到多项式中，并且这一项的相反数作为新建的节点的系数；当前一个多项式空，后一个不空时，将后一个多项式用新节点产生，当后一个空，前一个不空时，则前一个多项式用新节点产生，且其相反数作为新节点的系数。

4)输出函数并提供输入多项式的方法，以及实现加减运算。

2、哈夫曼树应用。

1)构造哈夫曼树：根据给定的权值构成二叉树集合，其中每棵二叉树中只有一个带权的根节点，其左右子树均为空；在二叉树集合中选取两棵根节点权值最小的树作为左右子树构造一棵新的二叉树，且新的二叉树的根节点的权值为其左、右子树上根节点的权值之和；在二叉树集合中删除这两棵树，并将得到的二叉树加入集合中；重复上述步骤，直至二叉树集合中只含一棵树为止。

2)哈夫曼编码：构造出哈夫曼树后，根据函数定义的双亲左孩子为0，右孩子为1，标出从叶子结点到根这条路径上的0或1，逐个字符求编码。

3)求带权路径长度：先求每个叶子结点到树根之间的路径长度与该叶子结点所带权值之积，在将所得之积求和。

四、主要变量、函数介绍。

1.链表应用。

a．#include<>提供输入输出函数。

#include<>提供malloc函数。

int j;定义一个结点结构体。

定义结点结构体lnode,结构体指针变量*next。

b．菜单。void menu()

printf("链表应用！两个高阶多项式的加减运算！请选择运算：0、构建 1、加法 2、减法 3、输出 4、退出");

c幂数从小到大构成多项式。

struct lnode *creat(int c)

int i,d;

struct lnode *head,*p;

head = struct lnode *)malloc(sizeof(struct lnode));为多项式链表分配空间。

head->next = 0;//初始化。

printf("由0次到%d次输入第% d个多项式的每项系数（若无该项则系数为0）："j,c);

for(i = 0;i <=j;i++)构建链表。

return(head);/返回头指针。

d 加减法函数将两个多项式对应系数相加相减。

struct lnode *jia(struct lnode *head1,struct lnode *head2)

int i;

struct lnode *p,*q,*s,*head3;

head3 = struct lnode *)malloc(sizeof(struct lnode));为接收链表分配空间。

head3->next = 0;//初始化。

p = head1;

q = head2;

for(i = 0;i <=j;i++)

return(head3);/返回头指针。

struct lnode *jian(struct lnode *head1,struct lnode *head2)

int i;

struct lnode *p,*q,*s,*head3;

head3 = struct lnode *)malloc(sizeof(struct lnode));

head3->next = 0;

p = head1;

q = head2;

for(i = 0;i <=j;i++)

return(head3);/返回头指针。

f 输出函数分两列输出幂数和系数。

struct lnode *shuchu(struct lnode *head)

int i,d;

struct lnode *p;

p = head->next;

printf("输出幂数\t系数");

for(i = 0;i <=j;i++)

return(head);

e 主函数。

void main()

int k;

struct lnode *a,*b,*c;

menu();调用目录函数。

scanf("%d",&k);/输入选择项。

while(k!=4)

menu();

scanf("%d",&k);

2 赫夫曼树建立。

a 定义。int s1=0,s2=0;//定义两个全局变量。

typedef struct// 定义/结构体。

int c;//字符域。

int w;//权值域。

int p,l,r;/双亲域/左孩子域右孩子域，ht,*huffmantree;//动态分配数组存储赫夫曼树。

typedef char * huffmancode;//动态分配数组存储赫夫曼编码。

ht *htree;

b 找出两个最小权值s1，s2

void select(ht *htree,int b)

int i,j,t;

for(i=1;i<=b;i++)找第一个p为0的结点。

if(!htree[i].p)

for(j=i+1;j<=b;j++)找第二个p为0的结点。

if(!htree[j].p)

for(i=1;i<=b;i++)找第一个w最小的结点。

if((htree[s1].w>htree[i].w)&&htree[i].p)&&s2!=i))

s1=i;for(j=1;j <=b;j++)找第二个w最小的结点。

if((htree[s2].w>htree[j].w)&&htree[j].p)&&s1!=j))

s2=j;if(s1>s2)//令s1小于s2

huffmancode hcode

c 输出状态图。

void pr(ht *htree,int m)

int i;

ht *h;

printf("输出状态图字符\t权值\t双亲\t左孩子\t右孩子");

h=htree+1;

for(i=1;i<=m;i++,h++)

printf("%c\t%d\t%d\t%d\t%d",h->c,h->w,h->p,h->l,h->r);

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

其他用户还读了