当前位置： 首页 > article >正文

数据结构(二)栈/队列和二叉树/堆

article 2025/1/21 16:10:09

目录

1.栈

2.队列

3. 二叉树

4.堆

1.栈:

1.1概念介绍:

        只允许一端进行数据插入和删除, 进行数据插入删除的叫栈顶, 另外一段就是栈底.

特点是先入数据后出来, 后入数据先出来.(先入后出)

 1.2 栈的实现:

(1) 栈结构:

        栈可以使用链表或者数组, 但是一般使用数组的.

typedef int STDataType;

typedef struct Stack
{
    STDataType* a;
    int top;
    int capacity;
}Stack;
 (2) 初始化:

        创建数组a以及top和capacity置空.

void StackInit(Stack* ps)
{
    assert(ps);

    ps->a = (STDataType*)malloc(sizeof(STDataType));
    ps->top = 0;
    ps->capacity = 0;
}
(3) 销毁:
void StackDestroy(Stack* ps)
{
    assert(ps);

    free(ps->a);
    ps->a = nullptr;
    ps->top = ps->capacity = 0;
}
(4) 入栈:

        如果栈满, 需要扩容二倍, 再插入数据.

void StackPush(Stack* ps, STDataType data)
{
    assert(ps);

    if(ps->top == ps->capacity)
    {
        STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);
        if(tmp == nullptr)
        {
            printf("realloc fail!\n");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity *= 2;
    }
    ps->a[ps->top] = data;
    ps->top++;
}
(5) 出栈:

        判断栈不为空的情况下, 再将top--就是出栈.

bool StackEmpty(Stack* ps)
{
    assert(ps);
    return ps->top == 0;
}

void StackPop(Stack* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));

    ps->top--;
}
(6) 获取栈顶元素:

        先判断栈不为空, 然后再从栈中查找栈顶元素出栈即可.

STDataType StackTop(Stack* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));

    return ps->a[ps->top-1];
}
(7) 获取栈中有效元素个数:

        栈中top字段恰好也记录了元素个数的.

int StackSize(Stack* ps)
{
    assert(ps);

    return ps->top;
}

2.队列:

2.1 概念介绍:

        只允许一边插入数据, 另外一边出数据. 特点是先进去的数据可以先出掉, 但是后进入的数据后面出掉(先入先出); 进数据是队尾, 出数据是队头. 而且一般使用链表结构来封装队列

 2.2 实现:

(1) 结构:

        结构和单链表一致. 由于出栈入栈比较频繁使用链表比数组效率高些. 由于队头队尾要记录一下使用到Queue封装一下.


typedef int QDataType;
typedef struct QListNode
{
    QDataType data;
    QListNode* next;
}QListNode;


typedef struct Queue
{
    QListNode* head;
    QListNode* tail;
};
(2) 初始化:

        起始时候tail和head都是空的.

void QueueInit(Queue* q)
{
    assert(q);
    q->head = nullptr;
    q->tail = nullptr;
}
(3) 销毁:

        因为是链表, for循环遍历链表的方式进行删除.

void QueueDestroy(Queue* q)
{
    assert(q);
    QListNode* cur = q->head;
    while(cur)
    {
        QListNode* next = cur->next;
        free(cur);
        cur = next;
    }
    q->head = q->tail = nullptr;
}
(4) 队尾入队列:

        先创建一个新结点newnode, 如果队列为空, 头和尾结点都是newnode, 否则只要插入到尾部结点之后再修改尾结点即可.

void QueuePush(Queue* q, QDataType data)
{
    assert(q);

    QListNode* newnode = (QListNode*)malloc(sizeof(QListNode));
    if(newnode == nullptr)
    {
        printf("malloc fail!\n");
        exit(-1);
    }
    newnode->data = data;
    newnode->next = nullptr;
    if(q->head = nullptr)
    {      
        //链表为空.
        q->head = q->tail = newnode;
    }
    else
    {
        //改变尾指针.
        q->tail->next = newnode;
        q->tail = newnode;
    }
}
(5) 队头出队列:

        出队列首先要判断释放队列为空, 接着就是队列只有一个数据只有删除后, head=tail=nullptr置空操作, 否则就是改变head指针指向到下一个结点位置, 然后删除结点.

