首页 > 其他分享 >数据结构（第七章）

数据结构（第七章）

时间：2023-07-11 20:22:05浏览次数：32  
标签：左子 结点 key int 关键字 查找 第七章 数据结构

数据结构（第七章）

基本概念

  1. 查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找。
  2. 查找表：用于查找的数据集合称为查找表
  3. 平均查找长度：在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值。

线性表查找

一、顺序查找

  • 顺序查找（Sequential Search）又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

算法实现：

int Sequential(int a[],int n,int key){
    for (int i = 1; i<=n ; i++) 
        if (a[i]==key)
            return i;
        else
            return 0;
}
  • ASL(成功)=(n+1)/2
  • ASL(失败)=n+1

二、折半查找

  • 折半查找（Binary Search）技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须来用顺序存储。
  • 折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等,则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。

算法实现：

int Binary(int a[], int key){
    int low=0 , high= sizeof(a)/sizeof(a[0])-1 , mid ; //
    while(low<=high){
        mid=(low+high)/2;
        if (a[mid]==key)
            return mid;
        else if(a[mid]<key)
            low=mid+1;
        else
            high=mid-1;
    }
    return -1;
}
  • 时间复杂度：O（logn）
  • ASL(成功)=log2(n+1)-1

三、分块查找

  • 分块查找又称索引顺序查找，这是一种性能介于顺序查找和折半查找之间的一种查找方法。
  • 基本思想：将查找表分为若干子块。块内的元素可以无序，但块之间是有序的.即第一个块中的最大关键字小于第二个块中的所有记录的关键字，第二个块中的最大关键字小于第三个块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键宝和各块中的第一个元素的地址，索引表按关键字有序排列。
  • 分块查找的过程分为两步：第一步是在素引表中确定待查记录所在的块，可以顺序查找或折半查找索引表：第二步是在块内顺序查找。

算法实现：

#define MaxSize 100
typedef struct {
    int key ; //假定表内元素为int型
    int low , high; //记录块中第一个和最后一个元素
}IndexElem;
IndexElem index[MaxSize]; //定义索引表
//在分块索引表中查找关键字为key的记录，n为块的最大数量，arr[]为原数组
int Block(IndexElem index[] , int key , int n , int arr[]){
    int i=0,j,k;
    while((i<n)&&index[i].key<key)
        i++;
    if (i>n){
        cout<<"not found"<<endl;
        return 0;
    }
    j=index[i].low;
    while(j<=index[i].high&&arr[j]!=key)
        j++;
    if (j>index[i].high)
        cout<<"not found"<<endl;
    return j;
}

树型查找

一、二叉排序树（BST）

  • 二叉排序树（BinarySort Tree），又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。
  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值。
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。它的左、右子树也分别为二叉排序树。
  • 从二叉排序树的定义也可以知道，它前提是二叉树，然后它采用了递归的定义方法，再者，它的结点间满足一定的次序关系，左子树结点一定比其双亲结点小，右子树结点一定比其双亲结点大。

定义二叉树结构

//二叉树的二叉链表的结点结构定义
typedef struct BiTNode{
    int data; //结点数据
    struct BiTNode *lchild , *rchild; //左右孩子指针
}BiTNode , *BiTree;

二叉排序树的查找（递归）

//二叉排序树的查找
int SearchBST(BiTNode *T,int key){
    if (T==NULL){ //空树，则创建一个只含有根结点的二叉树
       return 1;
    }
    else{
        if (T->data==key)
            return 0;
        else if(T->data<key)
            SearchBST(T->lchild,key);
        else if(T->data>key)
            SearchBST(T->rchild,key);
    }
}

二叉排序树的查找（非递归）

int SearchBST(BiTNode *T ,int key){
    while(T!=NULL&&key!=T->data){ //树空或等于根结点值，则循环结束
        if (key<T->data) //小于根结点值则在左子树中查找
            T=T->lchild;
        else
            T=T->rchild; //大于根结点则在右子树中查找
    }
    return T->data; //返回查找的数据
}

二叉排序树的插入

