（一）什么是鏈表？

鏈表是一種常見的基礎數(shù)據(jù)結(jié)構(gòu)，是一種線性表，是一種在物理存儲單元上非連續(xù)非順序的存儲結(jié)構(gòu)。
鏈表有一系列節(jié)點構(gòu)成，節(jié)點在運行時動態(tài)生成，每個節(jié)點包括數(shù)據(jù)域，數(shù)據(jù)域存儲當前節(jié)點的信息，指針域存儲下一個節(jié)點的手地址。

（二）為什么要使用鏈表？

順序存儲對空間的利用率不高；

內(nèi)存隨著時間的增加會找不到大塊的順序空間；

數(shù)組的大小只能是固定的，增加或刪除都會移動大量數(shù)據(jù)；

鏈式存儲大小可以伸縮；

鏈式存儲利用率高。

（三）單向鏈表和雙向鏈表

單向鏈表：每個元素包含一個指針域，該指針域指向該元素的直接后繼元素。
雙向鏈表：每個元素除了有一個指針域指向直接后繼元素以外，還有一個指針指向其直接前驅(qū)元素。
如果把最后一個節(jié)點的指針指向第一個結(jié)點，同時把第一個結(jié)點的前向指針指向最后一個結(jié)點，這樣就構(gòu)成單向循環(huán)鏈表和雙向循環(huán)鏈表。

c語言實現(xiàn)--單向循環(huán)鏈表操作

c語言實現(xiàn)--雙向循環(huán)鏈表操作

（四）一個簡單案例

這是一個小的系統(tǒng)，能實現(xiàn)幾項簡單的功能：創(chuàng)建鏈表、輸入數(shù)據(jù)、查看信息、保存信息、讀取信息、 刪除結(jié)點、 查找信息
以下為部分代碼：

結(jié)構(gòu)體定義

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;

創(chuàng)建鏈表
功能：構(gòu)造一個鏈表頭
傳參：空
返回值：鏈表頭
調(diào)用函數(shù)：無

PH create_list() { PH phead=NULL; phead = (PH)malloc(sizeof(Head)); phead->pfhead=NULL; phead->len=0; return phead; }

獲取數(shù)據(jù)
功能：獲取數(shù)據(jù)
傳參：空
返回值：鏈表頭
調(diào)用函數(shù)：無

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

插入結(jié)點
功能：插入結(jié)點到鏈表中
傳參：鏈表頭
返回值：鏈表頭
調(diào)用函數(shù)：獲取數(shù)據(jù)函數(shù) getdate()

PH insert_list(PH phead) { NODE* node; int flag=0,i=0; while(1) { if(flag!=0) { printf("是否繼續(xù)添加:1繼續(xù),0結(jié)束\n"); printf("你的選擇:"); scanf("%d",&i); getchar(); if(i == 0) break; } node = getdate(); node->next=phead->pfhead; phead->pfhead=node; phead->len++; flag++; } return phead; }

打印鏈表
功能：打印鏈表信息
傳參：鏈表頭
返回值：空
調(diào)用函數(shù)：無

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

查找數(shù)據(jù)
功能：查找數(shù)據(jù)成員
傳參：鏈表頭
返回值：無
調(diào)用函數(shù)：無

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

刪除結(jié)點
功能：刪除結(jié)點
傳參：鏈表頭
返回值：鏈表頭
調(diào)用函數(shù)：無

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

保存信息
功能：保存信息到文件
傳參：鏈表頭
返回值：無
調(diào)用函數(shù)：無

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

讀取信息
功能：從文件中讀取信息
傳參：空
返回值：鏈表頭
調(diào)用函數(shù)：無

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