#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;
}

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

//#define INIT 10000

#define INIT 5

//#define TOTAL 100000000

#define TOTAL 10

static int count = 0;

typedef struct tree
{
   int num;
   struct tree* parent;
   struct tree* lchild;
   struct tree* rchild;
  }TREE;
  
TREE* add_tree(TREE** T, TREE* parent, int num)
{
  if(*T == NULL)
   {
     *T = (TREE*)malloc(sizeof(TREE));
     if(*T == NULL)
      {
        printf("malloc error\n");
        return NULL;
        }
        printf("added %d\n",num);
       (*T)->num = num;
       (*T)->parent = parent;
       (*T)->lchild = NULL;
       (*T)->rchild = NULL;
     }
    else if((*T)->num < num)
       return add_tree(&(*T)->rchild,*T,num);
    else
       return add_tree(&(*T)->lchild,*T,num);
}

int midwalk(TREE* T)
{
  if(T!=NULL)
   {
     midwalk(T->lchild);
     count++;
     if(count%10 == 0)
      {
        count = 0;
        printf("%d\n",T->num);
       }
     else
       printf("%d\t",T->num);
     
     midwalk(T->rchild);
     }
   return 0;
}

int tree_out(TREE** T)
{
  int num = 0;
  TREE* p = NULL;
  TREE* q = NULL;
  TREE** tmp = T;
  TREE* tmp1 = *T;
  
  printf("tmp is %p\ntmp1 is %p\n",*tmp,tmp1);
   if(*tmp == NULL)
    {
      printf("sorry the tree is empty\n");
      return -1;
      }
    if((*tmp)->lchild == NULL)
    {
      q = *tmp;
      num = q->num;
      *tmp = (*tmp)->rchild;
      printf("now head is %d\n",q->num);
      free(q);
      q = NULL;
      return num;
      }
    #if 1
    while(tmp1->lchild != NULL)
     {
        p = tmp1;
        tmp1 = tmp1->lchild;
      }
     p->lchild = tmp1->rchild;
    num = tmp1->num;
    free(tmp1);
   #endif
   #if 0
   while((*tmp)->lchild != NULL)
     {
        p = *tmp;
        *tmp = (*tmp)->lchild;
      }
     p->lchild = (*tmp)->rchild;
    num = (*tmp)->num;
    free(*tmp);
   #endif
    return num;
}

int minimum(TREE* T)
{
  while(T->lchild != NULL)
   {
     T = T->lchild;
     }
   return T->num;
}
   
int main(int argc, char *argv[])
{
  int i = 0;
  int num = 0;
  double j = INIT;
  int mini = 0;
  
  
  TREE* T = NULL;
  srand( (unsigned)time( NULL ) );

  for(i=0;i<INIT;i++)
  {
    num = rand();
    add_tree(&T, NULL, num);
   }
   midwalk(T);
   
   mini = minimum(T);
  for(j=INIT;j<TOTAL;j++)
  {
    num = rand();
    if(num > mini)
      {
       tree_out(&T);
       add_tree(&T, NULL, num);
       mini = minimum(T);
      }
   }
   
  midwalk(T);
  system("PAUSE");   
  return 0;
}