数据结构实验四 线性表的基本操作及应用

一、 实验目的

1、掌握线性表的逻辑结构

2、熟练掌握线性表的链式存储结构定义及基本操作

3、加深对链式存储数据结构的理解，逐步培养解决实际问题的编程能力

二、 实验要求

1、演示程序运行结果

2、分析调试过程中出现的现象

3、总结单链表基本操作的特点

4、分析算法的时间复杂度

三、实验内容

编写程序，实现一元多项式的创建、求和等基本操作算法。

(1) 根据一元多项式创建单链表。

(2) 实现两个多项式的求和。

(3) 输出求和结果。

#include
#include
#include
using namespace std;
#define ERROR 0
 
typedef struct PNode {
	float coef; //系数
	int expn; //指数
	struct PNode *next;
} PNode, *Polynomial;
string head_1, head_2;
int temp;
char st = 'A';
 
void CreatPolyn(Polynomial &P, int m) //算法2.18 多项式的创建
{
	//输入m项的系数和指数，建立表示一个多项式的有序链表P
	Polynomial q, pre, s;
	int i;
	P = new PNode;
	P->next = NULL; //先建立一个带头结点的单链表
	char filename[20] = { 0 };
	cout << "请输入有关多项式p" << char(st + 32)  << endl;
	++st;
	gets(filename);
	fstream file;
	file.open(filename);
	if (!file) {
		cout << "未找到相关文件，无法打开！" << endl;
		exit(ERROR);
	}
	file >> head_1 >> head_2;
	while (!file.eof())
	{
		s = new PNode; //生成新结点
		file >> s->coef >> s->expn; //输入元素值
		pre = P; //pre用于保存q的前驱，初值为头结点
		q = P->next;
		while (q && q->expn < s->expn) //通过比较指数找到第一个大于输入项指数的项q
		{
			pre = q;
			q = q->next;
		} //while
		s->next = q; //将输入项s插入到q和其前驱结点pre之间
		pre->next = s;
	}//for
	file.close();
} //CreatPolyn
 
void AddPolyn(Polynomial &Pa, Polynomial &Pb) //算法2.19 多项式的相加
{
	//多项式加法：Pa=Pa+Pb，利用两个多项式的结点构成"和多项式"
	Polynomial r, p1, p2, p3;
	float sum;
	p1=Pa->next;  //补充代码
    p2=Pb->next;  //补充代码
//p1和p2初值分别指向Pa和Pb的第一个结点
	p3=Pa;  //补充代码
//p3指向和多项式的当前结点，初值为Pa
	while (p1 && p2) //p1和p2均非空
	{
		if (p1->expn == p2->expn) //指数相等
		{
			sum = p1->coef + p2->coef; //sum保存两项的系数和
			if (sum != 0) //系数和不为0
			{
				p1->coef=sum;//补充代码//修改Pa当前结点p1的系数值为两项系数的和
				p3->next = p1;
				p3 = p1; //将修改后的Pa当前结点p1链在p3之后，p3指向p1
				p1 = p1->next; //p1指向后一项
				r = p2;
				p2 = p2->next;
				delete r; //删除Pb当前结点r
			} else //系数和为0
			{
				r=p1;p1=p1->next;delete r;
 
//删除Pb当前结点p1
				r = p2;
				p2 = p2->next;
				delete r; //删除Pb当前结点p2
			}
		} else if (p1->expn < p2->expn) //Pa当前结点p1的指数值小
		{
			p3->next=p1;  //将p1链在p3之后
			p3=p1;     //p3指向p1
			p1=p1->next;     //p1指向后一项
		} else //Pa当前结点p2的指数值小
		{
			p3->next = p2; //将p2链在p3之后
			p3 = p2; //p3指向p2
			p2 = p2->next; //p2指向后一项
		}
	} //while
	p3->next = p1 ? p1 : p2; //插入非空多项式的剩余段
	delete Pb; //释放Pb的头结点
} //AddPolyn
 
 
int main() {
	Polynomial Pa, Pb;
	Polynomial p;
	int i;
 
	//创建多项式Pa
	CreatPolyn(Pa, temp); //调用函数，输入Pa每一项的系数和指数
 
	//创建多项式Pb
	CreatPolyn(Pb, temp); //调用函数，输入Pa每一项的系数和指数
 
	AddPolyn(Pa, Pb);
	cout << "多项式Pa和Pb相加后的结果是：\n";
	p = Pa->next;
	i = 0;
	while (p) //输出相加后的结果，每一项以x^n表示
	{
		if (i)
			cout << " + ";
		cout << "(" << p->coef << ") * x^" << p->expn;
		p = p->next;
		i = 1;
	}
	cout << endl;
	return 0;
}

程序运行需要创建两个文本文档PolyA和PolyB，例如：