2014年软考程序员常考知识点复习笔记第三章

 2、线性表

　　(1) 性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表。

　　(2)单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式。

　　(3)单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处。

　　3、栈与队列

　　你可以问一下自己是不是已经知道了以下几点：

　　(1)栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队等。栈与队列存取数据(请注意包括：存和取两部分)的特点。

　　(2)递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法：n!阶乘问题，fib数列问题，hanoi问题，背包问题，二叉树的递归和非递归遍历问题，图的深度遍历与栈的关系等。其中，涉及到树与图的问题，多半会在树与图的相关章节中进行考查。

　　(3)栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性了解，具体要求考查此为题目的算法设计题不多。

　　(4)循环队列中判队空、队满条件，循环队列中入队与出队(循环队列在插入时也要判断其是否已满，删除时要判断其是否已空)算法。

　　【循环队列的队空队满条件

　　为了方便起见，约定：初始化建空队时，令

　　front=rear=0,

　　当队空时：front=rear，

　　当队满时：front=rear 亦成立，

　　因此只凭等式front=rear无法判断队空还是队满。

　　有两种方法处理上述问题：

　　(1)另设一个标志位以区别队列是空还是满。

　　(2)少用一个元素空间，约定以"队列头指针front在队尾指针rear的下一个位置上"作为队列"满"状态的标志。

　　队空时： front=rear，

　　队满时： (rear+1)%maxsize=front】

　　如果你已经对上面的几点了如指掌，栈与队列一章可以不看书了。注意，我说的是可以不看书，并不是可以不作题哦。

　　循环队列的主要操作：

　　(1)创建循环队列

　　(2)初始化循环队列

　　(3)判断循环队列是否为空

　　(4)判断循环队列是否为满

　　(5)入队、出队

　　//空出头尾之间的一个元素不用

　　#include

　　#include

　　#define MAXSIZE 100

　　typedef struct

　　{

　　intelem[MAXSIZE];

　　intfront, rear;

　　}Quque; //定义队头

　　int initQue(Quque **q) //初始化

　　{

　　(*q)->front=0;

　　(*q)->rear=0;

　　}

　　int isFull(Quque *q)

　　{

　　if(q->front==(q->rear+1)%MAXSIZE)//判满(空出一个元素不用)

　　return 1;

　　else

　　return 0;

　　}

　　int insertQue(Quque **q,int elem)

　　{

　　if(isFull(*q))return -1;

　　(*q)->elem[(*q)->rear]=elem;

　　(*q)->rear=((*q)->rear+1)%MAXSIZE;//插入

　　return0;

　　}

　　int isEmpty(Quque *q)

　　{

　　if(q->front==q->rear)//判空

　　return 1;

　　else

　　return 0;

　　}

　　int deleteQue(Quque ** q,int *pelem)

　　{

　　if(isEmpty(*q))

　　return 0;

　　*pelem=(*q)->elem[(*q)->front];

　　(*q)->front=((*q)->front +1)%MAXSIZE;

　　return0;

　　}