C語言基礎(chǔ)教程之鏈表

（一）什么是鏈表？

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

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

順序存儲(chǔ)對(duì)空間的利用率不高；

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

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

鏈?zhǔn)酱鎯?chǔ)大小可以伸縮；

鏈?zhǔn)酱鎯?chǔ)利用率高。

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

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

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

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

（四）一個(gè)簡單案例

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

結(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)造一個(gè)鏈表頭
傳參：空
返回值：鏈表頭
調(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("請(qǐng)輸入以下信息:\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é)點(diǎn)
功能：插入結(jié)點(diǎn)到鏈表中
傳參：鏈表頭
返回值：鏈表頭
調(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("請(qǐng)輸入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é)點(diǎn)
功能：刪除結(jié)點(diǎn)
傳參：鏈表頭
返回值：鏈表頭
調(diào)用函數(shù)：無

PH delete_list(PH phead) { PN node=phead->pfhead; PN node2; char id[32]; printf("請(qǐng)輸入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; }