线性表及其顺序存储结构
线性表的基本概念
线性结构又称为线性表，线性表是最简单也是最常用的一种数据结构。
线性表的顺序存储结构
1.元素所占的存储空间必须连续
2.元素在存储空间的位置是按照逻辑顺序存放的
线性表的插入运算
在第i个元素之前插入一个新元素的步骤：
步骤一，把原来第n个结点至第i个结点依次往后移动一个元素的位置；
步骤二，把新结点放在第I个位置上；
步骤三，修正线性表的结点个数。
在最坏的情况下，插入元素在第一个位置，所有的元素都需要向后移动
线性表的删除运算
删除第i个元素的步骤如下：
步骤一，把第i个元素之后不包括第i个元素的n-i个元素依次前移一个位置；
步骤二，修正线性表的结点个数
栈和队列
栈及其基本运算
1.基本概念：栈是一种特殊的线性表，其插入运算与删除运算都只在线性表的一端运行，也被称之为先进后出，或后进先出
栈顶：允许插入与删除的一端
栈底：栈顶的另一端
空栈：栈中没有元素的栈
2.特点：栈顶元素是最后被插入和最早被删除的元素；栈底元素是最早被插入和最后被删除的元素；栈有记忆作用；在顺序存储的结构下，栈的插入和删除运算不需要移动表中其他数据元素；栈顶指针top动态反映了栈中元素的变化情况
3.顺序存储和运算：入栈运算、退栈运算、和读栈顶运算
网友评论