【文章內(nèi)容簡介】 1]=elem[i]。 curlen。 return(el)。 }。 }。 逐個上移傳送： 邏輯序號： i 從 loc ＋ 1到 curlen 物理序號： i 從 loc 到 curlen1 最后將 loc 位置的元素刪除 57 刪除操作 ? 執(zhí)行實例： 假設(shè)線性表為 （ ’ a’,’c’,’e’,’g’,’i’,’k’,’m’） loc＝ 3 則正確刪除，返回結(jié)果為： ’e’； 線性表成為 （ ’ a’,’c’,’g’,’i’,’k’,’m’） loc＝ 8 則輸出出錯信息 58 互動環(huán)節(jié)：順序表的逆置操作 設(shè)計一個函數(shù) ， 其功能為對順序表中的所有元素進行逆置 ， 同時編制一個主程序 ， 對該函數(shù)的功能進行測試 。 設(shè)計思想：將該函數(shù)設(shè)置成類中的成員函數(shù) 。 由于是類中的成員函數(shù) ， 執(zhí)行操作的對象是當(dāng)前對象 ， 因此該函數(shù)無須設(shè)置參數(shù) 。 另外該函數(shù)也無須設(shè)置返回值 ， 因此其形式可設(shè)置如下： void inver ()。 其處理過程為：將整個元素序列分為前后兩部分，然后將這兩部分中所有對應(yīng)的元素進行交換。 59 逆置操作 ? 處理過程： (1) 將整個元素序列分為前后兩部分， (2)然后將這兩部分中所有對應(yīng)的元素進行交換。 Curlen1 elem 交換對象： elem[ i] 與 [ n1 i] i ： 從 0 到 n / 2 1 0 60 逆置操作 ? 程序： template class Telem void SqListTelem::inver ( ) { int i,m,n。 Telem temp。 n=curlen。 m= n / 2。 for (i= 0。im。 i++ ) { temp=elem[i]。 elem[i]=elem[n1i]。 elem[n1i]=temp。 }。 }。 逐個交換 ： elem[ i] 〈－〉 elem[ n1i] i ： 從 0 到 curlen / 2 1 61 逆置操作 在主函數(shù)中設(shè)置如下的測試代碼： void main() { char a[]={39。a39。,39。b39。,39。c39。,39。d39。,39。e39。}。 SqList char sql1(a,5)。 for(int i=1。i=5。i++) cout(i) 。 coutendl。 ()。 for(int i=1。i=5。i++) cout(i) 。 } 程序的運行結(jié)果如下： a b c d e e d c b a 62 作業(yè)：順序表合并操作 設(shè)計一個函數(shù) ， 其功能為將兩個順序表中的數(shù)據(jù)元素進行合并 ，同時編制一個主程序 ， 對該成員函數(shù)的功能進行測試 。 設(shè)計思想：將合并操作設(shè)計成順序表類中的成員函數(shù) 。 由于是成員函數(shù) ， 操作的一方是當(dāng)前對象 ， 而在參數(shù)中只要指定另一個順序表 。 合并的結(jié)果使當(dāng)前對象發(fā)生了改變 ， 同時作為函數(shù)的返回值返回 。 因此合并操作可設(shè)計成如下的形式： SqListTelemamp。 merg(SqListTelemamp。 l2) 處理過程：將參數(shù)中指定的順序表中的元素依次追加到當(dāng)前順序表之后 ,使其長度為兩者之和并返回當(dāng)前對象 。 63 作業(yè)：順序表合并操作 template class Telem SqListTelemamp。 SqListTelem::merg(SqListTelemamp。 l2) {int i,m,n。 m=curlen。n=。 if(m+n=maxlen) {for(i=0。in。i++)elem[m+i]=[i]。 curlen=m+n。 return *this。 } } 64 后記 ? 結(jié)束 65 版權(quán)所有 , 1997 (c) Dale Carnegie amp。 Associates, Inc. 線性表（二） 朱振元 66 單鏈表類 采用單向鏈?zhǔn)降拇鎯Ψ绞酱鎯Φ木€性表稱為單鏈表 , 由此建立一個實現(xiàn)類 ,實現(xiàn)線性表抽象類中定義的各接口函數(shù)的功能 , 該實現(xiàn)類稱為單鏈表類。 順序結(jié)構(gòu)的不足之處 : ? 難以為它確定適當(dāng)?shù)拇鎯臻g的大小 ? 在作插入或刪除時需移動大量元素 鏈?zhǔn)浇Y(jié)構(gòu)的特點 : ? 存儲單元的位置是任意的 ,由指針相連 ? 完全避免了順序存儲結(jié)構(gòu)所具有的弱點 67 鏈?zhǔn)酱鎯Y(jié)構(gòu)的分類 ? 按節(jié)點的分配方式 動態(tài)鏈表 單鏈表 循環(huán)鏈表 雙向鏈表 雙向循環(huán)鏈表 靜態(tài)鏈表 ? 按鏈的類別 68 單鏈表的結(jié)構(gòu)形式及特點 ? 由節(jié)點組成 ? n個結(jié)點（ ai （ 1≦i≦n ） 的存儲映象）鏈結(jié)成一個鏈表，即為線性表(a1,a2,……… ,an)的鏈?zhǔn)酱鎯Y(jié)構(gòu) ? 數(shù)據(jù)元素之間的邏輯關(guān)系是由結(jié)點中的指針指示的 數(shù)據(jù)域 指針域 NULL NULL 69 相關(guān)的類型定義 struct Tnode { Telem data。 Tnode *next。 }。 Tnode * head； 鏈表定義 head = new nodetp。 生成鏈頭節(jié)點 headnext= NULL。 data next 70 單鏈表結(jié)點類的定義 template class Telem class LinkList。 template class Telem class Node { friend class LinkList Telem。 Telem data。 Node Telem *next。 public: Node(Telem d=0,Node Telem *n=NULL) :data(d),next(n){}。 }。 71 單鏈表類的定義 template class Telem class LinkList :public ListTelem {private: Node Telem *head。 public: LinkList(){head=new Node Telem()。}。 LinkList(Telem a[],int n)。 ~LinkList(){delete[] head。}。 void init() {delete[] head。 head=new Node Telem()。}。 Telem gete(int i)。 int leng()。 int loct (Telemamp。 el)。 bool inst (int loc,Telemamp。 el)。 Telem dele(int i)。 bool full(){return false。}。 bool empt(){return headnext==NULL。}。 }。 72 單鏈表建表操作 ? 含義：指由一個一維數(shù)組 a中的 n個元素的值，建立一個長度為 n的線性鏈表， （圖 ） a2 a1 head an nil a1 a2 an 數(shù)組 a 73 建表操作表示形式 LinkList(Telem a[],int n) 其功能為：建立一個由 head指向的長度為 n的單鏈表 （ 帶頭結(jié)點 ） ， 并使其 n個數(shù)據(jù)元素的值依次等于一維數(shù)組 a中的 n個元素的值 。 該操作的處理過程為： (1)建立一個空表； (2)生成一個結(jié)點 ， 按從下到上的次序從數(shù)組 a中取出元素作為結(jié)點中的元素值 ， 然后從鏈頭插入該結(jié)點； (3)重復(fù)執(zhí)行過程 (2)直至生成 n個結(jié)點 。 74 建表操作處理過程 ? 處理過程： （ 1）建立一個空表； （ 2）生成一個結(jié)點，按從下到上的次序從數(shù)組 a中取出元素作為結(jié)點中的元素值，然后從鏈頭插入該結(jié)點； （ 3）重復(fù)執(zhí)行過程 2直至生成 n個結(jié)點。 an nil nil head an nil head an1 nil head 75 建表操作程序代碼 template class Telem LinkListTelem::LinkList(Telem a[],int n) {Node Telem *p。 int i。 head=new Node Telem()。 headnext=NULL。 for (i=n1。i=0。i ) { p=new Node Telem()。 pdata=a[i]。 pnext= headnext。 headnext=p。 }。 }。 76 單鏈表取元素操作 Telem gete(int i) 功能：取帶頭結(jié)點的單鏈表中的第 i個數(shù)據(jù)元素 。 若 1≦ i≦ 表長 ,則返回表中的第 i個數(shù)據(jù)元素 ， 否則返回空元素 NULL。 處理過程： (1)初始化 ， 使指針 p指向第一個元素的結(jié)點； (2)順指針逐個后移直至指針指向第 i個元素結(jié)點或指針為空； (3)若 i個元素結(jié)點存在則返回該元素否則返回空元素 NULL。 NIL i el 77 取元素操作程序代碼 template class Telem Telem LinkListTelem::gete(int i) {Node Telem *p。 int j。 p= head。 j=0。 while ((p!=NULL ) amp。amp。 (ji)) {p=pnext。 j=j+1。 }。 if ((p!=NULL ) amp。amp。 (j==i)) return(pdata)。 else return(NULL)。 }。 特殊情形： 1. 當(dāng) i1 時 ,循環(huán)一次也沒有執(zhí)行，執(zhí)行判別語句時 j!=i,返回 NULL； 2. 當(dāng) i＝ 1 時 ,循環(huán)一次也沒有執(zhí)行，但 p指向第一個節(jié)點 , j＝ i,返回第一個節(jié)點的元素值 ； 3. 當(dāng) i表長時 ,p=NULL,返回 NULL； 78 求長度操作 int leng()。 功能：求單鏈表的長度 。 其處理過程為： (1)使指針 p指向第一個元素的結(jié)點 ， 計數(shù)值初態(tài) 。 (2)順指針逐個后移并逐個計數(shù)直至指針為空 。 (3)返回計數(shù)值 。 實現(xiàn)代碼： template class Telem int LinkListTelem::leng() {Node Telem *p。int j。 p= headnext。 j=0。 while (p!=NULL ) {p=pnext。 j=j+1。 }。 return j。 }。 79 定位操作 int loct(Telemamp。 el) 功能：求元素 el在單鏈表中的序號 。 其處理過程為： (1)使指針 p指向第一個元素的結(jié)點 ， 計數(shù)值初態(tài) 。 (2)順指針逐個進行比較并逐個計數(shù)直至結(jié)點中的數(shù)據(jù)值與 el相等或指針為空 。 (3)若查到則返回計數(shù)值否則返回 0。 template class Telem int LinkListTelem::loct(Telemamp。 el) {Node Telem *p。 int j。 Telem data。 p= headnext。 j=1。 while (p!=NULL ) {data=pdata。 if (data==el) break。 p=pnext。 j=j+1。 }。 if (p!=NULL ) return(j)。 else return(0)。 }。 80 單鏈表插入操作 ? 含義：在線性表 L的第 i個節(jié)點前插入一個指定元素值的新結(jié)點。 el i1 i 81 插入操作表示形式 bool inst (int loc,Telemamp。 el) 表示 ， 參數(shù) loc、 el分別表示插入的位置與插入的元素 。 該函數(shù)的功能為：在帶頭結(jié)點的單鏈表中的第 loc號結(jié)點之前插入數(shù)據(jù)元素值為 el的新結(jié)點 ，該操作的處理過程為： (1)尋找第 loc－ 1個結(jié)點 ， 使指針 p指向該結(jié)點 。 (2)若由于 loc不合理而找不到相應(yīng)的結(jié)點 ， 則輸出信息