鍊表檢視原始碼討論檢視歷史

鍊表
原圖鏈接來自搜狗的圖片

鍊表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鍊表中的指針鏈接次序實現的。鍊表由一系列結點（鍊表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。相比於線性表順序結構，操作複雜。由於不必須按順序存儲，鍊表在插入的時候可以達到O(1)的複雜度，比另一種線性表順序錶快得多，但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間，而線性表和順序表相應的時間複雜度分別是O(logn)和O(1)。

使用鍊表結構可以克服數組鍊表需要預先知道數據大小的缺點，鍊表結構可以充分利用計算機內存空間，實現靈活的內存動態管理。但是鍊表失去了數組隨機讀取的優點，同時鍊表由於增加了結點的指針域，空間開銷比較大。

鍊表最明顯的好處就是，常規數組排列關聯項目的方式可能不同於這些數據項目在記憶體或磁盤上順序，數據的存取往往要在不同的排列順序中轉換。鍊表允許插入和移除表上任意位置上的節點，但是不允許隨機存取。鍊表有很多種不同的類型：單向鍊表，雙向鍊表以及循環鍊表。鍊表可以在多種編程語言中實現。像Lisp和Scheme這樣的語言的內建數據類型中就包含了鍊表的存取和操作。程序語言或面向對象語言，如C,C++和Java依靠易變工具來生成鍊表。

特點

線性表的鏈式存儲表示的特點是用一組任意的存儲單元存儲線性表的數據元素（這組存儲單元可以是連續的，也可以是不連續的）。因此，為了表示每個數據元素與其直接後繼數據元素之間的邏輯關係，對數據元素來說，除了存儲其本身的信息之外，還需存儲一個指示其直接後繼的信息（即直接後繼的存儲位置）。由這兩部分信息組成一個"結點"，表示線性表中一個數據元素。線性表的鏈式存儲表示，有一個缺點就是要找一個數，必須要從頭開始找起，十分麻煩。

根據情況，也可以自己設計鍊表的其它擴展。但是一般不會在邊上附加數據，因為鍊表的點和邊基本上是一一對應的（除了第一個或者最後一個節點，但是也不會產生特殊情況）。不過有一個特例是如果鍊表支持在鍊表的一段中把前和後指針反向，反向標記加在邊上可能會更方便。

對於非線性的鍊表，可以參見相關的其他數據結構，例如樹、圖。另外有一種基於多個線性鍊表的數據結構：跳表，插入、刪除和查找等基本操作的速度可以達到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<n do
       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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 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<> nthen exit(0);
       s^.next:=t^.next;
       dispose(t);
       exit⑴
   end;

查找類似於刪除，只需要找到不刪即可插入插入，在以zz為頭的鍊表第w個的前面插入nn元素，函數返回值正常是0，如果w超過了鍊表的長度，函數返回鍊表的長度 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 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; 鍊表函數語音 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138

include<stdio.h>
include<stdlib.h>
include<iostream.h>

usingnamespacestd;

