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

算法分析與線性數(shù)據(jù)結構線性表的鏈式存儲、順序棧、鏈棧順序表的鏈式存儲—鏈表棧結構的順序存儲棧結構的鏈式存儲了解線性表的含義，通過指針的方式生成鏈表的基本操作。掌握棧結構的順序存儲掌握棧結構的鏈式存儲1鏈表主要的優(yōu)點就是可以方便的進行插入、刪除操作，利用這一優(yōu)點，可以在游戲設計過程中方便地管理大量的數(shù)據(jù)。在鏈表中的每個元素都放在節(jié)點中進行描述。節(jié)點不必是連續(xù)的物理單元。每個節(jié)點中都包含了與該節(jié)點相關的其他節(jié)點的位置信息。這種關于其他節(jié)點的位置信息被稱之為鏈或指針。鏈表概念3.1算法分析與數(shù)據(jù)結構3.1.8：線性表的鏈式存儲2該圖的鏈表結構被稱之為單向鏈表,每個鏈表節(jié)點都正好有一個鏈接域。第一個節(jié)點e1的指針指向第二個節(jié)點e2，e2的指針指向下一個節(jié)點，最后一個節(jié)點鏈接域為NULL（或0），故這種結構也被稱作鏈。3.1算法分析與數(shù)據(jù)結構3.1.8：線性表的鏈式存儲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ù)結構3.1.8：線性表的鏈式存儲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個元素}1）鏈表中的查詢。3.1算法分析與數(shù)據(jù)結構3.1.8：線性表的鏈式存儲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對象，遍歷鏈表找出和x對象相同的元素，返回該元素所在的位置。3.1算法分析與數(shù)據(jù)結構3.1.8：線性表的鏈式存儲6如果被刪除節(jié)點是第一個節(jié)點。這種情況只需使head指向第二個節(jié)點即可。當把這個節(jié)點移出之后，這個節(jié)點就可以釋放了。3.1算法分析與數(shù)據(jù)結構3.1.8：線性表的鏈式存儲7GameCollege::List&GameCollege::List::Delete(intk,int&x){ if(k<1||!m_pFirstNode)//不存在第k個元素 throw"此元素不存在"; Node*deleteNode=m_pFirstNode;

if(k==1)//要刪除的是第一個元素 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個元素if(!perNode||!perNode->m_pNextNode) throw"此元素不存在";//不存在第k個元素

deleteNode=perNode->m_pNextNode;//存在第k個元素 perNode->m_pNextNode=deleteNode->m_pNextNode;

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

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

if(k>0&&!insertNode) throw"此元素不存在！";//不存在第k個元素 //插入元素 Node*newNode=newNode; newNode->m_Data=x; if(k) {//在insertNode之后插入 newNode->m_pNextNode=insertNode->m_pNextNode; insertNode->m_pNextNode=newNode; } else {//作為第一個元素插入 newNode->m_pNextNode=m_pFirstNode; m_pFirstNode=newNode; } return*this;}3.1算法分析與數(shù)據(jù)結構3.1.8：線性表的鏈式存儲12棧是一種只允許在一端進行插入和刪除的線性表，它是一種操作受限的線性表。在表中只允許進行插入和刪除的一端稱為棧頂，另一端稱為棧底。棧的插入操作通常稱為入?；蜻M棧，而棧的刪除操作則稱為出?；蛲藯?。當棧中沒有數(shù)據(jù)元素時，稱為空棧。3.1算法分析與數(shù)據(jù)結構3.1.9：棧的順序存儲13棧通常用指針top指示棧頂?shù)奈恢?，用指針bottom指向棧底。棧頂指針top動態(tài)反映棧的當前位置。入棧時，新加入的元素變成新的棧頂，棧頂指針top指向新加入的元素；出棧時，它指向出棧元素的下一個元素，即新的棧頂3.1算法分析與數(shù)據(jù)結構3.1.9：棧的順序存儲14棧的基本運算棧的基本運算包括以下6種：1）StackFull判斷是否棧滿；2）Empty()棧的空判斷：若棧為空，則返回TRUE；否則，返回FALSE；3）Push(x)入棧：在棧的頂部插入元素x，若棧滿，則返回FALSE；否則，返回TRUE；4）Pop()出棧：若棧不空，則返回棧頂元素，并從棧頂中刪除該元素；否則，返回空元素NULL；5）GetTop()取棧元素：若棧不空，則返回棧頂元素；否則返回空元素NULL；6）SetEmpty()置?？詹僮鳎褐脳榭諚?。3.1算法分析與數(shù)據(jù)結構3.1.9：棧的順序存儲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();//將棧設為空};順序棧3.1算法分析與數(shù)據(jù)結構3.1.9：棧的順序存儲161）Push(x)入棧voidGameCollege::Stack::Push(intdata){ if(StackFull()) { Exceptione("棧已經(jīng)滿，無法進行壓入操作"); throwe; }

m_StackData[m_nTop++]=data;//將數(shù)據(jù)壓入棧中}m_nTop用來表示棧頂位置，它對應m_StackData數(shù)組單元的位置，當有數(shù)據(jù)需要壓入棧中，只要通過m_nTop找到m_StackData數(shù)組相對應的單元，然后將數(shù)據(jù)寫入此單元3.1算法分析與數(shù)據(jù)結構3.1.9：棧的順序存儲172）Pop()出棧intGameCollege::Stack::Pop(){ if(Empty()) { Exceptione("棧已空，無法進行出棧操作"); throwe; } returnm_StackData[--m_nTop];}3.1算法分析與數(shù)據(jù)結構3.1.9：棧的順序存儲183）StackFull判斷是否棧滿boolGameCollege::Stack::StackFull()const{ returnm_nTop==STACKSIZE;}4）Empty()空棧判斷。boolGameCollege::Stack::Empty()const{ returnm_nTop==0;}3.1算法分析與數(shù)據(jù)結構3.1.9：棧的順序存儲195）SetEmpty()設置棧為空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ù)結構3.1.9：棧的順序存儲20structNode{ intnData; Node*pNextNode;};classStack{public: Stack(); ~Stack(); voidPush(intdata); intPop(); boolEmpty(); voidSetEmpty(); intGetTop()const;private: voidClearStack(); Node*m_pTop;};3.1算法分析與數(shù)據(jù)結構3.1.10：棧的鏈式存儲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ù)結構3.1.10：棧的鏈式存儲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ù)結構3.1.10：棧的鏈式存儲233）Empty()空棧判斷boolGameCollege::Stack::Empty(){ if(!m_pTop) { returntrue; } else { returnfalse; }}3.1算法分析與數(shù)據(jù)結構3.1.10：棧的鏈式存儲244）SetEmpty()設置棧為空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ù)結構3.1.10：棧的鏈式存儲25intGameCollege::Stack::GetTop()const{ if(!m_pTop) { Exceptione("棧為空，無法獲取棧頂數(shù)據(jù)！"); throwe; }

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