高級c語言鏈表,c語言鏈表基礎詳解

本文目錄一覽：

• 1、C語言鏈表概念
• 2、C語言裡面的鏈表是什麼
• 3、如何用C語言創建一個鏈表，實現增、刪、改、查？
• 4、在C語言中，什麼是鏈表呀?
• 5、C語言中鏈表是怎樣調用的？

C語言鏈表概念

簡單說來，就是通過指針指向，把兩個結構體連接起來。比如定義下面這個結構體

struct node

{

int data;

struct node *next;

}

可以看到結構體裡面定義了一個自身類型的指針，通過讓指針指向另外一個結構體，我們就能通過結構體裡面的next變量訪問下個結構體裡面的內容，而通過下一個結構體，同樣可以通過下一個結構體的next指向，找到下一個這種類型的結構體，這樣就形成了所謂的鏈表。

C語言裡面的鏈表是什麼

C語言裡面的鏈表是一種數據結構

是一種線形的存儲結構

鏈表和數組一樣，也是將一組同類型的數據組織在一起的一種數據結構

不同的是

數組採用的是順序存儲，依靠數組的首地址和元素的相對地址（下標）來實現訪問。

優點是訪問方便快捷，而缺點是數組是靜態的，不利於實現元素的動態增減。

而鏈表採用的是離散存儲，依靠節點間的指向下一個節點的指針來實現訪問。

其優缺點和數組相反

如何用C語言創建一個鏈表，實現增、刪、改、查？

