第二章线性表及其顺序存储结构1

1、体现在体现在顺序关系上顺序关系上记录排列为记录排列为顺序关系顺序关系ADR(ai) = ADR(a1) + (i-1) k转图示 意 图操作演示操作演示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) 的线性表的线性表 栈底栈顶a1a4a2a3NULLa5an-1a1a0topn-110m本课完a a* *b+cb+ca a* *b/cb/ca a* *b b* *c c*

2、*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* *d d* *e e* *f f* *abcabc* *d+e/+d+e/+abc+de-/f-abc+de-/f-* *abc-/deabc-/de* *+ +表表2.2 2.2 中缀表达式和后缀表达式中缀表达式和后缀表达式中缀表达式中缀表达式后缀表达式后缀表达式/-DECB*+A;TOPvTOPp+*()-*T2 = A + T1T

3、1/T2T1 = B * C；;-T3 = D / ET3/T4 = T2 T3T4;=结果：结果：T4T4本课完a1a2a3a4a5队列空队列空队列满队列满l 逻辑上循环：front=(front+1)%6; fear=(rear+1)%6a1a2a3a4a5ABABCACABABCBCCAi,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,000000000000000

4、00000000000000000000000000001S S00000001P P由于每趟比较都是在p的最后一个字符才出现不等，i将回溯到i-6的位置，再重新从p的第一个字符开始比较。整个匹配过程中i 需回溯需回溯36（即：（即：43- 81）次）次。4242个个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中中哪个字符比较？

5、哪个字符比较？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 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失败！失败！失败！失败！成功！成功！结论：结论：K应应取最大的！取最大的！本课完a

6、 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 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 b 1 2 3 4