4.11   PROC  chars_in_s(VAR r:Strtp;  s,t:Strtp; VAR a: ARRAY[1..max] OF integer);

           {本算法求所有包含在串s中而不包含在串t 中的字符组成的新串r。}

           {a 为整形数组，存放r中字符在s中的位置}

           {只准使用 StrAssign, StrCompare,StrLength,Concat,Substring 五个操作}

         [ StrAssign(r,'');  {串r初始化}

           jj:=0;    {jj 记串中字符个数}

           FOR  i:=1 TO StrLength(s)  DO

             [ch:= Substring(s,i,1);   {取S中每个字符}

              j:=INDEX(t,ch);  k:=INDEX(r,ch);    { 查ch是否已在r或t中}

              IF(j=1)  AND  (k=1)

                 THEN [ StrAssign(r,Concat(r,ch));  a[jj+1]:=i;  jj:=jj+1]    

          ]

       ENDP;

 

       FUNC   index(s1:strtp; ch:char):integer;  { 查ch是否已在r或t中}

              ii:=1;  eq:=true;

              WHILE  (ii<=StrLength(s1)  AND  eq  DO

                 IF StrCompare(Substring(s1,ii,1),ch)=0

                   THEN  eq:=false   { ch已在r或t中存在}

                    ELSE   ii:=ii+1；

               IF eq=true    THEN  index:=1   { ch不在r或t中}

                            ELSE  index:=0   { ch已在r或t中存在}

        ENDF;

 

4.12  用基本操作1-6编写REPLACE（s,t,v）算法

      PROC  replace(VAR s:string; t,v:string);

          {本算法实现串的置换操作，用串v置换串s中所有非重叠的t串。}

          i:=INDEX(s,t);      {判s中有无t}

          IF i<>0

             THEN [ CREATE (temp, ‘’);    {t为临时串变量，存放部分结果}

                    m:=LENGTH(t);  n:=LENGTH(s);

                    WHILE  i<>0  DO

                       [ ASSIGN (temp,CONCAT(temp,SUBSTR(s,1,i-1),v));

                        {用v替换t形成部分结果}

                         ASSIGN (s,SUBSTR(s, i+m,  n-i-m+1)); {t串以后形成新s串}

                         n:= n-(i-1)-m;

                         i:=INDEX(s,t);

                        ]

                       ASSIGN (s,CONCAT(temp,s)); {将剩余s连接临时串t再赋给s}

                    ]

       ENDP;

                                                                  

 

 

4.19   PROC  chars_in_s(VAR r:Strtp;  s,t:Strtp; VAR a: ARRAY[1..max] OF integer);

           {在顺序存储结构上实现4.11的算法，求所有包含在s中而不包含在t 中的}

           {字符组成的新串r。a 为整形数组，存放r中字符在s中的位置}

      TYPE

          strtp=RECORD

                  ch:ARRAY[1..maxlen] OF char;

                  curlen:0..maxlen;

                END;

      VAR  ch:char;

         [ jj:=0;    {jj 记串中字符个数}

          r.curlen:=0;

          FOR  i:=1 TO s.curlen DO

             [ch:=s.ch[i];

              j:=INDEX(t,ch);  k:=INDEX(r,ch);

              IF(j=1)  AND  (k=1)

                 THEN [ r.curlen:=r.curlen+1; r.ch[r.curlen]:=ch; a[jj+1]:=i;  jj:=jj+1]    

          ]

       ENDP;

 

       FUNC   index(s1:strtp; ch:char):integer;

              ii:=1;  eq:=true;

              WHILE  (ii<=s1.curlen)  AND  eq  DO

                 IF s1.ch[ii]=ch

                   THEN  eq:=false   { ch已在r或t中存在}

                    ELSE   ii:=ii+1；

               IF eq=true    THEN  index:=1   { ch不在r或t中}

                            ELSE  index:=0   { ch已在r或t中存在}

        ENDF;

 

 

4.23

CONST  chunksize=用户定义的结点大小；

TYPE    pointer=^chunk;

         chunk=RECORD

                  ch:ARRAY[1..chunksize] OF char;

                  next:pointer;

               END;

        Linkstringtp=RECORD

                     head,tail:pointer;

                     length:integer;

                   END;         

FUNC  sym(sh:linkstringtp):boolean;

    {sh是块链结构的头指针，本算法判sh是否中心对称}

    sh:=sh^.next;   {指向首结点}

    n:=sh.length;  {串长}   INISTACK(s);   {栈初始化}

k:=0; {记字符个数}  match:=true;

j:=1;  {块内指针}

IF n<>0  THEN

   [ FOR  i:=1  TO  n  DIV  2  DO  {串的前一半入栈}

           [ PUSH(s,sh^.ch[j]);

             IF j=chunksize  THEN [ sh:=sh^.next; j:=1 ] {移指针}

                             ELSE j:=j+1;

              k:=k+1;

            ]  

         IF odd(n) THEN [ k:=k+1; j:=j+1]; {表长为奇数，中间字符不比}

         IF j=chunksize  THEN [ sh:=sh^.next; j:=1 ]

         WHILE (k<=n) AND match DO      {弹出栈顶元素与串的后一半字符比较}

            [ x:=pop(s);

              IF x<>sh^.ch[j]

                  THEN match:=false

                  ELSE IF j=chunksize  THEN [ sh:=sh^.next; j:=1 ]

                           ELSE j:=j+1;

               k:=k+1;

              ]

           IF empty(s) AND match

                 THEN sym :=true  {串中心对称}

                 ELSE sym:=false; {串中心不对称}

        ]

      ENDF;

 

 

4.27

FUNC INDEX(s,t:strtp):integer;

   {本算法是模式匹配,s是主串,t是模式串,算法先将t中第一字符和最后一个字符与主串s}

   {中相应字符比较,在两次相等后,再依次从t的第二字符开始比较。}

   {.设s是'anb'(连续n个a)型字符串, t是'akb'(连续k个a)型字符串, k<=n}

TYPE

      strtp=RECORD

         ch:ARRAY[1..maxlen] OF char;

         curlen:0..maxlen

       end;

 i:=1;j:=1;eq:=fasle;

WHILE (i<=(n+1)-(k+1)-1) AND (j<=(k+1)) AND NOT eq  DO

       IF s.ch[i]<>t.ch[j] OR s.ch[i+k]<>t.ch[j+k]

           THEN [i:=i-j+2;j:=1]

           ELSE [ WHILE (j<=k+1)  DO

                    IF s.ch[i]=t.ch[j]

                        THEN [i:=i+1;j:=j+1]

                        ELSE [i:=i-j+2;j:=1];

                  IF  j=k+2 THEN eq:=true;

                 ]；

             ]

   IF eq  THEN index:=i-j+1    {模式匹配}

          ELSE index:=0;      {模式不匹配}

ENDF