查找和排序实验报告(共45页)

1、附件(fjin)（四）深 圳 大 学 实 验 报 告 课程名称： 数据结构(sh j ji u)实验(shyn)与课程设计 实验项目名称： 查找排序实验. 学院： 计算机与软件学院 专业： 指导教师： 报告人： 学号： 班级： 实验时间： 实验报告提交时间： 教务处制一、实验目的与完成说明：1. 简单介绍本实验的主要目的2. 说明你自己在本次实验中完成了第几项要求（必填）Contest1657 - DS实验-静态查找Problem A: 数据结构实验-静态查找之顺序查找主要目的：给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从1开始要求使用带哨兵的顺序查找算法Input第一行输入

2、n，表示队列有n个数据(完成)第二行输入n个数据，都是正整数，用空格隔开(完成)第三行输入t，表示有t个要查找的数值(完成)第四行起，输入t个数值，输入t行(完成)Output每行输出一个要查找的数值在队列的位置，如果查找不成功，输出字符串error(完成)Problem B: 数据结构实验-静态查找之折半查找主要目的：给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从1开始要求使用折半查找算法Input第一行输入n，表示队列有n个数据(完成)第二行输入n个数据，都是正整数，用空格隔开(完成)第三行输入t，表示有t个要查找的数值(完成)第四行起，输入t个数值，输入t行(完成)Out

3、put每行输出一个要查找的数值在队列的位置，如果查找不成功，输出字符串error(完成)Problem C: 数据结构实验-静态查找之顺序索引查找主要目的：给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从1开始(完成)要求使用顺序索引查找算法，其中索引表查找和块内查找都采用不带哨兵、从头开始的顺序查找方法。(完成)Input第一行输入n，表示主表有n个数据(完成)第二行输入n个数据，都是正整数，用空格隔开(完成)第三行输入k，表示主表划分为k个块，k也是索引表的长度(完成)第四行输入k个数据，表示索引表中每个块的最大值(完成)第五行输入t，表示有t个要查找的数值(完成)第六行起，

4、输入t个数值，输入t行(完成)Output每行输出一个要查找的数值在队列的位置和查找次数，数据之间用短划线隔开，如果查找不成功，输出字符串error(完成)Contest1040 - DS实验-动态查找Problem A: 数据结构实验-二叉排序树之创建和插入主要目的：给出一个数据序列，建立二叉排序树，并实现插入功能对二叉排序树进行中序遍历，可以得到有序的数据序列Input第一行输入t，表示有t个数据序列(完成)第二行输入n，表示首个序列包含n个数据(完成)第三行输入n个数据，都是自然数且互不相同，数据之间用空格隔开(完成)第四行输入m，表示要插入m个数据(完成)从第五行起，输入m行，每行一个

5、要插入的数据，都是自然数且和前面的数据不等(完成)以此类推输入下一个示例(完成)Output第一行输出有序的数据序列，对二叉排序树进行中序遍历可以得到(完成)从第二行起，输出插入第m个数据后的有序序列，输出m行(完成)以此类推输出下一个示例的结果(完成)Problem B: 数据结构实验-二叉排序树之查找主要目的：给出一个数据序列，建立二叉排序树，并实现查找功能(完成)对二叉排序树进行中序遍历，可以得到有序的数据序列(完成)Input第一行输入t，表示有t个数据序列(完成)第二行输入n，表示首个序列包含n个数据(完成)第三行输入n个数据，都是自然数且互不相同，数据之间用空格隔开(完成)第四行输

6、入m，表示要查找m个数据(完成)从第五行起，输入m行，每行一个要查找的数据，都是自然数(完成)以此类推输入下一个示例(完成)Output第一行输出有序的数据序列，对二叉排序树进行中序遍历可以得到(完成)从第二行起，输出查找结果，如果查找成功输出查找次数，如果查找失败输出-1(完成)以此类推输出下一个示例的结果(完成)Problem C: 数据结构实验-二叉排序树之删除主要目的：给出一个数据序列，建立二叉排序树，并实现删除功能对二叉排序树进行中序遍历，可以得到有序的数据序列Input第一行输入t，表示有t个数据序列(完成)第二行输入n，表示首个序列包含n个数据(完成)第三行输入n个数据，都是自然

