-
鏈表
鎖定
鏈表是一種物理存儲單元上非連續、非順序的存儲結構,數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點(鏈表中每一個元素稱為結點)組成,結點可以在運行時動態生成。每個結點包括兩個部分:一個是存儲數據元素的數據域,另一個是存儲下一個結點地址的指針域。 相比於線性表順序結構,操作複雜。由於不必須按順序存儲,鏈表在插入的時候可以達到O(1)的複雜度,比另一種線性表順序錶快得多,但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間,而線性表和順序表相應的時間複雜度分別是O(logn)和O(1)。
使用鏈表結構可以克服數組鏈表需要預先知道數據大小的缺點,鏈表結構可以充分利用計算機內存空間,實現靈活的內存動態管理。但是鏈表失去了數組隨機讀取的優點,同時鏈表由於增加了結點的指針域,空間開銷比較大。鏈表最明顯的好處就是,常規數組排列關聯項目的方式可能不同於這些數據項目在記憶體或磁盤上順序,數據的存取往往要在不同的排列順序中轉換。鏈表允許插入和移除表上任意位置上的節點,但是不允許隨機存取。鏈表有很多種不同的類型:單向鏈表,雙向鏈表以及循環鏈表。鏈表可以在多種編程語言中實現。像Lisp和Scheme這樣的語言的內建數據類型中就包含了鏈表的存取和操作。程序語言或面嚮對象語言,如C,C++和Java依靠易變工具來生成鏈表。
- 中文名
- 鏈表
- 外文名
- linked list
- 分 類
- 計算機數據結構
- 構 成
- 一系列結點組成
- 類 型
- 計算機結構術語
鏈表特點
線性表的鏈式存儲表示的特點是用一組任意的存儲單元存儲線性表的數據元素(這組存儲單元可以是連續的,也可以是不連續的)。因此,為了表示每個數據元素 與其直接後繼數據元素 之間的邏輯關係,對數據元素 來説,除了存儲其本身的信息之外,還需存儲一個指示其直接後繼的信息(即直接後繼的存儲位置)。由這兩部分信息組成一個"結點"(如概述旁的圖所示),表示線性表中一個數據元素。線性表的鏈式存儲表示,有一個缺點就是要找一個數,必須要從頭開始找起,十分麻煩。
根據情況,也可以自己設計鏈表的其它擴展。但是一般不會在邊上附加數據,因為鏈表的點和邊基本上是一一對應的(除了第一個或者最後一個節點,但是也不會產生特殊情況)。不過有一個特例是如果鏈表支持在鏈表的一段中把前和後指針反向,反向標記加在邊上可能會更方便。
鏈表基本操作
(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
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超過了鏈表的長度,函數返回鏈表的長度
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;
鏈表鏈表函數
#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
參考代碼
#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)作品
#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: { 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就被插進去了
其他的功能都大同小異