一、线性表
1、定义
：线性表是n个元素的有限序列，通常记为（a1,a2,…,an）。
2、特点
：
存在惟一的表头和表尾；
除了表头外，表中的每一个元素均只有
惟一的直接前驱
；
除了表尾外，表中的每一个元素均只有
惟一的直接后驱
。
3、存储结构
：顺序存储，链式存储。
4、顺序存储
：是用一组地址连续的存储单元一次存储线性表中的数据元素，从而使得逻辑关系相邻的两个元素在物理外置上也相邻。
优点：可以随机存取表中的元素
缺点：插入和删除操作需要移动大量的元素。
5、链式存储
：是指用结点来存储数据元素，结点的空间可以是连续的，也可以是不连续的。因此存储数据元素的同时必须存储元素直接的逻辑关系。
优点：插入和删除操作不需要移动元素，操作方便。
缺点：增加了存储空间开销，不能随机访问任一结点。
6、其他链表结构：双向链表，循环链表，静态链表。
二、栈：（先进后出的线性表）
1、定义
：栈是只能通过一端来实现数据存储和检索的一种线性表。
进行插入和删除操作的一端称为栈顶，另一端称为栈底。
2、存储结构
：顺序存储，链式存储。
三、队列：（先进先出的线性表）
1、定义
：队列是一种先进先出的线性表，它只允许在表的一端插入元素，而在表的另一端删除元素。
在队列中，允许
插入元素的一端称为队尾
（rear），允
许删除元素的一端称为队头
（front）。
2、存储结构
：顺序存储，链式存储。
3、队列为空的判定条件是
：头指针和尾指针的值相同，且均指向头结点。
四、串：
1、定义
：串是仅由字符构成的有限序列，是取值范围受限的线性表。
2、串的存储结构
：顺序存储，链式存储。
3、串的几个基本概念
：
（1）空串：
长度为零
的串，空串不包含任何字符。
（2）空格串：由一个或多个
空格组
成的串。
（3）子串：由串中任意长度的连续字符构成的序列。含有子串的串称为主串。空串是任意串的子串。
（4）串相等：指两个串长度相等且对应位置上的字符也相同。
（5）串比较：两个串比较大小时以字符的
ASCII码
值作为依据。
五、软考常考的题
1、
函数
的调用和返回控制是用
栈
实现的。
2、栈和队列都不允许在元素序列的中间插入和删除元素。
3、线性表采用单链表存储结构时，访问表中的元素的方式是顺序存取。
4、栈和队列的主要区别是插入和删除运算的要求不同。
5、单链表不具有可随机访问表中的任一元素。
6、在堆栈操作中，堆栈的底保持不变。
7、线性表采用
单链表
存储时的特点是
插入和删除不需要移动元素
。
8、一个序列经过一个初始为空的
队列
后，元素的排列
次序不变
。一个序列经过一个初始为空的
栈
后，元素的排列
次序可能发生改变
。因为使用栈时，只要
栈不空，就可以进行出栈的操作
。
9、
数组
只能进行
读取和修改
的操作。
10、对于顺序栈和链栈，
入栈时需要判断是否栈满
不是两者的共有的运算特征。（
顺序栈需要判断，链栈不需要
）。无论栈采用那种存储结构，进行
出栈
的时候，
都需要判断栈是否为空
，栈为空时无法出栈。
11、含有n个元素的线性表采用顺序存储等概率的删除其中的任意一个元素，平均需要移动==（n-1）/2==个元素。
12、线性表采用
单循坏链表存储
的主要特点时
从表中任意一结点出发都能遍历整个链表
。
13、若某线性表长度为n且采用
顺序存储
方式，则运算速度
最快
的操作是
查找并返回第i个元素
。
14、令序列
X、Y、Z
的每一元素按照顺序进栈，且每个元素进出栈各一次，则
不可能
得到的
出栈序列是ZXY
（ZXY不可能得到这个序列，因为当Z最先出栈，说明X、Y已经入栈，且X比Y先入栈，那么在出栈的时候，X比Y要后出栈，所以当X最先出栈，只能够得到Z、Y、X这样的出栈序列。）
15、对于一个初始为空的栈，
入栈序列为abc
，则出栈序列有
5
种。
16、设数组A[1…n,1…m]的每个元素占用1个存储单元， 对于数组元素A[i，j](1≤i≤n， 1≤j≤m)，
在按
行存储
方式下，其相对于数组空间首地址的偏移量为==(i-1)*m+j-1==，
在按
列存储
方式下，其相对于数组，空间首地址的偏移量为==(j-1)*i+i-1==。
17、若采用链地址法对关键字序列(74, 10,23, 6, 45, 38, 18)构造哈希表(或散列表)，设散列函数为H(Key)=Key%7 (%表示整除取余运算)，则哈希表中地址为(
0、1、5
)的单链表长度为0(即没有关键字被映射到这些哈希地址)。
