【正文】 實(shí)現(xiàn)了完善的封裝 。 鏈表與鏈表的基本操作 線性表 是最簡(jiǎn)單，最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表的邏輯結(jié)構(gòu)是 n個(gè)數(shù)據(jù)元素的有限序列（ a1,a2,…,an ）。而線性表的 物理結(jié)構(gòu) 包括：順序表， 鏈表 。 單鏈表基本算法 雙向鏈表 (選讀 ) 單鏈表基本算法 單鏈表 （ Singly Linked list） ： 每個(gè)數(shù)據(jù)元素占用一個(gè)節(jié)點(diǎn) （ Node） 。 一個(gè)節(jié)點(diǎn)包含兩個(gè)域 ， 一個(gè)域存放數(shù)據(jù)元素 info， 其數(shù)據(jù)類型由應(yīng)用問題決定；另一個(gè)存放指向該鏈表中下一個(gè)節(jié)點(diǎn)的指針 link。 節(jié)點(diǎn)定義如下： typedef int Datatype。 //數(shù)據(jù)為整型 struct node{ Datatype info。 node *link。 }。 在 C/C++中允許結(jié)構(gòu)（或?qū)ο螅┏蓡T是 結(jié)構(gòu)自身的指針類型 ，通過指針引用自身這種類型的結(jié)構(gòu)。 但結(jié)構(gòu)成員決不能是結(jié)構(gòu)自身類型 ，即結(jié)構(gòu)不能自己定義自己，這會(huì)導(dǎo)致一個(gè)無窮遞歸的定義。 單鏈表基本算法 單鏈表的第一個(gè)結(jié)點(diǎn)的地址可通過鏈表的表頭指針 head找到， head在使用中千萬不可丟失，否則鏈表整個(gè)丟失，內(nèi)存也發(fā)生泄漏。 infon1 ^ info2 info1 info0 …… head 圖 單鏈表結(jié)構(gòu) 單鏈表的插入與刪除： 只要改變鏈中結(jié)點(diǎn)指針的值，無需移動(dòng)表中的元素，就能實(shí)現(xiàn)插入和刪除操作。 插入算法有 三種 情況，我們希望在單鏈表中包含數(shù)據(jù)infoi的結(jié)點(diǎn)之前插入一個(gè)新元素，則 infoi可在第一個(gè)結(jié)點(diǎn)，或在中間結(jié)點(diǎn)，如未找到，則把新結(jié)點(diǎn)插在鏈尾結(jié)點(diǎn)之后。 單鏈表基本算法 newnode infox info0 info1 head head 插在鏈?zhǔn)祝? 首先新結(jié)點(diǎn)的 link指針指向 info0所在結(jié)點(diǎn) ， 然后 ， head指向新結(jié)點(diǎn) 。 即： newnode→ link=head； //注意：鏈表操作次序非常重要 head=newnode； 單鏈表基本算法 infox infoi1 infoi p ｑ newnode 插在中間： 首先用工作指針 p找到指定結(jié)點(diǎn) ， 而讓指針 q指向緊跟其后的結(jié)點(diǎn) ， 令 infoi1所在結(jié)點(diǎn)的 link指針指向新結(jié)點(diǎn) ， 而后讓新結(jié)點(diǎn)的 link指向 infoi所在結(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。 單鏈表基本算法 帶表頭結(jié)構(gòu)的鏈表： 研究以上算法 ， 插在鏈表第一個(gè)結(jié)點(diǎn)之前與其他結(jié)點(diǎn)之前的算法有所不同 。 要使算法中沒有特殊者 ， 可以給每一個(gè)鏈表加上一個(gè) 表頭結(jié)點(diǎn) ， 如下圖所示 。 空表如下： head info0 Infon1 ^ info1 … head ^ 下面分別介紹 帶表頭結(jié)構(gòu) 的鏈表的生成鏈表算法、鏈表查找算法、插入一個(gè)結(jié)點(diǎn)的算法和刪除一個(gè)結(jié)點(diǎn)的算法。 單鏈表基本算法 head tail p info1 tail p info0 tail ^ 1. 向后生成鏈表算法： node *createdown(){ Datatype data。 Node*head,*tail,*p。 head=new node。 //建立鏈表頭結(jié)點(diǎn) tail=head。 while(cindata){ //回車結(jié)束 p=new(node)。 //每輸入一個(gè)數(shù)申請(qǐng)一個(gè)結(jié)點(diǎn) pinfo=data。 //添入數(shù)據(jù) taillink= p。 //新結(jié)點(diǎn)接到鏈尾 tail=p。 } //尾指針到鏈尾 taillink=NULL。 //鏈尾加空指針 ， 表示鏈結(jié)束 return head。 //返回頭指針 } 單鏈表基本算法 head ^ info0 P ^ P info1 2. 向前生成鏈表算法： node *createup(){ node *head,*p。 Datatype data。 head=new node。 //建立頭結(jié)點(diǎn) headlink=NULL。 while(cindata){ //建立的總是第一個(gè)結(jié)點(diǎn) p=new node。 pinfo=data。 plink= headlink 。 //新結(jié)點(diǎn)放在原鏈表前方 headlink=p。 //頭結(jié)點(diǎn)放新結(jié)點(diǎn)之前 } return head。} 單鏈表基本算法 (按關(guān)鍵字 )查找： node *traversal(node *head,Datatype data){ node *p=headlink。 while(p!=NULLamp。amp。pinfo!=data) p=plink。 return p。 //p為 NULL則未找到 } 返回值為指針 p， 指向鏈表中找到的結(jié)點(diǎn) 。 4. 在單鏈表的 p節(jié)點(diǎn)后插入 ： 注意只有一種情況。 void insert(node *p,Datatype x){ node *q=new node。 qinfo=x。 qlink=plink。 plink=q。 } 單鏈表基本算法 5. 刪除單鏈表節(jié)點(diǎn) *p后面節(jié)點(diǎn)： void del (node *p){ node *q。 q=plink。 plink=qlink。 delete q。 //如果要把該節(jié)點(diǎn)移入另一個(gè)鏈中 ， 則可將 q返回 。 } 單鏈表類型模板 【 例 】 單鏈表類模板 。 定義結(jié)點(diǎn)類： templatetypename Tclass List。 templatetypename Tclass Node{ T info。 //數(shù)據(jù)域 NodeT *link。 //指針域，注意結(jié)點(diǎn)類格式，尖括號(hào)中是參數(shù)名表，類模板實(shí)例化為類 public: Node()。 //生成 頭結(jié)點(diǎn)的構(gòu)造函數(shù) Node(const T amp。 data)。 //生成 一般結(jié)點(diǎn)的構(gòu)造函數(shù) void InsertAfter(NodeT* p)。 //在當(dāng)前 結(jié)點(diǎn)后插入 一個(gè)結(jié)點(diǎn) NodeT* RemoveAfter()。 //刪除當(dāng)前結(jié)點(diǎn)的后繼 結(jié)點(diǎn) friend class ListT。 //以 List為友元類， List可直接訪問 Node的私有函數(shù) }。 定義鏈表類 : templatetypename Tclass List{ NodeT *head,*tail。 //鏈表頭指針和尾指針 public: List()。 //構(gòu)造函數(shù) ，生成頭結(jié)點(diǎn) (空鏈表 ) ~List()。 //析構(gòu)函數(shù) void MakeEmpty()。 //清空鏈表 ，只余表頭結(jié)點(diǎn) NodeT* Find(T data)。 //搜索 數(shù)據(jù)域與 data相同的結(jié)點(diǎn)，返回該結(jié)點(diǎn)的地址 int Length()。 //計(jì)算 單鏈表長(zhǎng)度 void PrintList()。 //打印鏈表 的數(shù)據(jù)域 void InsertFront(NodeT* p)。 //可用來 向前生成鏈表 void InsertRear(NodeT* p)。 //可用來 向后生成鏈表 void InsertOrder(NodeT *p)。 //按 升序生成鏈表 NodeT*CreatNode(T data)。 //創(chuàng)建結(jié)點(diǎn) (孤立結(jié)點(diǎn) ) NodeT*DeleteNode(NodeT* p)。 }。 //刪除指定結(jié)點(diǎn) 單鏈表類型模板 單鏈表類型模板 【 例 】 由鍵盤輸入 16個(gè)整數(shù) ， 以這些整數(shù)作為結(jié)點(diǎn)數(shù)據(jù) ， 生成兩個(gè)鏈表 ， 一個(gè)向前生成 ， 一個(gè)向后生成 ， 輸出兩個(gè)表 。 然后給出一個(gè)整數(shù)在一個(gè)鏈表中查找 ， 找到后刪除它 ， 再輸出該表 。 清空該表 ， 再按升序生成鏈表并輸出 。 在本例中程序只需調(diào)用類模板中的成員函數(shù)就可以完成所有鏈表操作。 【 例 】 以學(xué)生類作為鏈表的數(shù)據(jù)類，完成學(xué)生檔案的管理。 單鏈表類型模板 討論復(fù)制構(gòu)造函數(shù)： 在本例中沒有給出 Node類的復(fù)制構(gòu)造函數(shù)，并非可以使用默認(rèn)的復(fù)制構(gòu)造函數(shù)，而是避開了所有使用它的情況，本例中函數(shù)的參數(shù)和返回值僅使用指向 Node的指針，類定義中也沒有用復(fù)制方式初始化。 定義復(fù)制構(gòu)造函數(shù)與類的實(shí)際意義和使用方式有關(guān)，并非只是深復(fù)制和淺復(fù)制的問題 。 通常對(duì) Node類復(fù)制的結(jié)果應(yīng)是一個(gè)孤立結(jié)點(diǎn)： template typename T NodeT::Node(Node amp。 node){ info=。 link=NULL。 } link域值為 NULL。該函數(shù)與 Node的有參構(gòu)造函數(shù)功能基本相同?？紤]到函數(shù)的參數(shù)和返回值僅使用指向 Node的指針，定義復(fù)制構(gòu)造函數(shù)已經(jīng)沒有實(shí)際意義 單鏈表的復(fù)制構(gòu)造函數(shù)和復(fù)制運(yùn)算符是一個(gè)復(fù)雜的算法，與前文所編的復(fù)制構(gòu)造函數(shù)和復(fù)制運(yùn)算符構(gòu)造相去甚遠(yuǎn)了。 雙向鏈表（選讀） 雙向鏈表引入： 考慮單鏈表只能找后繼。如要找前驅(qū)，必須從表頭開始搜索。為了克服這一缺點(diǎn)，可采用 雙向鏈表 （ Double Linked List)。雙向鏈表的 結(jié)點(diǎn)有三個(gè)域 ： 左鏈接指針 （ llink)，數(shù)據(jù)域（ info)， 右鏈接指針域 (rlink)。雙向鏈表經(jīng)常采用 帶頭結(jié)點(diǎn)的循環(huán)鏈表方式 。 info0 infon1 .’.’.’.’.’.’ info1 head (a) 非空表 head (b)空表 雙向鏈表（選讀） 雙向鏈表的訪問： 假設(shè)指針 p指向雙向循環(huán)鏈表的某一個(gè)結(jié)點(diǎn)，那么， pllink指示 P所指結(jié)點(diǎn)的 前驅(qū)結(jié)點(diǎn) ， prlink指示 后繼結(jié)點(diǎn)。 pllinkrlink指示本結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的后繼結(jié)點(diǎn)，即本結(jié)點(diǎn)，間接訪問符 可以連續(xù)使用 。 p llink rlink rlink llink rlink 前驅(qū)結(jié)點(diǎn) llink 本結(jié)點(diǎn) 后繼結(jié)點(diǎn) 間接訪問符的使用 【 例 】 雙向鏈表類模板和結(jié)點(diǎn)類模板。 棧與隊(duì)列的基本操作及其應(yīng)用 棧和隊(duì)都是特殊的線性表， 限制存取位置 的線性結(jié)構(gòu)，可以由順序表實(shí)現(xiàn)，也可以由鏈表實(shí)現(xiàn)。 7. 3. 1 棧 7. 3. 3 隊(duì) 列 7. 3. 2 棧的應(yīng)用（選讀） 棧 棧的基本概念： 棧定義為只允許在表的一端進(jìn)行插入和刪除的線性表 。允許進(jìn)行插入和刪除的一端叫做 棧頂 (top)，而另一端叫 棧底 (bottom)。 棧中沒有任何元素時(shí)，稱為空棧。 進(jìn)棧時(shí)最先進(jìn)棧的在最下面，最后的在最上面，后來居上。而出棧時(shí)順序相反，最后進(jìn)棧的最先出棧，而最先進(jìn)棧的 a0最后出棧。所以棧又稱作 后進(jìn)先出（ LIFO： Last In First Out）的線性表 。 ?？梢杂庙樞虮韺?shí)現(xiàn)，稱 順序 棧；也可以用鏈表實(shí)現(xiàn)，稱 鏈棧 。 棧 棧的基本操作： 參見下圖，設(shè)給定棧 s=(a0， a1， …… ， an1)，稱 a0為棧底， an1為棧頂。進(jìn)棧時(shí)最先進(jìn)棧的 a0在最下面， an1在最上面。而出棧時(shí)順序相反，最后進(jìn)棧的 an1最先出棧，而最先進(jìn)棧的 a0最后出棧。 a0 an2 …… a1 an1 bottom