[TOC]
### 鏈表
線性表的另一種實現方式。每個結點不僅不含元素本身的信息，還包含了元素之間的邏輯關系：前驅結點包含了后繼結點的信息。
不再支持隨機訪問，但插入和刪除操作比順序表簡單。
因為，物理結構不再連續，需要我們自己去維護結點之間的地址關系。
### 單向鏈表
#### 定義
在每個結點中除了包含數據域外，還包含了一個指針域，用于指向其后繼結點。
類型分為帶頭結點和不帶頭結點的鏈表。
> 單：鏈表中地址指向為單向。故遍歷的方向也是單向。
* 用結構體定義一個結點
```
struct elt {
int data;
struct elt *next;
};
```
* 頭結點
不帶頭結點的單向鏈表。
我們一般都會將一個結構體指針變量直接指向鏈表的起始結點，但更多的時候，我們會把頭結點封裝到一個結構體中，以便于我們存放更多地有關該鏈表的信息。（如圖）
結構體定義為：
```
struct elt {
int data;
struct elt *next;
};
```
* 刪除一個結點
```
p->next = p->next->next; //main code
```
* 增加一個結點
```
new->next = p->next;
p->next = new;
```
#### ADT
```
void init(Node *Lp);
void insert(Node L,int data);
int isExist(Node L,int data);
void del(Node L,int data);
void print(Node L);
void destroy(Node L);
Node search(Node L,int data);
Node locate(Node L,int data);
```
#### 代碼實現
```
#include <stdio.h>
#include <malloc.h>
/**
* @time:2016/9/6
* @author:j
* @info:the implement of single linked list with head node
*
**/
//the node
struct NodeN{
int data;
struct NodeN *next;
};
typedef struct NodeN *Node;
void init(Node *Lp);
void insert(Node L,int data);
int isExist(Node L,int data);
void del(Node L,int data);
void print(Node L);
void destroy(Node L);
Node search(Node L,int data);
Node locate(Node L,int data);
void init(Node *Lp) {
Node tmp = (struct NodeN *)malloc(sizeof(struct NodeN));
tmp->next = NULL; //empty linked list
tmp->data = -999; //first head
*Lp = tmp;
return;
}
void insert(Node L,int data) {
Node tmp = (struct NodeN *) malloc(sizeof(struct NodeN));
tmp->data = data;
if(L->next == NULL) { // empty
tmp->next = NULL;
L->next = tmp;
} else {
Node p = locate(L,data);
tmp->next = p->next;
p->next = tmp;
}
}
void del(Node L,int data) {
Node tmp = search(L,data);
Node del = tmp->next;
if(NULL != tmp) { //I find it
tmp->next = tmp->next->next;
free(del);
}
}
Node search(Node L,int data) {
Node tmp = L;
while(tmp->next != NULL) {
if(tmp->next->data == data) {
return tmp;
}
tmp = tmp->next;
}
return NULL;
}
Node locate(Node L,int data) {
Node tmp = L;
while(tmp->next != NULL) {
if(tmp->next->data > data) {
return tmp;
}
tmp = tmp->next;
}
return tmp;
}
void print(Node L) {
Node tmp = L->next;
while(tmp!=NULL) {
printf("data is %d\t",tmp->data);
printf("next address is %d",tmp->next);
printf("\n");
tmp = tmp->next;
}
}
void destroy(Node L) {
if(L->next!=NULL)
destroy(L->next);
free(L);
}
int main() {
Node L1;
init(&L1);
insert(L1,10);
insert(L1,5);
insert(L1,8);
del(L1,8);
print(L1);
return 0;
}
```
### 雙向鏈表
#### 定義
單向鏈表的操作是單向的。我們可以在結點的結構體中增加一條指針。即每個結點都有指向其前驅和后繼的兩條指針，這樣就構成了雙向表。
```
struct elt {
int data;
struct elt *next;
struct elt *prior;
};
```
* 增加一個節點
```
s->data = e;
s->prior = p->prior;
p->prior->next = s;
s->next= p;
p->prior = s;
```
* 刪除一個節點
```
p->prior->next = p->next;
p->next->prior = p->prior;
```
#### ADT
```
void init(...);
int *getElement(...);
void delElement(...);
void insertElement(...);
void merge(...); // merge two link lists
void destory(...); // destory a link list.
```
#### 代碼實現
```
```
### 循環鏈表
#### 定義
將單鏈表中最后一個結點的指針指向第一個元素，整個指針域就構成了一個環，這樣，不論從哪個結點出發，都可以找到其余任何元素。我們把這樣的表叫做循環表。
而基于單鏈表構成的循環表，叫做單向循環表。
當然，雙向鏈表也可以構成循環鏈表，如下圖所示。
#### 代碼實現
### 靜態鏈表
#### 定義
鏈表的一種實現方式，即用數組描述鏈表。
在C語言中，靜態鏈表的表現形式即為結構體數組，結構體變量包括數據域data和游標CUR。即
```
struct Node {
int data; //data area
int cur; //current
};
typedef struct Node * pNode;
pNode arr[MAXSIZE];
```
#### 代碼實現
```
#include <stdio.h>
struct Node {
int data; //data area
int cur; //current
};
typedef struct Node * pNode;
typedef struct Node nodeArr;
//pNode arr[MAXSIZE];
int main() {
}
```
