鏈表中幾個較重要的問題

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;
}

關于多層次鏈表的平鋪操作，因為多層次鏈表是類似于樹的結構，當然可以采用類似樹的遍歷形式進行平鋪，但是這種方式對節點的訪問形式往往都是多次遍歷。由于多層次的鏈表平鋪還需要取消平鋪操作，因此最好不要破壞每一個層次中的鏈接關系，如果破壞了每一層中的鏈接關系，就會使得每一層的還原操作非常復雜，我們可以按照層次逐層逐層的訪問。

多層次鏈表的平鋪最好的方式是充分利用尾節點，也就是將每一層的對象都接到平鋪鏈表的尾部，而且隨著平鋪鏈表長度的增長，下一層次的節點也能夠訪問到，這時候通過判斷節點是否存在子層，如果有就繼續添加到尾節點，這樣就能實現不同層次節點的平鋪。這種平鋪操作的優點在于只遍歷了一次第一層的節點完成平鋪操作，而且沒有破壞每一層對象的鏈接關系，便于后期的還原。這種方法的關鍵在于如何控制鏈表的尾節點。

/*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;
}
}

取消平鋪操作，主要是切斷每一層之間的前后鏈接關系，而保持子層鏈接關系，實質上這可以采用遞歸的形式實現，因為如果當前節點存在子節點，那么就將子節點的鏈接關系切斷，如果子節點也仍然存在子節點，那么先切斷子層的鏈接關系，因為平鋪沒有破壞每一層的鏈接關系，這樣只訪問第一層就能完成取消平鋪操作。實質完成的操作就是講當前子節點的前一個節點的后一個節點設置為NULL，而將當前子節點的前一個對象設置為NULL，這樣就切斷了各層之間的關系。因為每一次切斷都會導致平鋪鏈表的縮短，當平鋪鏈表只有原始第一層的長度時，這時候就完成了鏈表的取消平鋪操作，當然仍然需要注意尾節點的管理問題。但是我們不能將取消平鋪操作直接設置成一個遞歸操作，平鋪操作最后肯定會管理鏈表尾，而子層與母層的鏈表斷裂關系并不需要設置鏈表尾。

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;
}

總結

關于鏈表的操作我認為主要還是要設置恰當的指針，鏈表的操作就是指針的操作，但是因為鏈表的特殊性，使得指針的比較操作變得無效，但是可以通過指針的相等和不相等進行操作，設置哨兵指針等指針的重要操作。

同時需要注意鏈表是一個可能動態增長的對象，只要時刻理解這種動態特性就能比較好的理解鏈表中的多層次問題，平鋪過程就是利用了鏈表的動態增長過程，通過鏈表尾實現動態操作。而取消平鋪操作只是完成了切斷各層之間的連接關系而已，并不會更新鏈表尾，但是鏈表的長度也發生了動態變化。

把握鏈表的動態增長特性和指針的相關操作就能很好的完成鏈表的相關操作。