数据结构篇_知识点板块_第三章栈、队列和数组

2022年05月11日 阅读数:2
这篇文章主要向大家介绍数据结构篇_知识点板块_第三章栈、队列和数组,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
  • 数据结构篇为本人考研时所写笔记,包括知识点和编程思想两大板块,笔记内容依据王道数据结构考研书所写,但比书本上知识更加生动形象,愿本篇章能对您有所帮助

3、栈、队列和数组

(一)栈(LIFO)

  1. 栈的数学性质:n个不一样元素进栈,出栈元素不一样排列的个数为1/(n+1) *Cn,2n编程

  2. 因栈的删除插入操做都在栈顶进行,故只可能发生上溢数组

  3. 存储数据的原则是先进后出数据结构

  4. 顺序栈:3d

① 栈顶指针:初始时设s.top=-1(此处注意看题目是等于-1仍是0,两种入栈和出栈操做等会有不一样)指针

② 进栈:栈不满时,栈顶指针先加1,再送值到栈顶(S.data[++s.top])code

③ 出栈:非空时,先取栈顶元素,再将栈顶指针减1(S.data[s.top--])blog

④ 栈空:s.top==-1递归

⑤ 栈满:s.top==Maxsize-1队列

⑥ 栈长:s.top+1数学

  1. 共享栈:

① 两个顺序栈共享一个一维数组空间,将两个栈底分别设置在共享栈的两端(利用栈底相对位置不变的特性),栈顶向共享空间的中间延伸

② 栈空:top0=-1时0号栈为空,top1=Maxsize时1号栈为空

③ 栈满:top1与top0相邻

④ 进栈:s.data[++top0],s.data[--top1]

  1. 链栈:

① 优势:便于多个栈共享存储空间和提升其效率

② 通常没有判断栈满的操做,由于是动态

③ 建栈和判空时在没有头结点时是判断是否等于NULL,区别于顺序栈的等于-1

(二)队列(FIFO)

  1. (会出例以下列不是队列的基本运算的是这种选择题)

  2. 队头-删除;队尾-插入

  3. 作题时注意rear和front所指元素是队头/尾元素仍是后一个元素

  4. 顺序存储:

① 队空:q.frontq.rear0

② 进队:不满时先送值到队尾元素再将队尾指针+1(区别于栈)

③ 出队:不空时先取队头元素再将队头指针+1

④ 假上溢:因为入队和出队操做使头尾指针只增不减,致使被删元素的空间没法利用,队尾指针超过向量空间的上界而不能入队

  1. 循环队列:

① 为克服“假上溢”而想象出来的一种队列

② 初始:q.front=q.rear=0

③ 队首指针进1:q.front=(q.front+1) % maxsize

④ 队尾指针进1:q.rear=(q.rear+1) % maxsize

⑤ 出队入队:指针都按顺时针方向进1

⑥ 队满三种处理方式

(1) 牺牲一个单元来区分,此时:

​ (1 队满:(q.rear+1) % maxsize == q.front

​ (2 队中元素个数:(q.rear-q.front+maxsize) % maxsize

(2) 增设记录元素个数的数据成员

(3) 增设tag成员,判断条件为(q.frontq.rear && tag1),故tag只要插入一个元素就变为1,删除一个元素就变回0

  1. 链式存储:

① 注意题目中是否带头结点

② 插入时注意:若原队列为空列,则另q.front和q.rear一同指向插入结点

③ 删除时注意:若删除后队列为空则需修改尾指针为rear=front 选择可能会考查当插入一个就队满或删除一个就队空时rear和front的指向状况

④ 程序中使用多个队列或栈宜采用链式

⑤ 特别注意对于循环链表的插入删除后必须保持其循环

  1. 双端队列:(选择看到与普通队列操做不同时想到可能为双端队列)

① 输入受限双端队列:容许在一端进行插入和删除,但在另外一端只容许删除

② 输出受限双端队列:容许在一端进行插入和删除,但在另外一端只容许插入

(三)数组和特殊矩阵

  1. 下标的取值范围被称为数组的维界

  2. 若题中没指定数组下标范围只说明了为数组则下标默认从0开始数组的存储结构:

① 行优先:

② 列优先:

  1. 矩阵的压缩存储:

① 对称矩阵:

(1) 上三角区的全部元素和下三角区的对应元素相同

(2) 将矩阵A[1..n][1..n]存放在一维数组B[n(n+1)/2]中

(3)

② 三角矩阵:

(1) 下三角:

​ (1 上三角区的全部元素均为同一常量

​ (2 存完下三角区和主队角线元素后,还存储对角线上方的常量一次

​ (3 将矩阵A[1..n][1..n]压缩在B[n(n+1)/2+1]中

​ (4

(2) 上三角:

​ (1 下三角区的全部元素均为同一常量

​ (2 存完上三角区和主队角线元素后,还存储对角线下方的常量一次

​ (3 将矩阵A[1..n][1..n]压缩在B[n(n+1)/2+1]中

​ (4

③ 三对角矩阵:

(1)

(2) 已知三对角矩阵中某元素ai,j存放于一维数组B的第k个位置,则可得 : i=向下取整((k+1)/3+1),j=k-2i+3

  1. 稀疏矩阵:

① 压缩存储后必失去随机存储的特性

② 稀疏矩阵的三元组(行号,列号,值)既能够采用数组存储,也能够采用十字链表法存储

  1. 广义表:

① 广义表是线性表的推广,广义表是n个元素的有限序列,元素能够是原子或一个广义表,记为LS

② 若元素是广义表称它为LS的子表。若广义表非空,则第一个元素称表头,其他元素称表尾。

③ 表的深度是指表展开后所含括号的层数

④ 把与树对应的广义表称为纯表,它限制了表中成分的共享和递归;

⑤ 容许结点共享的表称为再入表

⑥ 容许递归的表称为递归表;

⑦ 相互关系:线性表∈纯表∈再入表∈递归表;

⑧ 广义表的特殊运算:1)取表头head(LS);2)取表尾tail(LS);