首页 > 其他分享 >坐牢第十五天 20240723

坐牢第十五天 20240723

时间：2024-07-24 18:55:05浏览次数：11  
标签：queue 结点 队列 坐牢 20240723 NULL 第十五天 节点 指针

一.笔记

1.栈的补充

 链式栈

1> 链式存储的栈，称为链式栈

2> 对于单链表而言，我们可以使用，使用头插头删完成一个栈，或者尾插尾删完成链式栈

3> 头插头删：链表的头部就是栈顶，链表的尾部就是栈底（常用）

4> 尾插尾删：链表的尾部就是栈顶，链表的头部就是栈底

2.队列

2.1 队列介绍

1> 队列也是操作受限的线性表：所有操作只能在端点处进行，其删除和插入必须在不同端进行

2> 允许插入操作的一端称为队尾，允许删除操作的一端称为队头

3> 特点：先进先出（FIFO）

4> 分类：

顺序存储的队列称为顺序队列

链式存储的队列，称为链式队列

2.2 顺序队列

1> 使用一片连续存储的空间存储队列，并且给定两个变量，分别记录队头和队尾下标

2> 普通顺序队列使用中，存在“假溢满”现象

假溢满：队列中明明还有存储空间，但是由于队尾已经达到了数组的最大下标，不能在继续入队元

素了

3> 为了解决“假溢满”现象，我们引入了循环顺序队列

2.3 循环顺序队列

1> 循环顺序队列：通过相关操作，当对头或队尾达到数组最大下标时，可以返回到下标为0的位置

2> 结构体类型：一个数组存储队列，两个变量分别存储队头和队尾的下标

注意：需要人为浪费一个存储空间，用于判满

2.5代码：

1> loopseqqueue.h

#ifndef LOOPSEQQUEUE_H
#define LOOPSEQQUEUE_H

#include<myhead.h>

#define MAX 8          //队列最大长度
typedef int datatype;   //数据元素类型
//定义队列类型
typedef struct
{
    datatype data[MAX];   //存储队列的容器
    int front;          //记录队头下标
    int tail;           //记录队尾下标
}SeqQueue, *SeqQueuePtr;

//创建队列
SeqQueuePtr queue_create();

//队列判空
int queue_empty(SeqQueuePtr Q);

//队列判满
int queue_full(SeqQueuePtr Q);

//入队
void queue_push(SeqQueuePtr Q, datatype e);

//遍历队列
void queue_show(SeqQueuePtr Q);

//出队
void queue_pop(SeqQueuePtr Q);

//求队列的大小
int queue_size(SeqQueuePtr Q);

//销毁队列
void queue_destroy(SeqQueuePtr Q);

#endif

2> loopseqqueue.c

#include"loopseqqueue.h"

//创建队列
SeqQueuePtr queue_create()
{
    //在堆区申请一个队列的大小
    SeqQueuePtr Q =(SeqQueuePtr)malloc(sizeof(SeqQueue));
    if(NULL==Q)
    {
        printf("创建失败\n");
        return NULL;
    }

    //初始化
    bzero(Q->data, sizeof(Q->data));  //初始化数组
    Q->front = Q->tail = 0;          //队列为空

    printf("队列创建成功\n");
    return Q;
}

//队列判空
int queue_empty(SeqQueuePtr Q)
{
    return Q->front == Q->tail;
}

//队列判满
int queue_full(SeqQueuePtr Q)
{
    return (Q->tail+1)%MAX == Q->front;
}

//入队
void queue_push(SeqQueuePtr Q, datatype e)
{
    //判断逻辑
    if(NULL==Q || queue_full(Q))
    {
        printf("入队失败\n");
        return ;
    }

    //入队逻辑
    Q->data[Q->tail] = e;

    //队列变化：队尾后移
    Q->tail = (Q->tail+1)%MAX;

    printf("入队成功\n");
}

//遍历队列
void queue_show(SeqQueuePtr Q)
{
    //判断逻辑
    if(NULL==Q || queue_empty(Q))
    {
        printf("遍历失败\n");
        return ;
    }

    //遍历逻辑
    printf("从队头到队尾元素分别是：");
    for(int i=Q->front; i!=Q->tail; i=(i+1)%MAX)
    {
        printf("%d\t", Q->data[i]);
    }
    printf("\n");
}

