从小白到大牛：IT人的日常代码苦练心得

从小白到大牛：IT人的日常代码苦练心得

日常代码苦练

名称：一元稀疏多项式计算器

一、问题描述：

设计一个一元稀疏多项式的简单计算器，要求能进行加减运算，

**问题输入：**每组数据有3行构成，第1行为3个正整数n，m，t， n表示第一个多项式的项数，m表示第二个多项式的项数，t表示运算类型，0为加法，1为减法，每组数据的第 2 行包含2n个整数，每两个整数分别表示第一个多项式每一项的系数和指数；第3行包含2m个整数，每两个整数分别表示第二个多项式每一项的系数和指数。输入每一项按 指数从低到高的顺序排列。

**问题输出：**在一行上以多项式形式输出结果，指数按从低到高的顺序

示例：

输入：

6 3 0

1 0 1 1 -3 2 1 3 1 4 1 5

-1 3 -2 4 1 5

输出：（注意正负号以及 “1” ）

1+x-3x2-x4+2x^5

二、问题解决分析:

1. 选择存储结构为链表:

   1. 灵活性：链表可以动态地分配内存空间，可以根据实际需要动态地插入、删除节点，而不需要提前知道多项式的项数。这对于稀疏多项式来说是非常有用的，因为它们通常只有少量非零项。
   2. 节省空间：对于稀疏多项式来说，大部分项的系数为0，使用链表可以只存储非零项，节省了存储空间。
   3. 方便的插入和删除：链表结构可以方便地进行节点的插入和删除操作，这对于多项式的加法、减法等操作是非常有利的。
   4. 易于实现：链表的操作相对简单，易于实现，可以快速地编写出多项式的创建、加法、减法等操作

2. 设计思想：

   我们从头到尾处理两个多项式的每一项。如果两项中，多项式a的项的指数小于多项式b的项的指数，那么将a的此项直接作为多项式c的一项。如果多项式a的指数等于多项式b的指数，将两项合并作为多项式c的一项。如果多项式a的指数大于多项式b的指数，那么将b的此项直接作为多项式c的一项。因为多项式a和多项b的都是按照指数升序建立的，因此，指数小的项会被先计算出来，使用尾插法插入多项式c中，这样多项式c也是按照指数升序排列的。而减法就是将a-b改为a+(-b)。我们将b的每一项系数都取相反数，最后按照加法计算。

3. 输出要点（此处费劲了我半天！！！）：

   1. 首先，检查多项式链表是否为空。如果链表为空，表示多项式为零多项式，直接输出"0"即可。
   2. 在遍历多项式链表时，需要考虑每一项的系数和指数。
   3. 对于系数为零的项，可以直接跳过不进行输出。
   4. 对于系数不为零的项，需要根据系数和指数的情况进行输出。
   5. 如果系数为正数，并且不是第一项，则在输出前需要添加一个加号"+"。
   6. 对于系数不为1或-1的项，需要输出系数的绝对值，并根据指数的情况输出对应的代数表达式，如"x"或"x^exp"。
   7. 对于系数为1的项，需要根据指数的情况输出对应的代数表达式，如"1"、“x"或"x^exp”。
   8. 对于系数为-1的项，需要根据指数的情况输出对应的代数表达式，如"-1"、“-x"或”-x^exp"。
   9. 在输出每一项后，需要将指针指向下一个节点，继续遍历链表。
   10. 最后，输出换行符"\n"，以确保多项式输出后换行。

三、代码展示说明：

1. 定义结构体：定义一个结构体来存储多项式的系数和指数，以及下一个节点指针

   // 定义了一个结构体 Node，用于表示多项式的每一项
   typedef struct node {
       int coef;  // 系数
       int exp;   // 指数
       struct node *next;  // 指向下一项的指针
   } Node;
   

2. 自定义初始化链表函数

   // 创建一个多项式链表，输入参数 n 表示多项式的项数
   Node *Create(int n) {
       int coef;  // 系数
       int exp;   // 指数
       Node *p, *q, *head;  // 定义指针变量 p, q, head
   
       head = NULL;  // 初始化头指针为 NULL
       q = NULL;     // 初始化辅助指针 q 为 NULL
   
       int i=0;
   
       for(i = 0; i < n; i++) {
           scanf("%d %d", &coef, &exp);  // 从输入中读取系数和指数
           p = (Node *) malloc(sizeof(Node));  // 分配内存空间给新节点 p
           p->coef = coef;  // 将系数赋值给新节点的 coef 成员
           p->exp = exp;    // 将指数赋值给新节点的 exp 成员
           p->next = NULL;  // 将新节点的 next 指针初始化为 NULL
   
           if(head == NULL) {
               head = p;  // 如果头指针为空，将头指针指向新节点
           } else {
               q->next = p;  // 否则将辅助指针 q 的下一项指针指向新节点
           }
           q = p;  // 将辅助指针 q 指向新节点，准备处理下一个节点
       }
       if (q != NULL) q->next = NULL;  // 确保最后一个节点的 next 指针为 NULL
   
       return head;  // 返回多项式的头指针
   }
   

