兰州大学数据结构课程设计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、allowanc

2、e、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)，要求多项式采用链表进行存储。另外该任务要求具

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

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

5、t;#include<string.h>#include<math.h>#define n 100#define m 2*n-1typedef struct /码结点的存储结构char ch;char bits9;int len;CodeNode;typedef CodeNode HuffmanCoden+1;typedef struct /树结点的存储结构int weight;int lchild,rchild,parent;HTNode;typedef HTNode HuffmanTreem+1;int num;void select(HuffmanTree HT,

6、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;minl=HTi.weight;s2=j;int jsq(char *s,int cnt,char str)

7、/统计输入字符和串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 cnt,char str) int i,s1,s2; for(i=1;i<=2*num-1;

8、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;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,&cdstart); HCi.len=num-start

10、; 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(strcmp(HCj.bits,cd)=0) str

11、k=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; /str用于在统计输入序列中的字母时用，存

12、放是什么字符，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");printf(" 2.生成霍夫曼编码.n");printf(" 3.编码文件译码.n"); while(ch='y&

13、#39;)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); /根据霍

14、夫曼树建立霍夫曼编码 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_ratio(st,cn,HC);break;case 3: prin

15、tf("输入二进制码开始译码："); char receive10000; scanf("%s",&receive); decode(HC,receive,s);/译码 printf("译码为：%sn",s);break;printf("n是否继续？(y/n):");scanf("%c",&ch);scanf("%c",&ch);题目11：关键路径寻找（学时：6）对于给定的一个工程施工图，该图以边为单位从键盘输入，编写能够找出该图的关键路径的程序。#i

16、nclude"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 print(enode di

17、g,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->adjvex;if (digj.ee=digj.el)listtop=dig

18、j.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=stacktpbottom;q=digi.link;bottom+;while (q!=NULL)j=q->adjv

19、ex;digj.indegree-; /入度-if (digi.ee+q->dut>digj.ee) /求一下最早开始时间digj.ee=digi.ee+q->dut;if (digq->adjvex.indegree=0) /入度为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=0;while (top>bottom)

20、/栈非空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 *q; /邻接点链表char ch; int e_n,v_n,m,i,j,u,v,sta

21、cktp20;printf("-关键路径-nn");printf("请输入顶点个数和边的条数：");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; i<v_n; i+)scanf("%d%d%d",&u,

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

23、'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 MAX 255int AMAX;void creatdui(int l,int m) /*建初始堆过程函数*/ int i,j,x;

24、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; /*被筛结点的值存入最终的位置*/void sortdui(int n) int i; int m; for(i=n/2;i>=1;i-)creatdui(i,n); /*建立初始堆，遍布所有

25、的根结点*/ 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("输入整型一维数组A中数字总数:"); scanf("%d",&n); if(n<=0|n>MAX) printf("n输入的数据有误!&q

26、uot;); 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堆排序后的序列为:n"); for(i=1;i<=n;i+) printf("%4d",Ai); printf("n");题目13基数排序

27、的实现（学时：3）A为每个关键字不超过3位的十进制整数关键字集合，试编写一个采用静态链表组织模式实现的基数排序程序将A进行由小到大的排序。#include<stdio.h>#include <stdlib.h>#define N 1024int RadixCountSort(int* npIndex, int nMax, int* npData, int nLen) int* pnCount=(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=npDatai; for (i=0;i<n