数据结构课程设计

河海大学计算机与信息学院（常州）

课程设计题目：多项式问题

专业、年级：计算机科学与技术09级。

学号： 0962810226

姓名：王超

目录。一、问题描述3

二、需求分析4

三、概要设计4

1.概要设计目的与要求4

2.概要设计内容4

3.功能算法描述与数据结构说明5

四、详细设计5

五、系统测试8

六、使用说明9

七、总结及心得体会10

多项式问题。

一．问题描述。

给你九个整数，这九个整数分别是x的8次方至0次方的系数，请你按照多项式的一半形式合理地构造（去除不必要的）。例如九个系数分别是为0,0，0,1,22，-333,0,1，-1，你要构造并输出一行多项式：x^5 + 22x^4 – 333x^3 + x – 1。

它的格式规则如下：

1.多项式的项必须按其指数从高到低排列。

2.指数必须跟在符号“^”后显示。

3.有常数的只显示常数项（无需跟x^0）。

4.只显示系数不为0的项；若系数全为0，需显示常数项。

5.在多项式中唯一需要空格的地方是项与项之间的加号或减号的两边需加上空格。

6.如果首项的系数是正数，则系数前不加符号；如果首项的系数是负数，则符号与数字之间不加空格，就如：-3x^2 + 2x。

7.系数为1，指数为0时，系数的1才显示（推广到系数为-1）。

输入/输出说明。

1.输入/输出方式为文件方式，输入文件有一行或多行的系数，系数之间有空格分隔。

2.每行共有九个系数，每个系数的绝对值为小于1000的整数。输出文件包含构造完地多项式，每行一个多项式。输入范例。

输出范例。x^5 + 22x^4 – 333x^3 + x – 1

55x^2 + 5x

二．需求分析。

2.1可行性研究。

该程序主要从技术的角度来分析可行性。技术上的可行性研究主要分析技术条件能否顺利完成开发工作，硬、软件能否满足开发者的需要等。该系统采用了windows 7操作系统结合visual c++ 6.

0等软件开发平台已成熟可行。硬件方面，科技飞速发展的今天，硬件更新的速度越来越快，容量越来越大，可靠性越来越高，其硬件平台也比较能满足此系统的需要。

2.2结构与主要功能模块。

从实现多项式输出过程的角度来分析，至少需要这样一些子功能模块。如：

1. 多项式创建功能；

2. 多项式输出功能；

3. 释放多项式功能；

4. 操作界面显示功能；

三．概要设计。

1.概要设计目的与要求。

通过多项式程序设计，使我们进一步掌握和利用c++语言进行结构化程序设计的能力；进一步理解和运用结构化程设计的思想和方法；初步掌握开发一个小型系统程序设计的基本方法；学会调试一个较长程序的基本方法；以及掌握书写课程设计开发文档的能力（书写课程设计报告）。总之，通过本课程设计加深对《c++语言》及《数据结构》课程所学知识的理解，进一步巩固c++语言语法规则，在程序中体现出算法的思想，提高程序的运行效率。学会编制结构清晰、风格良好、数据结构适当的c++语言程序，从而具备解决综合性实际问题的能力。

2.概要设计内容。

多项式输出程序具有以下基本功能：

1．创建多项式。接收输入的数据，并保存到链表中。

2．txt文档输入输出功能。

3．清除内存内容，释放创建的链表，退出程序。

3.功能算法描述与数据结构说明。

该多项式程序除了main()函数外，主要有以下函数：

node *createpolyn()

void firstnode(node *p)

void othernode(node *p)

void printpolyn(node *pa)

void deletechain(node *h)

下面对这些函数逐一介绍。

.main（）函数。

main函数主要调用其他函数，用来实现输入、显示功能。

在main（）函数中，定义一维数组p用来保存多项式的系数，pa定义程序所需链表的头指针。在程序开始要求输入多项式的系数，随后创建链表以保存多项式，再显示出构建的符合要求的多项式。

.node *createpolyn()

该函数功能是创建新的多项式链表。使用for语句，控制输入多项式的每一项。

.void firstnode(node *p)

该函数功能是判断输出多项式第一项。对于第一项的系数为1或-1，指数为0或-1等五种情况进行讨论。

.void othernode(node *p)

该函数功能是判断输出多项式除第一项外的其它项。对于第一项的系数为1或-1，指数为0或-1等五种情况进行讨论。

.void printpolyn(node *pa)

该函数功能：显示构造的符合要求的多项式链表。在该函数中调用③、④函数，进行多项式的输出。

.void deletechain(node *h)

该函数的功能是释放掉创建的链表，释放内存。

四．详细设计。

下面讨论重要函数具体实现过程：

1. node *createpolyn() 定义int i=9计数，当i>0时，for语句反复提示用户输入该多项式的每一项的指数。当i=1时，输入完毕，该链表也创建完毕。

详细的实现过程如下：

node *createpolyn()

node *head,*pa,*s;

int i;

pa=head=new node;//创建一个新的结点。

head->next=null;

for (i = 9; i >0;i--)依次输入9项

return head;

2. void firstnode(node *p) 对多项式第一项输出可能性进行多种分类讨论。

void firstnode(node *p)//输出多项式第一个结点。

/指数不为1且不为0,系数绝对值不为1（正常的输出）

if(p->exp!=1&&p->exp&&fabs(p->coef)!=1) else

if(p->exp==0)//指数为0，即常数项。else

//指数大于0且不为1，系数绝对值为1

if(p->exp>0&&fabs(p->coef)==1&&p->exp!=1)

if(p->coef>0)

elseif(p->exp==1&&fabs(p->coef)!=1)//指数为1且系数绝对值不为1

if(p->coef>0&&p->coef!=1)

if(p->coef<0&&p->coef!=-1)

if(p->exp==1&&fabs(p->coef)==1)//指数为1且系数绝对值为1

if(p->coef==1)

outfile<<"x";

elseoutfile<<"x";

3. void printpolyn(node *pa) 该函数有一个参数，该指针指向多项式链表的头指针，以下是实现插入的关键**：

void printpolyn(node *pa)

node *p;

if(pa->next==null首项判断，如果首项无，则显示“0”

outfile<<"0";

return;

elsep=pa->next->next定义指针p指向pa的下下个指针。

while(p!=null)

outfile<}

五．系统测试。

该程序在vc6.0中调试通过，没有错误和警告，运行结果经过检验为正确。以下图为该程序运行结果效果图：

图5-1 范例。

图5-2 一行输出。

图5-3 多行输出。

六．使用说明。

1．打开文件，在里面任意输入9个整数，每个数字间要有空格，可以输入一行或者多行，输入多行的时候需要换行。

2.编译运行后，打开文件，即可看到输出的符合要求的多项式。

七．总结及心得体会。

通过这次课程设计练习，使我更深刻地理解了c++语言的精髓---指针的使用。完成整个程序设计有很大的收获，对指针掌握的更加熟练。

同时通过直接对单链表的操作，加深了对数据结构的理解和认识。并在完成课程设计的过程作主动查阅了相关资料，学到了不少课本上没有的技术知识。

经过这次课程设计，我深刻认识到算法在程序设计中的重要性，如何让程序简单、易读是这个课程设计的难点。程序总是由若干个函数构成的，这些相应的函数体现了算法的基本思想。

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了