5.19 PROC  saddlepoint(a:array2tp);

           {a是m行n列的二维数组,本算法求所有马鞍点}

           {b是一维数组,存放一行中可能的马鞍点的列值,k记相等值个数}

           {c是一维数组,存放某列可能马鞍点的行值,kk记相等值个数}

      FOR  i:=1 to m  DO

         [ min:=a[i,1]; {最小值初始化}

          b[1]:=1; k:=1

          FOR j:=2 to n DO {找每一行中的最小值}

             IF a[i,j]<min THEN [b[1]:=j; min:=a[ i,j]; k:=1]  {重新确定最小值}

                ELSE IF a[ i,j]=min THEN [b[k+1]:=j; k:=k+1] {有相等的最小值}

          FOR jj:=1 TO k DO {第I行有k个相等的最小值}

             [ j:=b[jj]; max:=a[1,j] ; kk:=1;  c[1]:=I; {a[i,j]是否是马鞍点}

              FOR ii:=2 to m DO {找第j列的最大值}

                 IF a[ii,j]>max THEN [c[1]:=ii; max:=a[ii,j]; kk:=1]  {重新确定最大值}

                    ELSE IF a[ii,j]=max THEN [c[kk+1]:=ii; kk:=kk+1] {有相等的最大值}

              IF  max=min  THEN  {有可能是马鞍点}

                 FOR ii:=1 TO kk DO   {kk个相等的最大值哪个是马鞍点}

                    IF  c[ii]= i  THEN WRITE(‘马鞍点 ’,i:4,j:4,a[ i,j]:4)

             ]  {END OF  ‘FOR jj=1  TO  k  DO’}

           ]   { END OF  ‘FOR  i =1 to m DO’ }

   ENDP;

   解法2: 若矩阵中元素值互不相同,则第i行只一个最小值,记下列号j;

          然后在第j列查最大值,记下其行号ii, 若i=ii,则a[ i,j]是马鞍点.

 

  改进: 在第j列求最大值时,可用WHILE 循环,一但某值大于最小值min时, 即可

        退出循环, 该点不是马鞍点. 程序段如下:

        FOR jj:=1 TO k DO {第I行有k个相等的最小值}

             [ j:=b[jj];  ii:=1;  flag:=true;  kk:=0;  c[1]:= i; {a[ii,j]是否是马鞍点}

              WHILE  (ii<=m) AND flag  DO {找第j列的最大值}

                 IF a[ii,j]>min THEN flag:=false

                    ELSE IF a[ii,j]=min THEN [c[kk+1]:=ii; kk:=kk+1] {有相等的最大值}

              IF  kk<>0  THEN  {有可能有马鞍点}

                 FOR ii:=1 TO kk DO   {kk个相等的最大值哪个是马鞍点}

                    IF  c[ii]= i  THEN WRITE(‘马鞍点 ’,i:4,j:4,a[ i,j]:4)

             ]  {END OF  ‘FOR jj=1  TO  k  DO’}

解法2: 先将矩阵每行的最小值存入 row 一维数组,将每列的最大值存入col 一维数组,再

       进行两层循环,若a[ i,j]=row[ i]=col[j], 则 a[ i,j] 为马鞍点.

       FOR I:=1 TO m  DO

           FOR j:=1 TO n  DO

               IF a[ i,j]=row[ i] AND a[ i,j]=col[ j] THEN WRITE(‘马鞍点 ’,i:4,j:4,a[ i,j]:4)

      {时间复杂度O(3*(m*n)) ,  当马鞍点很多时适宜}

 

5.21  TYPE link=^matnode;

       feature=(headnode,element);

       matnode=RECORD

                 i,j:integer;     Right,down:link;

                 Case feature OF

                     Headnode:( next:link);  Element: (v:elemtp);

                 END;