//二叉排序树的插入
int InsertBST(BiTNode *T , int key){
    if (T==NULL){ //如果二叉树为空，则创建一个二叉树
        T=new BiTNode ;
        T->data=key;
        T->lchild=T->rchild=NULL;
        return 1;
    }
    else{  //二叉树非空
        if (T->data==key) //二叉树中存在关键字相同的结点，则插入失败
            return 1; 
        else if(T->data<key) //根结点的值比插入值小，则将关键字向根结点的右子树中插入
            InsertBST(T->rchild,key);
        else
            InsertBST(T->lchild,key); //根结点的值比插入值大，则将关键字向根结点的左子树中插入
        
    }
}

二叉排序树的构造

//二叉树的构造
void CreateBST(BiTNode * T , int arr[] , int n){ //arr[]二叉树中的根结点数组，n表示数组中元素个数
       T==NULL; //初始化
    for (int i = 0; i < n; ++i) {
        InsertBST(T,arr[i]);
    }
}

二叉排序树的删除

删除的结点存在三种情况：

  1. 删除结点为叶子结点，直接删除不会对二叉排序树产生影响
  2. 删除结点仅有左或右子树，删除结点可以直接继承其根结点的位置
  3. 删除结点左右子树都存在，我们需要查找到该结点的前驱（或后继），将其放在删除结点的位置，其原本所含有的孩子结点则按照这三种情况，递归的进行更改

这里对于左右子树都存在的情况使用的是查找该结点的前驱（相对简单）

对删除结点进行的操作

//在二叉排序树中删除结点T ，并重接它的左右子树
int Delete(BiTNode *T){
    BiTNode *p,*s ; //定义两个结点
    if (T->rchild==NULL) //如果该结点的右子树为空，则只需要重接它的左子树就行(待删结点是叶子也走此分支)
    {
        p=T; //记录待删结点
        T=T->lchild; //重接左子树
        free(T);//释放该结点
    }
    else if (T->lchild==NULL)//如果该结点的左子树为空，则只需要重接它的右子树就行(待删结点是叶子也走此分支)
    {
        p=T;
        T=T->rchild; //重接右子树
        free(T);
    }
    else{ //左右子树均不为空
        p=T;
        s=T->lchild; //转左
        while(s->rchild){ //转左，向右走到尽头找到待删结点的前驱
            p=s; //p此时指向的为s的前驱结点，为了后续将s的孩子结点接到该处
            s=s->rchild;
        }
        T->data=s->data;//s指向被删除结点直接前驱（用被删结点的前驱替代被删结点的值）
        if (p!=T) 
            p->rchild=s->lchild;//重接p结点的右子树
        else
            p->lchild=s->lchild;//重接p结点的左子树
        free(s);
    }
    return 0;
}

二叉排序树删除

//二叉排序树的删除
int DeleteBST(BiTNode *T ,int key){
    if (T==NULL) //结点为空
        return 1;
    else{
        if (key==T->data)//查找到该结点，删除该结点
            Delete(T);
        else if(key<T->data) //如果关键字比根结点小，则在根结点左子树中递归遍历
            DeleteBST(T->lchild,key);
        else
            DeleteBST(T->rchild,key);
    }
}

二、平衡二叉树（AVL）

  • 平衡二叉树，是一种二叉排序树，其中每个结点的左右子树的高度差至多等于1
  • 将二叉树上结点的左子树高度减去右子树高度的值称为平衡因子BF，那么平衡二叉树上所有结点的平衡因子只可能是-1、1、0.只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。
  • 距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，我们称为最小不平衡子树。

当左右子树不平衡时，进行的旋转（巧记）

  • 左旋（LL平衡旋转）

  • 右旋（RR平衡旋转）

  • 先右后左旋（RL平衡旋转）

  • 先左后右旋（LR平衡旋转）

平衡二叉树的算法实现：

  • 定义的二叉树的二叉链表存储结构
//二叉树的二叉链表结点结构定义
typedef struct BiTNode {
    int data ; //数据域
    int bf; //结点的平衡因子
    struct BiTNode *lchild ,*rchild ; //左右孩子指针
}BiTNode , *BiTree;
  • 右旋操作

此时的最小不平衡子树，如图所示，可以看出进行的应该是右旋操作，但可以看到进行右旋操作变成根结点的结点p，存在着右孩子，根据二叉排序树的定义可知，右孩子的权值大于其父结点p，小于根结点T，所以要把p的右子树链接到根结点T的左子树位置。

代码展示：

