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

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

1、*实践教学* 兰州理工大学计算机与通信学院2015年秋季学期算法与数据结构课程设计 题 目: 散列表的设计与实现 教学计划编制问题专业班级：软件工程二班姓 名： 学 号： 指导教师： 成 绩：目 录摘要3一. 散列表的设计与实现 1.采用类语言定义相关的数据类型42. 算法设计43.函数的调用关系图74.调试分析86.源程序（带注释）11 二教学计划编制问题1.采用类语言定义相关的数据类型182.算法设计193. 函数的调用关系图215. 测试结果226.源程序（带注释）23总结31致 谢32摘要1. 散列表的设计与实现 (1)查找并显示给定电话号码的记录(2) 查找并显示给定用户名的记录(3

2、) 用散列表实现电话号码查找系统(4) 以电话号码和用户名为关键字建立散列表关键字：电话号码 用户名 地址 查找2. 教学计划编制问题（1) 输入参数：学期总数，一学期的学分上限，每门课的课程号（2) 输出参数：输出提示信息（3) 阐明了如何搞好教学管理，从而为提高教学质量提供保证（4) 重视教学计划的改革修订工作，以确保教育教学质量，提高教育教学水平。（5) 明确培养目标,注重学科设置的整体性、统一性和灵活性、全面性,学分制改革有机结合关键字：学期 学分 课程号 教学计划 管理 一散列表的设计与实现。设计散列表实现电话号码查找系统。基本要求： (1)设每个记录有下列数据项：电话号码、用户名、

3、地址； (2) 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；(3)采用双散列法解决冲突；(4)查找并显示给定电话号码的记录；(5) 查找并显示给定用户名的记录。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; /当前容量HashTable2. 算法设计初

4、始化散列表算法：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)/哈希函数 long n; int m; n=fold(str);/先将用户名进行折叠处理 m=n%HASHSIZE; /折叠处理后的数，用除留余数法构造哈希函数 return m; /并返回模值int Hash2(NA str)/哈希函数 long

