兰州大学数据结构课程设计3.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 中出现的元素。另外该任务要求具有建立有序表功能以及输出有序表到屏幕的功能。 题目 5：一元多项式的减法（学时：6） 设有两个一元多项式 A(x),B(x)，请完成运算 A(x)+B(x)、A(x)-B(x)，要求多项式采用链表进行存储。另外该任务要求具有建立多项式链表以及输出多项式到屏幕的功能。 题目 6：床位分配（学时：6） 某客店有 N 个等级的房间，第 k 级客房有 A（k）个，每个房间有 B（k）个单人床，以菜单调用方式设计为单身旅客分配床位以及离店时收回床位的程序。要求分配成功时，印出旅客姓名、年龄、性别、到达日期、客房等级、房间号及床位号；分配不成功时，允许更改房间等级，若不更改等级，印出“满客”提示。 题目 7：文本文件单词的检索及计数（学时：6） 要求编程建立一个文本文件，每个单词不包括空格及跨行，单词由字符序列构成且区分大小写，完成以下功能：统计给定单词在文本文件中出现的总次数、检索输出某单词在文本文件中首次出现的行号及位置。 #includestdio.h #includestdlib.h #includemalloc.h #includestring.h #define N 250 typedef struct Cstring //定义结构体(字符长串） { char string[N]; }Cstring; typedef struct File //定义结构体（文件） { Cstring filename[N];//文件数组 FILE *in, *out; //文件指针（入/出） int line[N], filenum ; //行编号，文件编号 }File; typedef struct Line //结构体（行） { int pos[N],counter;//所在行号，计数器 }Line; int Length(char* a)//函数（判断单词是否结束）返回单词长度 { int i=0; while(a[i]!=\0a[i]!=\n) i++; return i; } int Index(Cstring a,Cstring b,Line* l)//索引（字符总串，单词，要查找的字符总串第几行） { int i,k,j,p=1,num=0; l-counter=0; Cstring temp; while(p=a.string[0])//sring[0]用于存字符串大小 { i=1; while(a.string[p]!= a.string[p]!=\0a.string[p]!=,a.string[p]!=.)//将字符总串的一个单词放到 temp 中，并没进行一次，num++ { temp.string[i]=a.string[p]; i++; p++; } temp.string[i]=\0; temp.string[0]=Length((temp.string[1])); num++; k=1; j=1; if(temp.string[0]==b.string[0]) { while(j=b.string[0]) { if(temp.string[k]==b.string[j]) { k++; j++; } else break; } } if(jb.string[0])//说明 2 个单词相同 { 个单词) } l-pos[l-counter]=num;//该行第 l-co