本文最后更新于 707 天前，其中的信息可能已经有所发展或是发生改变。
编程实现折半查找的非递归算法
/*
* @Author: Vastsea(lyx8851@qq.com)
* @Date: 2023-05-06 19:32:10
* @LastEditors: Vastsea(lyx8851@qq.com)
* @LastEditTime: 2023-05-15 18:30:44
* @FilePath: \Development\Cpp\3_SecondSemesterCollege\Experiment\Experiment_4\1_折半查找_非递归实现.cpp
* @Description: 编程实现折半查找的非递归算法
* Link:https://59888888.xyz/
* Phone:18893558104
*/
#include <iostream>
using namespace std;
/**
* @description: 折半查找_非递归
* @param {int} r 待查找序列
* @param {int} n 待查找序列长度
* @param {int} k 待查找元素
* @return {*} 非0:待查找元素在序列中的下标 返回0:未找到
*/
int HalfSearch_NoRecursion(int r[], int n, int k)
{
int low = 0, high = n, mid;
while (low <= high)
{
mid = (low + high) >> 1;
if (k < r[mid])
{
high = mid - 1;
}
else if (k > r[mid])
{
low = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
int main()
{
int N, tmp;
cout << "输入数据个数:";
cin >> N;
int data[N];
cout << "依次输入数据:";
for (int i = 0; i < N; i++)
{
cin >> data[i];
}
cout << "输入要查询的值(输入0结束):" << endl;
cin >> tmp;
while (tmp)
{
if ((tmp = HalfSearch_NoRecursion(data, N, tmp)) != -1)
{
cout << "在" << tmp << "号位找到输入的元素。" << endl;
}
else
{
cout << "未找到" << endl;
}
cout << "输入要查询的值(输入0结束):" << endl;
cin >> tmp;
}
return 0;
}* @Description: 编程实现一棵二叉排序树包括
* 插入
* 删除
* 查找等功能
/*
* @Author: Vastsea(lyx8851@qq.com)
* @Date: 2023-05-06 19:32:30
* @LastEditors: Vastsea(lyx8851@qq.com)
* @LastEditTime: 2023-05-22 21:29:36
* @FilePath: \Development\Cpp\3_SecondSemesterCollege\Experiment\Experiment_4\2_二叉排序树.cpp
* @Description: 编程实现一棵二叉排序树包括
* 插入
* 删除
* 查找等功能
* Link:https://59888888.xyz/
* Phone:18893558104
*/
#include <iostream>
#include <queue>
using namespace std;
typedef int ElemType;
typedef int DataType;
struct node
{
ElemType key = 0;
DataType data = 0;
struct node *lchild = NULL;
struct node *rchild = NULL;
};
typedef node *BsTree;
BsTree Search(BsTree &root, ElemType key) // 搜索
{
if (root == NULL)
{
return NULL;
}
else if (key == root->key)
{
return root;
}
else if (key < root->key)
{
return Search(root->lchild, key);
}
else
{
return Search(root->rchild, key);
}
return NULL;
}
void Insert(BsTree &root, ElemType &key) // 插入
{
if (Search(root, key))
{
cout<<"树内已有该KEY节点"<<endl;
return;
}
if (root == NULL)
{
node *P = new node;
P->key = key;
root = P;
}
else if (key < root->key)
{
Insert(root->lchild, key);
}
else
{
Insert(root->rchild, key);
}
}
bool DeleteNode(BsTree &p) // 删除
{
BsTree tmp;
if (p->lchild == NULL && p->rchild == NULL)
{
delete (p);
p = NULL;
}
else if (p->lchild == NULL)
{
tmp = p;
p = p->rchild;
delete (tmp);
}
else if (p->rchild == NULL)
{
tmp = p;
p = p->lchild;
delete (tmp);
}
else
{
BsTree successors;
tmp = p;
successors = p->lchild; // 找p的左子树的最右端（中序直接前继）
while (successors->rchild) // 有左子树的最右端
{
tmp = successors;
successors = successors->rchild;
}
p->key = successors->key;//数据域对调，应该结构体对调的
if (tmp != p)
{
tmp->rchild = successors->lchild;//
}
else
{//无左子树，接到左边
tmp->lchild = successors->lchild;
}
delete (successors);
}
return 0;
}
bool Delete(BsTree &root, ElemType key) // 删除寻址
{
if (root == NULL)
{
return false;
}
else
{
if (key == root->key)
{
return DeleteNode(root);
}
else if (key < root->key)
{
return Delete(root->lchild, key);
}
else
{
return Delete(root->rchild, key);
}
}
}
void Structure(BsTree &root, ElemType source[], int numberOfSources) // 根据数组构造
{
node *s;
for (int i = 0; i < numberOfSources; i++)
{
Insert(root, source[i]);
}
}
void Print(BsTree T, int level = 0, int lr = 0) // 打印二叉树
{
if (!T)
{
return;
}
Print(T->rchild, level + 1, 2);
for (int i = 0; i < level; i++)
{
cout << " ";
}
switch (lr)
{
case 1:
{
cout << "\\-";
break;
}
case 2:
{
cout << "/-";
break;
}
default:
break;
}
cout << T->key << endl;
Print(T->lchild, level + 1, 1); // 打印左子树，并将层次加1
}
int main()
{
// 根据数组构建
cout << "根据已有数组{39, 11, 68, 46, 75, 23, 71, 8, 86, 34}构建排序二叉树" << endl;
BsTree T1 = NULL;
int da[10] = {39, 11, 68, 46, 75, 23, 71, 8, 86, 34};
Structure(T1, da, 10);
system("pause");
system("cls");
Print(T1);
system("pause");
system("cls");
BsTree T2 = NULL;
BsTree P;
// 插入
int tmp;
while (1)
{
cout << "插入元素请直接输入,删除元素在元素前加负号,查找元素输入0+空格+要查找的元素" << endl;
cin >> tmp;
system("cls");
if (tmp > 0)
{
Insert(T2, tmp);
cout << "已插入" << endl;
Print(T2);
}
else if (tmp < 0)
{
Delete(T2, -tmp);
cout << "已删除" << endl;
Print(T2);
}
else
{
cin >> tmp;
if (Search(T2, tmp))
{
cout << "找到KEY为" << tmp << "的元素" << endl;
}
else
{
cout << "没有找到KEY为" << tmp << "的元素" << endl;
}
}
}
return 0;
}* @
* @Description:选择合适散列函数和冲突处理方法，编程实现QQ账户的申请与登录
* ！！！号码统一为6位，号码范围100000~999999，Hash后内存为0~287
* ！！！Hash(KEY)为key的1、2位，3、4位，5、6位相加后减10 eg:Hash(123456)=12+34+56-10=92
* ！！！静态查找，登录和注册分开
/*
* @Author: Vastsea(lyx8851@qq.com)
* @Date: 2023-05-06 19:33:07
* @LastEditors: Vastsea(lyx8851@qq.com)
* @LastEditTime: 2023-05-23 23:18:19
* @FilePath: \Development\Cpp\3_SecondSemesterCollege\Experiment\Experiment_4\3_散列表应用_QQ账户申请and登录.cpp
* @Description:选择合适散列函数和冲突处理方法，编程实现QQ账户的申请与登录
* ！！！号码统一为6位，号码范围100000~999999，Hash后内存为0~287
* ！！！Hash(KEY)为key的1、2位，3、4位，5、6位相加后减10 eg:Hash(123456)=12+34+56-10=92
* ！！！静态查找，登录和注册分开
* Link:https://59888888.xyz/
* Phone:18893558104
*/
#include <iostream>
#include <ctime>
using namespace std;
struct userNode
{
int key;
bool sex;
int birthday;
struct userNode *next = NULL;
};
userNode *HashTable[288];
int Hash(int key)
{
int res = 0;
while (key)
{
res += key % 100;
key /= 100;
}
return res - 10;
}
userNode *Login(int key)
{
int afterHash = Hash(key);
userNode *p = HashTable[afterHash];
while (p && p->key != key)
{
p = p->next;
}
if (p && (p->key == key))
{
return p;
}
else
{
return NULL;
}
return NULL;
}
int Register(userNode *newUser)
{
int afterHash = Hash(newUser->key);
// userNode *p = HashTable[afterHash];
// while (p)
// {
// p = p->next;
// }
newUser->next = HashTable[afterHash];
HashTable[afterHash] = newUser;
return 0;
}
int main()
{
userNode *nowTmp;
int tmp;
while (1)
{
system("cls");
cout << "请输入你的PP号:" << endl;
tmp=0;
while (tmp<100000 || tmp>999999)
{
cin >> tmp;
}
nowTmp = Login(tmp);
if (nowTmp)
{
system("cls");
cout << "-------------------------------------------" << endl
<< "| 登录成功！ |" << endl
<< "| PP号:" << nowTmp->key << " |" << endl
<< "| 性别:" << (nowTmp->sex ? "男" : "女") << " |" << endl
<< "| 生日:" << nowTmp->birthday << " |" << endl
<< "-------------------------------------------" << endl;
system("pause");
}
else
{ // 自动注册
srand(time(0));
nowTmp = new userNode;
nowTmp->key=tmp;
nowTmp->birthday= 2002 + rand() % 21;
nowTmp->birthday*=100;
nowTmp->birthday+= 1 + rand() % 12;
nowTmp->birthday*=100;
nowTmp->birthday+= 1 + rand() % 28;
nowTmp->sex= rand() % 2;
Register(nowTmp);
cout << "这个PP号还没注册！帮你注册了！请重新登录！" << endl;
system("pause");
}
}
//散列情况展示部分
// int a[288];
// for (int i = 0; i <= 287; i++)
// {
// a[i]=0;
// }
// for (int i = 100000; i <= 999999; i++)
// {
// a[Hash(i)]++;
// }
// for (int i = 0; i <= 287; i++)
// {
// cout<<"a["<<i<<"]="<<a[i]<<endl;
// }
return 0;
}
haha
haha