【正文】 //打印鏈表 int Length()。 //鏈尾插入 DblNodeT* Remove(DblNodeT* p)。 void Insert(const T amp。 public: DblList()。 rlink=NULL。} templatetypename T DblNodeT::DblNode(T data){ info=data。}。}。 //生成一般結(jié)點的構(gòu)造函數(shù) DblNode()。 //數(shù)據(jù)域 DblNodeT *llink,*rlink。 return 0。 (P1)。ih。 ()。 coutlist1長度： ()endl。 delete P1。 P1=(j)。 cout請輸入一個要求刪除的學(xué)生學(xué)號 endl。 例 學(xué)生檔案的管理 coutlist1長度： ()endl。 (P1)。 (P1)。ih。,18,重慶路 95號 ,78,95,81,88),}。,18,上海路 37號 ,78,95,81,88), student(6004219,趙昀 ,39。,19,天津路 64號 ,88,75,91,68), student(6004118,劉蓓 ,39。,19,北京路 58號 ,80,85,90,78), student(6004121,關(guān)雨 ,39。 student n[h]={ student(6004327,張菲 ,39。 Nodestudent * P1。 例 學(xué)生檔案的管理 int main(){ const int h=4。 } coutendl。 while(tempP!=NULL){ tempP()。} }。\t39。\t39。\t39。\t39。\t39。\t39。\t39。\t39。} bool operator!=(student ele){return id!=。,int=0,string=, float=,float=,float=,float=)。 //英語，物理，數(shù)學(xué)和電子學(xué)成績 public: student(int=0,string=,char=39。string address。char sex。} 例 學(xué)生檔案的管理 include class student{ int id 。 } //升序創(chuàng)建 list1 ()。i++){ P1=(a[i])。 //清空 list1 for(i=0。 } else cout未找到 endl。 ()。 if(P1!=NULL){ P1=(P1)。 cinj。 ()。 } //向后生成 list2 ()。 //向前生成 list1 P1=(a[i])。i++){ P1=(a[i])。 //隨機輸入 16個整數(shù) for(i=0。i16。 cout請輸入 16個整數(shù) endl。 Listint list1,list2。 return tempPRemoveAfter()。tempPlink!=p) tempP=tempPlink。 while(tempPlink!=NULLamp。 return tempP。 //插在 tempP指向結(jié)點之前， tempQ之后 if(tail==tempQ) tail=tempQlink。 tempP=tempPlink。 //tempQ指向 tempP前面的一個結(jié)點 while(tempP!=NULL){ if(pinfotempPinfo)break。 tail=p。} templatetypename Tvoid ListT::InsertRear(NodeT *p){ plink=taillink。 headlink=p。 } coutendl。\t39。 } 例 單鏈表類型模板 鏈表類成員函數(shù)： templatetypename Tvoid ListT::PrintList(){//顯示鏈表 NodeT* tempP=headlink。count++。 int count=0。 return tempP。amp。 } //表頭指針與表尾指針均指向表頭結(jié)點，表示空鏈 例 單鏈表類型模板 鏈表類成員函數(shù)： templatetypename T NodeT* ListT::Find(T data){ NodeT *tempP=headlink。 //把頭結(jié)點后的第一個結(jié)點從鏈中脫離 delete tempP。 while(headlink!=NULL){ tempP=headlink。 delete head。 } 例 單鏈表類型模板 鏈表類成員函數(shù)： templatetypename TListT::List(){ head=tail=new NodeT()。 //已在鏈尾 ,后面無結(jié)點 else link=tempPlink。 } templatetypename TNodeT* NodeT::RemoveAfter(){ NodeT* tempP=link。 } templatetypename T void NodeT::InsertAfter(NodeT* p){ plink=link。 data){ info=data。} 例 實現(xiàn)深復(fù)制 例 單鏈表類型模板 template typename T NodeT::Node(){ link=NULL。 s3=s2。} int main(void){ student s1(范英明 ),s2(沈俊 ),s3。 coutpNameendl。//如原來已分配，應(yīng)先撤銷，再重分配 if(){ //否則會發(fā)生內(nèi)存泄漏 if(pName=new char[strlen()+1]) strcpy(pName,)。s){ coutCopy Assign operator。} //釋放字符串 例 實現(xiàn)深復(fù)制 復(fù)制賦值操作符： student amp。\039。} 析構(gòu)函數(shù)： student::~student(){ coutDestructorpNameendl。 } else pName=NULL。s){ coutCopy Constructor。 coutpNameendl。 } 帶參數(shù) 構(gòu)造函數(shù)： student::student(char *pname){ coutConstructor。 pName=NULL。 return 0。 delete pc1。 pc2=new CGoods[n]。 //調(diào)用默認構(gòu)造函數(shù) cout’輸入商品類數(shù)組元素數(shù) ’ endl。 pc=new CGoods(“夏利 2021”， 10， 118000)。 對象與構(gòu)造函數(shù) 【 例 】 使用： int main(){ int n。} }。 Total_value=price*amount。 Amount=amount。 CGoods(string name,int amount ,float price){ cout調(diào)用三參數(shù)構(gòu)造函數(shù) endl。 public: CGoods(){cout調(diào)用默認構(gòu)造函數(shù) endl。 float Price。 } 對象與構(gòu)造函數(shù) 【 例 】 類說明： class CGoods{ string Name。i++) delete[] data[i]。 for (i=0。 return 0。 //數(shù)組元素賦值 display(data)。jn。im。 return 1。j++){ data[j] = new double[n]。 } for(j=0。 //建立指向組成二維數(shù)組各行的指針數(shù)組 if ((data ) == 0){ cout Could not allocate. Bye ...。 int i,j。 (選讀 ) int m=4,n=6。 } 內(nèi)存的分配與釋放 【 例 】 【 例 】 動態(tài)創(chuàng)建和刪除一個 m*n個元素的數(shù)組。 delete []pc。 strcpy(pc, 自由存儲區(qū)內(nèi)存的動態(tài)分配 )。 cinn。 char *pc。 算法：用中序遍歷即可，但遞歸慢，下面為迭代查找算法。 } } return NULL。 if(tempinfodata)temp=temprchild。data,NodeT *b){ if(b!=NULL){ NodeT *temp=b。這步就是插入算法。 2. 若 a1a0，令 a1為 a0左子樹的根結(jié)點，否則 a1為 a0右子樹的根結(jié)點。 10 18 26 8 12 22 29 11 24 16 15 圖 二叉排序樹例 二叉排序樹的遍歷： 二叉排序樹生成算法： 對任意一組數(shù)據(jù)元素序列 {a0， a1， a2， … ， an1}。 二叉排序樹的定義： 二叉排序樹或者是空樹或者是具有下述性質(zhì)的二叉數(shù)，其左子樹上所有結(jié)點的數(shù)據(jù)值均小于根結(jié)點的數(shù)據(jù)值；右子樹上所有結(jié)點的數(shù)據(jù)值均大于等于根結(jié)點的數(shù)據(jù)值，左子樹和右子樹又各是一棵二叉排序樹。 排序二叉樹 （選讀） 二叉排序樹 （ Binary Sorting Tree） 又稱二叉搜索樹 （ Binary Search Tree） ， 是一種特殊結(jié)構(gòu)的二叉數(shù) ，作為一種排序和查找的手段 ， 對應(yīng)有序表的對半查找 ，通常亦被稱為數(shù)表 。 再由先序 C E F知 C為左子樹根結(jié)點，由中序 E C F知 E為 C左子樹，F(xiàn)為的右子樹。 解： 由先序知 A為根結(jié)點，而由中序知 E C F B D G為左子樹， I H J K為右子樹。結(jié)果如圖 。 檢驗 主函數(shù) 二叉樹的遍歷（選讀） 【 例 】 某二叉樹先序遍歷為ABCEFDGHIJK，中序遍歷為ECFBDGAIHJK繪出該二叉樹。} //前序遍歷，公有函數(shù)為接口 void PostOrder(){PostOrder(root)。 //建立（排序）二叉樹 void InOrder(){InOrder(root)。} //空樹構(gòu)造函數(shù) ~BinaryTree(){Destory(root)。 //插入結(jié)點 ， 參數(shù)為引用！ void Destory(NodeT * Current)。data,NodeT * amp。 //前序遍歷 void PostOrder(NodeT *Current)。 //二叉樹的根指針 void InOrder(NodeT *Current)。 本例采用簡單的接口函數(shù) ， 而把較復(fù)雜的算法作為私有函數(shù) 。 特別注意插入結(jié)點時 ， 第二參數(shù)為指針的引用 ！否則不能建立樹 。 后序遍歷結(jié)果為 D G E B H F C A。 遍歷二叉樹有不同次序，規(guī)定先左后右，令 L， R， V分別代表遍歷一個結(jié)點的左右子樹和訪問該結(jié)點的操作，有三種方式： 前序遍歷（ VLR） 中序遍歷（ LVR） 后序遍歷（ LRV） 二叉樹的遍歷（選讀） 遍歷實 例： 前序遍歷訪問次序為 ABDEGCFH。 //二叉樹類說明為友元類 } 二叉樹的遍歷（選讀） 二叉樹的遍歷 (binary tree traversal)： 定義： 遵從某種次序 ， 查巡二叉樹的所有結(jié)點 ， 每個結(jié)點都被訪問一次 ， 而且僅訪問一次 。} //設(shè)置左指針 void setrightNodeT *right){rchild=right。} //取得左子樹 NodeT *Getright(){return rchild。data){info=data。 } 二叉樹的概念（選讀） T Getinfo(){return info。 lchild=left。 rchild=NULL。 T info。