#include\x0d\x0a#include\x0d\x0a#include \x0d\x0a//先定義一種student類型,表示一個學生的信息，如下：\x0d\x0atypedef struct student\x0d\x0a{\x0d\x0aint num; //表示學號\x0d\x0achar name[30]; //表示姓名\x0d\x0afloat score; //表示分數\x0d\x0a}student;\x0d\x0a//定義一種NODE類型,表示一個結點信息，如下：\x0d\x0atypedef struct node\x0d\x0a{\x0d\x0astudent st; //表示一個學生的信息\x0d\x0astruct node *next; //表示一個NODE類型的指針\x0d\x0a}NODE;\x0d\x0a//1、寫出建立一個帶頭結點的線性鏈表的函數，其中每個結點包括學號、姓名、分數三個數據域。函數形式如下：\x0d\x0aNODE *creat_link(int direction)\x0d\x0a{\x0d\x0aNODE *head,*p,*tail;\x0d\x0aint xh,i=1;\x0d\x0aif(direction==1) //當direction的值為1時，新建立的結點連到尾部\x0d\x0a{\x0d\x0atail=head=(NODE *)malloc(sizeof(NODE));\x0d\x0ahead-next=NULL;\x0d\x0aprintf(“請輸入第%d個學生的學號：”,i);\x0d\x0ascanf(“%d”,xh);\x0d\x0awhile(xh0) //從鍵盤臨時輸入學生情況，當輸入的學號非正，則鏈表建立完畢\x0d\x0a{\x0d\x0ap=(NODE *)malloc(sizeof(NODE));\x0d\x0ap-st.num=xh;\x0d\x0aprintf(“請輸入第%d個學生的姓名：”,i);\x0d\x0ascanf(“%s”,p-st.name);\x0d\x0aprintf(“請輸入第%d個學生的成績：”,i);\x0d\x0ascanf(“%f”,p-st.score);\x0d\x0ap-next=NULL;\x0d\x0atail-next=p;\x0d\x0atail=p;\x0d\x0ai=i+1;\x0d\x0aprintf(“請輸入第%d個學生的學號：”,i);\x0d\x0ascanf(“%d”,xh);\x0d\x0a}\x0d\x0a}\x0d\x0aelse if(direction==0) //當direction為0時，新建立的結點成為第一個結點\x0d\x0a{\x0d\x0ahead=(NODE *)malloc(sizeof(NODE));\x0d\x0ahead-next=NULL;\x0d\x0aprintf(“請輸入第%d個學生的學號：”,i);\x0d\x0ascanf(“%d”,xh);\x0d\x0awhile(xh0) //從鍵盤臨時輸入學生情況，當輸入的學號非正，則鏈表建立完畢\x0d\x0a{\x0d\x0ap=(NODE *)malloc(sizeof(NODE));\x0d\x0ap-st.num=xh;\x0d\x0aprintf(“請輸入第%d個學生的姓名：”,i);\x0d\x0ascanf(“%s”,p-st.name);\x0d\x0aprintf(“請輸入第%d個學生的成績：”,i);\x0d\x0ascanf(“%f”,p-st.score);\x0d\x0ap-next=head-next;\x0d\x0ahead-next=p;\x0d\x0ai=i+1;\x0d\x0aprintf(“請輸入第%d個學生的學號：”,i);\x0d\x0ascanf(“%d”,xh);\x0d\x0a}\x0d\x0a}\x0d\x0areturn head;\x0d\x0a}\x0d\x0a//2、寫出輸出上述鏈表各結點數據域值的函數。該函數對應的函數需要一個形參，表示鏈表的頭指針，形式如下：\x0d\x0avoid print_link(NODE *head)\x0d\x0a{\x0d\x0aNODE *p;\x0d\x0ap=head-next;\x0d\x0aprintf(“%-10s%-20s%-10s\n”,”學號”,”姓名”,”分數”);\x0d\x0awhile(p!=NULL)\x0d\x0a{\x0d\x0aprintf(“%-10d%-20s%-10.1f\n”,p-st.num,p-st.name,p-st.score);\x0d\x0ap=p-next;\x0d\x0a}\x0d\x0a//該函數能輸出head所指的鏈表的所有結點值，輸出形式如下：\x0d\x0a/*本函數輸出線性表sq中所有數據，形式如下：\x0d\x0a學號 姓名 分數\x0d\x0a12 張三 234.5\x0d\x0a18 李四 987.7\x0d\x0a??? ??? ??.*/\x0d\x0a}\x0d\x0a//3、寫出在鏈表中刪除結點的函數\x0d\x0aint del_link(NODE *head,char name[])\x0d\x0a{\x0d\x0aNODE *p,*p1;\x0d\x0ap=head-next;\x0d\x0ap1=head;\x0d\x0awhile(p!=NULL)\x0d\x0a{\x0d\x0aif(strcmp(p-st.name,name)!=0)\x0d\x0a{\x0d\x0ap1=p;\x0d\x0ap=p-next;\x0d\x0a}\x0d\x0aelse\x0d\x0a{\x0d\x0abreak;\x0d\x0a}\x0d\x0a}\x0d\x0aif(p!=NULL)\x0d\x0a{\x0d\x0ap1-next=p-next;\x0d\x0afree(p);\x0d\x0areturn 1;\x0d\x0a}\x0d\x0aelse\x0d\x0a{\x0d\x0areturn 0;\x0d\x0a}\x0d\x0a//刪除head所指的鏈表中，名字為name的結點，刪除成功返回1，不成功返回0\x0d\x0a}\x0d\x0a//4、寫出在鏈表中插入結點的算法\x0d\x0aint insert(NODE *head,student x,int wz)\x0d\x0a{\x0d\x0aNODE *p=head;\x0d\x0aint i=0,jg;\x0d\x0aif(wznext;\x0d\x0a}\x0d\x0aif(p==NULL)\x0d\x0a{\x0d\x0ajg=0;\x0d\x0a}\x0d\x0aif(i=wz-1)\x0d\x0a{\x0d\x0a//找到wz前面的節點，p指向它\x0d\x0aNODE *q;\x0d\x0aq=(NODE *)malloc(sizeof(NODE));\x0d\x0aq-st.num=x.num;\x0d\x0astrcpy(q-st.name,x.name);\x0d\x0aq-st.score=x.score;\x0d\x0aq-next=p-next;\x0d\x0ap-next=q;\x0d\x0ajg=1;\x0d\x0a}\x0d\x0a}\x0d\x0areturn jg;\x0d\x0a//該函數能夠在wz這個結點之前，插入一個新結點，新結點的數據域為x。插入成功返回1，不成功返回0。\x0d\x0a}\x0d\x0a//5、寫出主函數，分別調用上面算法所對應的程序，建立鏈表，並輸出鏈表的值。\x0d\x0avoid main()\x0d\x0a{\x0d\x0aNODE *head; //定義指針變量head\x0d\x0aint wz; //表示插入位置\x0d\x0achar xm[30];\x0d\x0astudent st; //定義一個變量st，用來表示一個學生的信息\x0d\x0ahead=creat_link(1);\x0d\x0aprint_link(head); //調用函數建立鏈表，並把返回值送給head;\x0d\x0a//調用函數，輸出鏈表中各個結點的值\x0d\x0a//輸入一個學生的有關信息，送給變量st的有關成員\x0d\x0aprintf(“\n\n請輸入要插入的位置：”);\x0d\x0ascanf(“%d”,wz); //輸入wz的值\x0d\x0aprintf(“請輸入要插入的學生的學號：”);\x0d\x0ascanf(“%d”,st.num);\x0d\x0aprintf(“請輸入要插入的學生的姓名：”);\x0d\x0ascanf(“%s”,st.name);\x0d\x0aprintf(“請輸入要插入的學生的成績：”);\x0d\x0ascanf(“%f”,st.score); \x0d\x0a//調用函數，在鏈表中把學生st的值作為一個結點插入,如果插入成功，輸出新鏈表\x0d\x0aif(insert(head,st,wz)==1)\x0d\x0a{\x0d\x0aprintf(“\n插入成功，新表為：\n”);\x0d\x0aprint_link(head);\x0d\x0a}\x0d\x0aelse\x0d\x0a{\x0d\x0aprintf(“插入不成功”);\x0d\x0a}\x0d\x0a//調用函數，在鏈表中刪除一個指定結點的值,如果刪除成功，輸出新鏈表\x0d\x0aprintf(“\n\n請輸入要刪除的學生的姓名：”);\x0d\x0agetchar();\x0d\x0agets(xm);\x0d\x0aif(del_link(head,xm)==1)\x0d\x0a{\x0d\x0aprintf(“\n刪除成功，新表為：\n”);\x0d\x0aprint_link(head);\x0d\x0a}\x0d\x0aelse\x0d\x0a{\x0d\x0aprintf(“刪除不成功”);\x0d\x0a}\x0d\x0a}

