C語言之連結串列
陣列：方便訪問，不方便插入刪除
連結串列：不必連續，定義連結串列，節點定義，結構體構造，生成連結串列和動態機制，進行連結串列的三個操作（增刪改）
（1）連結串列概述
連結串列是一種資料結構，它採用動態分配儲存單元方式。它能夠有效地節省儲存空間（同陣列比較）。
連結串列都有一個“頭指標”變數（head），它用於指向連結串列中第一個元素（即用於存放連結串列中第一個元素的地址）。連結串列中的元素稱為“結點”，連結串列中的所有結點都是結構體型別，且同一結點都是同一結構體型別。每個結點都應包括資料部分和下個節點的地址兩部分內容。連結串列的最後一個元素（結點）稱為鏈尾，它不再指向其他結點（即該結點的指標成員值為NULL）。
連結串列的訪問都是通過指標變數從頭結點開始。
由於連結串列中的節點是一個結構體型別，並且節點中有一個成員用於指向下一個結點。所以定義作為結點的格式：
struct 結構體名
{定義資料成員；
struct 結構體名*指標變數名；
}；
例如：
struct student
{int num；float score；
struct student *next；
}；
struct student a，*p；
//出現指向自身的指標是連結串列中的節點
（2）動態儲存分配函式<stdlib.h>
1.malloc（）函式
格式：malloc（size）
malloc()返回值是void型別，必須進行強制型別轉換！！！
作用是在記憶體的動態儲存區中分配一個長度為size個位元組的連續空間
，函式返回值為一個指向分配域起始地址的指標若分配失敗則返回NULL。
例如：開闢一個用於存放struct student資料的記憶體空間，並讓p指向該空間：
struct student*p=（struct student*）malloc（sizeof（struct student
2.free（）函式
格式：free（p）；
作用是釋放用malloc（）分配的記憶體。
3.連結串列操作
（1）建立動態連結串列（假定若輸入的成員為0則表示結束）
#include<stdlib.h>
struct node{
int data;
struct node *next;
};
int main() {
struct node *head,*p=(struct node *)malloc(sizeof(struct node)),*q=(struct node *)malloc(sizeof(struct node));
p->data=10;
head=p;
q->data=20;
q->next=NULL;
p->next=q;
return 0;
}
（2）訪問連結串列
求平均數
struct node{
int data;
struct node *next;
};
struct node *head,*p=(struct node *)malloc(sizeof(struct node));
int sum=0;
p=head;
while(p!=NULL)
{sum+=p->data;
p=p->next;
}
sum/=3;//隨便敲der
（3）連結串列結點的刪除
如：
a、請將結點b從連結串列中刪除。
b、請將結點d從連結串列中刪除。
c、請將結點a從連結串列中刪除並讓head重新指向連結串列的第一個結點。
刪除中間節點：必須要拿到要刪除的節點的錢一個節點的地址
q->next=p->next;free(p); p=q->next;q->next=q->next->next;free(p); 刪除頭節點：p=head;head=head->next；free(p); 刪除尾節點：知道尾節點前一個節點q p=q->next;q->next=NULL;free(p)
（4）增加結點
如：
a、請將結點c插入結點之間，形成新連結串列
b、請將結點c插到已有連結串列的末尾
c、請將結點c插到已有連結串列的前面
在中間插入節點q後插入s：先連後改指向,s->next=q->next;q->next=s; 在頭部插入節點s：s->next=head;head=s； 尾部s：s->next=NULL;q->next=s;