5、 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元素的个数while(ij)/该循环将各元素得到哈希地址后，将元素存储到相应的哈希表中hash1(tempi.name);while(strlen(hashAddsNamekey.HashName)key=(key+1)%m;/线形探测法处理冲突strcpy(h

6、ashAddsNamekey.HashName,tempi.name);/将作为关键字的姓名存入哈希表hash2(tempi.number);while(strlen(hashAddsNumkey2.HashNum)key2=(key2+1)%m;/线形探测法处理冲突strcpy(hashAddsNumkey2.HashNum,tempi.number);/将作为关键字的电话号码存入哈希表i+;输入各个记录信息算法void inputNode() /提示用户输入信息的同时将信息写入文件int i=1;char yn;Pnode temp;openfile(1);/调用”打开文件”函数while

7、(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 %15s %30sn,temp.name,temp.number,temp.add);printf( 是否继续添加( Y继续 )?t);scanf(%s,&yn);if(yn!=y&yn!=Y) break;/当键入Y或 y 时继续输入i+;fclose(fp); 显示记录算法void display(

8、)int i=0,j=1;Pnode a;openfile(2);/以写方式调用打开文件函数printf(n);printf( - - - - - - - - - - - - - - - - - - - - - - -n);printf( 序号 姓名 电话号码 地址nn);while(!feof(fp)/当文件指针没有指向文件末尾时循环fscanf(fp,%s%s%s,&a.name,&a.number,&a.add);printf( %2dt%-15s%-15s %-30sn,j+,a.name,a.number,a.add);printf(nn);fclose(fp);/关闭文件 依靠散列

9、的查找算法int search1(char name15) /*关键字为姓名*/hash1(name);/调用哈希函数求取哈希地址下标while(strlen(hashAddsNamekey.HashName)!=0)if(strcmp(hashAddsNamekey.HashName,name)=0)return 1;/如果输入的关键字与哈希表中的关键字相等返回1elsekey=(key+1)%m;/*线性探测法处理冲突在下一位继续查找return -1;/如果未找到返回-1 3.函数的调用关系图4.调试分析a、 调试中遇到的问题及对问题的解决方法在编写算法时，遇到文件的具体操作，在从文件中

10、读取整条数据后，无法直接与其他算法相关联。while(!feof(fp)fgets(temp,100,fp);for(j=0,i=0;j15;j+)if(tempj!= )t1i=tempj;i+; t1i=0;for(j=16,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);

11、经过查阅书籍及网络资料，采取以上的方法解决问题 ，将从文件中读取出的一整行数据，经过拆分后，将各段数据分别存入结构体中的各个元素中去，问题得以解决。b、算法的时间复杂度和空间复杂度空间复杂度数据结构定义 5%散列部分 5%显示函数 5%查找部分5%添加部分10%删除部分10%处理函数30% 输入函数部分 10%主函数10%其他占：10%时间复杂度散列函数时, 输入信息函数, 显示函数,查找函数时间复杂度 O(n)主函数，转换函数时间复杂度O(n2);5.测试结果（1）、程序初始运行结果：（2）新建通讯录：（3） 读取用户信息（4） 解决冲突（5） 查找（号码 用户名 ）6.源程序（带注释）ty

12、pedef int Status;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;Stat

13、us NUM_BER; /记录的个数void getin(Record* a)/键盘输入各人的信息 printf(输入要添加的个数：n); scanf(%d,&NUM_BER); 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

14、* a)/显示输入的用户信息 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+; p

15、rintf(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 &c)/冲突处理函数，采用二次探测再

16、散列法解决冲突 int i,q; i=c/2+1; while(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; return UNSUCCESS;void benGetTime();void CreateHash1(HashTable* H,Record* a)/建表，以人的姓名为关键字，建立相应的散列表 /若哈希地址冲突，进行冲突处理 benGetTime(); int i,p=-1,c,pp; for(i=0;ielempp!=NULL) pp=collisi

17、on(p,c); if(ppelempp=&(ai); /求得哈希地址，将信息存入 H-count+; printf(第%d个记录冲突次数为%d。n,i+1,c);/需要显示冲突次数时输出 printf(n建表完成!n此哈希表容量为%d,当前表内存储的记录个数为%d.n,HASHSIZE,H-count); benGetTime();void SearchHash1(HashTable* H,int &c)/在通讯录里查找姓名关键字，若查找成功，显示信息 /c用来记录冲突次数,查找成功时显示冲突次数 benGetTime(); NA str; printf(n请输入要查找记录的姓名：n); s

18、canf(%s,str); int p,pp; p=Hash1(str); pp=p; while(H-elempp!=NULL)&(eq(str,H-elempp-name)=-1) pp=collision(p,c); if(H-elempp!=NULL&eq(str,H-elempp-name)=1) printf(n查找成功！n查找过程冲突次数为%d以下是您需要要查找的信息：nn,c); printf(姓 名：%sn电话号码：%sn联系地址：%sn,H-elempp-name,H-elempp-tel,H-elempp-add); else printf(n此人不存在，查找不成功!n)

19、; benGetTime();void benGetTime() SYSTEMTIME sys; GetLocalTime( &sys ); 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

20、=-1,c,pp; for(i=0;ielempp!=NULL) pp=collision(p,c); if(ppelempp=&(ai); /求得哈希地址，将信息存入 H-count+; printf(第%d个记录冲突次数为%d。n,i+1,c);/需要显示冲突次数时输出 printf(n建表完成!n此哈希表容量为%d,当前表内存储的记录个数为%d.n,HASHSIZE,H-count); benGetTime();void SearchHash2(HashTable* H,int &c)/在通讯录里查找电话号码关键字，若查找成功，显示信息 /c用来记录冲突次数,查找成功时显示冲突次数 be

21、nGetTime(); NA tele;printf(n请输入要查找记录的电话号码：n); scanf(%s,tele); int p,pp; p=Hash2(tele); pp=p; while(H-elempp!=NULL)&(eq(tele,H-elempp-tel)=-1) pp=collision(p,c); if(H-elempp!=NULL&eq(tele,H-elempp-tel)=1) printf(n查找成功！n查找过程冲突次数为%d以下是您需要要查找的信息：nn,c); printf(姓 名：%sn电话号码：%sn联系地址：%sn,H-elempp-name,H-elem

22、pp-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-c

23、ount=0; Record aMAXSIZE; while (1) printf(n ); printf(n 欢迎使用电话号码查找系统 ); printf(n ); printf(n 哈希表的设计与实现 ); printf(n 【1】. 添加用户信息 ); printf(n 【2】. 读取所有用户信息 ); printf(n 【3】. 以姓名建立哈希表(再哈希法解决冲突) ); printf(n 【4】. 以电话号码建立哈希表(再哈希法解决冲突) ); printf(n 【5】. 查找并显示给定用户名的记录 ); printf(n 【6】. 查找并显示给定电话号码的记录 ); printf(

24、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,&num); switch(num) case 1: getin(a); break; case 2: ShowInformation(a); break; case 3: CreateHash1(H,a);

25、 /* 以姓名建立哈希表 */ break; case 4: CreateHash2(H,a); /* 以电话号码建立哈希表 */ break; case 5: c=0; SearchHash1(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);二教学

26、计划编制问题。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。基本要求：1)输入参数：学期总数，一学期的学分上限，每门课的课程号(固定占3位的字母数字串，规定从C01C12)、学分和直接先修课的课程号；2)输出参数：输出提示信息，由用户在键盘上输入运行程序中规定的命令来指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学

27、期中；3)若根据给定的条件问题无解，则报告适当的信息，否则将教学计划输出到用户指定的文件中。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 VertexT

28、ypeMAX_NAME; /* 字符串类型*/ /* 图的邻接表存储表示*/ #define MAX_VERTEX_NUM 100 typedef enumDGGraphKind; /* 有向图,有向网,无向图,无向网 */ typedef struct ArcNode int adjvex; /* 该弧所指向的顶点的位置*/ struct ArcNode *nextarc; /* 指向下一条弧的指针*/ InfoType *info; /* 网的权值指针）*/ ArcNode; /* 表结点*/ typedef struct VertexType data; /* 顶点信息*/ ArcNod

29、e *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针*/ VNode,AdjListMAX_VERTEX_NUM; /* 头结点*/ typedef struct AdjList vertices,verticestwo; int vexnum,arcnum; /* 图的当前顶点数和弧数*/ int kind; /* 图的种类标志*/ ALGraph;2.算法设计1头结点，表结点，邻接表的定义#define MAX_VERTEX_NUM 100 /最大课程总数typedef struct ArcNode int adjvex; struct ArcNode *ne

30、xtarc; 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 *);创建邻接表vo

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

32、ices; 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. 函数的调用关系图StackEmpty()f ClearStack()FindInDegree()CreateGraph()Display()LocateVex()Main()4.调试分析A.在调试过程

33、中需要把输入的信息保存到一个文件夹中，在老师的帮助下以及上网查找下，最后解决了问题。解决问题参考代码如下：#include #include using namespace std; int main() 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.对于有n个定点，e条边的AOV网而言，拓扑排序算法中扫描表，将入度为0的顶点表，栈的时间复杂度为O（n），若为有向无回路，每个顶点进出栈各一次，共循环e次，所以整个算法复杂度为o（n+e）。5. 测试结果程序初始运行结果：6.源程序（带注释）using namespace std; / 函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status