兰州大学数据结构课程设计4.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） 要求编程建立一个文本文件，每个单词不包括空格及跨行，单词由字符序列构成且区分大小写，完成以下功能：统计给定单词在文本文件中出现的总次数、检索输出某单词在文本文件中首次出现的行号及位置。 题目 8：二叉树的遍历（学时：6） 二叉树以 lson-rson 链接方式存储，以菜单方式设计并完成功能任务：建立并存储树、输出前序遍历结果、输出中序遍历结果、输出后序遍历结果、交换左右子树、统计高度，其中对于中序、后序的遍历运算要求采用非递归方式。 题目 9：创建二叉排序树（学时：3） 二叉排序树以 lson-rson 链接方式存储，编写能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示中序遍历结果的程序。 题目 10：霍夫曼编码应用（学时：3） 假设一串由大写字母构成的电文，采用霍夫曼规则对其进行编码，以菜单方式设计并完成功能任务：建立霍夫曼树、霍夫曼编码生成、编码文件译码。 #includestdio.h #includestring.h #includemath.h #define n 100 #define m 2*n-1 typedef struct //码结点的存储结构 { char ch; char bits[9]; int len; }CodeNode; typedef CodeNode HuffmanCode[n+1]; typedef struct //树结点的存储结构 { int weight; int lchild,rchild,parent; }HTNode; typedef HTNode HuffmanTree[m+1]; int num; void select(HuffmanTree HT,int k,int s1,int s2)//挑选权值最小的两个结点 { int i,j; int minl=32767; for(i=1;i=k;i++) if(HT[i].weightminlHT[i].parent==0) { } s1=j; j=i; minl=HT[i].weight; minl=32767; for(i=1;i=k;i++) if(HT[i].weightminlHT[i].parent==0i!=s1) { j=i; minl=HT[i].weight; } s2=j; } int jsq(char *s,int cnt[],char str[])//统计输入字符和串 { char *p; int i,j,k=0; int temp[257]; for(i=0;i257;i++) temp[i]=0; for(p=s;*p!