//出队
void queue_pop(SeqQueuePtr Q)
{
    //判断逻辑
    if(NULL==Q || queue_empty(Q))
    {
        printf("出队失败\n");
        return;
    }

    //出队逻辑
    printf("%d出队成功\n", Q->data[Q->front]);

    //队头后移
    Q->front = (Q->front+1)%MAX;

}

//求队列的大小
int queue_size(SeqQueuePtr Q)
{
    //在不使用循环的情况下求大小
    //判断逻辑
    if(NULL == Q)
    {
        printf("失败\n");
        return -1;
    }

    return (Q->tail-Q->front+MAX)%MAX;    //核心语句
}

//销毁队列
void queue_destroy(SeqQueuePtr Q)
{
    if(NULL != Q)
    {
        free(Q);
        Q = NULL;
    }

    printf("销毁成功\n");
}

3> main.c

#include<myhead.h>
#include"loopseqqueue.h"

int main(int argc, const char *argv[])
{
    //调用创建队列函数
    SeqQueuePtr Q = queue_create();
    if(NULL == Q)
    {
        return -1;
    }
    
    //调用入队函数
    queue_push(Q, 520);
    queue_push(Q, 1314);
    queue_push(Q, 666);
    queue_push(Q, 999);

    //调用遍历函数
    queue_show(Q);

    //调用出队函数
    queue_pop(Q);
    queue_pop(Q);
    queue_pop(Q);
    queue_pop(Q);
    queue_pop(Q);

    queue_show(Q);

    //销毁队列
    queue_destroy(Q);
    Q = NULL;




    
    return 0;
}

2.6 链式队列

1> 链式存储的队列称为链式队列

2> 实现原理：

单向链表头插尾删实现：链表的头部就是队尾，链表的尾部就是队头

单向链表头删尾插实现：链表的头部就是队头，链表的尾部就是队尾

但是：上述操作中，都要用到链表尾部节点，都需要遍历整个链表完成，效率较低

此时，我们可以引入尾指针的概念，专门指向最后一个节点的指针。

3> 将一个头指针和一个尾指针封装成一个队列

4>代码：

1 looplinkqueue.h

#ifndef LOOPLINKQUEUE_H
#define LOOPLINKQUEUE_H
#include<myhead.h>
//定义数据元素类型
typedef int datatype;

//定义结点类型
typedef struct Node
{
    union
    {
        datatype data;  //数据域
        int len;      //长度
    };

    struct Node *next;   //指针域
}Node, *NodePtr;

//定义队列类型
typedef struct 
{
    NodePtr head;    //头指针
    NodePtr tail;    //尾指针
}Queue, *QueuePtr;

//创建队列
QueuePtr queue_create();


//判空
int queue_empty(QueuePtr Q);

//入队
void queue_push(QueuePtr Q, datatype e);

//遍历队列
void queue_show(QueuePtr Q);

//出队
void queue_pop(QueuePtr Q);

//求队列长度
int queue_size(QueuePtr Q);

//销毁队列
void queue_destroy(QueuePtr Q);





#endif

2 looplinkqueue.c
 

#include"looplinkqueue.h"

//创建队列
QueuePtr queue_create()
{
    //堆区申请一个队列的空间
    QueuePtr Q = (QueuePtr)malloc(sizeof(Queue));
    if(NULL == Q)
    {
        printf("创建失败\n");
        return NULL;
    }

    //此时 Q->head 和Q->tail是两个野指针

    //创建一个链表
    Q->head = (NodePtr)malloc(sizeof(Node));
    if(Q->head == NULL)
    {
        printf("创建失败\n");
        free(Q);     //释放队列空间
        return NULL;
    }
    //给头结点初始化
    Q->head->len = 0;
    Q->head->next = NULL;
    
    //将两个指针指向头结点
    Q->tail = Q->head;

    printf("创建成功\n");
    return Q;

}

