// 2-链表实现多项式的求和.cpp : 定义控制台应用程序的入口点。

 //

 #include "stdafx.h"

 #include<stdio.h>

 #include<stdlib.h > //使用malloc的时候使用的头文件

 typedef int ElementType;

 typedef struct Node{

     ElementType coef;

     ElementType exp;

     struct Node * Next;

 } List;

 List *InitialEmpty(List* PtrL)

 {

     PtrL->coef = ;

     PtrL->exp = ;

     PtrL->Next = NULL;

     return PtrL;

 }

 void DispList(List* p){

     while (p){

         printf("%d,%d ", p->coef, p->exp);

         p = p->Next;

     }

     printf("\n");

 }

 List * InsertAsEndNode(ElementType coef, ElementType exp, List*PtrL) {//往PtrL后面插入coef, exp

     List *tmp, *pre;

     pre = PtrL;//获取首地址 

     while (pre->Next){//找到最后一个节点

         pre = pre->Next;

     }

     if (pre == NULL)

         return NULL;

     tmp = (List*)malloc(sizeof(List));//创建一个空间用来存放

     tmp->coef = coef;

     tmp->exp = exp;

     tmp->Next = NULL;

     pre->Next = tmp;//将temp插入到pre后面

     return PtrL;

 }

 void Attach(ElementType coef, ElementType exp, List* PtrL){//在

     List *p;

     p = (List*)malloc(sizeof(List));

     p->coef = coef;

     p->exp = exp;

     p->Next = NULL;

     PtrL->Next = p;

     //PtrL = PtrL->Next;

 }

 //单链表排序程序 从小到大排序

 List * Add_List(List* pa, List* pb){

     List *h1,*h2,*p3, *h3;

     int exp1, exp2;

     ElementType sum;

     p3 = (List*)malloc(sizeof(struct Node));

     p3->coef = ;

     p3->exp = ;

     h1 = pa;

     h2 = pb;

     h3 = p3;

     while (h1&&h2){

         exp1 = h1->exp;

         exp2 = h2->exp;

         if (exp1<exp2){

             Attach(h1->coef,h1->exp,h3);

             h1 = h1->Next;

             h3 = h3->Next;

         }

         else if (exp1>exp2){

             Attach(h2->coef, h2->exp, h3);

             h2 = h2->Next;

             h3 = h3->Next;

         }

         else{

             sum = h1->coef + h2->coef;

             if (sum != ){

                 Attach(sum, h1->exp, h3);

                 h3 = h3->Next;

             }

             h1 = h1->Next;

             h2 = h2->Next;

             }

     }

     //h3 = h3->Next;

     for (; h1; h1 = h1->Next)

     {

         Attach(h1->coef, h1->exp, h3);

         h3 = h3->Next;

     }

     for (; h2; h2 = h2->Next)

     {

         Attach(h2->coef, h2->exp, h3);

         h3 = h3->Next;

     }

     p3 = p3->Next;

     return p3;

 }

 int main(){

     int M, N;

     ElementType coef, exp;

     int cnt1 = ;

     List *pa = (List*)malloc(sizeof(List));//首先必须要有一个内存空间的

     pa = InitialEmpty(pa);//初始化这个头结点

     List *pb = (List*)malloc(sizeof(List));//首先必须要有一个内存空间的

     pb = InitialEmpty(pb);//初始化这个头结点

     List *pc = (List*)malloc(sizeof(List));//首先必须要有一个内存空间的

     pc = InitialEmpty(pc);//初始化这个头结点 

     scanf_s("%d", &M);

     for (cnt1 = ; cnt1<M; cnt1++) {

         scanf_s("%d %d", &coef, &exp);//循环在链表后面插入数

         InsertAsEndNode(coef, exp, pa);

     }

     scanf_s("%d", &N);

     for (cnt1 = ; cnt1<N; cnt1++) {

         scanf_s("%d%d", &coef, &exp);//循环在链表后面插入数

         InsertAsEndNode(coef, exp, pb);

     }

     pc = Add_List(pa, pb);

     DispList(pc);

     return ;

 }