3. 输出函数构造

   输出：按给定格式输出一元多项式；（例如：3*x^20-x7+10）

   分析：我们要解决的有三个问题，系数为1，-1，其它；指数为1，0，其它；符号显示

   // 输出多项式链表的内容
   void Output(Node *head){
       Node *q;  // 定义一个指针变量 q
       q = head;  // 将指针 q 指向多项式的头节点
       int flag = 0;  // 用于记录是否为第一项
   
       if (!q) {
           printf("0");  // 如果多项式为空，直接输出"0"，表示零多项式
           return;
       }
   
       if(q->next != NULL && q->coef == 0) {
           q = q->next;  // 如果第一项的系数为0，则跳过第一项
       }
   
       while(q) {
           if(q->coef > 0 && flag == 1) {
               printf("+");  // 如果系数为正数且不是第一项，则输出加号
           }
           flag = 1;  // 将 flag 置为 1，表示已经输出了第一项
   
           if(q->coef != 1 && q->coef != -1) {
               printf("%d", q->coef);  // 输出系数的绝对值
   
               if(q->exp == 1) {
                   printf("x");  // 如果指数为1，则输出"x"
               } else if(q->exp != 0) {
                   printf("x^%d", q->exp);  // 如果指数不为0，则输出"x^exp"
               }
           } else {
               if(q->coef == 1) {
                   if(q->exp == 0) {
                       printf("1");  // 如果系数为1且指数为0，则输出"1"
                   } else if(q->exp == 1) {
                       printf("x");  // 如果系数为1且指数为1，则输出"x"
                   } else {
                       printf("x^%d", q->exp);  // 如果系数为1且指数不为0或1，则输出"x^exp"
                   }
               }
               if(q->coef == -1) {
                   if(q->exp == 0) {
                       printf("-1");  // 如果系数为-1且指数为0，则输出"-1"
                   } else if(q->exp == 1) {
                       printf("-x");  // 如果系数为-1且指数为1，则输出"-x"
                   } else {
                       printf("-x^%d", q->exp);  // 如果系数为-1且指数不为0或1，则输出"-x^exp"
                   }
               }
           } 
           q = q->next;  // 将指针 q 指向下一个节点
       }
       printf("\n");  // 输出换行符，表示多项式输出结束
   }
   

4. 链表的加法运算

   这段代码实现了一个名为 NodeAdd 的函数，其功能是将两个多项式链表相加，并返回相加后的结果链表。函数接受两个参数，分别是指向两个多项式链表头节点的指针 pa 和 pb。

   函数首先初始化了三个指针变量 pc、a 和 b，分别用于指向结果链表的头节点、新节点和最后一个节点。然后通过循环遍历两个多项式链表，根据指数的大小关系逐项进行相加操作。

   在循环中，如果当前节点的指数小于另一个链表的当前节点指数，则将当前节点的系数和指数赋值给新节点 a，并将新节点插入到结果链表中。如果当前节点的指数大于另一个链表的当前节点指数，则同样将当前节点的系数和指数赋值给新节点 a，并将新节点插入到结果链表中。如果两个节点的指数相等，则将它们的系数相加，如果结果系数为0，则直接跳过当前循环；否则将相加后的系数和指数赋值给新节点 a，并将新节点插入到结果链表中。

   接着，函数处理了两个多项式链表长度不一致的情况，将剩余的节点依次插入到结果链表中。

   最后，函数确保了结果链表的最后一个节点的 next 指针为 NULL，并返回了相加后的结果链表的头指针。

   // 将两个多项式相加，返回相加后的结果链表
   Node *NodeAdd(Node *pa, Node *pb) {
       Node *pc, *a, *b;
       pc = NULL;  // 初始化结果链表的头指针为 NULL
       a = NULL;   // 初始化辅助指针 a 为 NULL
       b = NULL;   // 初始化辅助指针 b 为 NULL
   
       while(pa != NULL && pb != NULL) {
           if(pa->exp < pb->exp) {
               a = (Node *) malloc(sizeof(Node));
               a->coef = pa->coef;
               a->exp = pa->exp;
               if(pc == NULL) {
                   pc = a;  // 如果结果链表为空，将头指针指向新节点
               } else {
                   b->next = a;  // 否则将辅助指针 b 的下一项指针指向新节点
               }
               b = a;  // 将辅助指针 b 指向新节点，准备处理下一个节点
   
               ​        pa = pa->next;  // 移动指针 pa 指向下一个节点
               ​    } else if(pb->exp < pa->exp) {
               ​        a = (Node *) malloc(sizeof(Node));
               ​        a->coef = pb->coef;
               ​        a->exp = pb->exp;
               ​        if(pc == NULL) {
                   ​            pc = a;  // 如果结果链表为空，将头指针指向新节点
                   ​        } else {
                   ​            b->next = a;  // 否则将辅助指针 b 的下一项指针指向新节点
                   ​        }
               ​        b = a;  // 将辅助指针 b 指向新节点，准备处理下一个节点
   
               ​        pb = pb->next;  // 移动指针 pb 指向下一个节点
               ​    } else {
               ​        if(pa->coef + pb->coef == 0) {
                   ​            pa = pa->next;
                   ​            pb = pb->next;
                   ​            continue;  // 如果两项系数相加为0，则直接跳过当前循环
                   ​        }
               ​        a = (Node *) malloc(sizeof(Node));
               ​        a->coef = pa->coef + pb->coef;
               ​        a->exp = pa->exp;
               ​        if(pc == NULL) {
                   ​            pc = a;  // 如果结果链表为空，将头指针指向新节点
                   ​        } else {
                   ​            b->next = a;  // 否则将辅助指针 b 的下一项指针指向新节点
                   ​        }
               ​        b = a;  // 将辅助指针 b 指向新节点，准备处理下一个节点
   
               ​        pa = pa->next;  // 移动指针 pa 指向下一个节点
               ​        pb = pb->next;  // 移动指针 pb 指向下一个节点
               ​    }
       }
   
       while(pb != NULL) {
           a = (Node *) malloc(sizeof(Node));
           a->coef = pb->coef;
           a->exp = pb->exp;
           if(pc == NULL) {
               pc = a;  // 如果结果链表为空，将头指针指向新节点
           } else {
               b->next = a;  // 否则将辅助指针 b 的下一项指针指向新节点
           }
           b = a;  // 将辅助指针 b 指向新节点，准备处理下一个节点
   
           ​    pb = pb->next;  // 移动指针 pb 指向下一个节点
       }
   
       while(pa != NULL) {
           a = (Node *) malloc(sizeof(Node));
           a->coef = pa->coef;
           a->exp = pa->exp;
           if(pc == NULL) {
               pc = a;  // 如果结果链表为空，将头指针指向新节点
           } else {
               b->next = a;  // 否则将辅助指针 b 的下一项指针指向新节点
           }
           b = a;  // 将辅助指针 b 指向新节点，准备处理下一个节点
   
           ​    pa = pa->next;  // 移动指针 pa 指向下一个节点
       }
   
       if(b != NULL) {
           b->next = NULL;  // 确保最后一个节点的 next 指针为 NULL
       }
       return pc;  // 返回相加后的结果链表的头指针
   }
   