//判空
int queue_empty(QueuePtr Q)
{
    return Q->head == Q->tail;
}

//入队
void queue_push(QueuePtr Q, datatype e)
{
    //判断逻辑
    if(NULL==Q)
    {
        printf("入队失败\n");
        return;
    }

    //申请结点封装数据
    NodePtr p = (NodePtr)malloc(sizeof(Node));
    if(NULL==p)
    {
        printf("入队失败\n");
        return;
    }
    //初始化
    p->data = e;
    p->next = NULL;

    //尾插
    Q->tail->next = p;    //将结点连接到链表上

    //更新尾指针
    Q->tail = p;

    //表长变化
    Q->head->len++;

    printf("入队成功\n");
}

//遍历队列
void queue_show(QueuePtr Q)
{
    //判断逻辑
    if(NULL==Q || queue_empty(Q))
    {
        printf("遍历失败\n");
        return ;
    }

    //定义遍历指针，从第一个结点出发
    NodePtr q = Q->head->next;
    while(q!=NULL)
    {
        //只要结点不为空，就输出数据域
        printf("%d\t", q->data);

        q = q->next;     //向后遍历
    }
    printf("\n");

}

//出队
void queue_pop(QueuePtr Q)
{
    //判断逻辑
    if(NULL==Q || queue_empty(Q))
    {
        printf("出队失败\n");
        return ;
    }

    //出队：头删
    NodePtr p = Q->head->next;    //标记
    Q->head->next = p->next;      //孤立

    printf("%d出队成功\n", p->data);
    free(p);                      //删除
    p = NULL;

    //判断是否已经全部删除
    if(Q->head->next == NULL)
    {
        //尾指针重新指向头结点
        Q->tail = Q->head;
    }


    //表长变化
    Q->head->len--;

}

//求队列长度
int queue_size(QueuePtr Q)
{
    //判断逻辑
    if(NULL==Q)
    {
        return -1;
    }

    return Q->head->len;

}

//销毁队列
void queue_destroy(QueuePtr Q)
{
    //判断逻辑
    if(NULL==Q)
    {
        return;
    }

    //释放所有的结点
    while(!queue_empty(Q))
    {
        queue_pop(Q);      //不断将结点出队
    }
    
    //释放头结点
    free(Q->head);
    Q->head=Q->tail = NULL;    //防止野指针

    //释放队列空间
    free(Q);
    Q = NULL;
    printf("释放成功\n");
}

3> main.c

#include"looplinkqueue.h"

int main(int argc, const char *argv[])
{
    //调用创建函数
    QueuePtr Q = queue_create();
    if(NULL==Q)
    {
        return -1;
    }

    //调用入队函数
    queue_push(Q, 111);
    queue_push(Q, 222);
    queue_push(Q, 333);
    queue_push(Q, 444);

    //调用遍历函数
    queue_show(Q);

    //调用出队函数
    queue_pop(Q);
    queue_pop(Q);
    
    //释放队列空间
    queue_destroy(Q);
    Q = NULL;


    
    return 0;
}

3.树

1.树形结构相关概念

1> 树形结构：表示数据元素之间存在一对多的关系

2> 树：是由一个根结点个多个子树构成的树形结构

3> 节点：就是树中的数据元素

4> 父亲结点：当前结点的直接上级节点

5> 孩子节点：当前结点的直接下级节点

6> 祖先结点：当前结点的直接或间接上级节点

7> 子孙节点：当前结点的直接或间接下级节点

8> 兄弟节点：拥有相同父结点的所有节点互称为兄弟节点

9> 堂兄弟节点：其父结点在同一层的所有节点，互为堂兄弟节点

10> 根结点：没有父结点的节点

11> 叶子节点：没有子节点的节点称为叶子节点

12> 分支节点：节点的度不为0的节点叫分支节点

13> 节点的度：就是当前结点的孩子节点个数，就称为节点的度

14> 树的度：就是树中节点的度的最大值

15> 节点的层次：从根结点开始到当前结点所经历的层数称为该节点的层次

16> 树的层次：输出节点的层次的最大值

2.二叉树

2.1 二叉树的相关概念

