高等学校计算机实践教学用书 《数据结构》实验指导书 p-q->next /指向当前报数的人 t=t+1 if(t%m==0) printf(4d”p->num) q->nextp->next free(p) else P-q i while(p==q) head=p /*主程序 linklist *head scanf(&n) scanf(&m) creat(head, n) select(head, m) printf("the last one: is%d,, head-num) 题目三一元多项式简单计算 [问题描述] 设计一个一元多项式的简单计算器 [基本要求] 一元多项式简单计算器的基本功能为 (1)输入并建立多项式 (2)输出多项式 (3)两个多项式相加减,相乘除,建立并输出多项式 实现提示 可选择带头结点的单向循环链表或单链表存储多项式,头结点可以存储 多项式的参数如项数等。 [程序实现] 这里利用单链表作为存储多项式的结构:单链表定义如下: 西南科技大学计算机科学学院
高等学校计算机实践教学用书 ★ 《数据结构》实验指导书 西南科技大学 计算机科学学院 11 do{ p=q->next; /*指向当前报数的人 t=t+1; if(t%m==0) { printf(“%4d”,p->num); q->next=p->next; free(p); p=q; } else p=q; } while(p==q); head=p; } /*主程序 main() { int n,m; linklist *head; scanf(&n); scanf(&m); creat(head,n); select(head,m); printf(“the last one:is%d”,head-num); } 题目三 一元多项式简单计算 [问题描述] 设计一个一元多项式的简单计算器 [基本要求] 一元多项式简单计算器的基本功能为： （1） 输入并建立多项式 （2） 输出多项式 （3） 两个多项式相加减，相乘除，建立并输出多项式 [实现提示] 可选择带头结点的单向循环链表或单链表存储多项式，头结点可以存储 多项式的参数如项数等。 [程序实现] 这 里 利用 单链 表 作为 存储 多项 式的 结 构： 单链 表定 义 如下 ：
高等学校计算机实践教学用书 《数据结构》实验指导书 #define null rue #define false int coef./*系数 nt exp,/*指数 struct mulpoly next; i 假设输入一组多项式的系数和指数,以输入实数0为结束标记,这里建 立多项式时,总是按指数从大到小排列。 /*产生多项式链表,设头指针为head struct mulpoly *head, r nt m,n; ead =(struct mulpoly *)malloc(sizeof(struct scant%d,%d”&n,&m); while(n) /*n不等于0时建立多项式链表 f s=(struct mulpoly )malloc(sizeof(struct mulpoly)); /建立一个新结点 s->coen /*把*S链接到*R后面 printf("input coef and exp: In) scanf(%d, %d,, &n, &m) /*a+b实现多项式相加 /*两多项式相加运算hahb分别是A、B链表的头指针相加后存放到多 项式C,头指针为he struct mulpoly polyadd (ha, hb) struct mulpoly *h i struct mulpoly *hc, *p, *q,*s 西南科技大学计算机科学学院
高等学校计算机实践教学用书 ★ 《数据结构》实验指导书 西南科技大学 计算机科学学院 12 #define null 0 #define true 1 #define false 0 struct mulpoly { int coef ;/*系数 int exp; /*指数 struct mulpoly next; } 假设输入一组多项式的系数和指数，以输入实数 0 为结束标记，这里建 立多项式时，总是按指数从大到小排列。 /*产生多项式链表，设头指针为 head struct mulpoly creatpoly() { struct mulpoly *head, *r , *s; int m,n; head =(struct mulpoly *)malloc(sizeof(struct mulpoly)); scanf(“%d,%d”&n,&m)； r=head; while(n) /*n 不等于 0 时建立多项式链表 { s=(struct mulpoly )malloc(sizeof(struct mulpoly)); /*建立一个新结点 s->coef=n; s->exp=m; r->next=s; /*把*S 链接到*R 后面 r=s; printf(“input coef and exp:\n”); scanf(“%d,%d”,&n,&m); } r->next=null; head=head->next; return (head); } /*a+b 实现多项式相加： /*两多项式相加运算 ha hb 分别是 A、B 链表的头指针,相加后存放到多 项式 C，头指针为 hc struct mulpoly polyadd(ha,hb) struct mulpoly *ha, *hb; { struct mulpoly *hc, *p, *q, *s , *r; int x; p=ha;
高等学校计算机实践教学用书 《数据结构》实验指导书 lulpoly *)malle lulpoly)) {if(p->ext==q-ext)/*两个结点指数相等 ef+q->coef,/*系数相加 if(x!=0) oly ")malloc(sizeof(struct Ipoly)) else/*两结点指数不相等 f r=(struct mulpoly *)malloc(sizeof(struct *mulpoly)); I->exp-p->exp; f r(struct mulpoly *)malloc(sizeof(struct*mulpoly)); while(p)/p!=NULL复制A的剩余部分 f r(struct mulpoly *)malloc(sizeof(struct*mulpoly)); 西南科技大学计算机科学学院
高等学校计算机实践教学用书 ★ 《数据结构》实验指导书 西南科技大学 计算机科学学院 13 q=hb; hc=(struct mulpoly *)malloc(sizeof(struct *mulpoly)); s=hc; while((p!=null)&&(q!=null)) {if(p->ext==q->ext) /*两个结点指数相等 { x=p->coef+q->coef; /*系数相加 if(x!=0) {r=(struct mulpoly *)malloc(sizeof(struct *mulpoly)); r->exp=p->exp; r->coef=x; s->next=r; s=r; } p=p->next; q=q->next; } else/*两结点指数不相等 if(p->next<q->next) { r=(struct mulpoly *)malloc(sizeof(struct *mulpoly)); r->exp=p->exp; r->coef=p->coef; s->next=r; s=r; p=p->next; } else /* p->next>q->next 时 { r=(struct mulpoly *)malloc(sizeof(struct *mulpoly)); r->exp=q->exp; r->coef=q->coef; s->next=r; s=r; q=q->next; } } while(p) /* p!=NULL 复制 A 的剩余部分 { r=(struct mulpoly *)malloc(sizeof(struct *mulpoly)); r->exp=p->exp; r->coef=p->coef;
高等学校计算机实践教学用书 《数据结构》实验指导书 S-r p-p->next; while(q)/q!=NULL复制B的剩余部分 f r=(struct mulpoly *)malloc(sizeof(struct*mulpoly)): s->nextnull /*链成单链表 free(r retur n(hc) 相减运算,实际上也是多项式相加的运算,无非是各项的系数符号不等 而已。而多项式的乘法运算可说明如下。 /*多项式相乘 struct mulpoly* polymulti(f, g) struct mulpoly *f, maxp, p, extern reverse( mulpoly *p maxp=f->exp+- >exp (struct mulpoly *)malloc(sizeof( struct*mulpoly)) reverse(g) for(r=maxp r >=0; r--) i X0 fp=f; gp=g, while((fq!=null)&&(gp!=null)) i p=fp->exp=gp->exp, fp=fp->next; else 西南科技大学计算机科学学院
高等学校计算机实践教学用书 ★ 《数据结构》实验指导书 西南科技大学 计算机科学学院 14 s->next=r; s=r; p=p->next; } while(q) /* q!=NULL 复制 B 的剩余部分 { r=(struct mulpoly *)malloc(sizeof(struct *mulpoly)); r->exp=q->exp; r->coef=q->coef; s->next=r; s=r; q=q->next; } s->next=null; /*链成单链表 r=hc; hc=hc->next; free ( r ); return(hc); } 相减运算，实际上也是多项式相加的运算，无非是各项的系数符号不等 而已。而多项式的乘法运算可说明如下。 /*多项式相乘 struct mulpoly * polymulti(f,g) struct mulpoly *f, *g; { mulpoly *fp, *gp, *q, *h; int maxp , p, r, x; extern reverse(mulpoly *p); maxp=f->exp+q->exp; h=(struct mulpoly *)malloc(sizeof(struct *mulpoly)); hp=h; reverse(g); for(r=maxp;r>=0;r--) { x=0;fp=f;gp=g; while((fq!=null)&&(gp!=null)) { p=fp->exp=gp->exp; if(p>r) fp=fp->next; else if(p<r)
高等学校计算机实践教学用书 《数据结构》实验指导书 else fp=fp->next, * end of while i p=(struct mulpoly *)malloc(sizeof(struct*mulpoly)) q->exp-r; q->coef-x hp=h h=h->next free(hp) return h 其中的 reverse函数说明如下 mulpoly *q i mulpoly*pl,"p2 while(pl!=null) i p2=p1->next; 多项式的输出的输出,实际上就是单链表的输出,只是该单链表的数据 域含有系数和指示两部分而已。 /*多项式的输出 playout(head) 西南科技大学计算机科学学院
高等学校计算机实践教学用书 ★ 《数据结构》实验指导书 西南科技大学 计算机科学学院 15 gp=gp->next; else { x+=fp->coef*gp->coef; fp=fp->next; gp=gp->next; } } /* end of while if (abs(x)>le-6) { p=(struct mulpoly *)malloc(sizeof(struct *mulpoly)); q->exp=r; q->coef=x; q→next=null; hp->next=q; hp=q; } } /* end of for hp=h; h=h->next; free(hp); return h; } 其中的 reverse 函数说明如下 reverse(q) mulpoly *q; { mulpoly *p1, *p2; if(q!=null) { p1=q->next; q->next=null; while(p1!=null) { p2=p1->next; p1->next=q; q=p1; p1=p2; } } 多项式的输出的输出，实际上就是单链表的输出，只是该单链表的数据 域含有系数和指示两部分而已。 /*多项式的输出 ployout(head)