兰州大学数据结构课程设计4讲解

1、数据结构课程设计题目 （程序实现采用 C 语言） 题目 1：猴子选王（学时：3） 一堆猴子都有编号，编号是 1，2，3 .m ，这群猴子（ m个）按照 1-m的顺 序围坐一圈，从第 1 开始数，每数到第 n 个，该猴子就要离开此圈，这样依次下 来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求： m及 n 要求从键盘输入，存储方式采用向量及链表两种方式实现该问 题求解。 题目 2 ：字符逆转（学时：3） 从键盘读入一个字符串，把它存入一个链表（每个结点存储 1 个字符），并 按相反的次序将字符串输出到显示屏。 题目 3 ：工资核算（学时：3） 设有一个单位的人员工资有如下信息：name、

2、department 、 base pay 、 allowance 、 total 。现从键盘输入一组人员工资数据并将它们存储到名为 paydata 的文件中； 再从 paydata 取出工资数据并给每个人的 base pay 增加 100 元，增加后将工资数据显示于屏幕 （ 每行 1 人 ） 。 题目 4：满足条件的有序表生成（学时：3） 已知三个有序表 A、B、C，它们皆由同一类元素构成，现要求对于表 A 作以 下运算而获得有序表 D：排出 A中所有的既在 B 中又在 C中出现的元素。另外该 任务要求具有建立有序表功能以及输出有序表到屏幕的功能。 题目 5：一元多项式的减法（学时：6） 设

3、有两个一元多项式 A（x）,B（x） ，请完成运算 A（x）+B（x） 、A（x）-B（x） ，要求多项 式采用链表进行存储。 另外该任务要求具有建立多项式链表以及输出多项式到屏 幕的功能。 题目 6：床位 分配（学时：6） 某客店有 N个等级的房间，第 k 级客房有 A（k）个，每个房间有 B（k）个 单人床，以菜单调用方式设计为单身旅客分配床位以及离店时收回床位的程序。 要求分配成功时，印出旅客姓名、年龄、性别、到达日期、客房等级、房间号及 床位号； 分配不成功时， 允许更改房间等级， 若不更改等级， 印出“满客” 提示。 题目 7：文本文件单词的检索及计数（学 时：6） 要求编程建立一个

4、文本文件， 每个单词不包括空格及跨行， 单词由字符序列 构成且区分大小写，完成以下功能：统计给定单词在文本文件中出现的总次数、 检索输出某单词在文本文件中首次出现的行号及位置。 题目 8：二叉 树的遍历（学时：6） 二叉树以 lson-rson 链接方式存储， 以菜单方式设计并完成功能任务： 建立 并存储树、输出前序遍历结果、输出中序遍历结果、输出后序遍历结果、交换左 右子树、统计高度，其中对于中序、后序的遍历运算要求采用非递归方式。 题目 9：创建 二叉排序树（学时： 3） 二叉排序树以 lson-rson 链接方式存储， 编写能够通过键盘输入建立二叉排 序树，并在建立完立即在屏幕显示中序遍

5、历结果的程序。 题目 10：霍夫曼编码应用（学时：3） 假设一串由大写字母构成的电文， 采用霍夫曼规则对其进行编码， 以菜单方 式设计并完成功能任务：建立霍夫曼树、霍夫曼编码生成、编码文件译码。 #include #include #include #define n 100 #define m 2*n-1 typedef struct / 码结点的存储结构 char ch; char bits9; int len; CodeNode; typedef CodeNode HuffmanCoden+1; typedef struct / 树结点的存储结构 int weight; int lchi

