首页 > 编程语言 >数据结构与算法2

数据结构与算法2

时间:2024-10-10 09:46:20浏览次数:8  
标签:1.5 顺序 栈链 1.3 int 算法 base 数据结构

目录

栈和队列

1.栈(stack)

1.1 栈的定义和特点

  • 栈是一个特殊的线性表,在表尾进行插入和删除
  • 后进先出的线性表(LIFO结构)

表尾(an端)称为栈顶TOP;表头(a1端)称为栈底BASE

  • 入栈:插入元素到TOP
  • 出栈:从TOP删除最后一个元素

同线性表相同,为一对一关系

  • 存储结构:顺序栈、链栈

    • 栈的顺序存储:顺序栈
    • 栈的链式存储:链栈
  • 上溢(overflow):栈已经满,继续压入值

  • 下溢(underflow):栈已经空,继续弹出值

上溢是一种错误,使问题处理无法进行
下溢使一种结束条件,问题处理结束

1.2 顺序栈的表示

#define MAXSIZE 100
typedef struct{
  int *base;    //栈底
  int *top;     //栈顶
  int stacksize;  //栈可用的最大容量
}SqStack;

1.3 顺序栈的实现

1.3.1 顺序栈的初始化

void InitStack(SqStack &S){    //构建一个空顺序栈
  S.base = new int[MAXSIZE];
  if(!S.base)  return;    //存储分配失败
  S.top = S.base;    
  S.stacksize = MAXSIZE;
}

1.3.2 顺序栈判断栈是否为空

bool StackEmpty(SqStack S){  //若栈顶等于栈底,则顺序栈为空
  if(S.top == S.base)  return true;
  else   return false;
}

1.3.3 求顺序栈长度

int StackLength(SqStack S){
  return S.top - S.base;
}

1.3.4 清空顺序栈

void ClearStack(SqStack &S){
  if(S.base)  S.top = S.base;
}

1.3.5 销毁顺序栈

void DestoryStack(SqStack &S){
  if(S.base){
    delete S.base;
    S.stacksize = 0;
    S.base = S.top = NULL;
  }
}

1.3.6 顺序栈的入栈

void Push(SqStack &S, int e){
  if(S.top - S.base == S.stacksize)    return;  //栈满
  *S.top++ = e;
}

1.3.7 顺序栈的出栈

void Pop(SqStack &S, int &e){
  if(S.top == S.base) return;
  e = *--S.top;
}

1.4 栈链的表示

  • 运算受限的单链表,只能在链表头部进行操作
  • 链表的头指针就是栈顶,不需要头结点
  • 插入删除仅在栈顶
typedef struct StackNode{
  int data;
  struct StackNode *next;
}StackNode, *LinkStack;
LinkStack S;

1.5 栈链的实现

1.5.1 栈链的初始化

void InitStack(LinkStack &S){
  S = NULL;
}

1.5.2 判断栈链是否为空

bool StackEmpty(LinkStack S){
  if(S == NULL)  return true;
  else           return false; 
}

1.5.3 栈链的入栈

void Push(LinkStack &S, int e){
  p = new StackNode;    //生成新节点
  p->data = e;
  p->next = S;
  S = p;
}

1.5.4 栈链的出栈

void Pop(LinkStack &S, int &e){
  if(S == NULL)  return;  
  e = S->data;   //出栈的元素值
  p = S;
  S = S->next;
  delete p;
}

1.5.5 取栈顶元素

int GetTop(LinkStack S){
  if(S == NULL)  return;
  return S->data;
}

2.队列(queue)

