从小白到大牛: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
二、问题解决分析:
-
选择存储结构为链表:
- 灵活性:链表可以动态地分配内存空间,可以根据实际需要动态地插入、删除节点,而不需要提前知道多项式的项数。这对于稀疏多项式来说是非常有用的,因为它们通常只有少量非零项。
- 节省空间:对于稀疏多项式来说,大部分项的系数为0,使用链表可以只存储非零项,节省了存储空间。
- 方便的插入和删除:链表结构可以方便地进行节点的插入和删除操作,这对于多项式的加法、减法等操作是非常有利的。
- 易于实现:链表的操作相对简单,易于实现,可以快速地编写出多项式的创建、加法、减法等操作
-
设计思想:
我们从头到尾处理两个多项式的每一项。如果两项中,多项式a的项的指数小于多项式b的项的指数,那么将a的此项直接作为多项式c的一项。如果多项式a的指数等于多项式b的指数,将两项合并作为多项式c的一项。如果多项式a的指数大于多项式b的指数,那么将b的此项直接作为多项式c的一项。因为多项式a和多项b的都是按照指数升序建立的,因此,指数小的项会被先计算出来,使用尾插法插入多项式c中,这样多项式c也是按照指数升序排列的。而减法就是将a-b改为a+(-b)。我们将b的每一项系数都取相反数,最后按照加法计算。
-
输出要点(此处费劲了我半天!!!):
- 首先,检查多项式链表是否为空。如果链表为空,表示多项式为零多项式,直接输出"0"即可。
- 在遍历多项式链表时,需要考虑每一项的系数和指数。
- 对于系数为零的项,可以直接跳过不进行输出。
- 对于系数不为零的项,需要根据系数和指数的情况进行输出。
- 如果系数为正数,并且不是第一项,则在输出前需要添加一个加号"+"。
- 对于系数不为1或-1的项,需要输出系数的绝对值,并根据指数的情况输出对应的代数表达式,如"x"或"x^exp"。
- 对于系数为1的项,需要根据指数的情况输出对应的代数表达式,如"1"、“x"或"x^exp”。
- 对于系数为-1的项,需要根据指数的情况输出对应的代数表达式,如"-1"、“-x"或”-x^exp"。
- 在输出每一项后,需要将指针指向下一个节点,继续遍历链表。
- 最后,输出换行符"\n",以确保多项式输出后换行。
三、代码展示说明:
-
定义结构体:定义一个结构体来存储多项式的系数和指数,以及下一个节点指针
// 定义了一个结构体 Node,用于表示多项式的每一项 typedef struct node { int coef; // 系数 int exp; // 指数 struct node *next; // 指向下一项的指针 } Node;
-
自定义初始化链表函数
// 创建一个多项式链表,输入参数 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*x20-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"); // 输出换行符,表示多项式输出结束 }
-
链表的加法运算
这段代码实现了一个名为 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; // 返回相加后的结果链表的头指针 }
-
链表数值倒转相反数,完成减法
这段代码实现了一个名为 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 指向下一个节点 } }
-
主函数设计
这段代码是一个 C 语言程序的主函数。它首先从标准输入中读取三个整数值 n、m 和 t,分别代表两个多项式的项数、另一个多项式的项数以及一个操作类型。然后,它创建了三个指针变量 node1、node2 和 node3,用于存储两个多项式的头节点以及它们的相加结果。
接下来,根据输入的操作类型 t 的值,程序有两种可能的操作:
- 如果 t 的值为 0,表示需要对两个多项式进行相加。程序调用 Create 函数创建两个多项式链表,然后调用 NodeAdd 函数将这两个多项式相加,将结果存储在 node3 中。
- 如果 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,表示程序正常结束 }