博客作业05--查找

时间:2022-02-05 21:56:13

1.学习总结(2)

1.1查找的思维导图

 博客作业05--查找

1.2 查找学习体会

查找又称检索,是指在某种数据结构中找出满足给定条件的元素。查找是一种十分有用的操作,在数据结构中占有不容忽视的地位。且应用范围十分广泛,可以解决种类不同的许多问题。

2.PTA实验作业(4分)

 

2.1 题目1:6-2 是否二叉搜索树

2.3 代码截图

 博客作业05--查找

2.4 PTA提交列表说明。

 博客作业05--查找

一开始因为自己的疏忽导致基础的编译错误,理解问题以后仔细检查之后修改正确。

2.1 题目2:6-3 二叉搜索树中的最近公共祖先

2.2 设计思路(伪代码或流程图)

if(T是空树) 返回error

if(查找不到u,v)返回error

if(u,v有一个是根节点)返回根节点的关键字

if(u,v一个在左子树,一个在右子树)返回根节点的关键字

if(都在右子树)继续调用,节点变成右节点

if(都在左子树)继续调用,节点变成左节点

2.3 代码截图

 博客作业05--查找

2.4 PTA提交列表说明。

 博客作业05--查找

一开始因为自己的疏忽 没有事先在Dev上很好的运行,导致基础的编译错误,理解问题以后仔细检查之后发现是非常不应该的错误,改正以后得以解决。

2.1 题目3:7-1 QQ帐户的申请与登陆

2.3 代码截图

 博客作业05--查找

2.4 PTA提交列表说明。

 博客作业05--查找

此题并不是非常了解,询问同学之后得知运用c++方面的知识可以解决,于是经过询问同学和参考网络完成

3.截图本周题目集的PTA最后排名(3分)

3.1 PTA排名

 博客作业05--查找

3.2 我的总分:115

4. 阅读代码(必做,1分)

 哈希表及其运算的实现

#include <stdio.h>

#define MaxSize 100 //定义最大哈希表长度

#define NULLKEY -1 //定义空关键字值

#define DELKEY -2 //定义被删关键字值

typedef int KeyType; //关键字类型

typedef char * InfoType; //其他数据类型

typedef struct { KeyType key; //关键字域

InfoType data; //其他数据域

int count; //探查次数域

} HashData;

typedef HashData HashTable[MaxSize]; //哈希表类型

void InsertHT(HashTable ha,int &n,KeyType k,int p) //将关键字k插入到哈希表中

{

int i,adr;

adr=k % p;

if (ha[adr].key==NULLKEY || ha[adr].key==DELKEY) //x[j]可以直接放在哈希表中

{

ha[adr].key=k;

ha[adr].count=1;

}

else //发生冲突时采用线性探查法解决冲突

{

i=1; //i记录x[j]发生冲突的次数

do

{

adr=(adr+1) % p; //此处处理冲突,但有不妥之处。应该%m,但m在这一个系列的解答中,并未作为参数传递进来。见程序后面的讨论

i++;

}

while (ha[adr].key!=NULLKEY && ha[adr].key!=DELKEY);

ha[adr].key=k;

ha[adr].count=i; } n++;

}

void CreateHT(HashTable ha,KeyType x[],int n,int m,int p) //创建哈希表

{

int i,n1=0; for (i=0; i<m; i++) //哈希表置初值

{

ha[i].key=NULLKEY;

ha[i].count=0;

}

for (i=0; i<n; i++)

InsertHT(ha,n1,x[i],p);

}

int SearchHT(HashTable ha,int p,KeyType k) //在哈希表中查找关键字k

{

int i=0,adr;

adr=k % p;

while (ha[adr].key!=NULLKEY && ha[adr].key!=k)

{

i++; //采用线性探查法找下一个地址

adr=(adr+1) % p;

}

if (ha[adr].key==k) //查找成功

return adr;

else //查找失败

return -1; }

int DeleteHT(HashTable ha,int p,int k,int &n) //删除哈希表中关键字k

{

int adr;

adr=SearchHT(ha,p,k);

if (adr!=-1) //在哈希表中找到该关键字

{

ha[adr].key=DELKEY; n--; //哈希表长度减1

return 1;

}

else //在哈希表中未找到该关键字

return 0;

}

void DispHT(HashTable ha,int n,int m) //输出哈希表

{

float avg=0;

int i;

printf(" 哈希表地址:\t");

for (i=0; i<m; i++)

printf(" %3d",i);

printf(" \n");

printf(" 哈希表关键字:\t");

for (i=0; i<m; i++)

if (ha[i].key==NULLKEY || ha[i].key==DELKEY)

printf(" "); //输出3个空格

else

printf(" %3d",ha[i].key);

printf(" \n");

printf(" 搜索次数:\t");

for (i=0; i<m; i++)

if (ha[i].key==NULLKEY || ha[i].key==DELKEY)

printf(" "); //输出3个空格

else

printf(" %3d",ha[i].count);

printf(" \n");

for (i=0; i<m; i++)

if (ha[i].key!=NULLKEY && ha[i].key!=DELKEY)

avg=avg+ha[i].count;

avg=avg/n;

printf(" 平均搜索长度ASL(%d)=%g\n",n,avg); }

int main()

{ int x[]= {16,74,60,43,54,90,46,31,29,88,77};

int n=11,m=13,p=13,i,k=29;

HashTable ha;

CreateHT(ha,x,n,m,p);

printf("\n");

DispHT(ha,n,m);

i=SearchHT(ha,p,k);

if (i!=-1) printf(" ha[%d].key=%d\n",i,k);

else printf(" 未找到%d\n",k);

k=77;

printf(" 删除关键字%d\n",k);

DeleteHT(ha,p,k,n);

DispHT(ha,n,m);

i=SearchHT(ha,p,k);

if (i!=-1)

printf(" ha[%d].key=%d\n",i,k);

else

 printf(" 未找到%d\n",k);

printf(" 插入关键字%d\n",k);

InsertHT(ha,n,k,p);

DispHT(ha,n,m);

printf("\n");

 

 

return 0;

 

}