新聞中心

EEPW首頁 > 嵌入式系統(tǒng) > 設(shè)計(jì)應(yīng)用 > 鏈表中幾個(gè)較重要的問題

鏈表中幾個(gè)較重要的問題

作者: 時(shí)間:2016-12-01 來源:網(wǎng)絡(luò) 收藏

鏈表倒數(shù)m個(gè)節(jié)點(diǎn)的對(duì)象
這種問題的解決方式很多,但是如何保證復(fù)雜度上最小卻是一個(gè)重要的問題,最好是只遍歷一次鏈表就能找到對(duì)應(yīng)的節(jié)點(diǎn),實(shí)質(zhì)上采用類似于哨兵指針的形式就能實(shí)現(xiàn)。設(shè)置兩個(gè)指針,分別執(zhí)行鏈表頭和鏈表的第m個(gè)對(duì)象,然后兩個(gè)指針分別遍歷,當(dāng)執(zhí)行第m個(gè)節(jié)點(diǎn)對(duì)象的指針指向了最后一個(gè)節(jié)點(diǎn)對(duì)象時(shí),這時(shí)指向表頭的那個(gè)鏈表實(shí)質(zhì)上就指向了倒數(shù)第m個(gè)節(jié)點(diǎn)的對(duì)象。這個(gè)指向第m個(gè)節(jié)點(diǎn)的指針就起到了類似哨兵指針的作用。

本文引用地址:http://butianyuan.cn/article/201612/324509.htm

List_handle_t findMlastnode(List_handle_t list, int m)
{
int n = 0;
List_handle_t temp = list;
List_handle_t mtemp = NULL;

if(temp != NULL)
{
/*find the mth node*/
while( temp != NULL && n != m)
{
temp = temp->next;
++ n;
}

if(n == m && temp != NULL)
{
/*point to the mth node*/
mtemp = temp;
/*point to thehead*/
temp = list;

/*pass the list*/
while(mtemp->next != NULL)
{
mtemp = mtemp->next;
temp = temp->next;
}

return temp;
}
}
return NULL;
}

關(guān)于多層次鏈表的平鋪操作,因?yàn)槎鄬哟捂湵硎穷愃朴跇涞慕Y(jié)構(gòu),當(dāng)然可以采用類似樹的遍歷形式進(jìn)行平鋪,但是這種方式對(duì)節(jié)點(diǎn)的訪問形式往往都是多次遍歷。由于多層次的鏈表平鋪還需要取消平鋪操作,因此最好不要破壞每一個(gè)層次中的鏈接關(guān)系,如果破壞了每一層中的鏈接關(guān)系,就會(huì)使得每一層的還原操作非常復(fù)雜,我們可以按照層次逐層逐層的訪問。

多層次鏈表的平鋪?zhàn)詈玫姆绞绞浅浞掷梦补?jié)點(diǎn),也就是將每一層的對(duì)象都接到平鋪鏈表的尾部,而且隨著平鋪鏈表長(zhǎng)度的增長(zhǎng),下一層次的節(jié)點(diǎn)也能夠訪問到,這時(shí)候通過判斷節(jié)點(diǎn)是否存在子層,如果有就繼續(xù)添加到尾節(jié)點(diǎn),這樣就能實(shí)現(xiàn)不同層次節(jié)點(diǎn)的平鋪。這種平鋪操作的優(yōu)點(diǎn)在于只遍歷了一次第一層的節(jié)點(diǎn)完成平鋪操作,而且沒有破壞每一層對(duì)象的鏈接關(guān)系,便于后期的還原。這種方法的關(guān)鍵在于如何控制鏈表的尾節(jié)點(diǎn)。

/*addsublevel listnode to the tail of first level*/
void appendtail(MList_handle_thead, MList_handle_t *tail)
{
MList_handle_t list = head;

/*update the list tail*/
(*tail)->next = head;
head->next= (*tail);

/*pass the node in this list*/
for(list; list->next != NULL; list= list->next);

/*updatathe list tail*/
*tail = list;
}

