查看匯總：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;

　　}

　　相關推薦：

　　各地2014年下半年軟件水平考試報名時間匯總

　　各地2014下半年軟件水平考試準考證打印時間匯總

　　考試吧特別策劃：2014年計算機軟考報考指南專題