2第2章：線性表

1、第第2 2章章 線性表線性表 Slide. 2 - 1D.S. & A.2013秋秋2.1 抽象數(shù)據(jù)型線性表抽象數(shù)據(jù)型線性表2.2 線性表的實(shí)現(xiàn)線性表的實(shí)現(xiàn)2.3 棧（棧（Stack）2.4 隊(duì)列（隊(duì)列（Queue）實(shí)驗(yàn)一：多項(xiàng)式的代數(shù)運(yùn)算實(shí)驗(yàn)一：多項(xiàng)式的代數(shù)運(yùn)算2.5 串（串（String）2.6 數(shù)組（數(shù)組（Array）2.7 廣義表廣義表(Lists)第第2章章 線性表（線性表（Liner List）第第2 2章章 線性表線性表 Slide. 2 - 2D.S. & A.2013秋秋2.1 抽象數(shù)據(jù)型線性表抽象數(shù)據(jù)型線性表 定義定義 線性表是由線性表是由n(n0)n(n0)個(gè)相同類型的元

2、素組成的有序集合。個(gè)相同類型的元素組成的有序集合。 記為：記為： ( a( a1 1,a,a2 2,a,a3 3, ,a ai-1i-1,a,ai i,a,ai+1i+1, , a an n ) )其中：其中： n為線性表中元素個(gè)數(shù)，稱為線性表的長度；為線性表中元素個(gè)數(shù)，稱為線性表的長度； 當(dāng)當(dāng)n=0時(shí)，為空表，記為（時(shí)，為空表，記為（ ）。）。 ai為線性表中的元素，類型定義為為線性表中的元素，類型定義為elementtype a1為表中第為表中第1個(gè)元素，無前驅(qū)元素；個(gè)元素，無前驅(qū)元素；an為表中最后一個(gè)為表中最后一個(gè) 元素，無后繼元素；對(duì)于元素，無后繼元素；對(duì)于ai-1,ai,ai+1(

3、1in)，稱，稱ai-1 為為ai的直接前驅(qū)，的直接前驅(qū)，ai+1為為ai的直接后繼。的直接后繼。 線性表是有限的，也是有序的。線性表是有限的，也是有序的。第第2 2章章 線性表線性表 Slide. 2 - 3D.S. & A.2013秋秋線性表線性表 LIST = ( D , R)D = ai | ai Elementset , i = 1, 2, , n, n 0 R = H H = | ai-1, ai D , i = 2 , , n 操作：操作：設(shè)設(shè)L的型為的型為LIST線性表實(shí)例，線性表實(shí)例，x 的型為的型為elementtype的元素的元素 實(shí)例，實(shí)例，p 為位置變量。所有操作描述

4、為：為位置變量。所有操作描述為： INSERT(x, p, L) LOCATE(x, L) RETRIEVE(p, L) DELETE(p, L) PREVIOUS(p, L), NEXT(p, L) MAKENULL( L) FIRST( L)數(shù)學(xué)模型數(shù)學(xué)模型第第2 2章章 線性表線性表 Slide. 2 - 4D.S. & A.2013秋秋舉例：舉例：設(shè)計(jì)函數(shù)設(shè)計(jì)函數(shù) DELEVAL（LIST &L, elementtype d) 其功能其功能 為刪除為刪除 L 中所有值為中所有值為 d 的元素。的元素。 Void DELEVAL( LIST &L, elementtype d ) pos

5、ition p ; p = FIRST( L ) ; while ( P != END( L ) ) if ( same( RETRIEVE( p, L ), d ) ) DELETE(p, L ) ; else p = NEXT(p, L ) ; 第第2 2章章 線性表線性表 Slide. 2 - 5D.S. & A.2013秋秋2.2 線性表的實(shí)現(xiàn)線性表的實(shí)現(xiàn)問題：確定數(shù)據(jù)結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）實(shí)現(xiàn)問題：確定數(shù)據(jù)結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）實(shí)現(xiàn)型型LIST，并在此基礎(chǔ)上，并在此基礎(chǔ)上 實(shí)現(xiàn)各個(gè)基本操作。實(shí)現(xiàn)各個(gè)基本操作。存儲(chǔ)結(jié)構(gòu)的三種方式：存儲(chǔ)結(jié)構(gòu)的三種方式： 連續(xù)的存儲(chǔ)空間（數(shù)組）連續(xù)的存儲(chǔ)空間（數(shù)組）

6、靜態(tài)存儲(chǔ)靜態(tài)存儲(chǔ) 非連續(xù)存儲(chǔ)空間非連續(xù)存儲(chǔ)空間指針（鏈表）指針（鏈表） 動(dòng)態(tài)存儲(chǔ)動(dòng)態(tài)存儲(chǔ) 游標(biāo)（連續(xù)存儲(chǔ)空間游標(biāo)（連續(xù)存儲(chǔ)空間+動(dòng)態(tài)管理思想）動(dòng)態(tài)管理思想） 靜態(tài)鏈表靜態(tài)鏈表2.2.1 指針和游標(biāo)指針和游標(biāo)指針：地址量，其值為另一存儲(chǔ)空間的地址；指針：地址量，其值為另一存儲(chǔ)空間的地址；游標(biāo)：整型量，其值為數(shù)組的下標(biāo)，用以表示指定元素游標(biāo)：整型量，其值為數(shù)組的下標(biāo)，用以表示指定元素 的的“地址地址” 或或 “位置位置”第第2 2章章 線性表線性表 Slide. 2 - 6D.S. & A.2013秋秋2.2.2 線性表的數(shù)組實(shí)現(xiàn)線性表的數(shù)組實(shí)現(xiàn) 第第1個(gè)元素個(gè)元素第第2個(gè)元素個(gè)元素 最后最后1個(gè)

