第二章線性表及其順序存儲結(jié)構(gòu)1

1、體現(xiàn)在體現(xiàn)在順序關(guān)系上順序關(guān)系上記錄排列為記錄排列為順序關(guān)系順序關(guān)系A(chǔ)DR(ai) = ADR(a1) + (i-1) k轉(zhuǎn)圖示 意 圖操作演示操作演示n-1ai a0 ai-1。前移前移n-i-1個元素個元素 0 i-1 i i+1 n-1 m-1an-1刪除它刪除它ai+1ain-1操作演示操作演示2) 1(1,2)(1100ninnAninnAnidelniins先進后出先進后出 (FirstInLastOut) 的線性表的線性表 棧底棧頂a1a4a2a3NULLa5template class Stack public: virtual bool flag() const=0; vir

2、tual bool readTop(T ) const=0; virtual bool push(T )=0; virtual bool pop()=0; virtual bool print() const=0; ;an-1a1a0topn-110m本課完a a* *b+cb+ca a* *b/cb/ca a* *b b* *c c* *d d* *e e* *f fa+(ba+(b* *c+d)/ec+d)/ea a* *(b+c)/(d-e)-f)(b+c)/(d-e)-f)a/(b-c)+da/(b-c)+d* *e eabab* *c+c+abab* *c/c/abab* *c c*

3、 *d d* *e e* *f f* *abcabc* *d+e/+d+e/+abc+de-/fabc+de-/f- -* *abcabc-/de-/de* *+ +表表2.2 2.2 中綴表達式和后綴表達式中綴表達式和后綴表達式中綴表達式中綴表達式后綴表達式后綴表達式/-DECB*+A;TOPvTOPp+*()-*T2 = A + T1T1/T2T1 = B * C；;-T3 = D / ET3/T4 = T2 T3T4;=結(jié)果：結(jié)果：T4T4本課完a1a2a3a4a5隊列空隊列空隊列滿隊列滿l 邏輯上循環(huán)：front=(front+1)%6; fear=(rear+1)%6a1a2a3a4

4、a5ABABCACABABCBCCAi,0i,0j,0j,0AABCBACB Ai,1i,1j,1j,1j,0j,0i,2i,2AAi,3i,3j,1j,1i,4i,4j,2j,2BBi,5i,5j,3j,3CCi,6i,6j,4j,4串串S, n=10串串P, m=5匹配成功，匹配成功，耶！耶！演示j,0j,00000000000000000000000000000000000000000001S S00000001P P由于每趟比較都是在p的最后一個字符才出現(xiàn)不等，i將回溯到i-6的位置，再重新從p的第一個字符開始比較。整個匹配過程中i 需回溯需回溯36（即：（即：43- 81）次）次。4

5、242個個0 0 ija b a b c a b c a c b a ba b c a c1a b a b c a b c a c b a b a b c a c2a b a b c a b c a c b a b (a) b c a c3S3=a再重新與再重新與P中中哪個字符比較？哪個字符比較？S7=b再重新與再重新與P中中哪個字符比較？哪個字符比較？a b a b c a b c a c b a b a b c a cK可分三可分三種情況種情況a a a a b c a b c a c b a b a a a b cj=3i=43K=3j=4i=4a a a a b c a b c a c

6、 b a ba a a b cK=1,2,3i=4, j=4時失配時失配a a a a b c a b c a c b a b a a a b cj=2i=42K=2a a a a b c a b c a c b a b a a a b cj=1i=41K=1失敗！失??！失??！失??！成功！成功！結(jié)論：結(jié)論：K應(yīng)應(yīng)取最大的！取最大的！本課完a b a b c a b c a c b a b a b c a c2i=7j=5a b a b c a b c a c b a b (a) b c a c3i=7-i=11j=2- j=6i=7, j=5時失配時失配得得K=2K=2a b a b c a

7、b c a c b a ba b cj=3i=31得得K=1i=3, j=3時時失配失配失配失配a b a b c a a a a b c a a a a c c a a a a c1 2 3 4 5 6 7 8 9 i=10 1 2 3 4 5 j=6 失配失配 | | | | |失配失配1 2 3 4 5 6 7 8 i=91 2 3 j=4 a b a b c a a a a b c a c b a b a a a b cSPa b a b c a a a a b c ( i=9 ) a a a b c ( j=4 ) a a a b c1 2 3 4 5 6 7 8 i=9SPP k= 3兩序列增加兩序列增加一相同字符一相同字符 a a a b c