第一章 緒論
1-教學(xué)安排
略
2-數(shù)據(jù)結(jié)構(gòu)基本概念课舍，術(shù)語(yǔ)與主要學(xué)習(xí)內(nèi)容
1-數(shù)據(jù)結(jié)構(gòu)主要內(nèi)容
????在計(jì)算機(jī)學(xué)科中，學(xué)習(xí)程序語(yǔ)言之后就要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法內(nèi)容他挎。
1筝尾、為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法？它和計(jì)算機(jī)有什么關(guān)系办桨？
????計(jì)算機(jī)除去硬件以外筹淫，還需要有軟件，用來(lái)豐富計(jì)算機(jī)的功能呢撞。軟件就是程序+文檔構(gòu)成： 程序＝算法+數(shù)據(jù)結(jié)構(gòu)损姜，算法=邏輯+控制；
【例1】 迷宮：字符界面殊霞、圖形界面摧阅、迷宮游戲
????這些迷宮形式不同，但是本質(zhì)相同
需要解決下面的幾個(gè)問題：
①輸入是什么：迷宮地圖绷蹲、入口與出口
②輸出是什么：入口到出口的路徑
③輸入如何轉(zhuǎn)換為輸出：在已知迷宮地圖尋找入口到出口路徑的方法（算法）
要解決的問題1：迷宮地圖【數(shù)據(jù)結(jié)構(gòu)選擇與設(shè)計(jì)】
如何表示給定的空間和可行的路徑棒卷？（迷宮表示）
如何表示入口與出口顾孽？
????可以用一個(gè)m行n列的二維數(shù)組maze[m][n]來(lái)表示迷宮空間，并約定：
????當(dāng)數(shù)組元素maze[i][j]=0比规，表示通路若厚；maze[i][j]=1，表示不通蜒什。
要解決的問題2：尋路過程【算法設(shè)計(jì)】
當(dāng)有多條可行路徑時(shí)如何選擇测秸？
當(dāng)某條路徑在某一點(diǎn)沒有可行之路時(shí)如何處理？
某點(diǎn)會(huì)重復(fù)經(jīng)過嗎（避免兜圈子）吃谣？
多條可行路：
????在某一點(diǎn)（x乞封，y）做裙，有8個(gè)可以探索的方向：
????假設(shè)：從正東方向開始岗憋，沿順時(shí)針方向依次進(jìn)行探索，將探索方向存儲(chǔ)在增量數(shù)組DeltaXY中：
Problem：角點(diǎn)锚贱、邊點(diǎn)和中間點(diǎn)探測(cè)的判斷方法是一致的嗎仔戈？
答：角點(diǎn)和邊點(diǎn)都要考慮邊界的問題，沒有八個(gè)方向拧廊，因此要對(duì)三者的探測(cè)方法進(jìn)行一致性處理监徘，也就是迷宮地圖簡(jiǎn)化，在迷宮四周都擴(kuò)展一個(gè)點(diǎn)吧碾，增加兩行兩列凰盔，并全部設(shè)置為1，表示是墻不能通行倦春。這樣所有點(diǎn)都成為中間點(diǎn)户敬，不用再判斷當(dāng)前點(diǎn)是角點(diǎn)、邊點(diǎn)還是中間點(diǎn)睁本，每個(gè)點(diǎn)的探索方向均為8個(gè)尿庐。
死路退回：
????回退到上一個(gè)有多條路徑的地方選擇下一條路徑探測(cè)；
????需要存儲(chǔ)每一個(gè)局有多條路徑的點(diǎn)坐標(biāo)和探索方向（x呢堰，y抄瑟，d）【x代表橫坐標(biāo)，y代表縱坐標(biāo)枉疼，d取值0~7代表方向】皮假；
????存儲(chǔ)的多個(gè)（x，y骂维，d）選擇最新存儲(chǔ)位置回退——棧
兜死圈子：
????兩種方法：
????1.設(shè)置一個(gè)標(biāo)志數(shù)組mark[m][n]钞翔，所有元素初始化為0；
????在探索中席舍，當(dāng)所探索的點(diǎn)（i布轿，j）對(duì)應(yīng)的mark[i][j]=0時(shí)，才進(jìn)入該點(diǎn)，并將mark[i][j]設(shè)置為1汰扭；當(dāng)所探索的點(diǎn)（i稠肘，j）對(duì)應(yīng)的mark[i][j]=1時(shí)，表明已經(jīng)探索過萝毛，不需要再進(jìn)入项阴。
????2.當(dāng)?shù)竭_(dá)某點(diǎn)（i，j）后笆包，在迷宮地圖的該點(diǎn)坐標(biāo)上標(biāo)記特殊值环揽，例如把maze[i][j]設(shè)置為-1，以便區(qū)分沒有到達(dá)過的點(diǎn)庵佣。
小結(jié)：
1.二維數(shù)組maze[m+2][n+2]來(lái)表示迷宮歉胶，解決迷宮地圖的存儲(chǔ)；
2.一維數(shù)組DeltaXY[8]來(lái)記載8個(gè)探索方向的坐標(biāo)增量巴粪，將8個(gè)探索方向數(shù)字化為0到7通今，并將向下一點(diǎn)前進(jìn)的操作統(tǒng)一為當(dāng)前點(diǎn)的坐標(biāo)+沿該探索方向的增量，即可得到下一點(diǎn)的坐標(biāo)肛根；
3.當(dāng)某點(diǎn)無(wú)路通行時(shí)辫塌，需要從該點(diǎn)返回到前一點(diǎn)，再?gòu)那耙稽c(diǎn)選擇下一個(gè)方向繼續(xù)進(jìn)行探索派哲，即需要知道前一點(diǎn)和前一點(diǎn)當(dāng)前探索的方向臼氨。因此，我們需要保留依次到達(dá)各點(diǎn)的坐標(biāo)和到達(dá)該點(diǎn)的方向芭届；
4.需要防止重復(fù)到達(dá)某點(diǎn)储矩，避免在迷宮中兜死圈子，需要記載已經(jīng)到達(dá)過的點(diǎn)喉脖。
本節(jié)小結(jié)：
數(shù)據(jù)結(jié)構(gòu)有兩大用途：
一是用于存放要處理的數(shù)據(jù)椰苟，如迷宮地圖；
二是用于實(shí)現(xiàn)算法策略树叽，如迷宮例子中探索方向增量數(shù)組舆蝴、回溯的棧、避免重復(fù)走的標(biāo)志數(shù)組或特殊標(biāo)記题诵。
