实验二 链表的实现和应用

实验目的：

  掌握线性表的链式存储结构设计与基本操作的实现。

实验内容与要求：

  ⑴定义线性表的链式存储表示；

  ⑵基于所设计的存储结构实现线性表的基本操作；

  ⑷线性表的应用：①设线性表L1和L2分别代表集合A和B，试设计算法求A和B的并集C，并用线性表L3代表集合C；  ⑸设计一个一元多项式计算器，要求能够：①输入并建立多项式；②输出多项式；③执行两个多项式相加；④（选做）执行两个多项式相乘。

#include
using namespace std;

class list {
private:
	class node {
	public:
		float coef;		//多项式系数
		int expn;		//多项式指数
		node* next;
	};
	node* head;			//头结点
public:
	//初始化
	list() {
		head = new node;
		head->coef = 0;
		head->expn = 0;
	}

	//创建
	void create(int n) {
		node* p = head; node* q = NULL;
		for (int i = 0; i < n; i++) {
			q = new node;
			cin >> q->coef >> q->expn;
			q->next = NULL;
			p->next = q;
			p = q;
		} 
	}

	//取值,取第i个元素的系数和指数
	void get(int i,float &e1,int &e2) {
		node* p = head;
		for (int j = 0; j < i; j++) {
			p = p->next;
		}
		e1 = p->coef;
		e2 = p->expn;
	}

	//插入,前插
	void insert(int i, float e1, int e2) {
		node* p = head; node* q = NULL;
		for (int j = 0; j < i-1; j++) {
			p = p->next;
		}
		q = new node;
		q->coef = e1; q->expn = e2;
		q->next = p->next;
		p->next = q;
	}

	//删除，删除第i个节点
	void remove(int i) {
		node* p = head;
		for (int j = 0; j < i - 1; j++) {
			p = p->next;
		}
		p->next = p->next->next;
	}

	//遍历，以多项式形式输出
	void print() {
		node* ptr = head->next;
		cout << "F(x) = ";
		if (ptr->coef == 0);
		else if (ptr->expn == 0) {
			cout << ptr->coef;
		}
		else if (ptr->coef == 1 || ptr->coef == -1) {
			if (ptr->coef < 0)cout << "-";
			cout << "X^" << ptr->expn;
		}
		else {
			cout << ptr->coef << "X^" << ptr->expn;
		}
		cout << " ";
		ptr = ptr->next;
		while (ptr != NULL) {
			if (ptr->coef == 0);
			else if (ptr->expn == 0) {
				if (ptr->coef > 0)cout << "+";
				cout << ptr->coef;
			}
			else if (ptr->coef == 1 || ptr->coef == -1) {
				if (ptr->coef > 0)cout << "+";
				if (ptr->coef < 0)cout << "-";
				cout << "X^" << ptr->expn;
			}
			else {
				if (ptr->coef > 0)cout << "+";
				cout << ptr->coef << "X^" << ptr->expn;
			}
			cout << " ";
			ptr = ptr->next;
		}
	}

	//合并
	void merge(list L1, list L2) {
		node* ptr = L1.head->next;
		node* p = this->head; node* q = NULL;
		while (ptr != NULL) {
			q = new node;
			q->coef = ptr->coef; q->expn = ptr->expn;
			q->next = NULL;
			p->next = q;
			p = q;
			ptr = ptr->next;
		}
		ptr = L2.head->next;
		while (ptr != NULL) {
			q = new node;
			q->coef = ptr->coef; q->expn = ptr->expn;
			q->next = NULL;
			p->next = q;
			p = q;
			ptr = ptr->next;
		}
	}

	//排序，将多项式按指数排序
	void sort() {
		node* p = NULL; node* p2 = head->next;
		node* q = NULL;
		//中转介质
		float temp1; int temp2;
		while (p2 != NULL) { 
			p = this->head->next;
			q = p->next;
			while (q!= NULL) {
				if (p->expn > q->expn) {
					//交换指数
					temp2 = p->expn;
					p->expn = q->expn;
					q->expn = temp2;
					//交换系数
					temp1 = p->coef;
					p->coef = q->coef;
					q->coef = temp1;
				}
				p = p->next;
				q = q->next;
			}
			p2 = p2->next;
		
		}
		

	}

