数据结构 程序设计（C++）

#include<StdAfx.h>

#include<iostream.h>

#include<string.h>

#include<stdlib.h>

/*栈*/

template <class T>

class CStack

{

public:

int m_count

T * m_arr

int m_curposition

CStack(int count)

{

m_arr = new T [count]

m_count = count

m_curposition = -1

}

bool push(T val)

{

if(m_curposition == m_count-1)

return false

m_arr[++m_curposition] = val

}

T pop()

{

if(IsEmpty())

return 0

return m_arr[m_curposition--]

}

T GetElement()

{

if(IsEmpty())

return 0

return m_arr[m_curposition]

}

bool IsEmpty()

{

if(m_curposition <0)

return true

return false

}

~CStack()

{

delete [] m_arr

}

}

/* *** 作函数定义 */

bool ExpressionIsRight(char * pExpression) // 表达式是否正确

bool ProcessExpression(char * pExpression) // 处理表达式

int GetIndex(char ch) // 获取 *** 作符在数组中的下标

void Calculate() // 计算

double GetResult() // 得到结果

bool IsEnd(char ch)// 表达式是否结束

double GetNum(char *pStr, int &i) // 获取 *** 作数

CStack<char>stack_sign(100) // 运算符栈CStack<double>stack_num(100) // *** 作数栈

//运算符号优先级表

int PriTbl[7][7]={

{1,1,-1,-1,-1,1,1},

{1,1,-1,-1,-1,1,1},

{1,1,1,1,-1,1,1},

{1,1,1,1,-1,1,1},

{-1,-1,-1,-1,-1,0,2},

{1,1,1,1,2,1,1},

{-1,-1,-1,-1,-1,2,0}

}

bool ExpressionIsRight(char * pExpression)

{

int len = strlen(pExpression)

char arr[7] = {'+','-','*','/','(',')','.'}

for(int i=0i<leni++)

{

if(!(pExpression[i]>='0' &&pExpression[i]<='9'))

{

if(pExpression[0] == '.' || pExpression[len-1] == '.')

return false

int flag = 0

for(int j=0j<sizeof(arr)j++)

{

if(pExpression[i] == arr[j])

{

flag = 1

break

}

}

if(flag == 0)

return false

}

}

return true

}

bool ProcessExpression(char * pExpression)

{

if(!ExpressionIsRight(pExpression))

return false

int len = strlen(pExpression)

pExpression[len++] = '#'

stack_sign.push('#')

if(len == 1)

return false

for(int i=0i<leni++)

{

if(pExpression[i] >= '0' &&pExpression[i] <= '9') // *** 作数

{

double val = GetNum(pExpression, i)

stack_num.push(val)

}

else // *** 作符

{

int pre = GetIndex(stack_sign.GetElement())

int next = GetIndex(pExpression[i])

switch(PriTbl[pre][next])

{

case -1:// next >pre

stack_sign.push(pExpression[i])

break

case 0: // next = pre

if(IsEnd(pExpression[i]))

return true

stack_sign.pop()

break

case 1: // next <pre

Calculate()

i--// back

break

}

}

}

return true

}

double GetNum(char *pStr, int &i)

{

char Nums[100]

int j = 0

while((pStr[i] >= '0' &&pStr[i] <= '9') || pStr[i]=='.')

Nums[j++] = pStr[i++]

i--

Nums[j] = '\0'

return atof(Nums)

}

int GetIndex(char ch)

{

switch(ch)

{

case '+': return 0

case '-': return 1

case '*': return 2

case '/': return 3

case '(': return 4

case ')': return 5

case '#': return 6

}

}

void Calculate()

{

double num1, num2

num2 = stack_num.pop()

if(stack_num.IsEmpty())

{

cout <<"表达式错误！" <<endl

exit(0)

}

num1 = stack_num.pop()

switch(stack_sign.pop())

{

case '+': stack_num.push(num1+num2)return

case '-': stack_num.push(num1-num2)return

case '*': stack_num.push(num1*num2)return

case '/':

{

if(num2 == 0)

{

cout <<"除数不能为0！程序终止！" <<endl

exit(0)

}

stack_num.push(num1/num2)

return

}

}

}

bool IsEnd(char ch)

{

if(ch == '#')

if(stack_sign.GetElement() == ch)

return true

return false

}

double GetResult()

{

if(stack_sign.GetElement() != '#')

{

cout <<"表达式错误！" <<endl

exit(0)

}

return stack_num.GetElement()

}