//右旋操作
//对以T为根的二叉排序树作右旋处理
//处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点
void R_Rotate(BiTree &T){
    BiTNode *p;
    p=T->lchild; //p指向T的左子树的根结点
    T->lchild=p->rchild; //p的右孩子（右子树）链接到T的左孩子（左子树）位置
    p->rchild=T; //p的右子树变成T
    T=p; //T指向新的根结点，即回到根结点的位置
}
  • 左旋操作

此时的最小不平衡子树，如图所示，可以看出进行的应该是左旋操作，但可以看到进行左旋操作变成根结点的结点p，存在着左孩子，根据二叉排序树的定义可知，左孩子的权值小于其父结点p，大于根结点T，所以要把p的左子树链接到根结点T的右子树位置。

代码展示：

//左旋操作
//对以T为根的二叉排序树作左旋处理
//处理之后p指向新的树根结点，即旋转处理之前的右子树的根结点
void L_Rotate(BiTree &T){
    BiTNode *p;
    p=T->rchild; //p指向根结点T的右子树
    T->rchild=p->lchild; //将p的左子树链接到T的右子树上
    p->lchild=T;//p的左子树变成T
    T=p; //T指向新的根结点，即回到根结点的位置
}
  • 左平衡旋转（LR型）：先左旋再右旋

上述为LR型存在的三种情况：

  1. 第一种就是最普通的LR型不平衡二叉子树，根据二叉排序树的性质，C>B,为了进行旋转，我们需要把所在的这条链统一符号单位即转换成最基本的左（右）旋，所以先对BC进行左旋将B变成C的左子树，然后进行右旋
  2. 第二种LR型不平衡二叉树中的L型，即所进行LR旋转变成根结点的p存在左子树，根据二叉排序树的性质，P1的权值小于其父结点p，大于T1，因此链接到T1的右子树。
  3. 第三种LR型不平衡二叉树中的R型，即所进行LR旋转变成根结点的p存在右子树，根据二叉排序树的性质，P1的权值大于其父结点p，大于T，因此链接到T的左子树。

代码展示：

//LR型（左平衡旋转处理）
//定义三个宏常量，分别表示LR型旋转的三种情况
#define LH +1 //左高
#define EH 0 //等高
#define RH -1 //右高

//对以指针T所指结点为根的二叉树做左平衡旋转（LR）
//当结点传入的时候，说明以T为根结点的子树平衡因子大于1，已经是一个不平衡子树了。
void LeftBalance(BiTree &T){
    BiTNode *p ,*q;
    p=T->lchild; //p指向T的左子树结点
    switch (p->bf) { //检查T的左子树的平衡度，并作相应的平衡处理
        case LH:  //当p的平衡因子为1的时候，说明所在链同符号都为正，可以直接进行右单旋
            T->bf=p->bf=EH; //结点平衡因子赋值为0，平衡
            R_Rotate(T);//新结点插入在T的左孩子的左子树上，要作单右旋处理
            break;
        case RH:  //新结点插入在T的左孩子的右子树上，要做双旋处理
            q=p->rchild; //获取p的右子树的根结点
            switch (q->bf) {
                case LH:
                    T->bf=RH;
                    p->bf=EH;
                    break;
                case EH:
                    T->bf=p->bf=EH;
                    break;
                case RH:
                    T->bf=EH;
                    p->bf=LH;
                    break;
            }
            q->bf=EH;//上述平衡因子，变换完整后，将q达到平衡
            L_Rotate(T->lchild); //对T的左子树作左平衡处理
            R_Rotate(T); //对T进行右平衡处理
    }
}
  • 右平衡旋转（RL型）：先右旋转再左旋转

和上述做平衡旋转思想一致，这里只给出代码，原理参考上述。

代码展示：

//RL型（右平衡旋转处理）
//定义三个宏常量，分别表示RL型旋转的三种情况
#define LH +1 //左高
#define EH 0 //等高
#define RH -1 //右高
//右平衡旋转
void RightBalance(BiTree &T){
    BiTNode *p , *q;
    p=T->rchild; //p指向T的右子树的根结点
    switch (p->bf) {
        case RH: //当p的平衡因子为-1的时候进行，左单旋操作
            p->bf=T->bf=EH;
            L_Rotate(T);
            break;
        case LH:
            q=p->lchild;
            switch (q->bf) {
                case LH:
                   T->bf=EH;
                   p->bf=RH;
                    break;
                case EH:
                   p->bf=T->bf=EH;
                    break;
                case RH:
                    T->bf=LH;
                    p->bf=EH;
                    break;
            }
            q->bf=EH;
            R_Rotate(T->rchild);//对T的右子树作右旋平衡处理
            L_Rotate(T);//对T作左旋平衡处理
    }
}

