【正文】 。 Delete(L,i) 刪除操作 。 //初始化 virtual int leng()=0。 //返回第 i個元素 virtual int loct (Telemamp。 //查找 ， 若找到返回元素的序號否則返回 0 virtual bool inst (int loc,Telemamp。 //將 el插入在 loc位置中 virtual Telem dele(int loc)=0。 //判線性表是否為滿 virtual bool empt()=0。 37 線性表的存儲方式 ? 線性表在計(jì)算機(jī)中的存儲方式（又稱映象）可分為順序存儲方式和鏈?zhǔn)酱鎯Ψ绞蕉N。 順序存儲結(jié)構(gòu)及特點(diǎn) ? 用一組地址連續(xù)的存儲單元來依次存儲線性表的各個元素。 L=(a1,a2,……ai1,ai,ai+1,……An) （圖 ） a1 a2 ai an 39 順序表元素的地址計(jì)算 ? 由于在順序表中的元素是順序排列的，所以可以下列公式進(jìn)行地址計(jì)算 (設(shè)第一個元素的地址為 a1， 每個元素占用 L個單元 ) LOC(ai) ＝ LOC(a1) ＋ (i1)* L LOC(ai+1) ＝ LOC(ai) ＋ L LOC(an) ＝ LOC(a1) ＋ (n1)* L 40 類型描述 const int maxlen=線性表可能達(dá)到的最大長度； struct TsqList { Telem elem[maxlen]。 }。 [0]表示線性表的第一個元素， 則表示線性表的當(dāng)前長度 a1 a2 an Elem[0..max1] max curlen 41 順序表的類定義 template class Telem class SqList :public ListTelem {private: Telem *elem。 int maxlen。 SqList(Telem a[],int n,int maxsz=100)。}。}。 int leng(){return curlen。 int loct (Telemamp。 bool inst (int loc,Telemamp。 Telem dele(int loc)。}。}。 42 順序表類定義中的構(gòu)造函數(shù) SqList(int maxsz=100):maxlen(maxsz) {curlen=0。 }。 elem=new Telem[maxlen]。in。 }。 若 L中存在其值與 el相等的數(shù)據(jù)元素，則函數(shù)值為該數(shù)據(jù)元素在線性表中的位序，否則為 0。 el) 功能：在順序表中查找數(shù)據(jù)元素 el， 若線性表中存在與 el相等的數(shù)據(jù)元素 ， 則返回該數(shù)據(jù)元素在線性表中的序號 ， 否則返回 0。 Curlen1 elem 比較對象 el 與 elem[ i] i ： 從 0 到 curlen1 0 46 查找函數(shù) ? 程序： template class Telem int SqListTelem::loct(Telemamp。 while ((icurlen)amp。(elem[i]!=el) ) i++。 else return(0)。 在上述程序中 while循環(huán)的條件是必須同時滿足 (icurlen)與 (elem[i]?。?el) 其中第 1個條件表示還沒有比較完，第 2個條件表示還沒有查到。 48 順序表的插入操作： ? 含義：在順序表的第 i1個數(shù)據(jù)元素與第 i個數(shù)據(jù)元素之間插入一個新的元素 。 el) 表示 ， 其功能為：將數(shù)據(jù)元素 el插入在順序表中的第 loc個位置處 ， 其中 ， 1 = loc = curlen + 1 若插入成功返回 true,否則返回 false。 50 插入操作 處理過程： （ 1）檢查插入位置 loc是否合法；若不合法返回 false， 否則： （ 2）長度加 1并將第 loc號到第curlen號元素向后移動一個位置； （ 3） 將元素 el在位置 loc插入到線性表中并返回 true。 el) { int i。 else { curlen++。i=loc。 elem[loc1]=el。 }。 52 插入操作 ? 執(zhí)行實(shí)例： 假設(shè)線性表為 （ ’ a’,’c’,’e’,’g’,’i’,’k’,’m’） el＝ ?x?, loc＝ 3 則正確插入，結(jié)果為：（ ’ a’,’c’,’x’, ’e’,’g’,’i’,’k’,’m’） loc＝ 8 則正確插入，結(jié)果為：（ ’ a’,’c’,’e’,’g’,’i’,’k’,’m’,’x’） loc＝ 9 則輸出出錯信息 53 順序表的刪除操作 ： 含義：線性表的刪除操作是指在線性表中刪除其中的第 i個數(shù)據(jù)元素 elem i 刪除元素 i＋ 1 i－ 1 54 順序表的刪除操作： 刪除操作由成員函數(shù) Telem dele(int loc) 表示 ， 其功能為：在順序表中刪除第 loc號元素并返回該元素 ， 其中 ， 1 = loc = curlen。 55 刪除操作 ? 處理過程： (1)檢查插入位置 loc是否合法； (2)將第 loc+1號到第 curlen號元素向前移動一個位置； (3)線性表長度減 1并返回刪除元素 。 Telem el。 else { el=elem[loc1]。 icurlen。 curlen。 }。 逐個上移傳送： 邏輯序號： i 從 loc ＋ 1到 curlen 物理序號： i 從 loc 到 curlen1 最后將 loc 位置的元素刪除 57 刪除操作 ? 執(zhí)行實(shí)例： 假設(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è)計(jì)一個函數(shù) ， 其功能為對順序表中的所有元素進(jìn)行逆置 ， 同時編制一個主程序 ， 對該函數(shù)的功能進(jìn)行測試 。 由于是類中的成員函數(shù) ， 執(zhí)行操作的對象是當(dāng)前對象 ， 因此該函數(shù)無須設(shè)置參數(shù) 。 其處理過程為：將整個元素序列分為前后兩部分，然后將這兩部分中所有對應(yīng)的元素進(jìn)行交換。 Curlen1 elem 交換對象： elem[ i] 與 [ n1 i] i ： 從 0 到 n / 2 1 0 60 逆置操作 ? 程序： template class Telem void SqListTelem::inver ( ) { int i,m,n。 n=curlen。 for (i= 0。 i++ ) { temp=elem[i]。 elem[n1i]=temp。 }。a39。b39。c39。d39。e39。 SqList char sql1(a,5)。i=5。 coutendl。 for(int i=1。i++) cout(i) 。 設(shè)計(jì)思想：將合并操作設(shè)計(jì)成順序表類中的成員函數(shù) 。 合并的結(jié)果使當(dāng)前對象發(fā)生了改變 ， 同時作為函數(shù)的返回值返回 。 merg(SqListTelemamp。 63 作業(yè)：順序表合并操作 template class Telem SqListTelemamp。 l2) {int i,m,n。n=。in。 curlen=m+n。 } } 64 后記 ? 結(jié)束 65 版權(quán)所有 , 1997 (c) Dale Carnegie amp。 順序結(jié)構(gòu)的不足之處 : ? 難以為它確定適當(dāng)?shù)拇鎯臻g的大小 ? 在作插入或刪除時需移動大量元素 鏈?zhǔn)浇Y(jié)構(gòu)的特點(diǎn) : ? 存儲單元的位置是任意的 ,由指針相連 ? 完全避免了順序存儲結(jié)構(gòu)所具有的弱點(diǎn) 67 鏈?zhǔn)酱鎯Y(jié)構(gòu)的分類 ? 按節(jié)點(diǎn)的分配方式 動態(tài)鏈表 單鏈表 循環(huán)鏈表 雙向鏈表 雙向循環(huán)鏈表 靜態(tài)鏈表 ? 按鏈的類別 68 單鏈表的結(jié)構(gòu)形式及特點(diǎn) ? 由節(jié)點(diǎn)組成 ? n個結(jié)點(diǎn)（ ai （ 1≦i≦n ） 的存儲映象）鏈結(jié)成一個鏈表，即為線性表(a1,a2,……… ,an)的鏈?zhǔn)酱鎯Y(jié)構(gòu) ? 數(shù)據(jù)元素之間的邏輯關(guān)系是由結(jié)點(diǎn)中的指針指示的 數(shù)據(jù)域 指針域 NULL NULL 69 相關(guān)的類型定義 struct Tnode { Telem data。 }。 生成鏈頭節(jié)點(diǎn) headnext= NULL。 template class Telem class Node { friend class LinkList Telem。 Node Telem *next。 }。 public: LinkList(){head=new Node Telem()。 LinkList(Telem a[],int n)。}。 head=new Node Telem()。 Telem gete(int i)。 int loct (Telemamp。 bool inst (int loc,Telemamp。 Telem dele(int i)。}。}。 72 單鏈表建表操作 ? 含義：指由一個一維數(shù)組 a中的 n個元素的值，建立一個長度為 n的線性鏈表， （圖 ） a2 a1 head an nil a1 a2 an 數(shù)組 a 73 建表操作表示形式 LinkList(Telem a[],int n) 其功能為：建立一個由 head指向的長度為 n的單鏈表 （ 帶頭結(jié)點(diǎn) ） ， 并使其 n個數(shù)據(jù)元素的值依次等于一維數(shù)組 a中的 n個元素的值 。 74 建表操作處理過程 ? 處理過程： （ 1）建立一個空表； （ 2）生成一個結(jié)點(diǎn)，按從下到上的次序從數(shù)組 a中取出元素作為結(jié)點(diǎn)中的元素值，然后從鏈頭插入該結(jié)點(diǎn)； （ 3）重復(fù)執(zhí)行過程 2直至生成 n個結(jié)點(diǎn)。 int i。 headnext=NULL。i=0。 pdata=a[i]。 headnext=p。 }。 若 1≦ i≦ 表長 ,則返回表中的第 i個數(shù)據(jù)元素 ， 否則返回空元素 NULL。 NIL i el 77 取元素操作程序代碼 template class Telem Telem LinkListTelem::gete(int i) {Node Telem *p。 p= head。 while ((p!=NULL ) amp。 (ji)) {p=pnext。 }。amp。 else return(NULL)。 特殊情形： 1. 當(dāng) i1 時 ,循環(huán)一次也沒有執(zhí)行，執(zhí)行判別語句時 j!=i,返回 NULL； 2. 當(dāng) i＝ 1 時 ,循環(huán)一次也沒有執(zhí)行，但 p指向第一個節(jié)點(diǎn) , j＝ i,返回第一個節(jié)點(diǎn)的元素值 ； 3. 當(dāng) i表長時 ,p=NULL,返回 NULL； 78 求長度操作 int leng()。 其處理過程為： (1)使指針 p指向第一個元素的結(jié)點(diǎn) ， 計(jì)數(shù)值初態(tài) 。 (3)返回計(jì)數(shù)值 。int j。 j=0。 j=j+1。 return j。 79 定位操作 int loct(Telemamp。 其處理過程為： (1)使指針 p指向第一個元素的結(jié)點(diǎn) ， 計(jì)數(shù)值初態(tài) 。 (3)若查到則返回計(jì)數(shù)值否則返回 0。 el) {Node Telem *p。 Telem data。 j=1。 if (data==el) break。 j=j+1。 if (p!=NULL ) return(j)。 }。 el i1 i 81 插入操作表示形式 bool inst (int loc,Telemamp。 該函數(shù)的功能為：在帶頭結(jié)點(diǎn)的單鏈表中的第 loc號結(jié)點(diǎn)之前插入數(shù)據(jù)元素值為 el的新結(jié)點(diǎn) ，該操作的處理過程為： (1)尋找第 loc－ 1個結(jié)點(diǎn) ， 使指針 p指向該結(jié)點(diǎn) 。 82 插入操作 ? 處理過程： （ 1） 尋找第 loc