7、元素個(gè)元素012maxlength-1last表表空單元空單元圖圖2-1 線性表的數(shù)組實(shí)現(xiàn)線性表的數(shù)組實(shí)現(xiàn)表的最大長度表的最大長度 第第 i 個(gè)元素個(gè)元素1 i last類型定義：類型定義：# define maxlength 100struct LIST elementtype datamaxlength; int last;位置類型：位置類型： typedef int position;線性表線性表 L: LIST L;第第2 2章章 線性表線性表 Slide. 2 - 7D.S. & A.2013秋秋操作：操作： Void INSERT ( elementtype x, position

8、 p, LIST &L) position q ; if (L.last = maxlength 1) error( “ 表滿表滿 ” ) ； else if ( P L.last +1 ) | ( p = p; q - ) L.data q + 1 = L.data q ; L.last = L.last + 1 ; L.data p = x ; 第第2 2章章 線性表線性表 Slide. 2 - 8D.S. & A.2013秋秋 position LOCATE ( elementtype x , LIST L ) position q ; for ( q = 1; q L.last ) e

9、rror( “指定元素不存在指定元素不存在” ) ; else return ( L.data p ) ; 第第2 2章章 線性表線性表 Slide. 2 - 9D.S. & A.2013秋秋 Void DELETE( position p , LIST &L) position q ; if ( ( p L.last ) | ( p 1 ) ) error ( “指定位置不存在指定位置不存在” ) ； else L.last = L.last 1; for ( q = p ; q = L.last ; q + ) L.data q = L.data q + 1 ; position PREV

10、IOUS( position p , LIST L ) if ( ( p L.last ) ) error ( “前驅(qū)元素不存在前驅(qū)元素不存在” ) ; else return ( p 1 ); 第第2 2章章 線性表線性表 Slide. 2 - 10D.S. & A.2013秋秋 position END( LIST L ) return( L.last + 1 ); position FIRST( LIST L ) return ( 1 ); position NEXT( position p , LIST L ) if ( ( p = L.last ) ) error ( “前驅(qū)元素不存

11、在前驅(qū)元素不存在” ) ; else return ( p + 1 ); position MAKENULL( LIST &L ) L.last = 0 ; return ( L.last +1 ); 第第2 2章章 線性表線性表 Slide. 2 - 11D.S. & A.2013秋秋2.2.3 線性表的指針實(shí)現(xiàn)線性表的指針實(shí)現(xiàn)結(jié)點(diǎn)形式結(jié)點(diǎn)形式data next結(jié)點(diǎn)信息結(jié)點(diǎn)信息下一結(jié)點(diǎn)地址下一結(jié)點(diǎn)地址NODE結(jié)點(diǎn)類型結(jié)點(diǎn)類型struct NODE elementtype data ; struct NODE *next ; ;typedef NODE *LIST;typedef NODE *

12、position;LIST header ;position p , q;a1a2a3anheaderqpa2: ( *p ).data ; q: ( *p ).next ; a2: p-data ; q: p-next ;記法記法:第第2 2章章 線性表線性表 Slide. 2 - 12D.S. & A.2013秋秋操作討論：操作討論：插入元素插入元素:pa1xheaderqai-1aixpqanxqp(a) 表頭插入元素表頭插入元素(b) 中間插入元素中間插入元素(c) 表尾插入元素表尾插入元素q = new NODE ;q-data = x ;q-next = p-next ;pnext

13、 = q ;或或:temp = p-next ;P-next = new NODE ;P-next-data = x ;P-next-next = temp ;討論表頭結(jié)點(diǎn)的作用討論表頭結(jié)點(diǎn)的作用第第2 2章章 線性表線性表 Slide. 2 - 13D.S. & A.2013秋秋操作討論：操作討論：刪除元素刪除元素:q = p-next ;P-next = q-next ;delete q ;或：或：q = p-next ;P-next = p-next-next ;delete q ;討論結(jié)點(diǎn)討論結(jié)點(diǎn) ai 的位置的位置 pa1header(a) 刪除第一個(gè)元素刪除第一個(gè)元素a2qpai-

14、1aipq(b) 刪除中間元素刪除中間元素ai+1anan-1qp(c) 刪除表尾元素刪除表尾元素第第2 2章章 線性表線性表 Slide. 2 - 14D.S. & A.2013秋秋ADT操作：操作： position END ( LIST ) position q ; q = L ; while ( qnext != NULL ) q = qnext ; return ( q ) ; ; Void INSERT ( elementtype x, position p, LIST &L ) position q ; q = new NODE ; q data = x ; q next = p

15、 next ; p next = q ; 第第2 2章章 線性表線性表 Slide. 2 - 15D.S. & A.2013秋秋 position LOCATE ( elementtype x, LIST L ) position p ; p = L ; while ( pnext != NULL ) if ( pnextdata = x ) return p ; else p = pnext ; return p ; elementtype RETRIEVE ( position p , LIST L ) return ( p next data ); 第第2 2章章 線性表線性表 Slid

16、e. 2 - 16D.S. & A.2013秋秋 Void DELETE ( position p, LIST &L ) position q ; if ( pnext != NULL ) q = p next ; p next = q next ; delete q ; ; position PREVIOUS ( position p, LIST L ) position q ; if ( p = Lnext ) error ( “不存在前驅(qū)元素不存在前驅(qū)元素” ) ； else q = L ; while ( qnext != p ) q = qnext ; return q ; 第第2

