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

数据结构_day3

article 2024/10/25 21:37:05

目录

4.栈 stack

4.2.1 特性

练习：

4.3 链式栈

4.3.1 特性

总结：

4.栈 stack

4.2.1 特性

逻辑结构：线性结构

存储结构：顺序结构

操作：创建、入栈、出栈、判空和判满

创空：

入栈：

出栈：

代码实现：

#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct seqstack
{
    int maxlen;     //表示数组元素总个数
    datatype *data; //指向存放数据的数组的指针
    int top;        //栈顶有可以称栈针，本质还是最后一个有效元素下标等同于之前学的顺序表的last
} seqstack_t;

//创建空顺序栈, len代表创建栈时的最大长度
seqstack_t *createEmptySeqStack(int len)
{
    //1. 开辟顺序栈结构体大小空间
    seqstack_t *p = (seqstack_t *)malloc(sizeof(seqstack_t));
    if (NULL == p)
    {
        perror("p malloc err");
        return NULL;
    }
    //2. 初始化结构体空间
    p->top = -1;                                          //如同之前的last初始化为-1，因为元素个数是0，下标是0-1=-1
    p->maxlen = len;                                      //保存数组长度可以通过传参获取
    p->data = (datatype *)malloc(sizeof(datatype) * len); //开辟数组大小空间，单个元素大小乘以元素个数
    if (NULL == p->data)
    {
        perror("p->data malloc err");
        return NULL;
    }

    return p;
}

//判断是否为满,满返回1 未满返回0
int isFullSeqStack(seqstack_t *p)
{
    return p->top + 1 == p->maxlen;
}

//入栈,data代表入栈的数据
int pushStack(seqstack_t *p, int data)
{
    //  1. 判满： p->top + 1 == p->maxlen
    if (isFullSeqStack(p))
    {
        printf("pushStack err\n");
        return -1;
    }
    // 让top栈顶加一
    p->top++;
    // 将数据入栈
    p->data[p->top] = data;

    return 0;
}

//判断栈是否为空
int isEmptySeqStack(seqstack_t *p)
{
    return p->top == -1;
}

//出栈
int popSeqStack(seqstack_t *p)
{
    //1.容错判断
    if (isEmptySeqStack(p))
    {
        printf("popSeqStack\n");
        return -1;
    }
    //printf("%d\n", p->data[p->top]);  //或者加打印也可以
    //2. 将栈针top减一
    p->top--;
    //3. 返回要出栈数据
    return p->data[p->top + 1];
}

int main(int argc, char const *argv[])
{
    seqstack_t *p = createEmptySeqStack(6);
    for (int i = 0; i < 7; i++)
        pushStack(p, i); //最后报一个pushStack err，因为栈满了

    while (!isEmptySeqStack(p))
        printf("%d\n", popSeqStack(p));  //5 4 3 2 1 0 后进先出
    return 0;
}

练习：

*通动力校园招聘笔试题

1. 若进栈顺序为 1,2,3,4 一下四种情况不可能出现的出栈序列是( )

  A.  1,4,3,2    //入1出1入234出4出3出2

  B.  2,3,4,1    //入12 出2 入3 出3 入4出4 出1

  C.  3,1,4,2

  D.  3,4,2,1 //入123出3入4出4出2 出1

  1. 下列叙述正确的是( )

A. 线性表是线性结构

B. 栈与队列是非线性结构

C. 线性链表是非线性结构

  1. 二叉树是线性结构

3. 下列关于栈叙述正确的是( )

    A.在栈中只能插入数据

    B.在栈中只能删除数据

    C.栈是先进先出的线性表

    D.栈是先进后出的线性表

4.请问下面的程序有问题吗？如果有问题在哪儿？

#include <stdio.h>
#include <stdlib.h>

void get_mem(int *q) //q=NULL
{
    q = (int *)malloc(sizeof(int)); //改变q不会影响到函数外的p， 开辟空间也不够
}

int main(int argc, char const *argv[])
{

    int i;
    int *p = NULL;
    get_mem(p); //函数调用完成后p还是等于NULL
    for (i = 0; i < 10; i++)
        p[i] = i;

    for (i = 0; i < 10; i++)
        printf("%d\n", p[i]);

    free(p);

    return 0;
}
​​​​​​​​​​​​​​

错误：相当于值传递，改变函数内的q不会影响到主函数的p，函数调用后p还是等于NULL。再一个开辟空间大小不够，只开辟了4字节。

修改：可以通过传递二级指针，或者返回值

#include <stdio.h>
#include <stdlib.h>

void get_mem(int **q) //q=&p
{
    *q = (int *)malloc(sizeof(int) * 10); //*q = *&p =p ,也就是操作*q就等同操作函数外的p
}

int main(int argc, char const *argv[])
{
    int i;
    int *p = NULL;
    get_mem(&p); //函数调用结束后p真的指向了堆区
    for (i = 0; i < 10; i++)
        p[i] = i;

    for (i = 0; i < 10; i++)
        printf("%d\n", p[i]);

    free(p);

    return 0;
}

