鏈表

list 鏈表是線性表的一類。線性表分順序表和鏈表，順序表可以簡單理解成數(shù)組
正常定義一個數(shù)組，計算機會從內(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運算符

1. 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)存空間大?。磗izeof(node))為malloc函數(shù)的參數(shù)

malloc函數(shù)向內(nèi)存申請一塊大小為sizeof(node)的空間，并且返回指向這塊空間的指針。
至此該指針仍是一個未確定類型的指針void，需要把它強制轉(zhuǎn)換為node型的指針，在malloc前加(node)，于是等號右邊得到一個node型的指針，并通過賦值等號把這個指針賦給node*型的指針變量p。
至此，成功申請了一塊node類型大小的內(nèi)存空間，并通過指針p來訪問它。
可能存在失敗的情況，就會返回空指針NULL

int* p = (int*)malloc(100000 * sizeof(int));    //申請了較大的動態(tài)內(nèi)存

2. 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];

3. 內(nèi)存泄漏
   內(nèi)存泄漏是指使用malloc和new開辟出來的內(nèi)存空間在使用過后沒有釋放，導致其在程序結(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);

鏈表基本操作

1. 創(chuàng)建鏈表

#include<stdio.h>
#include<stdlib.h>

struct node {
    int data;
    node* next;
};

node* create(int Array[]) {
    node *p, *pre, *head;   //pre保存當前結(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è)為當前新建結(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

2. 查找元素
   從第一個結(jié)點開始，不斷判斷當前結(jié)點的數(shù)據(jù)域是否等于 x，如果等于，那么就給計數(shù)器count + 1。當鏈表到鏈表結(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;
}
//該段代碼也可直接寫進創(chuàng)建鏈表中使用，將創(chuàng)建的頭指針L作為第一個參數(shù)傳入

3. 插入元素
   首先找到插入結(jié)點的位置，將要插入位置的結(jié)點指向后一個結(jié)點，再將插入位置的前一個結(jié)點指向需要插入的結(jié)點處（想想為什么不能調(diào)換順序？初學的時候卡過我）

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)建鏈表的過程中

4. 刪除元素
   首先由指針變量p枚舉結(jié)點，另一個指針變量pre表示p指向結(jié)點的前驅(qū)結(jié)點；當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ù)組的下標直接表示結(jié)點的地址，來達到直接訪問數(shù)組中的元素就能訪問結(jié)點的效果。另外，由于結(jié)點的訪問非常方便，因此靜態(tài)鏈表是不需要頭結(jié)點的。

struct Node {
    typename data;  //數(shù)據(jù)域
    int next;       //指針域 
}node[size]; 

next是一個int型的整數(shù)，用以存放下一個結(jié)點的地址（事實上就是數(shù)組下標）

  node[11111] = 22222;
  node[22222] = 33333;
  node[33333] = -1; //-1對應(yīng)動態(tài)鏈表的NULL，表示沒有后繼結(jié)點

在使用靜態(tài)鏈表時，盡量不要把結(jié)構(gòu)體類型名和結(jié)構(gòu)體變量名取相同名字