数据结构课程设计

华南师范大学增城学院。

课程设计报告册。

2012 ——2013 学年度第二学期。

计算机院/系网络工程专业 2011 年级 1 班。

课程名称：数据结构课程设计

姓名：苏梓翰

学号： 201106024115

一、程序设计与实现。

1、一元多项式运算。

1）需求分析：

一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。

2）概要设计：

多项式输入输出：

功能：将要进行运算的多项式输入输出。

数据流入：要输入的多项式的系数与指数。

数据流出：合并同类项后的多项式。

程序流程图：多项式输入流程图如下图所示。

测试要点：输入的多项式是否正确，若输入错误则重新输入。

多项式的运算：

功能：将两多项式相加（减）

数据流入：调用输入函数。

数据流出：多项式相加（减）后的结果。

测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算

3）详细设计：

建立一元多项式。

polynlink createpolynlink(polynlink head,int m)

case 0:

case -1:

if(qc->xishu!=0)

else free(qc

return headc;

多项式x1-x2

polynlink subtractpolynlink(polynlink pa,polynlink pb)

pd=addpolynlink(pa,h);

for(p=h->next;p;p=p->next

p->xishu*=-1;

return pd;

4）调试报告：

在调试的过程中，我想到了在现实计算中，系数是可以为小数的，在该程序中，因为系数定义为int即整数类型的，不能完成这种操作，经过查书，只要把系数定义为float即浮点数类型就可以了，但由于老师要求是定义为int，这个程序我改动后运行可以成功，但老师要求的是int的类型，我就没把改动后的程序弄上去。

运行结果：运行一元多项式计算。exe

输入数字1输入数字2

输入数字1数字2数字3以外的字符，得到。

输入数字3，退出。

2、猴子吃桃子问题。

1）需求分析：

猴子每天都吃当前桃子的一半且再多吃一个，假设第一天开始时，即摘的桃子总数有a0只桃子，第一天吃过之后剩下a1只桃子，第二天吃过之后剩下a2只，. 第9天吃过之后剩下a9只，第10天吃过之后剩下a10只，在a0，a1， a2，. a1 0中，只有a10= 1是知道的，现要求a0，

a9= 2 * a1 0+ 1 )

a8= 2 * a9+ 1 )

a1= 2 * a2+ 1 )

a0= 2 * a1+ 1 )

也就是：ai= 2 * ai + 1)，其中i=10,9，8，7，6，..1，0

2）概要设计：

采用数组和递归方法，不管是采用哪种方法、哪种数据结构，其基本语句都是 ai= 2 * ai + 1+1)，其中i=10,9，8，7，6，..1，0

3）详细设计：

采用数组数据结构：构建子函数void array(int a)初始化i=10，从10开始计算，i--，通过语句while(i>0)，来循环运行a[i-1]=2*a[i]+2，以求出每天剩下的桃子数当i<=1时退出循环。在主函数中定义数组int a[11]来存储每天剩下的桃子总数，初始化a[10] =1，通过调用子函数array(a)，并利用for循环来输出每天剩下的桃子总数，其中a[0]即为原来猴群所摘的桃子的总数。

void array(int a)

可知n=2*recursion(n+1)+2语句要调用10+9+……1共55次，桃子原来的总数为： recursion(0)。

int recursion(int n){

if(n==10)

return 1;

elsereturn n=2*recursion(n+1)+2;

4）调试报告：

由于此程序是分模块进行，且每一个模块相对比较简单，所以在做程序的过程中比较顺利，刚开始时，每一个算法我都是单独的一个程序来实现，基本上没有出现问题，在将所有方法、程序做好后，再将所有程序集合在一起，利用主函数的菜单来分块调用以实现题目要求。在整合过程中，出现了一些编辑错误，但是都是比较小的错误，很快就找出来了，应该说整个程序做的过程还是比较顺利的，我在程序要求上增加了一个数字键3，用来退出这个exe程序，由于该程序相对简单，我在排版上也做了比较充足的考虑，并执行，让问题也显示在屏幕上，使得界面比较完整，看起来比较舒服，本来有在主函数里面加入背景颜色的语句system("color 15")，不过感觉不好看，最后还是把这个语句删掉。

运行结果：运行猴子吃桃子。exe

输入数字1，得到。

输入数字2，得到。

输入数字3，得到。

输入数字1数字2数字3以外的字符，得到。

3、哈夫曼编码&译码系统。

1）需求分析。

程序的功能：输入组成编码字母各个叶子的值和权值，建立哈夫曼树并生成哈夫曼编码，且能利用生成的编码对huffman**串进行译码，输出相应结果。

2）概要设计。

主要设想模块示意图如下：

3）详细设计。

哈夫曼树节点的数据类型定义：

struct node

char st1[99];

char st2[99];

float weight;

int parent,lch,rch;

;struct node ht[max];

编码和译码功能：

void creat()

float min1,min2;

int i=0,j=0,min11,min22;

printf(" 输入(编码权值),输入0结束：");

while(1)

printf(" 编码%d,权值%d:",i,i);

j=0;while(1)

scanf("%c",&ht[i].st1[j]);

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了