一、 实验目的
1、掌握线性表的逻辑结构
2、熟练掌握线性表的链式存储结构定义及基本操作
3、加深对链式存储数据结构的理解，逐步培养解决实际问题的编程能力
二、 实验要求
1、演示程序运行结果
2、分析调试过程中出现的现象
3、总结单链表基本操作的特点
4、分析算法的时间复杂度
三、实验内容
编写程序，实现一元多项式的创建、求和等基本操作算法。
(1) 根据一元多项式创建单链表。
(2) 实现两个多项式的求和。
(3) 输出求和结果。
1. #include<iostream> 2. #include<string> 3. #include<fstream> 4. using namespace std; 5. #define ERROR 0 6. 7. typedef struct PNode { 8. float coef; //系数 9. int expn; //指数 10. struct PNode *next; 11. } PNode, *Polynomial; 12. string head_1, head_2; 13. int temp; 14. char st = 'A'; 15. 16. void CreatPolyn(Polynomial &P, int m) //算法2.18 多项式的创建 17. { 18. //输入m项的系数和指数，建立表示一个多项式的有序链表P 19. Polynomial q, pre, s; 20. int i; 21. P = new PNode; 22. P->next = NULL; //先建立一个带头结点的单链表 23. char filename[20] = { 0 }; 24. cout << "请输入有关多项式p" << char(st + 32) << endl; 25. ++st; 26. gets(filename); 27. fstream file; 28. file.open(filename); 29. if (!file) { 30. cout << "未找到相关文件，无法打开！" << endl; 31. exit(ERROR); 32. } 33. file >> head_1 >> head_2; 34. while (!file.eof()) 35. { 36. s = new PNode; //生成新结点 37. file >> s->coef >> s->expn; //输入元素值 38. pre = P; //pre用于保存q的前驱，初值为头结点 39. q = P->next; 40. while (q && q->expn < s->expn) //通过比较指数找到第一个大于输入项指数的项q 41. { 42. pre = q; 43. q = q->next; 44. } //while 45. s->next = q; //将输入项s插入到q和其前驱结点pre之间 46. pre->next = s; 47. }//for 48. file.close(); 49. } //CreatPolyn 50. 51. void AddPolyn(Polynomial &Pa, Polynomial &Pb) //算法2.19 多项式的相加 52. { 53. //多项式加法：Pa=Pa+Pb，利用两个多项式的结点构成"和多项式" 54. Polynomial r, p1, p2, p3; 55. float sum; 56. p1=Pa->next; //补充代码 57. p2=Pb->next; //补充代码 58. //p1和p2初值分别指向Pa和Pb的第一个结点 59. p3=Pa; //补充代码 60. //p3指向和多项式的当前结点，初值为Pa 61. while (p1 && p2) //p1和p2均非空 62. { 63. if (p1->expn == p2->expn) //指数相等 64. { 65. sum = p1->coef + p2->coef; //sum保存两项的系数和 66. if (sum != 0) //系数和不为0 67. { 68. p1->coef=sum;//补充代码//修改Pa当前结点p1的系数值为两项系数的和 69. p3->next = p1; 70. p3 = p1; //将修改后的Pa当前结点p1链在p3之后，p3指向p1 71. p1 = p1->next; //p1指向后一项 72. r = p2; 73. p2 = p2->next; 74. delete r; //删除Pb当前结点r 75. } else //系数和为0 76. { 77. r=p1;p1=p1->next;delete r; 78. 79. //删除Pb当前结点p1 80. r = p2; 81. p2 = p2->next; 82. delete r; //删除Pb当前结点p2 83. } 84. } else if (p1->expn < p2->expn) //Pa当前结点p1的指数值小 85. { 86. p3->next=p1; //将p1链在p3之后 87. p3=p1; //p3指向p1 88. p1=p1->next; //p1指向后一项 89. } else //Pa当前结点p2的指数值小 90. { 91. p3->next = p2; //将p2链在p3之后 92. p3 = p2; //p3指向p2 93. p2 = p2->next; //p2指向后一项 94. } 95. } //while 96. p3->next = p1 ? p1 : p2; //插入非空多项式的剩余段 97. delete Pb; //释放Pb的头结点 98. } //AddPolyn 99. 100. 101. int main() { 102. Polynomial Pa, Pb; 103. Polynomial p; 104. int i; 105. 106. //创建多项式Pa 107. CreatPolyn(Pa, temp); //调用函数，输入Pa每一项的系数和指数 108. 109. //创建多项式Pb 110. CreatPolyn(Pb, temp); //调用函数，输入Pa每一项的系数和指数 111. 112. AddPolyn(Pa, Pb); 113. cout << "多项式Pa和Pb相加后的结果是：\n"; 114. p = Pa->next; 115. i = 0; 116. while (p) //输出相加后的结果，每一项以x^n表示 117. { 118. if (i) 119. cout << " + "; 120. cout << "(" << p->coef << ") * x^" << p->expn; 121. p = p->next; 122. i = 1; 123. } 124. cout << endl; 125. return 0; 126. }
程序运行需要创建两个文本文档PolyA和PolyB，例如：