下面就是主函数的代码展示：

//平衡二叉树的插入操作
bool InsertAVL(BiTree &T , int e , int *taller){
    if (!T){ //如果结点为空，则插入新结点，树长高 置taller为TRUE
        T=new BiTNode;
        T->data=e;
        T->lchild=T->rchild=NULL; //左右孩子为空
        T->bf=EH;
        *taller= true;
    }
    else{
        if (e==T->data){ //如果插入的关键字与AVL树中的相等，则插入失败
            *taller= false;
            return false;
        }
        if (e<T->data)//继续在左子树中寻找
        {
            if (!InsertAVL(T->lchild,e,taller)) //未插入
                return false;
            if (*taller){ //插入到左子树中，且左子树长高
                switch (T->bf) { //检查树的平衡度
                    case LH: //原本左子树比右子树高，需要作左平衡处理
                        LeftBalance(T);
                        *taller=false;
                        break;
                    case EH: //左右子树原先等高，现在因加入新关键字，长高
                        T->bf=LH;
                        *taller= true;
                        break;
                    case RH: //原本右子树比左子树高，现在等高
                        T->bf=EH;
                        *taller= false;
                        break;
                }
            }
        }
        else{ //继续在右子树中搜索
            if (!InsertAVL(T->rchild,e,taller))
                return false; //未插入
            if (*taller){
                switch (T->bf) { //检查T的平衡度
                    case LH: //原本右子树比左子树高，现在左右等高
                        T->bf=EH;
                        *taller=false;
                        break;
                    case EH: //原本左右子树等高，现在右子树比左子树高
                        T->bf=RH;
                        *taller= true;
                        break;
                    case RH: //原本右子树比左子树高，需要进行右平衡处理
                        RightBalance(T);
                        *taller= false;
                        break;
                }
            }
        }
    }
    return true;
}

B树和B+树

B树

  • 定义：B树（B-tree）是一种平衡的多路查找树。结点最大的孩子数目称为B树的阶（order）
  • 一个m阶的B树具有如下属性：
    1. 如果根结点不是叶结点，则其至少有两棵子树。
    2. 每一个非根的分支结点都有k-1个元素和k个孩子，其中[m/2]≤k≤m。每一个叶子结点n都有k-1个元素，其中[m/2]≤k≤m。
    3. 所有叶子结点都位于同一层次。
    4. 所有分支结点包含下列信息数据（n,AK，A,KA，….KA，)，其中：K,（i=1,2，…n)为关键字，且K<K(i=1,2,…,n-1)；A,(i=0,2，…，n)为指向子树根结点的指针，且指针A，所指子树中所有结点的关键字均小于K，(i=1,2，…，n)，A.所指子树中所有结点的关键字均大于K，，n（[m/2]-1≤n≤m-1）为关键字的个数（或n+1为子树的个数）。

B+树

  • 定义：B+树是应数据库所需而出现的一种B树的变形树。
  • 一棵m阶的B+树需满足下列条件：
    1）每个分支结点最多有m棵子树（孩子结点）。
    2）非叶根结点至少有两棵子树，其他每个分支结点至少有[m/2]棵子树。
    3）结点的子树个数与关键字个数相等。
    4）所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。
    5）所有分支结点（可视为索引的索引）中仅包含它的各个子结点（即下一级的索引块）中关键字的最大值及指向其子结点的指针。

B树和B+树的差异

1）在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；而在
B树中，具有n个关键字的结点含有n+1棵子树。
2）在B+树中，每个结点（非根内部结点）的关键字个数n的范围是「m/2]≤n≤m（根结点：
2≤n≤m)；在B树中，每个结点（非根内部结点）的关键字个数n的范围是[m/2]-1≤n≤
m-1(根结点：1≤n≤m-1)。
3）在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只
含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。

4）在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中；
而在B树中，叶结点（最外层内部结点）包含的关键字和其他结点包含的关键字是不重复的。

