习题09-两链表合并.c

数据结构各章实验源代码； 数据结构实验源代码

#include  "datastru.h"
#include  <stdio.h>
#include  <malloc.h>

void unite(LINKLIST *a, LINKLIST *b, LINKLIST *c){
/*两有序链表a, b合并到一新链表c中，c表中元素值也有序*/
LINKLIST *la, *lb, *lc, *p;

la = a->next; lb = b->next; lc = c;
while(la != NULL && lb != NULL)
 { if (la->data <= lb->data)
    { p = (LINKLIST *) malloc(sizeof(LINKLIST));
      p->data = la->data;   p->next = NULL;
      lc->next = p;   lc = lc->next;   la = la->next;
    }
   else
    { p = (LINKLIST *) malloc(sizeof(LINKLIST));
      p->data = lb->data;   p->next = NULL;
      lc->next = p;   lc = lc->next;   lb = lb->next;
    }
 }
 while(la != NULL)
 {  p = (LINKLIST *) malloc(sizeof(LINKLIST));
    p->data = la->data;   p->next = NULL;
    lc->next = p;   lc = lc->next;  la = la->next;
 }
while(lb != NULL)
 {  p = (LINKLIST *) malloc(sizeof(LINKLIST));
    p->data = lb->data;   p->next = NULL;
    lc->next = p;   lc = lc->next;   lb = lb->next;
 }
}

int count_head(LINKLIST *head){
/*带头结点的单链表：输出单链表元素值并计数*/
  int i = 0;
  LINKLIST *p;
  p = head->next;
  printf("输出单链表元素值 : ");
  while(p != NULL)
   {i++;
    printf("  %c",p->data);
    p = p->next;}
    printf("\n");
    return i;
}

LINKLIST *creatlink_order_head(LINKLIST *head)
/*建立带头结点的、元素值有序的单链表*/
{ LINKLIST *t, *p, *q;
  char ch;

  t = (LINKLIST *)malloc(sizeof(LINKLIST));
  head = t;  t->next = NULL;
  printf("单链表元素值为单个字符, 连续输入，$为结束字符  : ");
  while ((ch = getchar()) != '$')
   {t = (LINKLIST *)malloc(sizeof(LINKLIST));
    t->data = ch;
    q = head;  p = head->next;
    while( p != NULL && p->data <= ch) {
	q = p;  p = p->next;}
    q->next = t; t->next = p;
   }
  return(head);
}

main()
{
  LINKLIST *a1 = NULL, *a2 = NULL, *c;
  int  num;

  printf("\n    建立单链表a1\n\n");
  a1 = creatlink_order_head(a1);
  fflush(stdin);
  num = count_head(a1);
  printf("单链表a1元素个数 = %d\n", num);
  printf("\n    建立单链表a2\n\n");
  a2 = creatlink_order_head(a2);
  fflush(stdin);
  num = count_head(a2);
  printf("单链表a2元素个数 = %d\n", num);
  c = (LINKLIST *)malloc(sizeof(LINKLIST));
  c->next = NULL;
  unite(a1, a2, c);
  printf("\n\n合并到单链表c中\n");
  num = count_head(c);
  printf("单链表c元素个数 = %d\n", num);
}