structNode { intdata;//數據域 structNode*next;//指針域 };

/* Create

函數功能：創建鍊表.
輸入：各節點的data
返回值：指針head
/

Node*Create() { intn=0; Node*head,*p1,*p2; p1=p2=newNode; cin>>p1->data; head=NULL; while(p1->data!=0) { if(n==0) { head=p1; } else p2->next=p1; p2=p1; p1=newNode; cin>>p1->data; n++; } p2->next=NULL; returnhead; }

/* insert

函數功能：在鍊表中插入元素.
輸入：head鍊表頭指針，p新元素插入位置，x新元素中的數據域內容
返回值：無
/

voidinsert(Node*head,intp,intx) { Node*tmp=head;//for循環是為了防止插入位置超出了鍊表長度 for(inti=0;i<p;i++) { if(tmp==NULL) return; if(i<p-1） tmp=tmp->next; } Node*tmp2=newNode; tmp2->data=x; tmp2->next=tmp->next; tmp->next=tmp2; }

/* del

函數功能：刪除鍊表中的元素
輸入：head鍊表頭指針，p被刪除元素位置
返回值：被刪除元素中的數據域.如果刪除失敗返回-1
/

intdel(Node*head,intp) { Node*tmp=head; for(inti=0;i<p;i++) { if(tmp==NULL) return-1; if(i<p-1） tmp=tmp->next; } intret=tmp->next->data; tmp->next=tmp->next->next; returnret; }

voidprint(Node*head) { for(Node*tmp=head;tmp!=NULL;tmp=tmp->next) printf("%d",tmp->data); printf("\n"); }

intmain() { Node*head; head=newNode; head->data=-1; head->next=NULL; return0; } 例子

include<iostream>
defineNULL0

structstudent { longnum; structstudent*next; }; intmain() { inti,n; student*p=(structstudent*)malloc(sizeof(structstudent)); student*q=p; printf("輸入幾個值"); scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&(q->num)); q->next=(structstudent*)malloc(sizeof(structstudent)); q=q->next; } printf("值第幾個"); intrank; scanf("%d%d",&(q->num),&rank); student*w=p; for(i=1;i<rank-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; } return0; }//指針後移麻煩鍊表形式循環鍊表循環鍊表是與單鍊表一樣，是一種鏈式的存儲結構，所不同的是，循環鍊表的最後一個結點的指針是指向該循環鍊表的第一個結點或者表頭結點，從而構成一個環形的鏈。循環鍊表的運算與單鍊表的運算基本一致。所不同的有以下幾點： 1、在建立一個循環鍊表時，必須使其最後一個結點的指針指向表頭結點，而不是象單鍊表那樣置為NULL。此種情況還使用於在最後一個結點後插入一個新的結點。 2、在判斷是否到表尾時，是判斷該結點鏈域的值是否是表頭結點，當鏈域值等於表頭指針時，說明已到表尾。而非象單鍊表那樣判斷鏈域值是否為NULL。雙向鍊表雙向鍊表其實是單鍊表的改進。當我們對單鍊表進行操作時，有時你要對某個結點的直接前驅進行操作時，又必須從表頭開始查找。這是由單鍊表結點的結構所限制的。因為單鍊表每個結點只有一個存儲直接後繼結點地址的鏈域，那麼能不能定義一個既有存儲直接後繼結點地址的鏈域，又有存儲直接前驅結點地址的鏈域的這樣一個雙鏈域結點結構呢？這就是雙向鍊表。在雙向鍊表中，結點除含有數據域外，還有兩個鏈域，一個存儲直接後繼結點地址，一般稱之為右鏈域；一個存儲直接前驅結點地址，一般稱之為左鏈域。應用舉例概述約瑟夫環問題：已知n個人（以編號1，2，3...n分別表示）圍坐在一張圓桌周圍。從編號為k的人開始報數，數到m的那個人出列；他的下一個人又從1開始報數，數到m的那個人又出列；依此規律重複下去，直到圓桌周圍的人全部出列。例如：n = 9,k = 1,m = 5 參考代碼 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

include<stdio.h>
include<malloc.h>
defineN41
defineM5

typedefstructnode*link; structnode { intitem; linknext; }; linkNODE(intitem,linknext) { linkt=malloc(sizeof*t); t->item=item; t->next=next; returnt; } intmain(void) { inti; linkt=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); return0; } 其他相關結語與個人總結 C語言是學習數據結構的很好的學習工具。理解了C中用結構體描述數據結構，那麼對於理解其C++描述，Java描述都就輕而易舉了！鍊表的提出主要在於順序存儲中的插入和刪除的時間複雜度是線性時間的，而鍊表的操作則可以是常數時間的複雜度。對於鍊表的插入與刪除操作，個人做了一點總結，適用於各種鍊表如下：插入操作處理順序：中間節點的邏輯，後節點邏輯，前節點邏輯。按照這個順序處理可以完成任何鍊表的插入操作。刪除操作的處理順序：前節點邏輯，後節點邏輯，中間節點邏輯。按照此順序可以處理任何鍊表的刪除操作。如果不存在其中的某個節點略過即可。上面的總結，大家可以看到一個現象，就是插入的順序和刪除的順序恰好是相反的，很有意思！操作

悉尼大學工程學院張志剛（Stone Cold）作品

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154

include<stdio.h>
include<stdlib.h>
include<conio.h>

typedefstructSlist { intdata; structSlist*next; } SLIST; SLIST*InitList_Sq()/*初始化函數*/ { inta; 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'; returnh; } voidprint_list(SLIST*finder)/*打印函數*/ { while(finder!='\0') { printf("->%d",finder->data); finder=finder->next; } printf("->end\n"); } intDeleteNode(SLIST*killer)//刪除節點函數 { inti,j=0; SLIST*p,*q; intx; p=killer; q=killer->next; printf("請輸入您要刪除的節點序號："); scanf("%d",&i); while((p->next!='\0')&&(j<i-1）） { p=p->next; j++; q=p->next; } if(p->next=='\0'||j>i-1） { printf("\nerror"); return-1; } else { p->next=q->next; x=q->data; free(q); returnx; } } voidInsert_Node(SLIST*jumper)//插入函數，本算法為前插結點法 { intt,e,j=0; SLIST*p,*q; p=jumper; printf("請輸入要插入位置的序號："); scanf("%d",&t); printf("請輸入要插入的元素："); scanf("%d",&e); while(p->next!='\0'&&j<t-1） { 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; } } voidLocate_List(SLIST*reader)//查找值為e的元素 { inte,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("無此元素！"); } voidmain() { inti,k,y; SLIST*head; printf("\n1.建立線性表"); printf("\n2.在i位置插入元素e"); printf("\n3.刪除第i個元素，返回其值"); printf("\n4.查找值為e的元素"); printf("\n5.結束程序運行"); printf("\n==================================================="); printf("請輸入您的選擇："); scanf("%d",&k); switch(k) { case1: { head=InitList_Sq(); print_list(head->next); }break; case2: { head=InitList_Sq(); print_list(head->next); Insert_Node(head); print_list(head->next); } break; case3:^[1] { head=InitList_Sq(); print_list(head->next); y=DeleteNode(head); print_list(head->next); if(y!=-1） printf("被刪除元素為：%d",y); }break;//頭結點不算，從有數據的開始算第一個 case4: { head=InitList_Sq(); print_list(head->next); Locate_List(head); }break; } } 本程序可在微軟VC++下編譯通過並且運行使用方法簡介：運行程序後，先打數字1，然後回車，這樣就可以先創建一個新的鍊表，比如你要創建一個 4->5->6->7這樣一個鍊表，你就輸入數字4回車，輸入5回車，輸入6回車，輸入7回車，最後輸入-1回車，這個-1就是告訴程序到此為止的標誌假如你要使用插入的功能位置插入，就輸入3，回車，程序會問你插入的數值是什麼，比如你要插入999，然後回車，999就被插進去了其他的功能都大同小異。

參考資料

↑ 鍊表,搜狗, 2017-02-13

[1] 鍊表,搜狗, 2017-02-13

[1]

鍊表檢視原始碼討論檢視歷史

目錄

目錄

特點

基本操作

參考資料