ch4_3.c

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

#include<stdio.h>
#include<stdlib.h>
typedef struct list                      /* 链表结构声明 */
{
  int data;                                   /* 结点内容 */
  struct list *link;                 /* 指向下一个结点的地址 */
}node; 
void print_list(node *);
node *create_list(int *, int);
node *invert(node *);
void free_list(node *);
void main( )
{
  node *head=NULL;
  int array[5]={ 1, 3, 5, 7, 9 };
  head=create_list(array, 5);                 /* 建立链表 */
  printf("原来的链表:\n");
  print_list(head); 
  head=invert(head);                 /* 将原来的链表反转 */
  printf("反转后的链表:\n");
  print_list(head); 
  free_list(head);                 /* 将链表的内存归还 */
}

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,*pre_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;
}

node *invert(node *head)             /* 单向链表反转函数 */
{
  node *p, *q, *r;
  p=head, q=NULL; 
  while(p != NULL)
  {
    r=q;
    q=p;
    p=p->link;
    q->link=r;
  }
  head=q;
  return head;
}

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