C语言：链表的概念和其简单操作

（一）什么是链表？

链表是一种常见的基础数据结构，是一种线性表，是一种在物理存储单元上非连续非顺序的存储结构。
链表有一系列节点构成，节点在运行时动态生成，每个节点包括数据域，数据域存储当前节点的信息，指针域存储下一个节点的手地址。

（二）为什么要使用链表？

1. 顺序存储对空间的利用率不高；
2. 内存随着时间的增加会找不到大块的顺序空间；
3. 数组的大小只能是固定的，增加或删除都会移动大量数据；
4. 链式存储大小可以伸缩；
5. 链式存储利用率高。

（三）单向链表和双向链表

单向链表：每个元素包含一个指针域，该指针域指向该元素的直接后继元素。
双向链表：每个元素除了有一个指针域指向直接后继元素以外，还有一个指针指向其直接前驱元素。
如果把最后一个节点的指针指向第一个结点，同时把第一个结点的前向指针指向最后一个结点，这样就构成单向循环链表和双向循环链表。

• c语言实现--单向循环链表操作
• c语言实现--双向循环链表操作

（四）一个简单案例

这是一个小的系统，能实现几项简单的功能：创建链表、输入数据、查看信息、保存信息、读取信息、 删除结点、 查找信息
以下为部分代码：

结构体定义

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;
}