void flattenList(MList_handle_t head, MList_handle_t *tail)
{
MList_handle_t list =head;

/*list will be growing*/
while(list)
{
if(list->child)
{
appendtail(list->child,tail);
}

list = list->next;
}
}

取消平鋪操作,主要是切斷每一層之間的前后鏈接關(guān)系,而保持子層鏈接關(guān)系,實(shí)質(zhì)上這可以采用遞歸的形式實(shí)現(xiàn),因?yàn)槿绻?dāng)前節(jié)點(diǎn)存在子節(jié)點(diǎn),那么就將子節(jié)點(diǎn)的鏈接關(guān)系切斷,如果子節(jié)點(diǎn)也仍然存在子節(jié)點(diǎn),那么先切斷子層的鏈接關(guān)系,因?yàn)槠戒仜]有破壞每一層的鏈接關(guān)系,這樣只訪問第一層就能完成取消平鋪操作。實(shí)質(zhì)完成的操作就是講當(dāng)前子節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)設(shè)置為NULL,而將當(dāng)前子節(jié)點(diǎn)的前一個(gè)對(duì)象設(shè)置為NULL,這樣就切斷了各層之間的關(guān)系。因?yàn)槊恳淮吻袛喽紩?huì)導(dǎo)致平鋪鏈表的縮短,當(dāng)平鋪鏈表只有原始第一層的長(zhǎng)度時(shí),這時(shí)候就完成了鏈表的取消平鋪操作,當(dāng)然仍然需要注意尾節(jié)點(diǎn)的管理問題。但是我們不能將取消平鋪操作直接設(shè)置成一個(gè)遞歸操作,平鋪操作最后肯定會(huì)管理鏈表尾,而子層與母層的鏈表斷裂關(guān)系并不需要設(shè)置鏈表尾。

void unflattensearch(MList_handle_t head)
{
MList_handle_t list =head;

while(list)
{
if(list->child)
{
/*break the link between two levels*/
list->child->prev->next = NULL;
list->child->prev = NULL;

/*break the link between other levels*/
unflattensearch(list->child);
}
/*next listnode*/
list = list->next;
}
}

/*************************************************************
this function can not be reserve
because the function must update tail
actual there is only one time to operate.
**************************************************************/
void unflattenList(MList_handle_t head, MList_handle_t * tail)
{
MList_handle_t list =head;

unflattensearch(list);

/*pass to the last of list*/
for(list; list->next; list = list->next);

/*update the tail of list*/
*tail = list;
}


總結(jié)

關(guān)于鏈表的操作我認(rèn)為主要還是要設(shè)置恰當(dāng)?shù)闹羔?,鏈表的操作就是指針的操作,但是因?yàn)殒湵淼奶厥庑?,使得指針的比較操作變得無效,但是可以通過指針的相等和不相等進(jìn)行操作,設(shè)置哨兵指針等指針的重要操作。

同時(shí)需要注意鏈表是一個(gè)可能動(dòng)態(tài)增長(zhǎng)的對(duì)象,只要時(shí)刻理解這種動(dòng)態(tài)特性就能比較好的理解鏈表中的多層次問題,平鋪過程就是利用了鏈表的動(dòng)態(tài)增長(zhǎng)過程,通過鏈表尾實(shí)現(xiàn)動(dòng)態(tài)操作。而取消平鋪操作只是完成了切斷各層之間的連接關(guān)系而已,并不會(huì)更新鏈表尾,但是鏈表的長(zhǎng)度也發(fā)生了動(dòng)態(tài)變化。

把握鏈表的動(dòng)態(tài)增長(zhǎng)特性和指針的相關(guān)操作就能很好的完成鏈表的相關(guān)操作。


上一頁 1 2 下一頁

關(guān)鍵詞: 鏈表指針比較操

評(píng)論


技術(shù)專區(qū)

關(guān)閉