5. 链表数值倒转相反数，完成减法

   这段代码实现了一个名为 Reverse 的函数，其功能是将多项式链表中的每一项系数取反（乘以-1）。

   函数接受一个指向多项式链表头节点的指针 head。首先，定义了一个指针变量 p，并将其指向链表的头节点。然后通过循环遍历链表中的每一项，将当前节点的系数乘以-1，即取反。最后移动指针 p 指向下一个节点，直到遍历完整个链表。

   这样的操作可以实现对多项式的系数取反，即改变多项式的符号，例如将多项式从正号变为负号，或者从负号变为正号。

   // 将多项式链表中的每一项系数取反（乘以-1）
   void Reverse(Node *head) {
       Node *p;  // 定义一个指针变量 p
       p = head;  // 将 p 指向链表的头节点
       while(p) {  // 循环遍历链表中的每一项
           p->coef *= -1;  // 将当前节点的系数乘以-1，即取反
           p = p->next;  // 移动指针 p 指向下一个节点
       }
   }
   

6. 主函数设计

   这段代码是一个 C 语言程序的主函数。它首先从标准输入中读取三个整数值 n、m 和 t，分别代表两个多项式的项数、另一个多项式的项数以及一个操作类型。然后，它创建了三个指针变量 node1、node2 和 node3，用于存储两个多项式的头节点以及它们的相加结果。

   接下来，根据输入的操作类型 t 的值，程序有两种可能的操作：

   1. 如果 t 的值为 0，表示需要对两个多项式进行相加。程序调用 Create 函数创建两个多项式链表，然后调用 NodeAdd 函数将这两个多项式相加，将结果存储在 node3 中。
   2. 如果 t 的值为 1，表示需要对第二个多项式的系数进行取反操作。程序同样调用 Create 函数创建两个多项式链表，然后调用 Reverse 函数对第二个多项式的系数进行取反，接着调用 NodeAdd 函数将两个多项式相加，将结果存储在 node3 中。

   int main()
   {
       int n, m, t;  // 定义整型变量 n, m, t，用于存储输入的值
       scanf("%d %d %d", &n, &m, &t);  // 从标准输入中读取 n, m, t 的值
   
       Node *node1, *node2, *node3;  // 定义指向多项式链表头节点的指针变量
   
       node1 = Create(n);  // 调用 Create 函数创建第一个多项式链表
       node2 = Create(m);  // 调用 Create 函数创建第二个多项式链表
   
       if (t == 0) {
           node3 = NodeAdd(node1, node2);  // 如果 t 的值为 0，调用 NodeAdd 函数将两个多项式相加
       } else if (t == 1) {
           Reverse(node2);  // 如果 t 的值为 1，调用 Reverse 函数将第二个多项式的系数取反
           node3 = NodeAdd(node1, node2);  // 然后调用 NodeAdd 函数将两个多项式相加
       }
   
       Output(node3);  // 调用 Output 函数输出相加后的多项式链表
   
       return 0;  // 返回 0，表示程序正常结束
   }