算法与数据结构课程设计-散列表的设计与实现教学计划编制问题.doc

1 * 实践教学实践教学 * 兰州理工大学兰州理工大学 计算机与通信学院 2015 年秋季学期 算法与数据结构算法与数据结构课程设计课程设计 题 目: 散列表的设计与实现 教学计划编制问题 专业班级：软件工程二班 姓 名： 学 号： 指导教师： 成 绩： 2 目目 录录 摘要摘要.3 一一. . 散列表的设计与实现散列表的设计与实现 1.采用类语言定义相关的数据类型.4 2. 算法设计4 3.函数的调用关系图7 4.调试分析.8 6.源程序（带注释）.11 二教学计划编制问题二教学计划编制问题 1.采用类语言定义相关的数据类型.18 2.算法设计.19 3. 函数的调用关系图21 5. 测试结果22 6.源程序（带注释）.23 总结.31 致致 谢谢.32 3 摘要摘要 1.1. 散列表的设计与实现散列表的设计与实现 (1)(1)查找并显示给定电话号码的记录查找并显示给定电话号码的记录 (2)(2) 查找并显示给定用户名的记录查找并显示给定用户名的记录 (3)(3) 用散列表实现电话号码查找系统用散列表实现电话号码查找系统 (4)(4) 以电话号码和用户名为关键字建立散列表以电话号码和用户名为关键字建立散列表 关键字：电话号码关键字：电话号码 用户名用户名 地址地址 查找查找 2.2.教学计划编制问题教学计划编制问题 （1)1)输入参数：学期总数，一学期的学分上限，每门课的课程号输入参数：学期总数，一学期的学分上限，每门课的课程号 （2)2)输出参数：输出提示信息输出参数：输出提示信息 （3)3)阐明了如何搞好教学管理，从而为提高教学质量提供保证阐明了如何搞好教学管理，从而为提高教学质量提供保证 （4)4)重视教学计划的改革修订工作，以确保教育教学质量，提高教育教学水平。重视教学计划的改革修订工作，以确保教育教学质量，提高教育教学水平。 （5)5)明确培养目标明确培养目标, ,注重学科设置的整体性、统一性和灵活性、全面性注重学科设置的整体性、统一性和灵活性、全面性, ,学分制学分制 改革有机结合改革有机结合 关键字：学期关键字：学期 学分学分 课程号课程号 教学计划教学计划 管理管理 4 一一散列表的设计与实现散列表的设计与实现。设计散列表实现电话号码查找系统。基本要 求： (1)设每个记录有下列数据项：电话号码、用户名、地址； (2) 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表； (3)采用双散列法解决冲突； (4)查找并显示给定电话号码的记录； (5) 查找并显示给定用户名的记录。 1.1.采用类语言定义相关的数据类型采用类语言定义相关的数据类型 typedef int status; typedef char namax_size; typedef struct/记录 na name; na tel; na add; record; typedef struct/哈希表 record *elemhashsize; /数据元素存储基址 int count; /当前数据元素个数 int size; /当前容量 hashtable 2.2.算法设计算法设计 初始化散列表算法： void inithashtable(hashtable ht,hashtable2 ht2) for(int i=0;i=0) return q; else i=c/2+1; else q=(p-i*i)%hashsize; c+; if(q=0) return q; else i=c/2+1; 14 return unsuccess; void bengettime(); void createhash1(hashtable* h,record* a)/建表，以人的姓名为关键字，建立相应的散列 表 /若哈希地址冲突，进行冲突处理 bengettime(); int i,p=-1,c,pp; for(i=0;ielempp!=null) pp=collision(p,c); if(ppelempp= /求得哈希地址，将信息存入 h-count+; printf(“第%d 个记录冲突次数为%d。n“,i+1,c);/需要显示冲突次数时输出 printf(“n 建表完成!n 此哈希表容量为%d,当前表内存储的记录个数为% d.n“,hashsize,h-count); bengettime(); void searchhash1(hashtable* h,int na str; printf(“n 请输入要查找记录的姓名：n“); scanf(“%s“,str); int p,pp; p=hash1(str); pp=p; while(h-elempp!=null) if(h-elempp!=null 15 printf(“姓 名：%sn 电话号码：%sn 联系地址：%sn“,h-elempp-name,h-elempp- tel,h-elempp-add); else printf(“n 此人不存在，查找不成功!n“); bengettime(); void bengettime() systemtime sys; getlocaltime( printf( “%4d/%02d/%02d %02d:%02d:%02d.%03d n“,sys.wyear,sys.wmonth,sys.wday,sys.whour,sys.wminute, sys.wsecond,sys.wmilliseconds); void createhash2(hashtable* h,record* a)/建表，以电话号码为关键字，建立相应的散列 表 /若哈希地址冲突，进行冲突处理 bengettime(); int i,p=-1,c,pp; for(i=0;ielempp!=null) pp=collision(p,c); if(ppelempp= /求得哈希地址，将信息存入 h-count+; printf(“第%d 个记录冲突次数为%d。n“,i+1,c);/需要显示冲突次数时输出 printf(“n 建表完成!n 此哈希表容量为%d,当前表内存储的记录个数为% d.n“,hashsize,h-count); bengettime(); void searchhash2(hashtable* h,int 16 na tele; printf(“n 请输入要查找记录的电话号码：n“); scanf(“%s“,tele); int p,pp; p=hash2(tele); pp=p; while(h-elempp!=null) if(h-elempp!=null printf(“姓 名：%sn 电话号码：%sn 联系地址：%sn“,h-elempp-name,h-elempp- tel,h-elempp-add); else printf(“n 此人不存在，查找不成功!n“); bengettime(); void save() file *fp; if(fp=fopen(“c:test.txt“, “w“)=null) printf(“nerror opening customet file“); fclose(fp); int main(int argc, char* argv) int c,flag=1; hashtable *h; h=(hashtable*)malloc(len); for(int i=0;ielemi=null; h-size=hashsize; h-count=0; record amaxsize; while (1) printf(“n “); printf(“n 欢迎使用电话号码查找系统 “); printf(“n “); printf(“n 哈希表的设计与实现 “); printf(“n 【1】. 添加用户信息 “); printf(“n 【2】. 读取所有用户信息 17 “); printf(“n 【3】. 以姓名建立哈希表(再哈希法解决冲突) “); printf(“n 【4】. 以电话号码建立哈希表(再哈希法解决冲突) “); printf(“n 【5】. 查找并显示给定用户名的记录 “); printf(“n 【6】. 查找并显示给定电话号码的记录 “); printf(“n 【7】. 清屏 “); printf(“n 【8】. 保存 “); printf(“n 【9】. 退出程序 “); printf(“n 温馨提示： “); printf(“n .进行 5 操作前 请先输出 3 “); printf(“n .进行 6 操作前 请先输出 4 “); printf(“n “); printf(“n“); printf(“请输入一个任务选项“); printf(“n“); int num; scanf(“%d“, switch(num) case 1: getin(a); break; case 2: showinformation(a); break; case 3: createhash1(h,a); /* 以姓名建立哈希表 */ break; case 4: createhash2(h,a); /* 以电话号码建立哈希表 */ break; case 5: c=0; searchhash1(h,c); 18 break; case 6: c=0; searchhash2(h,c); break; case 7: cls(a); break; case 8: save(); break; case 9: return 0; break; default: printf(“你输错了，请重新输入!“); printf(“n“); system(“pause“); return 0; display(f); 二教学计划编制问题。二教学计划编制问题。假设任何专业都有固定的学习年限，每 学年含两学期，每学期的时间长度和学分上限值均相等。每个专业 开设的课程都是确定的，而且课程在开设时间的安排必须满足先修 关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可 以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学 计划编制程序。基本要求：1)输入参数：学期总数，一学期的学分 上限，每门课的课程号(固定占 3 位的字母数字串，规定从 c01c12)、学分和直接先修课的课程号；2)输出参数：输出提示信 息，由用户在键盘上输入运行程序中规定的命令来指定下列两种编 排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使 19 课程尽可能地集中在前几个学期中；3)若根据给定的条件问题无解， 则报告适当的信息，否则将教学计划输出到用户指定的文件中。 1.1.采用类语言定义相关的数据类型采用类语言定义相关的数据类型 typedef int status; / status 是函数的类型,其值是函数结果状态代码，如 ok 等 typedef int boolean; / boolean 是布尔类型,其值是 true 或 false #define max_name 10 /* 顶点字符串的最大长度*/ #define maxclass 100 int z=0; int x=0; int xqzs,q=1,xfsx; typedef int infotype; typedef char vertextypemax_name; /* 字符串类型*/ /* 图的邻接表存储表示*/ #define max_vertex_num 100 typedef enumdggraphkind; /* 有向图,有向网,无向图,无向网 */ typedef struct arcnode int adjvex; /* 该弧所指向的顶点的位置*/ struct arcnode *nextarc; /* 指向下一条弧的指针*/ infotype *info; /* 网的权值指针）*/ arcnode; /* 表结点*/ typedef struct vertextype data; /* 顶点信息*/ arcnode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指 针*/ vnode,adjlistmax_vertex_num; /* 头结点*/ typedef struct adjlist vertices,verticestwo; int vexnum,arcnum; /* 图的当前顶点数和弧数*/ int kind; /* 图的种类标志*/ algraph; 2.2.算法设计算法设计 1头结点，表结点，邻接表的定义 #define max_vertex_num 100 /最大课程总数 typedef struct arcnode 20 int adjvex; struct arcnode *nextarc; arcnode; typedef struct vnode char name24; /课程名 int classid; /课程号 int credit; /课程的学分 int indegree; /该结点的入度 int state; /该节点的状态 arcnode *firstarc; /指向第一条依附该顶点的弧的 指针 vnode,adjlistmax_vextex_num; typedef struct adjlist vertices; int vexnum, arcnum; algraph; 邻接表的基本操作： void creatgraph(algraph *); 创建邻接表 void findindegree(algraph , int * ); 求一个结点的入度 void topologicalsort_1(algraph g,int numterm,int maxcredit); 拓扑排序来编排课程 void topologicalsort_2(algraph g,int numterm,int maxcredit); 2栈的定义： #define stack_init_size 100 /存储空间的初时分配量 #define stackincrement 10 /存储空间的分配增量 typedef int elemtype; typedef struct adjlist vertices; 21 int vexnum, arcnum; algraph; 基本操作： void initstack (sqstack *s); 栈的初始化 int stackempty(sqstack s); 判断栈是否为空 void push(sqstack *s, int ); 入栈操作 int pop(sqstack *s, int *e); 出栈操作 int sort(sqstack *s,int *t); 3.3.函数的调用关系图函数的调用关系图 4. .调试分析调试分析 a.在调试过程中需要把输入的信息保存到一个文件夹中，在老师的帮助下以及上网查找下， 最后解决了问题。解决问题参考代码如下： #include #include using namespace std; int main() main() locatevex() creategraph() display() findindegree() clearstack() stackempty() f 22 int a; ofstream outfile(“d:fl.txt“,ios:out); if(!outfile) cerra; outfileadjvex=j; p-info=null; /* 图*/ p-nextarc=(*g).verticesi.firstarc; /* 插在表头*/ (*g).verticesi.firstarc=p; return ok; void display(algraph g) /* 输出图的邻接矩阵 g */ int i; arcnode *p; switch(g.kind) case dg: printf(“有向图n“); printf(“%d 个顶点：n“,g.vexnum); for(i=0;iadjvex.data); p=p-nextarc; printf(“n“); void findindegree(algraph g,int indegree) /* 求顶点的入度，算法调用*/ int i; arcnode *p; for(i=0;iadjvex+; p=p-nextarc; typedef int selemtype; /* 栈类型*/ /*栈的顺序存储表示*/ #define stack_init_size 10 /* 存储空间初始分配量*/ #define stackincrement 2 /* 存储空间分配增量*/ typedef struct sqstack selemtype *base; /* 在栈构造之前和销毁之后，base 的值为 null */ selemtype *top; /* 栈顶指针*/ int stacksize; /* 当前已分配的存储空间，以元素为单位*/ sqstack; /* 顺序栈*/ /* 顺序栈的基本操作*/ status initstack(sqstack *s) /* 构造一个空栈 s */ (*s).base=(selemtype *)malloc(stack_init_size*sizeof(selemtype); if(!(*s).base) exit(overflow); /* 存储分配失败*/ (*s).top=(*s).base; (*s).stacksize=stack_init_size; 27 return ok; void clearstack(sqstack *s) /清空栈的操作 s-top=s-base; status stackempty(sqstack s) /* 若栈 s 为空栈，则返回 true，否则返回 false */ if(s.top=s.base) return true; else return false; status pop(sqstack *s,selemtype *e) /* 若栈不空，则删除 s 的栈顶元素，用 e 返回其值，并返回 ok；否则返回 error */ if(*s).top=(*s).base) return error; *e=*-(*s).top; return ok; status push(sqstack *s,selemtype e) /* 插入元素 e 为新的栈顶元素*/ if(*s).top-(*s).base=(*s).stacksize) /* 栈满，追加存储空间*/ (*s).base=(selemtype *)realloc(*s).base,(*s).stacksize+stackincrement)*sizeof (selemtype); if(!(*s).base) exit(overflow); /* 存储分配失败*/ (*s).top=(*s).base+(*s).stacksize; (*s).stacksize+=stackincrement; *(*s).top)+=e; return ok; typedef int pathonemaxclass; typedef int pathtwomaxclass; status topologicalsort(algraph g) /* 有向图 g 采用邻接表存储结构。若 g 无回路,则输出 g 的顶点的一个拓扑序列并返回 28 ok, */ /* 否则返回 error。*/ int i,k,j=0,count,indegreemax_vertex_num; bool has=false; sqstack s; pathone a; pathtwo b; arcnode *p; findindegree(g,indegree); /* 对各顶点求入度 indegree0vernum-1 */ initstack( /* 初始化栈*/ for(i=0;inextarc) /* 对 i 号顶点的每个邻接点的入度减*/ k=p-adjvex; if(!(-indegreek) /* 若入度减为,则入栈*/ push( /coutxfsx) break; indegreei-; for(p=g.verticesi.firstarc;p;p=p-nextarc) /* 对 i 号顶点的每个邻接点的入度减*/ k=p-adjvex; indegreek-; /* if(!(-indegreek) 若入度减为,则入栈 push( */ resultrtop=i; rtop+; 30 /保存本地文件 ofstream outfile(“课程文件.txt“,ios:out); outfile“第“qq“个“学期的课程为：“endl; for(nn=0;nnrtop;nn+) outfile“课程“g.verticesresultnn.dataendl; qq+; outfile.close(); cout“处理完毕，请打开文件查看结果！“endl; return ok; void main() algraph f; printf(“.n“); printf(“教学计划编制问题的数据模型为拓扑排序 aov-网结构。n“); printf(“.n“); printf(“以下为教学计划编制问题的求解过程:n“); printf(“*n“); printf(“请输入学期总数:n“); printf(“*n“); scanf(“%d“, printf(“*n“); printf(“请输入学期的学分上限:n“); printf(“*n“); scanf(“%d“, printf(“*n“); creategraph( topologicalsort(f); 31 总结总结 虽然在大一我们已经学习了 c 语言，但是，直到本期我们才开设了数据结构这一门课 程。这门课程让我们对程序的原理有了系统的认识。对以往模糊的经验，起了总结提升的 作用。在学习了这门课程后，我们进行了 2 个星期的课程设计，以实践我们的学习内容。 在这次课程设计中，我被分配到了散列表的设计与实现和教学计划课程编制问题，开 始感觉很难，因为我从未编写过如此复杂的程序。在多方查找资料并参考类似程序后，我 大体将程序的构架描绘好了。一边对照着网上的资料，一边对程序进行修改补充，然后根 据拟好的大纲进行编制。期间，我与其它同学进行了讨论和探究，对程序的细节问题和应 用方面进行了探索，并解决了主要的问题，于是便着手写具体的程序。 这次实验，我进行了大量的资料查阅，包括向老师请求帮助解释题目要求，对所学知 识进行复习。通过这些努力，我对算法有了更深入的理解，对编程的步骤，有了具体的体 会。通过和同学的广泛交流，我体会到了合作的必要性及合作的优势。更重要的是，这个 课题完全脱胎于实际问题，让我对计算机行业，充满了信心和自豪。 以往我们学的计算机知识一般停留在理论上，这让我们不太理解计算机的应用和前景， 而较少注重我们对算法的实践锻炼。而这一次的实习既需要