第十六章 数据管理
16.1 简单链表
链表是一种常见的基础数据结构，是一种线性表，但并不会按线性的顺序存储数据，而是在每一个结点里存储下一个结点的指针。由于不必按顺序存储，链表的插入和删除操作不需要移动数据。
案例 通讯录管理
问题描述 完成一个采用有序链表管理的通讯录，具备插入、查询、删除、输出通信者信息的功能。每个通信者具有编号、姓名、性别、电话及地址信息。
为采用链表管理多条通信者记录，首先定义通信者的数据结构和链表结点的结构。设链表结点仅含一个数据域和一个指针域，数据域描述通信者的相关信息。
定义通信者的结点类型：
typedef struct
{
char num[5]; /*编号*/
char name[20]; /*姓名*/
char sex[3]; /*性别*/
char phone[13]; /*电话*/
char addr[31]; /*地址*/
}DataType;
因此，线性表的链式存储结构定义如下：
typedef struct node
{
DataType data; /*结点数据域*/
struct node *next; /*结点指针域*/
}ListNode;
typedef ListNode * LinkList;
ListNode * p; /*定义一个指向结点的指针变量*/
LinkList head; /*定义指向单链表的头指针*/
上面的LinkList和ListNode *是不同名字的同一指针类型，取不同的名是为了在概念上更明确。指针变量的值要么为空（NULL），不指向任何结点，要么非空，值为一个结点的存储地址。指针变量指向的结点没有具体说明，在程序执行过程中，需要存储结点时才产生，通过malloc函数实现。如给指针变量p分配一个结点的地址：p=(ListNdoe *)malloc(sizeof(ListNode));该语句功能是申请分配一个类型为ListNode的结点的地址空间，将其首地址存入指针变量p中。结点不需要时可用free(p)释放结点的存储空间，这时p为空值NULL。
为实现通讯录管理的功能，首先设计一个含有多个菜单的主菜单程序，然后实现菜单中的相应功能：
Case1 通讯录链表初始化；
Case2 通信者结点的插入；
Case3 通信者结点的查询；
Case4 通信者结点的删除；
Case5 通信录链表的输出；
Case6 退出管理系统。
请选择0~5：使用数字0~5选择菜单项，其他输入不起作用。
1.通讯录链表初始化
链表初始化是建立一个空的链表，这里的链表采用的是带头结点的链表。带头结点的链表好处是使得在链表头和尾插入结点与在链表中间插入算法一致，简化了代码。
初始化链表结构：头指针head --> 头结点 NULL
2.通信者结点的插入
因为是有序（依据编号从小到大）链表，首先找插入位置。需要找到第一个比插入结点p编号大的结点p2，p要插入在p2前。需要用指针p1记载p2之前的结点，这样插入时，即可把p插在p1之后p2之前。
插入结点的关键代码为：
p->next=p2;
p1->next=p;
3.通信者结点的查询
可分别依据编号和姓名进行查询。
（1）依据编号：设链表中结点按编号升序排列，查询过程中，从头开始比较。碰到待查编号等于某结点编号时，返回该结点地址。碰到待查编号大于某结点编号时，继续和下一结点比较。碰到待查编号小于某结点编号时，说明链表中不存在该编号的结点，返回NULL。
（2）依据姓名：从头开始比较，依次用待查姓名和各个结点的姓名比较，相等则返回该结点地址。否则，继续和下一结点比较，直到链表结束，若没有相等结点则返回空指针。
4.通信者结点的删除
首先调用查询功能找到结点p，删除时还需要找到该结点之前的结点q，删除语句为：
q->next=p->next;
最后通过free(p)释放p指向的结点空间。
5.通信录链表的输出
依次遍历各个结点的数据信息
6.退出管理系统
终止程序
例：通讯录有序链表管理(待修改)
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
/*通讯录结点类型*/
typedef struct
{
char num[5]; /*编号*/
char name[8]; /*姓名*/
char sex[3]; /*性别*/
char phone[13]; /*电话*/
char addr[31]; /*地址*/
} DataType;
/*结点类型定义*/
typedef struct node
{
DataType data; /*结点数据域*/
struct node *next; /*结点指针域*/
} ListNode;
typedef ListNode * LinkList;
LinkList head;
ListNode *p;
/*函数说明*/
int menu_select();
LinkList createList();
void insertNode(LinkList head,ListNode *p);
ListNode * listFind(LinkList head);
void delNode(LinkList head);
void printList(LinkList head);
/*主函数*/
void main()
{
for( ; ; )
{
switch(menu_select())
{
case 1:
printf("**************************\n");
printf("* 通讯录链表的初始化 *\n");
printf("**************************\n");
head=createList();
break;
case 2:
printf("**************************\n");
printf("* 通讯者信息的添加 *\n");
printf("**************************\n");
printf("编号 姓名 性别 电话 地址\n");
p=(ListNode *)malloc(sizeof(ListNode)); /*申请新结点*/
scanf("%s%s%s%s%s",p->data.num,p->data.name,p->data.sex,p->data.phone,p->data.addr);
insertNode(head,p);
break;
case 3:
