数据结构课程设计_1210522

数据结构课程设计实习报告题目：用链表实现多项式的基本操作学号：1210522姓名：何厚华年级：大二学院：计算机与控制工程学院专业：计算机科学与技术完成日期：2014年3月22日授课教师：辛运帏目录1.题目 (2)2.要求... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . (2)3.程序实现... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... (2)3.1程序运行及编译环境 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... (2)3.2程序描述 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... (2)3.3实现功能... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . (3)3.3.1子功能模块1 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... (4)3.3.1.1 输入项 .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... (6)3.3.1.2输出项 .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... (6)3.3.1.3数据结构的定义 ... ... ... ... ... ... ... ... ... ... ... ... ... ... (6)3.3.1.3.1全局数据结构.. ... ... ... ... ... ... ... ... ... ... ... ... ... (6)3.3.1.3.2局部数据结构... ... ... ... ... ... ... ... ... ... ... ... ... ... (6)3.3.1.4算法及程序说明... ... ... ... ......... ... ... ... ... ... ... ... ... (7)3.3.1.5接口设计... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... (8)3.3.2子功能模块2 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... . (10)3.4运行结果 .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... .... .... (11)3.5尚未解决的问题 .... ... ... ... ... ... ... ... ... ... ... ... ... ... .... .... .... (12)1.题目利用链表实现多项式的基本操作2.要求链表中，各结点按指数升幂或降幂排列，生成的结果多项式仍使用原多项式所占用的存储空间：两个同类项相加或相减时，如果系数不为0，则修改该结点的系数值，而指数值不变，将该结点链入结果多项式中，而另一项则释放空间；如果系数为0，则这两项占用的空间均需释放。

不同类项则直接放入结果多项式中。

3.程序实现3.1程序运行及编译环境程序是用Visual Studio 2008即VS9.0 编译的。

可以在windows系列的操作系统上运行。

3.2程序描述改程序主要用于多项式的四则运算和微分运算。

其流程如下：A).程序读取输入文件a.逐个字符读取文件inputfile.txt的内容放到字符变量str里面，遇数字字符和字符区别对待。

b.将每个数字作为相应的系数或者指数，组成一个结点c.将结点一个一个地插入到链表类对象myPoly1d.重复以上步骤，得到myPoly2e.读取第三行的操作符，并将其数字化B).控制台输出多项式Poly类里面封装好了多项式的输出函数，用的是重载运算符”<<”的方法，用此方法依次输出myPoly1和myPoly1。

C).多项式运算根据输入文件的操作符，执行相应的运算。

D).在控制台以及文件里依次输出结果。

E).完成3.3实现功能3.3.1子功能模块1fout.open("outfile.txt");//存放输出多项式的文件fin.open("inputfile.txt");//存放输入多项式的文件fin.get(str);//逐个字符读取while(!fin.eof()){judge=0;//judge用来判断当前的这两个node->coef还有node->index是否可以用于插入，//judge=1,时插入if(crlf==1&&str=='\n'){//crlf用来判定出现过回车换行的次数，因为第一行是myPoly1//的数据，第二行是myPoly2，第三行是操作符fin.get(str);switch (str){//对第三行的符号数字化case'+':case'a':case'A':sign=1;break;...........................................c ase .......default:}}if (dot!=0)//dot用来记录小数点到该数字结束部分的位数{dot++;}if(str=='\n'){crlf++;//换行书加1}if((str>'0'||str=='0')&&(str<'9'||str=='9')||str=='-'||str=='.')//对数字，负号还有小数点处理{...................................}if(str==',')//因为”,”总出现在node->coef的后面，此时表示node->coef已经初步生产{while(dot>2)//把小数点的位置考虑进去{num/=10;dot--;}num=(harsh==1)?-num:num;//harsh表示负号的出现情况，harsh=1表明这个是负数node->coef=num;num=dot=0;harsh=judge=0;//harsh置零，此时还没有生成指数，所以judge=0}if(str==')')//因为”)”总出现在node->index的后面，此时表示node->index已经初步生产{while(dot>2){num/=10;dot--;}num=(harsh==1)?-num:num;node->index=num;num=dot=0;judge=1;//judge=1表示指数以及系数均生成，下一个步骤就是插入harsh=0;//harsh置零}if(judge==1&&crlf==0)myPoly1.insert(node);//第一行就插入多项式myPoly1if(judge==1&&crlf==1)myPoly2.insert(node);//第二行就插入多项式myPoly2fin.get(str);}3.3.1.1 输入项输入项有:ofstream fout;//输入流文件char str;//str用于读入字符的存储，可以为任意可打印字符int judge=0;//judge 用于判断从文本读入的node数据是否可以插入链表,//因为那些数是一个一个的取得的//有效值为0,1int harsh=0;//harsh用来判断各个数字前面的是否为负号//harsh有效值为0,1int crlf=0;//crlf用来判定出现过回车换行的次数//有效值为大于0的所有整数int sign=0;//sign用来表示多项式的操作表示没有操作，1,2,3,4,5分别表示加,减,乘,除,微分int dot=0;//dot用来记录小数点的位置double num=0;//临时存放指数以及系数的变量PNode* node=new PNode;//用于插入到链表的一个项3.3.1.2输出项ifstream fin;//输出流文件Poly myPoly1,myPoly2;//从文件输出到这两个多项式对象里面//以类似于10x^0+1x^1-7.7x^2+5x^10+9.3x^31的方式输出3.3.1.3数据结构的定义3.3.1全局数据结构全局数据结构有：链表myPoly1,myPoly2；3.3.2 局部数据结构用于插入链表的PNode* node；3.3.1.4算法及程序说明A).本程序最重要的是这两个模块：1.删除具有某个指数的链表项，这个操作十分重要，因为经常遇到两个项目合在一起后就对消的情况，这还需要把相应的指针项释放掉。

2.把某个项目插入到链表里面。

如果它的次数在原来这个多项式里面出现过，那么就不产生新的结点。

To sum up,这就是把一项加到多项式里面去。

这个模块有多重要看看后面的算法就知道了。

B).各个运算的算法a).加法有了上面那个插入函数，加法就变得非常简单了，因为主要的工作还是它完成的。

把myPoly2的每一项取出来再插进myPoly1里面去。

b).减法有了上面那个加法函数，减法就变得非常简单了把myPoly2的每一项取出来，再把每一项的系数变为其相反数，然后插进插进myPoly1里面去。

c).乘法有了上面那个加法函数，乘法也是非常简单的。

这需要两个循环，依次取出两个多项式的每一项，然后，相应项的系数相乘，指数相加，形成一个结点，插入到一个空链表里面去，最后空链表成长为，两个多项式之积。

把myPoly2的每一项取出来，再把每一项的系数变为其相反数，然后插进插进myPoly1里面去。

d).除法就是以上几个运算的简单综合。

比较被除数以及除数最高次数的项，决定商的最高次项，其中指数为被除数指数减去除数指数，系数，其中系数为被除数系数减去除数系数，依次用被除数减去每一个项与除数的乘积（哈哈，这就叫站在巨人的肩膀上！！），被除数每减一次它的值都会变，因此不用每次减去商与除数的积（不过e).微分运算因为它只需要遍历一遍链表，每一项系数指数昨简单变换即可，而不需要像减法，乘法和除法一样反复调用加法。