//穷举法

void FindBro1(int * pArray,int nCount)

{

int * pTemp = new int[nCount]

for(int i=0i<nCounti++)

{

pTemp[i]=-1

for(int j=i+1j<nCountj++)

{

if(pArray[j]>=pArray[i])//找到

{

pTemp[i]=j

break

}

}

}

cout<<"结果："

for(int m=0m<nCountm++)

{

cout<<pTemp[m]<<" "

}

cout<<endl<<endl

delete []pTemp

}

//栈方法

void FindBro2(int * pArray,int nCount)

{

CStack<int>stack_bro(nCount)

for(int i=nCount-1i>=0i--)

{

stack_bro.push(-1)

for(int j=i+1j<nCountj++)

{

if(pArray[j]>=pArray[i])//找到

{

stack_bro.pop()

stack_bro.push(j)

break

}

}

}

cout<<"结果："

while(!stack_bro.IsEmpty())

{

cout<<stack_bro.pop()<<" "

}

cout<<endl<<endl

}

void FindBro(int nmode)//nmode为1时，是用普通穷举法，为2时，加入栈编程

{

int nCount

cout <<"请输入元素个数：\n"

cin>>nCount

int *pArray = new int[nCount]

for(int i=0i<nCounti++)

{

printf("请输入第%d个元素的值：\n",i+1)

cin>>pArray[i]

}

if(nmode==1)

{

FindBro1(pArray,nCount)

}

else

{

FindBro2(pArray,nCount)

}

delete []pArray

return

}

//表达式

void express()

{

char strExpression[100]

cout <<"请输入算术表达式："

cin >>strExpression // 输入表达式

if(!ProcessExpression(strExpression)) // 处理表达式

{

cout <<"表达式错误！" <<endl<<endl

}

else

cout <<"计算结果：" <<GetResult() <<endl<<endl // 输出结果

}

void main()

{

cout <<"1. 表达式求值：\n"

express() //表达式求值

cout <<"2. 数组穷举法，找亲兄弟：\n"

FindBro(1)//数组穷举法，找亲兄弟

cout <<"3. 借助栈编程，找亲兄弟：\n"

FindBro(2)//借助栈进行

}

表达式部分参考了网上的一个方法