6、ld,rchild,parent; HTNode; typedef HTNode HuffmanTreem+1; int num; void select(HuffmanTree HT,int k,int int minl=32767; for(i=1;i=k;i+) if(HTi.weightminl minl=HTi.weight; s1=j; minl=32767; for(i=1;i=k;i+) if(HTi.weightminl minl=HTi.weight; s2=j; int jsq(char *s,int cnt,char str)/ 统计输入字符和串 char *p; in

7、t i,j,k=0; int temp257; for(i=0;i257;i+) tempi=0; for(p=s;*p!=0;p+) temp*p+; for(i=0,j=0;i=256;i+) if(tempi!=0) j+; strj=i; cntj=tempi; num=j; return j; /建立霍夫曼树 void chuffmanTree(HuffmanTree for(i=1;i=2*num-1;i+) HTi.lchild=0; HTi.rchild=0; HTi.parent=0; HTi.weight=0; for(i=1;i=num;i+) HTi.weight=cn

8、ti; for(i=num+1;i=2*num-1;i+) select(HT,i-1,s1,s2); HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; for(i=1;i=num;i+) HCi.ch=stri; /给霍夫曼树的每个叶子节点分配二进制代码 void HuffmanEncoding(HuffmanTree HT,HuffmanCode HC) int c,p,i; char cdn; int start; cdnum=0; 进制编码串 f

9、or(i=1;i0) start-; cdstart=(HTp.lchild=c)?0:1; c=p; strcpy(HCi.bits, HCi.len=num-start; void decode(HuffmanCode HC,char receive,char s)/ 译码 char str268; char cd9; int i,j,k=0,p=0,cjs; while(receivep!=0) cjs=0; for( i=0;inumi+) cdi= ; cdi+1=0; cdi=receivep+; for(j=1;j=num;j+) if(strcmp(HCj.bits,cd)=0

10、) strk=HCj.ch; k+; cjs = 1; break; strk=0; strcpy(s,str); void coding(HuffmanCode HC,char str,char get)/ 输出字符串的二进制编码 int i,j=0; while(strj!=0) for(i=1;i=num;i+) if(HCi.ch = strj) strcat(get,HCi.bits); break; j+; strcat(get,0); void main() /str 用于在统计输入序列中的字母时用，存放是什么字 char str257; 符， 1 到 256 char st10

11、000,s10000; /st 用来接收输入的字符串， s用来接收解压的字符串 int cn257; /cn 用于接收统计后的每个字符的频率， 1 到 256 HuffmanTree HT; HuffmanCode HC; char ch=y;int d,i; printf( 霍夫曼树 nn); printf(1.建立霍夫曼树 .n); printf(2.生成霍夫曼编码 .n); printf(3.编码文件译码 .n); while(ch=y) printf( 请选择 :); scanf(%d, switch(d) case 1: printf( 输入要编码的字符串： ); scanf(%s,

12、 num=jsq(st,cn,str); /统计文件中的字符 strnum+1 = 0; chuffmanTree(HT,HC,cn,str); printf( 霍夫曼树建立成功 !n);/ 建立霍夫曼树 break; case 2: HuffmanEncoding(HT,HC);/根据霍夫曼树建立霍夫曼编码 printf( 建立霍夫曼编码如下 n 共有 %d 种字符 n,num); for(i=1;i=num;i+) printf( 字符 %c 次数为 %d, 编码为 %sn,HCi.ch,cni,HCi.bits); char get10000; get0 = 0; coding(HC,s

13、t,get); printf(n 上述字符串的霍夫曼码为 %sn,get); / printf( 编码效率为 %f%n,code_ratio(st,cn,HC); break; case 3: printf( 输入二进制码开始译码： ); char receive10000; scanf(%s, decode(HC,receive,s);/ 译码 printf( 译码为： %sn,s); break; printf(n 是否继续？ (y/n):); scanf(%c, scanf(%c, 题目 11：关键路径寻找(学时：6) 对于给定的一个工程施工图，该图以边为单位从键盘输入，编写能够找出该

14、图的关键路径的程序。 #includestdio.h #includestdlib.h #define LEN sizeof(struct Enode) typedef struct Vexnode /顶点表 int adjvex;/ 邻接域 int dut;/ 记录权值 struct Vexnode * next; vexnode; typedef struct Enode int indegree; int vertex; int ee,el; struct Vexnode * link; /记录入度 /顶点 /记录最迟开始时间和最早结束时间 enode; void print(enode

15、 dig,int first,int len) int i,j; static int top=0,list50; vexnode * q; i=first; q=digi.link; listtop=digi.vertex; top+; if (q=NULL) printf(%d,listlen); for (i=1+len;i%d,listi); printf(n); while (q!=NULL) j=q-adjvex; if (digj.ee=digj.el) listtop=digj.vertex; print(dig,j,len); / q=q-next; top-;/ int t

16、oposort(enode dig,int e_n,int stacktp) /进栈 int top=0,bottom=0,i,j,len=0; vexnode *q; for (i=1; ibottom) i=stacktpbottom; q=digi.link; bottom+; while (q!=NULL) j=q-adjvex; digj.indegree-; if (digi.ee+q-dutdigj.ee) 时间 digj.ee=digi.ee+q-dut; if (digq-adjvex.indegree=0) stacktptop=q-adjvex; top+; q=q-ne

17、xt; if (top=e_n) 存在，则求出最迟结束时间 for (i=1; ibottom) top-; 一个事件开始倒推 i=stacktptop; q=digi.link; while (q!=NULL) j=q-adjvex; if (digj.el-q-dutdut; q=q-next; for (i=0; ilen; i+) print(dig,stacktpi,i); return 0; else return 1; void main() enode dig20; / 顶点表数组 vexnode *q;/邻接点链表 char ch; int e_n,v_n,m,i,j,u,v

18、,stacktp20; printf( 关键路径 nn); printf( 请输入顶点个数和边的条数： ); scanf(%d%d, for (i=1; i=e_n; i+)/ 初始化 digi.indegree=0; digi.link=NULL; digi.vertex=i; digi.ee=digi.el=0; printf( 请输入 %d 条边以及该边的权： n,v_n); for (i=0; iadjvex=v; q-dut=j; q-next=digu.link;/ 将 q 结点 放入 u 邻接链表中 digu.link=q;/将 q 结点 放入 u 邻接链表中 m=toposor

19、t(dig,e_n,stacktp); /拓扑排序 if (m) printf( 图中存在环，不存在关键路径 n); else printf( 需要各点明细查询吗 y/n); scanf(n%c,; if (ch=y|ch=Y) for (i=0; ie_n; i+) printf(%d (%d %d) n,stacktpi,digstacktpi.ee,digstacktpi.el); 题目 12：堆排序实现(学时：3) 假设有一个数据类型为整型的一维数组 A，A 中的数据元素呈无序状态，编 写一个采用堆排序法将 A 中的数据元素按由小到大进行排序的程序。 #include #define

20、MAX 255 int AMAX; void creatdui(int l,int m) /* 建初始堆过程函数 */ int i,j,x; i=l; j=2*i; /*Rj 是 Ri 的左孩子 */ x=Ai; while(j=m) if(jm /* 若左孩子较大，则把 j 修改为右孩子的下标 */ if(x=1;i-) creatdui(i,n); /* 建立初始堆，遍布所有的根结点 */ for(i=n;i=2;i-) /* 进行 n-1 次循环完成堆排序 */ m=Ai; Ai=A1; /* 将第一个元素同当前区域的最后一个元素对换 */ A1=m; creatdui(1,i-1);

21、/* 筛选 A1 结点，得到 i-1 个结点的堆，仅有 A1 可能违反堆性质 */ void main() int i,n; printf( 堆排序 nn); printf( 输入整型一维数组 A 中数字总数 :); scanf(%d, if(nMAX) printf(n 输入的数据有误 !); return; printf(n 请输入整型无序序列 :n); for(i=1;i=n;i+) scanf(%d, printf(n 该序列为 :n); for(i=1;i=n;i+) printf(%4d,Ai); sortdui(n); printf(n 堆排序后的序列为 :n); for(i=1

22、;i=n;i+) printf(%4d,Ai); printf(n); 题目 13基数排序的实现(学时：3) A为每个关键字不超过 3 位的十进制整数关键字集合， 试编写一个采用静态 链表组织模式实现的基数排序程序将 A 进行由小到大的排序。 #include #include #define N 1024 int RadixCountSort(int* npIndex, int nMax, int* npData, int nLen) int* pnCount=(int*)malloc(sizeof(int)* nMax);/保存计数的个数 int i=0; for (i=0;inMax;+i) pnCounti=0; for (i=0;inLen;+i) / 初始化计数个数 +pnCountnpIndexi; for (i=1; i=0;-i) -pnCountnpIndexi; pnSortpnCountnpInde