试题名称 多项式加减法
时间限制: 1 秒
内存限制: 10000KB
问题描述
给定两个多项式，求解其和与差。多项式的项数为M，而最高幂次为N。（1<=M<=10，1<=N<=1000000）
输入说明
输入包含了两个多项式，分为两行给出（同行数据间以空格隔开）：
每一行为两组数据：第一组为一个值，表示多项式的非零项数M；第二组为2*M个值，每相邻两个值表达一个多项式的非零系数项，分别为系数值、幂次值（其中各项按照幂次的降序排列）。但如果多项式没有非零系数项，则仅用0（M的值）表示，后面没有系数和幂次值出现。例如，第一行的数据为：4 1 10 2 5 3 4 4 0，那么表示多项式有4项，对应的多项式为：x^10+2x^5+3x^4+4. 又例如，第二行的数据为：4 1 8 -2 5 3 3 4 1，表示多项式有4项，对应的多项式为：x^8-2x^5+3x^3+4x。那么上述两个多项式相加的输出结果应为：6 1 10 1 8 3 4 3 3 4 1 4 0，对应的多项式为：x^10+x^8+3x^4+3x^3+4x+4.第一个多项式减去第二个多项式的输出结果为：7 1 10 -1 8 4 5 3 4 -3 3 -4 1 4 0，对应多项式：x^10-x^8+4x^5+3x^4-3x^3-4x+4.
输出说明
输出包含了两个多项式，分为两行给出（同行数据间以空格隔开）：
第一行是多项式相加的结果，第二行是多项式相减的结果。每一行为两组数据：第一组为一个值，表示多项式的非零项数M；第二组为2*M个值，每相邻两个值表达一个多项式的非零系数项，分别为系数值、幂次值（其中各项按照幂次的降序排列）。但如果多项式没有非零系数项，则仅用0（M的值）表示，后面没有系数和幂次值出现。
输入样例
例1：
4 1 10 2 5 3 4 4 0
4 1 8 -2 5 3 3 4 1
输出样例
例1：
6 1 10 1 8 3 4 3 3 4 1 4 0
7 1 10 -1 8 4 5 3 4 -3 3 -4 1 4 0
提示：
用链表表示多项式
——————————————————————分割线——————————————————————
详细代码
1 #define _CRT_SECURE_NO_WARNINGS 1 2 #include<stdio.h> 3 #include<stdlib.h> 4 5 typedef struct Node{//要先命名结构体 要不然结构体内指针会报错 6 Node* next; 7 int x_up; 8 float x_bottom; 9 }Node;//结点的数据结构 10 11 typedef struct { 12 Node *head; 13 int n; 14 }list;//定义链表的结构体 包含头指针和节点个数n 头指针是结点类型的头指针 15 //注意以上的定义顺序 先有结点再有列表 不然会报错 16 list* creat_list() {//初始化链表 17 list* l = (list*)malloc(sizeof(list));//要为列表分配空间malloc 18 l->head = NULL; 19 l->n = 0; 20 return l; 21 } 22 //初始化结点但素这里的命名不太规范（） 23 Node* creat_Node(float x_b,int x_u) {//将结点的数据类型一一输入最后返回malloc的节点指针 24 Node* new_Node; 25 new_Node = (Node*)malloc(sizeof(Node)); 26 new_Node->x_bottom = x_b; new_Node->x_up = x_u; 27 new_Node->next = NULL; 28 return new_Node; 29 } 30 //尾插结点 分两种情况 链表为空 31 void add_Node(list* l, int x_u, float x_b) {//尾插节点 32 Node* newNode = creat_Node(x_b, x_u); 33 if (l->head == NULL) {//链表为空（头指针为空时） 34 l->head = newNode; 35 } 36 else { 37 Node* tail = l->head; 38 while (tail->next != NULL) 39 { 40 tail = tail->next;//如果不为空就步进，直到找到最后一个结点（next指针为空） 41 } 42 tail->next = newNode;//将尾部结点的next指向新结点 43 } 44 } 45 //加函数 用列表实现功能的函数 46 void add_list(list* A, list* B,list* l) { 47 Node* cur_A, * cur_B; 48 cur_A = A->head; cur_B = B->head;//现在当前结点指针为链表第一个 49 while (1) { 50 if (cur_A == NULL && cur_B == NULL) break; 51 float x_b; int x_u; 52 if (cur_A == NULL) { 53 add_Node(l, cur_B->x_up, cur_B->x_bottom); 54 cur_B = cur_B->next; 55 } 56 else if (cur_B == NULL) { 57 add_Node(l, cur_A->x_up, cur_A->x_bottom); 58 cur_A = cur_A->next; 59 } 60 else { 61 if (cur_A->x_up == cur_B->x_up) {//AB指数相等，系数相加 62 if (cur_A->x_bottom + cur_B->x_bottom != 0) { 63 add_Node(l, cur_A->x_up, cur_A->x_bottom + cur_B->x_bottom); 64 cur_A = cur_A->next; cur_B = cur_B->next; 65 } 66 else { 67 cur_A = cur_A->next; cur_B = cur_B->next; 68 continue; 69 } 70 } 71 else if (cur_A->x_up > cur_B->x_up) {//A项的指数大 72 add_Node(l, cur_A->x_up, cur_A->x_bottom); 73 cur_A = cur_A->next; 74 } 75 else {//B项指数大 76 add_Node(l, cur_B->x_up, cur_B->x_bottom); 77 cur_B = cur_B->next; 78 } 79 } 80 l->n++; 81 } 82 } 83 84 void minus_list(list* A, list* B, list* l) { 85 Node* cur_A, * cur_B; 86 cur_A = A->head; cur_B = B->head;//现在当前结点指针为链表第一个 87 while (1) { 88 if (cur_A == NULL && cur_B == NULL) break;//当现在的指针都为空时，说明所有结点都处理完毕 89 float x_b; int x_u; 90 if (cur_A == NULL) { 91 add_Node(l, cur_B->x_up, (-1) * cur_B->x_bottom); 92 cur_B = cur_B->next; 93 } 94 else if (cur_B == NULL) { 95 add_Node(l, cur_A->x_up, cur_A->x_bottom); 96 cur_A = cur_A->next; 97 } 98 else { 99 if (cur_A->x_up == cur_B->x_up) {//AB指数相等，系数相加 100 if (cur_A->x_bottom - cur_B->x_bottom != 0) {//系数相减为零这项就gg 接着步进 101 add_Node(l, cur_A->x_up, cur_A->x_bottom - cur_B->x_bottom); 102 cur_A = cur_A->next; cur_B = cur_B->next; 103 } 104 else { 105 cur_A = cur_A->next; cur_B = cur_B->next; 106 continue; 107 } 108 } 109 else if (cur_A->x_up > cur_B->x_up) {//A项的指数大 110 add_Node(l, cur_A->x_up, cur_A->x_bottom); 111 cur_A = cur_A->next; 112 } 113 else {//B项指数大 114 add_Node(l, cur_B->x_up, (-1) * cur_B->x_bottom); 115 cur_B = cur_B->next; 116 } 117 } 118 l->n++; 119 } 120 } 121 //打印链表 122 void print_list(Node* head) { 123 Node* node; 124 node = head; 125 while (node!= NULL) { 126 printf("%.0f %d ", node->x_bottom, node->x_up); 127 node = node->next; 128 } 129 printf("\n"); 130 } 131 132 int main() { 133 int n1, n2; 134 float x_b;//底数可能是小数 135 int x_u;//指数为整数 136 list* A, * B, * add, * minus; 137 A = creat_list();//初始化A、B链表 138 B = creat_list();//链表应该初始化（也就是分配空间）后才能使用 要不然编译器会报错 说找不到这块东东 139 add = creat_list(); 140 minus = creat_list(); 141 scanf("%d", &n1); 142 A->n = n1; 143 for (int i = n1; i > 0; i--) { 144 scanf("%f %d", &x_b, &x_u); 145 add_Node(A, x_u, x_b); 146 } 147 scanf("%d", &n2); 148 B->n = n2; 149 for (int i = n2; i > 0; i--) { 150 scanf("%f %d", &x_b, &x_u); 151 add_Node(B, x_u, x_b); 152 } 153 add_list(A, B, add); 154 minus_list(A, B, minus); 155 printf("%d ", add->n); 156 print_list(add->head); 157 printf("%d ", minus->n); 158 print_list(minus->head); 159 return 0; 160 }
盒盒盒 就这样吧