17、2章章 線性表線性表 Slide. 2 - 17D.S. & A.2013秋秋 position NEXT ( position p, LIST L ) position q ; if ( pnext = NULL ) error ( “不存在后繼元素不存在后繼元素” ) ； else q = pnext; return q ; position MAKENULL ( LIST &L ) L = new NODE ; Lnext = NULL; return L ; 第第2 2章章 線性表線性表 Slide. 2 - 18D.S. & A.2013秋秋 position FIRST ( LIS

18、T L ) return L; 舉例：舉例：遍歷線性鏈表，按照線性表中遍歷線性鏈表，按照線性表中元素的順序，依次訪問表中的元素的順序，依次訪問表中的每一個(gè)元素，每個(gè)元素只能被每一個(gè)元素，每個(gè)元素只能被訪問一次。訪問一次。Void VISITE( LIST L ) position p ; p = Lnext ; while ( p != NULL) cout pdata ; p = pnext ; 第第2 2章章 線性表線性表 Slide. 2 - 19D.S. & A.2013秋秋線性表線性表 靜態(tài)存儲(chǔ)靜態(tài)存儲(chǔ) 與與 動(dòng)態(tài)存儲(chǔ)的動(dòng)態(tài)存儲(chǔ)的 比較比較比較參數(shù)比較參數(shù)表的容量表的容量存取操作存取

19、操作時(shí)間時(shí)間空間空間鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)靈活，易擴(kuò)充靈活，易擴(kuò)充順序存取順序存取訪問元素費(fèi)時(shí)間訪問元素費(fèi)時(shí)間實(shí)際長度，節(jié)省空間實(shí)際長度，節(jié)省空間順序存儲(chǔ)順序存儲(chǔ)固定，不易擴(kuò)充固定，不易擴(kuò)充隨機(jī)存取隨機(jī)存取插入刪除費(fèi)時(shí)間插入刪除費(fèi)時(shí)間估算表長度，浪費(fèi)空間估算表長度，浪費(fèi)空間第第2 2章章 線性表線性表 Slide. 2 - 20D.S. & A.2013秋秋2.2.4 線性表的游標(biāo)實(shí)現(xiàn)線性表的游標(biāo)實(shí)現(xiàn)結(jié)點(diǎn)形式結(jié)點(diǎn)形式data next結(jié)點(diǎn)信息結(jié)點(diǎn)信息下一結(jié)點(diǎn)位置下一結(jié)點(diǎn)位置spacestr結(jié)點(diǎn)類型結(jié)點(diǎn)類型struct spacestr elementtype data ; int next ; ;線

20、性表：線性表：spacestr SPACE maxsize ;typedef int position;元素：元素：SPACE i .data “型型”為為elementtype( 基本、復(fù)合基本、復(fù)合)下一元素位置：下一元素位置：SPACE i .next “型型”為為 int類似指針鏈表，對(duì)游標(biāo)實(shí)現(xiàn)的線性表仍設(shè)表頭結(jié)點(diǎn)。類似指針鏈表，對(duì)游標(biāo)實(shí)現(xiàn)的線性表仍設(shè)表頭結(jié)點(diǎn)。第第2 2章章 線性表線性表 Slide. 2 - 21D.S. & A.2013秋秋d65c-1-0 a108e-1-4-1-11b21210123456789101112SPACE73LM9available線性表：線性表：

21、 L = ( a, b, c ) L = 7M = ( d, e ) M = 3空閑表：空閑表：available = 9q = new spacestr ; q = SPACEavailable.next ; SPACEavailable.next = SPACE q .next ;delete q ; SPACE q .next = SPACEavailable.next ; SPACEavailable.next = q ;第第2 2章章 線性表線性表 Slide. 2 - 22D.S. & A.2013秋秋 Void INSERT ( elementtype x, position p

22、, spacestr *SPACE ) position q ; q = new spacestr ; SPACE q .data = x ; SPACE q .next = SPACE p .next ; SPACE p .next = q ; Void DELETE ( position p, spacestr *SPACE ) position q ; if ( SPACE p .next != -1 ) SPACE q = SPACE p .next ; SPACE p .next = SPACE q .next ; delete q ; ;操作：操作：第第2 2章章 線性表線性表 S

23、lide. 2 - 23D.S. & A.2013秋秋2.2.5 雙向鏈表雙向鏈表結(jié)點(diǎn)形式結(jié)點(diǎn)形式datanext結(jié)點(diǎn)信息結(jié)點(diǎn)信息后繼結(jié)點(diǎn)指針后繼結(jié)點(diǎn)指針dcelltypeprevious前驅(qū)結(jié)點(diǎn)指針前驅(qū)結(jié)點(diǎn)指針結(jié)點(diǎn)類型結(jié)點(diǎn)類型 struct dnodetype elementtype data ; dnodetype *next, *previous ; ;typedef dnodetype *DLIST ;typedef dnodetype *position ;ai-1 a i ai+1 p刪除位置刪除位置p的元素：的元素：ppreviousnext = pnext;pnextprevi

24、ous = pprevious ; header a n tail第第2 2章章 線性表線性表 Slide. 2 - 24D.S. & A.2013秋秋操作：操作：Void INSERT( elementtype x, position p, DLIST &L ) ； position q ; q = new dnodetype ; qdata = x ; Ppreviousnext = q ; qprevious = pprevious ; qnext = p ; pprevious = q ; ;討論：元素的位置？討論：元素的位置？第第2 2章章 線性表線性表 Slide. 2 - 25D

