数据结构第二章复习.docVIP

线性表及其顺序存储 2.1线性表 线性表是一个线性结构，有n（n=0）个结点的有限序列，对于其中的结点，有且仅有一个开始结点，它没有前驱担忧一个后继结点；有且仅有一个终端结点，它没有后继但有一个前驱结点；其他的结点都有且仅有一个前驱和一个后继结点。 线性表的存储采用顺序存储和链式存储两种方式。 2.2顺序表 2.2.1顺序标的基本概念及描述 线性表采用顺序存储方式存储就称为顺序表。顺序表是将表中的结点一次存放在计算机内存中一组地址连续的存储单元中。 2.2.2顺序表的实现 用C语言中的数组存储顺序表，数组的下标是从0开始的，即数组中下标为0的元素队友的是顺序表中的第一个结点，数组中下标为i的元素是顺序表中第i+1个结点。为了方便，将顺序表中各结点的序号改为和对应数组元素的下标序号一致，即将顺序表中个结点的序号从0开始编号。这样，一个长度为n的顺序表表示为：｛k0,k1,k2,...,kn-1｝ 顺序表存储结构的C语言描述如下： 普及概念，如果是变量，那么用XXX. 如果是指针则用XXX- 下面是顺序表的基本操作 顺序表的插入操作 顺序表的插入算法的平均移动次数为n/2，在一个长度为n的顺序表中插入一个元素平均需要移动表中的一半元素，该算法的时间复杂度为O(n) 顺序表的删除操作 顺序表的删除算法的平均移动次数为（n-1）/2，在一个长度为n的顺序表中插入一个元素平均需要移动表中的一半元素，该算法的时间复杂度为O(n) 2.3栈 2.3.1栈的基本概念及描述 栈是一种特殊的线性表，它的插入运算和删除运算均在线性表的同一端进行，进行插入和删除的那一端称为栈顶，另一端称为栈底。栈的插入操作和删除操作菲尼被简称进栈和出栈。 2.3.2顺序栈及其实现 顺序栈存储结构的C语言描述如下： 下面是顺序栈的基本操作 2.4队列 2.4.1队列的基本概念及描述 队列是一种特殊的线性表，特殊在于队列的插入和删除操作分别在表的两端进行。插入的那一端称为队尾，删除的那一端称为队首。插入操作和删除操作分别简称进队和出队。 队列是具有“先进先出”（First In Fitst Out,FIFO）特点的线性结构（也可以是后进后出LILO）。 队列的操作集合如下： 队列顺序存储结构的C语言描述如下 下面是顺序队列的基本操作 2.4.3顺序循环队列 循环队列满与空的条件都是rear=front，这个问题有两个方法解决，估计要采用后者，牺牲一个数组元素的空间，即若数组的大笑是MAXSIZE，则该数组所表示的循环队列最多允许存储MAXSIZE-1个结点。(书P32有两种方法的详细讲述) 这样，循环队列满的条件是：(rear+1)%MAXSIZE=front 队空的条件是：rear=front ① 10计科②班数据结构复习资料