bool QueueEmpty(Queue* q)
{
    return q->head == q->tail;
}

void QueuePop(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));

    if(q->head->next == nullptr)
    {
        //队列中只有一个结点:
        free(q->head);
        q->head = q->tail = nullptr;
    }
    else
    {
        QListNode* next = q->head->next;
        free(q->head);
        q->head = next;
    }
}
(6) 获取队列头部/尾部元素:

        先检查队列释放为空, 然后不是前面封装头尾指针, 直接使用查询data数据即可.

QDataType QueueFront(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));

    return q->head->data;
}

QDataType QueueBack(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));

    return q->tail->data;
}
(7) 获取队列中有效元素个数:

        和链表一样队列遍历一边即可.

int QueueSize(Queue* q)
{
    assert(q);

    QListNode* cur = q->head;
    int count = 0;

    while(cur)
    {
        count++;
        cur = cur->next;
    }
    return count;
}

2.3 循环队列:

        这里不详细讲解在生产者消费者中讲解. 如果head==tail就是空队列, 但是tail+1 = head就是满的队列. 计算内部有效元素个数 = (tail - head + 队列长度) %队列长度.

3. 二叉树:

3.1 树的概念:

        非线性的数据结构, 有限结点组成的具有层次的关系集合, 而且树是递归定义的; 有点像倒过来的树. 而且子树之间不能有交集, 要不然就不是树型结构了.

(1) 结点的度: 一个结点拥有结点的个数; 例如上面1的度就是2;

(2) 叶子结点(终端结点): 度为0的结点; 例如8, 9, 6, 7结点;

(3) 分支结点: 度不为0的结点; 例如4, 2, 3结点;

(4) 父节点/子节点: 拥有孩子的结点就是父节点, 孩子结点就是子节点;

(5) 树的度: 最大结点的度就是树的度;

(6) 树的高度: 树结点的最大层数;

(7) 森林: 互不相交结点的集合就是森林;

 3.2 结构:

        一般使用的就是孩子兄弟表示法; 因为既要保存值还要保存结点和结点之间的关系;

firstchild是第一个孩子结点, nextBrother是兄弟结点;

typedef int DataType;
struct Node
{
    struct Node* firstchild;
    struct Node* nextBrother;
    DataType data;
};

3.3 二叉树概念:

        二叉树是结点的有限集合, 一种情况是空, 另外就是根节点加上左右子树.

(1) 二叉树的度不能大于2;

(2) 二叉树有左右子树之分, 不能搞错.

(3) 二叉树有五种可能: 空, 只有根结点, 只有根节点和左子树, 只有根节点和右子树, 根节点和左右结点都有.

特殊二叉树:

        满二叉树: 每一层的结点都是最大值;

        完全二叉树: 可能最后一层的结点不是满的最大值, 但是左结点是有的, 不可能只有右节点没有左结点.

 3.4 二叉树性质:

(1) 第i层最多2^(i-1)个结点;

(2) 深度为h的二叉树最多2^h-1个结点;

(3) 度为0的结点个数为n0, 度为2的结点个数为n2, 那么n0 = n2 + 1;

(4) n个结点的满二叉树深度是: log2^(n+1);

(5) i结点双亲结点: (i-1)/2; 左孩子结点:(2i+1); 右孩子结点:(2*i+2);

 3.5 二叉树存储结构:

        一般二叉树都是完全二叉树比较适合数组结构, 在物理结构是数组, 但是逻辑结构是二叉树.采用下标进行排列成二叉树

也有链表结构的二叉树:

 3.6 链表实现二叉树:

(1) 链式二叉树结构:        

前面主要是利用数组进行实现二叉树, 其实还可以使用链表;

typedef char BTDataType;

typedef struct BTNode
{
    BTDataType data;
    struct  BTNode* left;
    struct  BTNode* right;
}BTNode;
 (2) 前中后遍历:

        根据遍历规则进行使用链表结构进行遍历, 包括前中后序遍历.

void BinaryPrevOrder(BTNode* root)
{
    //前序遍历: 根->左子树->右子树
    if(root == nullptr)
        return;
    printf("%c ", root->data);
    BinaryPrevOrder(root->left);
    BinaryPrevOrder(root->right);
}