7、数且互不相同，数据之间用空格隔开(完成)第四行输入m，表示要删除m个数据(完成)从第五行起，输入m行，每行一个要删除的数据，都是自然数(完成)以此类推输入下一个示例(完成)Output第一行输出有序的数据序列，对二叉排序树进行中序遍历可以得到(完成)从第二行起，输出删除第m个数据后的有序序列，输出m行(完成)以此类推输出下一个示例的结果(完成)Contest1050 - DS实验-哈希查找Problem A: 数据结构实验-哈希查找主要目的：给出一个数据序列，建立哈希表，采用求余法作为哈希函数，模数为11，哈希冲突用链地址法和表头插入如果首次查找失败，就把数据插入到相应的位置中实现哈希查找功能

8、Input第一行输入n，表示有n个数据(完成)第二行输入n个数据，都是自然数且互不相同，数据之间用空格隔开(完成)第三行输入t，表示要查找t个数据(完成)从第四行起，每行输入一个要查找的数据，都是正整数(完成)Output每行输出对应数据的查找结果(完成)Contest1060 - DS实验-排序算法Problem A: 数据结构实验-希尔排序主要目的：给出一个数据序列，使用希尔排序算法进行从小到大的排序间隔gap使用序列长度循环除2直到1Input第一行输入t，表示有t个测试示例(完成)第二行输入n，表示第一个示例有n个数据(完成)第三行输入n个数据，都是正整数，数据之间用空格隔开(完成)以

9、此类推Output每行输出每个示例排序后，从小到大的结果(完成)Problem B: 数据结构实验-快速排序主要目的：给出一个数据序列，使用快速排序算法进行从小到大的排序Input第一行输入t，表示有t个测试示例(完成)第二行输入n，表示第一个示例有n个数据(完成)第三行输入n个数据，都是正整数，数据之间用空格隔开(完成)以此类推Output每行输出每个示例排序后，从小到大的结果(完成)二、主要思路与方法：1. 对于本次实验，说明你认为最重要的函数、算法或知识点，并谈谈你对它们的理解Contest1657 - DS实验-静态查找Problem A: 数据结构实验-静态查找之顺序查找比起普通的顺

10、序查找，带哨兵的顺序查找是从表尾查到表头的，然后将表的第一位数赋值为要查找的值。这样做能够减少一个步骤，即在循环后减少几行判断语句来决定返回值。查到了就返回下标，下标为0即没有找到。Problem B: 数据结构实验-静态查找之折半查找需要排好序后才能进行折半查找。找22。1122334455667788LowMidHigh1122334455667788LowMidHigh找881122334455667788LowMidHigh1122334455667788LowMidHigh1122334455667788Low、MidHigh1122334455667788Low、Mid、HighP

11、roblem C: 数据结构实验-静态查找之顺序索引查找把一长条数据切割成几段，然后在这几段中分别取最代表性的数据作为索引数据，然后查找数据时先与这几个数据比较，找到符合条件的数据后再根这段里的数据比较。找53设定间隔为索引数目为3224886l=3;num=2;SS=12;22121389203342443824486058748653l=3+6=9; i=17; return i+1;(18)找90设定间隔为索引数目为3224886num=3; return 0;Contest1040 - DS实验-动态查找Problem A: 数据结构实验-二叉排序树之创建和插入按照大小顺序插入，如果孩

12、子为空，比父节点大插右边，比父节点小插左边；如果孩子不为空，父节点往右孩子或左孩子推移。Problem B: 数据结构实验-二叉排序树之查找根据左孩子比父节点小，右孩子比父节点大的特性，通过判断与父节点的大小左移或右移，找到后就返回该结点，输出移动的次数。Problem C: 数据结构实验-二叉排序树之删除如果左孩子或右孩子其中一个为空，直接把它们往父节点提。如果都为空，直接删除该结点。如果都不为空，从左子树中取最大的一个值与父节点交换，然后删除该结点。Contest1050 - DS实验-哈希查找Problem A: 数据结构实验-哈希查找01112323448563976286352975

13、10Contest1060 - DS实验-排序算法Problem A: 数据结构实验-希尔排序Gap表示取值的间隔和移动的次数。 gap=length/2;gap=6/2=3;1112264443335511144422333655gap/2=1111226444333552211162211162211144462211133344462255111333444排序完毕。gap=8/2=4;7755533144477666222277444775553366612222gap/2=2;7777331444555666222233774446661775552222gap/2=1;331777

14、7444555666222213313377133777713377774441337777444555133777744455566613377774445556662222排序完毕Problem B: 数据结构实验-快速排序第一种算法（有交换函数）：在low-high区间内找到比alow要小的值，high等于这个值的下标。然后alow和ahigh互换。在low-high区间内找到比ahigh要小的值，low等于这个值的下标。然后alow和ahigh互换。重复步骤直到low等于high。 low=0;high=n-1;(5)pivotloc=Partition(a,0,5);11122644

