ch4_2.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 *find_node(node *, int);
node *delete_node(node *, node *);
void main( )
{
  node *head=NULL, *ptr=NULL;
  int array[5]={ 1, 3, 5, 7, 9 };              /* 初始链表的数组 */
  int input;                                   /* 使用者输入值 */
  head=create_list(array, 5);                   /* 建立链表 */
  printf("原来的链表\n");
  print_list(head);                      /* 输出链表内的数据值 */
  printf("请输入Ctrl+Z表示数据输入结束\n");
  printf("请输入欲删除的结点内容(int)=>\n");
  while(scanf("%d", &input) != EOF)
  {                  /* 若输入值为EOF(文件结束码)才停止循环 */
    ptr=find_node(head, input);                      /* 查寻结点 */
    if(head->data!=input && ptr==NULL)       /* 若没有找到结点 */
      printf("没有找到要删除的结点!\n");
    else
      head=delete_node(head, ptr);                  /* 删除结点 */
  }
  printf("删除后的链表\n");
  print_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;                               /* 链表起始指针 */
  node *ptr;                              /* 遍历链表的指针 */
  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(ptr=head; ptr->link!=NULL; ptr=ptr->link);
      new_node->link=ptr->link;
      ptr->link=new_node;
    }
  }
  return head;                     /* 返回建立好的链表指针 */
}

node *find_node(node *head, int entry)
{
  node *ptr=head;
  if(ptr->data == entry) return NULL;
  for( ; ptr->link!=NULL; ptr=ptr->link)         /* 遍历链表 */    
    if(ptr->link->data == entry)       /* 若下一结点内容值与传入值相同 */
      return ptr;                           /* 则返回该结点的地址 */
  return NULL;
}

node *delete_node(node *head, node *pre_node)
{
  node *del_node;
  if(pre_node == NULL)      /* 当删除结点是链表的第一个结点时 */
  {
    del_node=head;
    head=head->link;
  }
  else
  {                      /* 指定pre_node的下一结点就是要删除的结点 */
    del_node=pre_node->link;
    if(del_node->link == NULL)          /* 若要删除的是最后一个结点时 */
    /* 直接将删除的前一结点的下一链接地址设置为NULL */
      pre_node->link=NULL; 
    else
    /* 将删除结点的前一结点的下一链接地址设定为删除结点的下一结点地址 */
      pre_node->link=del_node->link;
  }
  free(del_node);             /* 将删除的结点所占用的内存空间释放掉 */
  return head;                     /* 返回改变过后的链表开始指针 */
}