25、.S. & A.2013秋秋2.2.6 環(huán)形鏈表環(huán)形鏈表單向線性鏈表單向線性鏈表雙向線性鏈表雙向線性鏈表單向循環(huán)鏈表單向循環(huán)鏈表雙向循環(huán)鏈表雙向循環(huán)鏈表對(duì)線性鏈表的改進(jìn)，對(duì)線性鏈表的改進(jìn)，解決解決“單向操作單向操作”的的問題；改進(jìn)后的鏈問題；改進(jìn)后的鏈表，能夠從任意位表，能夠從任意位置元素開始，訪問置元素開始，訪問表中的每一個(gè)元素。表中的每一個(gè)元素。單向環(huán)形鏈表：單向環(huán)形鏈表：a1a2a3anR 其結(jié)構(gòu)與單向線性鏈表相同，用表尾指針標(biāo)識(shí)鏈表，從其結(jié)構(gòu)與單向線性鏈表相同，用表尾指針標(biāo)識(shí)鏈表，從而省去了表頭結(jié)點(diǎn)。而省去了表頭結(jié)點(diǎn)。 表頭：表頭：Rnext ( 亦即表中的一個(gè)元素亦即表中的一個(gè)元素a

26、1 )第第2 2章章 線性表線性表 Slide. 2 - 26D.S. & A.2013秋秋操作：操作：在表左端插入結(jié)點(diǎn)在表左端插入結(jié)點(diǎn)INSERT(x,FIRST(R),R); LINSERT(x,R) Void LINSERT( elementtype x , LIST &R ) celltype *p ; p = new NODE ; pdata = x ; if ( R = NULL ) pnext = p ; R = p ; else pnext = Rnext ; Rnext = p ; ;在表右端插入結(jié)點(diǎn)在表右端插入結(jié)點(diǎn)INSERT(x,END(R),R); RINSERT(x,

27、R) Void RINSERT( elementtype x , LIST R ) LINSERT ( x , R ) ; R = Rnext ; 第第2 2章章 線性表線性表 Slide. 2 - 27D.S. & A.2013秋秋 從表左端刪除結(jié)點(diǎn)從表左端刪除結(jié)點(diǎn)DELETE(FIRST(R),R); LDELETE(R) Void LDELETE( LIST &R ) struct NODE *p ; if ( R = NULL ) error ( “空表空表” ); else p = Rnext ; Rnext = pnext ; if ( p = R ) R=NULL; delete

28、 p ; ;第第2 2章章 線性表線性表 Slide. 2 - 28D.S. & A.2013秋秋雙向環(huán)形鏈表：雙向環(huán)形鏈表： a1 ai an R 雙向環(huán)形鏈表的結(jié)構(gòu)與雙向連表結(jié)構(gòu)相同，只是將表頭元素雙向環(huán)形鏈表的結(jié)構(gòu)與雙向連表結(jié)構(gòu)相同，只是將表頭元素的空的空previous域指向表尾，同時(shí)將表尾的空域指向表尾，同時(shí)將表尾的空next域指向表頭結(jié)點(diǎn)，域指向表頭結(jié)點(diǎn)，從而形成向前和向后的兩個(gè)環(huán)形鏈表，對(duì)鏈表的操作變得更加靈從而形成向前和向后的兩個(gè)環(huán)形鏈表，對(duì)鏈表的操作變得更加靈活?；睢５诘? 2章章 線性表線性表 Slide. 2 - 29D.S. & A.2013秋秋a1a2a3anRana

29、n-1an-2a1RVoid REVERS( LIST &R ) position p, q; p = Rnext ; Rnext = pnext ; pnext = p ; while ( R != NULL ) q = Rnext ; Rnext = qnext ; qnext = pnext ; pnext = q ; R = p ; ；算法如下：算法如下：舉例：舉例：設(shè)計(jì)算法，將一個(gè)單向環(huán)形鏈表反向。頭元素變成尾設(shè)計(jì)算法，將一個(gè)單向環(huán)形鏈表反向。頭元素變成尾 元素，尾元素變成新的頭元素，依次類推。元素，尾元素變成新的頭元素，依次類推。第第2 2章章 線性表線性表 Slide. 2 -

30、30D.S. & A.2013秋秋2.3 棧（棧（Stack） 棧是線性表的一種特殊形式，是一種限定性數(shù)據(jù)結(jié)構(gòu)，棧是線性表的一種特殊形式，是一種限定性數(shù)據(jù)結(jié)構(gòu)，也就是在對(duì)線性表的操作加以限制后，形成的一種新的數(shù)也就是在對(duì)線性表的操作加以限制后，形成的一種新的數(shù)據(jù)結(jié)構(gòu)。據(jù)結(jié)構(gòu)。定義：定義：是限定只在表尾進(jìn)行是限定只在表尾進(jìn)行插入和刪除操作的線性表。插入和刪除操作的線性表。 棧又稱為后進(jìn)先出棧又稱為后進(jìn)先出(Last In First Out )的線性表。的線性表。 簡稱簡稱LIFO結(jié)構(gòu)。結(jié)構(gòu)。棧舉例棧舉例a1a2an-1anInsertDeletetopbottom棧底棧底棧頂棧頂棧示意圖棧示意

31、圖第第2 2章章 線性表線性表 Slide. 2 - 31D.S. & A.2013秋秋棧的基本棧的基本 MAKENULL ( S )操作操作 TOP ( S ) POP ( S ) PUSH ( x , S ) EMPTY ( S ) 例例2：利用棧實(shí)現(xiàn)行編輯處理。利用棧實(shí)現(xiàn)行編輯處理。設(shè)定符號(hào)設(shè)定符號(hào)“#”為擦訖符，用以刪為擦訖符，用以刪除除“#”前的字符；符號(hào)前的字符；符號(hào)“”為刪為刪行符，用以刪除當(dāng)前編輯行。行符，用以刪除當(dāng)前編輯行。原理：原理： 一般字符進(jìn)棧；一般字符進(jìn)棧；讀字符讀字符 擦訖符退棧；擦訖符退棧； 刪行符則清棧刪行符則清棧算法：算法：Void LINEEDIT( ) S