void BinaryInOrder(BTNode* root)
{
    //中序遍历: 左子树->根->右子树;
    if(root == nullptr)
        return;
    
    BinaryInOrder(root->left);
     printf("%c ", root->data);
    BinaryInOrder(root->right);
}

void BinaryPostOrder(BTNode* root)
{
    //后序遍历: 左子树->右子树->根;
   if(root == nullptr)
        return;
    
    BinaryPostOrder(root->left);
    BinaryPostOrder(root->left);
    printf("%c ", root->data);
}
 (3) 层序遍历:

        使用到队列进行每层的遍历进行插入数据.

void BinaryLevelOrder(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    if(root != nullptr)
        QueuePush(&q, root);
    
    while(!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        printf("%c ", front->data);
        if(front->left)
        {
            QueuePush(&q, front->left);
        }
        if(front->right)
        {
            QueuePush(&q, front->right);
        }
    }
    QueueDestroy(&q);
}
(4) 计算二叉树结点个数:

               使用到递归链表进行计数. +1是每走一层进行++.

int BinaryTreeSize(BTNode* root)
{
    return root == nullptr ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
 (5) 计算叶子结点个数:

        叶子结点的特点就是左右子树为空.

int BinaryTreeLeafSize(BTNode* root)
{
    if(root == nullptr)
        return 0;
    
    if(root->left == nullptr && root->right == nullptr)
    {
        return 1;
    }

    return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
 (7) 计算K层结点个数:

        父节点个数等于左右子节点k-1层的结点个数.

int BinaryTreeLevelKSize(BTNode* root, int k)
{
    if(k < 1 || root == nullptr) 
        return 0;
    
    if(k == 1)
        return 1;
    
    return BinaryTreeLevelKSize(root->left, k-1) + BinaryTreeLevelKSize(root->right, k-1); 
}
 (8) 找出data==x的结点:
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
    if(root == nullptr)
        return nullptr;
    
    if(root->data == x)
        return root;
    
    BTNode* left = BinaryTreeFind(root->left, x);
    if(left)
        return left;
    BTNode* right = BinaryTreeFind(root->right, x);
    if(right)
        return right;
    return nullptr;
}
 (9) 计算树的最大深度:
int Max(int a, int b)
{
    return a > b ? a : b;
}

int BinaryTreeMaxDepth(BTNode* root)
{
    if(root == nullptr)
        return 0;
    
    return Max(BinaryTreeMaxDepth(root->left), BinaryTreeMaxDepth(root->right));
}

4.堆

4.1 概念:

        完全二叉树按照顺序结构进行存储在一个一维数组里面就是堆, 大堆就是第一个数据(顶数据)是最大的,小堆就是顶数据是最小的.

 4.2 实现:

(1) 堆的向下调整法:

        这里代码是建立小堆, 传递parent位置, 那么child位置就是parent*2+1; 首先还要比较左右结点的大小, 判断child的位置好进行后续的交换位置.(这里使用了其他博主的图).

时间复杂度是O(logN); 因为向下调整法要求左右子树都是堆结构, 所以我们从下到上建堆.

这样根据数学计算建堆的时间复杂度就是O(N);

void Swap(int* x, int* y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

//建立小堆
void AdjustDown(int* a, int n, int parent)
{
    int child = parent * 2 + 1;
    while(child < n)
    {
        if(child + 1 < n && a[child+1] < a[child])
        {
            //右孩子小于左孩子;
            child++;
        }

        if(a[child] < a[parent])
        {
            //交换父节点和子结点.
            Swap(&a[parent], &a[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            //以及是堆了.
            break;
        }
    }
}

//从最后一个父节点开始进行调整.
    for(int i = (n-1-1) / 2; i >= 0; i--)
    {
        AdjustDown(p->a, p->size, i);
    }
    return 0;
(2) 堆的向上调整法:

        用于插入数据进行调整; 这里同样是小堆, child的值小于parent的值就进行交换, 不断改变child和parent的位置就可以走完一条路径.

void AdjustUp(DataType* a, int child)
{
    int parent = (child-1) / 2;
    while(child > 0)
    {
        if(a[child] < a[parent])
        {
            Swap(&a[parent], &a[child]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}
(3) 初始化堆:

        先开辟n个空间, 再将a数据拷贝新空间里面, 再进行向下调整建堆.

void HeapCreate(Heap* hp, HPDataType* a, int n)
{
    assert(hp);

    //开辟n个空间;
    HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType )* n);
    if(tmp == nullptr)
    {
        printf("malloc fail!\n");
        exit(-1);
    }
    hp->a = tmp;
    //将a数据拷贝到hp->a里面;
    memcpy(hp->a, a, sizeof(HPDataType)*n);
    hp->size = n;
    hp->capacity = n;

    for(int i = (hp->size-1-1) / 2; i >= 0; i--)
    {
        //建立小堆;向下调整建堆.
        AdjustDown(hp->a, hp->size, i);
    }
}
(4) 堆销毁:
void HeapDestory(Heap* hp)
{
    assert(hp);
    free(hp->a);
    hp->a = nullptr;
    hp->size = hp->capacity = 0;
}
(5) 堆的插入:

          先要检查是否需要扩容, 扩容把原数据进行拷贝, 然后插入数据, 维持堆结构进行向上调整法.

void HeapPush(Heap* hp, HPDataType x)
{
    assert(hp);
    if(hp->size == hp->capacity)
    {
        HPDataType* tmp = (HPDataType*)realloc(hp->a, 2 * hp->capacity * sizeof(HPDataType));
        if(tmp == nullptr)
        {
            printf("realloc fail!\n");
            exit(-1);
        }
        hp->a = tmp;
        hp->capacity *= 2;
    }
    hp->a[hp->size] = x;
    hp->size++;

    //插入数据后需要保持堆结构采用向上调整法:
    AdjustUp(hp->a, hp->size-1);
}
(6) 堆的删除:

        删除只能删除堆顶元素, 因为删除任意元素都可能打乱原本的结构, 所以交换堆顶和堆底元素, 然后删除堆顶元素, hp->size--即可, 然后再进行向下调整即可.

void HeapPop(Heap* hp)
{
    assert(hp);
    assert(!HeapEmpty(hp));

    //交换堆顶和堆底元素
    Swap(&hp->a[0], &hp->a[hp->size-1]);
    hp->size--;

    AdjustDown(hp->a, hp->size, 0);
}
(7) 获取堆顶的数据:
HPDataType HeapTop(Heap* hp)
{
    assert(hp);
    return hp->a[0];
}
(8) 获取堆的数据个数:
int HeapSize(Heap* hp)
{
    assert(hp);
    return hp->size;
}

4.2 topk问题:

(1) 问题描述:

        给一个数组找到最大的k个数; 例如: 数组:[1, 3, 4, 2, 5 ,7] ,找到最大的三个数就是

[4, 5, 7]

(2) 解决方案(一):

        使用堆结构, 建立小堆, 然后再进行降序排序, 取出前k个即可. 可以思考一下降序我们就需要建立小堆(因为大的已经在堆顶排列好), 升序建立大堆; 这样时间复杂度就是

O(N + NlogN).

int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{
    *returnSize = k;
    //建立小堆.
    for(int i = (arrSize-1-1) / 2; i >= 0; i--)
    {
        AdjustDown(arr, arrSize, i);
    }

    //排降序;
    int end = arrSize - 1;
    while(end > 0)
    {
        Swap(&arr[0], &arr[end]);
        AdjustDown(arr, end, 0);
        end--;
    }

    int* retArr = (int*)malloc(sizeof(int) * k);
    for(int i = 0; i < k; i++)
    {
        retArr[i] = arr[i];
    }
    return retArr;
}
(3) 解决方案(二):

        采用建大堆的方法, 然后取出前k个大的数据, 先取堆顶元素, 然后进行向下调整法, 在得到次大的数取出来, 一直重复取得前k个大的数, 这样时间复杂度就是O(N + KlogN) ->O(N+logN).

//建立大堆
void AdjustDown(int* a, int n, int parent)
{
    int child = parent * 2 + 1;
    while(child < n)
    {
        if(child + 1 < n && a[child+1] > a[child])
        {
            //右孩子小于左孩子;
            child++;
        }

        if(a[child] > a[parent])
        {
            //交换父节点和子结点.
            Swap(&a[parent], &a[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            //以及是堆了.
            break;
        }
    }
}


int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{
    *returnSize = k;
    for(int i = (arrSize-1-1) / 2; i >= 0; i--)
    {
        AdjustDown(arr, arrSize, i);
    }

    //将最大k个数保持到数组;
    int* retArr = (int*)malloc(sizeof(int) * k);
    int end = arrSize - 1;
    for(int i = 0; i < k; i++)
    {
        retArr[i] = arr[0];
        Swap(&arr[0], &arr[end]);
        AdjustDown(arr, end, 0);
        end--;
    }
    return retArr;
}
(4) 解决方案(三):

        如果数据很大, 有1001亿个呢? 还能用吗? 有没有其他方法?

        先将前k个数进行建立小堆, 然后后面n-k个数就是一个个和堆顶元素进行比较, 如果比堆顶元素大, 就交换, 在进行调整选出其中最小的进行下一次的交换(就是被比下去了).这样时间复杂度就是O(K + NlogK) ---> O(N);

//建立小堆
void AdjustDown(int* a, int n, int parent)
{
    int child = parent * 2 + 1;
    while(child < n)
    {
        if(child + 1 < n && a[child+1] < a[child])
        {
            //右孩子小于左孩子;
            child++;
        }

        if(a[child] < a[parent])
        {
            //交换父节点和子结点.
            Swap(&a[parent], &a[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            //以及是堆了.
            break;
        }
    }
}


int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{
    *returnSize = k;
    if(k == 0)
        return nullptr;

    int* retArr = (int*)malloc(sizeof(int) * k);
    for(int i = 0; i < k; i++)
    {
        retArr[i] = arr[i];
    }

    //前k个数建小堆;
    for(int i = (k - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(retArr, k, i);
    }

    //将后n-k个数据每一个和retArr[0]进行比较, 
    //然后每次在k个里面选出最小和n-k个数据进行比较交换调整.
    for(int i = k; i < arrSize; i++)
    {
        if(arr[i] > retArr[0])
        {
            retArr[0] = arr[i];
        }
        AdjustDown(retArr, k, 0);
    }
    return retArr;
}


http://www.kler.cn/a/512290.html

相关文章：

  • Java基于SSM框架的社区团购系统小程序设计与实现（附源码，文档，部署）
  • Axios 封装：处理重复调用与内容覆盖问题
  • 写作利器：如何用 PicGo + GitHub 图床提高创作效率
  • 使用Torchvision框架实现对象检测：从Faster-RCNN模型到自定义数据集，训练模型，完成目标检测任务。
  • STL--list（双向链表）
  • Java开发提速秘籍：巧用Apache Commons Lang工具库
  • centos虚拟机异常关闭，导致数据出现问题
  • 【2024年度个人生活与博客事业的融合与平衡总结】
  • 深入解析 C++17 中的 u8 字符字面量：提升 Unicode 处理能力
  • 大模型LLM-微调 RAG
  • Java-数据结构-二叉树习题(1)
  • AUTOSAR OS模块详解(三) Alarm
  • 我想通过python语言，学习数据结构和算法该如何入手？
  • 低代码运维与管理服务
  • 大数据学习(37)- Flink运行时架构
  • 嵌入式STM32创新教学：华清远见虚拟仿真实验平台与智能车项目师资培训
  • Zemax STAR 模块的入门设置
  • 《数字图像处理（面向新工科的电工电子信息基础课程系列教材）》重印变更的彩插
  • Linux(Centos 7.6)命令详解：iconv
  • matlab中的griddata函数
  • element表格滚动错位问题，使用uniapp写的项目
  • 基于Web实时通信的无人机载物联网与严格时间敏感性：案例研究
  • 力扣刷题心得_JAVA
  • 鸿蒙系统 将工程HarmonyOS变成OpenHarmony
  • Leetcode3095：或值至少 K 的最短子数组 I
  • Ascend NPU 架构 CANN 平台入门学习