数据结构【查找篇】

数据结构【查找篇】

---

---

前言

为什么突然想学算法了？

> 用较为“官方”的语言讲，是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中，要想完成任何实质性的工作，理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。
> 但从实际而言，是因为当下竞争压力逐渐增大，无论走哪一条路，都不免需要一些相对丰富的算法知识，是故，便产生了一个寒假巩固速成算法的计划，可能对于像我这种算法竞赛小白而言，几乎很难，但我仍然还是想尝试一下，毕竟，梦想还是要有的，万一实现了呢？～(￣▽￣～)~

---

为什么选择码蹄集作为刷题软件？

码蹄集，是在全国高等学校计算机教学与产业实践资源建设专家委员会(TIPCC) 指导下建设的，其依托全国各大名校计算机系和清华大学出版社等单位的强大资源，旨在为计算机学习爱好者提供全面和权威的计算机习题。
.

---

目录

一、顺序查找

#include<iostream>

using namespace std;
#define Maxsize 100

typedef struct{         //查找表的数据结构（顺序表）
    int *elem;          //动态数组基址
    int Tablelen;       //表的长度
    int MaxSize;        //表的最大长度
}SSTable;

//顺序查找
int Search_Seq(SSTable ST,int key){
    int i;
    for(i=0;i<ST.Tablelen && ST.elem[i]!=key;++i);
    //查找功能，则返回元素下标；查找失败，则返回-1
    return i==ST.Tablelen? -1:i;
}

//顺序查找(哨兵)
int Search_SeqShaoBing(SSTable ST,int key){
    ST.elem[0]=key;                     //哨兵
    int i;
    for(i=ST.Tablelen;ST.elem[i]!=key;--i);//从后往前找
    return i;       //查找成功，则返回元素下标；查找失败，则返回0
}


//初始化顺序表
//基本操作——初始化一个程序表(动态分配)
void InitSSTable(SSTable &ST){
    //用malloc函数申请一片连续的存储空间
    ST.elem =(int*)malloc(Maxsize * sizeof(int));
    ST.Tablelen=0;
    ST.MaxSize=Maxsize;
}

//增加动态数组的长度
void IncreaseSize(SSTable &ST,int len){
    int *p=ST.elem;
    ST.elem=new int(Maxsize+len);
    for(int i=0;i<ST.Tablelen;i++){
        ST.elem[i]=p[i];      //将数据复制到新区域
    }
    ST.MaxSize=ST.MaxSize+len; //顺序表最大长度增加len
    delete p;
}

//在顺序表位置i处插入元素e
bool InsertSSTable(SSTable &ST,int i,int e){
    if(i<1 || i>ST.Tablelen+1) return false;
    if(ST.Tablelen >= ST.MaxSize) return false;
    for(int j=ST.Tablelen;j>i;j--){
        ST.elem[j]=ST.elem[j-1];
    }
    ST.elem[i-1]=e;
    ST.Tablelen++;
    return true;
}


//销毁顺序表
void DeleteSSTable(SSTable &ST){
    free(ST.elem);
    ST.elem = NULL;
    ST.Tablelen = ST.MaxSize = 0;
}

//输出顺序表
void PrintfSSTable(SSTable ST){
    for(int i=0;i<ST.Tablelen;i++)
        cout<<ST.elem[i]<<" ";
    cout<<endl;
}

int main(){
   SSTable ST;
   InitSSTable(ST);

    for(int i=1;i<=10;i++){
        InsertSSTable(ST,i,i);
    }

    PrintfSSTable(ST);

    int i=Search_Seq(ST,5);
    cout<<i<<endl;

    //销毁动态顺序表
    DeleteSSTable(ST);
    cout<<endl;


    return 0;
}

---

二、折半查找

#include<iostream>

using namespace std;
#define Maxsize 100

typedef struct{         //查找表的数据结构（顺序表）
    int *elem;          //动态数组基址
    int Tablelen;       //表的长度
    int MaxSize;        //表的最大长度
}SSTable;

//折半查找
int Binary_Search(SSTable ST,int key){
    int low=0,high=ST.Tablelen-1,mid;
    while(low<=high){
        mid=(low+high)/2;              //向下取整,取中间位置
        if(ST.elem[mid]==key)
            return mid;              //查找成功则返回所在位置
        else if(ST.elem[mid]>key)
            high = mid-1;            //从前半部分继续查找
        else
            low = mid+1;             //从后半部分继续查找
    }
    return -1;                       //查找失败，返回-1
}

