《数据结构》课程设计题目 (程序实现采用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中出现的元素。另外该任务要求具有建立有序表功能以及输出有序表到屏幕的功能。
#include
void sort(char a[],int len);
char a[100],b[100],c[100],d[100],same[100];
int i,j,k,l1,l2;
printf(\ gets(a);
sort(a,strlen(a));
printf(\ gets(b);
sort(b,strlen(b));
printf(\ gets(c);
sort(c,strlen(c));
printf(\ 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] 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] while(a[i]!='\\0') { d[k]=a[i]; k++; i++; } d[k]='\\0'; } printf(\ printf(\} void sort(char a[],int len) { int i,j; char temp; for(j=0;j 题目5：一元多项式的减法（学时：6） 设有两个一元多项式A(x),B(x)，请完成运算A(x)+B(x)、A(x)-B(x)，要求多项式采用链表进行存储。另外该任务要求具有建立多项式链表以及输出多项式到屏幕的功能。 #include # 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(struct Link *head,struct Link *pre); //链表相减函数声明 void print(struct Link *p); //输出函数声明 struct Link *a,*b; int sign=-1;//设置标志 start(); while(sign!=0) { scanf(\ switch(sign) { case 0: break;//退出 case 1: { printf(\你选择的操作是多项式相加:\\n\ a=creat('A');//输入多项式f(x) printf(\ print(a); b=creat('B');//输入多项式g(x) printf(\ print(b); printf(\ a=addLink(a,b);//两个多项式相加 print(a); sign=-1;//复位标志 start();//回复用户选择界面 break; } case 2: { printf(\你选择的操作是多项式相减:\\n\ a=creat('A');//输入多项式A(x) printf(\ print(a); b=creat('B');//输入多项式B(x) printf(\ print(b); printf(\ a=cutLink(a,b);//两个多项式相减 print(a); sign=-1;//复位标志 start();//回复用户选择界面 break; } default: { printf(\输入有误!请重新选择操作!\\n\选择错误,返回选择界面 start(); break; } } } } void start()//用户选择界面 { printf(\ printf(\两个一元多项式的相加/相减:\\n\ printf(\ printf(\请选择操作:\\n\ printf(\退出\\n\ printf(\两个一元多项式相加\\n\ printf(\两个一元多项式相减\\n\ } struct Link *creat(char ch) { void insert(struct Link *head,struct Link *inpt); struct Link *head,*inpt; int x; int y; head=(struct Link *)malloc(LEN);//创建链表头 head->next=NULL; printf(\ scanf(\ while(x!=0) { inpt=(struct Link *)malloc(LEN); inpt->c=x; inpt->e=y; inpt->next=NULL; insert(head,inpt);//将这个结点插到有序链表中 printf(\请输入一元多项式%c(x)的下一项:(The end: 0 0)\\n\ scanf(\ } return head; } void insert(struct Link *head,struct Link *inpt) { struct Link *pre,*now; int signal=0; pre=head;//pre定义为现在的前一个结点 if(pre->next==NULL) pre->next=inpt; else { now=pre->next; while(signal==0) { if((inpt->e)<(now->e))//当新链节小于现在的连接时向后移一个链节 { if(now->next==NULL) { now->next=inpt; signal=-1; } else { pre=now; now=pre->next; } } else if((inpt->e)>(now->e))//如果发现比现在的链节大了就插入到这个连接的前面 { inpt->next=now; pre->next=inpt; signal=1; } else { now->c=now->c+inpt->c; signal=1; free(inpt); if(now->c==0) { pre->next=now->next; free(now); } } } } } struct Link *addLink(struct Link *head,struct Link *pre)//多项式相加 { struct Link *inpt; int flag=0; while(flag==0) { if(pre->next==NULL) flag=1; else { pre=pre->next; inpt=(struct Link *)malloc(LEN); inpt->c=pre->c; inpt->e=pre->e; inpt->next=NULL; insert(head,inpt); }//将B(x)中的结点依次插入A(x)中(相加) } return head; } struct Link *cutLink(struct Link *head,struct Link *pre)//多项式相减 { struct Link *inpt; int flag=0; while(flag==0) { if(pre->next==NULL) flag=1; else { pre=pre->next; inpt=(struct Link *)malloc(LEN); inpt->c=0-pre->c; inpt->e=pre->e; inpt->next=NULL; insert(head,inpt); }//将B(x)中的结点依次插入A(x)中(相减) } return head; } void print(struct Link *p) //输出多项式 { } struct Link *now; int flag=0; now=p->next;//now表示输出的信息，从头开始 if(p->next==NULL) { printf(\ return; } while(flag==0) { if((now->c)>0 && (p->next)!=now) printf(\ if(now->c==1); //如果系数是1，就不用输出该系数了 else if(now->c==-1)//如果是-1，就只需输出\号 printf(\ else printf(\其他情况都做输出 if(now->e!=0) printf(\ else if((now->c==1)||(now->c==-1)) printf(\ if(now->next==NULL) flag=1; else now=now->next; } printf(\ 题目6：床位分配（学时：6） 某客店有N个等级的房间，第k级客房有A（k）个，每个房间有B（k）个单人床，以菜单调用方式设计为单身旅客分配床位以及离店时收回床位的程序。要求分配成功时，印出旅客姓名、年龄、性别、到达日期、客房等级、房间号及床位号；分配不成功时，允许更改房间等级，若不更改等级，印出“满客”提示。 //本人编写 #include typedef struct customer //旅客结构体 { char name[6];//姓名 int age;//年龄 int sex;//性别 int level;//房间等级 int bed_num;//房间号 char date[100]; struct customer *next; }customer; typedef struct hotel_level //旅店等级结构体 { int lv_num;//等级数目 struct hotel_level *next;//该结构体指针 指向下一个等级 struct room *next_r;//定义房间指针 指向下一个房间（等级划分下的房间指针） }hotel_lv; typedef struct room //房间结构体 { int r_num;//房间号 int max;//最大值 int member_num;//成员数 struct room *next;//定义房间指针 指向下一个房间（房间相指） struct customer *next_cus;//房间里的顾客指针 房间指向顾客 }room; void Init(hotel_lv *L) //初始化函数 { int i,j,k,l; hotel_lv *p,*q; room *p1,*p2,*p3; printf(\请输入房间分为几个等级: \ scanf(\ q=L; //等级设置了头结点 for(i=1;i<=j;i++) //创建等级-房间-床位数 { p=(hotel_lv *)malloc(sizeof(hotel_lv));//开辟等级结点 q->next=p; p->lv_num=i; //给房间等级赋值 printf(\请输入%d等级的房间个数: \ scanf(\ //输入该等级的房间数目 if(l==0) continue; else { p2=(room *)malloc(sizeof(room)); p2->r_num=1; printf(\请输入%d等级的房间号为1的房间床位个数的最大值: \ scanf(\ //输入房间1的床位数目 p2->member_num=0; //该房间内当前人数赋为零 p->next_r=p2; p3=p2; for(k=2;k<=l;k++) { p1=(room *)malloc(sizeof(room)); p3->next=p1; p1->r_num=k; printf(\请输入%d等级的房间号为%d的房间床位个数的最大值: \ scanf(\ //输入房间k的床位数目 p1->member_num=0; //该房间内当前人数赋为零 p3=p1; } p3->next=NULL; //该等级房间床位设置结束，房间链表尾指针赋为空 } q=q->next; //等级指针指向下一个等级 } q->next=NULL; //所有等级设置结束，等级链表尾指针域赋为空 } int full(hotel_lv *L) //是否客满函数 { hotel_lv *l; l=L->next; room *r; while(l!=NULL) { r=l->next_r; while(r!=NULL) { if(r->member_num!=r->max) //如果有房间的当前人数不等于房间的最大人数，则返回0 return 0; else r=r->next; //否则指向下一个房间 } l=l->next; //否则指向下一个等级 } if(!l) return 1; } void press(customer *p,room *q) { printf(\ _____________________________________________________________________________\\n\ printf(\ 旅客房间分配表 |\\n\ printf(\ printf(\ 姓名 | 性别 | 年龄 | 等级号 | 房间号 | 床位号 | 入住时间 |\\n\ printf(\ printf(\%6s | %d | - | - | - | - |%s\ printf(\_______________|\\n\ printf(\} void input(hotel_lv *L) //旅客入住函数 { time_t rawtime; struct tm * timeinfo; char c; customer *s,*p2,*p3; hotel_lv *l; l=L->next; room *p1; int i,lv; s=(customer *)malloc(sizeof(customer)); printf(\ printf(\ 旅客信息: \ printf(\ 请输入旅客姓名:\ scanf(\ printf(\ 请输入旅客年龄:\ scanf(\ printf(\ 请输入旅客性别(男1 女0):\ scanf(\ time ( &rawtime ); timeinfo = localtime ( &rawtime); strcpy(s->date,asctime (timeinfo) ); if(full(L)) { printf(\ 旅店客满 ，不能入住。\\n\ } else { printf(\请输入旅客所需的房间等级:\ //输入旅客所需的等级 scanf(\ while(l!=NULL) //等级不为空时 { if(l->lv_num!=lv) l=l->next; else //符合旅客需求的等级时 { p1=l->next_r; while(p1!=NULL) //当房间不为空时 { if(p1->member_num==p1->max) //房间满时访问下一个房间 { p1=p1->next; if(p1==NULL) { getchar(); printf(\此等级为%d的所有房间均无空位\\n是否愿意更换等级[y/n]\ scanf(\ //做出选择 if(c=='y') input(L); else return ; } } else //进行旅客登记 { //因为床位没有设置头结点，所以对于第一个结点要特别判断 if(p1->member_num==0) { s->level=lv; p1->next_cus=s; 时，输入旅客信息 p1->member_num++; //房间当前人数加1 s->bed_num=1; // 顾客床位号 s->next=NULL; //尾指针置为空 press(s,p1); //打印房间分配表 break; } else { p2=p1->next_cus; p3=p2; i=1; while(i<=p1->member_num) { if(i==p3->bed_num) { p3=p3->next; i++; } else { i++; break; } } if(p3==NULL)//如果p3是最后一个结点（NULL的） { s->level=lv; while(p2->next!=p3) p2=p2->next; if(s->sex==p2->sex) { p2->next=s; p1->member_num++; s->bed_num=i; s->next=NULL; press(s,p1); break; } else p1=p1->next; } else { while(p2->bed_num==i) p2=p2->next; if(s->sex==p2->sex) { p2->next=s; p1->member_num++; s->bed_num=i; s->next=NULL; press(s,p1); break; } else p1=p1->next; } } } } break; } } } } customer *Delete(hotel_lv *L) 房函数 { int lv,hotel_num,bed_num; hotel_lv *l; l=L->next; room *r; customer *p,*q; char c; printf(\请输入该退房人房间的等级号码：\\n\ scanf(\ 输入退房人的房间等级 getchar(); while(l!=NULL) { if(l->lv_num!=lv) l=l->next; else 到该等级 { r=l->next_r; //旅客退 // //找 printf(\请输入该退房人房间的房间号码：\\n\ scanf(\ //输入退房人的房间号码 getchar(); while(r!=NULL) { if(r->r_num!=hotel_num) r=r->next; else //找到该房间 { p=r->next_cus; q=r->next_cus; printf(\请输入该退房人的床位号码：\\n\ scanf(\ //输入退房人的床位号码 getchar(); while(q!=NULL) { if(q->bed_num!=bed_num) q=q->next; else //查找该床位 { if(bed_num==1) //因为床位没有设置头结点，所以对于第一个结点要特别判断 { //直接打印旅客信息 printf(\此等级、此房间、此床位旅客的信息为：\\n\ printf(\该名顾客的信息:\\n\ printf(\姓名\\t性别\\t年龄\\t入住时间\\n\ printf(\ printf(\是否与要退房人信息相符？[y/n]\\n\ scanf(\ if(c=='y') //做出是否退房的选择 { r->member_num--; printf(\退房成功！\\n\ return(q); } else return NULL; } else //如果床位不为1 { while(p->next!=q) //指向下一床位 通过循环找到该床位 p=p->next; //打印旅客信息 printf(\此等级、此房间、此床位旅客的信息为：\\n\ printf(\该名顾客的信息:\\n\ printf(\姓名\\t性别\\t年龄\\t入住时间\\n\ printf(\ printf(\是否与要退房人信息相符？[y/n]\\n\ scanf(\ if(c=='y') //做出是否退房的选择 { p->next=q->next; r->member_num--; printf(\退房成功！\\n\ return(q); } else return NULL; } } } if(q==NULL) //如果该房间内床位为空 { printf(\未找到该床位号，请核实信息后重新输入。\\n\ } } } if(r==NULL) //如果该等级的房间为空 { printf(\未找到该房间号，请核实信息后重新输入。\\n\ } } } if(l==NULL) //如果等级链表为空 { printf(\未找到该房间等级，请核实信息后重新输入。\\n\ } } void cx_customer(hotel_lv *L) //查询旅客信息函数 { char s[15]; hotel_lv *l; room *r; customer *t; int flag=0; 置标志量 printf(\请输入要查询的旅客姓名：\\n\ scanf(\ 要查找旅客的姓名 getchar(); l=L->next; while(l!=NULL) 级不为空时，走向房间 { r=l->next_r; while(r!=NULL) 间不为空时，走向床位 { if(r->member_num==0) 人数为零，走向下一房间 r=r->next; else { t=r->next_cus; while(t!=NULL) { if(!strcmp(t->name,s)) 客 { press(t,r); t=t->next; 继续查找 flag++; } else t=t->next; //设 //输入 //等 //房 //若此房间当前 //如果找到该旅//打印信息 //指向下一人， //标志量加1 } r=r->next; } } l=l->next; } if(!flag) //标志量为零，则未查找到 printf(\未找到该旅客，请核实后再输入。\\n\} //统计函数与查询旅客信息函数基本类似 void Tongji_cus(hotel_lv *L) 当前住宿人数函数 { hotel_lv *l; room *r; customer *t; int i=0,j=0; int flag; l=L->next; while(l!=NULL) { flag=0; i++; r=l->next_r; while(r!=NULL) { if(r->member_num==0) r=r->next; else { t=r->next_cus; while(t!=NULL) { flag++; j=j+flag; t=t->next; } r=r->next; } } printf(\等级为%d的房间入住人数为%d\\n\ l=l->next; //统计旅店 } if(!j) printf(\此时无人住宿。\\n\} void main() //主函数 { hotel_lv *L; customer *p; int c; L=(hotel_lv*)malloc(sizeof(hotel_lv)); printf(\初始化旅店信息：\\n\ Init(L); while(1) { //进入菜单选项 printf(\ printf(\ **************************************************************\\n\ printf(\ * *\\n\ printf(\ * 欢迎登陆某旅店住宿管理系统 *\\n\ printf(\ * *\\n\ printf(\ **************************************************************\\n\ printf(\ 1. 录入旅客信息\\n\ printf(\ 2. 旅客退房 \\n\ printf(\ 3. 查询旅客信息\\n\ printf(\ 4. 统计旅客信息\\n\ printf(\ 5. 退出本程序 \\n\ printf(\ 请选择1-5： \\n\ scanf(\ //做选择 getchar(); switch(c) { case 1: input(L); break; case 2: p=Delete(L);free(p); break; case 3: cx_customer(L); break; case 4: Tongji_cus(L); break; case 5: return; } } }
兰州大学数据结构课程设计2
