實驗報告查找算法

查找算法性能研究設計題目查找算法性能研究2.設計內(nèi)容對以下存儲表示的數(shù)據(jù)進行查找算法進行比較:順序存儲、有序順序存儲、鏈表存儲、二叉排序樹存儲.首先生成不少于2000個隨機數(shù)按要求存儲，然后隨機生成若干個數(shù)據(jù)進行查找。統(tǒng)計每次查找所用的時間及平均使用時間，最后對結(jié)果作出簡單分析及討論.流程圖結(jié)果#include<stdio.h>#include<stdlib.h>#include<iostream>staticconstintARRAY_MAX=10000;typedefintDataType;classSequentialStorage{ public: DataTypedata[ARRAY_MAX]; inttop; SequentialStorage() { top=-1; } voidinsertData(DataTypedata) { if(top==ARRAY_MAX-1) return; this->data[++top]=data; } intfind(DataTypedata) { for(inti=0;i<=top;i++) { if(this->data[i]==data) returni; } return-1; }};classOrderlySequenceStorage{ public: DataTypedata[ARRAY_MAX]; inttop; OrderlySequenceStorage() { top=-1; } voidinsertData(DataTypedata)//插入排序 { if(top==ARRAY_MAX-1) return; inti=top; while(this->data[i]>data&&i!=-1) { this->data[i+1]=this->data[i]; i--; } this->data[i+1]=data; top++; } intfind(DataTypedata)//普通查找 { for(inti=0;i<=top;i++) { if(this->data[i]==data) returni; } return-1; } intfind2(DataTypedata)//二分法 { if(this->data[0]>data||this->data[top]<data) return-1; if(this->data[0]==data) return0; if(this->data[top]==data) returntop; inta=0; intb=top; while(true) { if(a==b-1) return-1; if(this->data[(a+b)/2]==data) return(a+b)/2; elseif(this->data[(a+b)/2]<data) a=(a+b)/2; else b=(a+b)/2; } }};typedefstructnode{ DataTypedata; structnode*pNext;}LLSNode;classLinkedListStorage{public: LLSNode*pHead; LinkedListStorage() { pHead=NULL; } voidinsertData(DataTypedata) { LLSNode*p=(LLSNode*)malloc(sizeof(LLSNode)); p->data=data; p->pNext=pHead; pHead=p; } LLSNode*find(DataTypedata) { LLSNode*p=pHead; while(p) { if(p->data==data) returnp; p=p->pNext; } returnNULL; }};typedefstructnode2{ DataTypedata; structnode2*lchild,*rchild;}BSTNode;classBinarySortTree{public: BSTNode*pRoot; BinarySortTree() { pRoot=NULL; } voidinsertData(DataTypedata) { BSTNode*f,*p=pRoot; while(p) { f=p; if(data<p->data) p=p->lchild; else p=p->rchild; } p=(BSTNode*)malloc(sizeof(BSTNode)); p->data=data; p->lchild=NULL; p->rchild=NULL; if(pRoot==NULL) pRoot=p; else if(data<f->data) f->lchild=p; else f->rchild=p; } BSTNode*find(DataTypedata) { if(pRoot==NULL) returnNULL; else returnrecursion(data,pRoot); } BSTNode*recursion(DataTypedata,BSTNode*p) { if(data==p->data||p==NULL) returnp; elseif(data<p->data) returnrecursion(data,p->lchild); else returnrecursion(data,p->rchild); } voidprint() { if(pRoot!=NULL) printR(pRoot); } voidprintR(BSTNode*p) { if(p->lchild!=NULL) printR(p->lchild); printf("%d\t",p->data); if(p->rchild!=NULL) printR(p->rchild); }};classCPUTime{public: _int64getCPUCycleCount(void) { _asm_emit0x0F _asm_emit0x31 } longlongarr[1000]; intcount; longlonglastCPUCycleCount; intrandCount; CPUTime() { for(inti=0;i<1000;i++) arr[i]=0; count=-1; lastCPUCycleCount=getCPUCycleCount(); randCount=0; } voidsetTimePoint() { arr[++count]=getCPUCycleCount()-lastCPUCycleCount; lastCPUCycleCount=getCPUCycleCount(); } intrand() { randCount++; inttemp=getCPUCycleCount()%20000; return(temp*(randCount+temp))%10007; }};intmain(){ SequentialStoragess; OrderlySequenceStorageoss; LinkedListStoragells; BinarySortTreebst; DataTypetemp1; CPUTimecpuTime; for(inti=0;i<2000;i++) { temp1=cpuTime.rand(); ss.insertData(temp1); oss.insertData(temp1); lls.insertData(temp1); bst.insertData(temp1); } DataTypetemp[7]; for(inti=0;i<7;i++) temp[i]=ss.data[cpuTime.rand()%2000]; cpuTime.setTimePoint(); for(inti=0;i<7;i++) { ss.find(temp[i]); cpuTime.setTimePoint(); } for(inti=0;i<7;i++) { oss.find(temp[i]); cpuTime.setTimePoint(); } for(inti=0;i<7;i++) { oss.find2(temp[i]); cpuTime.setTimePoint(); } for(inti=0;i<7;i++) { lls.find(temp[i]); cpuTime.setTimePoint(); } for(inti=0;i<7;i++) { bst.find(temp[i]); cpuTime.setTimePoint(); } intcount=1; printf("各項存儲結(jié)構查找已存在數(shù)據(jù)的時間（cpu周期）：\n"); printf("儲存方式\t\t數(shù)據(jù)\t數(shù)據(jù)\t數(shù)據(jù)\t數(shù)據(jù)\t數(shù)據(jù)\t數(shù)據(jù)\t平均\n"); inta[9]; for(inti=1;i<8;i++) a[i]=(int)cpuTime.arr[count++]; a[8]=(a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7; printf("順序存儲\t\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]); for(inti=1;i<8;i++) a[i]=(int)cpuTime.arr[count++]; a[8]=(a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7; printf("有序順序存儲(普通)\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]); for(inti=1;i<8;i++) a[i]=(int)cpuTime.arr[count++]; a[8]=(a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7; printf("有序順序存儲(二分法)\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]); for(inti=1;i<8;i++) a[i]=(int)cpuTime.arr[count++]; a[8]=(a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7; printf("鏈表存儲\t\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]); for(