2.12

   FUNC  compare(A,B:sqlist):char;

{本算发比较顺序表A和B,若A<B,返回’<’, 若A=B,返回’=’, 若A>b返回’>’};

  算法1

      i:=1; equal:=true;{为退出while循环而设}

      WHILE (i<= LENGTH(A)) AND (i<=LENGTH(B) AND equal DO

         IF GET(A,i)=GET(B,i) {若A,B中对应字符相等,后移指针}

            THEN i:=i+1 ELSE equal:=false;

      IF (i=LENGTH(A)+1) and (i=LENGTH(B)+1) AND equal

        THEN compare:=’=’{A=B,除去最大公共前缀后子表为空}

        ELSE IF (LENGTH(A)=LENGTH(B) AND (GET(A,i)<GET(B,i) OR

              OR (I=LENGTH(A)+1) AND (i<LENGTH(B)+1) OR

              (I<LENGTH(A)+1) AND (i<LENGTH(B)+1) AND GET(A,i)<get(B,i)

              THEN compare:=’<’;{A’空B’非空;A’,B’均不空但A’第一字符小于B’}

              ELES compare:=’>’;

   ENDF;

 算法2  {建立子表A’和B’}

       equal:=true;

       i:=1; k:=0;{i为A,B比较对应元素的指针,k为A’,B’指针}

       INITIATE (A’); INITIATE (B’);

       WHILE (i<= LENGTH (A)) AND (i<= LENGTH(B) AND equal DO

          IF GET(A,i)=GET(B,i)

            THEN i:=i+1 ELSE equal:=false;

       FOR j:=i TO LENGTH (A) DO [INSERT[(A’,k+1,GET(A,i));k:=k+1];

       k:=0;

       FOR j:=i TO LENGTH(B) DO [INSERT[B’,k+1,GET(B,i)),k:=k+1];

       IF EMPTY(A’) AND EMPTY(B’) THEN RETURN(‘=’){A’,B’均空}

         ELSE IF (EMPTY (A’) AND NOT(EMPTY (B’)) OR

               (NOT EMPTY (A’) AND NOT EMPTY (B’) AND GET(A’,1)<GET(B’,1)

               THEN RETURN(‘<’)  {A’空B不空,或A’首字符小}

               ELSE RETURN(‘>’);

2.19

 PROC Deletelist (VAR la:Linkedlist; mink,maxk:elemtype);

   {la是带头节点的递增有序单链表,本算法删除递增有序单链表中}

   {所有值大于mink且小于maxk的元素}

   pre:=la;  {pre为链表中当前元素的前驱}

   q:=la^.next;  {q为链表中待处理的当前元素}

   found:=false;  {设标记};

   WHILE (q<>NIL) AND NOT  found  DO

      IF q^.data<=mink THEN  [pre:=q; q:=q^.next]

                     ELSE found:=true; {找到第一待删节点后停止搜索}

   WHILE (q<>NIL) AND found DO {找到大于maxk的就停止或到达表尾}

      IF q^.data<maxk THEN  [ p:=q; q:=q^.next; dispos(p)]

                     ELSE found:=false;

   pre^.next:=q;{删除了所有该删节点}

 ENDP;

2.21          

  PROC Invertsqlist (VAR va:sqlisttp);

{本算法就地逆置线性表va,2.21是顺序表,2.22是单链表}

    FOR i:=1 TO (va.last  DIV  2)  DO  va.data[i]ßàva.data[va.last-i+1]

  ENDP;

2.22          

  PROC Invertsqlist (VAR va:sqlisttp); {链式存储结构}

算法1

p:=NIL;{前驱} q:=la^.next;{当前}

WHILE q<>NIL DO

   [ r:=q^.next;  {r记下一结点}  或  [ r:=q; {r为临时变量}

    q^.next:=p;  {逆置}              q:=q^.next;

    p:=q;  {前驱跟上}               r^.next:=p;

    q:=r;  {处理下一结点}           p:=r

   ]                              ]

     la^.next:=p; {保留头指针不动,头节点指向第一元素}

     算法2

 q:=la^.next; la^.next:=NIL;

 WHILE q<>NIL DO  {此算法省去了中间变量r}

    [ p:=q;

     q:=q^.next;

     p^.next:=la^.next;

     la^.next:=p

    ]

ENDP;

2.24 PROC  unitinvert(VAR lc:linkedlist; la,lb:linkedlist);

     {la,lb是两个递增有序的单链表,本算法将la,lb合并成按元素值递减有序的}

     {单链表lc. 算法中比较la,lb相应元素,小者链入lc且逆置}

     pa:=la^.next;  pb:=lb^.next;  {pa,pb先指向la,lb中第一元素}

     lc:=la;  pc:=lc;  q:=NIL;  {q是pc的前驱,逆置后为后继}

     WHILE (pa<>NIL) AND (pb<>NIL) DO

        IF pa^.data<=pb^.data

           THEN [pc:=pa;  pa:=pa^.next;  pc^.next:=q;{逆置} q:=pc; ]

           ELSE [pc:=pb;  pb:=pb^.next;  pc^.next:=q;  q:=pc;  ]

     WHILE pa<>NIL DO {处理表A剩余部分}

        [pc:=pa; pa:=pa^.next ;  pc^.next:=q;  q:=pc;  ]

     WHILE pb<>NIL DO{处理表B剩余部分}

        [pc:=pb;  pb:=pb^.next ;  pc^.next:=q;  q:=pc;  ]

      lc^.next:=q;  {表头链入链表中}

  ENDP;             

2-25 PROC   IntersectSqlist   (VAR  vc: Sqlist;  va, vb:Sqlist);

   {va,vb是两个递增有序的线性表,用顺序存储结构存储,本算法求两表的交集,

   {且放入vc中, vc也是递增有序的线性表}

   vc.last:=0;   I:=1;   j:=1;  k:=1;  {i,j,k为va,vb,vc三表当前元素指针}

   WHILE  (I<=va.last)  AND  (j<=vb.last)  DO

      IF  va.data[I]<vb.data[j]  THEN  I:=I+1;

         ELSE IF va.data[I]=vb.data[j]{找到交集元素}

                 THEN  [k:=k+1;  vc.data[k]:=va.data[I];  I:=I+1;  j:=j+1]

                 ELSE   j:=j+1;

   vc.last:=k;

ENDP;

2-26 PROC  IntersectSqlist  (VAR  lc:Linklist;  la,lb:Linkedlist)

      { la,lb是两个递增有序单链表的头指针,本算法求两表的交集lc,}

      {且lc也是递增有序单链表}

     pa:=la^.next;  pb:=lb^.next;    new(lc);  lc^.next:=NIL;

     pc:=lc;   {初始化,pc指向lc表中最后一个结点}

     WHILE  (pa<>NIL)  AND  (pb<>NIL)  DO

        IF  pa^.data<pb^.data  THEN  pa:=pa^.next

           ELSE IF  pa^.data=pb^.data

                   THEN  [new(p);  p^.data:=pa^.data;  p^.next:=pc^.next;

                           pc^.next:=p;  pc:=p;

                           pa:=pa^.next;   pb:=pb^.next;

                          ]

                  ELSE  pb:=pb^.next;  {pb^.data<pa^.data, pb后移}

   ENDP; 

2.32

      PROC ChangeToBilink(hp:Bilinklist);

     {hp是bilinklist型单向循环链表,next是指向后继结点的指针域}

     {pre初值为NIL, 本算法将该链表改为双向循环链表}

     TYPE

          Bilinklist=^binode;

          binode=RECORD

                    data:elemtp;

                    pre,next:bilinklist;

                 END;

      p:=hp^.next;  q:=hp;  {q是p的前驱}

      WHILE p<>hp DO

         [p^.pre:=q;  q:=p;  p:=p^.next];

       hp^.pre:=q; {或p^.pre:=q}

   ENDP;

解2. P:=hp^.next;  q:=hp;

     WHILE p^.pre=NIL DO

        [p^.pre:=q;  q:=p;  p:=p^.next];

2.33

  PROC splitlinklist(VAR lc,ld,lo:linkedlist;ll:linkedlist);

{ ll是数据域为字符的循环链表，本算法将ll分解为lc,ld和lo}

{三个各含字母,数字和其它符号的循环链表，利用原空间}

p:=ll^.next;  lc:=lL;  lc^.next:=lc;

NEW(ld);  ld^.next:=ld;

NEW(lo);  lo^.next:=lo;{初始化}

WHILE p<>ll DO

  [q:=p^.next;  {用以记住后继结点}

   CASE

     p^.data IN ['0'..'9']: [ p^.next:=ld^.next;  ld^.next:=p ];

     p^.data IN ['A'..'Z'] OR p^data  IN  ['a'..'z']:

                            [ p^.next:=lc^.next;  lc^next:=p ];

     ELSE [ p^.next:=lo^.next;  lo^.next:=p];

    ENDC

   p:=q;

  ]

ENDP;