【正文】 ： 每個(gè)數(shù)據(jù)元素占用一個(gè)結(jié)點(diǎn) （ Node） 。 infon1 ^ info2 info1 info0 …… head 圖 單鏈表結(jié)構(gòu) 單鏈表的第一個(gè)結(jié)點(diǎn)的地址可通過(guò)鏈表的表頭指針 head找到。 head不可丟失，否則鏈表整個(gè)丟失，內(nèi)存發(fā)生泄漏。 //數(shù)據(jù)為整型 struct node{ Datatype info。 }。 但結(jié)構(gòu)成員決不能是結(jié)構(gòu)自身類(lèi)型 ，即結(jié)構(gòu)不能自己定義自己，這會(huì)導(dǎo)致一個(gè)無(wú)窮遞歸的定義。 插入算法有 三種 情況，我們希望在單鏈表中包含數(shù)據(jù) infoi的結(jié)點(diǎn)之前插入一個(gè)新元素，則 infoi可在第一個(gè)結(jié)點(diǎn)，或在中間結(jié)點(diǎn)，如未找到，則把新結(jié)點(diǎn)插在鏈尾結(jié)點(diǎn)之后。 head head 插在鏈?zhǔn)祝? 首先新結(jié)點(diǎn)的 link指針指向 info0所在結(jié)點(diǎn) ， 然后 ， head指向新結(jié)點(diǎn) 。 即： newnode→ link=p； //或 newnode→ link=q→ link；可用于插入某結(jié)點(diǎn)之后 q→ link=newnode； 單鏈表基本算法 infox newnode p ^ infon1 ^ 插在隊(duì)尾： 只要工作指針 p找到隊(duì)尾 ， 即可鏈在其后： p→ link=newnode； =NULL。 要使算法中沒(méi)有特殊者 ， 可以給每一個(gè)鏈表加上一個(gè) 表頭結(jié)點(diǎn) ， 如下圖所示 。 單鏈表基本算法 head tail p info1 tail p info0 tail ^ 1. 向后生成鏈表算法： node *createdown(){ Datatype data。 head=new node。 while(cindata){ //Ctrl+z結(jié)束 p=new(node)。 //添入數(shù)據(jù) taillink= p。 } //尾指針到鏈尾 taillink=NULL。 //返回頭指針 } 單鏈表基本算法 head ^ info0 P ^ P info1 2. 向前生成鏈表算法： node *createup(){ node *head,*p。 head=new node。 while(cindata){ //建立的總是第一個(gè)結(jié)點(diǎn) p=new node。 plink= headlink 。 //頭結(jié)點(diǎn)放新結(jié)點(diǎn)之前 } return head。 while(p!=NULLamp。pinfo!=data) p=plink。 //p為 NULL則未找到 } 返回值為指針 p， 指向鏈表中找到的結(jié)點(diǎn) 。 void insert(node *p,Datatype x){ node *q=new node。 qlink=plink。 } 單鏈表基本算法 5. 刪除單鏈表結(jié)點(diǎn) *p后面結(jié)點(diǎn)： void del (node *p){ node *q。 plink=qlink。 //如果要把該結(jié)點(diǎn)移入另一個(gè)鏈中 ， 則可將 q返回 。 定義結(jié)點(diǎn)類(lèi)： templatetypename Tclass List。 //數(shù)據(jù)域 NodeT *link。 //生成 頭結(jié)點(diǎn)的構(gòu)造函數(shù) Node(const T amp。 //生成 一般結(jié)點(diǎn)的構(gòu)造函數(shù) void InsertAfter(NodeT* p)。 //刪除當(dāng)前結(jié)點(diǎn)的后繼 結(jié)點(diǎn) friend class ListT。 定義鏈表類(lèi) : templatetypename Tclass List{ NodeT *head,*tail。 //構(gòu)造函數(shù) ，生成頭結(jié)點(diǎn) (空鏈表 ) ~List()。 //清空鏈表 ，只余表頭結(jié)點(diǎn) NodeT* Find(T data)。 //計(jì)算 單鏈表長(zhǎng)度 void PrintList()。 //可用來(lái) 向前生成鏈表 void InsertRear(NodeT* p)。 //按 升序生成鏈表 NodeT*CreatNode(T data)。 }。 然后給出一個(gè)整數(shù)在一個(gè)鏈表中查找 ， 找到后刪除它 ， 再輸出該表 。 在本例中程序只需調(diào)用類(lèi)模板中的成員函數(shù)就可以完成所有鏈表操作。 單鏈表類(lèi)型模板 討論復(fù)制構(gòu)造函數(shù)： 在本例中沒(méi)有給出 Node類(lèi)的復(fù)制構(gòu)造函數(shù)，并非可以使用默認(rèn)的復(fù)制構(gòu)造函數(shù)，而是避開(kāi)了所有使用它的情況，本例中函數(shù)的參數(shù)和返回值僅使用指向 Node的指針，類(lèi)定義中也沒(méi)有用復(fù)制方式初始化。 通常對(duì) Node類(lèi)復(fù)制的結(jié)果應(yīng)是一個(gè)孤立結(jié)點(diǎn)： template typename T NodeT::Node(Node amp。 link=NULL。該函數(shù)與 Node的有參構(gòu)造函數(shù)功能基本相同。 雙向鏈表（選讀） 雙向鏈表引入： 考慮單鏈表只能找后繼。為了克服這一缺點(diǎn)，可采用 雙向鏈表 （ Double Linked List)。雙向 鏈表經(jīng)常采用 帶頭結(jié)點(diǎn)的循環(huán)鏈表方式 。 p llinkrlink指示本結(jié)點(diǎn) 的前驅(qū)結(jié)點(diǎn)的后繼結(jié)點(diǎn)，即本結(jié)點(diǎn)，間接訪(fǎng)問(wèn)符 可以連續(xù)使用 。 棧與隊(duì)列的基本操作及其應(yīng)用 棧和隊(duì)都是特殊的線(xiàn)性表， 限制存取位置 的線(xiàn)性結(jié)構(gòu)，可以由順序表實(shí)現(xiàn)，也可以由鏈表實(shí)現(xiàn)。允許進(jìn)行插入和刪除的一端叫做 棧頂 (top)，而另一端叫 棧底 (bottom)。 進(jìn)棧時(shí)最先進(jìn)棧的在最下面，最后的在最上面，后來(lái)居上。所以棧又稱(chēng)作 后進(jìn)先出（ LIFO： Last In First Out）的線(xiàn)性表 。 棧 棧的基本操作： 參見(jiàn)下圖，設(shè)給定棧 s=(a0， a1， …… ， an1)，稱(chēng) a0為棧底， an1為棧頂。而出棧時(shí)順序相反，最后進(jìn)棧的 an1最先出棧，而最先進(jìn)棧的 a0最后出棧。其中棧底 bottom是指向棧數(shù)據(jù)區(qū)的下一單元，這樣判斷是否為空棧會(huì)更方便，只需 top與 bottom相同就是空棧。 棧 templatetypename Tclass Stack{ int top。 //動(dòng)態(tài)建立的元素 int maxSize。 //構(gòu)造函數(shù) ，棧如不指定大小，設(shè)為 20元素 ~Stack(){delete[ ] elements。data)。 //彈出 ， top T GetElem(int i)。} //清空棧 bool IsEmpty() const{return top== 1。} //判棧滿(mǎn) void PrintStack()。 //輸出 棧內(nèi)所有數(shù)據(jù) 【 例 】 順序棧的類(lèi)模板： 棧 void main(){ int i,a[10]={0,1,2,3,4,5,6,7,8,9},b[10]。 for(i=0。i++) (a[i])。 ()。i10。 if(()) cout?？?endl。i10。\t39。 ()。 NodeT *link。 link=next。 }。 //棧頂指針 public: Stack(){top=NULL。 //析構(gòu)函數(shù) void Push(const T amp。 //壓棧 T Pop()。 //取棧頂元素 void MakeEmpty()。} }。順序棧必須先開(kāi)一定大小內(nèi)存空間，執(zhí)行起來(lái)簡(jiǎn)單，速度快，可能溢出。 順序棧和鏈棧比較： 棧的應(yīng)用（選讀） 棧可用于 表達(dá)式的計(jì)算 。 為實(shí)現(xiàn)運(yùn)算符的優(yōu)先級(jí)，采用兩個(gè)棧：一個(gè) 數(shù)棧 ，一個(gè) 運(yùn)算符棧 。 棧的使用 (表達(dá)式運(yùn)算 ) ： N c b a ＊ ＋ O ＊ ＋ a t1 d e N a t1 d e ＋ ＋ ／ － O ／ － － ＋ O － ＋ N t1 a t2 t1 a t2 t3 a N t3 a N ＋ O ＋ O b*ct1 d/et2 t1t2t3 a+t3t4 N：數(shù)棧 O：運(yùn)算符 (a) (b) (c) (d) (e) 設(shè)有： a+b*cd/e=；參見(jiàn)上圖。否則將棧頂運(yùn)算符出棧，與數(shù)字棧出棧的兩個(gè)數(shù)據(jù)進(jìn)行運(yùn)算，結(jié)果壓入數(shù)棧，再將新運(yùn)算符壓棧。棧中數(shù)據(jù)繼續(xù)按前面規(guī)則出棧。 表達(dá)式結(jié)束符使用＝號(hào) ， 清空棧用 ‘ c’字符 。 簡(jiǎn)易計(jì)算器類(lèi)定義： class Calculator{ Stackint Nstack。 public: Calculator(void){}。 //計(jì)算器運(yùn)算程序 void GetTwoNum(int amp。Num2)。 //讀算式 void Clear(void)。 //清除 隊(duì)列 隊(duì)列的基本概念： 隊(duì)列 (Queue)也是一種限定存取位置的線(xiàn)性表。允許插入的一端稱(chēng)為 隊(duì)尾(rear)，允許刪除的一端叫做 隊(duì)頭 (front)。隊(duì)列的這種特性正好與棧相反，叫做 先進(jìn)先出 FIFO(First In First Out)。 隊(duì)列 rear front A D C A B D E C F H G BCD進(jìn)隊(duì) A進(jìn)隊(duì) 空隊(duì) D C AB出隊(duì) EFGH進(jìn)隊(duì) rear front rear rear rear front front front 圖 順序隊(duì)列的插入和刪除 由圖可見(jiàn)：空隊(duì)時(shí)指針（下標(biāo)）front和 rear在一起都指向隊(duì)前方，當(dāng)有元素進(jìn)隊(duì)，則 rear后移；有元素出隊(duì)，則 front后移，最后分配給隊(duì)的前端不再被利用。實(shí)際上 對(duì)象很大時(shí)，總是由索引（指針）來(lái)排隊(duì) 。 用鏈表實(shí)現(xiàn)隊(duì)列無(wú)此問(wèn)題 【 例 】 順序存儲(chǔ)方式的循環(huán)隊(duì)列類(lèi)模板 。鏈?zhǔn)壮鲫?duì)，鏈尾入隊(duì)。 二叉樹(shù)（選讀） 樹(shù)形結(jié)構(gòu)是一類(lèi)重要的非線(xiàn)性數(shù)據(jù)，樹(shù)和二叉樹(shù)是常用的樹(shù)形結(jié)構(gòu)。如 n=0，稱(chēng)為空樹(shù)。除根以外的其它結(jié)點(diǎn)劃分為 m（ m≥0）個(gè)互不相交的有限集合 T0， T1， …… ， Tm1，每個(gè)集合又是一棵樹(shù)，稱(chēng)為根的子樹(shù)（ subtree）。這是一個(gè)遞歸方法定義的數(shù)據(jù)結(jié)構(gòu)。 結(jié)點(diǎn)的度 ， 結(jié)點(diǎn)所擁有的子樹(shù)數(shù)量 。 分支結(jié)點(diǎn) ， 度 ≥1的結(jié)點(diǎn) 。 樹(shù)的術(shù)語(yǔ)： 二叉樹(shù)的概念（選讀） A B C D E F G I H J L K O N M ………… 0層 …… 1層 2層 3層 深度 圖 樹(shù)的示意圖 雙親結(jié)點(diǎn) ， 若結(jié)點(diǎn) x有孩子 ， 它即為孩子的雙親 。 結(jié)點(diǎn)的層次 ， 從根到該結(jié)點(diǎn)所經(jīng)路徑上的分支條數(shù) 。 樹(shù)的度 ，樹(shù)中結(jié)點(diǎn)度的最大值。二叉樹(shù)是結(jié)點(diǎn)的一個(gè)有限集合 ， 該集合或?yàn)榭?， 或是由一個(gè)根結(jié)點(diǎn)及兩棵樹(shù)分別稱(chēng)為左子樹(shù)和右子樹(shù)的 （ 注意有左右之分 ） 互不相交的二叉樹(shù)組成 ， 其中左右子樹(shù)分別可以為空子樹(shù)或均為空樹(shù) 。 二叉樹(shù)的特點(diǎn)是：每個(gè)結(jié)點(diǎn)最多兩個(gè)孩子 ， 并且子樹(shù)有左右之分 。 樹(shù)的概念： 二叉樹(shù)的概念（選讀） 【 例 】 畫(huà)出有三個(gè)結(jié)點(diǎn)的所有二叉樹(shù) 。 圖 5種不同的三結(jié)點(diǎn)二叉樹(shù) 二叉樹(shù)的概念（選讀） 滿(mǎn)二叉樹(shù)和完全二叉樹(shù)： 分別如圖 ，完全二叉樹(shù)已有的結(jié)點(diǎn)排序與滿(mǎn)二叉樹(shù)相同。每個(gè)結(jié)點(diǎn)有三個(gè)域：數(shù)據(jù)域、左孩子指針和右孩子指針，見(jiàn)圖 。 templatetypename Tclass Node{ NodeT *lchild,*rchild。 public: Node(){ lchild=NULL。} Node(T data,NodeT *left=NULL , NodeT *right=NULL){