数据结构课程设计

哈希表的设计与::李祥:软件班级:学号哈希表的设计与::李祥:软件班级:学号目录一、设计任 二、设计方 目录一、设计任 二、设计方 三、详细设 结点 单链表 哈希表 菜 主函 四、测试与分 输入数 运行结 简单分 五、课程设计总 ()节点 单链表 哈希表 菜单 主函 设计哈希表,O(1),但是由于”的限制只能尽可能让它的的时间复杂度接近O(1)设计哈希表的关键在于构造哈希函数,设计哈希表,O(1),但是由于”的限制只能尽可能让它的的时间复杂度接近O(1)设计哈希表的关键在于构造哈希函数,常见哈希函数的构造方法有:1.直接定址法;2.数字分析法;3.平方取中法;4.折中法;5.除留余数法;6.随机数法。实际情况下,”,在眉睫,出区的方法:1.开放地址法;2.再哈希法;3.链地址法;4.3的方法(链地址法)结合起来,来实现哈希表的设计比较合理。即用一个数组数组元素为链表的头指针。当然,为了使链表便于操作,主要类简介结点类:由数据域data和指针域next组成哈希表类:由指向动态数组的指针listsize和哈希表的元素总个数3)链表类:由链表的结点个数个数)numhead类间的关系list指向一个动态数组数组指针size大小为哈希表总元素个数length14;(见图-数据元素的类型定类型定1°将整型数 定义为结点数据成员2°指针域成员函数1°HTYPE&Data();2°NODE*&Next();^8^^^^^^^^^2120212202^8^^^^^^^^^2120212202单链表数据成1°链表长度(num, 个数2°链表头指针(head,成员函结点的单链表1°LLIST();构造函数,数据成员head通过new运算符得到一单链表数据成1°链表长度(num, 个数2°链表头指针(head,成员函结点的单链表1°LLIST();构造函数,数据成员head通过new运算符得到一个附加头结2°~LLIST();析构函数清空链表3°LLIST(constLLIST&x);拷贝构造函数4°LLIST&operator=(constLLIST&x);赋值函数5°Clear();清除函数,清空链表6°Input();输入函数输入多个数据,它调用Insert(x)函函数每次调用只能插一个数据10°Traverse();11°Num();返回链表的长度12°Head();取表头指13°Copy(*p,*q)q一张由p指向的单链哈希表数据成1(list)3°哈希表的元素总个数4°一2)成员函类型的静态常量(defaultSize,数组初值1°HASHTABLE();构造函数,用指针list指针new一个大小为size的数2°~HASHTABLE();析构函数list指针所申请的的内存空SHTABLE&x);拷贝构造函数4°HASHTABLE&operatorSHTABLE&x);赋值函数5°Input();输入函数输入多个数据,它调用Insert(x)函数函数7°Remove(x);删除一个目8°Search(x,i,j);xij9°Traverse();遍历，打印哈希表的所有元素10°FTraverse(x);遍历,打x的所有元11°Number(x);返回哈希表元素的总个12°Length();返x的数据的个13°Hash(x);哈希函数菜无数据成函1°YesNo(*question);问(*prompt,*option)6.主函1°运用菜单运行并测试数1.输入数425214312105054212431254 5431°YesNo(*question);问(*prompt,*option)6.主函1°运用菜单运行并测试数1.输入数425214312105054212431254 543800004654654624624324324323242.运行结**P**RT遍历哈希表F遍 相等的数ISL数据总个数相等的数据的个数Q退 请输入数据，以零(0)结束：425214312105054212431434543800004654654624624324324324324**PT遍历哈希表F遍 相等的数**RSL数据总个数相等的数据的个数Q退 1组(2组(3组(4组(5组(6组(7组(8组(0为1为2为3为4为5为6为7为2432323232323264123452565234510433444444441242124545462**P**RTFI相等的数据的个数Q退 SL数据总个数元素**PT遍历哈希表F遍 相等的数**RSL数据总个数相等的数据的个数Q退 1组(2组(3组(4组(5组(6组(7组(8组(0为1为2为3为4为5为1组(2组(3组(4组(5组(6组(7组(8组(0为1为2为3为4为5为6为7为2432323232323264123452565234510433444444441242128000044545462**P**RT遍历哈希表F遍 相等的数ISL数据总个数相等的数据的个数Q退 4444444444444124212800004**P**RT遍历哈希表F遍 相等的数ISL数据总个数相等的数据的个数Q退 请输入需要删除的数据80000004x(y/n)：n**PT遍历哈希表F遍 相等的数**RSL数据总个数相等的数据的个数Q退 ：4444444444444124212**PT遍历哈希F遍 相等的数**RSL 相等的数据的个数Q退 请输入需要删除的数据**P**RT遍历哈希表F遍 相等的数ISL数据总个数相等的数据的个数Q退 4124212**PT遍历哈希表F遍 相等的数**RSL数据总个数相等的数据的个数Q退 请输入需要查询的数据4124212**PT遍历哈希表F遍 相等的数**RSL数据总个数相等的数据的个数Q退 请输入需要查询的数据5**PT遍历哈希表F遍 相等的数**RSL数据总个数相等的数据的个数Q退 请输入需要查询的数据5**PT遍历哈希表F遍 相等的数**RSL数据总个数相等的数据的个数Q退 数据总个数**PT遍历哈希表F遍 相等的数**RSL数据总个数相等的数据的个数Q退 相等的数据的个数34124212**PT遍历哈希表F遍 相等的数**RSL数据总个数相等的数据的个数Q退 Pressanykeyto3.简单分五、课程设计总结1)第一次单独完成一个比较大的程序,虽然花了几天时间,而且遇到不少问题,但是通过学习、思五、课程设计总结1)第一次单独完成一个比较大的程序,虽然花了几天时间,而且遇到不少问题,但是通过学习、思考,最终还是完整的做出来了,感觉蛮高兴的。2)完全用C++的类做完这个程序,更深次地体会到,类,应该把涉及它的所有操作(成员函数)都应该做出来,把它们封装在一起。而其它类(,数据成员的类(内部类)去操作数据成员,要交流,遇到问题,既要同老师交流,也应该和同学交流,率。最重要的是 作为学习软件工程的学生,遇到问题时,要学会利用搜索引擎切勿让优厚的资源没有被浪费掉,毕竟站在巨人的肩膀上六、附录()1.节点{HTYPE&Data();NODE*&Next();HTYPEdata;//数据域NODE*next;////返回数据域HTYPE&{returnthis-}//返回指针域NODE*{returnthis-}2.单链表classLLIST//{//析构函LLIST(constLLIST2.单链表classLLIST//{//析构函LLIST(constLLIST&x);//赋值函LLIST&operatorboolClear();boolboolInsert(const//删除一个目boolRemove(const//查NODE*Find(constHTYPE//遍boolTraverse()//链表长度，Num()//取表NODE*Head()num;//链表长度，NODE*head;//newicvoidCopy(NODE*p,NODE{head=newNODE;head->Next()=NULL;num=0;}{deletehead;}{deletehead;}LLIST::LLIST(constLLIST&x){head=newNODE;head->Next()=NULL;Copy(head,x.head);num=x.num;}//赋值函LLIST&LLIST::operator{if(this!={Copy(head,x.head);num=x.num;}return}//清除函bool{NODEwhile(s=head-{head->Next()=s->Next();deletes;}num=0;returntrue;}bool{HTYPEwhile(cin>>x,{}return}//单个的加目boolLLIST::Insert(const{NODENODE*p=head,*q=NODE*p=head,*q=head->Next();while(q&&q->Data()<x){p=q=p-}s=newNODE;s->Data()=s->Next()=p->Next()=s;num++;return}//删除一个目boolLLIST::Remove(constHTYPE{i=charNODE*p,coutx(y/n)：";cin>>c;if(c=={if(p=Find(x,{s=p-p->Next()=s->Next();deletes;num--;returntrue;}}{while(p=Find(x,i))if(p=Find(x,i)){s=p-p->Next()=s->Next();deletes;num--}return}return}//查NODE*LLIST::Find(constHTYPE{NODE*p,*q;i=1;for(p=head,q=p->Next();q;{if(q->Data()==}&i)i++,p=p->Next(),qreturnq?p:}//遍boolLLIST::Traverse(){NODEreturnq?p:}//遍boolLLIST::Traverse(){NODE*p=for(p=p->Next();p;p=p-{cout<<''<<p-}cout<<endl;returntrue;}//链表长度，LLIST::Num(){return}//取表NODE*LLIST::Head(){return} voidLLIST::Copy(NODE*p,NODE{NODEfor(q=q->Next();q;q=q-{s=news->Data()=q->Data();p->Next()=s;p=}p->Next()=}3.哈希表classHASHTABLE//{const defaultSize;//数组初//析构函//拷贝构造函//赋值函SHTABLEHASHTABLE&operatorbool//单个的加目bool//删bool//查bool//遍历哈希bool//赋值函SHTABLEHASHTABLE&operatorbool//单个的加目bool//删bool//查bool//遍历哈希boolTraverse()boolFTraverse(&x)Length()const;//x的数据的个&x)LLIST*list;//动态数组指针size,length;////哈希函 链地址x)//数组初=//构造函HASHTABLE::HASHTABLE():size(defaultSize),{list=newLLIST}{delete[]}{SHTABLEsize=x.size;length=x.length;list=newLLIST[size];for(i=0;i<size;i++){list[i]=}}//赋值函HASHTABLE&HASHTABLE::operator{if(this!={size=x.size;length=x.length;list=newLLIST[size];for{list[i]=}}//赋值函HASHTABLE&HASHTABLE::operator{if(this!={size=x.size;length=x.length;list=newLLIST[size];for(i=0;i<size;i++){list[i]=}}return}bool{HTYPEwhile(cin>>x,{}return}//单个的加目bool{length++;return}//删bool{i=return}//查bool{booli=if(list[i].Find(x,j))t=true;elset=false;return}//遍历哈希boolHASHTABLE::Traverse(){{i=0;i<size;cout第i1"组("i"为}return}//遍历哈希boolHASHTABLE::Traverse(){{i=0;i<size;cout第i1"组("i"为}return}//遍历具有相bool{&x)cout<<" 为x数据有：";return}HASHTABLE::Length()const{return}//x的数据的个&x){return}//哈希函 链地址{returnx%}x)4.菜单class{icboolYesNo(constcharic(constchar*prompt,charboolMYIO::YesNo(constchar{charcout<<while(!strchr("YN",answer={cout<<}cout<<{charcout<<while(!strchr("YN",answer={cout<<}cout<<answer<<endl;returnanswer=='Y';}char{(constchar*prompt,constcharcharcout<<wh