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

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

關(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問(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;
}
}
}