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

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

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

 1 #include <stdio.h>
 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     else
19       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 <stdio.h>
 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

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

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