鱼C论坛

 找回密码
 立即注册
查看: 4182|回复: 7

[技术交流] 一元多项式的计算问题,线性链表的典型应用.

[复制链接]
发表于 2011-8-20 03:08:45 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 Be_envious 于 2011-8-20 03:10 编辑
  1. #include<stdio.h>
  2. #include<malloc.h>
  3. //需注意的是 多项式加法默认的是 幂指数从小大依次排列 输入幂指数时应注意
  4. //只是练习题,所以没有更深入的对多项式进行幂指数整理升序排序
  5. //目的只是学会线性链表在多项式上的应用
  6. struct polynomial
  7. //polynomial 中文意思 多项式 起这么长的名字其实是为了顺便学学英语
  8. {
  9. int coefficient; //coefficient 系数
  10. int index; //index 指数
  11. struct polynomial * next; //多项式后继指针
  12. };

  13. struct polynomial * creat(void); //创建函数
  14. //多项式相加函数
  15. struct polynomial * plus(struct polynomial * an,struct polynomial * bn);
  16. void print(struct polynomial * P);
  17. int main(void)
  18. {
  19. struct polynomial * an = NULL;
  20. struct polynomial * bn = NULL;
  21. struct polynomial * cn = NULL;

  22. an = creat();
  23. bn = creat();
  24. cn = plus(an,bn);
  25. print(cn);
  26. system("pause");
  27. }

  28. //创建函数
  29. struct polynomial * creat(void)
  30. {
  31. //分配一个没有数据的空间给头结点,这个很重要
  32. struct polynomial * head = (struct polynomial *)malloc(sizeof(struct polynomial));
  33. if(NULL == head)
  34. {
  35. printf("No enough space!");
  36. exit(-1);
  37. }

  38. struct polynomial * tail = head;
  39. tail->next = NULL;

  40. int NUMBER_OF_TERMS;
  41. int coefficient;
  42. int index;
  43. int loop;

  44. printf("Input number of terms: ");
  45. scanf("%d",&NUMBER_OF_TERMS);

  46. for(loop = 0;loop < NUMBER_OF_TERMS;++loop)
  47. {
  48. printf("\nInput coefficient of No.%d term: ",loop+1);
  49. scanf("%d",&coefficient);
  50. printf("Input index of No.%d term: x^",loop+1);
  51. scanf("%d",&index);

  52. struct polynomial * GENERAL_TERM = (struct polynomial *)malloc(sizeof(struct polynomial));
  53. if(NULL == GENERAL_TERM)
  54. {
  55. printf("no enough space!");
  56. exit(-1);
  57. }
  58. GENERAL_TERM->coefficient = coefficient;
  59. GENERAL_TERM->index = index;

  60. tail->next = GENERAL_TERM;
  61. GENERAL_TERM->next = NULL;
  62. tail = GENERAL_TERM;
  63. }
  64. return (head);
  65. }

  66. //多项式相加函数
  67. struct polynomial * plus(struct polynomial * an,struct polynomial * bn)
  68. {
  69. struct polynomial * pointer_a = an->next;
  70. struct polynomial * pointer_b = bn->next;

  71. //这里很重要
  72. struct polynomial * cn = (struct polynomial *)malloc(sizeof(struct polynomial));
  73. if(NULL == cn)
  74. {
  75. printf("No enough space!");
  76. exit(-1);
  77. }
  78. struct polynomial * pointer_c = cn;

  79. while(pointer_a && pointer_b)
  80. {
  81. struct polynomial * pointer_a_plus_b = (struct polynomial *)malloc(sizeof(struct polynomial));
  82. if(NULL == (pointer_a_plus_b))
  83. {
  84. printf("No enough space!");
  85. exit(-1);
  86. }
  87. if(pointer_a->index < pointer_b->index)
  88. {
  89. pointer_a_plus_b->coefficient = pointer_a->coefficient;
  90. pointer_a_plus_b->index = pointer_a->index;
  91. pointer_a = pointer_a->next;

  92. pointer_c->next = pointer_a_plus_b;
  93. pointer_a_plus_b->next = NULL;
  94. pointer_c = pointer_a_plus_b;
  95. }
  96. else if(pointer_a->index == pointer_b->index)
  97. {
  98. pointer_a_plus_b->coefficient = pointer_a->coefficient + pointer_b->coefficient;
  99. pointer_a_plus_b->index = pointer_a->index;
  100. pointer_a = pointer_a->next;
  101. pointer_b = pointer_b->next;

  102. pointer_c->next = pointer_a_plus_b;
  103. pointer_a_plus_b->next = NULL;
  104. pointer_c = pointer_a_plus_b;
  105. }
  106. else
  107. {
  108. pointer_a_plus_b->coefficient = pointer_b->coefficient;
  109. pointer_a_plus_b->index = pointer_b->index;
  110. pointer_b = pointer_b->next;

  111. pointer_c->next = pointer_a_plus_b;
  112. pointer_a_plus_b->next = NULL;
  113. pointer_c = pointer_a_plus_b;
  114. }
  115. }

  116. if(pointer_a == NULL)
  117. {
  118. while(pointer_b)
  119. {
  120. struct polynomial * pointer_a_plus_b = (struct polynomial *)malloc(sizeof(struct polynomial));
  121. if(NULL == pointer_a_plus_b)
  122. {
  123. printf("No enough space");
  124. exit(-1);
  125. }

  126. pointer_a_plus_b->coefficient = pointer_b->coefficient;
  127. pointer_a_plus_b->index = pointer_b->index;
  128. pointer_b = pointer_b->next;

  129. pointer_c->next = pointer_a_plus_b;
  130. pointer_a_plus_b->next = NULL;
  131. pointer_c = pointer_a_plus_b;
  132. }
  133. }
  134. else
  135. {
  136. while(pointer_a)
  137. {
  138. struct polynomial * pointer_a_plus_b = (struct polynomial *)malloc(sizeof(struct polynomial));
  139. if(NULL == pointer_a_plus_b)
  140. {
  141. printf("No enough space!");
  142. exit(-1);
  143. }

  144. pointer_a_plus_b->coefficient = pointer_a->coefficient;
  145. pointer_a_plus_b->index = pointer_a->index;
  146. pointer_a = pointer_a->next;

  147. pointer_c->next = pointer_a_plus_b;
  148. pointer_a_plus_b = NULL;
  149. pointer_c = pointer_a_plus_b;
  150. }
  151. }
  152. return (cn);
  153. }

  154. //打印输出函数
  155. void print(struct polynomial * P)
  156. {
  157. int total_terms = 0;
  158. struct polynomial * pointer = P->next;
  159. while(pointer)
  160. {
  161. if(total_terms != 0)
  162. {
  163. printf("+");
  164. }
  165. printf("%dx^%d",pointer->coefficient,pointer->index);
  166. pointer = pointer->next;
  167. ++total_terms;
  168. }
  169. printf("\nTotal terms : %d\n",total_terms);
  170. }

复制代码

希望大家多多交流,有不足之处望指出,日后写的代码都会完全共享,希望大家给予支持.
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-8-20 18:45:59 | 显示全部楼层
多项式用数组更简洁哦
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2011-8-20 20:14:21 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-8-20 22:51:25 | 显示全部楼层
Be_envious 发表于 2011-8-20 20:14
用数组要写动态二维数组
只是现在在学习线性链表
不过谢谢你的提议

一维就够了,下标当指数,保存系数
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2011-8-20 22:54:21 | 显示全部楼层
wangyexin 发表于 2011-8-20 22:51
一维就够了,下标当指数,保存系数

好办法  学习了  
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-9-10 13:59:10 | 显示全部楼层
不错啊!!!!!!!!!!!!!!!!!!!!!!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-10-28 16:35:49 | 显示全部楼层
如果用一维数组,下标存指数,指数跳跃很大时,会很浪费空间的啊,还是二维好点吧~
LZ的代码写得很清晰,很容易读懂~。~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-4-1 11:32:49 | 显示全部楼层
不错啊!!!!!!!!!!!!!!!!!!!!!!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 06:00

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表