在C語言中，什麼是鏈表呀?

鏈表

鏈錶鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。 相比於線性表順序結構，鏈表比較方便插入和刪除操作。

概況

鏈表(Linked list)是一種常見的基礎數據結構，是一種線性表，但是並不會按線性的順序存儲數據，而是在每一個節點裡存到下一個節點的指針(Pointer)。由於不必須按順序存儲，鏈表在插入的時候可以達到O(1)的複雜度，比另一種線性表：順序錶快得多，但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間，而順序表相應的時間複雜度分別是O(logn)和O(1)。使用鏈表結構可以克服數組鏈表需要預先知道數據大小的缺點，鏈表結構可以充分利用計算機內存空間，實現靈活的內存動態管理。但是鏈表失去了數組隨機讀取的優點，同時鏈表由於增加了結點的指針域，空間開銷比較大。在計算機科學中，鏈表作為一種基礎的數據結構可以用來生成其它類型的數據結構。鏈表通常由一連串節點組成，每個節點包含任意的實例數據(data fields)和一或兩個用來指向明上一個/或下一個節點的位置的鏈接（”links”）。鏈表最明顯的好處就是，常規數組排列關聯項目的方式可能不同於這些數據項目在記憶體或磁盤上順序，數據的存取往往要在不同的排列順序中轉換。而鏈表是一種自我指示數據類型，因為它包含指向另一個相同類型的數據的指針（鏈接）。鏈表允許插入和移除表上任意位置上的節點，[1]但是不允許隨機存取。鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環鏈表。鏈表可以在多種編程語言中實現。像Lisp和Scheme這樣的語言的內建數據類型中就包含了鏈表的存取和操作。程序語言或面向對象語言，如C,C++和Java依靠易變工具來生成鏈表。

編輯本段特點

線性表的鏈式存儲表示的特點是用一組任意的存儲單元存儲線性表的數據元素（這組存儲單元可以是連續的，也可以是不連續的）。因此，為了表示每個數據元素 與其直接後繼數據元素 之間的邏輯關係，對數據元素 來說，除了存儲其本身的信息之外，還需存儲一個指示其直接後繼的信息（即直接後繼的存儲位置）。由這兩部分信息組成一個”結點”（如概述旁的圖所示），表示線性表中一個數據元素 。

編輯本段擴展

根據情況，也可以自己設計鏈表的其它擴展。但是一般不會在邊上附加數據，因為鏈表的點和邊基本上是一一對應的（除了第一個或者最後一個節點，但是也不會產生特殊情況）。不過有一個特例是如果鏈表支持在鏈表的一段中把前和後指針反向，反向標記加在邊上可能會更方便。 對於非線性的鏈表，可以參見相關的其他數據結構，例如樹、圖。另外有一種基於多個線性鏈表的數據結構：跳錶，插入、刪除和查找等基本操作的速度可以達到O(nlogn)，和平衡二叉樹一樣。 其中存儲數據元素信息的域稱作數據域（設域名為data），存儲直接後繼存儲位置的域稱為指針域（設域名為next）。指針域中存儲的信息又稱做指針或鏈。 由分別表示,,…, 的N 個結點依次相鏈構成的鏈表，稱為線性表的鏈式存儲表示，由於此類鏈表的每個結點中只包含一個指針域，故又稱單鏈表或線性鏈表.

