ch4_5.c

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

#include <stdio.h>
#include <stdlib.h>
typedef struct list{        /* 声明链表结构 */
  int data;                      /* 数据域 */
  struct list *link;               /* 指针域 */
}node;
node *create_list(node *);
int length(node *);
void print_list(node *);
void main( )
{
  node *head=NULL;
  head=create_list(head);      /* 建立链表 */
  printf("链表:\n");
  print_list(head);                        
  printf("\n此链表的长度为:%d\n", length(head));  /* 输出链表长度 */
}
                                          
node *create_list(node *head)
{
  node *new_node;                                 /* 新结点指针 */
  node *ptr;                                /* 遍历链表指针 */
  int input;                                    /* 使用者输入值 */
  printf("请输入Ctrl+Z表示数据输入结束\n");
  printf("请输入结点内容(int)=>\n");
  while(scanf("%d", &input) != EOF)
  {                        /* 若输入值为EOF(文件结束码)才停止循环 */
    new_node=(node *)malloc(sizeof(node));           /* 配置内存空间 */
    if(new_node == NULL)                         /* 检查内存指针 */
    {
      printf("内存配置失败!\n");
      exit(1);                                          /* 结束程序 */
    }
    new_node->data=input;           /* 将输入值放入新结点的数据域 */   
    if(head == NULL)                       /* 若链表为空串列时 */
    {
      head=new_node;         /* 链表的起始结点即为新加入的结点 */
      new_node->link=NULL;         /* 将新结点的链结域设为NULL */
    }
    else          /* 先遍历至最后一个结点，再将新结点接到后面 */
    {
      for(ptr=head; ptr->link!=NULL; ptr=ptr->link);
      new_node->link=ptr->link;
      ptr->link=new_node;
    }
  }
  return head;
}

void print_list(node *head)             /* 输出链表的内容 */
{
  node *ptr;
  for(ptr=head; ptr!=NULL; ptr=ptr->link)
    printf("[%d]", ptr->data);
  printf("\n");
}

int length(node *head)                 /* 计算出链表的长度 */
{
  int len=0;                           /* 链表长度的累加器 */
  node *ptr;                         /* 遍历链表所用的指针 */
  for(ptr=head; ptr!=NULL; ptr=ptr->link)
    len++;                              /* 遍历时，将链表长度加一 */
  return len;                            /* 返回链表的长度 */
}