	//两个多项式相加，结果集为Lc
	void add(list La,list Lb) {
		node* ha = La.head->next; node* hb = Lb.head->next;
		node* hc = this->head; node* q = NULL;
		while (ha != NULL && hb != NULL) {
			if (ha->expn == hb->expn) {
				q = new node;
				q->expn = ha->expn; q->coef = ha->coef + hb->coef;
				q->next = NULL;
				hc->next = q;
				hc = q;
				ha = ha->next;
				hb = hb->next;
			}
			else if (ha->expn < hb->expn) {
				q = new node;
				q->expn = ha->expn; q->coef = ha->coef;
				q->next = NULL;
				hc->next = q;
				hc = q;
				ha = ha->next;
			}
			else {
				q = new node;
				q->expn = hb->expn; q->coef = hb->coef;
				q->next = NULL;
				hc->next = NULL;
				hc = q;
				hb = hb->next;
			}
		}
		if (ha == NULL&&hb!=NULL) {
			while (hb != NULL) {
				q = new node;
				q->expn = hb->expn; q->coef = hb->coef;
				q->next = NULL;
				hc->next = q;
				hc = q;
				hb = hb->next;
			}
		}
		if (hb == NULL && ha != NULL) {
			while (ha != NULL) {
				q = new node;
				q->expn = ha->expn; q->coef = ha->coef;
				q->next = NULL;
				hc->next = q;
				hc = q;
				ha = ha->next;
			}
		}
	}

	//两个多项式相乘，结果集为Lc
	void multiply(list La, list Lb) {
		node* hc = this->head; 
		node* q = NULL;
		node* ha = La.head->next; node* hb = Lb.head->next;
		//交叉相乘，列出所有项
		while(ha!=NULL) {
			while(hb!=NULL) {
				q = new node;
				q->coef = ha->coef * hb->coef;
				q->expn = ha->expn + hb->expn;
				q->next = NULL;
				hc->next = q;
				hc = q;
				hb = hb->next;
			}
			hb = Lb.head->next;
			ha = ha->next;
		}
		//合并同类项
		node* p = this->head; node* p2=NULL;
		while (p->next!= NULL) {
			p2 = p->next;
			while (p2->next!= NULL) {
				if (p->next->expn == p2->next->expn) {
					p->next->coef =p->next->coef+p2->next->coef;
					p2->next = p2->next->next;	
				}
				else {
					p2 = p2->next;
				}
			}
			p = p->next;
		}
	}
};

void show1() {
	cout << "---链表创建多项式---" << endl;
	cout << "---1.多项式的实现" << endl;
	cout << "---2.多项式的相加和相乘" << endl;
	cout << "---3.退出" << endl;
	cout << endl;
}

void show2() {
	cout << "---1.创建多项式;" << endl;
	cout << "---2.取值;" << endl;
	cout << "---3.插入;" << endl;
	cout << "---4.删除;" << endl;
	cout << "---5.遍历;" << endl;
	cout << "---6.返回上一级;" << endl;
	cout << endl;
}

int main() {
	int m = 1; int n; char ch, ch2;
	list L3;
	while (1) {
		//主界面
		if (m == 1) {
			system("cls");
			show1();
			cin >> n;
			if (n == 1)m = 2;
			if (n == 2)m = 3;
			if (n == 3)break;
		}
		//链表的实现
		if (m == 2) {
			system("cls ");
			show2();
			cin >> n;
			int i; float e1; int e2;
			if (n == 1) {
				cout << "创建多项式项数:";
				cin >> i;
				cout << "依次输入每一项的系数和指数:";
				L3.create(i);
				cout << endl << "创建成功!";
			}
			if (n == 2) {
				cout << "输入取值位置:";
				cin >> i;
				L3.get(i, e1, e2);
				cout << endl << "第" << i << "项的系数为:" << e1 << ",指数为:" << e2;
			}
			if (n == 3) {
				cout << "输入插入位置、插入项的系数和指数(前插):";
				cin >> i >> e1 >> e2;
				L3.insert(i, e1, e2);
				cout << endl << "插入成功!";
			}
			if (n == 4) {
				cout << "输入删除位置:";
				cin >> i;
				L3.remove(i);
				cout << endl << "删除成功!";
			}
			if (n == 5) {
				L3.print();
				cout <> i1;
				cout << "依次输入每一项的系数和指数:";
				L1.create(i1);
				cout  << "创建成功!"<> i2;
				cout << "依次输入每一项的系数和指数:";
				L2.create(i2);
				cout << "创建成功!"<