兰州大学数据结构课程设计4概要

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

2、se pay、 allowanee、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）-

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

4、在文本文件中出现的总次数、 检索输出某单词在文本文件中首次出现的行号及位置。 题目 8：二叉 树的 遍历（学时：6） 二叉树以 lson-rson 链接方式存储， 以菜单方式设计并完成功能任务： 建立 并存储树、输出前序遍历结果、输出中序遍历结果、输出后序遍历结果、交换左 右子树、统计高度，其中对于中序、后序的遍历运算要求采用非递归方式。 题目 9：创建 二叉排序树（ 学时： 3） 二叉排序树以 lson-rson 链接方式存储， 编写能够通过键盘输入建立二叉排 序树，并在建立完立即在屏幕显示中序遍历结果的程序。 题目 10：霍夫曼编码应用（学时：3） 假设一串由大写字母构成的电文， 采用霍夫

5、曼规则对其进行编码， 以菜单方 式设计并完成功能任务：建立霍夫曼树、霍夫曼编码生成、编码文件译码。 #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 lchild,rchild,parent; HTNode; typedef HTNode Huffman

6、Treem+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(HTi.weightminl&HTi.parent=0) j=i; minl=HTi.weight; s1=j; minl=32767; for(i=1;i=k;i+) if(HTi.weightminl&HTi.parent=0&i!=s1) j=i; minl=HTi.weight; s2=j; int

7、jsq(char *s,int cnt,char str)/ 统计输入字符和串 char *p; int 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&HT,HuffmanCode&HC,int cnt,char str) int i,s1,s2; f

8、or(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=cnti; 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; /给霍夫曼树的每个叶子节点

9、分配二进制代码 void HuffmanEncoding(HuffmanTree HT,HuffmanCode HC) int c,p,i; char cdn; int start; cdnum=0; for(i=1;i0) start-; cdstart=(HTp.lchild=c)?0:1; c=p; strcpy(HCi.bits,&cdstart); HCi.len=num-start; void decode(HuffmanCode HC,char receive,char s)/ 译码 char str268; char cd9; int i,j,k=0,p=0,cjs;

10、while(receivep!=0) cjs=0; for( i=0;inum&cjs=0&receivep!=0;i+) cdi= ; cdi+1=0; cdi=receivep+; 进制编码串 for(j=1;j=num;j+) if(strcmp(HCj.bits,cd)=0) 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;

11、i=num;i+) if(HCi.ch = strj) strcat(get,HCi.bits); break; j+; strcat(get,0); void main() char str257; 符， 1 到 256 char st10000,s10000; /st用来接收输入的字符串， s用来接收解压的字符串 int cn257; /cn 用于接收统计后的每个字符的频率， 1 到 256 HuffmanTree HT; HuffmanCode HC; char ch=y;int d,i; printf( - 霍夫曼树 -nn); printf( 1 .建立霍夫曼树 .n); print

12、f( 2.生成霍夫曼编码 .n); printf( 3.编码文件译码 .n); while(ch=y) printf( 请选择 :); scanf(%d,&d); switch(d) case 1: printf( 输入要编码的字符串： ); scanf(%s,&st); num=jsq(st,cn,str); /统计文件中的字符 strnum+1 = 0; chuffmanTree(HT,HC,cn,str); printf( 霍夫曼树建立成功 !n);/ 建立霍夫曼树 break; case 2: HuffmanEncoding(HT,HC); /根据霍夫曼树建立霍夫曼编码

13、 printf( 建立霍夫曼编码如下 n 共有 %d 种字符 n,num); /str 用于在统计输入序列中的字母时用，存放是什么字 for(i=1;i=num;i+) printf( 字符 %c 次数为 %d, 编码为 %sn,HCi.ch,cni,HCi.bits); char get10000; get0 = 0; coding(HC,st,get); printf(n 上述字符串的霍夫曼码为 %sn,get); / printf( 编码效率为 %f%n,code_ratio(st,cn,HC); break; case 3: printf( 输入二进制码开始译码： ); char re

14、ceive10000; scanf(%s,&receive); decode(HC,receive,s);/ 译码 printf( 译码为： %sn,s); break; printf(n 是否继续？ (y/n):); scanf(%c,&ch); scanf(%c,&ch); 题目 11：关键路径寻找(学时：6) 对于给定的一个工程施工图，该图以边为单位从键盘输入，编写能够找出该 图的关键路径的程序。 #includestdio.h #includestdlib.h #define LEN sizeof(struct Enode) typedef struct Vex

15、node /顶点表 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 dig,int first,int len) int i,j; static int top=0,list50; vexnode * q; i=first; q=digi.link;

16、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 toposort(enode dig,int e_n,int stacktp) /进栈 int top=0,bottom=0,i,j,len=0; vexnode *q; for (i=1

17、; 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-next; if (top=e_n) 存在，则求出最迟结束时间 for (i=1; ibottom) top-; 一个事件开始倒推 i=stacktptop; q=digi.link; wh

18、ile (q!=NULL) j=q-adjvex; if (digj.el-q-dutdut; q=q-next; for (i=0; ilen; i+) print(dig,stacktpi,i); return 0;/拓扑排序 /入度 - /求一下最早开始 /入度为 0 则进栈 / 表示没有环 /先初始化一下 /栈非空 / 从最后的 else return 1; void main() enode dig20; / 顶点表数组 vexnode *q; /邻接点链表 char ch; int e_n,v_n,m,i,j,u,v,stacktp20; printf(- 关键路径 -nn); p

19、rintf( 请输入顶点个数和边的条数： ); scanf(%d%d,&e_n,&v_n); 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=toposort(dig,e_n,

20、stacktp); /拓扑排序 if (m) printf( 图中存在环，不存在关键路径 n); else printf( 需要各点明细查询吗 y/n); scanf(n%c,&ch); 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 MA

21、X 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&AjAj+1)j+; /* 若左孩子较大，则把 j 修改为右孩子的下标 */ if(x=1;i-) creatdui(i,n); /* 建立初始堆，遍布所有的根结点 */ for(i=n;i=2;i-) /* 进行 n-1 次循环完成堆排序 */ m=Ai; Ai=A1; /* 将第一个元素同当前区域的最后一个元素对换 */ A1=m; crea

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

23、); printf(n 堆排序后的序列为 :n); for(i=1;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; pnSortpnCou