線性表存儲結構分為順序存儲、鏈式存儲。順序存儲的優點：
順序存儲的缺點：
鏈表就是典型的鏈式存儲，將線性表L = （a0,a1,a2,........an-1）中個元素分布在存儲器的不同存儲塊，成為結點（Node），通過地址或指針建立他們之間的練習，所得到的存儲結構為鏈表結構。表中元素ai的結點形式如下：
其中，結點的data域存放數據元素ai,而next域是一個指針，指向ai的直接後繼a(i+1)所在的結點。於是，線性表L=（a0,a1,......an-1）的結構如圖：
一、節點類型描述：[cpp] view
plain copy
typedef struct node_t
{
data_t data; //節點的數據域
struct node_t *next;//節點的後繼指針域
}linknode_t,*linklist_t;
也可這樣表示：
[cpp] view
plain copy
struct node_t
{
data_t data;
struct node_t *next;
}
typedef struct node_t linknode_t;
typedef struct node_t *linklist_t;
若說明
linknode_t A;
linklist_t p = &A;
則結構變量A為所描述的節點，而指針變量P為指向此類型節點的指針（p的值為節點的地址）；
這樣看來 linknode_t linklist_t 的作用是一樣的，那為什麼我們要定義兩個數據類型（同一種）呢？主要為了代碼的可讀性，我們要求標識符要望文識義，便於理解；
1、linknode_t *pnode 指向一個節點；
2、linklist_t list 指向一個整體
二、頭結點 head 我們在前篇提到的順序存儲線性表，如何表達一個空表{ }，是通過list->last = -1來表現的，所謂的空表就是數據域為NULL，而我們的鏈表有數據域和指針域，我們如何表現空鏈表呢？這時，就引入了
頭結點的概念，頭結點和其他節點數據類型一樣，只是數據域為NULL，head->next = NULL，下面我們看一個創建空鏈表的函數，如何利用頭結點來創建一個空鏈表：
[cpp] view
plain copy
linklist_t CreateEmptyLinklist()
{
linklist_t list;
list = (linklist_t)malloc(sizeof(linknode_t));
if (NULL != list) {
list->next = NULL;
}
return list;
}
只要頭結點，鏈表就還在！
三、鏈表基本運算的相關算法 鏈表的運算除了上面的創建空鏈表，還有數據的插入，刪除，查找等函數，鏈表的運算有各種實現方法，如何寫出一個高效的，封裝性較好的函數是我們要考慮的，比如數據插入函數，我們就要盡可能考慮所有能出現的結果，比如：1）如果需插入數據的鏈表是個空表；2）所插入的位置超過了鏈表的長度；如果我們的函數能包含所有能出現的情況，不僅能大大提高我們的開發效率，也會減少代碼的錯誤率。下面，我們來看看下面的這個鏈表的插入函數的實現：
[cpp] view
plain copy
int InsertLinklist(linklist_t list, int at, data_t x)
{
linknode_t *node_prev, *node_at, *node_new;
int pos_at;
int found = 0;
if (NULL == list) return -1;
/* at must >= 0 */
if (at < 0) return -1;
/*第一步、分配空間*/
node_new = malloc(sizeof(linknode_t));
if (NULL == node_new)
{
return -1;
}
node_new->data = x; /* assigned value */
node_new->next = NULL; /*節點如果插入超過鏈表長度的位置，會接到尾節點後面，這樣，node_new成了尾節點，node_new->next = NULL */
/*第二步、定位*/
node_prev = list;//跟隨指針，幫助我們更好的定位
node_at = list->next; //遍歷指針
pos_at = 0;
while (NULL != node_at)
{
if (pos_at == at)
{
found = 1; //找到正確的位置，跳出循環
break;
}
/* move to the next pos_at */
node_prev = node_at; //跟隨指針先跳到遍歷指針的位置
node_at = node_at->next;//遍歷指針跳到下一個節點的位置
pos_at++;
}
/*第三步、插入*/
if (found)
{
/* found = 1,找到正確的位置，插入 */
node_new->next = node_at;//插入的節點next指向node_at
node_prev->next = node_new;//插入節點的前一個節點
}
else
{
/*若是沒找到正確的位置，即所插入位置超越了鏈表的長度，則接到尾節點的後面，同樣，這樣適用於{ }即空鏈表，這樣我們可以建立一個空鏈表，利用這個函數，實現鏈表的初始化*/
node_prev->next = node_new;
}
這個插入函數可利用性就非常高。
下面講一個完整鏈表代碼貼出：
listlink.h
[cpp] view
plain copy
#ifndef _LNK_LIST_H_
#define _LNK_LIST_H_
typedef int data_t;
typedef struct node_t {
data_t data;
struct node_t *next;
} linknode_t, *linklist_t;
linklist_t CreateEmptyLinklist();
void DestroyLinklist(linklist_t list);
void ClearLinklist(linklist_t list);
int EmptyLinklist(linklist_t list);
int LengthLinklist(linklist_t list);
int GetLinklist(linklist_t list, int at, data_t *x);
int SetLinklist(linklist_t list, int at, data_t x);
int InsertLinklist(linklist_t list, int at, data_t x);
int DeleteLinklist(linklist_t list, int at);
linklist_t ReverseLinklist(linklist_t list);
#endif /* _LNK_LIST_H_ */
linklist.c
[cpp] view
plain copy
#include <stdio.h>
#include <stdlib.h>
#include "linklist.h"
linklist_t CreateEmptyLinklist()
{
linklist_t list;
list = (linklist_t)malloc(sizeof(linknode_t));
if (NULL != list) {
list->next = NULL;
}
return list;
}
void DestroyLinklist(linklist_t list)
{
if (NULL != list) {
ClearLinklist(list);
free(list);
}
}
void ClearLinklist(linklist_t list)
{
linknode_t *node; /* pointer to the node to be removed */
if (NULL == list) return;
while (NULL != list->next) {
node = list->next;
list->next = node->next;
free(node);
}
return;
}
int LengthLinklist(linklist_t list)
{
int len = 0;
linknode_t *node; //iterate pointer
if (NULL == list) return -1;
node = list->next; // node points to the first data node
while (NULL != node) {
len++;
node = node->next;
}
return len;
}
int EmptyLinklist(linklist_t list)
{
if (NULL != list) {
if (NULL == list->next) {
return 1;
} else {
return 0;
}
} else {
return -1;
}
}
int GetLinklist(linklist_t list, int at, data_t *x)
{
linknode_t *node; /* used for iteration */
int pos; /* used for iteration and compare with */
if (NULL == list) return -1;
/* at must >= 0 */
if (at < 0) return -1;
/* start from the first element */
node = list->next;
pos = 0;
while (NULL != node) {
if (at == pos) {
if (NULL != x) {
*x = node->data;
}
return 0;
}
/* move to the next */
node = node->next;
pos++;
}
return -1;
}
int SetLinklist(linklist_t list, int at, data_t x)
{
linknode_t *node; /* used for iteration */
int pos;
int found = 0;
if (!list) return -1;
/* at must >= 0 */
if (at < 0) return -1;
/* start from the first element */
node = list->next;
pos = 0;
while (NULL != node) {
if (at == pos) {
found = 1; /* found the position */
node->data = x;
break;
}
/* move to the next */
node = node->next;
pos++;
}
if (1 == found) {
return 0;
} else {
return -1;
}
}
int InsertLinklist(linklist_t list, int at, data_t x)
{
/*
* node_at and pos_at are used to locate the position of node_at.
* node_prev follows the node_at and always points to previous node
* of node_at.
* node_new is used to point to the new node to be inserted.
*/
linknode_t *node_prev, *node_at, *node_new;
int pos_at;
int found = 0;
if (NULL == list) return -1;
/* at must >= 0 */
if (at < 0) return -1;
node_new = malloc(sizeof(linknode_t));
if (NULL == node_new) {
return -1;
}
node_new->data = x; /* assigned value */
node_new->next = NULL;
node_prev = list;
node_at = list->next;
pos_at = 0;
while (NULL != node_at) {
if (pos_at == at) {
/*
* found the node 'at'
*/
found = 1;
break;
}
/* move to the next pos_at */
node_prev = node_at;
node_at = node_at->next;
pos_at++;
}
if (found) {
/* insert */
node_new->next = node_at;
node_prev->next = node_new;
} else {
/*
* If not found, means the provided "at"
* exceeds the upper limit of the list, just
* append the new node to the end of the list.
*/
node_prev->next = node_new;
}
return 0;
}
int DeleteLinklist(linklist_t list, int at)
{
/*
* node_at and pos_at are used to locate the position of node_at.
* node_prev follows the node_at and always points to previous node
* of node_at.
*/
linknode_t *node_prev, *node_at;
int pos_at;
int found = 0;
if (!list) return -1;
/* at must >= 0 */
if (at < 0) return -1;
node_prev = list;
node_at = list->next;
pos_at = 0;
while (NULL != node_at) {
if (pos_at == at) {
/*
* found the node 'at'
*/
found = 1;
break;
}
/* move to the next pos_at */
node_prev = node_at;
node_at = node_at->next;
pos_at++;
}
if (found) {
/* remove */
node_prev->next = node_at->next;
free(node_at);
return 0;
} else {
return -1;
}
}
linklist_t ReverseLinklist(linklist_t list)
{
linknode_t *node; /* iterator */
linknode_t *node_prev; /* previous node of iterator */
linknode_t *node_next; /* next node of iterator,
* used to backup next of iterator
*/
if (NULL == list) return NULL;
node_prev = NULL;
node = list->next;
while (NULL != node) {
/*
* step1: backup node->next
* due to the next of iterator will be
* modified in step2
*/
node_next = node->next;
/*
* when iterator reaches the last node
* of original list, make the list head
* point to the last node, so the original
* last one becomes the first one.
*/
if (NULL == node_next) {
list->next = node;
}
/*
* step2: reverse the linkage between nodes
* make the node pointer to the previous node,
* not the next node
*/
node->next = node_prev;
/*
* step3: move forward
*/
node_prev = node;
node = node_next;
}
return list;
}
main.c
[cpp] view
plain copy
#include <stdio.h>
#include <stdlib.h>
#include "linklist.h"
int main()
{
int i;
data_t x;
linklist_t p;
p = CreateEmptyLinklist();
data_t a[10] = {1,3,5,7,9,11,13,15,17,19};
for(i = 0;i < 10;i++)
{
InsertLinklist(p,i,a[i]);
}
ReverseLinklist(p);
printf("The length of the list is:%d\n",LengthLinklist(p));
GetLinklist(p,4,&x);
printf("The NO.4 of this list is:%d\n",x);
SetLinklist(p,4,100);
GetLinklist(p,4,&x);
printf("After updating!The No.4 0f this list is:%d\n",x);
DeleteLinklist(p,4);
printf("After updating!The length of the list is:%d\n",LengthLinklist(p));
GetLinklist(p,4,&x);
printf("After updating!The No.4 0f this list is:%d\n",x);
ReverseLinklist(p);
ClearLinklist(p);
if(EmptyLinklist(p))
printf("This list is empty!\n");
DestroyLinklist(p);
printf("This list is destroyed!\n");
return 0;
}
執行結果如下：
[cpp] view
plain copy
fs@ubuntu:~/qiang/list/list2$ ./Test
The length of the list is:10
The NO.4 of this list is:11
After updating!The No.4 0f this list is:100
After updating!The length of the list is:9
After updating!The No.4 0f this list is:9
This list is empty!
This list is destroyed!
