基本概述
概況
鍊表特點
鍊表擴展
根據情況，也可以自己設計鍊表的其它擴展。但是一般不會在邊上附加數據，因為鍊表的點和邊基本上是一一對應的（除了第一個或者最後一個節點，但是也不會產生特殊情況）。不過有一個特例是如果鍊表支持在鍊表的一段中把前和後指針反向，反向標記加在邊上可能會更方便。對於非線性的鍊表，可以參見相關的其他數據結構，例如樹、圖。另外有一種基於多個線性鍊表的數據結構：跳表，插入、刪除和查找等基本操作的速度可以達到O(nlogn），和平衡二叉樹一樣。
其中存數據元素信息的域稱作數據域（設域名為data），存儲直接後繼存儲位置的域稱為指針域（設域名為next）。指針域中存儲的信息又稱做指針或鏈。
由分別表示,的N個結點依次相鏈構成的鍊表，稱為線性表的鏈式存儲表示，由於此類鍊表的每個結點中只包含一個指針域，故又稱單鍊表或線性鍊表。
基本操作
（pascal語言）建立
第一行讀入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，否則返回0function 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("%d\n",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("->end\n");
}
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就被插進去了。
其他的功能都大同小異。