散列表

  • 散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr（这里的地址可以是数组下标、索引或内存地址等）。
  • 散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突，这些发生碰撞的不同关键字称为同义词。
  • 散列表：根据关键字而直接进行访问的数据结构。散列表建立了关键字和存储地址之间的一种直接映射关系。

散列函数的构造方法

一、直接地址法
  • 直接取关键字的某个线性函数值为散列地址，散列函数为：H（key）=key或 H（key）=a*key+b式中，a和b为常数。
  • 这种方法计算最简单，且不会产生冲突。
  • 适合关键字的分布基本连续的情况，若关键字分布不连续，空位比较多，则会造成存储空间的浪费。
二、除留余数法（最常用）
  • 这是一种最简单、最常用的方法，假定散列表表长为m，取一个不大于m但最接近或等于m的质数p，利用公式H（key）=key%p

把关键字转换成散列地址。

  • 这种方法的关键是选好p，使得每个关键字通过该函数转换后等概率地映射到散列空间上的任一地址，从而尽可能减少冲突的可能性。
三、数字分析法（了解）
  • 设关键字是r进制数（如十进制数)，而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时应选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。
四、平方取中法（了解）
  • 顾名思义，这种方法取关键字的平方值的中间几位作为散列地址。具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀,适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。

处理冲突的方法

