实习一实验报告
1、需求及规格说明
本次实习要求完成一个程序，实现两个多项式的加法。为了练习单链表的操作，要求对两个多项式实现合并同类项。
2、设计
设计思想：每个节点有两个数据：系数和次数，同时含有指向下一个节点的指针。在实现加法的时候要先判断两个节点的次数是否相同，如果相同就让系数相加。如果相加后系数为0，则在输出结果时要避免输出这一项。
设计表示：
主函数main，在其中首先定义两个多项式p1和p2，然后调用input函数来输入多项式，接着调用print函数来输出这两个多项式。然后调用add函数来对p1和p2实现加法，将结果存入链表p。最后调用print函数输出p（结果）。
3、用户手册
输入时每一项按照“系数”+“空格符”+“次数”的格式输入。当整个多项式都输入完毕时，请输入“0”作为结束。
4、调试报告
两个多项式加法的函数add是程序的核心函数。相加时要对同次数的项进行合并，不相同次数的项直接跳过。实现时定义了一个临时的链表，将已经完成的部分存入该链表。最后，当两个链表的加法做完就返回该临时链表。
在相同次数项相加后可能会出现系数为0的情况。为了解决这个问题，我在输出中加了一项判断：在判断指针不是空指针的同时判断节点系数是不是0，如果是0就不再输出。
时间复杂度O(n)。
5、附录
源程序代码
//polynomial.h
struct polynomial
{
double coef; //记录成员(系数和次数，coef：系数，exp：次数）
double exp;
polynomial *next; //记录下一个结构体对象地址
//构造函数初始化私有数据成员
polynomial(double c=0,double e=0, polynomial *N=0)
{
coef=c;
exp=e;
next=N;
}//构造函数结束定义
//定义析构函数
~polynomial() {}
//析构函数结束定义
};//polynomial结构体定义结束
//polynomial.cpp
#include<iostream>
#include"polynomial.h"
using namespace std;
polynomial* input() //输入函数。
{
double coef=0;
double exp=0;
polynomial *p;
int i=1;
while(true)
{
cout<<"第"<<i<<"项"<<endl;
cin>>coef;
if(coef==0)break;
cin>>exp;
if(i==1)
{
p=new polynomial(coef,exp,0);
}
else
{
polynomial* q=p;
polynomial* rear=0;
while(q!=0&&q->exp<=exp)
{
rear=q;
q=q->next;
}
if(rear==0)
{
p=new polynomial(coef,exp,q);
}
else
{
if(rear->exp<exp)
rear->next=new polynomial(coef,exp,q);
else
rear->coef+=coef;
}
}
i++;
}
return p;
}
polynomial* add(polynomial* exp1,polynomial* exp2) //实现两个多项式的加法的函数。
{
if(exp1==0)
return exp2;
else if(exp2==0)
return exp1;
polynomial *p1=exp1;
polynomial *p2=exp2;
polynomial *Result=new polynomial();
polynomial *p3=Result;
while(true)
{
if(p1==0&&p2!=0)
{
p3->coef=p2->coef;
p3->exp=p2->exp;
p2=p2->next;
}
else if(p2==0&&p1!=0)
{
p3->coef=p1->coef;
p3->exp=p1->exp;
p1=p1->next;
}
else if(p1==0&&p2==0)
{
p3=0;
break;
}
else if(p1->exp==p2->exp)
{
p3->coef=p1->coef+p2->coef;
p3->exp=p1->exp;
p1=p1->next;
p2=p2->next;
}
else if(p1->exp<p2->exp)
{
p3->coef=p1->coef;
p3->exp=p1->exp;
p1=p1->next;
}
else if(p1->exp>p2->exp)
{
p3->coef=p2->coef;
p3->exp=p2->exp;
p2=p2->next;
}
if(p1!=0||p2!=0)
{
p3->next=new polynomial();
p3=p3->next;
}
}
return Result;
}
void print(polynomial* n) //输出一个多项式。
{
polynomial* p=n;
polynomial* q=new polynomial();
while(true)
{
q->coef=p->coef;
q->exp=p->exp;
if(p->next!=0)
{
q=new polynomial(0,0,q);
p=p->next;
}
else break;
}
while(q!=0&&q->coef!=0) //节点的系数不为0时才将该节点输出。
{
cout<<" "<<q->coef<<"x^"<<q->exp;
q=q->next;
if(q!=0&&q->coef>0) //系数为正数的时候要先输出一个“+”号。
cout<<"+";
}
cout<<endl;
}
//main.cpp
#include<iostream>
#include"polynomial.h"
using namespace std;
polynomial* add(polynomial*,polynomial*);
void print(polynomial*);
polynomial* input();
void main()
{
cout<<"该程序是为了实现两个多项式的加法"<<endl
<<"请输入第一个式子中的系数以及次数（输入格式：1 2），输入0（只需要输入0，不要输入0 X）结束。"<<endl;
polynomial* p1=input();
cout<<"请输入第二个式子中的系数以及次数（输入格式：1 2），输入0（只需要输入0，不要输入0 X）结束。"<<endl;
polynomial* p2=input();
cout<<endl<<"式子1：";
print(p1);
cout<<"式子2：";
print(p2);
polynomial* p=add(p1,p2);
cout<<"结果： ";
print(p);
}
测试数据：
1.25 7
2.36 5
3.56 3
-4.78 1
0
1.48 8
2.34 5
-2.35 3
4.78 1
0
运行结果
测试结果分析：
很好地实现了两个多项式的加法。
第二篇：数据结构程序实习报告
数据结构程序实习报告
一：约瑟夫环问题
（1）问题描述：
设有编号为1，2，3……n的n个人顺时针方向围坐一圈，每人有一密码（正整数）。开始时给出一报数上限，从编号为1的人开始报数，报m的人出列；以后将出列者的密码作为新的m，从顺时针方向紧挨着他的下一个人开始报数……直至所有人出列。试编一算法，求出出列顺序。
（2）编程思想：
首先人为地输入要参与的人数m，和要求第一次出列的人的序号n。
然后根据输入的m值构造一个单向环链，每一个节点包括序号域（每个人各自的序号），密码域（记录当他出环后下一个出环的人是从他数后面的第几个人，由随机函数random()+1生成，加一的目的是防止生成数为零），链域（链接下各结点）。 然后再主程序总主要通过一个while循环实现功能，流程图如下：
二：迷宫问题
（1） 问题描述：
由0和1构成的n维方阵M表示一个迷宫，其中0表示通路，1表示墙壁。迷宫
入口为(1,1),出口为(n,n)。试编一算法求出从入口点到出口点可沿八个方向前进的一条通路。
（2） 编程思想：
该程序主要由一个递归函数和一个栈来完成任务。首先随机生成一个迷宫，维数由人为给定，然后通过调递归函数和栈来寻找路径，直到找到出口，找的过程中主要在当前节点的四周找，如果找不到任何通路，则返回到生成迷宫的那一步再次生成一个迷宫，直到找到一条通路为止。流程图如下：
三：二叉树问题
（1） 问题描述：
已知一棵二叉树的前序ABDFIGCEHJ，中序序列为BIFDGAEJHC、试设计完成下列任务的一个算法：
?构造此二叉树
?证明构造的正确性（即分别按先序和中序遍历该树，将所得的结果与给出的序列进行比较）
（2） 编程思想:
根据二叉树的先序序列和中序序列的关系，可以逐个确定各个节点的位置， 此程序主要通过递归函数来构造二叉树的二叉链表存储结构，然后输出结果以便校对。具体流程如下：
四：调试技巧
在调试中最大问题就是指针问题，尤其是有时候程序可以执行但是结果不对 在调试过程中主要积累了以下几条经验：
（1） 若遇到调试不通过的情况，不要单看出错的地方，还要仔细检查可能的其他错
误；
（2） 当遇到结果不对时，最好用F7逐步执行，执行一步就看一下结果，以便查处问
题所在；
（3） 如果需要的话可以设一些断点以便随时观察变量的变化情况。
