C语言基础教程之链表

（一）什么是链表？

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

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

顺序存储对空间的利用率不高；

内存随着时间的增加会找不到大块的顺序空间；

数组的大小只能是固定的，增加或删除都会移动大量数据；

链式存储大小可以伸缩；

链式存储利用率高。

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

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

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