数据结构课件 第二章线性表5_线性结构总结

1、,41 铁路进行列车调度时，常把站台设计成栈式结构的站台，如右图所示。试问： （1）设有编号为1，2，3，4，5，6的六辆车，顺序开入栈式结构的站台，则可能的出栈序列有多少种？ （2）若进站的六辆列车顺序如上所述，那么是否能够得到435612，325641，154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到（即写出“进站”或“出站”的序列）。,将两个有序单链表合并为一个有序单链表,if ( pa-data data ) pc-next = pa ；pc = pa ；pa = pa-next ； else pc-next = pb ；pc = pb ；pb =

2、pb-next ；,将两个有序单链表合并为一个有序单链表,pa = La-next ； pb = Lb-next ；/分别指向第一个结点,pc-next = pa ? pa : pb ；/处理剩余部分,Lc = pc = La ；,delete(Lb) ；,思想:,通过比较不断后移指针合并链表。,析构函数 IntSLList（）,class DLList public: DLList() head = tail = 0; void R() reverse( head ); DLLNode * tmp; tmp = head; head = tail; tail = tmp; tail - ne

3、xt = 0; void addtotail( int ,递归方法实现的单链表反转,void DLList:reverse( DLLNode * n ) DLLNode * t1 = n, * t2 = n -next; if ( t2 -next != 0 ) reverse( t2 ); t2 - next = t1; ,单链表反转的其他解法,1) 插入,1. 找到要在之前插入的结点，p记录。,2. s-prior = p-prior ；,3. p-prior-next = s ；,4. s-next = p ；,5. p-prior = s ；,双链表,2) 删除,A,C,B,1. 找到

4、要删除的结点，p记录。,2. p-prior-next = p-next ；,3. p-next-prior = p-prior ；,4. delete(p) ；,2.4 一元多项式的表示及相加,数学表示: Pn(x) = p0 + p1x + p2x2 + + pnxn,计算机表示: P = ( p0，p1，p2，pn ),可以描述为一个由 n+1 个系数构成的线性表。,多项式相加:,则 Rn(x) = Pn(x) + Qm(x) R = ( p0 + q0，p1 + q1，p2 + q2，pm + qm，pm+1，pn ),显然，采用 结构实现方便。,顺序存储,+,然而实际应用中，多项式的

5、次数往往很高，且可能存在很多缺项。,例，S(x) = 1 + 3x10000 + 2x20000,计算机表示: P = ( ( p1 ，e1 ) ，( p2 ，e2 ) ，( pm ，em ) ),? 采用那种存储结构？,系数,指数,下一个结点,算法2.23 多项式相加 AddPolyn ( &Pa，&Pb ),要求: Pa = Pa + Pb,思想:,依据归并两个有序表的过程，分三种情况考虑:,令 qa 和 qb 分别指向多项式 A 和 B 中当前进行比较的结点；,qa-expo qb-expo，qa所指向的结点应插入和多项式中,qa-expo qb-expo，qb所指向的结点应插入和多项式

6、中,qa-expo qb-expo，求和 qa-coef + qb-coef,和 0，释放 qa 和 qb 所指结点；,和 0，修改 qa 所指结点的系数值，释放 qb 所指结点；,qa = Pa-next ； qb = Pb-next ；,case : / 插入 qa 结点,case : / 插入 qb 结点,case = : /计算 qa-coef + qb-coef,FreeNode ( hb ) ；,ha-next = qa ? qa : qb ；/处理剩余部分,ha = Pa ； hb = Pb ；,case :,ha = qa ；qa = qa-next ；break ；,case :,qa,qb,5,3,7,ha,8,hb,case = :,qa,qb,3,3,7,ha,8,hb,2,-2,sum = qa-coef + qb-coef ；,if ( sum != 0.0 ) ,qa-coef = sum ；,else ,hb-next=qb-next ；Free( qb ) ；qb = hb-next ； /释放 qb,ha = qa ；qa = qa-next ； /后移 qa,break ；,hb-next=qb-next ；Free( qb ) ；qb = hb-next ； /