1> 二叉树：由根结点和最多两个子树组成，并且严格区分左右子树的树形结构

2> 左子树：由当前结点的左孩子节点为根结点构成的二叉树

3> 右子树：由当前结点的右孩子节点为根结点构成的二叉树

4> 满二叉树：二叉树的最后一层全是叶子节点，在没有添加层数的条件下，不能在向该树中增加节点的树

（除了最后一层为叶子节点外，其余层中的节点的度全为2）

5> 完全二叉树：在一棵满二叉树的基础上，最后一层自右向左逐渐减少节点的二叉树

2.2 二叉树的状态

一共有五种：空二叉树、只有根结点、只有根结点和左孩子、只有根结点和右孩子、全都有

2.3 二叉树的性质

1> 在二叉树的第 i 层上最多有 2^(i-1)个节点

2> 在二叉树的前n层最多有 2^n - 1个节点

3> 在二叉树中，叶子节点的个数，总比度为2的节点个数多 1

4> 在二叉树上，如果第i个节点存在左孩子，那么其左孩子一定是第 2*i个节点，如果存在右孩子，那么一定是第2*i+1个节点

二.面试题

第一天
1.typedef定义指针函数的方式  
答： typedef  int（*a）（int）
2.对void *指针的相关理解 相关应用 
答：可以存放任意类型的地址的指针，属于万能指针， 常用于函数的形参，不能直接对万能指针进行取值运算

标准答案：void *表示“任意类型的指针”或表示“该指针与一地址值相关，但是不清楚在此地址上的对象的类型”。void指针只支持几种有限的操作：与另一个指针进行比较；向函数传递void指针或从函数返回void指针；给另一个void指针赋值。不允许使用void指针操作它所指向的对象，例如，不允许对void指针进行解引用。不允许对void指针进行算术操作。
3.static 修饰局部变量的作用  
答：从功能上改变局部变量的定义域 使其变成全局变量  

标准答案：  static实际修改了局部变量的存储类型，将原本应该存储在栈区的局部变量存储在静态区。静态的数据存储的特点是，程序结束变量才被释放。我们常见的全局变量就是存储在静态区上。

现在我们分析static修饰后作用域和生命周期的变化：

1.作用域：作用域不变，只是出作用域不被销毁

2.生命周期：生命周期变长，程序结束生命周期才结束

4.野指针是什么 ，野指针的产生情况
答：指向非法内存称为野指针  1.没有初始化2.下标越界3.指针函数返回的是生命周期较短的地址4.指向的地址空间被释放的指针

标准答案：1.野指针，就是指针指向的位置是不可知的（随机的、不正确的、没有明确限制的）很可能触发运行时段错误（Sgmentation fault）

2.野指针的产生情况

1.创建指针时没有对指针进行初始化，导致指针指向一个随机的位置；
2、释放指针指向的内存后没有置空，从而指向垃圾内存；
3、在超越变量作用域下使用指针，如：在栈内存被释放之后，指向栈内存的指针会指向垃圾内存；

3.如何避免免野指针

第一：定义指针时，同时初始化为NULL
第二：在指针解引用之前，先去判断这个指针是不是NULL
第三：指针使用完之后，将其赋值为NULL 　
第四：在指针使用之前，将其赋值绑定给一个可用地址空间
5.栈和队列的区别 
答1.他们都是操作受限的线性表，都是线性结构2.栈是先进后出 队列是先进先出3.栈的插入和删除只能在一段进行操作 队列可以在队头和队尾操作

标准答案：

栈和队列都是常用的数据结构，它们的主要区别在于数据的插入和删除顺序。

栈 (Stack) 是一种后进先出 (Last-In-First-Out, LIFO) 的数据结构，只允许在一端进行插入和删除操作，这一端称为栈顶。新元素插入后成为新的栈顶，而删除时也只能删除栈顶元素。

队列 (Queue) 是一种先进先出 (First-In-First-Out, FIFO) 的数据结构，允许在两端进行插入和删除操作，插入在队尾，删除在队头。新元素插入时成为新的队尾，而删除时也只能删除队头元素

