ch4_4.c

本内容为清华大学严蔚敏版数据结构部分算法实现代码

#include<stdio.h>
#include<stdlib.h>
typedef struct list         /* 声明链表结构 */
{
  int data;                 /* 数据域 */
  struct list *link;        /* 指针域 */
}node;
node *Z=NULL;
void print_list(node *);
node *create_list(int *, int);
void free_list(node *);
void concatenate(node *, node *);
void main( )
{
  node *X=NULL, *Y=NULL;
  int array1[6]={ 1, 3, 5, 7, 9, 11 };
  int array2[6]={ 2, 4, 6, 8, 10, 12 };
  X=create_list(array1, 6);                 /* 建立链表X */
  Y=create_list(array2, 6);                 /* 建立链表Y */
  printf("原来的链表X:\n");
  print_list(X);
  printf("原来的链表Y:\n");
  print_list(Y);
  concatenate(X, Y);                /* 将链表X，Y合并成Z */
  printf("合并后的链表Z:\n");
  print_list(Z); 
  free_list(Z);
}

void print_list(node *head)     /* 输出链表的内容 */
{
  node *ptr;                /* 遍历链表所用的指针 */
  for(ptr=head; ptr!=NULL; ptr=ptr->link)
    printf("[%d]", ptr->data);   /* 输出链表结点内容 */
  printf("\n");                /* 换行 */
}
                            
node *create_list(int *array, int len)   /* 依数组架构出链表 */
{
  node *head;                  /* 链表的起始指针 */
  node *pre_node;            /* 新结点之前结点的指针 */
  node *new_node;                   /* 新结点的指针 */
  int i;
  for(i=0; i<len; i++)
  {
    new_node=(node *)malloc(sizeof(node));  /* 配置内存空间给新结点 */
    if(new_node == NULL)
    {
      printf("内存配置失败!\n");
      exit(1);              /* 立刻结束程式 */
    }
    new_node->data=array[i];  /* 将数组内容置入链表中 */
    if(i == 0)            /* 当第一次放入时，将head指针指向第一个结点 */
    {
      new_node->link=NULL;
      head=new_node;
    }
    else                  /* 先遍历至最后一个结点，再加入新的结点 */
    {
      for(pre_node=head; pre_node->link!=NULL; pre_node=pre_node->link);
      new_node->link=pre_node->link;
      pre_node->link=new_node;
    }
  }
  return head;               /* 将改变过后的链表返回 */ 
}

void free_list(node *head)    /* 将整个链表的内存归还 */
{
  node *free_node;
  while(head != NULL)
  {
    free_node=head;
    head=head->link;
    free(free_node);
  }
}

void concatenate(node *X, node *Y)
{
  node *ptr;
  if(X == NULL)          /* 若X为空链表，则将Y的地址返回 */
    Z=Y;
  else if(Y == NULL)       /* 若Y为空链表，则将X的地址返回 */
    Z=X;
  else
  {                   /* 遍历至尾端结点 */
    for(ptr=X, Z=X; ptr->link!=NULL; ptr=ptr->link); 
            /* 将链表X的尾端结点指向链表Y的开始结点 */
    ptr->link=Y;
  }
}