鏈表中幾個較重要的問題

/*單鏈表*/
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;

intdata;
}MList_t, *MList_handle_t;

關于鏈表主要還是搞清楚指針的相關問題。鏈表頭的更新操作也是指針操作的一部分，如何實現鏈表頭的自動更新也是需要注意的，如果每次都采用返回值的形式實現鏈表的頭的更新，這在實際的操作中非常的不放便，采用指向指針的指針實現鏈表頭的更新將是非常不錯的選擇。其實這也是內存分配中經常使用的技巧。

/*內存分配*/
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;
}

其中這種采用指向指針的指針的方式就能夠保證鏈表的自動更新，這種特性主要是C/C++中函數值傳遞的特性，形參不改變實參的值，但是當傳遞的是指針時，這時指針實質上就是地址，作為參數時，地址并不會改變，但是地址中的內容是可改變的，這是內存分配問題中經常使用的技巧，如上面的代碼所示。這種代碼的形式還有一些優點，可以判斷判斷問題是否完成，通過判斷是否需要再次分配。

單鏈表的逆序問題：
逆序問題實質上主要是完成每一個鏈表節點的操作，然后更新鏈表頭，這時需要三個指針，其中一個表示逆序鏈表的表頭，一個表示需要操作的節點，最后一個表示下一個即將操作的節點，也就是逆序操作需要保存三個節點才能保證一個逆序的完成。首先保證下一個即將操作的節點存在，然后實現逆序鏈表表頭與實際操作的節點進行指向操作，更新表頭。

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

關于鏈表是否為循環鏈表的問題，這種問題是一個經典的問題，因為鏈表操作實質上就是指針的比較高級的操作。所以一般都需要依仗指針進行操作。如何判斷是否為循環呢？如果是像數組那種連續的內存空間可以通過指針的值進行判斷，連續性就能使得指針的比較存在意義，但是鏈表是一個非連續的內存空間，對指針進行比較就沒有任何的意義。通常采用快慢指針的形式進行判斷。

兩個指針，其中一個指針以每次一個對象的形式遍歷鏈表，另一個鏈表以每次多個對象的形式遍歷，如果是非循環的鏈表，那么快的指針會首先到達鏈表的尾部。但是如果是循環鏈表，這時快指針的遍歷速度快，因為存在循環，就會存在快指針指向慢指針后面對象的時刻，如果快指針指向的對象就是慢指針指向的對象或者快指針的下一個對象就是慢指針指向的對象（這兩種情況都合適，這需要一句循環鏈表中的對象進行確定），就說明了鏈表是一個循環鏈表。快指針的訪問速度可以設置為每次兩個對象，這樣就能實現判斷。如下所示：

bool isTermination(List_handle_t list)
{
List_handle_t slow , fast;
slow = fast = list;

while(1)
{
if(!fast || !fast->next)
return false;
else
{
/*快指針以2倍速度循環*/
fast = fast->next->next;
/*慢指針以1倍速度循環*/
slow = slow->next;

if(fast == slow || fast->next== slow)
return false;
}
}
}