DataStructure-链表实现指数非递减一元多项式的求和

  1 // 2-链表实现多项式的求和.cpp : 定义控制台应用程序的入口点。
  2 //
  3 #include "stdafx.h"
  4 #include<stdio.h> 
  5 #include<stdlib.h > //使用malloc的时候使用的头文件 
  6 typedef int ElementType;
  7 typedef struct Node{
  8     ElementType coef;
  9     ElementType exp;
 10     struct Node * Next;
 11 } List;
 12 
 13 List *InitialEmpty(List* PtrL)
 14 {
 15     PtrL->coef = 0;
 16     PtrL->exp = 0;
 17     PtrL->Next = NULL;
 18     return PtrL;
 19 }
 20 void DispList(List* p){
 21     while (p){
 22         printf("%d,%d ", p->coef, p->exp);
 23         p = p->Next;
 24     }
 25     printf("
");
 26 }
 27 List * InsertAsEndNode(ElementType coef, ElementType exp, List*PtrL) {//往PtrL后面插入coef, exp
 28     List *tmp, *pre;
 29     pre = PtrL;//获取首地址 
 30 
 31     while (pre->Next){//找到最后一个节点 
 32         pre = pre->Next;
 33     }
 34     if (pre == NULL)
 35         return NULL;
 36     tmp = (List*)malloc(sizeof(List));//创建一个空间用来存放
 37     tmp->coef = coef;
 38     tmp->exp = exp;
 39     tmp->Next = NULL;
 40     pre->Next = tmp;//将temp插入到pre后面
 41     return PtrL;
 42 }
 43 
 44 void Attach(ElementType coef, ElementType exp, List* PtrL){//在
 45     List *p;
 46     p = (List*)malloc(sizeof(List));
 47     p->coef = coef;
 48     p->exp = exp;
 49     p->Next = NULL;
 50     PtrL->Next = p;
 51     //PtrL = PtrL->Next;
 52 }
 53 //单链表排序程序 从小到大排序 
 54 List * Add_List(List* pa, List* pb){
 55     List *h1,*h2,*p3, *h3;
 56     int exp1, exp2;
 57     ElementType sum;
 58     p3 = (List*)malloc(sizeof(struct Node));
 59     p3->coef = 0;
 60     p3->exp = 0;
 61     h1 = pa;
 62     h2 = pb;
 63     h3 = p3;
 64     while (h1&&h2){
 65         exp1 = h1->exp;
 66         exp2 = h2->exp;
 67         if (exp1<exp2){
 68             Attach(h1->coef,h1->exp,h3);
 69             h1 = h1->Next;
 70             h3 = h3->Next;
 71         }
 72         else if (exp1>exp2){
 73             Attach(h2->coef, h2->exp, h3);
 74             h2 = h2->Next;
 75             h3 = h3->Next;
 76         }
 77         else{
 78             sum = h1->coef + h2->coef;
 79             if (sum != 0){
 80                 Attach(sum, h1->exp, h3);
 81                 h3 = h3->Next;
 82             }
 83             h1 = h1->Next;
 84             h2 = h2->Next;
 85             }
 86     }
 87     //h3 = h3->Next;
 88     for (; h1; h1 = h1->Next)
 89     {
 90         Attach(h1->coef, h1->exp, h3);
 91         h3 = h3->Next;
 92     }
 93     for (; h2; h2 = h2->Next)
 94     {
 95         Attach(h2->coef, h2->exp, h3);
 96         h3 = h3->Next;
 97     }
 98     p3 = p3->Next;
 99     return p3;
100 }
101 
102 
103 
104 int main(){
105     int M, N;
106     ElementType coef, exp;
107     int cnt1 = 0;
108     List *pa = (List*)malloc(sizeof(List));//首先必须要有一个内存空间的 
109     pa = InitialEmpty(pa);//初始化这个头结点 
110     List *pb = (List*)malloc(sizeof(List));//首先必须要有一个内存空间的 
111     pb = InitialEmpty(pb);//初始化这个头结点 
112     List *pc = (List*)malloc(sizeof(List));//首先必须要有一个内存空间的 
113     pc = InitialEmpty(pc);//初始化这个头结点 
114 
115     scanf_s("%d", &M);
116     for (cnt1 = 0; cnt1<M; cnt1++) {
117         scanf_s("%d %d", &coef, &exp);//循环在链表后面插入数
118         InsertAsEndNode(coef, exp, pa);
119         
120     }
121 
122 
123     scanf_s("%d", &N);
124     for (cnt1 = 0; cnt1<N; cnt1++) {
125         scanf_s("%d%d", &coef, &exp);//循环在链表后面插入数
126         InsertAsEndNode(coef, exp, pb);
127         
128     }
129     pc = Add_List(pa, pb);
130     DispList(pc);
131     return 0;
132 }
View Code