2、線性表
(1) 性表的鏈?zhǔn)酱鎯?chǔ)方式及以下幾種常用鏈表的特點(diǎn)和運(yùn)算:?jiǎn)捂湵怼⒀h(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)題,二叉樹(shù)的遞歸和非遞歸遍歷問(wèn)題,圖的深度遍歷與棧的關(guān)系等。其中,涉及到樹(shù)與圖的問(wèn)題,多半會(huì)在樹(shù)與圖的相關(guān)章節(jié)中進(jìn)行考查。
(3)棧的應(yīng)用:數(shù)值表達(dá)式的求解,括號(hào)的配對(duì)等的原理,只作原理性了解,具體要求考查此為題目的算法設(shè)計(jì)題不多。
(4)循環(huán)隊(duì)列中判隊(duì)空、隊(duì)滿(mǎn)條件,循環(huán)隊(duì)列中入隊(duì)與出隊(duì)(循環(huán)隊(duì)列在插入時(shí)也要判斷其是否已滿(mǎn),刪除時(shí)要判斷其是否已空)算法。
【循環(huán)隊(duì)列的隊(duì)空隊(duì)滿(mǎn)條件
為了方便起見(jiàn),約定:初始化建空隊(duì)時(shí),令
front=rear=0,
當(dāng)隊(duì)空時(shí):front=rear,
當(dāng)隊(duì)滿(mǎn)時(shí):front=rear 亦成立,
因此只憑等式front=rear無(wú)法判斷隊(duì)空還是隊(duì)滿(mǎn)。
有兩種方法處理上述問(wèn)題:
(1)另設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)列是空還是滿(mǎn)。
(2)少用一個(gè)元素空間,約定以“隊(duì)列頭指針front在隊(duì)尾指針rear的下一個(gè)位置上”作為隊(duì)列“滿(mǎn)”狀態(tài)的標(biāo)志。
隊(duì)空時(shí): front=rear,
隊(duì)滿(mǎn)時(shí): (rear+1)%maxsize=front】
如果你已經(jīng)對(duì)上面的幾點(diǎn)了如指掌,棧與隊(duì)列一章可以不看書(shū)了。注意,我說(shuō)的是可以不看書(shū),并不是可以不作題哦。
循環(huán)隊(duì)列的主要操作:
(1)創(chuàng)建循環(huán)隊(duì)列
(2)初始化循環(huán)隊(duì)列
(3)判斷循環(huán)隊(duì)列是否為空
(4)判斷循環(huán)隊(duì)列是否為滿(mǎn)
(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)//判滿(mǎn)(空出一個(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;
}
北京 | 天津 | 上海 | 江蘇 | 山東 |
安徽 | 浙江 | 江西 | 福建 | 深圳 |
廣東 | 河北 | 湖南 | 廣西 | 河南 |
海南 | 湖北 | 四川 | 重慶 | 云南 |
貴州 | 西藏 | 新疆 | 陜西 | 山西 |
寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
黑龍江 | 內(nèi)蒙古 |