（一）什么是鏈表？

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

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

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

內存隨著時間的增加會找不到大塊的順序空間；

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

鏈式存儲大小可以伸縮；

鏈式存儲利用率高。

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

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

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