15、4333555511111144455226111333444pivotloc=3;a. QSort(a,low,pivotloc-1);QSort(a,0,2);b. QSort(a, pivotloc+1,high);QSort(a,4,5);(a)low=0;high=2;5522611133344465562255111333444privotloc=2;low=0;a. QSort(a,low,pivotloc-1);QSort(a,0,1);b. QSort(a, pivotloc+1,high); QSort(a,3,2);(a)low=0;high=1;622551113334

16、44privotloc=0;low=0;a. QSort(a,low,pivotloc-1); QSort(a,0,-1);b. QSort(a,pivotloc+1,high);QSort(a,1,1);(b) low=4;high=5;62255111333444privotloc=4;a. QSort(a,low,pivotloc-1); QSort(a,4,3);b. QSort(a,pivotloc+1,high); QSort(a,5,5);排序完毕。流程图：第二种改进算法（没有交换函数）：把low下标的值赋给一个临时变量在low high区间里找一个比临时变量小的值赋给low下标

17、的数组。这个值的下标赋给high。在low-high区间里找一个比临时变量大的值赋给high下标的数组。这个值的下标赋给low。重复步骤直到low等于high;把临时变量的值赋给low下标的数组。low=0;high=7;Partition(a,0,7);temp=77;7755533144477666222215553314447766622221555335554447766622221333355544477666222213377555444776662222pivotloc =2;a. QSort(a,low,pivotloc-1);QSort(a,0,1);b. QSort(a,

18、pivotloc+1,high);QSort(a,3,7);(b)low=3;high=7;Partition(a,3,7);temp=555;1337755544477666222277444776662222774445556662222pivotloc =5;a. QSort(a,low,pivotloc-1);QSort(a,3,4);b. QSort(a, pivotloc+1,high);QSort(a,6,7);(b)low=6;high=7;Partition(a,6,7);temp=666;13377774445556662222pivotloc =6a. QSort(a,l

19、ow,pivotloc-1);QSort(a,3,5);b. QSort(a, pivotloc+1,high);QSort(a,7,7);排序完毕。三实验程序或内容：1. 针对每一项实验要求，给出编写的代码，2. 可以粘贴全部代码，或者可以只粘贴重要的代码（为了节省纸张），但代码必须完整，至少是完整的函数。3. 代码符合以下要求，评分更高：a. 排版整齐，可读性高b. 代码有注释，越详细越清晰越好Contest1657 - DS实验-静态查找Problem A: 数据结构实验-静态查找之顺序查找#include using namespace std; int Search(int *Arr

20、aySize,int S,int n) int i; ArraySize0=S; for(i=n;!(ArraySizei-=S);); return i+1; int main() int n,i,t,S,num; cinn; int *ArraySize=new intn+1; for(i=0;+iArraySizei; /for cint; while(t-) cinS; num=Search(ArraySize,S,n); if(num) coutnumendl; /if else couterrorendl; /else /while return 0; /main Problem

21、B: 数据结构实验-静态查找之折半查找#include using namespace std; int Search(int *ArraySize,int S,int n) int low=1; int high=n; int mid; while(lowS)high=mid-1; else low=mid+1; return 0; int main() int n,i,t,S,num; cinn; int *ArraySize=new intn+1; for(i=0;+iArraySizei; /for cint; while(t-) cinS; num=Search(ArraySize,

22、S,n); if(num) coutnumendl; /if else couterrorendl; /else /while return 0; /main Problem C: 数据结构实验-静态查找之顺序索引查找#include using namespace std; int Search(int *ArraySize,int *max,int S,int n,int k,int &l) int num; int SS; for(num=-1;numk&!(S=max+num);l+); if(num=k)return 0; SS=(n/k)*(num); for(int i=SS-1

