《兰州大学数据结构课程设计4概要.doc》由会员分享，可在线阅读，更多相关《兰州大学数据结构课程设计4概要.doc（14页珍藏版）》请在三一文库上搜索。
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人）。题目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 Huff
6、manTreem+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 cn
8、t,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<=nu
9、m;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,&a
10、mp;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(strcmp
11、(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()/str 用于在统计输入序列中的字母时用，
12、存放是什么字char str257;符， 1 到 256char st10000,s10000; /st用来接收输入的字符串，s用来接收解压的字符串int cn257;/cn 用于接收统计后的每个字符的频率， 1 到 256HuffmanTree HT;HuffmanCode HC;char ch='y'int d,i;printf(" 霍夫曼树 nn");printf("1 .建立霍夫曼树 .n");printf("2.生成霍夫曼编码 .n");printf("3.编码文件译码 .n");whil
13、e(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:HuffmanEnco
14、ding(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_ratio(st,
15、cn,HC);break;case 3:printf(" 输入二进制码开始译码： ");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) 对于给定的一个工程施工图，该图以
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;/记录入度/顶点/记录最迟开始时间和最早结束时
17、间enode;void print(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->adjvex; if (di
18、gj.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;/拓扑排序/入度 -/求一下最早开始/入度为 0 则进栈/ 表示没有环/先初始化一下/栈非空/ 从最后的top+;len=top;while (
19、top>bottom)i=stacktpbottom;q=digi.link;bottom+;while (q!=NULL)j=q->adjvex; digj.indegree-; if (digi.ee+q->dut>digj.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; i<=e_n; i+) digi.el=digstac
20、ktptop-1.ee; bottom=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 *q;/
21、邻接点链表char ch;int e_n,v_n,m,i,j,u,v,stacktp20;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;
22、 i<v_n; i+)scanf("%d%d%d",&u,&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("
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 255int 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; /* 被筛结点的值存入最终的位置 */voi
25、d 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(" 输入整型一维数组 A 中
26、数字总数 :"); 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 堆排序后的序列为 :n
27、");for(i=1;i<=n;i+)printf("%4d",Ai);printf("n");题目 13基数排序的实现(学时：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
28、*)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&
29、gt;=0;-i)-pnCountnpIndexi; pnSortpnCountnpIndexi=npDatai;for (i=0;i<nLen;+i)/把排序结构输入到返回的数据中。npDatai = pnSorti;free(pnSort); / 释放 free(pnCount);return 1;/基数排序int RadixSort(int* nPData, int nLen)/申请存放基数的空间 int *nDataRadix=(int *)malloc(sizeof(int) *nLen);int nRadixBase=1;/ 初始化倍数基数为 1int nIsOk=0;/设置
30、完成排序为 falseint i;/循环，知道排序完成while (nIsOk=0)nIsOk=1;nRadixBase *=10;for (i=0;i<nLen;+i)nDataRadixi = nPDatai % nRadixBase;nDataRadixi /= nRadixBase/10;if (nDataRadixi>0)nIsOk=0;就是已经判断到最if (nIsOk=1)/如果所有的基数都为 0，认为排序完成，高位了。break;RadixCountSort(nDataRadix, 10, nPData, nLen);free(nDataRadix);return
31、1;int main()int i=0;int j;int nDataN;printf(" 基数排序 nn");printf(" 请输入你要排序的个数： ");scanf("%d",&j);if(j=0) return 0;printf(" 请输入的 %d 个整数： n",j);for(i=0;i<j;i+)scanf("%d",&nDatai);RadixSort(nData, j);printf（" 基数排序法排序后： n"）;for (i = 0; i < j; +i)printf("%d ", nDatai);printf("n");return 0;