数据结构实验4
本文最后更新于 377 天前,其中的信息可能已经有所发展或是发生改变。

编程实现折半查找的非递归算法
/*
 * @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;
}

评论

  1. 1年前
    2023-6-13 13:15:05

    haha

  2. 1年前
    2023-6-13 13:15:04

    haha

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