数据结构上机课的一次作业： 实现多项式的加法。开始并没有立刻做出来，主要原因是用insert插入的时候的i值没有把握好，以及当值两个链表中的指数相等的时候的处理没有到位。后来经过一番修改后，功能都得以实现。

当天晚上学习了一下怎么放图片博客，终于万事俱备，开始写博客啦 

#include <iostream>

using namespace std;
typedef int datatype;
typedef int index;
typedef struct node* pointer;
struct node {
	datatype data;
	index ind;
	pointer next;
};
typedef pointer lklist;

lklist init() {
	pointer head;
	head = new node;
	head->next = NULL;
	return head;
}

lklist create(lklist head) {
	pointer rear, s;
	int a,b;
	rear = head;
	while (cin >> a >> b && (a != -1 && b != -1)) {
		s = new node;
		s->data = a;
		s->ind = b;
		rear->next = s;
		rear = s;
	}
	rear->next = NULL;
	return head;
}

void print(lklist head) {
	pointer p;
	int j = 0;
	p = head->next;
	while (p != NULL) {
		if (j == 0) {
			if (p->ind == 0) {
				cout << p->data;
			}
			else if(p->data==1){
				cout << "x^" << p->ind;
			}
			else {
				cout << p->data << "x^" << p->ind;
			}
		}
		else {
			
			if (p->ind == 0) {
				cout << "+"<<p->data ;
			}
			else if (p->data == 1) {
				cout <<"+"<< "x^" << p->ind;
			}
			else {
				cout << "+" << p->data << "x^" << p->ind;
			}
		}
		j++;
		p = p->next;
	}
	cout << endl;
}

int locate(lklist head,index y) {
	int j;
	pointer p;
	j = 0;
	p = head->next;
	while (p != NULL) {
		j++;
		if (p->ind== y)break;
		p = p->next;
	}
	if (p != NULL)return j;
	else return -1;
}

pointer get(lklist head, int i) {
	int j;
	pointer p;
	if (i == 0)return head;
	if (i < 0)return NULL;
	j = 0;
	p = head->next;
	while (p != NULL) {
		j++;
		if (j == i)break;
		p = p->next;
	}
	return p;
}



int insert(lklist head, datatype x, index y, int i) {
	pointer q, s;
	q = get(head, i - 1);
	if (q == NULL) {
		cout << "非法插入位置!\n";
		return 0;
	}
	s = new node;
	s->data = x;
	s->ind = y;
	s->next = q->next;
	q->next = s;
	return 1;
}

int length(lklist head) {
	int j;
	pointer p;
	j = 0;
	p = head->next;
	while (p != NULL) {
		j++;
		p = p->next;
	}
	return j;
}

void merge(lklist head1, lklist head2) {//合并两个链表
	pointer p, q,s;
	p = head1->next;
	q = head2->next;
	while (q != NULL) {
		if (p->ind == q->ind) {//指数相等的时候
			p->data += q->data;
			if (p->next != NULL) {
				p = p->next;
			}
		}
		else if (p->ind < q->ind) {
			if (p->next == NULL) {
				insert(head1, q->data, q->ind, length(head1)+1);
			}
			else {
				p = p->next;
			}
		}
		else if(p->ind > q->ind){
			insert(head1, q->data, q->ind, length(head1));
		}
		q = q->next;
	}
}

int  main() {
	lklist p,q;
	p = init();
	p = create(p);
	q = init();
	q = create(q);
	merge(p, q);
	print(p);
	return 0;
}