基本概述
概況
鍊表結構可以克服數組鍊表需要預先知道數據大小的缺點，鍊表結構可以充分利用計算機内存空間，實現靈活的内存動态管理。但是鍊表失去了數組随機讀取的優點，同時鍊表由于增加了結點的指針域，空間開銷比較大。在計算機科學中，鍊表作為一種基礎數數據結構可以用來生成其它類型的數據結構。鍊表通常由一連串節點組成，每個節點包含任意的實例數據（data fields）和一或兩個用來指向上一個/或下一個節點的位置的鍊接（"links"）。鍊表最明顯的好處就是，常規數組排列關聯項目的方式可能不同于這些數據項目在記憶體或磁盤上順序，數據的存取往往要在不同的排列順序中轉換。而鍊表是一種自我指示數據類型，因為它包含指向另一個相同類型的數據的指針（鍊接）。鍊表允許插入和移除表上任意位置上的節點，但是不允許随機存取。鍊表有很多種不同的類型：單向鍊表，雙向鍊表以及循環鍊表。鍊表可以在多種編程語言中實現。像Lisp和Scheme這樣的語言的内建數據類型中就包含了鍊表的存取和操作。程序語言或面向對象語言，如C,C++和Java依靠易變工具來生成鍊表。
特點
線性表的鍊式存儲表示的特點是用一組任意的存儲單元存儲線性表的數據元素（這組存儲單元可以是連續的，也可以是不連續的）。因此，為了表示每個數據元素 與其直接後繼數據元素 之間的邏輯關系，對數據元素 來說，除了存儲其本身的信息之外，還需存儲一個指示其直接後繼的信息（即直接後繼的存儲位置）。由這兩部分信息組成一個"結點"（如概述旁的圖所示），表示線性表中一個數據元素。線性表的鍊式存儲表示，有一個缺點就是要找一個數，必須要從頭開始找起，十分麻煩。
擴展
根據情況，也可以自己設計鍊表的其它擴展。但是一般不會在邊上附加數據，因為鍊表的點和邊基本上是一一對應的（除了第一個或者最後一個節點，但是也不會産生特殊情況）。不過有一個特例是如果鍊表支持在鍊表的一段中把前和後指針反向，反向标記加在邊上可能會更方便。
對于非線性的鍊表，可以參見相關的其他數據結構，例如樹、圖。另外有一種基于多個線性鍊表的數據結構：跳表，插入、删除和查找等基本操作的速度可以達到O(nlogn），和平衡二叉樹一樣。
其中存數據元素信息的域稱作數據域（設域名為data），存儲直接後繼存儲位置的域稱為指針域（設域名為next）。指針域中存儲的信息又稱做指針或鍊。
由分别表示,的N個結點依次相鍊構成的鍊表，稱為線性表的鍊式存儲表示，由于此類鍊表的每個結點中隻包含一個指針域，故又稱單鍊表或線性鍊表。
基本操作
建立
第一行讀入n，表示n個數
第二行包括n個數
以鍊表的形式存儲輸出這些數
program project1;
type
point=^node;
node=record
data:longint;
next:point;
end;
var
i,n,e:longint;
p,q,head,last:point;
begin
write('Input the number count:');
readln(n);
i:=1;
new(head);
read(e);
head^.data:=e;
head^.next:=nil;
last:=head;
q:=head;
while i
begin
inc(i);
read(e);
new(p);
q^.next:=p;
p^.data:=e;
p^.next:=nil;
last:=p;
q:=last
end;
//建立鍊表
q:=head;
while q^.next<>nil do begin
write(q^.data,' ');
q:=q^.next;
end;
write(q^.data);
//輸出
readln;
readln
end.
删除
在以z為頭的鍊表中搜索第一個n，如果找到則删去，返回值為1，否則返回0
function delete(n:longint;var z:point):longint;
var
t,s:point;
begin
t:=z;
while (t^.next<>nil) and (t^.data<>n) do begin
s:=t;
t:=t^.next;
end;
if t^.data<>n then exit(0);
s^.next:=t^.next;
dispose(t);
exit⑴
end;
查找
類似于删除，隻需要找到不删即可
插入
插入，在以zz為頭的鍊表第w個的前面插入nn元素，函數返回值正常是0，如果w超過了鍊表的長度，函數返回鍊表的長度
function insert(w,nn:longint;var zz:point):longint;
var
d:longint; v,vp,vs:point;
begin
v:=zz;
for d:=1 to w do
if v^.next=nil then exit(d)
else begin
vp:=v;
v:=v^.next;
end;
new(vs);
vs^.data:=nn;
vp^.next:=vs;
vs^.next:=v;
exit(0)
end;
鍊表函數
C/C++語言描述
#include
#include
#include
struct Node{
int data;//數據域
struct Node * next;// 指針域
};
/**************************************************************************************
*函數名稱：Create
*函數功能：創建鍊表.
*輸入：各節點的data
*返回值：指針head
*************************************************************************************/
Node * Create()
{
int n ;
Node *head,*p1,*p2;
p1= new Node;
cin>>p1->data;
head = NULL;
while(p1->data!=0)
{
if(n == 0)
{
head = p1;
}
else
p2->next = p1;
p2 =p1;
p1 = new Node;
cin>>p1->data;
n++;
}
p2->next = NULL;
return head;
}
/**************************************************************************************
*函數名稱：insert
*函數功能：在鍊表中插入元素.
*輸入：head 鍊表頭指針，p新元素插入位置，x 新元素中的數據域内容
*返回值：無
*************************************************************************************/
void insert(Node * head,int p,int x){
Node * tmp = head;
//for循環是為了防止插入位置超出了鍊表長度
for(int i = 0;i
{
if(tmp == NULL)
return ;
if(i
tmp = tmp->next;
}
Node * tmp2 = new Node;
tmp2->data = x;
tmp2->next = tmp->next;
tmp->next = tmp2;
}
/**************************************************************************************
*函數名稱：del
*函數功能：删除鍊表中的元素
*輸入：head 鍊表頭指針，p 被删除元素位置
*返回值：被删除元素中的數據域.如果删除失敗返回-1
**************************************************************************************/
int del(Node * head,int p){
Node * tmp = head;
for(int i = 0;i
{
if(tmp == NULL)
return -1;
if(i
tmp = tmp->next;
}
int ret = tmp->next->data;
tmp->next = tmp->next->next;
return ret;
}
void print(Node *head){
for(Node *tmp = head; tmp!=NULL; tmp = tmp->next)
printf("%d ",tmp->data);
printf("n");
}
int main(){
Node * head;
head = new Node;
head->data = -1;
head->next=NULL;
return 0;
}
例子
#include
#define NULL 0
struct student
{
long num;
struct student* next;
};
int main()
{
int i,n;
student* p=(struct student*)malloc(sizeof(struct student));
student* q=p;
printf("輸入幾個值");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&(q->num));
q->next=(struct student*)malloc(sizeof(struct student));
q=q->next;
}
printf("值 第幾個");
int rank;
scanf("%d %d",&(q->num),&rank);
student* w=p;
for(i=1;i
{
w=w->next;
}
q->next=w->next;
w->next=q;
for(i=1;i<=n+1;i++)
{
printf("%d ",p->num);
p=p->next;
}
return 0;
}
//指針後移麻煩
鍊表形式
一、循環鍊表
循環鍊表是與單鍊表一樣，是一種鍊式的 存儲結構，所不同的是，循環鍊表的最後一個結點的 指針是指向該循環鍊表的第一個結點或者表頭結點，從而構成一個環形的鍊。循環鍊表的運算與單鍊表的運算基本一緻。所不同的有以下幾點：
1、在建立一個循環鍊表時，必須使其最後一個結點的 指針指向表頭結點，而不是象單鍊表那樣置為NULL。此種情況還使用于在最後一個結點後插入一個新的結點。
2、在判斷是否到表尾時，是判斷該結點鍊域的值是否是表頭結點，當鍊域值等于表頭 指針時，說明已到表尾。而非象單鍊表
那樣判斷鍊域值是否為NULL。
二、雙向鍊表
雙向鍊表其實是單鍊表的改進。當我們對單鍊表進行操作時，有時你要對某個結點的直接前驅進行操作時，又必須從表頭開始查找。這是由單鍊表結點的結構所限制的。因為單鍊表每個結點隻有一個存儲直接後繼結點地址的鍊域，那麼能不能定義一個既有存儲直接後繼結點地址的鍊域，又有存儲直接前驅結點地址的鍊域的這樣一個雙鍊域結點結構呢？這就是雙向鍊表。在雙向鍊表中，結點除含有數據域外，還有兩個鍊域，一個存儲直接後繼結點地址，一般稱之為右鍊域；一個存儲直接前驅結點地址，一般稱之為左鍊域。
應用舉例
概述
約瑟夫環問題：已知n個人（以編号1，2，3...n分别表示）圍坐在一張圓桌周圍。從編号為k的人開始報數，數到m的那個人出列；他的下一個人又從1開始報數，數到m的那個人又出列；依此規律重複下去，直到圓桌周圍的人全部出列。例如：n = 9,k = 1,m = 5
參考代碼
#include
#include
#define N 41
#define M 5
typedef struct node *link;
struct node{
int item;
link next;
};
link NODE(int item,link next)
{
link t = malloc(sizeof *t);
t->item = item;
t->next = next;
return t;
}
int main(void)
{
int i;
link t = NODE（1,NULL);
t->next = t;
for(i = 2; i <= N; i++)
t = t->next = NODE(i,t->next);
while(t != t->next)
{
for(i = 1; i < M; i++)
t = t->next;
t->next = t->next->next;
}
printf("%dn",t->item);
return 0;
}
其他相關
結語與個人總結
C語言是學習 數據結構的很好的學習工具。理解了C中用 結構體描述 數據結構，那麼對于理解其C++描述，Java描述都就輕而易舉了！
鍊表的提出主要在于順序存儲中的插入和删除的 時間複雜度是線性時間的，而鍊表的操作則可以是常數時間的複雜度。對于鍊表的插入與删除操作，個人做了一點總結，适用于各種鍊表如下：
插入操作處理順序：中間節點的邏輯，後節點邏輯，前節點邏輯。按照這個順序處理可以完成任何鍊表的插入操作。
删除操作的處理順序：前節點邏輯，後節點邏輯，中間節點邏輯。
按照此順序可以處理任何鍊表的删除操作。
如果不存在其中的某個節點略過即可。
上面的總結，大家可以看到一個現象，就是插入的順序和删除的順序恰好是相反的，很有意思！
鍊表的查插删改
-----悉尼大學工程學院 張志剛（Stone Cold）作品
#include
#include
#include< conio.h>
typedef struct Slist
{int data;
struct Slist * next;
}SLIST;
SLIST * InitList_Sq()/*初始化函數*/
{ int a;
SLIST *h,*s,*r;
h=(SLIST *)malloc(sizeof(SLIST));/*建立頭指針，頭指針不可以更改！！！*/
r=h;
if (!h){printf("分配失敗");
exit(0);}
scanf("%d",&a);
for(;a!=-1;)
{s=(SLIST *)malloc(sizeof(SLIST));/*每次都開辟一個結點空間并賦值*/
s->data=a;
r->next=s;
r=s;
scanf("%d",&a);
}r->next='0';
return h;
}
void print_list(SLIST *finder)/*打印函數*/
{
while(finder!='0')
{printf("->%d",finder->data);
finder=finder->next;}
printf("->endn");
}
int DeleteNode(SLIST *killer)//删除節點函數
{int i,j=0;SLIST *p,*q;int x;
p=killer;q=killer->next;
printf("請輸入您要删除的節點序号：");
scanf("%d",&i);
while((p->next!='0')&&(j
{p=p->next;j++;q=p->next;}
if(p->next=='0'||j>i-1）
{printf("n error");
return -1;
}
else
{p->next=q->next;
x=q->data;
free(q);
return x;
}
}
void Insert_Node(SLIST *jumper)//插入函數，本算法為前插結點法
{int t,e,j=0;SLIST *p,*q;
p=jumper;
printf("請輸入要插入位置的序号：");
scanf("%d",&t);
printf("請輸入要插入的元素：");
scanf("%d",&e);
while(p->next!='0'&&j
{j++;p=p->next;}
if(p=='0'||j>t-1）printf("插入的目的位置不存在");
else{q=(SLIST *)malloc(sizeof(SLIST));
q->data=e;
q->next=p->next;
p->next=q;
}
}
void Locate_List(SLIST *reader)//查找值為e的元素
{
int e,i=0;SLIST *p;
p=reader;
printf("請輸入要查找的元素：");
scanf("%d",&e);
while(p->next!='0'&&p->data!=e)
{i++;p=p->next;}
if(p->data==e)printf("此元素在%d号位置n",i);
else printf("無此元素！");
}
void main()
{int i,k,y;SLIST *head;
printf("n 1.建立線性表");
printf("n 2.在i位置插入元素e");
printf("n 3.删除第i個元素，返回其值");
printf("n 4.查找值為e的元素");
printf("n 5.結束程序運行");
printf("n ===================================================");
printf("請輸入您的選擇：");
scanf("%d",&k);
switch(k){
case 1:{head=InitList_Sq();print_list(head->next);}break;
case 2:{head=InitList_Sq();
print_list(head->next);
Insert_Node(head);
print_list(head->next);
}break;
case 3:{head=InitList_Sq();
print_list(head->next);
y=DeleteNode(head);
print_list(head->next);
if(y!=-1）printf("被删除元素為：%d",y);
}break;// 頭結點不算，從有數據的開始算第一個
case 4:{head=InitList_Sq();
print_list(head->next);
Locate_List(head);
}break;
}
}
本程序可在 微軟VC++下編譯通過并且運行
使用方法簡介：運行程序後，先打數字1，然後回車，這樣就可以先創建一個新的鍊表，比如你要創建一個
4->5->6->7這樣一個鍊表，你就輸入數字4回車，輸入5回車，輸入6回車，輸入7回車，最後輸入-1回車，這個-1就是告訴程序到此為止的标志
假如你要使用插入的功能，就在運行程序後輸入2，回車，像上面所說的一樣方法創建一個新鍊表，然後程序會出現提示，問你在哪個位置插入，比如你要在第三個位置插入，就輸入3，回車，程序會問你插入的數值是什麼，比如你要插入999，然後回車，999就被插進去了。
其他的功能都大同小異。
