最终报告2-201708020305-杨兰馨1

大的到小的顺序插入新节点；2. 定义一个 add 函数，将两个有序链表中的多项式相加，合并相同幂次的项并更新系数；3. 定义一个 format 函数，对有序链表中的表达式进行格式化处理，处理特殊情况；4. 定义一个 print 函数，遍历链表并输出多项式。 三、详细设计 1. 有序链表节点结构设计： 创建一个结构体，包含以下域： - `int index`：表示多项式的幂次。 - `double coef`：存储对应幂次的系数。 - `struct Node* next`：指向下一个节点的指针。 2. 插入函数（insert）： - 接收一个已排序的链表头指针和一个新的数对（index, coef）。 - 遍历链表，找到合适的位置，根据index值将新节点插入，保持链表有序。 3. 多项式相加函数（add）： - 创建一个新的有序链表作为结果链表。 - 并行遍历两个输入链表，查找相同幂次的项，如果找到，则合并系数，否则分别添加到结果链表中。 - 对于未遍历完的链表，将其剩余项添加到结果链表末尾。 4. 格式化函数（format）： - 遍历链表，处理特殊情况： - 系数为1时，省略“1”； - 系数为-1时，仅保留“-”； - 幂次为0时，不显示项； - 幂次为1时，省略“^1”。 5. 输出函数（print）： - 遍历链表，根据格式化后的多项式输出表达式，如：“A(X)=6x^5+2x^3+9”。 四、实现与测试 使用C/C++或Python等编程语言实现以上设计，编写代码并进行单元测试，确保每个函数能正常工作。然后利用提供的测试样例进行综合测试，确保程序在各种情况下都能正确地输出结果。 五、性能优化 1. 使用哈希表或字典记录幂次和系数，加快查找相同幂次项的速度。 2. 使用尾插法构建链表，减少中间节点的移动操作。 3. 对于格式化处理，可以在插入链表时就进行判断，减少后续遍历。 六、实验总结 通过这个实验，我们实现了有序链表数据结构，用于表示一元多项式，并实现了多项式的加法运算、格式化输出等功能。这个过程加深了对线性表操作的理解，同时锻炼了数据结构的应用能力。