文章還是關(guān)于鏈表，本次主要涉及幾個(gè)比較深入的問(wèn)題：循環(huán)鏈表的判定、倒數(shù)第m個(gè)節(jié)點(diǎn)的數(shù)據(jù)獲取、多層次鏈表的設(shè)計(jì)、平鋪和取消平鋪。
/*單鏈表*/
typedef struct list
{
struct list *next;
int data;
} List_t, *List_handle_t;
/*雙向鏈表*/
typedef struct Dblist
{
struct Dblist *next;
struct Dblist *prev;
int data;
}DList_t, *DList_handle_t;
/*多層次鏈表*/
typedef struct mullevel_list
{
struct mullevel_list *prev;
struct mullevel_list *next;
struct mullevel_list *child;
int data;
}MList_t, *MList_handle_t;
關(guān)于鏈表主要還是搞清楚指針的相關(guān)問(wèn)題。鏈表頭的更新操作也是指針操作的一部分，如何實(shí)現(xiàn)鏈表頭的自動(dòng)更新也是需要注意的，如果每次都采用返回值的形式實(shí)現(xiàn)鏈表的頭的更新，這在實(shí)際的操作中非常的不放便，采用指向指針的指針實(shí)現(xiàn)鏈表頭的更新將是非常不錯(cuò)的選擇。其實(shí)這也是內(nèi)存分配中經(jīng)常使用的技巧。
/*內(nèi)存分配*/
bool GetMemory(char ** str, int n)
{
*str = (char *) malloc(n);
if(*str)
return true;
return false;
}
/*鏈表頭的更新*/
bool insert_listnode(List_handle_t *head, int a)
{
List_handle_t newlistnode = (List_handle_t)malloc(sizeof(List_t)/sizeof(char));
if(*head == NULL && newlistnode != NULL)
{
*head = newlistnode;
newlistnode->data = a;
newlistnode->next = NULL;
return true;
}
else if(*head != NULL ** newlistnode != NULL)
{
newlistnode->data = a;
newlistnode->next = *head;
*head = newlistnode;
return true;
}
return false;
}
其中這種采用指向指針的指針的方式就能夠保證鏈表的自動(dòng)更新，這種特性主要是C/C++中函數(shù)值傳遞的特性，形參不改變實(shí)參的值，但是當(dāng)傳遞的是指針時(shí)，這時(shí)指針實(shí)質(zhì)上就是地址，作為參數(shù)時(shí)，地址并不會(huì)改變，但是地址中的內(nèi)容是可改變的，這是內(nèi)存分配問(wèn)題中經(jīng)常使用的技巧，如上面的代碼所示。這種代碼的形式還有一些優(yōu)點(diǎn)，可以判斷判斷問(wèn)題是否完成，通過(guò)判斷是否需要再次分配。
單鏈表的逆序問(wèn)題：
逆序問(wèn)題實(shí)質(zhì)上主要是完成每一個(gè)鏈表節(jié)點(diǎn)的操作，然后更新鏈表頭，這時(shí)需要三個(gè)指針，其中一個(gè)表示逆序鏈表的表頭，一個(gè)表示需要操作的節(jié)點(diǎn)，最后一個(gè)表示下一個(gè)即將操作的節(jié)點(diǎn)，也就是逆序操作需要保存三個(gè)節(jié)點(diǎn)才能保證一個(gè)逆序的完成。首先保證下一個(gè)即將操作的節(jié)點(diǎn)存在，然后實(shí)現(xiàn)逆序鏈表表頭與實(shí)際操作的節(jié)點(diǎn)進(jìn)行指向操作，更新表頭。
bool reversed_list(List_handle_t *head)
{
List_handle_t mid ;
List_handle_t fir ;
List_handle_t last;
if(*head != NULL)
{
mid = last = head;
/*save the node next to be operated*/
fir = mid->next;
/*tail of the list*/
last->next = NULL;
while(fir != NULL)
{
/*get the node to be operated*/
mid = fir;
/*save the node next to be operated*/
fir = fir->next;
/*link to the head of list*/
mid->next = last;
/*update the head of list*/
last = mid;
}
/*return the actual list head*/
*head = last;
return true;
}
return false;
}
關(guān)于鏈表是否為循環(huán)鏈表的問(wèn)題，這種問(wèn)題是一個(gè)經(jīng)典的問(wèn)題，因?yàn)殒湵聿僮鲗?shí)質(zhì)上就是指針的比較高級(jí)的操作。所以一般都需要依仗指針進(jìn)行操作。如何判斷是否為循環(huán)呢？如果是像數(shù)組那種連續(xù)的內(nèi)存空間可以通過(guò)指針的值進(jìn)行判斷，連續(xù)性就能使得指針的比較存在意義，但是鏈表是一個(gè)非連續(xù)的內(nèi)存空間，對(duì)指針進(jìn)行比較就沒(méi)有任何的意義。通常采用快慢指針的形式進(jìn)行判斷。
兩個(gè)指針，其中一個(gè)指針以每次一個(gè)對(duì)象的形式遍歷鏈表，另一個(gè)鏈表以每次多個(gè)對(duì)象的形式遍歷，如果是非循環(huán)的鏈表，那么快的指針會(huì)首先到達(dá)鏈表的尾部。但是如果是循環(huán)鏈表，這時(shí)快指針的遍歷速度快，因?yàn)榇嬖谘h(huán)，就會(huì)存在快指針指向慢指針后面對(duì)象的時(shí)刻，如果快指針指向的對(duì)象就是慢指針指向的對(duì)象或者快指針的下一個(gè)對(duì)象就是慢指針指向的對(duì)象（這兩種情況都合適，這需要一句循環(huán)鏈表中的對(duì)象進(jìn)行確定），就說(shuō)明了鏈表是一個(gè)循環(huán)鏈表�？熘羔樀脑L(fǎng)問(wèn)速度可以設(shè)置為每次兩個(gè)對(duì)象，這樣就能實(shí)現(xiàn)判斷。如下所示：
bool isTermination(List_handle_t list)
{
List_handle_t slow , fast;
slow = fast = list;
while(1)
{
if(!fast || !fast->next)
return false;
else
{
/*快指針以2倍速度循環(huán)*/
fast = fast->next->next;
/*慢指針以1倍速度循環(huán)*/
slow = slow->next;
if(fast == slow || fast->next == slow)
return false;
}
}
}
鏈表倒數(shù)m個(gè)節(jié)點(diǎn)的對(duì)象
這種問(wèn)題的解決方式很多，但是如何保證復(fù)雜度上最小卻是一個(gè)重要的問(wèn)題，最好是只遍歷一次鏈表就能找到對(duì)應(yīng)的節(jié)點(diǎn)，實(shí)質(zhì)上采用類(lèi)似于哨兵指針的形式就能實(shí)現(xiàn)。設(shè)置兩個(gè)指針，分別執(zhí)行鏈表頭和鏈表的第m個(gè)對(duì)象，然后兩個(gè)指針?lè)謩e遍歷，當(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)的指針就起到了類(lèi)似哨兵指針的作用。
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 the head*/
temp = list;
/*pass the list*/
while(mtemp->next != NULL)
{
mtemp = mtemp->next;
temp = temp->next;
}
return temp;
}
}
return NULL;
}
關(guān)于多層次鏈表的平鋪操作，因?yàn)槎鄬哟捂湵硎穷?lèi)似于樹(shù)的結(jié)構(gòu)，當(dāng)然可以采用類(lèi)似樹(shù)的遍歷形式進(jìn)行平鋪，但是這種方式對(duì)節(jié)點(diǎn)的訪(fǎng)問(wèn)形式往往都是多次遍歷。由于多層次的鏈表平鋪還需要取消平鋪操作，因此最好不要破壞每一個(gè)層次中的鏈接關(guān)系，如果破壞了每一層中的鏈接關(guān)系，就會(huì)使得每一層的還原操作非常復(fù)雜，我們可以按照層次逐層逐層的訪(fǎng)問(wèn)。
多層次鏈表的平鋪?zhàn)詈玫姆绞绞浅浞掷梦补?jié)點(diǎn)，也就是將每一層的對(duì)象都接到平鋪鏈表的尾部，而且隨著平鋪鏈表長(zhǎng)度的增長(zhǎng)，下一層次的節(jié)點(diǎn)也能夠訪(fǎng)問(wèn)到，這時(shí)候通過(guò)判斷節(jié)點(diǎn)是否存在子層，如果有就繼續(xù)添加到尾節(jié)點(diǎn)，這樣就能實(shí)現(xiàn)不同層次節(jié)點(diǎn)的平鋪。這種平鋪操作的優(yōu)點(diǎn)在于只遍歷了一次第一層的節(jié)點(diǎn)完成平鋪操作，而且沒(méi)有破壞每一層對(duì)象的鏈接關(guān)系，便于后期的還原。這種方法的關(guān)鍵在于如何控制鏈表的尾節(jié)點(diǎn)。
/*add sublevel listnode to the tail of first level*/
void appendtail(MList_handle_t head, 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);
/*updata the 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)槠戒仜](méi)有破壞每一層的鏈接關(guān)系，這樣只訪(fǎng)問(wè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)的管理問(wè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)殒湵淼奶厥庑�，使得指針的比較操作變得無(wú)效，但是可以通過(guò)指針的相等和不相等進(jìn)行操作，設(shè)置哨兵指針等指針的重要操作。
同時(shí)需要注意鏈表是一個(gè)可能動(dòng)態(tài)增長(zhǎng)的對(duì)象，只要時(shí)刻理解這種動(dòng)態(tài)特性就能比較好的理解鏈表中的多層次問(wèn)題，平鋪過(guò)程就是利用了鏈表的動(dòng)態(tài)增長(zhǎng)過(guò)程，通過(guò)鏈表尾實(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)操作。