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

《算法与数据结构课程设计散列表的设计与实现教学计划编制问题.doc》由会员分享，可在线阅读，更多相关《算法与数据结构课程设计散列表的设计与实现教学计划编制问题.doc（33页珍藏版）》请在三一文库上搜索。

1、* 实践教学实践教学 * 兰州理工大学兰州理工大学 计算机与通信学院 2015 年秋季学期 算法与数据结构算法与数据结构课程设计课程设计 题 目: 散列表的设计与实现 教学计划编制问题 专业班级：软件工程二班 姓 名： 学 号： 指导教师： 成 绩： 目目 录录 摘要摘要.3 一一. . 散列表的设计与实现散列表的设计与实现 1.采用类语言定义相关的数据类型.4 2. 算法设计.4 3.函数的调用关系图.7 4.调试分析.8 6.源程序（带注释）.11 二教学计划编制问题二教学计划编制问题 1.采用类语言定义相关的数据类型.18 2.算法设计.19 3. 函数的调用关系图.21 5. 测试结果

2、.22 6.源程序（带注释）.23 总结.31 致致 谢谢.32 摘要摘要 1.1. 散列表的设计与实现散列表的设计与实现 (1)(1)查找并显示给定电话号码的记录查找并显示给定电话号码的记录 (2)(2) 查找并显示给定用户名的记录查找并显示给定用户名的记录 (3)(3) 用散列表实现电话号码查找系统用散列表实现电话号码查找系统 (4)(4) 以电话号码和用户名为关键字建立散列表以电话号码和用户名为关键字建立散列表 关键字：电话号码关键字：电话号码 用户名用户名 地址地址 查找查找 2.2.教学计划编制问题教学计划编制问题 （1)1)输入参数：学期总数，一学期的学分上限，每门课的课程号输入参

3、数：学期总数，一学期的学分上限，每门课的课程号 （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; typed

5、ef struct/哈希表 Record *elemHASHSIZE; /数据元素存储基址 int count; /当前数据元素个数 int size; /当前容量 HashTable 2.2.算法设计算法设计 初始化散列表算法： void InitHashTable(HashTable HT,HashTable2 HT2) for(int i=0;iHashMaxSize;i+) strcpy(HTi.HashName,0);/将哈希表 1 初始化为空 strcpy(HT2i.HashNum,0);/将哈希表 2 初始化为空 哈希函数算法： int Hash1(NA str)/哈希函数 lo

6、ng n; int m; n=fold(str);/先将用户名进行折叠处理 m=n%HASHSIZE; /折叠处理后的数，用除留余数法构造哈希 函数 return m; /并返回模值 int Hash2(NA str)/哈希函数 long n; int m; n = atoi(str);/把字符串转换成整型数. m=n%HASHSIZE; /用除留余数法构造哈希函数 return m; /并返回模值 整体散列算法： void sanlie(Pnode temp) int i=0,j=0; while(strcmp(tempj.name,0)!=0) j+; /计算当前表中 name 元素的个数