32、TACK ；char c ; MAKENULL ( S ); c = getchar ( ) ; while ( c != n ) if ( c = # ) POP ( S ); else if ( c = ) MAKENULL ( S ); else PUSH ( c , S ); c = getchar( ); 逆序輸出棧中所有元素；逆序輸出棧中所有元素；第第2 2章章 線性表線性表 Slide. 2 - 32D.S. & A.2013秋秋1、順序存儲(chǔ)、順序存儲(chǔ)順序棧示意圖anaia3a2a1-maxlength-13210top結(jié)構(gòu)類型：結(jié)構(gòu)類型： typedef struct elem

33、enttype datamaxlength; int top ; STACK ;STACK S ;棧的容量：棧的容量：maxlength 1 ;?？眨簵？眨篠.top = 0 ;棧滿：棧滿：S.top = maxlength 1 ;棧頂元素：棧頂元素：S.data S.top ;第第2 2章章 線性表線性表 Slide. 2 - 33D.S. & A.2013秋秋操作：操作： Void MAKENULL( STACK &S ) S.top = 0 ; ; Boolean EMPTY( STACK S ) if ( S.top 1 ) return TRUE else return FALSE

34、; ; elementtype TOP( STACK S ) if EMPTY( S ) return NULL; else return ( S.data S.top ); ;第第2 2章章 線性表線性表 Slide. 2 - 34D.S. & A.2013秋秋操作：操作： elementtype POP( STACK &S ) if ( EMPTY (S ) ) error ( “棧空?？铡?) ; else S.top = S.top 1 ; ; Void PUSH ( elementtype x, STACK &S ) if ( S.top = maxlength - 1 ) erro

35、r ( “棧滿棧滿” ) ; else S.top = S.top + 1 ; S.data S.top = x ; ;第第2 2章章 線性表線性表 Slide. 2 - 35D.S. & A.2013秋秋2、鏈?zhǔn)酱鎯?chǔ)、鏈?zhǔn)酱鎯?chǔ) 采用由指針形成的線性鏈表來實(shí)現(xiàn)棧采用由指針形成的線性鏈表來實(shí)現(xiàn)棧的存儲(chǔ)的存儲(chǔ),要考慮鏈表的哪一端實(shí)現(xiàn)元素的插要考慮鏈表的哪一端實(shí)現(xiàn)元素的插入和刪除比較方便。入和刪除比較方便。 實(shí)現(xiàn)的方式如右圖所示，其操作與線實(shí)現(xiàn)的方式如右圖所示，其操作與線性鏈表的表頭插入和刪除元素相同。性鏈表的表頭插入和刪除元素相同。 anan-1a2a1top3、多個(gè)棧共用一個(gè)存儲(chǔ)空間的討論、多個(gè)

36、棧共用一個(gè)存儲(chǔ)空間的討論STACK maxlength bot1top1bot2top2bot3top3top2botntopn 0Maxlength-1botn+1botitopi第第2 2章章 線性表線性表 Slide. 2 - 36D.S. & A.2013秋秋Int Is_Stack_i_Full ( STACK S , int bot , int top , int i )/* 判斷第判斷第 i 個(gè)棧是否滿，滿返回個(gè)棧是否滿，滿返回1，否則返回，否則返回0 */ Void Move_Stack_i ( STACK &S , int &bot , int& top , int i ,

37、int dt )/* 移動(dòng)第移動(dòng)第 i 個(gè)棧，個(gè)棧，dt 為位移量為位移量 */ 第第2 2章章 線性表線性表 Slide. 2 - 37D.S. & A.2013秋秋Call B 主程序主程序ACall C 主程序主程序BCall D 主程序主程序Ci 主程序主程序DBeginEndDaDaDbDcDb Dc棧棧入棧入棧出棧出棧例例1：子程序的嵌套調(diào)用：子程序的嵌套調(diào)用2.3.2 棧的應(yīng)用棧的應(yīng)用1、棧和遞歸過程、棧和遞歸過程第第2 2章章 線性表線性表 Slide. 2 - 38D.S. & A.2013秋秋調(diào)用B 調(diào)用C調(diào)用BABC棧調(diào)用B 調(diào)用C調(diào)用BABC棧調(diào)用B 調(diào)用C調(diào)用BABC

38、棧A的返回點(diǎn)(1) 子程序A正在執(zhí)行(2) A調(diào)用B，B在執(zhí)行(3) B調(diào)用C，C在執(zhí)行先進(jìn)先出的規(guī)則：先進(jìn)先出的規(guī)則： 在執(zhí)行的任何點(diǎn)處，若一個(gè)程序要將控制返回到調(diào)用程序，則該程序一定是最末一個(gè)進(jìn)入的。例例2：間接遞歸：間接遞歸3個(gè)程序A、B、C，其中A調(diào)用B，B調(diào)用C，而C又遞歸調(diào)用B。第第2 2章章 線性表線性表 Slide. 2 - 39D.S. & A.2013秋秋調(diào)用B 調(diào)用C調(diào)用BABC棧調(diào)用B 調(diào)用C調(diào)用BABC棧(6) C返回到B，（第一次調(diào)用） B在執(zhí)行，C執(zhí)行完畢成(5) B返回到C，C在執(zhí)行對(duì)B的遞歸調(diào)用完畢調(diào)用B 調(diào)用C調(diào)用BABC棧(7) B返回到A，A在執(zhí)行，非遞

39、歸 調(diào)用B完畢調(diào)用B 調(diào)用C調(diào)用BABC棧(4) C遞歸調(diào)用B，,B在執(zhí)行第第2 2章章 線性表線性表 Slide. 2 - 40D.S. & A.2013秋秋Sub ACall ADa1 Da2 Da3Dan-1Da1Da2Da3Dan-1DanDanBeginEnd例例3：直接遞歸：直接遞歸第第2 2章章 線性表線性表 Slide. 2 - 41D.S. & A.2013秋秋2、迷宮求解、迷宮求解問題：問題：0 1 0 0 0 1 1 0 0 0 1 1 1 1 11 0 0 0 1 1 0 1 1 1 0 0 1 1 10 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1