标签：queue,结点,队列,坐牢,20240723,NULL,第十五天,节点,指针
From： https://blog.csdn.net/m0_62828714/article/details/140643622

相关文章

  • 20240723（30.2）AH股行情总结：创业板收跌3%，消费股、有色、黑色系齐跌，高股息资产及国债上涨
    半导体产业链全线回调，光刻机、GPU方向领跌，白酒领跌消费股。银行股逆势走强，四大行股价再创新高。黑色系及有色金属齐跌，沪锡跌4%，铁矿石跌超3%。周二，A股低开低走，午后跌幅加剧上证指数收跌1.6%，深成指跌近3%，创业板跌3%，两市成交额超6600亿，下跌股票数量超4600只。半导体产业链大幅走......
  • 坐牢第十三天 20240719
    一.笔记一.链表的引入1.1总结顺序表的优缺点1>优点：能够直接通过下标进行定位元素，访问效率高，对元素进行查找和修改比较快2>不足：插入和删除元素需要移动大量的元素，效率较低3>缺点：存储数据元素有上限，当达到MAX后，就不能再添加元素了1.2链表的概念1>链式存储的线性表叫......
  • 代码随想录算法训练营第十五天 | 110.平衡二叉树、257. 二叉树的所有路径 、404.左叶
    110.平衡二叉树题目：.-力扣（LeetCode）思路：后序遍历计算高度代码：/***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNode*left;*TreeNode*right;*TreeNode():val(0),left(nullptr),right(nullptr){}*......
  • 坐牢第五天加第六天 20240709
    作业1、提示并输入一个字符串，统计该字符串中字母、数字、空格以及其他字符的个数代码:​#include<stdio.h>#include<string.h>intmain(intargc,charconst*argv[]){chararr[100];inta,c,d,e=0;printf("请输入一个字符串:");gets(arr);f......
  • 坐牢第七天 20040710
    1.作业：完成学生管理系统1>使用菜单完成2>有学生的信息录入功能：输入学生个数，并将学生的姓名、分数录入3>查看学生信息：输出所有学生姓名以及对应的分数4>求出学习最好的学生信息：求最大值5>按姓名将所有学生进行升序排序6>按成绩将所有学生进行升序排序要求每个功能......
  • 代码随想录算法训练营第十五天|110.平衡二叉树、257.二叉树的所有路径、404.左叶子之
    110平衡二叉树1classSolution{2public:3intGetHeight(TreeNode*root){4if(!root){5return0;6}7intleftHeight=GetHeight(root->left);8if(leftHeight==-1)ret......
  • 代码随想录算法训练营第十五天 | 层序遍历 、226.翻转二叉树、101.对称二叉树
    层序遍历题目链接：学会二叉树的层序遍历，可以一口气打完以下十题：102.二叉树的层序遍历107.二叉树的层次遍历II199.二叉树的右视图637.二叉树的层平均值429.N叉树的层序遍历515.在每个树行中找最大值116.填充每个节点的下一个右侧节点指针117.填充每个节点的下一个右侧节点......
  • JavaWeb学习笔记——第十五天
    Maven高级分模块设计与开发分模块设计就是将项目按照功能拆分成若干个子模块。优点：方便项目的管理维护、扩展，也方便模块间的相互调用，资源共享。分模块设计需要先针对模块功能进行设计，再进行编码实现。不会先将工程开发完毕，然后进行拆分。继承与聚合继承继承描述的是两个......
  • 代码随想录算法训练营第十五天| 226. 翻转二叉树 101. 对称二叉树
    226.翻转二叉树https://leetcode.cn/problems/invert-binary-tree/description/publicTreeNodeinvertTree(TreeNoderoot){invert(root);returnroot;}publicvoidinvert(TreeNodenode){if(node==null)return;TreeNod......
  • Java学习笔记——第十五天
    集合进阶（一）集合体系结构单列集合（Collection）Collection代表单列集合，每个元素（数据）只包含一个值。双列集合（Map）Map代表双列集合，每个元素包含两个值（键值对）。Collection集合体系Collection集合体系的特点List系列集合：添加的元素有序、可重复、有索引。ArrayList、LinkedList......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99