【文章內(nèi)容簡(jiǎn)介】 return true。 }。 ? 實(shí)現(xiàn)單鏈表的插入和刪除算法，不需要移動(dòng)元素，只需修改結(jié)點(diǎn)指針，比順序表方便。 ? 情況復(fù)雜，要專門討論空表和在表頭插入的特殊情形。 ? 尋找插入或刪除位置只能沿著鏈順序檢測(cè)。 44 帶表頭結(jié)點(diǎn)的單鏈表 ? 表頭結(jié)點(diǎn)位于表的最前端，本身不帶數(shù)據(jù)，僅標(biāo)志表頭。 ? 設(shè)置表頭結(jié)點(diǎn)的目的是 統(tǒng)一空表與非空表的操作 ， 簡(jiǎn)化鏈表操作的實(shí)現(xiàn) 。 非空表 空表 0 an a1 first first 0 45 在帶表頭結(jié)點(diǎn)的單鏈表最前端插入新結(jié)點(diǎn) newnodelink = currentlink。 currentlink = newnode。 first newnode first newnode 插入 first newnode 0 first newnode 0 插入 current current current currrent 46 del = currentlink。 currentlink = dellink。 delete del。 從帶表頭結(jié)點(diǎn)的單鏈表中刪除最前端的結(jié)點(diǎn) (非空表） (空表） first first first 0 first 0 current del current del 47 單鏈表的模板類 ? 類模板將類的數(shù)據(jù)成員和成員函數(shù)設(shè)計(jì)得更完整、更靈活。 ? 類模板更易于復(fù)用。 ? 在單鏈表的類模板定義中，增加了 表頭結(jié)點(diǎn) 。 48 用模板定義的單鏈表類 template class T //定義在 “ ” struct LinkNode { //鏈表結(jié)點(diǎn)類的定義 T data。 //數(shù)據(jù)域 LinkNodeT *link。 //鏈指針域 LinkNode() { link = NULL。 } //構(gòu)造函數(shù) LinkNode(const T amp。 item, LinkNodeT *ptr = NULL) { data = item。 link = ptr。 } //構(gòu)造函數(shù) }。 49 template class T class List : public LinearListT { //單鏈表類定義 , 不用繼承也可實(shí)現(xiàn) protected: LinkNodeT *first。 //表頭指針 public: List() { first = new LinkNodeT。 } //構(gòu)造函數(shù) List(T amp。 x) { first = new LinkNodeT(x)。 } List( ListTamp。 L)。 //復(fù)制構(gòu)造函數(shù) ~List(){ makeEmpty()。} //析構(gòu)函數(shù) void makeEmpty()。 //將鏈表置為空表 int Length() const。 //計(jì)算鏈表的長(zhǎng)度 50 LinkNodeT *Search(T x)。 //搜索含 x元素 LinkNodeT *Locate(int i)。 //定位第 i個(gè)元素 T *getData(int i)。 //取出第 i元素值 void setData(int i, Tamp。 x)。 //更新第 i元素值 bool Insert (int i, Tamp。 x)。 //在第 i元素后插入 bool Remove(int i, Tamp。 x)。 //刪除第 i個(gè)元素 bool IsEmpty() const //判表空否 { return firstlink == NULL ? true : false。 } LinkNodeT *getFirst() const { return first。 } void setFirst(LinkNodeT *f ) { first = f。 } void Sort()。 //排序 }。 51 template class T void ListT::makeEmpty() { LinkNodeT *q。 while (firstlink != NULL) { q = firstlink。 //保存被刪結(jié)點(diǎn) firstlink = qlink。 //從鏈上摘下該結(jié)點(diǎn) delete q。 //刪除 } }； 鏈表置空算法（保留表頭結(jié)點(diǎn)） 52 first q first first q q first a0 a1 a1 a2 a2 a2 current 53 template class T int ListT :: Length ( ) const { ListNodeT *p = firstlink。 //檢測(cè)指針 p 指示第一號(hào)結(jié)點(diǎn) int count = 0。 while ( p != NULL ) { //逐個(gè)結(jié)點(diǎn)檢測(cè) p = plink。 count++。 } return count。 } 求單鏈表的長(zhǎng)度的算法 54 first p a0 a1 a2 c = 0 first p a0 a1 a2 c = 1 first p a0 a1 a2 c = 2 first p a0 a1 a2 c = 3 55 單鏈表的搜索算法 template class T LinkNodeT *ListT::Search(T x) { //在表中搜索含數(shù)據(jù) x的結(jié)點(diǎn) , 搜索成功時(shí)函數(shù)返 //該結(jié)點(diǎn)地址 。 否則返回 NULL。 LinkNodeT *current = firstlink。 while ( current != NULL amp。amp。 currentdata != x ) current = currentlink。 //沿著鏈找含 x結(jié)點(diǎn) return current。 }。 56 單鏈表的定位算法 template class T LinkNodeT *ListT::Locate ( int i ) { //函數(shù)返回表中第 i 個(gè)元素的地址。若 i 0或 i 超 //出表中結(jié)點(diǎn)個(gè)數(shù)，則返回 NULL。 if (i 0) return NULL。 //i不合理 LinkNodeT *current = first。 int k = 0。 while ( current != NULL amp。amp。 k i ) { current = currentlink。 k++。 } return current。 //返回第 i 號(hào)結(jié)點(diǎn)地址或 NULL }。 57 單鏈表的插入算法 template class T bool ListT::Insert (int i, T x) { //將新元素 x 插入在鏈表中第 i 個(gè)結(jié)點(diǎn)之后。 LinkNodeT *current = Locate(i)。 if (current == NULL) return false。 //無(wú)插入位置 LinkNodeT *newNode = new LinkNodeT(x)。 //創(chuàng)建新結(jié)點(diǎn) newNodelink = currentlink。 //鏈入 currentlink = newNode。 return true。 //插入成功 }。 58 單鏈表的刪除算法 template class T bool ListT::Remove (int i, Tamp。 x ) { //刪除鏈表第 i個(gè)元素 , 通過(guò)引用參數(shù) x返回元素值 LinkNodeT *current = Locate(i1)。 if ( current == NULL || currentlink == NULL) return false。 //刪除不成功 LinkNodeT *del = currentlink。 currentlink = dellink。 x = deldata。 delete del。 return true。 }。 59 前插法建立單鏈表 ? 從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)： ? 生成新結(jié)點(diǎn) ? 將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中 ? 將該新結(jié)點(diǎn)插入到鏈表的前端 ? 直到讀入結(jié)束符為止。 first newnode first newnode 0 0 60 template class T, class E void inputFront (T endTag, ListT, Eamp。 L) { LinkNodeT, E *newNode, *newF。 E val。 newF = new LinkNodeT, E。 (newF)。 //firstlink默認(rèn)值為 NULL cin val。 while (val != endTag) { newNode = new LinkNodeT, E(val)。 newNodelink = newFlink。 //插在表前端 newFlink = newNode。 cin val。 } }。 61 后插法建立單鏈表 ? 每次將新結(jié)點(diǎn)加在插到鏈表的表尾； ? 設(shè)置一個(gè)尾指針 last，總是指向表中最后一個(gè)結(jié)點(diǎn)，新結(jié)點(diǎn)插在它的后面； ? 尾指針 last 初始時(shí)置為指向表頭結(jié)點(diǎn)地址。 0 0 newnode first newnode 0 0 last last last last 62 template class T, class E void inputRear ( T endTag, ListT, Eamp。 L ) { LinkNodeT, E *newNode, *last。 E val。 last = new LinkNodeT, E。 //建立鏈表的頭結(jié)點(diǎn) (last)。 //為鏈表 L的 first賦值 cin val。 while ( val != endTag ) { //last指向當(dāng)前的表尾 newNode = new LinkNodeT, E(val)。 lastlink = newNode。 last = newNode。 cin val。 //插入到表末端 } lastlink = NULL。 //表收尾 }。 63 iniinnnxaxaxaxaaxP????????02210 )( ?多項(xiàng)式 (Polynomial) ? n階多項(xiàng)式 Pn(x) 有 n+1 項(xiàng) 。 ? 系數(shù) a0, a1, a2, …, an ? 指數(shù) 0, 1, 2, …, n。按升冪排列 64 多項(xiàng)式的順序存儲(chǔ)表示 第一種： private: (靜態(tài)數(shù) int degree。 組表示 ) float coef [maxDegree+1]。 Pn(x)可以表示為 ： = n [i] = ai, 0 ? i ? n a0 a1 a2 …… an ……… 0 1 2 degree maxDegree1 coef n 65 第二種： private: (動(dòng)態(tài)數(shù) int degree。 組表示 ) float * coef。 Polynomial :: Polynomial (int sz)