（一）什么是链表？
链表是一种常见的基础数据结构，是一种线性表，是一种在物理存储单元上非连续非顺序的存储结构。
链表有一系列节点构成，节点在运行时动态生成，每个节点包括数据域，数据域存储当前节点的信息，指针域存储下一个节点的手地址。
（二）为什么要使用链表？
- 顺序存储对空间的利用率不高；
- 内存随着时间的增加会找不到大块的顺序空间；
- 数组的大小只能是固定的，增加或删除都会移动大量数据；
- 链式存储大小可以伸缩；
- 链式存储利用率高。
（三）单向链表和双向链表
单向链表：每个元素包含一个指针域，该指针域指向该元素的直接后继元素。
双向链表：每个元素除了有一个指针域指向直接后继元素以外，还有一个指针指向其直接前驱元素。
如果把最后一个节点的指针指向第一个结点，同时把第一个结点的前向指针指向最后一个结点，这样就构成单向循环链表和双向循环链表。
（四）一个简单案例
这是一个小的系统，能实现几项简单的功能：创建链表、输入数据、查看信息、保存信息、读取信息、 删除结点、 查找信息
以下为部分代码：
结构体定义
typedef struct date
{
char name[32];
char pass[32];
char id[32];
}DATE;
typedef struct head
{
int len;
struct node * pfhead;
}Head,*PH;
typedef struct node
{
DATE date;
struct node * next;
}NODE,*PN;
创建链表
功能：构造一个链表头
传参：空
返回值：链表头
调用函数：无
PH create_list()
{
PH phead=NULL;
phead = (PH)malloc(sizeof(Head));
phead->pfhead=NULL;
phead->len=0;
return phead;
}
获取数据
功能：获取数据
传参：空
返回值：链表头
调用函数：无
PN getdate()
{
PN pnode=NULL;
pnode = (PN)malloc(sizeof(NODE));
printf("请输入以下信息:\n");
printf("name:");
scanf("%s",pnode->date.name);
getchar();
printf("pass:");
scanf("%s",pnode->date.pass);
getchar();
printf("id:");
scanf("%s",pnode->date.id);
getchar();
return pnode;
}
插入结点
功能：插入结点到链表中
传参：链表头
返回值：链表头
调用函数：获取数据函数 getdate()
PH insert_list(PH phead)
{
NODE* node;
int flag=0,i=0;
while(1)
{
if(flag!=0)
{
printf("是否继续添加:1继续,0结束\n");
printf("你的选择:");
scanf("%d",&i);
getchar();
if(i == 0)
break;
}
node = getdate();
node->next=phead->pfhead;
phead->pfhead=node;
phead->len++;
flag++;
}
return phead;
}
打印链表
功能：打印链表信息
传参：链表头
返回值：空
调用函数：无
void print_list(PH phead)
{
PN node=phead->pfhead;
while(node!=NULL)
{
printf("%-8s%-8s%-8s\n",node->date.name,node->date.pass,node->date.id);
node=node->next;
}
printf("任意键退出:");
getchar();
}
查找数据
功能：查找数据成员
传参：链表头
返回值：无
调用函数：无
void search_list(PH phead)
{
PN node=phead->pfhead;
char id[32];
printf("请输入ID:");
scanf("%s",id);
getchar();
while(node->next!=NULL && strcmp(node->date.id,id)!=0)
{
node = node->next;
}
if(strcmp(node->date.id,id)==0)
{
printf("%-8s%-8s%-8s\n",node->date.name,node->date.pass,node->date.id);
}
else
{
printf("查无此人\n");
}
printf("任意键退出:");
getchar();
return ;
}
删除结点
功能：删除结点
传参：链表头
返回值：链表头
调用函数：无
PH delete_list(PH phead)
{
PN node=phead->pfhead;
PN node2;
char id[32];
printf("请输入ID:");
scanf("%s",id);
getchar();
while(node->next!=NULL && strcmp(node->date.id,id)!=0)
{
node2=node;
node = node->next;
}
if(strcmp(node->date.id,id)==0)
{
if(node == phead->pfhead)
phead->pfhead=node->next;
else
node2->next=node->next;
phead->len--;
}
else
{
printf("查无此人\n");
}
return phead;
}
保存信息
功能：保存信息到文件
传参：链表头
返回值：无
调用函数：无
void save_list(PH phead)
{
FILE * fp;
if((fp=fopen("phead","w"))==NULL)
{
printf("打开文件失败\n");
exit(1);
}
PN node=phead->pfhead;
while(node!=NULL)
{
fwrite(node,sizeof(NODE),1,fp);
node=node->next;
}
fclose(fp);
return ;
}
读取信息
功能：从文件中读取信息
传参：空
返回值：链表头
调用函数：无
PH read_list()
{
FILE * fp;
if( (fp=fopen("phead","r"))==NULL)
{
printf("打开文件失败\n");
exit(1);
}
PH phead=(PH)malloc(sizeof(Head));
phead->pfhead=NULL;
PN node=(PN)malloc(sizeof(NODE));
while(fread(node,sizeof(NODE),1,fp)>0)
{
node->next=phead->pfhead;
phead->pfhead=node;
phead->len++;
node=(PN)malloc(sizeof(NODE));
}
fclose(fp);
return phead;
}
