基础知识补充内容 - 图文

循环队列

循环队列图

1、rear：队尾指针 front：队头指针

2、循环队列的初始状态为空front=rear=6（图a） 3、入队运算：插入一个新元素后：rear（队尾指针）=6+1=1（这表示在最后一个位置插入元素后，紧接着在第一个位置插入新元素，这是由循环队列特性决定的）（图b） 4、队列满时rear=front=6（图c）

5、退队运算：首先队头指针加1：front=6+1=1；然后删除指针指向的元素(图d)

6、判断队列满还是队列空要增加一个标志S：S=0表示队列空 S=1表示队列非空 队列空的条件：S=0

队列满的条件：S=1 且 front=rear

线性链表

一、线性链表示例

二、线性链表的逻辑状态

1、 Null：未知或不存在

2、 指向第一个数据元素的头指针(HEAD)=Null（或者为0）时，称为空表 三、线性链表的基本运算

1、查找指定元素：从队头指针出发，沿着指针域Next逐个结点搜索，直到找到指定元素或链表尾部为止。在链表中，如果有指定元素，则扫描到等于该元素值的结点时，停止扫描，返回该结点的位置，因此，如果链表中有多个等于指定元素值的结点，只返回第一个结点的位置。如果链表中没有

元素的值等于指定元素，则扫描完所有元素后，返回Null。 2、线性链表元素的插入：在线性链表中包含元素x的结点前插入一个新元素b

(1)从可利用的栈取得一个结点，设该结点号为p，并置结点p的数据域插入的元素值b（见图b）

(2)在线性链表中寻找包含元素x的前一个结点，并设该结点号为q（见图b）

(3)最后将结点p插入到结点q之后，两个结点（p、q）指针变化如下：

A）使结点p指向包含元素x的结点 B）使结点q的指针域内容改为指向结点p 结果见图c，插入完成。