40、0 1 1 1 1 0 1 1 0 1 1 0 01 1 0 1 0 0 1 0 1 1 1 1 1 1 10 0 1 1 0 1 1 1 0 1 0 0 1 1 10 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 11 1 0 0 0 1 1 0 1 1 0 0 0 0 00 0 1 1 1 1 1 0 0 0 1 1 1 1 0 0 1 0 0 1 1 1 1 1 0 1 1 1 1 0 一個(gè)迷宮可用上圖所示方陣一個(gè)迷宮可用上圖所示方陣m,n表示，表示，0表示能通過，表示能通過，1 表表示不能通過?，F(xiàn)假設(shè)耗子從左上角示不能通

41、過?，F(xiàn)假設(shè)耗子從左上角1,1進(jìn)入迷宮，編寫算法，尋進(jìn)入迷宮，編寫算法，尋求一條從右下角求一條從右下角 m,n 出去的路徑。出去的路徑。1115m n出口入口*迷宮示例第第2 2章章 線性表線性表 Slide. 2 - 42D.S. & A.2013秋秋2、迷宮求解、迷宮求解分析：分析： 迷宮可用二維數(shù)組迷宮可用二維數(shù)組Mazeij (1im, 1jn)表示，入口表示，入口maze11 = 0 ;耗子在任意位置可用（耗子在任意位置可用（i, j）坐標(biāo)表示；坐標(biāo)表示； 位置位置 ( i, j) 周圍有周圍有8個(gè)方個(gè)方 向可以走通，分別記為：向可以走通，分別記為：E,SE,S,SW,W,NW,N,N

42、E;如圖所如圖所 示。方向示。方向 v 按從正東開始且順時(shí)針分別記為按從正東開始且順時(shí)針分別記為1-8，v=1,8; 設(shè)設(shè) 二維數(shù)組二維數(shù)組 move 記下八個(gè)方位的增量；記下八個(gè)方位的增量； i,jN:( i-1, j)NE:(i-1, j+1)E:( i, j+1)SE:( i+1, j+1)S:( i+1, j)SW:(i+1, j-1)W:(i, j-1)NW:(i-1, j-1)ji第第2 2章章 線性表線性表 Slide. 2 - 43D.S. & A.2013秋秋從從( i , j ) 到到 ( g , h )且且 v = 2 ( 東南）則東南）則有：有： g = i + mov

43、e v 1 = i + 1 ; h = j + move v 2 = j + 1 ;V i j 說明說明1 0 1 E2 1 1 SE3 1 0 S4 1 -1 SW5 0 -1 W6 -1 -1 NW7 -1 0 N8 -1 1 NE 為避免時(shí)時(shí)監(jiān)測(cè)邊界狀態(tài)，可把二維數(shù)組為避免時(shí)時(shí)監(jiān)測(cè)邊界狀態(tài)，可把二維數(shù)組maze1:m, 1:n擴(kuò)大擴(kuò)大 為為maze0:m+1, 0:n+1，且令且令0行和行和0列、列、m+1行和行和n+1列的值為列的值為1；出口入口*迷宮示例第第2 2章章 線性表線性表 Slide. 2 - 44D.S. & A.2013秋秋 采用試探的方法，當(dāng)?shù)竭_(dá)某個(gè)位置且周圍八個(gè)方向

44、走不通時(shí)采用試探的方法，當(dāng)?shù)竭_(dá)某個(gè)位置且周圍八個(gè)方向走不通時(shí) 需要回退到上一個(gè)位置，并換一個(gè)方向繼續(xù)試探；為解決回需要回退到上一個(gè)位置，并換一個(gè)方向繼續(xù)試探；為解決回 退問題，需設(shè)一個(gè)棧，當(dāng)?shù)竭_(dá)一個(gè)新位置時(shí)將（退問題，需設(shè)一個(gè)棧，當(dāng)?shù)竭_(dá)一個(gè)新位置時(shí)將（i, j,v）進(jìn)棧，）進(jìn)棧， 回退時(shí)退棧?；赝藭r(shí)退棧。 每次換方向?qū)ふ倚挛恢脮r(shí)，需測(cè)試該位置以前是否已經(jīng)經(jīng)過，每次換方向?qū)ふ倚挛恢脮r(shí)，需測(cè)試該位置以前是否已經(jīng)經(jīng)過， 對(duì)已到達(dá)的位置，不能重復(fù)試探，為此設(shè)矩陣對(duì)已到達(dá)的位置，不能重復(fù)試探，為此設(shè)矩陣mark，其初值，其初值 為為0，一旦到達(dá)位置，一旦到達(dá)位置( i , j )時(shí)，置時(shí)，置 marki

45、j = 1;文字描述算法：文字描述算法： 耗子在耗子在(1, 1)進(jìn)入迷宮，并向正東（進(jìn)入迷宮，并向正東（v=1）方向試探。）方向試探。 檢測(cè)下一方位檢測(cè)下一方位(g, h)。若。若(g, h)=(m, n)且且mazemn=0，則耗子到達(dá)出口，輸出，則耗子到達(dá)出口，輸出 走過的路徑；程序結(jié)束。走過的路徑；程序結(jié)束。 若若(g, h) (m, n),但但(g, h)方位能走通且第一次經(jīng)過方位能走通且第一次經(jīng)過,則記下這一步，并從則記下這一步，并從(g, h) 出發(fā)，再向東試探下一步。否則仍在出發(fā)，再向東試探下一步。否則仍在(i, j)方位換一個(gè)方向試探。方位換一個(gè)方向試探。 若若(i, j)方

