您现在的位置：希赛网>云阅读>软件设计师考试考前串讲>线性表第3章：数据结构与算法作者：希赛教育软考学院来源：希赛网2014年05月19日线性表上一节本书简介下一节第3章：数据结构与算法作者：希赛教育软考学院来源：希赛网2014年05月19日栈3.2线性表在线性表方面，主要考查栈和队列的基本操作，循环链表和双向链表的操作，二维数组的存储，以及广义表的基本概念。严格地说，广义表不是线性表，但为了方便，我们把它归结到这个知识点。线性表是最简单和最常用的一种数据结构，线性表是由相同类型的结点组成的有限序列。一个由n个结点a0,a1,…，an-1组成的线性表可记为（a0,a1,…，an-1）。线性表的结点个数为线性表的长度，长度为0的线性表称为空表。对于非空线性表，a0是线性表的第一个结点，an-1是线性表的最后一个结点。线性表的结点构成一个序列，对序列中两相邻结点ai和ai+1称ai是ai+1的前驱结点，ai+1是ai的后继结点。其中a0没有前驱结点，an-1没有后继结点。线性表中结点之间的关系可由结点在线性表中位置所确定，通常用（ai,ai+1）（0≤i≤n–2）表示两个结点之间的先后关系。例如：如果两个线性表有相同的数据结点，但它们的结点在线性表中出现的顺序不同，则它们是两个不同的线性表。线性表的结点可由若干个成分组成，其中能唯一标识该结点的成分称为关键字，或简称键。为了讨论方便，往往只考虑结点的关键字，而忽略其他成分。版权方授权希赛网发布，侵权必究3.2.1栈栈是一种特殊的线性表，栈只允许在同一端进行插入和删除运算。允许插入和删除的一端称为栈顶，另一端称为栈底。称栈的结点插入为进栈，结点删除为出栈。因为最后进栈的结点必定最先出栈，所以栈具有后进先出（先进后出）的特征。1.顺序存储可以用顺序存储线性表来表示栈，为了指明当前执行插入和删除运算的栈顶位置，需要一个地址变量top指出栈顶结点在数组中的下标。2.链接存储栈栈也可以用链表实现，用链表实现的栈称为链接栈。链表的第一个结点为顶结点，链表的首结点就是栈顶指针top,top为NULL的链表是空栈。上一节本书简介下一节第3章：数据结构与算法作者：希赛教育软考学院来源：希赛网2014年05月19日队列上一节本书简介下一节第3章：数据结构与算法作者：希赛教育软考学院来源：希赛网2014年05月19日链表版权方授权希赛网发布，侵权必究3.2.2队列队列也是一种特殊的线性表，只允许在一端进行插入，另一端进行删除运算。允许删除运算的那一端称为队首，允许插入运...
