C++查找与排序实验.docx

附件（四）深 圳 大 学 实 验 报 告 课程名称： 数据结构实验与课程设计 实验项目名称： 树结构实验 学院： 计算机与软件学院 专业： 软件工程 指导教师： 报告人： 学号： 班级： 实验时间： 实验报告提交时间： 教务处制一、实验目的与完成说明：数据结构实验-哈希查找给出一个数据序列，建立哈希表，采用求余法作为哈希函数，模数为11，哈希冲突用链地址法和表头插入如果首次查找失败，就把数据插入到相应的位置中实现哈希查找功能数据结构实验-希尔排序给出一个数据序列，使用希尔排序算法进行从小到大的排序间隔gap使用序列长度循环除2直到1数据结构实验-快速排序第一行输入t，表示有t个测试示例第二行输入n，表示第一个示例有n个数据第三行输入n个数据，都是正整数，数据之间用空格隔开以此类推二、主要思路与方法：哈希查找：给定K值，根据造表时设定的哈希函数得到哈希地址，若此表中此位置没有记录，则查找不成功，否则比较关键字，若何给定值相等，则查找成功；否则根据造表时设定的处理冲突的方法找下一地址，直至哈希表的某个位置为空或表中记录的关键字等于给定的定值时为止。希尔排序： 先将整个待排记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。 快速排序：通过一趟排序将待排记录分割成独立的两个部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。三实验程序或内容： 哈希查找：#include using namespace std; class node public: int data; node* next; node()data=0;next=NULL; ; int main() int n; bool visit11; for(int z=0;zn; int a20; for(i=0;iai; int target,temp; node mylistnode11; for(i=0;idata=ai; mylistnodetemp.next=s; visittemp=true; else node* p=mylistnodetemp.next; node* q=new node(); q-data=ai; mylistnodetemp.next=q; q-next=p; int t; cint; while(t-) cintarget; int t1=target%11; if(!visitt1) couterrordata=target; mylistnodet1.next=r; visitt1=true; else int flag=0; int count=0; node* x=mylistnodet1.next; while(x!=NULL) count+; if(x-data=target) flag=1; break; x=x-next; if(flag=0) node* n2=mylistnodet1.next; node* newnode=new node(); newnode-data=target; mylistnodet1.next=newnode; newnode-next=n2; couterrorendl; else coutt1 ; coutcountendl; return 0; 希尔排序：#include using namespace std; class haxi public: void ShellInsert(int list,int dk,int length) int i,j; for(i=dk+1;i=length;+i) if(listi0 & (list0listj);j-=dk) listj+dk=listj; listj+dk=list0; void ShellSort(int list,int dlta,int t,int length) for(int k=0;kt; while(t-) haxi hh; int n,*p,m10,j,k=0; cinn; p=new intn; for(int i=1;ipi; j=n/2; while(j!=0) mk=j; j=j/2; +k; hh.ShellSort(p,m,k,n); for(int dp=1;dp=n;dp+) coutpdp ; coutendl; return 0; 快速排序：#include using namespace std; class fast private: int pivotkey; public: int partion(int list,int low,int high) list0=listlow; pivotkey = listlow; while(lowhigh) while(low=pivotkey) -high; listlow=listhigh; while(lowhigh & listlow=pivotkey) +low; listhigh=listlow; listlow=list0; return low; void sort(int list,int low,int high) if(lowt; while(t-) int n; cinn; fast ff; list = new intn+1; for(int i=1;ilisti; ff.partion(list,0,n); ff.sort(list,0,n); ff.quicksort(list,n); for(int j=1;j=n;j+) coutlistj