46、位周圍方位周圍8個(gè)方位阻塞或已經(jīng)過，則需退一步，并換一個(gè)方位試探。個(gè)方位阻塞或已經(jīng)過，則需退一步，并換一個(gè)方位試探。 若若(i, j)=(1, 1)則到達(dá)入口，說明迷宮走不通。則到達(dá)入口，說明迷宮走不通。第第2 2章章 線性表線性表 Slide. 2 - 45D.S. & A.2013秋秋Void GETMAZE ( maze , mark ,move ,S ) (i, j, v) = (1,1,1) ; mark11 = 1 ; s.top = 0 ; do g = i+movev1 ; h = j+movev2 ; if ( g = m) & ( h = n) & (mazemn = 0

47、) output( S ) ; return ; if (mazegh =0) & markgh = 0) markgh = 1 ; PUSH( i, j, v, S) ; (i, j, v) = (g, h, 1) ; else if ( v 0 ) ( i, j, v ) = POP( S ) ; ; while ( s.top ) & ( v != 8 ) ; cout : d = attch( pcoef, pexp, d );第第2 2章章 線性表線性表 Slide. 2 - 62D.S. & A.2013秋秋 p = plink ; break ; case : d = attch

48、( qcoef, qexp, d ) ; q = qlink ; break ; while ( p != NULL ) d = attch( pcoef, pexp, d ) ; p = plink ; while ( q !=NULL ) d = attch( qcoef, qexp, d ) ; q = qlink ; dlink = NULL ; p = c ; c = clink ; delete p ; return c ;第第2 2章章 線性表線性表 Slide. 2 - 63D.S. & A.2013秋秋2.5 串串( String ) 串是線性表的一種特殊形式，表中每個(gè)元素的

49、類型為字符型，串是線性表的一種特殊形式，表中每個(gè)元素的類型為字符型，是一個(gè)有限的字符序列。是一個(gè)有限的字符序列。 串的基本形式可表示成：串的基本形式可表示成：S = a1a2a3an ； 其中：其中： char ai ； 0 i n ；n 0 ； 當(dāng)當(dāng) n = 0 時(shí)，為空串。時(shí)，為空串。 n 為串的長度為串的長度 ；C 語言中串有兩種實(shí)現(xiàn)方法：語言中串有兩種實(shí)現(xiàn)方法： 1、字符數(shù)組，如：、字符數(shù)組，如：char str110 ； 2、字符指針，如：、字符指針，如：char *str2 ；操作：操作：string NULL( ) ;boolean ISNULL ( S ) ;Void IN(

50、S, a ) ;int LEN( S ) ;Void CONCAT( S1, S2 ) ;string SUBSTR( S, m, n ) ;boolean INDEX( S, S1 ) ;2.5.1 抽象數(shù)據(jù)型串抽象數(shù)據(jù)型串第第2 2章章 線性表線性表 Slide. 2 - 64D.S. & A.2013秋秋例一：將串例一：將串T 插在串插在串S 中第中第 i 個(gè)字符之后個(gè)字符之后INSERT( S, T, i )。Void INSERT( STRING &S, STRING T, int i ) STRING t1, t2 ; if ( ( i LEN( S ) ) error 指定位置不

51、對(duì)指定位置不對(duì) ; else if ( ISNULL( S ) ) S = T ; else if ( ISNULL ( T ) ) t1 = SUBSTR( S, 1, i ) ; t2 = SUBSTR( S, i + 1, LEN( S ) ); S = CONCAT( t1, CONCAT( T, t2 ) ); 第第2 2章章 線性表線性表 Slide. 2 - 65D.S. & A.2013秋秋Void DELETE( STRING &S, STRING T ) STRING t1, t2 ; int m, n ; m = INDEX( S, T ); if ( m=0 ) err

52、or 串串S中不包含子串中不包含子串T ; else n = LEN( T ) ; t1 = SUBSTR( S, 1, m - 1 ) ; t2 = SUBSTR( S, m + n, LEN( S ) ); S = CONCAT( t1, t2); 例二：從串例二：從串 S 中將子串中將子串 T 刪除刪除DELETE( S, T )。第第2 2章章 線性表線性表 Slide. 2 - 66D.S. & A.2013秋秋2.5.2 串的實(shí)現(xiàn)串的實(shí)現(xiàn)1、串的順序存儲(chǔ)、串的順序存儲(chǔ) 采用連續(xù)的存儲(chǔ)空間（數(shù)組），自第一個(gè)元素開始，依次采用連續(xù)的存儲(chǔ)空間（數(shù)組），自第一個(gè)元素開始，依次存儲(chǔ)字符串中的

53、每一個(gè)字符。存儲(chǔ)字符串中的每一個(gè)字符。 char str 10 =“China”； C h i n a 0 0 1 2 3 4 5 6 7 8 9str串的順序存儲(chǔ)串的順序存儲(chǔ)操作：操作：NULL，ISNULL，IN，LEN，CONCAT，SUBSTR，INDEX2、串的鏈?zhǔn)酱鎯?chǔ)、串的鏈?zhǔn)酱鎯?chǔ) 構(gòu)造線性鏈表，構(gòu)造線性鏈表，element類型為類型為char，自第一個(gè)元素開始，依，自第一個(gè)元素開始，依次存儲(chǔ)字符串中的每一個(gè)字符。次存儲(chǔ)字符串中的每一個(gè)字符。第第2 2章章 線性表線性表 Slide. 2 - 67D.S. & A.2013秋秋2、串的鏈?zhǔn)酱鎯?chǔ)、串的鏈?zhǔn)酱鎯?chǔ) i n a C h st

54、r1struct node char data ; node *link ; ;typedef node *STRING1 ;STRING str1 ; struct node char data4 ; node *link ; ;typedef node *STRING2 ;STRING str2 ; C h i n C str2假設(shè)地址量（假設(shè)地址量（link）占用）占用 2 個(gè)字節(jié)個(gè)字節(jié)5/155/12第第2 2章章 線性表線性表 Slide. 2 - 68D.S. & A.2013秋秋int INDEX ( STRING1 S, S1 ) struct node *p, *q, *i

