简介
此模块为学校数据结构必修课学习内容的记录与分享
全文大体分为一下几个部分
- 前言
- 背景
- 分析（伪代码部分）
- 代码
- 结果
- Points
前言
由于前段时间赶团队培训进度，后面需要对培训内容进行总结，因此以后相当一部分时间在 homework 上面的时间可能会减少，因此先贴出主要思路及要点，后面抽时间进行细节补充与整理
又挖坑了…QAQ
背景
多项式加法是基于链表数据结构的基础实际运用
本例选用一般化的稀疏多项式，考验对特殊特殊情况的处理
实现的基本目标如下：（需求分析）
输入两个稀疏多项式，输出其相加结果
eg：
// 输入：
7 * 10^0 + 3 * 10^1 + 9 * 10^8 + 5 * 10^17
8 * 10^1 + 22 * 10^7 + -9 * 10^8
// 输出：
7 * 10^0 + 11 * 10^1 + 22 * 10^7 + 9 * 10^8 + -9 * 10^10 + 5 * 10^17分析
需要创建结构体储存：
- 系数信息
- 次方信息
- 下一个节点地址
因此大概的结构体内容就出来了：
typedef struct LinkNode {
int coefficient; // 系数
int exponent; // 幂
NodePtr next;
struct LinkNode *next; // 指向下一个节点的指针
}*LinkList,*NodePtr;这里注意一个点：
不能用该结构体的别名在其内部创建变量
因为编译器是自上而下编译代码的，对于这里创建的结构体，编译器首先会自上而下识别结构体的内容，再为其创建别名，如果直接用该结构体的别名在其内部创建变量会报错变量未识别。
指针移动
一图简示：
首先需要确定哪一个链表作为更新的新链表
然后进行一般化的判断：
- 链表尾部是否为空【是则将非空后的节点链接到新链表尾部】
- 节点幂次比较【p大则插入节点、p小则p节点移动】
- 节点合并计算【注意求和后结果为0的特殊情况】
代码
这里先贴上课堂代码，后面进行补充
#include <stdio.h> #include <malloc.h> typedef struct LinkNode{ int coefficient; int exponent; struct LinkNode *next; } *LinkList, *NodePtr; LinkList initLinkList(){ // 分配头节点空间 LinkList tempHeader = (LinkList)malloc(sizeof(struct LinkNode)); // 初始化值 tempHeader->coefficient = 0; tempHeader->exponent = 0; tempHeader->next = NULL; return tempHeader; } // 可视化打印链表数据 void printList(LinkList paraHeader){ NodePtr p = paraHeader->next; while (p != NULL) { printf("%d * x^%d + ", p->coefficient, p->exponent); p = p->next; } printf("\r\n"); } // 可视化打印节点数据 void printNode(NodePtr paraPtr, char paraChar){ if (paraPtr == NULL) { printf("NULL\r\n"); } else { printf("The element of %c is (%d * x^%d)\r\n", paraChar, paraPtr->coefficient, paraPtr->exponent); } } // 插入节点【尾插】 void appendElement(LinkList paraHeader, int paraCoefficient, int paraExponent){ NodePtr p, q; // 创建一个新节点并赋值 // Step 1. Construct a new node. q = (NodePtr)malloc(sizeof(struct LinkNode)); q->coefficient = paraCoefficient; q->exponent = paraExponent; q->next = NULL; // 找到插入的位置 // Step 2. Search to the tail. p = paraHeader; while (p->next != NULL) { p = p->next; } // 添加节点 // Step 3. Now add/link. p->next = q; } // 多项式加法函数 void add(NodePtr paraList1, NodePtr paraList2){ NodePtr p, q, r, s; // 指针准备 // 选取List1作为更新链表 // 指针指向后直接free List2 // Step 1. Search to the position. p = paraList1->next; printNode(p, 'p'); q = paraList2->next; printNode(q, 'q'); r = paraList1; // Previous pointer for inserting. printNode(r, 'r'); free(paraList2); // The second list is destroyed. // 第一个判断条件 - 是否NULL while ((p != NULL) && (q != NULL)) { // 小于部分，p指针++ if (p->exponent < q->exponent) { //Link the current node of the first list. printf("case 1\r\n"); r->next = p; r = p; printNode(r, 'r'); p = p->next; printNode(p, 'p'); } else if ((p->exponent > q->exponent)) { // 大于部分，进行节点的插入 //Link the current node of the second list. printf("case 2\r\n"); r->next = q; r = q; printNode(r, 'r'); q = q->next; printNode(q, 'q'); } else { // 等于部分，进行加法运算 printf("case 3\r\n"); //Change the current node of the first list. p->coefficient = p->coefficient + q->coefficient; printf("The coefficient is: %d.\r\n", p->coefficient); if (p->coefficient == 0) { // 特殊情况进行判断 printf("case 3.1\r\n"); s = p; p = p->next; printNode(p, 'p'); // free(s); } else { printf("case 3.2\r\n"); r = p; printNode(r, 'r'); p = p->next; printNode(p, 'p'); }// Of if s = q; q = q->next; //printf("q is pointing to (%d, %d)\r\n", q->coefficient, q->exponent); free(s); }// Of if printf("p = %p, q = %p\r\n", p, q); } // Of while printf("End of while.\r\n"); if (p == NULL) { r->next = q; } else { r->next = p; } // Of if printf("Addition ends.\r\n"); }// Of add /** * Unit test 1. */ void additionTest1(){ // Step 1. Initialize the first polynomial. LinkList tempList1 = initLinkList(); appendElement(tempList1, 7, 0); appendElement(tempList1, 3, 1); appendElement(tempList1, 9, 8); appendElement(tempList1, 5, 17); printList(tempList1); // Step 2. Initialize the second polynomial. LinkList tempList2 = initLinkList(); appendElement(tempList2, 8, 1); appendElement(tempList2, 22, 7); appendElement(tempList2, -9, 8); printList(tempList2); // Step 3. Add them to the first. add(tempList1, tempList2); printf("The result is: "); printList(tempList1); printf("\r\n"); }// Of additionTest1 /** * Unit test 2. */ void additionTest2(){ // Step 1. Initialize the first polynomial. LinkList tempList1 = initLinkList(); appendElement(tempList1, 7, 0); appendElement(tempList1, 3, 1); appendElement(tempList1, 9, 8); appendElement(tempList1, 5, 17); printList(tempList1); // Step 2. Initialize the second polynomial. LinkList tempList2 = initLinkList(); appendElement(tempList2, 8, 1); appendElement(tempList2, 22, 7); appendElement(tempList2, -9, 10); printList(tempList2); // Step 3. Add them to the first. add(tempList1, tempList2); printf("The result is: "); printList(tempList1); printf("\r\n"); }// Of additionTest2 /** * The entrance. */ int main(){ additionTest1(); additionTest2(); printf("Finish.\r\n"); return 0; }// Of main
结果
7 * 10^0 + 3 * 10^1 + 9 * 10^8 + 5 * 10^17 +
8 * 10^1 + 22 * 10^7 + -9 * 10^8 +
The element of p is (7 * 10^0)
The element of q is (8 * 10^1)
The element of r is (0 * 10^0)
case 1
The element of r is (7 * 10^0)
The element of p is (3 * 10^1)
p = 9977536, q = 9977760
case 3
The coefficient is: 11.
case 3.2
The element of r is (11 * 10^1)
The element of p is (9 * 10^8)
p = 9977592, q = 9967144
case 2
The element of r is (22 * 10^7)
The element of q is (-9 * 10^8)
p = 9977592, q = 9967200
case 3
The coefficient is: 0.
case 3.1
The element of p is (5 * 10^17)
p = 9977648, q = 0
End of while.
Addition ends.
The result is: 7 * 10^0 + 11 * 10^1 + 22 * 10^7 + 5 * 10^17 +
7 * 10^0 + 3 * 10^1 + 9 * 10^8 + 5 * 10^17 +
8 * 10^1 + 22 * 10^7 + -9 * 10^10 +
The element of p is (7 * 10^0)
The element of q is (8 * 10^1)
The element of r is (0 * 10^0)
case 1
The element of r is (7 * 10^0)
The element of p is (3 * 10^1)
p = 9967200, q = 9967424
case 3
The coefficient is: 11.
case 3.2
The element of r is (11 * 10^1)
The element of p is (9 * 10^8)
p = 9967256, q = 9967480
case 2
The element of r is (22 * 10^7)
The element of q is (-9 * 10^10)
p = 9967256, q = 9977816
case 1
The element of r is (9 * 10^8)
The element of p is (5 * 10^17)
p = 9967312, q = 9977816
case 2
The element of r is (-9 * 10^10)
NULL
p = 9967312, q = 0
End of while.
Addition ends.
The result is: 7 * 10^0 + 11 * 10^1 + 22 * 10^7 + 9 * 10^8 + -9 * 10^10 + 5 * 10^17 +
Finish.
Press any key to continue
666666
hello