《大作业案例 数媒1 1233104 王瑜》由会员分享，可在线阅读，更多相关《大作业案例 数媒1 1233104 王瑜（6页珍藏版）》请在金锄头文库上搜索。
1、第第 2 章章的作业的作业2-24 若采用带头节点的单链表储存一元多项式，试编写一个算法，输入一组一元多项式的若采用带头节点的单链表储存一元多项式，试编写一个算法，输入一组一元多项式的 系数和指数，按指数降幂的方式建立多项式链表。如果输入的指数与链表中已有的某一个系数和指数，按指数降幂的方式建立多项式链表。如果输入的指数与链表中已有的某一个 的项的指数相等，则新的项不加入，并报告作废信息。整个输入序列以输入系数为的项的指数相等，则新的项不加入，并报告作废信息。整个输入序列以输入系数为 0 标志标志 结束。结束。 设计思路如下： （1）对单链表进行定义，有三个域来分别保存系数、指数、指针。 （2
2、）对 Input 函数进行定义： A：创建一个新节点和指针，定义 c 和 e 来接收输入的系数和指数。 B：进行一个以输入系数为 0 标志结束的循环，如果 e= 0 循环结束，否则给新 节点分配空间，分配不成功则报错，分配成功则将输入的值赋给新节点，使定义指针 指向单链表的头结点，进行一个循环对链表的指数进行判断，如果该节点的指针不为 空且该节点的指数大于新节点的指数，使 pre 指向它的下一个节点，直到该节点的指 针为空或指数小于等于新节点的指数，再判断该节点的指数是否等于新节点的指数， 如果相等，则新的项不加入，且报错，否则将新节点的值赋给单链表。 #include #include ty
3、pedef struct Term float coef; int exp; struct Term * link; *Polynomial;void Input(Polynomial float c; int e; while (1) cout c e ; if (!c) break;/以输入系数为 0 标志结束 newTerm = new Term; if (newTerm = NULL) cerr coef = c;/将输入的数据赋给 newTermnewTerm-exp = e; pre = PL; while (pre-link != NULL /pre 指向它的下一个 if (pr
4、e-link != NULL pre-link = newTerm; 2-26 设一个带头节点的单链表表示一元多项式。编写一个算法，按照降幂的次序输出一个设一个带头节点的单链表表示一元多项式。编写一个算法，按照降幂的次序输出一个 一元多项式。一元多项式。 设计思路如下： (1)对单链表进行定义，有三个域来分别保存系数、指数、指针。 (2)对 Output 函数进行定义： A：创建两个指针来表示单链表的前、后节点，创建临时指针来进行数据和指针 指向的转换，定义布尔变量 h 来判断多项式的指数。 B：如果单链表为空，返回空，否则对单链表进行循环，用 pre 表示单链表的前一 个节点，p 表示 pr
5、e 的后一个节点，如果 p 的指数大于 pre 的指数，交换 p 和 pre 节点 的位置，如果 p 的指数等于 pre 的指数，判断它们的系数来决定是否交换节点位置， 按照降幂的次序排好后，对系数进行判断，第一个系数和负系数都直接输出，其余的 都输出 + ，先输出系数，然后判断指数，指数为 0 直接跳出，指数为 1 输出 x，其 余的都输出 x 和该节点的指数。#include #include typedef struct Term float coef; int exp; struct Term * link; *Polynomial;void Output(Polynomial Ter
6、m *pre = PL-link; Term *p,*temp = new Term; if (pre = NULL) return; else cout link) for (p = pre-link ;p != NULL;p = p-link) if (pre-exp exp)/按指数排序 temp-exp = pre-exp; temp-coef = pre-coef; pre-exp = p-exp; pre-coef = p-coef; p-exp = temp-exp; p-coef = temp-coef; else if (pre-exp = p-exp pre-coef =
7、p-coef; p-coef = temp-coef; if (h = false switch (pre-exp) case 0 : break; case 1 : cout exp; cout #include typedef struct Term float coef; int exp; struct Term * link; *Polynomial;void revert(Polynomial Term *pre,*temp = new Term; if (p = NULL) return; else pre = NULL;/断开头节点的链接 while (p != NULL)/改变
8、节点指针的方向 temp = p-link; p-link = pre; pre = p; p = temp; PL-link = pre;/将头节点的指针指向最后的节点6调试方案 以下是循环单链表运算的调试方案，其中要链接循环单链表的头文件 CircList.h。 假设链表的元素个数（不计入头结点）在 1n 之间，对于结点序号i 的取值，应按照5边界值分析法，取正好等于边界和刚刚超出边界的值作为测试用例，检查对于合理的与不 合 理的输入，程序中是否有正确的处理。 在测试插入和删除运算时测试用例的选择如下序号 输入 预期结果1 A = 21,43,54,65,12,27,13,31,15,41
9、 21 43 54 65 12 27 13 31 15 41 链表长度=102 在i=1 位置插入38（边界） 38 21 43 54 65 12 27 13 31 15 41 链表长度=113 在i=12 位置插入62（边界） 38 21 43 54 65 12 27 13 31 15 41 62 链表长度=124 在i=0 位置插入38（边界外） 38 21 43 54 65 12 27 13 31 15 41 62 链表长度=125 在i=14 位置插入50（边界外） 38 21 43 54 65 12 27 13 31 15 41 62 链表长度=126 删i=7 位置元素（内部） 退
10、出元素=2738 21 43 54 65 12 13 31 15 41 62 链表长度=117 删i=1 位置元素（边界） 退出元素=3821 43 54 65 12 13 31 15 41 62 链表长度=108 删i=0 位置元素（边界外） 21 43 54 65 12 13 31 15 41 62 链表长度=109 删i=11 位置元素（边界外） 21 43 54 65 12 13 31 15 41 62 链表长度=10【调试 C 代码】如下 #define maxSize 10 #include “CircList.h” void main(void) DataType AmaxSiz
11、e = 21, 43, 54, 65, 12, 27, 13, 31, 15, 41, x; CircList L; int len, i; InitList(L); if ( !IsEmpty(L) ) cout “循环单链表为空表！n“; else cout “循环单链表为非空表！n“; createList(L, A, maxSize); printList(L); len = Length(L); cout “链表长度=“ len endl; x = 15; cout “查找“ x; i = Find(L,x); if ( i ) cout “ 成功！结果是“ i endl; else
12、 cout “ 不成功！结果是“ i endl; x = 38; cout “查找“ x; i = Find(L, x); if ( i ) cout “ 成功！结果是“ i endl; else cout “ 不成功！结果是“ i endl; cout “插入：“ endl; x = 38; i = 1; Insert(L, i, x);len = Length(L); cout “插入值“ x “在第“ i “个元素，链表长度=“ len endl; printList(L); x = 62; i = 12; Insert(L, i, x); len = Length(L); cout “
13、插入值“ x “在第“ i “个元素，链表长度=“ len endl; printList(L); x = 38; i = 0; Insert(L, i, x); len = Length(L);6cout “插入值“ x “在第“ i “个元素，链表长度=“ len endl; printList(L); x = 50; i = 14; Insert(L, 14, 50); len = Length(L); cout “插入值“ x “在第“ i “个元素，链表长度=“ len endl; printList(L); cout “删除：“ endl; i = 7; Remove(L, i,
14、x); cout “退出第“ i “个元素，值=“ x endl; printList(L); i = 1; Remove(L, i, x); cout “退出第“ i “个元素，值=“ x endl; printList(L); i = 0; Remove(L, i, x); cout “退出第“ i “个元素，值“ x endl; printList(L); i = 11; Remove(L, i, x); cout “退出第“ i “个元素，值“ x endl; printList(L); len = Length(L); cout “链表长度=“ len endl; 执行结果： 7结果分析 循环单链表是一种顺序存取结构，不能够随机存取，这决定了它的相关运算的时间复杂 度是 O(n)，其中 n 是链表长度。