23、;+in; int *ArraySize=new intn; for(i=-1;+iArraySizei; /for cink; int *max=new intk; for(i=-1;+imaxi; /for cint; while(t-) cinS; l=1; num=Search(ArraySize,max,S,n,k,l); if(num) coutnum-lendl; /if else couterrorendl; /else /while return 0; /mainContest1040 - DS实验-动态查找Problem A: 数据结构实验-二叉排序树之创建和插入#incl

24、ude using namespace std; #define OK 1 #define ERROR 0 class TreeNode public: int data; TreeNode *LeftChild; TreeNode *RightChild; TreeNode()LeftChild=NULL;RightChild=NULL;data=0; ; class Tree public: TreeNode* Root; void CreateBinary(int *a,int size) if(size=0)return; Root=NULL; TreeNode *t; int len

25、gth=0; t=new TreeNode(); t-data=alength; Root=t; for(;+lengthdata=alength; InsertElem(Root,t); /for /CreateBinary void InsertElem(TreeNode *F,TreeNode *t) if(F-data data) if(F-RightChild) InsertElem(F-RightChild,t); /if else F-RightChild=t; /if else if(F-LeftChild) InsertElem(F-LeftChild,t); else F-

26、LeftChild=t; /else /InsertElem void InOrder() InOrder(Root); void InOrder(TreeNode *t) if(t) InOrder(t-LeftChild); coutdataRightChild); /if /InSearch ; int main() int t,n,i,num,N; Tree T; cint; while(t-) cinn; int *a=new intn; for(i=-1;+iai; /for T.CreateBinary(a,n); T.InOrder(); coutnum; while(num-

27、) cinN; TreeNode *tr=new TreeNode(); tr-data=N; T.InsertElem(T.Root,tr); T.InOrder(); coutendl; /while /while return 0; Problem B: 数据结构实验-二叉排序树之查找#include using namespace std; #define OK 1 #define ERROR 0 class TreeNode public: int data; TreeNode *LeftChild; TreeNode *RightChild; TreeNode()LeftChild

28、=NULL;RightChild=NULL;data=0; ; class Tree public: TreeNode* Root; bool Find; int times; void CreateBinary(int *a,int size) if(size=0)return; Root=NULL; TreeNode *t; int length=0; t=new TreeNode(); t-data=alength; Root=t; for(;+lengthdata=alength; InsertElem(Root,t); /for /CreateBinary void InsertEl

29、em(TreeNode *F,TreeNode *t) if(F-data data) if(F-RightChild) InsertElem(F-RightChild,t); /if else F-RightChild=t; /if else if(F-LeftChild) InsertElem(F-LeftChild,t); else F-LeftChild=t; /else /InsertElem void Searchfordata(TreeNode *t,int data) if(Find & t) times+; if(t-data=data) Find=false; else i

30、f(t-data data) Searchfordata(t-LeftChild,data); else Searchfordata(t-RightChild,data); int Searchfordata(int data) Find=true; times=0; Searchfordata(Root,data); if(Find)return -1; else return times; void InOrder() InOrder(Root); void InOrder(TreeNode *t) if(t) InOrder(t-LeftChild); coutdataRightChil

31、d); /if /InSearch ; int main() int t,n,i,num,N; Tree T; cint; while(t-) cinn; int *a=new intn; for(i=-1;+iai; /for T.CreateBinary(a,n); T.InOrder(); coutnum; while(num-) cinN; coutT.Searchfordata(N)endl; /while /while return 0; Problem C: 数据结构实验-二叉排序树之删除#include using namespace std; #define OK 1 #de

32、fine ERROR 0 class TreeNode public: int data; TreeNode *LeftChild; TreeNode *RightChild; TreeNode()LeftChild=NULL;RightChild=NULL;data=0; ; class Tree public: TreeNode* Root; bool Find; int times; void CreateBinary(int *a,int size) if(size=0)return; Root=NULL; TreeNode *t; int length=0; t=new TreeNo

33、de(); t-data=alength; Root=t; for(;+lengthdata=alength; InsertElem(Root,t); /for /CreateBinary void InsertElem(TreeNode *F,TreeNode *t) if(F-data data) if(F-RightChild) InsertElem(F-RightChild,t); /if else F-RightChild=t; /if else if(F-LeftChild) InsertElem(F-LeftChild,t); else F-LeftChild=t; /else

34、/InsertElem void Searchfordata(TreeNode *t,int data) if(Find & t) times+; if(t-data=data) Find=false; else if(t-data data) Searchfordata(t-LeftChild,data); else Searchfordata(t-RightChild,data); void Delete(TreeNode* &p) TreeNode *q; if(!p-RightChild) q=p;p=p-LeftChild;delete q; else if(!p-LeftChild

35、) q=p;p=p-RightChild;delete q; else q=p; TreeNode *s; s=p-LeftChild; while(s-RightChild)q=s;s=s-RightChild; p-data=s-data; if(q!=p)q-RightChild=s-LeftChild; else q-LeftChild=s-LeftChild; delete s; void delete_data(TreeNode* &t,int data) if(Find & t) if(t-data=data) Find=false; Delete(t); else if(t-d

36、ata data) delete_data(t-LeftChild,data); else delete_data(t-RightChild,data); /delete_data void delete_data(int data) Find=true; delete_data(Root,data); int Searchfordata(int data) Find=true; times=0; Searchfordata(Root,data); if(Find)return -1; else return times; void InOrder() InOrder(Root); void

37、InOrder(TreeNode *t) if(t) InOrder(t-LeftChild); coutdataRightChild); /if /InSearch ; int main() int t,n,i,num,N; Tree T; cint; while(t-) cinn; int *a=new intn; for(i=-1;+iai; /for T.CreateBinary(a,n); T.InOrder(); coutnum; while(num-) cinN; T.delete_data(N); T.InOrder(); coutendl; /while /while ret

38、urn 0; Contest1050 - DS实验-哈希查找Problem A: 数据结构实验-哈希查找#include using namespace std; #define SUCCESS 1 #define UNSUCCESS 0 #define DUPLICATE -1 #define OK 1 #define Status int class Link public: Link*next; int data; Link()next=NULL; ; class HashTable public: Link *elem;/数据元素存储基址，动态分配数组 int count;/当前数据元

39、素个数 int sizeindex;/hashsizesizeindex为当前容量 Status NewElem(int size) elem=new Linksize; count=0; sizeindex=size; for(int i=-1;+isizeindex;) elemi.data=NULL; return SUCCESS; /NewElem int Hash(int data) return data%11; /Hash Status InsertHash(int data) int c=0; int p; if(SearchHash(data,p,c)return DUPLI

40、CATE; else if(pdata=data; count+; elemp.next=temp; return OK; else Link *temp=new Link(); temp-data=data; Link *q=elemp.next; temp-next=q; elemp.next=temp; return OK; /InsertHash Status SearchHash(int data,int &p,int &c) p=Hash(data); Link *q=elemp.next; while(q!=NULL & data!=q-data) if(q-next!=NULL

41、) q=q-next; c+; else break; if(q!=NULL & data=q-data) return SUCCESS; else return UNSUCCESS; /SearchHash ; int main() HashTable HT; int n,Data,t,p,c; cinn; HT.NewElem(11); for(int i=-1;+iData; HT.InsertHash(Data); /for cint; while(t-) cinData; c=1; if(HT.SearchHash(Data,p,c) coutp cendl; else couter

42、rorendl; HT.InsertHash(Data); return 0; Contest1060 - DS实验-排序算法Problem A: 数据结构实验-希尔排序#include using namespace std; class ShellSort public: void display(int *a,int length) int i; for(i=-1;+ilength-1;) coutai ; coutai1) / coutgapendl; for(start=-1;+startgap;) for(i=gap+start;i=0;j-=gap) if(aj=atemp)br

43、eak; swap(&aj,&atemp); temp=j; /for /for / display(a,length); /for gap/=2; /while / cout最后进行一次直接插入排序endl; /最后进行一次直接插入排序 for(i=0;+i=0;-j) if(ajt; while(t-) cinn; int *data=new intn; for(i=-1;+idatai; /for SS.Shell_Sort(data,n); for(i=-1;+in;) coutdatai ; /for coutendl; /while return 0; /intProblem B:

44、 数据结构实验-快速排序第一种算法：#include using namespace std; class QuickSort public: void swap(int *a,int *b) (*a)=(*b)=(*a)=(*b); int Partition(int *a,int low,int high) int pivotkey=alow; while(lowhigh) while(low=pivotkey)-high; if(low!=high) swap(&alow,&ahigh); while(lowhigh & alow=pivotkey)+low; if(low!=high)

45、 swap(&alow,&ahigh); /while return low; void QSort(int *a,int low,int high) int pivotloc; if(lowt; while(t-) cinn; int *data=new intn; for(i=-1;+idatai; /for QS.QSort(data,0,n-1); for(i=-1;+in;) coutdatai ; /for coutendl; /while return 0; /int第二种改进算法：#include using namespace std; class QuickSort pub

46、lic: int Partition(int *a,int low,int high) int temp=alow; int pivotkey=alow; while(lowhigh) while(low=pivotkey)-high; if(low!=high) alow=ahigh; while(lowhigh & alow=pivotkey)+low; if(low!=high) ahigh=alow; /while alow=temp; return low; void QSort(int *a,int low,int high) int pivotloc; if(lowt; while(t-) cinn; int *data=new intn; for(i=-1;+idatai; /for QS.QSort(data,0,n-1); for(i=-1;+in;) coutdatai ; /for coutendl; /while return 0; /int四、实验结论： 1、根据你完成的每个实验要求，给出相应的实验结果图，并结合图来解析运行过程2、如果运行过程简单，只要贴出VC运行的结果图。3、如果无结果图，有网站的判定结果，贴出相应结果Contest1657 - DS实验-静态查找Problem A: 数据结构实验-静态查找之顺序查找Sample Inp