【正文】 中的元素，就能實現(xiàn)插入和刪除操作。 單鏈表基本算法 newnode infox info0 info1 即： newnode→ link=head； //注意：鏈表操作次序非常重要 head=newnode； 單鏈表基本算法 infox infoi1 infoi p ｑ newnode 插在中間： 首先用工作指針 p找到指定結(jié)點 ， 而讓指針 q指向緊跟其后的結(jié)點 ， 令 infoi1所在結(jié)點的 link指針指向新結(jié)點 ， 而后讓新結(jié)點的 link指向 infoi所在結(jié)點 。 單鏈表基本算法 帶表頭結(jié)構(gòu)的鏈表： 研究以上算法 ， 插在鏈表第一個結(jié)點之前與其他結(jié)點之前的算法有所不同 。 空表如下： head info0 Infon1 ^ info1 … head ^ 下面分別介紹 帶表頭結(jié)構(gòu) 的鏈表的生成鏈表算法、鏈表查找算法、插入一個結(jié)點的算法和刪除一個結(jié)點的算法。 Node*head,*tail,*p。 //建立鏈表頭結(jié)點 tail=head。 //每輸入一個數(shù)申請一個結(jié)點 pinfo=data。 //新結(jié)點接到鏈尾 tail=p。 //鏈尾加空指針 ， 表示鏈結(jié)束 return head。 Datatype data。 //建立頭結(jié)點 headlink=NULL。 pinfo=data。 //新結(jié)點放在原鏈表前方 headlink=p。} 單鏈表基本算法 (按關(guān)鍵字 )查找： node *traversal(node *head,Datatype data){ node *p=headlink。amp。 return p。 4. 在單鏈表的 p節(jié)點后插入 ： 注意只有一種情況。 qinfo=x。 plink=q。 q=plink。 delete q。 } 單鏈表類型模板 【 例 】 單鏈表類模板 。 templatetypename Tclass Node{ T info。 //指針域，注意結(jié)點類格式，尖括號中是參數(shù)名表，類模板實例化為類 public: Node()。 data)。 //在當(dāng)前 結(jié)點后插入 一個結(jié)點 NodeT* RemoveAfter()。 //以 List為友元類， List可直接訪問 Node的私有函數(shù) }。 //鏈表頭指針和尾指針 public: List()。 //析構(gòu)函數(shù) void MakeEmpty()。 //搜索 數(shù)據(jù)域與 data相同的結(jié)點，返回該結(jié)點的地址 int Length()。 //打印鏈表 的數(shù)據(jù)域 void InsertFront(NodeT* p)。 //可用來 向后生成鏈表 void InsertOrder(NodeT *p)。 //創(chuàng)建結(jié)點 (孤立結(jié)點 ) NodeT*DeleteNode(NodeT* p)。 //刪除指定結(jié)點 單鏈表類型模板 單鏈表類型模板 【 例 】 由鍵盤輸入 16個整數(shù) ， 以這些整數(shù)作為結(jié)點數(shù)據(jù) ， 生成兩個鏈表 ， 一個向前生成 ， 一個向后生成 ， 輸出兩個表 。 清空該表 ， 再按升序生成鏈表并輸出 。 【 例 】 以學(xué)生類作為鏈表的數(shù)據(jù)類，完成學(xué)生檔案的管理。 定義復(fù)制構(gòu)造函數(shù)與類的實際意義和使用方式有關(guān)，并非只是深復(fù)制和淺復(fù)制的問題 。 node){ info=。 } link域值為 NULL?？紤]到函數(shù)的參數(shù)和返回值僅使用指向 Node的指針，定義復(fù)制構(gòu)造函數(shù)已經(jīng)沒有實際意義 單鏈表的復(fù)制構(gòu)造函數(shù)和復(fù)制運算符是一個復(fù)雜的算法，與前文所編的復(fù)制構(gòu)造函數(shù)和復(fù)制運算符構(gòu)造相去甚遠了。如要找前驅(qū)，必須從表頭開始搜索。雙向鏈表的 結(jié)點有三個域 ： 左鏈接指針 （ llink)，數(shù)據(jù)域（ info)， 右鏈接指針域 (rlink)。 info0 infon1 .’.’.’.’.’.’ info1 head (a) 非空表 head (b)空表 雙向鏈表（選讀） 雙向鏈表的訪問： 假設(shè)指針 p指向雙向循環(huán)鏈表的某一個結(jié)點，那么， pllink指示 P所指結(jié)點的 前驅(qū)結(jié)點 ， prlink指示 后繼結(jié)點。 p llink rlink rlink llink rlink 前驅(qū)結(jié)點 llink 本結(jié)點 后繼結(jié)點 間接訪問符的使用 【 例 】 雙向鏈表類模板和結(jié)點類模板。 7. 3. 1 棧 7. 3. 3 隊 列 7. 3. 2 棧的應(yīng)用（選讀） 棧 棧的基本概念： 棧定義為只允許在表的一端進行插入和刪除的線性表 。 棧中沒有任何元素時，稱為空棧。而出棧時順序相反，最后進棧的最先出棧，而最先進棧的 a0最后出棧。 ?？梢杂庙樞虮韺崿F(xiàn)，稱 順序 棧；也可以用鏈表實現(xiàn)，稱 鏈棧 。進棧時最先進棧的 a0在最下面， an1在最上面。 a0 an2 …… a1 an1 bottom 進棧 top top top top top 出棧 圖示為順序棧。通常只有棧頂與操作有關(guān)。 //棧頂指針（下標(biāo)） T *elements。 //棧最大容納的元素個數(shù) public: Stack(int=20)。} void Push(const T amp。 //壓棧 T Pop()。 //取數(shù)據(jù) ， top不變 void MakeEmpty(){top= 1。} //判?？? bool IsFull() const{return top==maxSize1。 }。 Stackint istack(10)。i10。 if(()) cout棧滿 endl。 for(i=0。i++) b[i]=()。 for(i=0。i++) coutb[i]39。 //注意先進后出 coutendl。 //下溢出 } 棧 【 例 】 鏈棧的 結(jié)點 類模板： templatetypename Tclass Node{ //鏈棧結(jié)點類模板 T info。 public: Node(T data=0,NodeT *next=NULL){ info=data。 } friend class StackT。 top …… ^ …… 鏈棧 棧 鏈棧類模板 (無頭結(jié)點鏈表 )： templatetypename Tclass Stack{ //鏈棧類模板 NodeT *top。} ~Stack()。data)。 //彈出 T GetTop()。 //清空棧 bool IsEmpty(){return top==NULL。 棧的應(yīng)用（選讀） 順序棧和鏈棧邏輯功能是一樣，盡管這里兩個棧模板的成員函數(shù)功能選擇稍有出入，因為 順序?？梢噪S機訪問其中的元素 ， 而鏈棧只能順序訪問， 但邏輯上完全可以做到一樣（物理結(jié)構(gòu)不同） 。 鏈棧內(nèi)存空間隨用隨開，不會溢出，但執(zhí)行復(fù)雜（不斷地動態(tài)分配），速度慢。現(xiàn)考慮最簡單的 +、 、 *、 /四個運算符和結(jié)束符＝組成的算術(shù)表達式，只有 兩個優(yōu)先級 ，先 */，后 +。數(shù)棧暫存操作數(shù)，運算符棧暫存運算符。 從左向右掃描算術(shù)表達式 ，遇到 操作數(shù) ， 壓入數(shù)棧 ；遇到 運算符 ，則 與運算符棧棧頂?shù)倪\算符比較優(yōu)先級 ，若新的運算符優(yōu)先級高，或運算符?？眨瑒t壓棧。繼續(xù)掃描，直到遇到＝號，掃描結(jié)束。 棧的應(yīng)用（選讀） 【 例 】 模擬簡單計算器 ， 該計算器只認 + * / 四個運算符 ，輸入為整數(shù) 。 使用 ‘ z’字符表示結(jié)束 。 //使用鏈棧 Stackchar Ostack。 void Cal(void)。Num1,int amp。 //取數(shù) void Compute(char Opr)。 }。它 只允許在表的一端插入，而在另一端刪除 。每次在隊尾加入新元素，加入稱為 進隊 ，刪除稱為 出隊 。 a0 a1 a2 … an1 … front 元素移動 方向 rear 圖 圖 ，隊尾 (rear)不斷向后移；而隨隊頭元素的出隊，則隊頭 (front)也不斷后移，即 位置在變 （如要位置不變， 移動元素 工作量也太大）。 順序表隊列的缺點： 隊列 順序表隊列的改進： 邏輯上的循環(huán)隊列 注意，空隊時 rear=front，滿隊時必須空一個位置 隊列 循環(huán)隊列 浪費一個位置好像太可惜，特別在該位置中存放一個很大的對象時。若想利用這個空間，必然加一個標(biāo)志來表示隊空 /隊滿，進隊出隊都要判斷，使用上更不方便。 【 例 】 鏈隊類模板。無鏈表頭結(jié)點方式。 二叉樹的遍歷 二叉樹的概念 排序二叉樹 二叉樹的概念 （選讀） 樹（ Tree） 是由 n（ n≥0）個結(jié)點組成的有限集合。非空樹有一個特定的結(jié)點，它只有直接后繼，沒有直接前驅(qū)，稱之為根（ root）。每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但可以有 0個或多個直接后繼。 樹的概念： 二叉樹的概念（選讀） A B C D E F G I H J L K O N M ………… 0層 …… 1層 2層 3層 深度 圖 樹的示意圖 結(jié)點 ， 包括數(shù)據(jù)項和多個指針項 ， 指針項數(shù)目并不固定 ， 且無次序 。 葉結(jié)點 ， 度為 0的結(jié)點 ，如 G， I， J， K， L，M， N， O結(jié)點 。 孩子結(jié)點 ， 若結(jié)點 x有子樹 ， 則子樹根結(jié)點即為 x的孩子結(jié)點 。 兄弟結(jié)點 ， 同一雙親的結(jié)點互稱為兄弟 。 樹的深度 ,樹中結(jié)點的層次數(shù) 。 樹的術(shù)語： 二叉樹的概念（選讀） 二叉樹 （ Binary Tree） 是另一種獨立的樹形結(jié)構(gòu) 。 這也是一個遞歸的定義 。 二叉樹的基本性質(zhì)： 1．二叉樹的第 i層上最多有 2i1(i=1)個結(jié)點； 2．深度為 h的二叉樹中最多有 2h1個結(jié)點； 3．在任一棵二叉樹中，有 n0個葉子結(jié)點，有 n2個度為 2的 結(jié)點，則有 n0=n2+1。 解：結(jié)果見圖 ， 共 5種 。 1 2 3 4 5 6 7 9 8 10 11 14 13 12 15 圖 滿二叉樹 1 2 3 4 5 6 7 9 8 10 圖 完全二叉樹 二叉樹的概念（選讀） 下面給出鏈式儲存方式的二叉樹。 lchild rchild info 圖 二叉樹結(jié)點 二叉樹的概念（選讀） 二叉樹類結(jié)點類模板定義： templatetypename Tclass BinaryTree。 T info。 rchild=NULL。 lchild=left。 } 二叉樹的概念（選讀） T Getinfo(){return info。data){info=data。} //取得左子樹 NodeT *Getright(){return rchild。} //設(shè)置左指針 void setrightNodeT *right){rchild=right。 //二叉樹類說明為友元類 } 二叉樹的遍歷（選讀） 二叉樹的遍歷 (binary tree traversal)： 遵從某種次序 ， 查巡二叉樹的所有結(jié)點 ， 每個結(jié)點都被訪問一次 ， 而且僅訪問一次 。 遍歷二叉樹有不同次序，規(guī)定先左后右，令 L， R， V分別代表遍歷一個結(jié)點的左右子樹和訪問該結(jié)點的操作，有三種方式： 前序遍歷（ VLR） 中序遍歷（ LVR） 后序遍歷（ LRV） 二叉樹的遍歷（選讀） 遍歷實 例： 前序遍歷訪問次序為 ABDEGCFH。 后序遍歷結(jié)果為