編輯本段三個鏈表函數（C語言描述）

#include stdio.h

#include stdlib.h

#include iostream

struct Node{

int data;//數據域

struct Node * next;//指針域

}; /************************************************************************************** *函數名稱:insert

*函數功能:在鏈表中插入元素. *輸入:head 鏈表頭指針,p新元素插入位置,x 新元素中的數據域內容 *輸出:無 *************************************************************************************/ void insert(Node * head,int p,int x)

{ Node * tmp = head; //for循環是為了防止插入位置超出了鏈表長度 for(int i = 0;ip;i++)

{

if(tmp == NULL)

return ;

if(ip-1)

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;ip;i++)

{

if(tmp == NULL)

return -1;

if(ip-1)

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;

}

編輯本段結語

C語言是學習數據結構的很好的學習工具。理解了C中用結構體描述數據結構，那麼對於理解其C++描述，Java描述都就輕而易舉了！

編輯本段兩種鏈表形式

一、循環鏈表 循環鏈表是與單鏈表一樣，是一種鏈式的存儲結構，所不同的是，循環鏈表的最後一個結點的指針是指向該循環鏈表的第一個結點或者表頭結點，從而構成一個環形的鏈。 循環鏈表的運算與單鏈表的運算基本一致。所不同的有以下幾點： 1、在建立一個循環鏈表時，必須使其最後一個結點的指針指向表頭結點，而不是象單鏈表那樣置為NULL。此種情況還使用於在最後一個結點後插入一個新的結點。 2、在判斷是否到表尾時，是判斷該結點鏈域的值是否是表頭結點，當鏈域值等於表頭指針時，說明已到表尾。而非象單鏈表那樣判斷鏈域值是否為NULL。

二、雙向鏈表 雙向鏈表其實是單鏈表的改進。 當我們對單鏈表進行操作時，有時你要對某個結點的直接前驅進行操作時，又必須從表頭開始查找。這是由單鏈表結點的結構所限制的。因為單鏈表每個結點只有一個存儲直接後繼結點地址的鏈域，那麼能不能定義一個既有存儲直接後繼結點地址的鏈域，又有存儲直接前驅結點地址的鏈域的這樣一個雙鏈域結點結構呢？這就是雙向鏈表。 在雙向鏈表中，結點除含有數據域外，還有兩個鏈域，一個存儲直接後繼結點地址，一般稱之為右鏈域；一個存儲直接前驅結點地址，一般稱之為左鏈域。

C語言中鏈表是怎樣調用的？

-運算是間接尋址,你用多指針的話會發現指針用-這種調用方式更簡潔

鏈表指針是C語言的一個難點，但也是重點，學懂了非常有用。要仔細講就必須先講變量、指針。

什麼是變量?所謂變量，不要淺顯的認為會變得量就是變量。舉個例子:“教室變不變?”變，因為每天有不同的人在裡面上課，但又不變，因為教室始終在那，沒有變大或變小。這就是變量:有一個不變的地址和一塊可變的存儲空間。正常情況下，我們只看到變量這個房間裡面的東西，也就是其內容，但不會關注變量的地址，但是C語言的指針，就是這個房間的地址。我們聲明變量就相當於蓋了間房子存放東西，我們可以直接觀看房子里的東西，而聲明指針，就是相當於獲得了一個定位器，當用指針指向某個變量時，就是用指針給變量定位，以後我們就可以用指針找到他所“跟蹤”的變量並可以獲得裡面的內容。

至於我們寫代碼的結構體就相當於是有好幾個房子組成的別墅，幾個房子綁定在一起使用。假設現在有很多這種別墅分布在一個大迷宮裡，每間別墅里都有一間房子。裡面放了另一個別墅的位置信息，現在你手拿定位器找到了第一棟別墅，從裡面得到了你想要的東西(鏈表的數據部分),然後把下一棟別墅的位置計入你的定位器(p

=

p-next)，再走向下一棟別墅……如此走下去，知道走到某地下一棟別墅信息沒有了(p-next

==

NULL)，你的旅行結束。這就是鏈表一次遍歷的過程。

aTdPage[ucTdPageIndex]-OnInit

();就相當於一個定位器