兰州大学数据结构课程设计2.docx

《数据结构》课程设计题目 (程序实现采用 C 语言) 题目 1：猴子选王（学时：3） 一堆猴子都有编号，编号是 一堆猴子都有编号，编号是 1，2，3 ...m，这群猴子（m 个）按照 1-m 的顺 序围坐一圈，从第1 开始数，每数到第n 个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：m 及 n 要求从键盘输入，存储方式采用向量及链表两种方式实现该问 题求解。 题目 2 ：字符逆转（学时：3） 从键盘读入一个字符串，把它存入一个链表（ 从键盘读入一个字符串，把它存入一个链表（每个结点存储 1 个字符），并 按相反的次序将字符串输出到显示屏。 题目 3 ：工资核算（学时：3） 设有一个单位的人员工资有如下信息： name、department、 base pay 、allowance、total。现从键盘输入一组人员工资数据并将它们存储到名为paydata 的文件中；再从 paydata 取出工资数据并给每个人的 base pay 增加 100 元，增加后将工资数据显示于屏幕(每行 1 人)。 题目 4：满足条件的有序表生成（学时：3） 已知三个有序表 A、B、C，它们皆由同一类元素构成，现要求对于表A 作以下运算而获得有序表 D：排出A 中所有的既在 B 中又在 C 中出现的元素。另外该任务要求具有建立有序表功能以及输出有序表到屏幕的功能。 #includestdio.h #includestring.h void main() { void sort(char a[],int len); char a[100],b[100],c[100],d[100],same[100]; int i,j,k,l1,l2; printf(Please input the line A:\n); gets(a); sort(a,strlen(a)); printf(\nPlease input the line B:\n); gets(b); sort(b,strlen(b)); printf(\nPlease input the line C:\n); gets(c); sort(c,strlen(c)); printf(\nThe right of the line A,B,C:\n); puts(a); puts(b); puts(c); for(i=j=k=0; (i(l1=strlen(b))) (j(l2=strlen(c)));) { if(b[i]==c[j]) { same[k]=b[i]; i++; j++; k++; } else if (b[i]c[j]) i++; else j++; } same[k]=\0; if(same[0]==\0) strcpy(d,a); else { for(i=j=k=0; (i(l1=strlen(a))) (j(l2=strlen(same))); ) { if(a[i]==same[j]) i++; else if (a[i]same[j]) {d[k]=a[i]; i++; k++;} else j++; } while(a[i]!=\0) { d[k]=a[i]; k++; i++; } d[k]=\0; } printf(\nThe line same is:%s\n,same); printf(\nThe line D is:%s\n,d); } void sort(char a[],int len) { int i,j; char temp; for(j=0;jlen-1;j++) for(i=0;ilen-1;i++) if(a[i]a[i+1]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; } } 题目 5：一元多项式的减法（学时：6） 设有两个一元多项式 A(x),B(x)，请完成运算 A(x)+B(x)、A(x)-B(x)，要求多项式采用链表进行存储。另外该任务要求具有建立多项式链表以及输出多项式到屏幕的功能。 #includestdio.h #includestdlib.h # define LEN sizeof(struct Link) struct Link { int c; int e; struct Link *next; }; void main() { void start(); //用户选择界面函数声明 struct Link *creat(char ch); //创造有序链表函数声明 struct Link *addLink(struct Link *head,struct Link *pre); //链表相加函数声明struct Link *cutLink(s