2.1 队列的定义和特点

  • 队列是一种先进先出(FIFO)的线性表
  • 在表尾插入,表头删除(头删尾插
  • 表尾为an端(队尾),表头为a1端(队头)

同线性表相同,为一对一关系

  • 存储结构:顺序队、链队

循环顺序队列更常见

2.2 顺序队的表示

#define MAXQSIZE 100 //最大队列长度
typedef define{
  int *base;  //初始化动态分配原始空间
  int front;  //头指针
  int rear;  //尾指针
}SqQueue;

2.3 顺序队的实现

常见问题:假上溢
解决方法:引入循环队列 实现方式:使用模运算

  1. 插入元素: Q.base[Q.rear] = x; Q.rear=(Q.rear+1) % MAXQSIZE;
  2. 删除元素: x = Q.base[s.front]; Q.front = (Q.front+1) % MAXQSIZE;

2.3.1 顺序队的初始化

void Init

标签:1.5,顺序,栈链,1.3,int,算法,base,数据结构
From: https://www.cnblogs.com/cherishviki/p/18430214

相关文章

  • 算法笔记(十五)——BFS 解决拓扑排序
    文章目录拓扑排序课程表课程表II火星词典拓扑排序有向无环图(DAG图)有向无环图指的是一个无回路的有向图AOV网:顶点活动图在有向无环图中,用顶点表示一个活动,用边来表示活动的先后顺序的图结构拓扑排序找到一个先后顺序,结果可能不唯一如何拓扑排序?找到一......
  • 二分图最大匹配-匈牙利算法
    二分图最大匹配设G为二分图,若在G的子图M中,任意两条边都没有公共节点,那么称M为二分图G的一组匹配。在二分图中,包含边数最多的一组匹配称为二分图的最大匹配。交替路:从一个未匹配点出发,依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。增广路:从一个未匹配点......
  • 算法修炼之路之前缀和
    目录一:一维前缀和二:二维前缀和 三:LeetCodeOJ练习  1.第一题2.第二题 3.第三题 4.第四题5.第五题6.第六题一:一维前缀和这里通过例题来引出牛客_DP34【模板】前缀和画图分析:具体代码:#include<iostream>#include<vector>usingnamespacestd;int......
  • 数据结构(链表)
    我可以接受失败,但绝对不能接受未奋斗过的自己。   链表链表的概念1.链表是⼀种物理存储结构上非连续、非顺序的存储结构。2.链表是顺序表的一种,所以它一定在逻辑结构上是线性的。3.数据元素的逻辑顺序是通过链表中的指针链接次序实现的。4.链表实际上由一个......
  • 算法校赛准备
    独木桥题目背景战争已经进入到紧要时间。你是运输小队长,正在率领运输部队向前线运送物资。运输任务像做题一样的无聊。你希望找些刺激,于是命令你的士兵们到前方的一座独木桥上欣赏风景,而你留在桥下欣赏士兵们。士兵们十分愤怒,因为这座独木桥十分狭窄,只能容纳$1$个人通过。假如......
  • 代码随想录算法训练营 | 背包问题 二维,背包问题 一维,416. 分割等和子集
    背包问题二维题目链接:背包问题二维文档讲解︰代码随想录(programmercarl.com)视频讲解︰背包问题二维日期:2024-10-09想法:dp[i][j],i表示需要从物品0-i中选择加入到背包中,j表示背包的容量,dp值表示最大的价值;递推公式,如果背包大小j都比此时要放的物品i的weight[i]小了,背包放不下......
  • 代码随想录算法训练营day10| 232.用栈实现队列 225. 用队列实现栈 20. 有效的括
    学习资料:https://programmercarl.com/栈与队列理论基础.html栈与队列学习记录:232.用栈实现队列(两个栈(stack_in,stack_out)实现一个队列的行为)点击查看代码classMyQueue(object):def__init__(self):self.stack_in=[]self.stack_out=[]d......
  • codeforces round 974(div.3)E(优先队列实现dijstra算法,devc++的优先队列用greater报
    解题历程:看到两边同时移动,计算最终的相遇时间,我就想到两边同时计算各点到起点的最短距离,就是使用dijstra算法,最后所有节点取两次计算的最大值,再对所有节点取最小值,就是最终答案了,可是这个思路没有考虑有马的情况,思考一番后发现可以多列一个数组记录有马的情况下的行走最短路,然后......
  • 必知的十大计算机视觉算法
    成长路上不孤单......
  • JAVA——常见算法
    查找算法基本查找从0索引开始查找是否找到packagecom.itheima.search;importjava.security.KeyStore;publicclassBasicSearchDemo1{publicstaticvoidmain(String[]args){int[]arr={23,34,54,24,43,46};intnumber=43;......