2013年軟考《程序員》考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理3

　　2、線性表

　　(1) 性表的鏈?zhǔn)酱鎯?chǔ)方式及以下幾種常用鏈表的特點(diǎn)和運(yùn)算：?jiǎn)捂湵�、循環(huán)鏈表，雙向鏈表，雙向循環(huán)鏈表。

　　(2)單鏈表的歸并算法、循環(huán)鏈表的歸并算法、雙向鏈表及雙向循環(huán)鏈表的插入和刪除算法等都是較為常見(jiàn)的考查方式。

　　(3)單鏈表中設(shè)置頭指針、循環(huán)鏈表中設(shè)置尾指針而不設(shè)置頭指針以及索引存儲(chǔ)結(jié)構(gòu)的各自好處。

　　3、棧與隊(duì)列

　　你可以問(wèn)一下自己是不是已經(jīng)知道了以下幾點(diǎn)：

　　(1)棧、隊(duì)列的定義及其相關(guān)數(shù)據(jù)結(jié)構(gòu)的概念，包括：順序棧，鏈棧，共享?xiàng)＃�循環(huán)隊(duì)列，鏈隊(duì)等。棧與隊(duì)列存取數(shù)據(jù)(請(qǐng)注意包括：存和取兩部分)的特點(diǎn)。

　　(2)遞歸算法。棧與遞歸的關(guān)系，以及借助棧將遞歸轉(zhuǎn)向于非遞歸的經(jīng)典算法：n!階乘問(wèn)題，fib數(shù)列問(wèn)題，hanoi問(wèn)題，背包問(wèn)題，二叉樹的遞歸和非遞歸遍歷問(wèn)題，圖的深度遍歷與棧的關(guān)系等。其中，涉及到樹與圖的問(wèn)題，多半會(huì)在樹與圖的相關(guān)章節(jié)中進(jìn)行考查。

　　(3)棧的應(yīng)用：數(shù)值表達(dá)式的求解，括號(hào)的配對(duì)等的原理，只作原理性了解，具體要求考查此為題目的算法設(shè)計(jì)題不多。

　　(4)循環(huán)隊(duì)列中判隊(duì)空、隊(duì)滿條件，循環(huán)隊(duì)列中入隊(duì)與出隊(duì)(循環(huán)隊(duì)列在插入時(shí)也要判斷其是否已滿，刪除時(shí)要判斷其是否已空)算法。

　　【循環(huán)隊(duì)列的隊(duì)空隊(duì)滿條件

　　為了方便起見(jiàn)，約定：初始化建空隊(duì)時(shí)，令

　　front=rear=0,

　　當(dāng)隊(duì)空時(shí)：front=rear，

　　當(dāng)隊(duì)滿時(shí)：front=rear 亦成立，

　　因此只憑等式front=rear無(wú)法判斷隊(duì)空還是隊(duì)滿。

　　有兩種方法處理上述問(wèn)題：

　　(1)另設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)列是空還是滿。

　　(2)少用一個(gè)元素空間，約定以“隊(duì)列頭指針front在隊(duì)尾指針rear的下一個(gè)位置上”作為隊(duì)列“滿”狀態(tài)的標(biāo)志。

　　隊(duì)空時(shí)： front=rear，

　　隊(duì)滿時(shí)： (rear+1)%maxsize=front】

　　如果你已經(jīng)對(duì)上面的幾點(diǎn)了如指掌，棧與隊(duì)列一章可以不看書了。注意，我說(shuō)的是可以不看書，并不是可以不作題哦。

　　循環(huán)隊(duì)列的主要操作：

　　(1)創(chuàng)建循環(huán)隊(duì)列

　　(2)初始化循環(huán)隊(duì)列

　　(3)判斷循環(huán)隊(duì)列是否為空

　　(4)判斷循環(huán)隊(duì)列是否為滿

　　(5)入隊(duì)、出隊(duì)

　　//空出頭尾之間的一個(gè)元素不用

　　#include

　　#include

　　#define MAXSIZE 100

　　typedef struct

　　{

　　intelem[MAXSIZE];

　　intfront, rear;

　　}Quque; //定義隊(duì)頭

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

　　{

　　(*q)->front=0;

　　(*q)->rear=0;

　　}

　　int isFull(Quque *q)

　　{

　　if(q->front==(q->rear+1)%MAXSIZE)//判滿(空出一個(gè)元素不用) 劉勉剛

　　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;

　　}