一起來(lái)看看C語(yǔ)言線性表的線性鏈表
定義
鏈表是通過(guò)一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)線性表中的數(shù)據(jù)元素,每一個(gè)結(jié)點(diǎn)包含兩個(gè)域:存放數(shù)據(jù)元素信息的域稱(chēng)為數(shù)據(jù)域,存放其后繼元素地址的域稱(chēng)為指針域。因此n個(gè)元素的線性表通過(guò)每個(gè)結(jié)點(diǎn)的指針域連接成了一個(gè)“鏈條”,稱(chēng)為鏈表。若此鏈表的每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域,則被稱(chēng)為線性鏈表或單鏈表。
線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),它不需要用地址連續(xù)的存儲(chǔ)單元來(lái)實(shí)現(xiàn),因?yàn)樗?strong>不要求邏輯上相鄰的兩個(gè)數(shù)據(jù)元素物理位置上也相鄰,它是通過(guò)“指針”建立起數(shù)據(jù)元素之間的邏輯關(guān)系。
鏈表是由一個(gè)個(gè)結(jié)點(diǎn)構(gòu)成的,結(jié)點(diǎn)定義如下:
typedef struct node { DataType data; struct node *next; } Linklist;
線性鏈表的存取必須從表頭指針開(kāi)始,表頭指針指示線性鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)單位置。由于線性表最后一個(gè)數(shù)據(jù)元素沒(méi)有直接后繼,則線性鏈表中的最后一個(gè)結(jié)點(diǎn)的指針域?yàn)?ldquo;空”(NULL)。
為了使用方便可以在第一個(gè)元素的前面增加一個(gè)結(jié)點(diǎn)(被稱(chēng)為頭節(jié)點(diǎn)),該節(jié)點(diǎn)的數(shù)據(jù)域?yàn)榭?/strong>,指針域中存儲(chǔ)線性鏈表的第一個(gè)元素所在的結(jié)點(diǎn)(表頭結(jié)點(diǎn))的存儲(chǔ)地址。如果為空表,則指針域?yàn)榭铡?/p>
因此空鏈表也分為帶有頭結(jié)點(diǎn)的空鏈表和不帶頭結(jié)點(diǎn)的空鏈表。若有頭結(jié)點(diǎn),頭結(jié)點(diǎn)的數(shù)據(jù)域?yàn)榭?,指針域?yàn)榭?,則說(shuō)明該鏈表為空鏈表;若沒(méi)有頭結(jié)點(diǎn),表頭指針為空指針,則說(shuō)明該鏈表為空鏈表。 假設(shè)要在線性表的兩個(gè)數(shù)據(jù)元素a和b之間插入一個(gè)數(shù)據(jù)元素x,p為指向結(jié)點(diǎn)a的指針。為了插入數(shù)據(jù)元素x,首先要生成一個(gè)數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn),s為指向新增節(jié)點(diǎn)的指針,然后使新增節(jié)點(diǎn)的指針域指向b(p->next),結(jié)點(diǎn)a的指針域指向新增節(jié)點(diǎn)(s)。 建立線性鏈表應(yīng)從空表開(kāi)始,每讀入一個(gè)數(shù)據(jù)元素則申請(qǐng)一個(gè)結(jié)點(diǎn),然后插在鏈表的頭結(jié)點(diǎn)與第一個(gè)結(jié)點(diǎn)之間。記頭結(jié)點(diǎn)為H,申請(qǐng)的結(jié)點(diǎn)為s,按照上述插入算法,操作步驟為: 再加上新建頭結(jié)點(diǎn)、讀入數(shù)據(jù)元素、申請(qǐng)結(jié)點(diǎn)等步驟,可編程如下: 因?yàn)槭窃阪湵淼念^部插入,讀入數(shù)據(jù)的順序和線性表中的邏輯順序是相反的。 在表頭插入建立線性鏈表方法簡(jiǎn)單,但讀入數(shù)據(jù)元素的順序與生成的鏈表中元素的順序是相反的,若希望次序一致,則用尾插法。因?yàn)槊看问菍⑿陆Y(jié)點(diǎn)插入到鏈表的尾部,所以需加入一個(gè)指針用來(lái)始終指向鏈表中的尾結(jié)點(diǎn),以便能夠?qū)⑿陆Y(jié)點(diǎn)插入到鏈表的尾部。 在前面,我們介紹了插入算法,在這里可以通過(guò)調(diào)用插入算法,即定義一個(gè)變量int i = 1;,調(diào)用前面的函數(shù)InsertLinkList(H, i, x);,每插入一個(gè)數(shù)據(jù)元素,便使i++;,這樣就可一直保持在鏈表的尾部插入。 但是這樣使得算法的時(shí)間復(fù)雜度比頭插法要高出了一個(gè)數(shù)量級(jí),因?yàn)槊看卧谖膊坎迦霐?shù)據(jù)元素時(shí),都要重新調(diào)用InsertLinkList()函數(shù),使指針重新從表頭指針開(kāi)始指向尾結(jié)點(diǎn)。 因此我們可以使指針(記為p)一直指向鏈表中的尾結(jié)點(diǎn),然后讓新結(jié)點(diǎn)(記為s)按照插入算法插入鏈表的尾部。只需修改上述代碼的while循環(huán)即可實(shí)現(xiàn): 假設(shè)鏈表中有a, b, c3個(gè)數(shù)據(jù)元素,要?jiǎng)h除數(shù)據(jù)元素a和數(shù)據(jù)元素c中間的數(shù)據(jù)元素b時(shí),僅需修改數(shù)據(jù)元素a所在的結(jié)點(diǎn)的指針域。假設(shè)指針p指向數(shù)據(jù)元素a,用語(yǔ)句表示就是: 添加一個(gè)指針變量q,讓q指向數(shù)據(jù)元素b,當(dāng)改變數(shù)據(jù)元素a所在的結(jié)點(diǎn)的指針域后,即可釋放q的內(nèi)存,即釋放數(shù)據(jù)元素b所占的內(nèi)存。進(jìn)一步地,調(diào)用函數(shù)時(shí)傳入標(biāo)志變量i,可實(shí)現(xiàn)刪除第i個(gè)數(shù)據(jù)元素。 對(duì)比插入算法和刪除算法,while循環(huán)的功能同樣是使p指向第i-1個(gè)元素,為什么插入算法的循環(huán)條件為p && j<i-1,而刪除算法的循環(huán)條件是p->next && j<i-1?能否將刪除算法的循環(huán)條件也改為p && j<i-1? 這是因?yàn)?,在鏈表根本沒(méi)有i-1個(gè)元素的情況下,循環(huán)條件為p && j<i-1的循環(huán)運(yùn)行結(jié)果為p指向尾結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)即p=NULL,而循環(huán)條件為p->next && j<i-1的循環(huán)運(yùn)行結(jié)果為p指向尾結(jié)點(diǎn)即p≠NULL。若將刪除算法的循環(huán)條件也改為p && j<i-1,在鏈表根本沒(méi)有i-1個(gè)元素的情況下,while循環(huán)后面的語(yǔ)句if (!(p->next))將會(huì)造成非法內(nèi)存訪問(wèn),因?yàn)榇藭r(shí)p=NULL,我們無(wú)法訪問(wèn)空指針指向的內(nèi)容。 查找結(jié)點(diǎn)使用的算法是線性查找法(順序查找法),即從鏈表的第一個(gè)結(jié)點(diǎn)開(kāi)始,順著指針鏈一個(gè)一個(gè)比較,相等則查找成功,返回結(jié)點(diǎn)位置;如果比較到最后也沒(méi)有相等的,則查找不成功,返回空。 若要返回值為x的結(jié)點(diǎn)在鏈表中的位序,則可使用一個(gè)標(biāo)記變量i,記錄結(jié)點(diǎn)的位序;若找不到則返回-1。修改程序如下: 設(shè)H是帶頭結(jié)點(diǎn)的線性鏈表(線性表的長(zhǎng)度不包括頭結(jié)點(diǎn)),求線性鏈表的表長(zhǎng)的操作與上述查找某結(jié)點(diǎn)在鏈表中的位序相似。 本篇文章就到這里了,希望能夠給你帶來(lái)幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容! 1.插入
int InsertLinkList(LinkList *H, int i, DataType x)
/*在有頭結(jié)點(diǎn)的線性鏈表H中第i個(gè)位置前插入元素x*/
{
LinkList *p;
LinkList *s;
int j = 0;
p = H;
while (p && j<i-1)
{
p = p->next;
j++;
}/*循環(huán)直到p指向第i-1個(gè)元素*/
if (!p)
return -1;/*i大于表長(zhǎng)加1*/
s = (LinkList *)malloc(sizeof(LinkList));
s->data = x;
s->next = p->next;/*插入數(shù)據(jù)元素x*/
p->next = s;
return 1;
}
2.建立線性鏈表
1)頭插法
s->next = H->next; H->next = s;
LinkList *CreateLinkList_front()
{
LinkList *H;/*H表示頭結(jié)點(diǎn)*/
LinkList *s;
char x;/*設(shè)數(shù)據(jù)元素的類(lèi)型為char*/
H = (LinkList *)malloc(sizeof(LinkList));/*為頭結(jié)點(diǎn)申請(qǐng)內(nèi)存空間*/
H->next = NULL;
scanf(" %c", &x);
while (x!=flag)/*flag為結(jié)束創(chuàng)建過(guò)程的標(biāo)志,如'#'等*/
{
s = (LinkList *)malloc(sizeof(LinkList));
s->data = x;
s->next = H->next;
H->next = s;
scanf(" %c", &x);
}
return H;
}
2)尾插法
LinkList *CreateLinkList_rear()
{
LinkList *H;
DataType x;/*設(shè)DataType為數(shù)據(jù)元素的類(lèi)型*/
int i = 1;
H = (LinkList *)malloc(sizeof(LinkList));
H->next = NULL;
scanf(&x);/*讀入數(shù)據(jù)元素的值*/
while (x!=flag)
{
InsertLinkList(H, i, x);/*調(diào)用插入算法*/
i++;
scanf(&x);
}
return H;
}
LinkList *CreateLinkList_rear()
{
LinkList *H, *p, *s;
DataType x;/*設(shè)DataType為數(shù)據(jù)元素的類(lèi)型*/
H = (LinkList *)malloc(sizeof(LinkList));
H->next = NULL;
scanf(&x);/*讀入數(shù)據(jù)元素的值*/
p = H;
while (x!=flag)
{
s = (LinkList *)malloc(sizeof(LinkList));
s->data = x;
s->next = NULL;
p->next = s;
p = p->next;
scanf(&x);
}
return H;
}
3.刪除
p->next = p->next->next;
int DeleteLinkList(LinkList *H, int i)
/*在有頭結(jié)點(diǎn)的線性鏈表H中刪除第i個(gè)元素*/
{
LinkList *p;
LinkList *q;
int j = 0;
p = H;
while (p->next && j<i-1)
{
p = p->next;
j++;
}/*循環(huán)直到p指向第i-1個(gè)元素*/
if (!(p->next))
return -1;/*刪除節(jié)點(diǎn)不合法*/
q = p->next;
p->next = q->next;/*刪除第i個(gè)數(shù)據(jù)元素*/
free(q);/*釋放第i個(gè)數(shù)據(jù)元素所占內(nèi)存*/
return 1;
}
4.查找
LinkList *SearchLinkList(LinkList *H, DataType x)
/*在線性鏈表H中查找值為x的結(jié)點(diǎn),找到后返回其指針,否則返回空*/
{
LinkList *p = H->next;/*p指向線性鏈表的第一個(gè)數(shù)據(jù)元素*/
while (p!=NULL && p->data!=x)
p = p->next;
return p;
}
int SearchLinkList(LinkList *H, DataType x)
/*在線性鏈表H中查找值為x的結(jié)點(diǎn),找到后返回其在鏈表中的位序,否則返回-1*/
{
LinkList *p = H->next;/*p指向線性鏈表的第一個(gè)數(shù)據(jù)元素*/
int i = 1;
while (p!=NULL && p->data!=x)
{
p = p->next;
i++;
}
if (p != NULL)
return i;
else
return -1;
}
5.求線性鏈表的表長(zhǎng)
int LinkListLength(LinkList *H)
{
LinkList *p = H;/*p指向頭結(jié)點(diǎn)*/
int n = 0;
while (p->next)
{
p = p->next;
n++;
}/*p所指的是第n個(gè)結(jié)點(diǎn)*/
return n;
}
總結(jié)
相關(guān)文章
C++將音頻PCM數(shù)據(jù)封裝成wav文件的方法
這篇文章主要為大家詳細(xì)介紹了C++將音頻PCM數(shù)據(jù)封裝成wav文件的方法,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-01-01cocos2dx實(shí)現(xiàn)橡皮擦效果以及判斷是否擦除完畢
這篇文章主要為大家詳細(xì)介紹了cocos2dx實(shí)現(xiàn)橡皮擦效果以及判斷是否擦除完畢,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-12-12解析C++哈夫曼樹(shù)編碼和譯碼的實(shí)現(xiàn)
本篇文章主要介紹了C++哈夫曼樹(shù)編碼和譯碼的實(shí)現(xiàn),詳細(xì)的講訴了哈夫曼樹(shù)編碼的原理,有需要的同學(xué)可以了解一下。2016-11-11C語(yǔ)言中sizeof和strlen的區(qū)別詳解
這篇文章主要介紹了C語(yǔ)言中sizeof和strlen的區(qū)別,文中有通過(guò)代碼示例和相關(guān)例題給大家介紹的非常詳細(xì),需要的朋友可以參考下2023-06-06C++ Leetcode實(shí)現(xiàn)從英文中重建數(shù)字
本文主要介紹了當(dāng)給你一個(gè)字符串s,其中包含字母順序打亂的用英文單詞表示的若干數(shù)字(0-9)時(shí),如何通過(guò)Leetcode按升序返回原始的數(shù)字。感興趣的童鞋可以來(lái)看看2021-11-11C++訪問(wèn)者模式模板函數(shù)無(wú)法重載的問(wèn)題解決
本文主要介紹了C++訪問(wèn)者模式模板函數(shù)無(wú)法重載的問(wèn)題解決,文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-12-12C++標(biāo)準(zhǔn)庫(kù)學(xué)習(xí)之weak_ptr智能指針用法詳解
這篇文章主要為大家詳細(xì)介紹了C++標(biāo)準(zhǔn)庫(kù)中weak_ptr智能指針用法的相關(guān)知識(shí),文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-12-12C++實(shí)現(xiàn)LeetCode(156.二叉樹(shù)的上下顛倒)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(156.二叉樹(shù)的上下顛倒),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07