鏈表
list 鏈表是線性表的一類鬓照。線性表分順序表和鏈表，順序表可以簡單理解成數(shù)組
正常定義一個數(shù)組孤紧，計算機(jī)會從內(nèi)存中取出一塊連續(xù)的地址來存放給定長度的數(shù)組
而鏈表則是由若干個結(jié)點組成豺裆，每個結(jié)點代表一個元素，且結(jié)點在內(nèi)存中的存儲位置通常是不連續(xù)的
鏈表一般由兩部分組成号显，數(shù)據(jù)域和指針域
struct node {
typename data; //數(shù)據(jù)域 要存放的數(shù)據(jù)
node* next; //指針域 指向下一個結(jié)點的地址
}
以鏈表是否存在頭結(jié)點臭猜，可以把鏈表分成帶頭結(jié)點的鏈表和不帶頭結(jié)點的鏈表
頭結(jié)點和第一個結(jié)點：頭結(jié)點一般稱為head，且其數(shù)據(jù)域data不存放任何內(nèi)容押蚤，指針域next指向第一個數(shù)據(jù)域有內(nèi)容的結(jié)點（一般直接把這個結(jié)點叫做第一個結(jié)點）
最后一個結(jié)點的next指針指向NULL获讳，即空地址，表示一條鏈表的結(jié)尾
下文鏈表均采用帶頭結(jié)點的寫法
鏈表結(jié)點分配內(nèi)存空間
介紹兩種方法：C的malloc函數(shù)與C++的new運算符
- malloc函數(shù)
malloc函數(shù)在C中stdlib.h頭文件下用于申請動態(tài)內(nèi)存的函數(shù)活喊，其返回類型是申請的同變量類型的指針
typename* p = (typename*)malloc(sizeof(typename));
//以申請一個int型變量和node型結(jié)構(gòu)體變量為例
int* p = (int*)malloc(sizeof(int));
node* p = (node*)malloc(sizeof(node));
//以需要申請的內(nèi)存空間大小（即sizeof(node))為malloc函數(shù)的參數(shù)
malloc函數(shù)向內(nèi)存申請一塊大小為sizeof(node)的空間，并且返回指向這塊空間的指針钾菊。
至此該指針仍是一個未確定類型的指針void帅矗，需要把它強(qiáng)制轉(zhuǎn)換為node型的指針，在malloc前加(node)煞烫，于是等號右邊得到一個node型的指針浑此，并通過賦值等號把這個指針賦給node*型的指針變量p。
至此滞详，成功申請了一塊node類型大小的內(nèi)存空間凛俱，并通過指針p來訪問它。
可能存在失敗的情況料饥，就會返回空指針NULL
int* p = (int*)malloc(100000 * sizeof(int)); //申請了較大的動態(tài)內(nèi)存
- new運算符
new是C++中用來申請動態(tài)空間的運算符蒲犬，其返回類型同樣是申請的同變量類型的指針
typename* p = new typename;
//以申請一個int型變量和node型結(jié)構(gòu)體變量為例
int* p = new int;
node* p = new node;
//可以申請較大動態(tài)數(shù)組
int* p = new int[100000];
- 內(nèi)存泄漏
內(nèi)存泄漏是指使用malloc和new開辟出來的內(nèi)存空間在使用過后沒有釋放，導(dǎo)致其在程序結(jié)束之前始終占據(jù)該內(nèi)存空間岸啡。
需要及時釋放malloc和new開辟出來的空間原叮。
3.1 free
free函數(shù)對應(yīng)malloc函數(shù)，在stdilb.h頭文件下
實現(xiàn)兩個效果：釋放指針變量p所指向的內(nèi)存空間巡蘸，將
free(p)奋隶； //p為所需要釋放內(nèi)存空間的指針變量
3.2 delete運算符
delete運算符對應(yīng)new運算符，其使用方法和實現(xiàn)效果均與free相同
delete(p);
鏈表基本操作
- 創(chuàng)建鏈表
#include<stdio.h>
#include<stdlib.h>
struct node {
int data;
node* next;
};
node* create(int Array[]) {
node *p, *pre, *head; //pre保存當(dāng)前結(jié)點的前驅(qū)結(jié)點悦荒，head為頭結(jié)點
head = new node; //創(chuàng)建頭結(jié)點
head->next = NULL; //頭結(jié)點不需要數(shù)據(jù)域唯欣，指針域初始為NULL
pre = head; //記錄pre為head
for(int i = 0; i < 5; i++) {
p = new node; //創(chuàng)建結(jié)點
//將Array[i]賦給新建的結(jié)點作為數(shù)據(jù)域，也可以scanf輸入
p->data = Array[i];
p->next = NULL; //新結(jié)點的指針域需要設(shè)為NULL
pre->next = p; //前驅(qū)結(jié)點的指針域設(shè)為當(dāng)前新建結(jié)點的地址
pre = p; //把pre設(shè)為p搬味，作為下個結(jié)點的前驅(qū)
}
return head;
}
int main() {
int Array[5] = {5, 3, 6, 1, 2};
node* L = create(Array); //新建鏈表境氢，返回的頭指針head賦給L
L = L->next; //從第一個結(jié)點開始有數(shù)據(jù)域
while(L != NULL) {
printf("%d ", L->data); //輸入每個結(jié)點的數(shù)據(jù)域
L = L->next;
}
return 0;
}
//輸出 5 3 6 1 2
- 查找元素
從第一個結(jié)點開始，不斷判斷當(dāng)前結(jié)點的數(shù)據(jù)域是否等于 x身腻，如果等于产还，那么就給計數(shù)器count + 1。當(dāng)鏈表到鏈表結(jié)尾時嘀趟，count的值就是鏈表中元素 x 的個數(shù)脐区。
int search(node* head, int x) {
int count = 0; //計數(shù)器
node* p = head->next; //從第一個結(jié)點開始
while(p != NULL) { //只要沒有到鏈表末尾
if(p->data == x) {
count++;
}
p = p->next;
}
return count;
}
//該段代碼也可直接寫進(jìn)創(chuàng)建鏈表中使用，將創(chuàng)建的頭指針L作為第一個參數(shù)傳入
- 插入元素
首先找到插入結(jié)點的位置她按，將要插入位置的結(jié)點指向后一個結(jié)點牛隅，再將插入位置的前一個結(jié)點指向需要插入的結(jié)點處（想想為什么不能調(diào)換順序？初學(xué)的時候卡過我）
void insert(node* head, int pos, int x) {
node* p = head;
for(int i = 0; i < pos -1; i++) {
p = p->next;
}
node* q = new node; //新建結(jié)點
q->data = x; //新結(jié)點的數(shù)據(jù)域為x
q->next = p->next; //新結(jié)點的下一個結(jié)點指向原先插入位置的結(jié)點
p->next = q; //前一個位置的結(jié)點指向新結(jié)點
}
//該段代碼同樣可插入到創(chuàng)建鏈表的過程中
- 刪除元素
首先由指針變量p枚舉結(jié)點酌泰，另一個指針變量pre表示p指向結(jié)點的前驅(qū)結(jié)點媒佣；當(dāng)p所指數(shù)據(jù)域恰好為x時，令pre所指結(jié)點的指針域next指向p所指結(jié)點的下一個結(jié)點陵刹，釋放p所指結(jié)點的內(nèi)存空間默伍，最后令p指向pre所指結(jié)點的下一個結(jié)點
void del(node* head, int x) {
node* p = head->next; //p從第一個結(jié)點開始枚舉
node* pre = head; //pre始終保存p的前驅(qū)結(jié)點的指針
while(p != NULL) {
if(p->next == x) { //找到數(shù)據(jù)域為x的結(jié)點
pre->next = p->next;
delete(p);
p = pre->next;
} else {
pre = p;
p = p->next;
}
}
}
//同樣也可再創(chuàng)建鏈表部分的代碼中使用
靜態(tài)鏈表
前面講的都是動態(tài)鏈表，即需要指針來建立結(jié)點之間的連接關(guān)系。而對有些問題如結(jié)點的地址是比較小的整數(shù)就沒有必要去建立動態(tài)鏈表也糊，而應(yīng)使用方便的多的靜態(tài)鏈表
靜態(tài)鏈表的實現(xiàn)原理是hash炼蹦，即通過建立一個結(jié)構(gòu)體數(shù)組，并令數(shù)組的下標(biāo)直接表示結(jié)點的地址狸剃，來達(dá)到直接訪問數(shù)組中的元素就能訪問結(jié)點的效果掐隐。另外，由于結(jié)點的訪問非常方便钞馁，因此靜態(tài)鏈表是不需要頭結(jié)點的虑省。
struct Node {
typename data; //數(shù)據(jù)域
int next; //指針域
}node[size];
next是一個int型的整數(shù)，用以存放下一個結(jié)點的地址（事實上就是數(shù)組下標(biāo)）
node[11111] = 22222;
node[22222] = 33333;
node[33333] = -1; //-1對應(yīng)動態(tài)鏈表的NULL僧凰，表示沒有后繼結(jié)點
在使用靜態(tài)鏈表時探颈，盡量不要把結(jié)構(gòu)體類型名和結(jié)構(gòu)體變量名取相同名字