55、; int t ; if ( ( S1 != NULL ) & ( S != NULL ) ) t = 1 ; i = S ; q = S1 ; do if ( pdata = qdata ) q = qlink ; if ( q = NULL ) return( t ) ; p = plink ; else t = t + 1 ; i = ilink ; p = i ; q = S1 ; while ( p != NULL ) ; return 0 ; ;INDEX(S,S1)若若 S1是是S的子串則返回的子串則返回 S1首字符在首字符在S中的位置；中的位置；否則否則 返回返回0；操作：操作

56、：第第2 2章章 線性表線性表 Slide. 2 - 69D.S. & A.2013秋秋2.6 數(shù)組數(shù)組( ARRAY )2.6.1 抽象數(shù)據(jù)型數(shù)組抽象數(shù)據(jù)型數(shù)組 數(shù)組是由下標(biāo)（數(shù)組是由下標(biāo)（index）和值（）和值（value）組成的序?qū)Γ┙M成的序?qū)Γ╥ndex，value）的集合。）的集合。 也可以定義為是由相同類型的數(shù)據(jù)元素組成有限序列。也可以定義為是由相同類型的數(shù)據(jù)元素組成有限序列。 數(shù)組在內(nèi)存中是采用一組連續(xù)的地址空間存儲(chǔ)的，正是數(shù)組在內(nèi)存中是采用一組連續(xù)的地址空間存儲(chǔ)的，正是由于此種原因，才可以實(shí)現(xiàn)下標(biāo)運(yùn)算。由于此種原因，才可以實(shí)現(xiàn)下標(biāo)運(yùn)算。 所有數(shù)組都是一個(gè)一維向量。所有數(shù)組都是

57、一個(gè)一維向量。數(shù)組數(shù)組1：( a1, a2, a3, , ai , , an ) ;數(shù)組數(shù)組2：( a11, , a1n, a21, , a2n, , aij , , am1, , amn ) ; 1im, 1jn ;數(shù)組數(shù)組3: ( a111, , a11n, a121, , a12n, , aijk , , amn1, , amnp ) ; 1 i m, 1 j n , 1 k p ;第第2 2章章 線性表線性表 Slide. 2 - 70D.S. & A.2013秋秋 n 維數(shù)組中含有維數(shù)組中含有 bi 個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素,每個(gè)元素都受著每個(gè)元素都受著 n 個(gè)關(guān)系個(gè)關(guān)系的約束。在每個(gè)關(guān)

58、系中，元素的約束。在每個(gè)關(guān)系中，元素aj1j2jn（0 ji bi-2）都有一個(gè)直接）都有一個(gè)直接后繼元素。后繼元素。i=1n 因此，數(shù)組仍是一種特殊形式的線性表。對(duì)二維數(shù)組可以理因此，數(shù)組仍是一種特殊形式的線性表。對(duì)二維數(shù)組可以理解成一維數(shù)組，其每個(gè)元素又是一個(gè)一維數(shù)組；以此類推，所謂解成一維數(shù)組，其每個(gè)元素又是一個(gè)一維數(shù)組；以此類推，所謂n 維數(shù)組同樣如此。維數(shù)組同樣如此。操作：操作：CREATE （ ）；建立一個(gè)空數(shù)組）；建立一個(gè)空數(shù)組 RETRIEVE（array，index）；返回第）；返回第 index 個(gè)元素個(gè)元素 STORE（array，index，value）；）； 在數(shù)組在

59、數(shù)組array中，為第中，為第index個(gè)元素賦值個(gè)元素賦值value注：由于高級(jí)語言中都提供了數(shù)組，本課略去操作。注：由于高級(jí)語言中都提供了數(shù)組，本課略去操作。第第2 2章章 線性表線性表 Slide. 2 - 71D.S. & A.2013秋秋2.6.2 數(shù)組的實(shí)現(xiàn)數(shù)組的實(shí)現(xiàn)1、數(shù)組的順序存儲(chǔ)、數(shù)組的順序存儲(chǔ) 數(shù)組的順序表示，指的是在計(jì)算機(jī)中，用一組連續(xù)的存數(shù)組的順序表示，指的是在計(jì)算機(jī)中，用一組連續(xù)的存儲(chǔ)單元來實(shí)現(xiàn)數(shù)組的存儲(chǔ)。目前的高級(jí)程序設(shè)計(jì)語言都是這儲(chǔ)單元來實(shí)現(xiàn)數(shù)組的存儲(chǔ)。目前的高級(jí)程序設(shè)計(jì)語言都是這樣實(shí)現(xiàn)的。樣實(shí)現(xiàn)的。兩種存儲(chǔ)方式：兩種存儲(chǔ)方式： 一是按行存儲(chǔ)（一是按行存儲(chǔ)（C語言

60、、語言、PASCAL等）等） 二是按列存儲(chǔ)（二是按列存儲(chǔ)（FORTRAN等）等）A00 A01 A02A10 A11 A12A =A00A01A02A10A11A12A00A10A01A11A02A12第一行第一行第二行第二行第一列第一列第二列第二列第三列第三列elementtype A23 ；第第2 2章章 線性表線性表 Slide. 2 - 72D.S. & A.2013秋秋1、數(shù)組的順序存儲(chǔ)、數(shù)組的順序存儲(chǔ)對(duì)二維數(shù)組有：對(duì)二維數(shù)組有： LOC（Aij ）= LOC（A00）+ n i + j ， 0 i m-1，0 j n-1對(duì)三維數(shù)組有：對(duì)三維數(shù)組有： LOC（Ai1i2i3 ）= L