西安交大软件学院：多项式链表相加算法详解

西安交通大学软件学院的数据结构课程PPT第41讲，主要内容是关于一元多项式链表的相加算法。这个算法的目标是将两个以头指针La和Lb表示的多项式链表相加，生成一个新的相加后的链表，同时保持原有的链表结构不变。在这个过程中，新链表的头指针为Lc，链表中的每个节点包含一个系数（coef）和指数（expn）。 算法的步骤如下： 1. 首先，创建一个新的多项式链表，用`malloc`函数分配内存空间，以`ploy`类型为节点，分配足够的空间来存储新节点（`p = (ploy*)malloc(sizeof(ploy))`）。 2. 初始化指针pa和pb分别指向两个待相加多项式链表的当前节点，即`pa = La->next`和`pb = Lb->next`。 3. 使用`while`循环遍历两个链表，直到其中一个链表遍历结束。在循环内，比较两个节点的指数，若pa的指数小于pb，则复制当前pa节点的值到新节点p，更新p的系数、指数，然后将p添加到新链表的末尾，更新`pc->next = p`，并将指针pc和pa向后移动。 4. 如果pa的指数大于或等于pb，直接移动pa和pb指针，继续比较下一个节点，确保按照从低指数到高指数的顺序进行相加。 5. 在整个过程中，原始的La和Lb链表保持不变，不会因相加操作而受到影响，这使得算法具有良好的可复用性，可以对同一链表进行多次操作。 6. 最后，整个过程由软件团队提供版权，并强调禁止传播。课程提供了联系方式（电话15229238541和QQ群871729782），以供进一步咨询和交流。 通过这个算法，学生可以学习到如何处理链表数据结构，并运用递归或迭代的方式实现多项式的加法操作，这对于理解和掌握软件设计中的数据结构和算法概念至关重要。