数据结构课程实验设计1

if (a->expn < b->expn) return -1; if (a->expn > b->expn) return 1; return 0; }

term* APolyn(term *Pa, term *Pb)// 多项式加法:Pa = Pa+Pb,利用两个多项式的结点构成\和多项式\。 {

term *h, *qa = Pa, *qb = Pb, *p, *q; float sum;

h = p = (term*)malloc(sizeof(term)); p->next = NULL;

while (qa && qb) // Pa和Pb均非空 {

switch (Compare(qa,qb)) {

case -1: // 多项式PA中当前结点的指数值小 p->next = qb; p = qb;

qb = qb->next; break;

case 0: // 两者的指数值相等 sum = qa->coef + qb->coef;

if (sum != 0.0) // 修改多项式PA中当前结点的系数值 {

p->next = qa; qa->coef = sum; p = qa;

qa = qa->next; }

else // 删除多项式PA中当前结点 {

q = qa;

qa = qa->next; free(q); }

q = qb;

qb = qb->next; free(q); break;

case 1: // 多项式PB中当前结点的指数值小 p->next = qa; p = qa;

qa = qa->next;

break; } // switch } // while

if (Pa) p->next = qa; // 链接Pa中剩余结点 if (Pb) p->next = qb; // 链接Pb中剩余结点 q = h;

h = h->next; free(q); return h; } // APolyn

term* A(term *Pa, term *Pb) {

int n;

puts(\再输入一元多项式的项数\ scanf(\

Pb = CreatPolyn(Pb,n); Pb = selsort(Pb); PrintfPoly(Pa);

if(Pb && Pb->coef>0) printf(\ PrintfPoly(Pb); Pa = APolyn(Pa,Pb); printf(\ Pa = selsort(Pa); PrintfPoly(Pa); return Pa; }

term* BPolyn(term *Pa, term *Pb) //多项式减法:Pa = Pa-Pb,利用两个多项式的结点构成\差多项式\。 {

term *p = Pb; while(p) {

p->coef *= -1; p = p->next; }

return APolyn(Pa,Pb); } // BPolyn

term* B(term *Pa, term *Pb) {

int n;

puts(\再输入一元多项式的项数\

scanf(\

Pb = CreatPolyn(Pb,n); Pb = selsort(Pb); PrintfPoly(Pa); printf(\

putchar('(');PrintfPoly(Pb);putchar(')'); Pa = BPolyn(Pa,Pb); printf(\ Pa = selsort(Pa); PrintfPoly(Pa); return Pa; }

term* CPolyn(term *Pa, term *Pb) //多项式乘法:Pa = Pa*Pb,利用两个多项式的结点构成\积多项式\。 {

if(!Pb) return NULL;

term *pa = Pa, *p, *q, *r, *s, *t; r = p = (term*)malloc(sizeof(term)); while(pa) {

p->coef = pa->coef; p->expn = pa->expn; q = p;

p = p->next = (term*)malloc(sizeof(term)); pa = pa->next; }

q->next = NULL; free(p); pa = Pa;

t = s = (term*)malloc(sizeof(term)); while(pa) { q = s;

s = s->next = (term*)malloc(sizeof(term)); pa = pa->next; }

q->next = NULL; free(s); pa = Pa;

while(pa) {

pa->coef *= Pb->coef; pa->expn += Pb->expn; pa = pa->next; } Pb = Pb->next; while(Pb)

{

p = r; s = t; while(p) {

s->coef = p->coef * Pb->coef; s->expn = p->expn + Pb->expn; p = p->next; s = s->next; }

Pa = APolyn(Pa,t); Pb = Pb->next; }

return Pa; } // CPolyn

term* C(term *Pa, term *Pb) {

int n;

puts(\再输入一元多项式的项数\ scanf(\

Pb = CreatPolyn(Pb,n); Pb = selsort(Pb);

putchar('(');PrintfPoly(Pa);putchar(')'); printf(\

putchar('(');PrintfPoly(Pb);putchar(')'); printf(\

Pa = CPolyn(Pa,Pb); Pa = selsort(Pa); PrintfPoly(Pa); return Pa; }

void main() {

term *M,*N; char s[2]; int i,n;

puts(\一元多项式计算:\\n输入一元多项式的项数\ scanf(\

M = CreatPolyn(M,n); M = selsort(M); PrintfPoly(M);

p: puts(\加\\n2:减\\n3:乘\\n4:退出\ getchar(); q: gets(s);

if(s[1]!='\\0' || !isdigit(*s)) {

puts(\输入有误,请重新输入!\ }

i = *s-48; switch(i) {

case 1:M = A(M,N);goto p;; case 2:M = B(M,N);goto p;; case 3:M = C(M,N);goto p; case 4:break;

default:puts(\输入有误,请重新输入!\ } }

C 猴子选大王

一.实验目的

任务:一堆猴子都有编号,编号是1,2,3 ...m ,这群猴子(m个)按照1-m的顺序围坐一圈,从第1开始数,每数到第N个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。

要求:输入数据:输入m,n m,n 为整数,n

输出形式:中文提示按照m个猴子,数n 个数的方法,输出为大王的猴子是几号 ,建立一个函数来实现此功能 二.实验要求:

利用单向循环链表模拟此过程,输出选出的大王编号。 三.程序的设计思想:

(1) 问题分析:“猴子选大王”问题是约瑟夫环问题的一个特例。由于本题目的数据元素个数不可知,所以可使用链表来动态的分配内存空间。而该问题又是一个不断的循环问题所以用循环链表来实现。

(2)总体设计:首先生成一个空链表,并给n个结点分配空间,让单链表的表尾指针指向头结点则生成一个带有n个结点的循环单链表。再给每只猴子建立顺序的编号。现从第一个结点开始报数,依次顺序查找出报数为m的待出列的结点(猴子)通过q->next=p->next

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4