PROC  addmatrix(var ha:link; hb:link);

 {ha,hb 分别是以十字链表为存储结构的稀疏矩阵的头指针,本算法将两矩阵加,}

 {结果放在以ha为头指针的稀疏矩阵中}

 ca:=ha^.next; cb:=hb^.next;  {ca,cb 分别指向第一行列表头}

 WHILE  (ca<>ha)  AND  (cb<>hb )  DO  
        [ pa:=ca^.right; pb:=cb^.right;  {pa,pb 分别指向该行第一非0元素}

     IF pb^.j=0 THEN  [ ca:=ca^.next;  cb:=cb^.next ];

        {B的该行无非0 元素, ca,cb各指向下一行}

     WHILE  pb^.j<>0  DO  {处理一行}

       [ qa:=pa;  {qa 为前驱结点}

        CASE

          (pa^.j<pb^.j) AND (pa^.j<>0) :qa:=pa; pa:=pa^.right;{qa^已是结果中的一项}

          (pa^.j>pb^.j) OR (pa^.j=0) : {pb^的列号小,是结果中的一项}

            [ p:=pb; qa^.right:=p; p^.right:=pa;  {将pb^ 结点插入pa^所在行行中}

             pp:=cpa[pb^.j];  {cpa,cpb是A,B 的行列表头指针数组}

             WHILE(pp^.down<>cpa[pb^.j]AND(pp^.down^.i<pa^.i)DO pp:=pp^.down;

              p^.down:=pp^.down; pp^.down:=p; 将pb^ 结点链入pb^.j所在列中}

              pb:=pb^.right;

             ]

            pa^.j=pb^.j: pa^.v:=pa^.v+pb^.v;  [ IF pa^.v=0 THEN {删除该结点}

                                   [ qa^.right:=pa^.right;  {行中删除}

                                    p:=cpa[pb^.j];

                                    WHILE p^.down<>pa  DO  p:=p^.down;

                                    p^.down:=pa^.down;  {列中删除}

                                   ]

                                   pa:=pa^.right; pb:=pb^.right;

                                 ] ; {END OF IF pa^.v=0 }

          ENDC;   { END OF CASE}

       ] ;  {END OF WHILE }

    ca:=ha^.next; cb:=hb^.next;  {ca,cb 分别指向下一行列表头}

]  { END OF WHILE (ca<>ha) AND (cb<>hb)  ]

 

5.25

  PROC addmatrix(VAR b3:ARRAY[1..m,1..n] OF 0..1;

                 VAR v3:ARRAY[1..maxlen] OF integer;

                 b1,b2:ARRAY[1..m,1..n] OF 0..1; v1, v2:ARRAY[1..maxlen] OF integer);

                     {b1,b2是稀疏矩阵A1,A2的0..1矩阵}

                     (稀疏矩阵中非0元在0..1矩阵的相应位置用1表示),}

                     {v1,v2是稀疏矩阵A1,A2的非0元以行序为主存储的一维数组;}

                     {本算法实现矩阵A1,A2相加,结果按上述约定存于b3,v3中}

         pb1:=pb2:=pb3:=0;  {pb1,pb2,pb3分别指向v1,v2,v3中当前元素位置}

         FOR  I: =1 TO m  DO

             FOR j :=1 TO n  DO

                 IF b1[ I,j] =1  OR b2[I,j]=1

                     THEN [  IF b1[I,j]=1

                                 THEN [ pb1:=pb1+1; s1:=v1[pb1]

                                 ELSE  s1:=0;

                              IF b2[I,j]=1

                                 THEN [ pb2:=pb2+1; s2:=v2[pb2]

                                 ELSE  s2:=0;

                              IF s1+s2<>0

                                 THEN [ pb3:=pb3+1; v3[pb3]:=s1+s2;b3[I,j]:=1

                                 ELSE  b3[I,j]::=0;

                           ]

   ENDP;

 

     讨论: 若以相加作为估计复杂度的主要操作, 则复杂度为O(n), n为两个稀疏矩阵中非0 元素之和.