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

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

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

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

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

5、霍夫曼编码生成、编码文件译码。#include<stdio.h> #include<string.h> #include<math.h> #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 Huffm

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

7、inl=HTi.weight; s2=j;int jsq(char *s,int cnt,char str)/ 统计输入字符和串 char *p;int i,j,k=0;int temp257;for(i=0;i<257;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

8、cnt,char str) int i,s1,s2;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=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;

9、i+)HCi.ch=stri;/给霍夫曼树的每个叶子节点分配二进制代码void HuffmanEncoding(HuffmanTree HT,HuffmanCode HC) int c,p,i;char cdn; int start;cdnum='0'for(i=1;i<=num;i+)/1 到 num 为叶子节点，每个节点都有二进制编码串start = num ;c=i;while(p=HTc.parent)>0) start-;cdstart=(HTp.lchild=c)?'0':'1' c=p;strcpy(HCi.bits,&

10、amp;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; while(receivep!='0')cjs=0;for( i=0;i<num&&cjs=0&&receivep!='0'i+)cdi=' 'cdi+1='0'cdi=receivep+;for(j=1;j<=num;j+)if(strcm

11、p(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;i<=num;i+)if(HCi.ch = strj) strcat(get,HCi.bits);break;j+;strcat(get,"0");void main()char str257;符， 1 到 256ch

12、ar st10000,s10000; int cn257; HuffmanTree HT; HuffmanCode HC; char ch='y'int d,i; printf(" printf(" printf(" printf("/str 用于在统计输入序列中的字母时用，存放是什么字/st 用来接收输入的字符串， s 用来接收解压的字符串/cn 用于接收统计后的每个字符的频率， 1 到 256霍夫曼树 nn");1.建立霍夫曼树 .n");2.生成霍夫曼编码 .n");3.编码文件译码 .n")

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

14、reak;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,st,get);printf("n 上述字符串的霍夫曼码为 %sn",get);printf(" 编码效率为 %f%n",code_ra

15、tio(st,cn,HC); break;printf(" 输入二进制码开始译码： "); char receive10000;scanf("%s",&receive); decode(HC,receive,s);/ 译码 printf(" 译码为： %sn",s); break;是否继续？ (y/n):");printf("n scanf("%c",&ch); scanf("%c",&ch);题 目 11：关 键 路径寻找 (学时 ：6)对于给定的一

16、个工程施工图，该图以边为单位从键盘输入，编写能够找出该图的关键路径的程序。#include"stdio.h"#include"stdlib.h"#define LEN sizeof(struct Enode) typedef struct Vexnode/顶点表int adjvex;/邻接域int dut;/记录权值struct Vexnode * next;vexnode;typedef struct Enodeint indegree;int vertex;int ee,el;struct Vexnode * link;enode;void prin

17、t(enode 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<top;i+) printf("->%d",listi); printf("n");while (q!=NULL) j=q->adjv

18、ex; 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; i<=e_n; i+)if (digi.indegree=0)/入度为 0 则进栈stacktptop=i;/拓扑排序/入度 -/求一下最早开始top+; len=top;while (top>bottom)i=stacktpb

19、ottom;q=digi.link; bottom+;while (q!=NULL)j=q->adjvex;digj.indegree-;if (digi.ee+q->dut>digj.ee)时间/入度为 0 则进栈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; i<=e_n; i+)digi.el=digstacktptop-1.ee;bottom

20、=0;while (top>bottom)top-;一个事件开始倒推/表示没有环/先初始化一下/栈非空/ 从最后的i=stacktptop; q=digi.link;while (q!=NULL) j=q->adjvex;if (digj.el-q->dut<digi.el) digi.el=digj.el-q->dut;q=q->next; for (i=0; i<len; i+) print(dig,stacktpi,i); return 0;else return 1;void main()enode dig20; / 顶点表数组 vexnode

21、 *q;/邻接点链表char ch;int e_n,v_n,m,i,j,u,v,stacktp20; printf(" 关键路径 printf(" 请输入顶点个数和边的条数： scanf("%d%d",&e_n,&v_n);for (i=1; i<=e_n; i+)/ 初始化nn");");digi.indegree=0;digi.link=NULL;digi.vertex=i;digi.ee=digi.el=0;printf(" 请输入 %d 条边以及该边的权： for (i=0; i<v_n;

22、 i+)scanf("%d%d%d",&u,&v,&j); 读入各边以及边的权值n",v_n);/q=malloc(LEN); digv.indegree+; q->adjvex=v; q->dut=j; q->next=digu.link;/ 将 q 结点 digu.link=q;/将 q 结点放入 u 邻接链表中 放入 u 邻接链表中m=toposort(dig,e_n,stacktp);/拓扑排序if (m) printf(" 图中存在环，不存在关键路径 n"); elseprintf("

23、; 需要各点明细查询吗 y/n"); scanf("n%c",&ch);if (ch='y'|ch='Y')for (i=0; i<e_n; i+)printf("%d (%d %d) n",stacktpi,digstacktpi.ee,digstacktpi.el);题目 12：堆排序实现(学时：3)假设有一个数据类型为整型的一维数组 A，A 中的数据元素呈无序状态，编写一个采用堆排序法将 A 中的数据元素按由小到大进行排序的程序。#include<stdio.h>#define M

24、AX 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(j<m&&Aj<Aj+1)j+; /* 若左孩子较大，则把 j 修改为右孩子的下标 */ if(x<Aj)Ai=Aj; /* 将 Aj 调到父亲的位置上 */ i=j; /* 修改 i 和 j 的值，以便继续向下筛选 j=2*i;else j=m+1; /* 起结束作用 */*/Ai=x; /* 被筛结点的值存入最终的位置 *

25、/void sortdui(int n) int i; int m; for(i=n/2;i>=1;i-)creatdui(i,n); /* 建立初始堆，遍布所有的根结点 for(i=n;i>=2;i-) /* 进行 n-1 次循环完成堆排序 */m=Ai;Ai=A1; /* 将第一个元素同当前区域的最后一个元素对换 A1=m;creatdui(1,i-1); /* 筛选 A1 结点，得到 i-1 个结点的堆，仅有 A1 可能违反堆性质 */*/*/void main()int i,n;printf(" 堆排序 nn");printf(" 输入整型一维

26、数组 A 中数字总数 :"); scanf("%d",&n);if(n<=0|n>MAX)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);printf("n 堆排序

27、后的序列为 :n");for(i=1;i<=n;i+)printf("%4d",Ai);printf("n");题目 13基数排序的实现（学时：3）A为每个关键字不超过3位的十进制整数关键字集合，试编写一个采用静态链表组织模式实现的基数排序程序将 A进行由小到大的排序。#include<stdio.h>#include <stdlib.h>#define N 1024 int RadixCountSort(int* npIndex, int nMax, int* npData, int nLen) int* pnC

28、ount=(int*)malloc(sizeof(int)* nMax); int i=0;/保存计数的个数for (i=0;i<nMax;+i)pnCounti=0;for (i=0;i<nLen;+i)/初始化计数个数+pnCountnpIndexi;for (i=1; i<10;+i)/确定不大于该位置的个数。pnCounti +=pnCounti-1;int * pnSort =(int*)malloc(sizeof(int) * nLen);/存放零时的排序结果。/注意：这里 i 是从 nLen-1 到 0 的顺序排序的， for (i=nLen-1;i>=0;-i)是为了使排序稳定。-pnCountnpIndexi; pnSortpnCountnpIndexi=npDa