//初始化顺序表
//基本操作——初始化一个程序表(动态分配)
void InitSSTable(SSTable &ST){
    //用malloc函数申请一片连续的存储空间
    ST.elem =(int*)malloc(Maxsize * sizeof(int));
    ST.Tablelen=0;
    ST.MaxSize=Maxsize;
}

//增加动态数组的长度
void IncreaseSize(SSTable &ST,int len){
    int *p=ST.elem;
    ST.elem=new int(Maxsize+len);
    for(int i=0;i<ST.Tablelen;i++){
        ST.elem[i]=p[i];      //将数据复制到新区域
    }
    ST.MaxSize=ST.MaxSize+len; //顺序表最大长度增加len
    delete p;
}

//在顺序表位置i处插入元素e
bool InsertSSTable(SSTable &ST,int i,int e){
    if(i<1 || i>ST.Tablelen+1) return false;
    if(ST.Tablelen >= ST.MaxSize) return false;
    for(int j=ST.Tablelen;j>i;j--){
        ST.elem[j]=ST.elem[j-1];
    }
    ST.elem[i-1]=e;
    ST.Tablelen++;
    return true;
}


//销毁顺序表
void DeleteSSTable(SSTable &ST){
    free(ST.elem);
    ST.elem = NULL;
    ST.Tablelen = ST.MaxSize = 0;
}

//输出顺序表
void PrintfSSTable(SSTable ST){
    for(int i=0;i<ST.Tablelen;i++)
        cout<<ST.elem[i]<<" ";
    cout<<endl;
}

int main(){
    SSTable ST;
    InitSSTable(ST);

    for(int i=1;i<=10;i++){
        InsertSSTable(ST,i,i);
    }

    PrintfSSTable(ST);

    int i=Binary_Search(ST,5);
    cout<<i<<endl;

    //销毁动态顺序表
    DeleteSSTable(ST);
    cout<<endl;


    return 0;
}

---

三、 二叉排序树的查找

//在二叉排序树中查找值为key的结点
BSTNode *BST_Search(BSTree T,int key){
    while(T!=NULL && key!=T->key){          //若树空或等于根结点值，则结束循环
        if(key<T->key) T=T->lchild;         //小于，则在左子树上查找
        else T=T->rchild;                   //大于，则在右子树上查找
    }
    return T;
} //最坏空间复杂度O(1)

//在二叉排序树中查找值为Key的结点（递归实现）
BSTNode *BSTSearch(BSTree T, int key){
    if(T==NULL)
        return NULL;                        //查找失效
    if(key==T->key)
        return T;                           //查找成功
    else if(key < T->key)
        return BSTSearch(T->lchild,key);    //在左子树中找
    else 
        return BSTSearch(T->rchild,key);    //在右子树中找
} //最坏空间复杂度O(h)

//在二叉排序树插入关键字为k的新结点(递归实现)
int BST_Insert(BSTree &T,int k){
    if(T==NULL){
        T = (BSTree)malloc(sizeof(BSTNode));
        T->key=k;
        T->lchild=T->rchild=NULL;
        return 1;                           //返回1，插入成功
    }
    else if(k==T->key)                      //树中存在相同关键字的结点，插入失败
        return 0;
    else if(k<T->key)                       //插入到T的左子树
        return BST_Insert(T->lchild,k);
    else                                    //插入到T的右子树
        return BST_Insert(T->rchild,k);
}

//按照str[]中的关键字序列建立二叉排序树
void Creat_BST(BSTree &T,int str[],int n){
    T=NULL;                                 //初始时T为空树
    int i=0;
    while(i<n){                             //依次将每个关键字插入到二叉排序树中
        BST_Insert(T,str[i]);
        i++;
    }
}

---

四、红黑树

struct RBNode{          //红黑树的定义
    int key;            //关键字的值
    RBNode* parent;     //父节点指针
    RBNode* lChild;     //左孩子指针
    RBNode* rChild;     //右孩子指针
    int color;          //结点颜色，如：可用0/1表示黑/红，也可以使用枚举型enum表示颜色
};

---

结语

感谢大家一直以来的不断支持与鼓励，码题集题库中的进阶塔350题正在逐步更新，之后会逐步跟进星耀，王者的题，尽请期待！！！
同时，也希望这些题能帮助到大家，一起进步，祝愿每一个算法道路上的“苦行僧”们，都能够历经磨难，终成正果，既然选择了这条路，走到了这里，中途放弃，岂不是太过可惜？

另附中国计算机学会的杰出会员、常务理事轩哥博士的B站视频讲解链接https://space.bilibili.com/518554541/?spm_id_from=333.999.0.0，供大家更好的进行学习与刷题～(￣▽￣～)~

愿你的结局，配得上你一路的颠沛流离。