三、棧和隊(duì)列

　　1、知識(shí)點(diǎn):

　　● 棧的定義:操作受限的線性表
　　● 特點(diǎn):后進(jìn)先出
　　● 棧的存儲(chǔ)結(jié)構(gòu):順序,鏈接
　　　/ push(s,d)
　　● 棧的基本操作:
　　　\ pop(s)

　　棧定義：

　　struct {
　　　datatype data[max_num];
　　　int top;
　　};

　　●隊(duì)列定義
　　特點(diǎn):先進(jìn)先出
　　/入隊(duì)列 in_queue(Q,x)
　　●隊(duì)列的操作:
　　\出隊(duì)列 del_queue(Q)
　　●隊(duì)列存儲(chǔ)結(jié)構(gòu):
　　鏈隊(duì)列:
　　Typedef struct node{
　　　Datatype data;
　　　Struct node *next;
　　}NODE;
　　Typedef struct {
　　　NODE *front;
　　　NODE *rear;
　　}Queue;
　　順序隊(duì)列:
　　struct {
　　　datatype data[max_num];
　　　int front,rear;
　　};
　　問(wèn)題:
　　隊(duì)列ó線性表
　　假溢出<=循環(huán)隊(duì)列
　　隊(duì)列滿，隊(duì)列空條件一樣<=浪費(fèi)一個(gè)存儲(chǔ)空間

　　遞歸

　　定義：?jiǎn)栴}規(guī)模為N的解依賴于小規(guī)模問(wèn)題的解。問(wèn)題的求解通過(guò)小規(guī)模問(wèn)題的解得到。
　　包括二個(gè)步驟：
　　1） 遞推 6!=>5!=>4!=>3!=>2!=>1!=>0!
　　2） 回歸 720<=120<=24<=6 <=2 <=1 <=0
　　遞歸工作棧實(shí)現(xiàn)遞歸的機(jī)制。

　　2、有關(guān)算法：

　　1） 順序，鏈表結(jié)構(gòu)下的出棧，入棧
　　2） 循環(huán)，隊(duì)列的入隊(duì)列，出隊(duì)列。
　　3） 鏈隊(duì)列的入隊(duì)列，出隊(duì)列。
　　4） 表達(dá)式計(jì)算：后綴表達(dá)式 35+6/4368/+*- 
　　　　　　　　　　中綴表達(dá)式 （3+5）/6-4*（3+6/8）

　　由于中綴比較難處理，計(jì)算機(jī)內(nèi)一般先將中綴轉(zhuǎn)換為后綴。
　　運(yùn)算：碰到操作數(shù)，不運(yùn)算，碰到操符，運(yùn)算其前兩個(gè)操作數(shù)。
　　　中綴=>后綴
　　5) 迷宮問(wèn)題
　　6) 線性鏈表的遞歸算法 一個(gè)鏈表=一個(gè)結(jié)點(diǎn)+一個(gè)鏈表
　　int fuction(NODE *p) {
　　　if(p==NULL) return 0;
　　　else return(function(p->next));
　　}

　　樹與二叉樹

　　一、 知識(shí)點(diǎn):

　　1. 樹的定義: data_struct(D,R);

　　其中:D中有一個(gè)根,把D和出度去掉,可以分成M個(gè)部分.
　　D1,D2,D3,D4,D5…DM
　　R1,R2,R3,R4,R5…RM
　　而子樹Ri形成樹.
　　1) 遞歸定義 高度

　　2.二叉樹定義:   

　　結(jié)點(diǎn)個(gè)數(shù)>=0 .

　　3. 術(shù)語(yǔ):左右孩子,雙親,子樹,度,高度等概念.

　　4. 二叉樹的性質(zhì)

　　●層次為I的二叉樹 I層結(jié)點(diǎn) 2^I 個(gè)
　　●高度為H的二叉樹結(jié)點(diǎn) 2^H+1-1個(gè)
　　●H(點(diǎn))=E(邊)+1
　　●個(gè)數(shù)為N的完全二叉樹高度為|_LOG₂n_|
　　●完全二叉樹結(jié)點(diǎn)編號(hào):從上到下,從左到右.

　　二叉樹的存儲(chǔ)結(jié)構(gòu):
　　　　1) 擴(kuò)展成為完全二叉樹,以一維數(shù)組存儲(chǔ)。

　　　　2) 雙親表示法 

　　　　3) 雙親孩子表示法

　　結(jié)構(gòu):
　　　　typedef struct {
　　　　　datatype data;
　　　　　int parent;
　　　　　int lchild;
　　　　　int rchild;
　　　　}NODE;
　　　　NODE tree[N]; // 生成N個(gè)結(jié)點(diǎn)的樹
　　　　4) 二叉鏈表
　　　　5) 三叉鏈表
　　　　6) 哈夫曼樹
　　5.二叉樹的遍歷
　　　先根 \
　　　中根 棧 中根遍歷(左子樹)根(右子樹),再用相同的方法處理左子樹,右子樹.
　　　后根 /
　　　先,中序已知求樹:先序找根,中序找確定左右子樹.
　　　層次遍歷(隊(duì)列實(shí)現(xiàn))
　　6.線索二叉樹(穿線樹)
　　　中序線索二樹樹目的:利用空指針直接得到中序遍歷的結(jié)果.
　　　手段(方法):左指針為空,指向前趨,右指針為空,指向后繼.
　　結(jié)點(diǎn)結(jié)構(gòu):

　　Ltag=0,lch指向左孩子,ltag=1,指向前趨結(jié)點(diǎn)
　　Rtag=0,rch指向右孩子;rtag=1,指向后繼結(jié)點(diǎn)
　　中序遍歷: 1) 找最左結(jié)點(diǎn)(其左指針為空)
　　　　2) 當(dāng)該結(jié)點(diǎn)的rtag=1,該結(jié)點(diǎn)的rch指向的就為后繼
　　　　3) 當(dāng)rtag=0,后繼元素為右子樹中最左邊那個(gè)
　　N個(gè)結(jié)點(diǎn)的二樹有空指針N+1個(gè) 

上一頁(yè)  [1] [2] [3] [4] [5] [6] [7] [8] [9] 下一頁(yè)