7、 while(ij)/该循环将各元素得到哈希地址后，将元素存储到相应的哈希表中 hash1(tempi.name); while(strlen(hashAddsNamekey.HashName) key=(key+1)%m;/线形探测法处理冲突 strcpy(hashAddsNamekey.HashName,tempi.name); /将作为关键字的姓名存入哈希表 hash2(tempi.number); while(strlen(hashAddsNumkey2.HashNum) key2=(key2+1)%m;/线形探测法处理冲突 strcpy(hashAddsNumkey2.HashNum

8、,tempi.number); /将作为关键字的电话号码存入哈希表 i+; 输入各个记录信息算法 void inputNode() /提示用户输入信息的同时将信息写入文件 int i=1; char yn; Pnode temp; openfile(1);/调用”打开文件”函数 while(1) printf( 请输入第%d个姓名:,i); scanf(%s,temp.name); printf( 请输入第%d个电话号码:,i); scanf(%s,temp.number); printf( 请输入第%d个地址:,i); scanf(%s,temp.add); fprintf(fp,%15s

9、%15s %30sn,temp.name,temp.number,temp.add); printf( 是否继续添加( Y 继续 )?t); scanf(%s, if(yn!=y/当键入 Y 或 y 时继续输入 i+; ; fclose(fp); 显示记录算法 void display() int i=0,j=1; Pnode a; openfile(2);/以写方式调用打开文件函数 printf(n); printf( - - - - - - - - - - - - - - - - - - - - - - -n); printf( 序号 姓名 电话号码 地址 nn); while(!feof

10、(fp)/当文件指针没有指向文件末尾时循环 fscanf(fp,%s%s%s, printf( %2dt%-15s%-15s %- 30sn,j+,a.name,a.number,a.add); printf(nn); fclose(fp);/关闭文件 依靠散列的查找算法 int search1(char name15) /*关键字为姓名*/ hash1(name);/调用哈希函数求取哈希地址下标 while(strlen(hashAddsNamekey.HashName)!=0) if(strcmp(hashAddsNamekey.HashName,name)=0) return 1;/如果

11、输入的关键字与哈希表中的关键字相等返回 1 else key=(key+1)%m;/*线性探测法处理冲突在下一位继续查找 return -1;/如果未找到返回-1 3.3.函数的调用关系图函数的调用关系图 4 4. .调试分析调试分析 a a、调试中遇到的问题及对问题的解决方法调试中遇到的问题及对问题的解决方法 在编写算法时，遇到文件的具体操作，在从文件中读取整条数据后，无法 直接与其他算法相关联。 while(!feof(fp) fgets(temp,100,fp); for(j=0,i=0;j15;j+) if(tempj!= ) t1i=tempj;i+; t1i=0; for(j=16

12、,i=0;j31;j+) if(tempj!= ) t2i=tempj;i+; t2i=0; for(j=31,i=0;j63;j+) if(tempj!= ) t3i=tempj;i+; t3i=0; strcpy(tempobjk.name,t1); strcpy(tempobjk.number,t2); strcpy(tempobjk.add,t3); k+; fclose(fp); 经过查阅书籍及网络资料，采取以上的方法解决问题 ，将从文件中读取出 的一整行数据，经过拆分后，将各段数据分别存入结构体中的各个元素中 去，问题得以解决。 b b、算法的时间复杂度和空间复杂度算法的时间复杂度

13、和空间复杂度 空间复杂度 数据结构定义 5% 散列部分 5% 显示函数 5%查找部分5% 添加部分 10% 删除部分 10% 处理函数30% 输入函数部分 10% 主函数 10% 其他占：10% 时间复杂度 散列函数时, 输入信息函数, 显示函数,查找函数时间复杂度 O(n) 主函数，转换函数时间复杂度 O(n2); 5.5.测试结果测试结果 （1）、程序初始运行结果：）、程序初始运行结果： （2）新建通讯录：）新建通讯录： （3）读取用户信息读取用户信息 （4）解决冲突解决冲突 （5）查找（号码查找（号码 用户名用户名 ） 6.6.源程序（带注释）源程序（带注释） typedef int S

14、tatus; typedef char NAMAX_SIZE; typedef struct/记录 NA name; NA tel; NA add; Record; typedef struct/哈希表 Record *elemHASHSIZE; /数据元素存储基址 int count; /当前数据元素个数 int size; /当前容量 HashTable; Status eq(NA x,NA y)/关键字比较，相等返回 SUCCESS；否则返回 UNSUCCESS if(strcmp(x,y)=0) return SUCCESS; else return UNSUCCESS; Status

15、 NUM_BER; /记录的个数 void getin(Record* a)/键盘输入各人的信息 printf(输入要添加的个数：n); scanf(%d, int i; for(i=0;iNUM_BER;i+) printf(请输入第%d 个记录的用户名:n,i+1); scanf(%s,ai.name); printf(请输入%d 个记录的电话号码:n,i+1); scanf(%s,ai.tel); printf(请输入第%d 个记录的地址:n,i+1); scanf(%s,ai.add); /gets(str2);? void ShowInformation(Record* a)/显示输

16、入的用户信息 int i; for( i=0;iNUM_BER;i+) printf(n 第%d 个用户信息:n 姓 名：%sn 电话号码：%sn 联系地址：%sn,i+1,ai. name,ai.tel,ai.add); void Cls(Record* a) printf(*); system(cls); long fold(NA s)/人名的折叠处理 char *p; long sum=0; NA ss; strcpy(ss,s);/复制字符串，不改变原字符串的大小写 strupr(ss);/将字符串 ss 转换为大写形式 p=ss; while(*p!=0) sum+=*p+; pri

17、ntf(nsum=%d,sum); return sum; int Hash1(NA str)/哈希函数 long n; int m; n=fold(str);/先将用户名进行折叠处理 m=n%HASHSIZE; /折叠处理后的数，用除留余数法构造哈希函数 return m; /并返回模值 int Hash2(NA str)/哈希函数 long n; int m; n = atoi(str);/把字符串转换成整型数. m=n%HASHSIZE; /用除留余数法构造哈希函数 return m; /并返回模值 Status collision(int p,int i=c/2+1; while(i=

18、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; 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= /求得哈希地址，将

19、信息存入 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 printf(姓 名：%

20、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 CreateHash

21、2(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

22、 SearchHash2(HashTable* H,int 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

23、=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(

24、n 哈希表的设计与实现 ); printf(n 【1】. 添加用户信息 ); printf(n 【2】. 读取所有用户信息 ); 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 操作前

25、 请先输出 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; Searc

26、hHash1(H,c); 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); 二教学计划编制问题。二教学计划编制问题。假设任何专业都有固定的学习年限，每 学年含两学期，每学期的时间长度和学分上限值均相等。每个专业 开设的课程都是确定的，而且课程在开设时间的安排必须

27、满足先修 关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可 以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学 计划编制程序。基本要求：1)输入参数：学期总数，一学期的学分 上限，每门课的课程号(固定占 3 位的字母数字串，规定从 C01C12)、学分和直接先修课的课程号；2)输出参数：输出提示信 息，由用户在键盘上输入运行程序中规定的命令来指定下列两种编 排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使 课程尽可能地集中在前几个学期中；3)若根据给定的条件问题无解， 则报告适当的信息，否则将教学计划输出到用户指定的文件中。 1.1.采用类语言定义相关的数据类型采用

28、类语言定义相关的数据类型 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; /* 字符串类型*/ /* 图的邻接表存储表示*/ #de

29、fine MAX_VERTEX_NUM 100 typedef enumDGGraphKind; /* 有向图,有向网,无向图,无向网 */ typedef struct ArcNode int adjvex; /* 该弧所指向的顶点的位置*/ struct ArcNode *nextarc; /* 指向下一条弧的指针*/ InfoType *info; /* 网的权值指针）*/ ArcNode; /* 表结点*/ typedef struct VertexType data; /* 顶点信息*/ ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指 针

30、*/ 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 int adjvex; struct ArcNode *nextarc; ArcNode; typedef struct

31、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

32、, 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; int vexnu

33、m, 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 #i

34、nclude using namespace std; int main() Main() LocateVex() CreateGraph() Display() FindInDegree() ClearStack() StackEmpty() f int a; ofstream outfile(d:fl.txt,ios:out); if(!outfile) cerropen error!endl; exit(1); for(int i=0;ia; outfileaendl; outfile.close(); cout处理完毕，请打开文件查看结果！endl; return 0; B.B.对于有

35、 n 个定点，e 条边的 AOV 网而言，拓扑排序算法中扫描表，将入度为 0 的顶点表， 栈的时间复杂度为 O（n），若为有向无回路，每个顶点进出栈各一次，共循环 e 次，所以 整个算法复杂度为 o（n+e）。 5.5.测试结果测试结果 程序初始运行结果：程序初始运行结果： 6.6.源程序（带注释）源程序（带注释） using namespace std; / 函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; / Statu

36、s 是函数的类型,其值是函数结果状态代码，如 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 enumDGGr

37、aphKind; /* 有向图,有向网,无向图,无向网 */ typedef struct ArcNode int adjvex; /* 该弧所指向的顶点的位置*/ struct ArcNode *nextarc; /* 指向下一条弧的指针*/ InfoType *info; /* 网的权值指针）*/ ArcNode; /* 表结点*/ typedef struct VertexType data; /* 顶点信息*/ ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针*/ VNode,AdjListMAX_VERTEX_NUM; /* 头结点*/

38、typedef struct AdjList vertices,verticestwo; int vexnum,arcnum; /* 图的当前顶点数和弧数*/ int kind; /* 图的种类标志*/ ALGraph; /* 图的邻接表存储的基本操作*/ int LocateVex(ALGraph G,VertexType u) /* 初始条件: 图 G 存在,u 和 G 中顶点有相同特征*/ /* 操作结果: 若 G 中存在顶点 u,则返回该顶点在图中位置;否则返回-1 */ int i; for(i=0;iG.vexnum;+i) if(strcmp(u,G.verticesi.data

39、)=0) return i; return -1; Status CreateGraph(ALGraph *G) /* 采用邻接表存储结构,构造没有相关信息的图 G(用一个函数构造种图) */ int i,j,k; VertexType va,vb; ArcNode *p; printf(*n); printf(请输入教学计划的课程数:n ); printf(*n); scanf(%d, printf(*n); printf(请输入拓扑排序所形成的课程先修关系的边数: n); printf(*n); scanf(%d, printf(*n); printf(请输入%d 个课程的代表值(%d 个

40、字符):n,(*G).vexnum,MAX_NAME); printf(*n); for(i=0;i(*G).vexnum;+i) /* 构造顶点向量*/ scanf(%s,(*G).verticesi.data); (*G).verticesi.firstarc=NULL; printf(请输入%d 个课程的学分值(%d 个字符):n,(*G).vexnum,MAX_NAME); for(i=0;i(*G).vexnum;+i) /* 构造顶点向量*/ scanf(%s,(*G).verticestwoi.data); printf(*n); printf(请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):n); printf(*n); for(k=0;kadjvex=j; p-info=NULL; /* 图*/ p