有序线性表合并

代码是在dev c++下写的,其他环境下主要注释掉system("PAUSE")就可以了,很多debug信息就没删除了...

 

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define QUIT 999

typedef struct node
{
  int num;
  struct node* next;
   }NODE;
   
int create_list(NODE** head)
{
  int num;
  int i = 0;
  NODE* p = NULL;
  NODE* q = NULL;
  
  *head = (NODE*)malloc(sizeof(NODE));
  if(*head == NULL)
   {
     printf("head malloc error\n");
     return -1;
     }
   (*head)->next = NULL;
   
   printf("input %d to end add list\n",QUIT);
   while(1)
   {
     p = *head;
     q = (NODE*)malloc(sizeof(NODE));
     if(q == NULL)
     {
      printf("head malloc error\n");
      return -1;
     }
     i++;
     printf("Now Please input num %d:\t",i);
     scanf("%d",&num);
     if(num == QUIT)
       {
         printf("end create list\n");
         break;
        }
     q->num = num;
     while((p->next != NULL) && (p->next->num < num))
      {
        p = p->next;
       }
        
     q->next = p->next;
     p->next = q;
   
    }
   return 0;
}

NODE* merge_list(NODE* head1,NODE* head2)
{
     assert(head1 != NULL);
     assert(head2 != NULL);
     
     
     NODE* head = (NODE*)malloc(sizeof(NODE));
     if(head == NULL)
     {
       printf("head malloc error\n");
       return NULL;
     }
     
     NODE* head_tmp = head;
     NODE* p1 = head1->next;
     NODE* p2 = head2->next;
     
     while((p1 != NULL) && (p2 != NULL))
       {
         printf("p1 data is %d\t p2 date is %d\n",p1->num,p2->num);
         if(p1->num < p2->num)
           {
             printf("copied %d\n",p1->num);
             system("PAUSE");
             head_tmp->next = p1;
             p1 = p1->next;
             }
          else
           {
             printf("copied %d\n",p2->num);
             system("PAUSE");
             head_tmp->next = p2;
             p2 = p2->next;
             }
            head_tmp = head_tmp->next;
         }
         
     if(p1 == NULL)
        {
         head_tmp->next = p2;
         printf("asdas copied:\n");
         print_list(head_tmp);
        }
     else
       {
         head_tmp->next = p1;
         printf("asdas copied:\n");
         print_list(head_tmp);
        }
     return head;
  }
int print_list(NODE* head)
{
   assert(head != NULL);
   NODE* p = head;
   while(p->next != NULL)
    {
      printf("%d\t",p->next->num);
      p = p->next;
      }
   printf("\n");
}

int main(int argc, char *argv[])
{
  NODE* head1 = NULL;
  NODE* head2 = NULL;
  
  create_list(&head1);
  create_list(&head2);

  printf("list1 is:\n");
  print_list(head1);
  printf("list2 is:\n");
  print_list(head2);
  printf("merged list is:\n");
  print_list(merge_list(head1,head2));
    
  system("PAUSE");    
  return 0;
}


写create_list(NODE** head)函数还是很顺利的,一遍就OK了.

主要是merge_list(NODE* head1,NODE* head2)秀逗了好久...

先是NODE* head = NULL;没有为头分配空间导致error...

不过最头疼的当是,我程序先是这么写的

     NODE* p1 = head1;
     NODE* p2 = head2;
     
     while((p1->next != NULL) && (p2->next != NULL))
       {
         printf("p1 data is %d\t p2 date is %d\n",p1->next->num,p2->next->num);
         if(p1->next->num < p2->next->num)
           {
             printf("copied %d\n",p1->next->num);
             system("PAUSE");
             head_tmp->next = p1->next;
             p1 = p1->next;
             }
          else
           {
             printf("copied %d\n",p2->next->num);
             system("PAUSE");
             head_tmp->next = p2->next;
             p2 = p2->next;
             }
            head_tmp = head_tmp->next;
         }

我的list1是 head1->1->3->5->6->7->NULL

     list2是 head2->2->4->8->9->10->NULL

结果发现程序copied 1 2后就一直copied 2

想了良久画了个图才弄明白

    1. p1->next->data（1） 小于 p1->next->data（2）

         copied 1这是 p1指向 1

                      head_tmp也就1的地址(p1)

    2.  p1->next->data（3） 大于 p1->next->data（2）

         copied 1这是 p2指向 4

                     head_tmp->next = 2的地址

           问题出来了,这样就导致p1->next为2了....

         于是一直copy 2 整个链表就都是2了...

其实大家可以画两个链表就看的比较清楚了....

 

 

也许说了这么多大家也还不是很清楚,运行下两个程序,可以帮助你理解...

 

 

聊表这个东西稍微不注意就丢失了.....