c语言链表中何时用点何时用箭头,链表基本操作及其过程详细叙述
鏈表概述：鏈表是一種常見的數(shù)據(jù)結(jié)構(gòu)。數(shù)組可以存放數(shù)據(jù)，但是使用數(shù)組時要先指定數(shù)組中包含元素的個數(shù)，即數(shù)組長度。但是如果向這個數(shù)組中加入的元素個數(shù)超過了數(shù)組的大小時，便不能將內(nèi)容完全保存。例如在定義一個班級的人數(shù)時，如果小班是30人，普通班是50人，且定義班級人數(shù)時使用數(shù)組，那么要定義數(shù)組的個數(shù)為最大，也就是最少為50個元素，否則不滿足最大時的情況。這種方式非常浪費空間。而鏈表，其存儲元素的個數(shù)不受限定的，當(dāng)進(jìn)行添加元素的時候存儲的個數(shù)就會隨之改變。
如圖1所示為鏈表結(jié)構(gòu)的示意圖
在鏈表中有一個頭指針變量，圖中head表示的就是頭指針，這個指針變量保存一個地址。從圖中的箭頭可以看到該地址為一個變量的地址，也就是說頭指針指向一個變量。這個變量稱為元素，在鏈表中每一個元素包括兩個部分：數(shù)據(jù)部分和指針部分。數(shù)據(jù)部分用來存放元素所包含的數(shù)據(jù)，而指針部分用來指向下一個元素。最后一個元素指針指向NULL，表示指向的地址為空。從圖1可以看到，head頭結(jié)點指向第一個元素，第一個元素中的指針又指向第二個元素，第二個元素的指針又指向第三個元素的地址，第三個元素的指針就指向為空。
根據(jù)對鏈表的描述，可以想象到鏈表就像一個鐵鏈，一環(huán)扣一環(huán)。然后通過頭指針尋找鏈表中的元素，這就好比在一個幼兒園中，老師拉著第一個小朋友的手，第一個小朋友又拉著第二個小朋友的手，這樣下去在幼兒園中的小朋友就連成了一條線。最后一個小朋友沒有拉著任何人，他的手是空著的，他就好像是鏈表中鏈尾，而老師就是頭指針，通過老師就可以找到這個隊伍中的任何一個小朋友。
注意：在鏈表這種結(jié)構(gòu)中，必須利用指針才能實現(xiàn)。因此鏈表中的結(jié)點應(yīng)該包含一個指針變量來保存下一個結(jié)點的地址。
三個函數(shù)：
void *malloc(unsigned int size);
該函數(shù)的功能是在內(nèi)存中動態(tài)地分配一塊size大小的內(nèi)存空間。malloc函數(shù)會返回一個指針，該指針指向分配的內(nèi)存空間，如果出現(xiàn)錯誤則返回NULL。
void *calloc(unsigned int n,unsigned int size);
該函數(shù)的功能是在內(nèi)存中動態(tài)分配n個長度為size的連續(xù)內(nèi)存空間數(shù)組。calloc函數(shù)會返回一個指針，該指針指向動態(tài)分配的連續(xù)內(nèi)存空間地址。當(dāng)分配空間錯誤時，返回NULL。
void free(void *ptr);
該函數(shù)的功能是使用由指針ptr指向的內(nèi)存區(qū)，使部分內(nèi)存區(qū)能被其他變量使用(簡單來說就是釋放不需要的內(nèi)存空間)。ptr是最近一次調(diào)用calloc或malloc函數(shù)時返回的值，free函數(shù)無返回值。
鏈表的插入操作：鏈表的插入操作可以在鏈表的頭指針位置進(jìn)行(圖3)，也可以在某個結(jié)點的位置進(jìn)行，或者可以像創(chuàng)建結(jié)構(gòu)時在鏈表的后面添加結(jié)點(圖2)。這三種插入操作的思想都是一樣的。
鏈表頭插入結(jié)點的過程就比如手拉手的小朋友連成一條線，這時又來了一個小朋友他要站在老師和一個小朋友的中間，那么老師就要放開原來的小朋友，拉住新加入的小朋友。這個新加入的小朋友就拉住原來的那個小朋友。這樣，這條連成的線還是連在一起。
鏈表的刪除操作：當(dāng)希望刪除鏈表中的結(jié)點時，應(yīng)該怎么辦？還是通過前文中小朋友手拉手的比喻進(jìn)行理解。例如隊伍中的一個小朋友離開隊伍了，并且這個隊伍不會斷開的方法只需他兩邊的小朋友將手拉起來就可以了。
例如在一個鏈表中刪除其中的一點：
通過圖4可以發(fā)現(xiàn)要刪除一個結(jié)點，首先要找到這個結(jié)點的位置，例如圖中的NO2結(jié)點。然后將NO1結(jié)點的指針指向NO3結(jié)點，最后將NO2結(jié)點的內(nèi)存空間釋放掉，這樣就完成了結(jié)點的刪除操作。
實例：
#include
#include
struct student//學(xué)生結(jié)構(gòu)體
{
char name[20];//姓名
int number;//學(xué)號
struct student * next;//指向下一個結(jié)點的指針
};
int count;//全局變量表示鏈表長度
/*
create函數(shù)的功能是創(chuàng)建鏈表，在create的外部可以看到一個整型的全局變量count，這個變量
的作用是表示鏈表中結(jié)點的數(shù)量。在create函數(shù)中，首先定義需要用到的指針變量，head用來表示頭
指針，end用來指向原來的尾結(jié)點，new指向新創(chuàng)建的結(jié)點。
使用malloc函數(shù)分配內(nèi)存，先用end和new兩個指針都指向第一個分配的內(nèi)存。然后顯示提示信息，
先輸入一個學(xué)生的姓名，再輸入學(xué)生的學(xué)號。使用while進(jìn)行判斷，如果學(xué)號為0，則不執(zhí)行循環(huán)語句。
在while循環(huán)中，count++自加操作表示鏈表中結(jié)點的增加。然后要判斷新加入的結(jié)點是否是第一次
加入的結(jié)點，如果是第一次加入結(jié)點則執(zhí)行if語句塊中的代碼，否則執(zhí)行else語句塊中的代碼。
在if語句塊中，因為第一次加入結(jié)點時其中沒有結(jié)點，所以新結(jié)點即為首結(jié)點也為最后一個結(jié)點，
并且要將新加入的結(jié)點的指針指向NULL，即為head指向。else語句實現(xiàn)的是鏈表中已經(jīng)有結(jié)點存在時的
操作。首先將新結(jié)點new的指針指向NULL，然后將原來最后一個結(jié)點的指針指向新結(jié)點，最后將end指針
指向最后一個結(jié)點。
這樣一個結(jié)點創(chuàng)建完之后，要再進(jìn)行分配內(nèi)存，然后向其中輸入數(shù)據(jù)，通過while語句再次判斷輸入
的數(shù)據(jù)是否符合結(jié)點的要求。當(dāng)結(jié)點不符合要求時，執(zhí)行下面的代碼，調(diào)用free函數(shù)將不符合要求的結(jié)點
空間進(jìn)行釋放。
*/
struct student * create()
{
struct student * head = NULL;//初始化鏈表頭指針為空
struct student * end,* new;
count = 0;//初始化鏈表長度
end = new = (struct student *)malloc(sizeof(struct student));
printf("please first enter name,then nember\n");
scanf("%s",new->name);
scanf("%d",&new->number);
while(0 != new->number)
{
count++;
if(1 == count)
{
new->next = head;//使得指向為空
end = new;//跟蹤新加入的結(jié)點
head = new;//頭指針指向首結(jié)點
}
else
{
new->next = NULL;//新結(jié)點的指針為空
end->next = new;//原來的尾結(jié)點指向新結(jié)點
end = new;//end指向新結(jié)點
}
new = (struct student *)malloc(sizeof(struct student));//再次分配結(jié)點內(nèi)存空間
scanf("%s",new->name);
scanf("%d",&new->number);
}
free(new);//釋放沒用到的空間
return head;
}
/*
print函數(shù)是用來將鏈表中的數(shù)據(jù)進(jìn)行輸出。在函數(shù)的參數(shù)中，head表示一個鏈表的頭結(jié)點。
在函數(shù)中，定義一個臨時的指針temp用來進(jìn)行循環(huán)操作。定義一個整型變量表示鏈表中的結(jié)點序號。
然后將臨時指針temp指針變量保存首結(jié)點的地址。
使用while語句將所有的結(jié)點中保存的數(shù)據(jù)都顯示輸出。其中每輸出一個結(jié)點的內(nèi)容后，就移動
temp指針變量指向下一個結(jié)點的地址。當(dāng)最后一個結(jié)點時，所擁有的指針指向NULL，此時循環(huán)結(jié)束。
*/
void print(struct student * head)
{
struct student *temp;//循環(huán)所用的臨時指針
int index = 1;//表示鏈表中結(jié)點的序號
printf("---the list has %d members:---\n\n",count);
temp = head;//指針得到首結(jié)點的地址
while(NULL != temp)
{
printf("the NO%d member is:\n",index); //輸出結(jié)點序號
printf("the name is:%s\n",temp->name);//輸出姓名
printf("the number is:%d\n\n",temp->number); //輸出學(xué)號
temp = temp->next;//移動臨時指針到下一個結(jié)點
index++;
}
}
/*
insert函數(shù)為鏈表頭插入操作函數(shù)，在代碼中，為要插入的新結(jié)點分配內(nèi)存，然后向新結(jié)點中輸入數(shù)據(jù)。這樣
一個結(jié)點就創(chuàng)建完成了，接下來就是將這個結(jié)果插入到鏈表中。首先將新結(jié)點的指針指向原來的首結(jié)點，保存首結(jié)
點的地址。然后將頭指針指向新結(jié)點，這樣就完成了結(jié)點的連接操作，最后增加鏈表的結(jié)點數(shù)量。
*/
struct student * insert(struct student * head)
{
struct student * new;//指向新分配的空間
printf("---insert member at first---\n");
new = (struct student *)malloc(sizeof(struct student));//分配內(nèi)存空間，并返回指向該內(nèi)存空間的指針
scanf("%s",new->name);
scanf("%d",&new->number);
new->next = head;//新結(jié)點指針指向原來的首結(jié)點
head = new;//頭指針指向新結(jié)點
count++;//增加鏈表結(jié)點數(shù)量
return head;
}
/*
為delete函數(shù)傳遞兩個參數(shù)，head表示鏈表的頭指針，index表示要刪除結(jié)點在鏈表中的位置。
定義整型變量i用來控制循環(huán)的次數(shù)，然后定義兩個指針，分別用來表示要刪除的結(jié)點和這個結(jié)點
之前的結(jié)點。
輸出一行提示信息表示要進(jìn)行刪除操作，之后利用for語句進(jìn)行循環(huán)操作找到要刪除的結(jié)點，
使用temp保存要刪除結(jié)點的地址，pre保存前一個結(jié)點的地址。找到要刪除的結(jié)點后，連接刪除結(jié)點
兩邊的結(jié)點，并使用free函數(shù)將temp指向的內(nèi)存空間進(jìn)行釋放。
*/
void delete(struct student * head,int index)//head表示頭結(jié)點，index表示要刪除的結(jié)點下標(biāo)
{
int i;//控制循環(huán)變量
struct student * temp;//臨時指針
struct student * pre;//表示要刪除結(jié)點前的結(jié)點
temp = head;//得到頭結(jié)點
pre = temp;
printf("---delete NO%d member---\n\n\n",index);
for(i=1;i
{
pre = temp;
temp = temp->next;
}
pre->next = temp->next;//連接刪除結(jié)點兩邊的結(jié)點
free(temp);//釋放掉要刪除結(jié)點的內(nèi)存空間
count--;//減少鏈表中的元素個數(shù)
}
/*
在main函數(shù)中，先定義一個頭結(jié)點指針head，然后調(diào)用create函數(shù)創(chuàng)建鏈表，并將鏈表的頭結(jié)點
返回給head指針變量。利用得到的頭結(jié)點head作為print函數(shù)的參數(shù)。
在main函數(shù)中分別添加代碼執(zhí)行插入和刪除操作。
*/
int main()
{
struct student * head;//定義頭結(jié)點
head = create();//創(chuàng)建結(jié)點
print(head);//輸出鏈表
head = insert(head);//插入結(jié)點
print(head);//輸出鏈表
delete(head,2);//刪除第二個結(jié)點
print(head);//輸出鏈表
return 0;
}
參考文獻(xiàn)：[C語言從入門到精通].王娣等
[C語言從入門到精通].王娣等PDF文檔下載地址：
總結(jié)
以上是生活随笔為你收集整理的c语言链表中何时用点何时用箭头,链表基本操作及其过程详细叙述的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 管理类联考笔试还是计算机考,干货来了！管
- 下一篇： 小马哥---高仿苹果6s 主板H339