《数据结构》试题一、选择题（每小题2分，共30分）1． 若某线性表中最常用的 *** 作是取第i 个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。A、单链表 B、双链表 C、单向循环 D、顺序表2． 串是任意有限个（ ）A、符号构成的序列B、符号构成的集合C、字符构成的序列D、字符构成的集合3． 设矩阵A（aij ，l≤i,j≤ 10）的元素满足：aij≠0(i≥j, l≤i, j≤ 10)aij=0 (i<j, l≤i, j≤ 10)现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则元素A[9][5]的首址为A、2340 B、2336 C、2164 D、21604． 如果以链表作为栈的存储结构，则退栈 *** 作时（ ）A、 必须判别栈是否满B、 对栈不作任何判别C、 必须判别栈是否空D、 判别栈元素的类型5． 设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队 *** 作的语句为（ ）A、front=front+1 B、front=(front+1)% mC、rear=(rear+1)%m D、front=(front+1)%(m+1)6． 深度为6（根的层次为1）的二叉树至多有（ ）结点。A、 64B、32 C、31D、637． 将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49的结点X的双亲编号为（ ）A、24 B、25 C、23D、无法确定8． 设有一个无向图G=（V，E）和G’=（V’，E’）如果G’为G的生成树，则下面不正确的说法是（ ）A、G’为G 的子图 B、G’为G 的边通分量C、G’为G的极小连通子图且V’=V D、G’为G的一个无环子图9． 用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（ ）A、 一定都是同义词B、一定都不是同义词 C、都相同 D、不一定都是同义词10． 二分查找要求被查找的表是（ ）A、 键值有序的链接表 B、链接表但键值不一定有序C、 键值有序的顺序表 D、顺序表但键值不一定有序11． 当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（ ）A、n2 B、nlog2n C、log2n D、n-1 12． 堆是一个键值序列{k1,k2,…, kn},对i=1,2,…,|_n/2_|,满足( )A、ki≤k2i≤k2i+1B、ki<k2i+1<k2iC、ki≤k2i且ki≤k2i+1(2i+1≤n) D、ki≤k2i 或ki≤k2i+1(2i+1≤n) 13．一个具有n个顶点的无向完全图的边数为（　）A、n(n+1)/2B、n(n-1)/2C、n(n-1)D、n(n+1)14．在索引顺序表中查找一个元素，可用的且最快的方法是（　）A、用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找B、用顺序查找法确定元素所在块，再用二分查找法在相应块中查找C、用二分查找法确定元素所在块，再用顺序查找法在相应块中查找D、用二分查找法确定元素所在块，再用二分查找法在相应块中查找15．若某线性表中最常用的 *** 作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（ 　）存储方式最节省运算时间。A、 单链表　 B、双链表　C、带头结点的双循环链表　D、容量足够大的顺序表 二、判断题（每小题1分，共10分）1．双链表中至多只有一个结点的后继指针为空。（）2．在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=rear。（ ）3．对链表进行插入和删除 *** 作时，不必移动结点。（ ）4．栈可以作为实现程序设计语言过程调用时的一种数据结构。（）5．在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧<a,b>。( )i6．对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。()7．“顺序查找法”是指在顺序表上进行查找的方法。（）8．向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（）9．键值序列{A，C，D，E，F，E，F}是一个堆。10．二路归并时，被归并的两个子序列中的关键字个数一定要相等。（） 三、填空题（每小题2分，共20分）1．在带有头结点的单链表L中，若要删除第一个结点，则需执行下列三条语句：＿＿＿＿＿＿＿＿；L->next=U->next；free(U)；2．有一个长度为20的有序表采用二分查找方法进行查找，共有＿＿＿＿＿＿个元素的查找长度为3。3．采用冒泡排序对有n个记录的表A按键值递增排序，若L的初始状态是按键值递增，则排序过程中记录的比较次数为＿＿＿＿＿。若A的初始状态为递减排列，则记录的交换次数为＿＿＿＿＿＿＿。4．在无头结点的双链表中，指针P所指结点是第一个结点的条件是＿＿＿＿＿＿。5．G为无向图，如果从G的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是＿＿＿＿＿图。6．如果一个有向图中没有＿＿＿＿＿＿，则该图的全部顶点可能排成一个拓扑序列。7．深度为8（根的层次号为1）的满二叉树有＿＿＿＿＿＿个叶子结点。 8．将一棵有100个结点的完全二叉树按层编号，则编号为49的结点X，其双亲PARENT（X）的编号为＿＿＿＿＿＿＿。9．设某闭散列表HT未满，散列函数H（KEY）为键值第一字母在字母表中的序号，处理冲突方法为线性探测法，请在下列算法划线处填上适当内容，以实现按键值第一字母的顺序输出闭散列表中所有键值的算法。void printword(keytype HT[m]) { for(i=1i<=26i++) { j=i while(____________________) { if (____________________) printf(“datatype”,HT[j]) j=(j+1)% m } } }10．设有一个链队，结点结构为data|next，front为队头指针，rear为队尾指针，当执行入队 *** 作时需执行下列语句：malloc(p)；p->data=xp->next=NULL；＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿；＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿； 四、简答题：（每小题4分，共20分）1. 对于一个有10000个结点的二叉树，树叶最多有多少个？最少有多少个？2. 已知一棵二叉树的中序序列和后序序列分别为： DBGEACHF和DGEBHFCA，则该二叉树的前序序列是什么？3. 设有1000个无序的元素，需排出前10个最大（小）的元素，你认为采用哪种排序方法最快？为什么？4. 在KMP算法中，已知模式串为ADABCADADA ，请写出模式串的next[j]函数值。5. 中序遍历的递归算法平均空间复杂度为多少？ 五、 算法设计题（每小题10分，共20分）1. 试编写一个算法，判断一给定的整型数组a[n]是不是一个堆。2. 一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积。试写一高效算法，求二叉树的繁茂度。参考答案一、选择题1、D 2、C 3、D 4、C 5、D 6、D 7、A 8、B 9、D 10、C 11、D 12、C 13、B14、C15、D二、判断题 1. √ 2. × 3. √ 4. √ 5. × 6. × 7. × 8. √ 9. √ 10. × 三、填空题1．U=L - >next2．4。　3．n-1、n(n-1)/2。4．p - >prior = NULL。5．连通6．回路或环7．28-1 = 27 = 1288．249．HT[j]!=NULL或HT[j]不为空、H(HT[j])=I10．rear - >next = p、rear = p四、简答题：1. 答： 最多是完全二叉树的形态，即5000个叶子；最少是单支树的形态，即1个叶子。2.答：是：ABDEGCFH3. 答：用锦标赛排序或堆排序很合适，因为不必等全部元素排完就能得到所需结果，时间效率为O(nlog2n)； 即O（1000log21000）=O(10000) 锦标赛排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9×10=1089堆排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9×10=1089若用冒泡排序也较快，最多耗费比较次数为（n-1+n-2+……＋n-10）=10n-55=10000-55=9945（次）4. 答： 01121123435. 答： 要考虑递归时占用了栈空间，但递归次数最多不超过树的高度，所以空间复杂度为O(log2n) 五、 算法设计题1.解：提示：堆的定义是：ki<k2i和K2i＋1 void SortA(sqlist &A, int n) { if(n==0) return(0) //空表if (a[1]<a[2]) { for( i=1i<=n/2i++) if (a[i]>a[2*i]|| a[i]>a[2*i+1])return(-1)return(minleap)}else { for( i=1i<=n/2i++) if (a[i]<a[2*i]|| a[i]<a[2*i+1])return(-1)return(“maxleap”)}}2. 要用层次遍历以及队列来处理，可以增设一个宽度计数器，在统计完每一层的结点个数之后,再从计数器中挑出最大值。typedef struct { BTNode node int layer//layer是结点所在层数 } BTNRecord, r int Width(Bitree T ){ //求树宽 int count[ ] //增开count向量，存放各层对应的结点数 InitQueue(Q) //队列初始化，Q的元素为BTNRecord类型 EnQueue(Q,{T, 0}) //根结点入队, 0 表示count[0]，下标值 while(!QueueEmpty(Q)) { DeQueue(Q, r) //结点出队 count[r.layer]++ //出队时再把结点对应层的计数器加if(r.node->lchild) EnQueue(Q,{r.node->lchild, r.layer+1})if(r.node->rchild) EnQueue(Q,{r.node->rchild, r.layer+1}) } //按层序入队时要随时标注结点所在层号 h=r.layer //最后一个队列元素所在层就是树的高度 for(maxn=count[0], i=1h i++) if(count[i]>maxn) maxn=count[i]//求出哪一层结点数最多 return (h*maxn)} // Width

苦逼的吉大孩子,你几班的啊，

#include<iostream>

#include<stdlib.h>

#include<time.h>

#include<fstream>

//#include<math>

using namespace std

void search(int,int,int *,int *)

template<class T>

int Find_s(T data[], int n,T key,int &icmp)

//顺序查找(从n维数组中查找key,并且给出比较的次数icmp

{

icmp=0

for(int i=0i<ni++)

{

   icmp++

   if(data[i]==key)

    return i

}

   return -1

} ///以下是二叉查找树查找法

template<class T>

class BintreeNode

{

public:

T data

BintreeNode* left

BintreeNode*right

BintreeNode():left(0),right(NULL){}

BintreeNode(T item):data(item),left(NULL),right(NULL){}

~BintreeNode(){

   if(left!=0)

    delete left

   if(right!=0)

    delete right

}

}

template<class T>

class Bintree

{

public:

int num

BintreeNode<T>* root

BintreeNode<T>* Find_bt(T key,int &icmp,int itype=0)//一个二叉树查找算法

{

   icmp=0

   if(root==0)

   {

    icmp++

    if(itype==0)//itype=1时有插入功能（不同的值时）

     return NULL

    else

    {

     num++

     return root=new BintreeNode<T>(key)

    }

   }

   else

   {

    BintreeNode<T>* ptr=root,*p

    while(ptr!=NULL)

    {

     icmp++

     p=ptr

     if(ptr->data==key)

      return ptr

     else

     {

      if(ptr->data>key)

       ptr=ptr->left

      else

       ptr=ptr->right

     }

    }

    if(itype)

    {

     num++

     if(p->data>key)

      return p->left=new BintreeNode<T>(key)

     else

      return p->right=new (BintreeNode<T>)(key)

    }

    return NULL

   }//else

}//Find_bt

Bintree():root(0),num(0){}

~Bintree(){delete root}

}

/*int compare(const void* a,const void* b)

{

return *(int *)a-*(int *)b

}*/

template<class T>

class Link

{

public:

T data

Link<T>* next

Link<T>():next(0){}

Link<T>(T item):data(item),next(0){}

~Link<T>(){if(next) delete next}

}

template<class T>

class LinkList

{

public:

Link<T>* first LinkList<T>():first(0){}

~LinkList<T>(){if(first)delete first}

Link<T>* Find_hash(T key,int &icmp,int ntype=0)//查找与插入

{

   icmp=0

   if(first==0)

   {

    icmp++

    if(ntype)

     return first=new Link<T>(key)

    else

     return NULL

   }

   else

   {

    Link<T>*ptr=first,*p

    while(ptr!=NULL)

    {

     icmp++

     p=ptr

     if(ptr->data==key)

      return ptr

     ptr=ptr->next

    }

    if(ntype)

     return p->next=new Link<T>(key)

    return NULL

   }

}

}

template<class T>

class Hash

{

public:

LinkList<T>* hashlist

int size

Hash<T>(int n=113):size(n)

{

   hashlist=new LinkList<T>[n]

}

~Hash<T>(){delete []hashlist}

void init_hash(T data[],int n)//初始化哈希查找表（拉链法）

{

   int t

   for(int i=0i<ni++)

   {

    int pos=data[i]%size

    hashlist[pos].Find_hash(data[i],t,1)

   }

}

Link<T>* Find_hash(T key,int &icmp)    //查找关键词   除法杂凑函数

{

   int pos=key%size

   return hashlist[pos].Find_hash(key,icmp)

}

} int compare1(const void* a,const void* b)

{

 return *(int *)a-*(int *)b

}

int compare2(const void* a,const void* b)

{

 return *(int *)b-*(int *)a

}   //主函数

int main()

{ int p

int m

int n

while(true)

{

cout<<"请选择数据类型 :1.正序排列2.逆序排列3.随机排列"  <<endl

cin>>p

switch(p){

case 1 :  {

   FILE *fp

 char *filename="data.in"

 if((fp=fopen(filename,"w+"))==NULL)

 {

  printf("cannot open this flie\n")

  exit(0)

 }

 

 

srand(time(0))

cout<<"  请输入数据规模n "<<endl

cin>>n

 fprintf(fp,"\t\t%d\t",n)

  cout<<" 请输入查找比较的 *** 作次数 m "<<endl cin>>m

 fprintf(fp,"\t\t%d\t\n",m)

int *a=new int[n]

for(int i=0i<ni++)

{    a[i]=rand()%1000000001

 fprintf(fp,"\t\t%d\t\n",a[i])

}

qsort(a,n,sizeof(int),compare1)   //对数组进行升序排序

qsort(a,n,sizeof(int),compare2)   //对数组进行降序排序

//随机生成m个随机数，并存入data.in

int *b=new int[m]

for(int k=0k<mk++)

{

   b[k]=rand()%1000000001

 fprintf(fp,"\t\t%d\t\n",b[k])

}

 fclose(fp)//关闭文件

 search(m,n,a,b)

 }

break

case 2 :  {

 FILE *fp

 char *filename="data.in"

 if((fp=fopen(filename,"w+"))==NULL)

 {

  printf("cannot open this flie\n")

  exit(0)

 }

 

 

srand(time(0))

cout<<"  请输入数据规模n "<<endl

cin>>n

 fprintf(fp,"\t\t%d\t",n)

 

  cout<<" 请输入查找比较的 *** 作次数 m "<<endl cin>>m

 fprintf(fp,"\t\t%d\t\n",m)

int *a=new int[n]

for(int i=0i<ni++)

{

   a[i]=rand()%1000000001

 fprintf(fp,"\t\t%d\t\n",a[i])

}

qsort(a,n,sizeof(int),compare2)   //对数组进行降序排序

//随机生成m个随机数，并存入data.in

int *b=new int[m]

for(int k=0k<mk++)

{

   b[k]=rand()%1000000001

 fprintf(fp,"\t\t%d\t\n",b[k])

}

 fclose(fp)//关闭文件

 search(m,n,a,b)

 }

 break

case 3 :

 {

   FILE *fp

 char *filename="data.in"

 if((fp=fopen(filename,"w+"))==NULL)

 {

  printf("cannot open this flie\n")

  exit(0)

 }

 

 

srand(time(0))

//输入n,并存入data.in

//int n

cout<<"  请输入数据规模n "<<endl

cin>>n

 fprintf(fp,"\t\t%d\t",n)

//输入m,并存入data.in

 cout<<" 请输入查找比较的 *** 作次数 m "<<endl

//int m

cin>>m

 fprintf(fp,"\t\t%d\t\n",m)

//随机生成n个随机数，并存入data.in

int *a=new int[n]

for(int i=0i<ni++)

{

   a[i]=rand()%1000000001

 fprintf(fp,"\t\t%d\t\n",a[i])

}

//随机生成m个随机数，并存入data.in

int *b=new int[m]

for(int k=0k<mk++)

{

   b[k]=rand()%1000000001

 fprintf(fp,"\t\t%d\t\n",b[k])

}

 fclose(fp)//关闭文件

 search(m,n,a,b)

}

}  

}

return 0

} //search函数

void search(int m,int n,int *a,int *b){

  FILE *fp

 char *filename="data.out"

 if((fp=fopen(filename,"w+"))==NULL)

 {

  printf("cannot open this flie\n")

  exit(0)

 }

  

 

clock_t start1 = clock()

for(int h=0h<mh++)

{

 int key=b[h]

 int icmp  int j=Find_s(a,n,key,icmp)//使用顺序查找法查找key值的位置  if(j==-1)

 {

  cout<<"数据总数:"<<n<<"\t查找关健字key:"<<key<<

   "\t查找比较次数:icmp\n顺序查找法：\n是否找到:" <<"no"<<"   icmp:"<<icmp<<endl

   fprintf(fp,"\t\t%s\t\n","no")

 }

   else

 {

 

 cout<<"数据总数:"<<n<<"\t查找关健字key:"<<key<<

   "\t查找比较次数:icmp\n顺序查找法：\n是否找到:" <<"yes"<<"   icmp:"<<icmp<<endl

  fprintf(fp,"\t\t%s\t\n","yes")

 }

}

 clock_t end1 = clock()    clock_t start2 = clock()

 for(int f=0f<mf++)

{

 int key=b[f]

 int icmp

Bintree<int> btree

for(int i=0i<ni++)

   btree.Find_bt(a[i],icmp,1)//未排序之前插入到二叉查找树中 qsort(a,n,sizeof(int),compare1)//对数组进行升序排序   cout<<"二叉查找树："<<endl

int p = (btree.Find_bt(key,icmp)==NULL?-1:btree.Find_bt (key,icmp)->data ) if(p==-1)

{

 

  cout<<"数据总数:"<<n<<"\t查找关健字key:"<<key<<

   "\t查找比较次数:icmp\n二叉树查找法：\n是否找到:" <<"no"<<"   icmp:"<<icmp<<endl

   fprintf(fp,"\t\t%s\t\n","no")

 

}

else

{   cout<<"数据总数:"<<n<<"\t查找关健字key:"<<key<<

   "\t查找比较次数:icmp\n二叉树查找法：\n是否找到:" <<"no"<<"   icmp:"<<icmp<<endl

   fprintf(fp,"\t\t%s\t\n","no") }  }  clock_t end2 = clock()   clock_t start3 = clock()  for(int g=0g<mg++)

{

 int key=b[g]

 int icmp

Hash<int > hash(1000)

hash.init_hash(a,n) cout<<"哈希表查找："<<endl

int q = ((hash.Find_hash(key,icmp)==NULL)?-1:(hash.Find_hash (key,icmp))->data) if(q==-1){

cout<<"数据总数:"<<n<<"\t查找关健字key:"<<key<<

   "\t查找比较次数:icmp\n哈希查找法：\n是否找到:" <<"no"<<"   icmp:"<<icmp<<endl

  fprintf(fp,"\t\t%s\t\n","no")

}

else{  cout<<"数据总数:"<<n<<"\t查找关健字key:"<<key<<

   "\t查找比较次数:icmp\n二叉树查找法：\n是否找到:" <<"yes"<<"   icmp:"<<icmp<<endl

  fprintf(fp,"\t\t%s\t\n","yes")

}  }  clock_t end3 = clock()

cout<<"顺序查找时间    :"<<(double)(end1-start1)/CLOCKS_PER_SEC<<endl<<endl//输出时间

cout<<"二叉树查找时间    :"<<(double)(end2-start2)/CLOCKS_PER_SEC<<endl<<endl//输出时间

cout<<"哈希查找时间    :"<<(double)(end3-start3)/CLOCKS_PER_SEC<<endl<<endl//输出时间

fclose(fp)//关闭文件

}    

不过 运行结果 不能排序 只能是随机的，你看看能改好吗？改好了 说给我  我11级12班的

---