第二章游戲中數(shù)據(jù)結(jié)構(gòu)與算法第一節(jié)分析線性

算法分析與線性數(shù)據(jù)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)、順序棧、鏈棧順序表的鏈?zhǔn)酱鎯?chǔ)—鏈表?xiàng)＝Y(jié)構(gòu)的順序存儲(chǔ)棧結(jié)構(gòu)的鏈?zhǔn)酱鎯?chǔ)了解線性表的含義，通過指針的方式生成鏈表的基本操作。掌握棧結(jié)構(gòu)的順序存儲(chǔ)掌握棧結(jié)構(gòu)的鏈?zhǔn)酱鎯?chǔ)1鏈表主要的優(yōu)點(diǎn)就是可以方便的進(jìn)行插入、刪除操作，利用這一優(yōu)點(diǎn)，可以在游戲設(shè)計(jì)過程中方便地管理大量的數(shù)據(jù)。在鏈表中的每個(gè)元素都放在節(jié)點(diǎn)中進(jìn)行描述。節(jié)點(diǎn)不必是連續(xù)的物理單元。每個(gè)節(jié)點(diǎn)中都包含了與該節(jié)點(diǎn)相關(guān)的其他節(jié)點(diǎn)的位置信息。這種關(guān)于其他節(jié)點(diǎn)的位置信息被稱之為鏈或指針。鏈表概念3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.8：線性表的鏈?zhǔn)酱鎯?chǔ)2該圖的鏈表結(jié)構(gòu)被稱之為單向鏈表,每個(gè)鏈表節(jié)點(diǎn)都正好有一個(gè)鏈接域。第一個(gè)節(jié)點(diǎn)e1的指針指向第二個(gè)節(jié)點(diǎn)e2，e2的指針指向下一個(gè)節(jié)點(diǎn)，最后一個(gè)節(jié)點(diǎn)鏈接域?yàn)镹ULL（或0），故這種結(jié)構(gòu)也被稱作鏈。3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.8：線性表的鏈?zhǔn)酱鎯?chǔ)3鏈表操作structNode{ intm_Data; Node*m_pNextNode;};classList{public: List(){m_pFirstNode=NULL;} ~List(); boolIsEmpty()const{returnm_pFirstNode==NULL;} intLength()const; boolFind(intk,int&x); intSearch(constint&x)const; List&Delete(intk,int&x); List&Insert(intk,constint&x); voidOutput(std::ostream&out)const;private: Node*m_pFirstNode;};3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.8：線性表的鏈?zhǔn)酱鎯?chǔ)4boolGameCollege::List::Find(intk,int&x){ if(k<1) returnfalse; Node*current=m_pFirstNode; intindex=1; while(index<k&¤t){ current=current->m_pNextNode; index++; } if(current){ x=current->m_Data; returntrue; } returnfalse;//不存在第k個(gè)元素}1）鏈表中的查詢。3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.8：線性表的鏈?zhǔn)酱鎯?chǔ)5intGameCollege::List::Search(constint&x)const{ Node*current=m_pFirstNode; intindex=1;//current的索引 while(current&¤t->m_Data!=x) { current=current->m_pNextNode; index++; } if(current) returnindex;

return0;}Search函數(shù)通過用戶傳入x對(duì)象，遍歷鏈表找出和x對(duì)象相同的元素，返回該元素所在的位置。3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.8：線性表的鏈?zhǔn)酱鎯?chǔ)6如果被刪除節(jié)點(diǎn)是第一個(gè)節(jié)點(diǎn)。這種情況只需使head指向第二個(gè)節(jié)點(diǎn)即可。當(dāng)把這個(gè)節(jié)點(diǎn)移出之后，這個(gè)節(jié)點(diǎn)就可以釋放了。3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.8：線性表的鏈?zhǔn)酱鎯?chǔ)7GameCollege::List&GameCollege::List::Delete(intk,int&x){ if(k<1||!m_pFirstNode)//不存在第k個(gè)元素 throw"此元素不存在"; Node*deleteNode=m_pFirstNode;

if(k==1)//要?jiǎng)h除的是第一個(gè)元素 m_pFirstNode=m_pFirstNode->m_pNextNode;//刪除掉 else { Node*perNode=m_pFirstNode; for(intindex=1;index<k-1&&perNode;index++) perNode=perNode->m_pNextNode; //用perNode指向第k-1個(gè)元素if(!perNode||!perNode->m_pNextNode) throw"此元素不存在";//不存在第k個(gè)元素

deleteNode=perNode->m_pNextNode;//存在第k個(gè)元素 perNode->m_pNextNode=deleteNode->m_pNextNode;

} x=deleteNode->m_Data; deletedeleteNode; return*this;}3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.8：線性表的鏈?zhǔn)酱鎯?chǔ)83）向鏈表中插入元素以下4種不同情況下插入節(jié)點(diǎn)：1）原表是空表，只需使head指向被插節(jié)點(diǎn)即可。3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.8：線性表的鏈?zhǔn)酱鎯?chǔ)92）被插節(jié)點(diǎn)值最小，應(yīng)插入在第一節(jié)點(diǎn)之前。3）在其他位置插入。3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.8：線性表的鏈?zhǔn)酱鎯?chǔ)104）在表末插入。這種情況下使原表末節(jié)點(diǎn)指針域指向被插節(jié)點(diǎn)，被插節(jié)點(diǎn)指針域置為NULL。3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.8：線性表的鏈?zhǔn)酱鎯?chǔ)11GameCollege::List&GameCollege::List::Insert(intk,constint&x){ if(k<0) throw"錯(cuò)誤的插入位置！"; Node*insertNode=m_pFirstNode;

//將insertNode移動(dòng)至第k個(gè)元素 for(intindex=1;index<k&&insertNode;index++) insertNode=insertNode->m_pNextNode;

if(k>0&&!insertNode) throw"此元素不存在！";//不存在第k個(gè)元素 //插入元素 Node*newNode=newNode; newNode->m_Data=x; if(k) {//在insertNode之后插入 newNode->m_pNextNode=insertNode->m_pNextNode; insertNode->m_pNextNode=newNode; } else {//作為第一個(gè)元素插入 newNode->m_pNextNode=m_pFirstNode; m_pFirstNode=newNode; } return*this;}3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.8：線性表的鏈?zhǔn)酱鎯?chǔ)12棧是一種只允許在一端進(jìn)行插入和刪除的線性表，它是一種操作受限的線性表。在表中只允許進(jìn)行插入和刪除的一端稱為棧頂，另一端稱為棧底。棧的插入操作通常稱為入棧或進(jìn)棧，而棧的刪除操作則稱為出棧或退棧。當(dāng)棧中沒有數(shù)據(jù)元素時(shí)，稱為空棧。3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.9：棧的順序存儲(chǔ)13棧通常用指針top指示棧頂?shù)奈恢?，用指針bottom指向棧底。棧頂指針top動(dòng)態(tài)反映棧的當(dāng)前位置。入棧時(shí)，新加入的元素變成新的棧頂，棧頂指針top指向新加入的元素；出棧時(shí)，它指向出棧元素的下一個(gè)元素，即新的棧頂3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.9：棧的順序存儲(chǔ)14棧的基本運(yùn)算棧的基本運(yùn)算包括以下6種：1）StackFull判斷是否棧滿；2）Empty()棧的空判斷：若棧為空，則返回TRUE；否則，返回FALSE；3）Push(x)入棧：在棧的頂部插入元素x，若棧滿，則返回FALSE；否則，返回TRUE；4）Pop()出棧：若棧不空，則返回棧頂元素，并從棧頂中刪除該元素；否則，返回空元素NULL；5）GetTop()取棧元素：若棧不空，則返回棧頂元素；否則返回空元素NULL；6）SetEmpty()置?？詹僮鳎褐脳榭諚！?.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.9：棧的順序存儲(chǔ)15constunsignedSTACKSIZE=10;//定義棧的最大容量classStack{ unsignedm_nTop;

intm_StackData[STACKSIZE];public: Stack():m_nTop(0){} boolEmpty()const;//判斷棧是否為空 boolStackFull()const;//判斷棧是否滿 voidPush(intdata);//將data數(shù)據(jù)壓入棧中 intPop();//將棧頂數(shù)據(jù)彈出 intGetTop()const;//獲取棧頂數(shù)據(jù) voidSetEmpty();//將棧設(shè)為空};順序棧3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.9：棧的順序存儲(chǔ)161）Push(x)入棧voidGameCollege::Stack::Push(intdata){ if(StackFull()) { Exceptione("棧已經(jīng)滿，無法進(jìn)行壓入操作"); throwe; }

m_StackData[m_nTop++]=data;//將數(shù)據(jù)壓入棧中}m_nTop用來表示棧頂位置，它對(duì)應(yīng)m_StackData數(shù)組單元的位置，當(dāng)有數(shù)據(jù)需要壓入棧中，只要通過m_nTop找到m_StackData數(shù)組相對(duì)應(yīng)的單元，然后將數(shù)據(jù)寫入此單元3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.9：棧的順序存儲(chǔ)172）Pop()出棧intGameCollege::Stack::Pop(){ if(Empty()) { Exceptione("棧已空，無法進(jìn)行出棧操作"); throwe; } returnm_StackData[--m_nTop];}3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.9：棧的順序存儲(chǔ)183）StackFull判斷是否棧滿boolGameCollege::Stack::StackFull()const{ returnm_nTop==STACKSIZE;}4）Empty()空棧判斷。boolGameCollege::Stack::Empty()const{ returnm_nTop==0;}3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.9：棧的順序存儲(chǔ)195）SetEmpty()設(shè)置棧為空voidGameCollege::Stack::SetEmpty(){ m_nTop=0;}6）GetTop()取棧頂元素intGameCollege::Stack::GetTop()const{ if(Empty()){ Exceptione("棧為空"); throwe; }

returnm_StackData[m_nTop-1];}3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.9：棧的順序存儲(chǔ)20structNode{ intnData; Node*pNextNode;};classStack{public: Stack(); ~Stack(); voidPush(intdata); intPop(); boolEmpty(); voidSetEmpty(); intGetTop()const;private: voidClearStack(); Node*m_pTop;};3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.10：棧的鏈?zhǔn)酱鎯?chǔ)21voidGameCollege::Stack::Push(intdata){ Node*pNewNode=newNode; if(!pNewNode){ Exceptione("內(nèi)存分配失??！"); throwe; }

pNewNode->nData=data; pNewNode->pNextNode=NULL; if(!m_pTop){ m_pTop=pNewNode; } else{ pNewNode->pNextNode=m_pTop; m_pTop=pNewNode; }}1）Push(x)入棧。3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.10：棧的鏈?zhǔn)酱鎯?chǔ)222）Pop()出棧intGameCollege::Stack::Pop(){ if(!m_pTop){ Exceptione("棧為空，無法完成彈出操作！"); throwe; } Node*tempNode=m_pTop; m_pTop=m_pTop->pNextNode; intdata=tempNode->nData; deletetempNode; returndata;}3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.10：棧的鏈?zhǔn)酱鎯?chǔ)233）Empty()空棧判斷boolGameCollege::Stack::Empty(){ if(!m_pTop) { returntrue; } else { returnfalse; }}3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.10：棧的鏈?zhǔn)酱鎯?chǔ)244）SetEmpty()設(shè)置棧為空voidGameCollege::Stack::SetEmpty(){ ClearStack(); }voidGameCollege::Stack::ClearStack(){ if(m_pTop){ Node*tempNode=m_pTop; while(m_pTop){ m_pTop=m_pTop->pNextNode; deletetempNode; tempNode=m_pTop; } m_pTop=NULL; }}3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.10：棧的鏈?zhǔn)酱鎯?chǔ)25intGameCollege::Stack::GetTop()const{ if(!m_pTop) { Exceptione("棧為空，無法獲取棧頂數(shù)據(jù)！"); throwe; }

returnm_pTop->nData;}5）GetTop()取棧頂元素3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.10：棧的鏈?zhǔn)酱鎯?chǔ)26迷宮問題的實(shí)現(xiàn)在迷宮中行進(jìn)時(shí)必須遵守以下3個(gè)原則：1）一次只能走一格；2）遇到墻無法往前走時(shí)則退回一步，看一下是否有其他的路可以走；3）走過的路不會(huì)再走第二次。走迷宮是棧在實(shí)際應(yīng)用上的一個(gè)很好的例子。在迷宮出口路徑的搜索過程中，程序必須判斷下一步該往哪一個(gè)方向移動(dòng)，此外還必須記錄走過的迷宮路徑，如此才可以在走迷宮中死路時(shí)回頭來搜索其他的路徑。3.1算法分析與數(shù)據(jù)結(jié)構(gòu)3.1.11：棧的應(yīng)用27用二維數(shù)組MAZE[row][col]來表現(xiàn)一個(gè)模擬迷宮1）MAZE[i][j]=1表示[i][j]處有墻，無法通過；2）MAZE[i][j]=0表示[i][j]處無墻，