一、开放地址法

  • 就是一旦发生冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。

  • 公式：Hi=(H(key)+di)%m,H(key)为散列函数，i=0，1，2，3，····，k（k<=m-1）,m表示散列表长，di为增量序列。

  • 取增量序列对应的四种方法：

      1.  **线性探测法（最常用）**：当d；=0，1,2，…，m-1时，称为线性探测法。这种方法的特点是：冲突发生时，顺序查看表中下一个单元（探测到表尾地址m一1时，下一个探测地址是表首地址0),直到找出一个空闲单元（当表未填满时一定能找到一个空闲单元）或查遍全表。
  2.  **平方探测法(了解)** ：当di=0^2，1^2，-^2，2^2、-2^2，…k^2，-k^2时，称为平方探测法，其中k≤m/2，散列表长度m必须是一个可以表示成4k+3的素数，又称二次探测法。
  3.  **双散列法（了解**）：当di=Hash2(key)时，称为双散列法。需要使用两个散列函数，当通过第一个散列函数H(key)得到的地址发生冲突时，则利用第二个散列函数Hash2(key)计算该关键字的地址增量。它的具体散列函数形式如下：***Hi=(H(key)+i*Hash2(key))%m***
      初始探测位置Ho=H(key）%m。i是冲突的次数，初始为0。在双散列法中，最多经过m-1次探测就会遍历表中所有位置，回到H位置。
  4.  **伪随机序列法（了解）**：当di=伪随机数序列时，称为伪随机序列法
二、拉链法（了解）
  • 对于不同的关键字可能会通过散列函数映射到同一地址，为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。假设散列地址为i的同义词链表的头指针存放在散列表的第i个单元中，因而查找、插入和删除操作主要在同义词链中进行。拉链法适用于经常进行插入和删除的情况。

散列表查找的算法实现

  • 定义一个散列表结构以及一些相关的常数。其中HashTable就是散列表结构，结构当中的elem为一个动态数组。
#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12 //定义散列表长为数组长度
#define NULLKEY -32768
typedef struct {
    int *elem; //数据元素存储基址，动态分配数组
    int count; //当前数据元素个数
}HashTable;
int m=0 ; //散列表长，定义为全局变量
  • 散列表的初始化
//散列表初始化
int InitHashTable(HashTable &H){
    m=HASHSIZE;
    H->count=m;
    H->elem=(int *) malloc(m*sizeof (int));
    for (int i = 0; i < m; ++i) {
        H->elem[i]=NULLKEY;
    }
    return 0;
}
  • 散列函数
//定义散列函数
int Hash(int key){
    return key%m; //除留余数法
}
  • 插入关键字进散列表
//插入关键字进散列表
void InsertHash(HashTable &H , int key){
    int addr= Hash(key);   //求散列地址
    while(H->elem[addr]!=NULLKEY){ //如果不为空，则冲突
        addr=(addr+1)%m;  //开放地址法的线性探测
    }
    H->elem[addr]=key; //直到有空位后插入关键字
}
  • 散列表查找关键字
//散列表查找关键字
int SearchHash(HashTable H , int key ,int *addr){
    *addr= Hash(key); //求散列地址
    while(H->elem[*addr]!=key) //如果不为空则冲突
    {
        *addr=(*addr+1)%m; //开放地址法的线性探测
        if (H->elem[*addr]==NULLKEY||*addr== Hash(key)) //如果循环回到原点，则说明关键字不存在
            return UNSUCCESS;
    }
    return SUCCESS;
}

标签：左子,结点,key,int,关键字,查找,第七章,数据结构
From： https://www.cnblogs.com/wfy-studying/p/17545802.html

相关文章

  • 浅谈BIT本科数据结构与算法课程 1
    关于C++基本输入输出流#include<bits/stdc++.h>usingnamespacestd;intmain(){ inta,b; cin>>a>>b; cout<<a<<endl; return0;}栈和队列关于stl#include<algorithm>vector<int>x;x.push_back(n);x.pop_back();x.back();x[1......
  • redis数据结构-String（SDS）
    redis数据结构（一）注：以下源码部分，来自redis-7.0.12，redis-3.0redis有一个核心的对象，叫做redisObject，用来标识所有的key和value，用结构体reidsObject来标识String、Hash、List、Set、Zset五种数据结构。源码位置在server.h。/*Objectsencoding.Somekindofobjects......
  • 数据结构链表的基本操作
    /*数据结构单向链表基本操作节点类*/importjava.util.Iterator;importjava.util.function.Consumer;publicclassshujujiegouimplementsIterable<Integer>{//整体privateNodehead;//头指针@OverridepublicIterator<Integer>iterator(){......
  • 数据结构问题
    编写一个时间复杂度为O(n),空间复杂度为O(1)是什么意思时间复杂度为O(n)表示算法的执行时间与输入规模n成正比，即算法的执行时间随着输入规模的增加而线性增长。空间复杂度为O(1)表示算法所需的额外空间是固定的，与输入规模n无关。这意味着算法使用的空间是常数级别的，不随输入规......
  • 【数据结构与算法】队列算法题
    TS实现队列interfaceIQueue<T>{//入队enqueue(item:T):void;//出队dequeue():T|undefined;//队首peek():T|undefined;//是否为空isEmpty():boolean;//大小size():number;}classArrayQueue<T>implementsIQueue<T>{......
  • 【数据结构与算法】栈相关算法题（长期更新）
    TS实现栈interfaceIStack<T>{push(e:T):void;pop():T|undefined;peek():T;isEmpyt():boolean;size():number;}//implements:实现接口,一个类可以实现多个接口classArrayStack<T>implementsIStack<T>{privatedata:T[]=[];//pri......
  • 图解算法数据结构
    算法复杂度1.算法复杂度旨在输入数据量N的情况下，算法的时间和空间使用情况，体现算法运行使用的时间和空间随数据大小N而增大的速度。 算法复杂度主要可以从时间，空间两个角度评价：时间：假设各操作的运行时间为固定常数，统计算法运行的计算操作的数量，以代表算法运行所需时间......
  • 第一节 线性数据结构 STL
    vector容器迭代器vector<int>v{1,0,0,8,6};for(vector<int>::interatorit=v.begin();it!=v.end();it++)cout<<*it<<"";函数push_back(x);//添加元素pop_back();//删除尾元素size();//查询vector长度insert(i......
  • 【技术积累】数据结构中栈与队列及其相关算法【一】
    什么是栈栈是一种特殊的数据结构，它的各个元素按照一定的次序排列，且只能在表的一端（称为栈顶）进行添加和删除数据，这种数据结构遵循后进先出（LIFO）的原则。栈可以简单地理解为一种容器，它在使用时非常方便，因为只需在顶部压入（push）或弹出（pop）元素即可。栈可以直接使用数组或链表等数据结构......
  • C++ Primer 学习笔记——第七章
    第七章类前言基本数据类型有时候并不能解决某些特定问题，而通过自定义的类就可以通过理解问题概念，使得程序更加容易编写、调试和修改。类的基本思想是数据抽象（dataabstraction）和封装（encapsulation）。数据抽象是一种依赖于接口（interface）和实现（implementation）分离的编程（以及设......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99