算法（3）—— 链表习题完结-白红宇

算法（3）—— 链表习题完结

阅读量：6265 次

发布时间：2019-06-22

本文共 5024 字，大约阅读时间需要 16 分钟。

注：链表有头结点，教科书上的答案会忽略头结点的存在，通过 PrintList ( List L）就能发现这样的算法存在的问题，解决这个问题需要做两点：（1）创建节点时候，用 MakeEmpty ( List L ) 创建带头结点的链表；（2）对链表进行操作的时候，从有数据部分进行操作，即函数调用参数为 ( List -> Next)。

1. 给定两个已经排序好的链表 P 和 L ，求二者的交集。（注意，二者未必长度相等）

1 #include 
      
        2 #include "list.c" 3  4  5 List ListJiaoJi (List P, List L)  { 6   if  (P == NULL || L == NULL ) 7     Error ("Out of space"); 8   Position   Ppos =  First (P); 9   Position   Lpos =  First (L);10   11   List R = MakeEmpty (NULL);12   Position Rpos = Header(R);13  14   while ( Ppos != NULL  && Lpos != NULL )  {15 16     if  ( Retrieve(Ppos) < Retrieve(Lpos) ) 17       Ppos = Advance (Ppos);18     else19       if ( Retrieve(Ppos) > Retrieve (Lpos)) 20     Lpos = Advance (Lpos);21       else {22     Insert ( Retrieve (Lpos),R,Rpos);23     Lpos = Advance (Lpos);24     Ppos = Advance (Ppos);25     Rpos = Advance (Rpos);26       }27   }28   return R;29 }30 31 int main(int argc, char *argv[])   {32 33   34   List L;35   Position Lpos;36   List P;37   Position Ppos;38   39   int i;40   P = MakeEmpty (NULL);41   L = MakeEmpty( NULL );42 43   Ppos = Header( P );44   Lpos = Header (L);45 46   for( i = 0; i < 10; i++ ) {47     Insert( i, L, Lpos );48   49     Lpos = Advance( Lpos );50   }51   PrintList( L );52   53   Insert (3,P,Ppos);54   Ppos = Advance (Ppos);55 56   Insert (5,P,Ppos);57 58   PrintList (P);59   List R = MakeEmpty(NULL);60   R =  ListJiaoJi (P,L);61   PrintList (R);62   63   return 0;64 }

SamePart.c

2.给定两个已经排序好的链表 P 和 L，求两者的并集。（注意，二者长度未必相等）

1 #include 
      
        2 #include "list.c" 3  4  5 List ListJiaoJi (List P, List L)  { 6   if  (P == NULL || L == NULL ) 7         Error ("Out of space"); 8   Position   Ppos =  First (P); 9   Position   Lpos =  First (L);10   11   List R = MakeEmpty (NULL);12   Position Rpos = Header(R);13   //PrintList (R);14 15   while ( Ppos != NULL  && Lpos != NULL )  {16 17     if  ( Retrieve(Ppos) < Retrieve(Lpos) )  {18       Insert(Retrieve(Ppos),R,Rpos);19       Ppos = Advance (Ppos);20       Rpos = Advance (Rpos);21     }22   23     else if ( Retrieve(Ppos) > Retrieve (Lpos))  {24       Insert ( Retrieve (Lpos),R,Rpos);25       Lpos = Advance (Lpos) ;26       Rpos = Advance (Rpos);27     }28 29     else {30       Insert ( Retrieve (Lpos),R,Rpos);31       Lpos = Advance (Lpos);32       Ppos = Advance (Ppos);33       Rpos = Advance (Rpos);34     }35   }36     37   while ( Lpos != NULL)  {  38     Insert (Retrieve(Lpos),R,Rpos);39     Lpos = Advance  (Lpos);40     Rpos = Advance (Rpos);41   }42 43   while ( Ppos != NULL)  {      44     Insert  (Retrieve (Ppos),R,Rpos);45     Ppos = Advance (Ppos);46     Rpos = Advance (Rpos);47   }48 49  50   return R;51 }52 53 int main(int argc, char *argv[])   {54 55   56   List L;57   Position Lpos;58   List P;59   Position Ppos;60   61   int i;62   P = MakeEmpty (NULL);63   L = MakeEmpty( NULL );64 65   Ppos = Header( P );66   Lpos = Header (L);67 68   for( i = 0; i < 10; i++ ) {69     Insert( i, L, Lpos );70   71     Lpos = Advance( Lpos );72   }73   PrintList( L );74   75   Insert (3,P,Ppos);76   Ppos = Advance (Ppos);77 78   Insert (5,P,Ppos);79 80   PrintList (P);81   List R = MakeEmpty(NULL);82   R =  ListJiaoJi (P,L);83   PrintList (R);84   85   return 0;86 }

UnionList.c

3.不用递归方法，反转链表。

树上的答案翻转后的链表并没有头结点，我给改进了一下。

1 #include "list.c" 2  3  4 /*  5  6    NOTE: book's answer will just return cur,if do this, the reverselist will not have a head node ,PrintList will not work as hoped.I think it is wrong.It is my method's (as follow) output: 7    1 2 8    2 1 9    1 2 10 */11 List ReverseList (List L)  {12 13   Position pre,cur,nex;14 15   pre = NULL;16   cur = L->Next;17   nex = First(L)->Next;18   while (nex != NULL )  {19     cur-> Next = pre;20     pre = cur;21     cur = nex;22     nex = Advance(nex);23   }24   cur->Next = pre;       //return cur; 25   nex = MakeEmpty (NULL);26   nex -> Next = cur;27 28   return nex;29 }30 31 32 33 int main()  {34   List L = MakeEmpty (NULL);35   Position Pos = Header( L);36 37   Insert (1,L,Pos);38   Pos = Advance (Pos);39 40   Insert (2,L,Pos);41 42   Pos = Advance (Pos);43 44   PrintList(L);45 46   List RL =  MakeEmpty(NULL);47   RL = ReverseList (L);48   PrintList (RL);49 50   List RRL = ReverseList(RL);51 52   PrintList (RRL);53 54   return 0;55 }

ReverseList.c

4. 使用递归实现链表的翻转。

1 #include "list.c" 2  3 List  ReverseList (Position P)  { 4  5   if ( P->Next == NULL )  { 6      List LR = MakeEmpty (NULL); 7      LR -> Next = P; 8      return LR; 9   }10 11   List RL = MakeEmpty(NULL);12   RL = ReverseList (P->Next);13   P->Next->Next = P;14   P->Next = NULL;15   return RL;16 }    17 18 int main()  {19   List L = MakeEmpty (NULL);20   Position Pos = Header( L);21 22   Insert (1,L,Pos);23   Pos = Advance (Pos);24 25   Insert (2,L,Pos);26 27   Pos = Advance (Pos);28 29   PrintList(L);30 31   List RL =  MakeEmpty(NULL);32   RL = ReverseList (L->Next);33   PrintList (RL);34 35  36 37   return 0;38 }

ReviseListRec.c

转载于:https://www.cnblogs.com/hanxinle/p/7414774.html

你可能感兴趣的文章