4.3 链式栈

4.3.1 特性

逻辑结构：线性结构

存储结构：链式存储

顺序栈和链式栈的区别：存储结构不同，实现的方式也不同，顺序栈是用顺序表实现而链式栈用链表实现。

栈的操作：创建、入栈、出栈、判空

入栈：

出栈：

代码实现：

#include <stdio.h>
#include <stdlib.h>

typedef int datatype;
typedef struct node
{
    datatype data;
    struct node *next;
} node_t, *node_p;

//创建一个空栈
void createEmptyLinkStack(node_p *p) //p=&top
{
    *p = NULL; //*p = top = NULL
}

//入栈, data是入栈的数据
int pushLinkStack(node_p *p, datatype data) //因为要用p接收函数外的&top来在函数内找到top, 所以参数需要为二级指针。
{
    // 创建新节点
    node_p pnew = (node_p)malloc(sizeof(node_t));
    if (NULL == pnew)
    {
        perror("pnew malloc err");
        return -1;
    }
    // 将要入栈数据存入新节点
    pnew->data = data;
    pnew->next = NULL;
    // 将新节点连入到链表中
    pnew->next = *p; //*p=top
    // 移动栈针到新的栈顶节点
    *p = pnew;
    return 0;
}

//判断栈是否为空
int isEmptyLinkStack(node_p p)
{
    return p == NULL;
}

//出栈
datatype popLinkStack(node_p *p) //p=&top
{
    node_p pdel = NULL;
    //1. 判空：*p == NULL;
    if (isEmptyLinkStack(*p)) //*p=top
    {
        printf("popLinkStack err\n");
        return -1;
    }
    //2. 让指针pdel指向栈顶节点
    pdel = *p;
    //3. 移动栈针到下一个节点
    *p = (*p)->next; //*p=pdel->next;
    //4. 定义临时变量保存要出栈数据: temp = pdel->data;
    datatype temp = pdel->data;
    //5. 释放要被删除节点: free(pdel);
    free(pdel);
    //6. 返回要出栈数据：return temp;
    return temp;
}

//求栈的长度
int lengthLinkStack(node_p p) //传递一级指针，因为不需要移动栈针(也就是主函数的top)。
{
    int len = 0;
    while (p != NULL)
    {
        len++;
        p = p->next;
    }
    return len;
}

int main(int argc, char const *argv[])
{
    node_p top;
    createEmptyLinkStack(&top); //top=NULL
    pushLinkStack(&top, 1);
    pushLinkStack(&top, 2);
    pushLinkStack(&top, 3);

    printf("len=%d\n", lengthLinkStack(top));

    while (!isEmptyLinkStack(top))
    {
        printf("%d\n", popLinkStack(&top)); //3 2 1
    }

    return 0;
}

总结：

顺序栈和链式栈的区别是什么？

  1. 顺序栈是顺序存储，内存连续，用顺序表实现；链表是链式存储，内存不连续，用链表实现。
  2. 顺序栈的长度固定，而链栈不会。​​​​​​​


http://www.kler.cn/news/364947.html

相关文章：

  • 【移动应用开发】界面设计（二）实现水果列表页面
  • 全栈面试题】模块5-1】Oracle/MySQL 数据库基础
  • 飞睿智能超宽带UWB音频传输模块，超低延迟数据传输，实时音频声音更纯净
  • JS | 如何使用 JavaScript 实现图片懒加载的淡入效果？
  • Android组件化开发
  • 《计算机视觉》—— 基于 dlib 库的方法将两张人脸图片进行换脸
  • 在Spring中，什么是配置类
  • 【C语言】自定义类型：结构体（下）
  • 《首尔破笑组：在欢笑中触摸生活的温度》
  • 给已经写好的裸机程序移植freeRTOS操作系统（二）
  • 6.Three.js贴图与uv映射(uv坐标)理解和实践
  • 鸿蒙应用示例：仿钉钉日历新建日程
  • C语言中的分支与循环(中 1)
  • Java中的基本数据类型和引用类型存储在JVM中那个区域？
  • 缓存池（对象池）使用
  • 现代山东比较出名的人物颜廷利：以塑造智慧为荣，以失去素质为耻
  • MATLAB Simulink （一）直接序列扩频通信系统
  • 深入理解 RabbitMQ 及在.NET 中的应用
  • 碰一碰发视频源码开发，矩阵短视频新模式，支持OEM
  • Python基础知识-模块与包篇
  • H7-TOOL的LUA小程序教程第15期：电压，电流，NTC热敏电阻以及4-20mA输入(2024-10-21，已经发布)
  • 【Linux】命令行参数环境变量
  • vue 对象拷贝,解决引用赋值内容变化会修改原对象的方式
  • 【K8S】快速入门Kubernetes
  • Lua 语言中的注释详解
  • 本地原生多IPseo建站