1
摘 要
近年来，随着计算机的广泛应用和各个学科的量化需求不断提高，
越来越多的人士希望学习数据结构课程。利用 TurboC 或 C++来设计
并解决计算机应用问题已经是非常重要的一门知识。这次课程设计就
是应用 TurboC 或 C++来设计一元多项式想加的问题，并解决了现实
游戏中猴子选大王的问题，我所选的程序完全是对链表的熟识，不管
是单链表还是循环链表。最后一个程序也是利用单链表解决运动会分
数统计的问题。
关键字： C++，链表，循环链表，数组
2
目 录
摘 要┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈1
设计任务:
一元多项式相加┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈3
运动会分数统计┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈6
猴子选大王┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈14
设计总结┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈14
设计心得┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈15
参考文献┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈15
谢 辞┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈16
3
设计任务：
一元多项式计算
(1) 目的
检验对链表结构及算法的掌握程度。
(2) 设计内容和要求
能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并
将结果输入；在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使
用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法
的改进方法。
程序编码：
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define LEN sizeof(node)
typedef struct polynode /*用单链表存储多项式的结点结构*/
{
int coef; /*多项式的系数*/
int exp; /*指数*/
struct polynode *next; /*next 是 struct polynode 类型中的一个成员，它又指向
struct polynode 类型的数据，以此建立链表*/
}node;/*若定为"node,*list;"，意即 node*与 list 同为结构指针类型*/
node * create(void) /*指针函数，返回指针类型；用尾插法建立一元多项式的链表的函
数*/
{
node *h,*r,*s;
int c,e;
h=(node *)malloc(LEN); /*建立多项式的头结点，为头结点分配存储空间*/
4
r=h; /*r 指针始终动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/
printf("coef:");
scanf("%d",&c); /*输入系数*/
printf("exp: ");
scanf("%d",&e); /*输入指针*/
while(c!=0) /*输入系数为 0 时，表示多项式的输入结束*/
{
s=(node *)malloc(LEN); /*申请新结点*/
s->coef=c; /*申请新结点后赋值*/
s->exp=e; /*申请新结点后赋值*/
r->next=s; /*做尾插，插入新结点*/
r=s; /*r 始终指向单链表的表尾*/
printf("coef:");
scanf("%d",&c);
printf("exp: ");
scanf("%d",&e);
}
r->next=NULL; /*将表的最后一个结点的 next 置 NULL，以示表结束*/
return(h);
}
void polyadd(node *polya, node *polyb)/*一元多项式相加函数，用于将两个多项式相加，
然后将和多项式存放在多项式 polya 中，并将多项式 ployb 删除*/
{
node *p,*q,*pre,*temp;
int sum;
p=polya->next;/*令 p 和 q 分别指向 polya 和 polyb 多项式链表中的第一个结点
*/
q=polyb->next;
pre=polya; /*位置指针，指向和多项式 polya*/
while(p!=NULL&&q!=NULL) /*当两个多项式均未扫描结束时，执行以下操作*/
{
if(p->exp<q->exp) /*若 p 指向的多项式指数小于 q 指的指
数*/
{
pre->next=p; /*将 p 结点加入到和多项式中*/
pre=pre->next;
p=p->next;
}
else if(p->exp==q->exp) /*若指数相等，则相应的系数相加*/
{
sum=p->coef+q->coef;
if(sum!=0)
{
p->coef=sum;
5
pre->next=p;pre=pre->next;p=p->next;
temp=q;q=q->next;free(temp);
}
else /*如果系数和为零，则删除结点 p 与 q，并将指针指向
下一个结点*/
{
temp=p->next;free(p);p=temp;
temp=q->next;free(q);q=temp;
}
}
else /*若 p 指数大于 q 指数*/
{
pre->next=q; /*p 结点不动，将 q 结点加入到和多项式中*/
pre=pre->next;
q=q->next;
}
}
if(p!=NULL) /*多项式 A 中还有剩余，则将剩余的结点加入到和多项式中*/
pre->next=p;
else /*否则将 B 的结点加入到和多项式中*/
pre->next=q;
}
void print(node * p) /*输出函数，打印出一元多项式*/
{
while(p->next!=NULL)
{
p=p->next;
printf(" %d*x^%d",p->coef,p->exp);
}
}
main() /*主函数*/
{
node * polya,* polyb;
printf("Welcome to use!\n");
printf("\nPlease input the ploya include coef && exp:\n");
polya=create(); /*调用建立链表函数，创建多项式 A*/
print(polya);
printf("\nPlease input the ployb include coef && exp:\n");
polyb=create(); /*同理，创建 B*/
print(polyb);
printf("\nSum of the poly is:\n");
