【 聲明:版權所有,歡迎轉載,請勿用於商業用途。 聯系信箱:feixiaoxing @163.com】
前面的博客中,我們曾經有一篇專門講到單向鏈表的內容。那麼今天討論的鏈表和上次討論的鏈表有什麼不同呢?重點就在這個"循環"上面。有了循環,意味著我們可以從任何一個鏈表節點開始工作,可以把root定在任何鏈表節點上面,可以從任意一個鏈表節點訪問數據,這就是循環的優勢。
那麼在實現過程中,循環單向鏈表有什麼不同?
1)打印鏈表數據
void print_data(const LINK_NODE* pLinkNode)
{
LINK_NODE* pIndex = NULL;
if(NULL == pLinkNode)
return;
printf("%d\n", pLinkNode->data);
pIndex = pLinkNode->next;
while(pLinkNode != pIndex){
printf("%d\n", pIndex->data);
pIndex = pIndex ->next;
}
}
void print_data(const LINK_NODE* pLinkNode)
{
LINK_NODE* pIndex = NULL;
if(NULL == pLinkNode)
return;
printf("%d\n", pLinkNode->data);
pIndex = pLinkNode->next;
while(pLinkNode != pIndex){
printf("%d\n", pIndex->data);
pIndex = pIndex ->next;
}
} 以往,我們發現打印數據的結束都是判斷指針是否為NULL,這裡因為是循環鏈表所以發生了變化。原來的條件(NULL != pLinkNode)也修改成了這裡的(pLinkNode != pIndex)。同樣需要修改的函數還有find函數、count統計函數。
2)插入數據
STATUS insert_data(LINK_NODE** ppLinkNode, int data)
{
LINK_NODE* pNode;
if(NULL == ppLinkNode)
return FALSE;
if(NULL == *ppLinkNode){
pNode = create_link_node(data);
assert(NULL != pNode);
pNode->next = pNode;
*ppLinkNode = pNode;
return TRUE;
}
if(NULL != find_data(*ppLinkNode, data))
return FALSE;
pNode = create_link_node(data);
assert(NULL != pNode);
pNode->next = (*ppLinkNode)->next;
(*ppLinkNode)->next = pNode;
return TRUE;
}
STATUS insert_data(LINK_NODE** ppLinkNode, int data)
{
LINK_NODE* pNode;
if(NULL == ppLinkNode)
return FALSE;
if(NULL == *ppLinkNode){
pNode = create_link_node(data);
assert(NULL != pNode);
pNode->next = pNode;
*ppLinkNode = pNode;
return TRUE;
}
if(NULL != find_data(*ppLinkNode, data))
return FALSE;
pNode = create_link_node(data);
assert(NULL != pNode);
pNode->next = (*ppLinkNode)->next;
(*ppLinkNode)->next = pNode;
return TRUE;
}這裡的insert函數在兩個地方發生了變化:
a)如果原來鏈表中沒有節點,那麼鏈表節點需要自己指向自己
b)如果鏈表節點原來存在,那麼只需要在當前的鏈表節點後面添加一個數據,同時修改兩個方向的指針即可
3) 刪除數據
STATUS delete_data(LINK_NODE** ppLinkNode, int data)
{
LINK_NODE* pIndex = NULL;
LINK_NODE* prev = NULL;
if(NULL == ppLinkNode || NULL == *ppLinkNode)
return FALSE;
pIndex = find_data(*ppLinkNode, data);
if(NULL == pIndex)
return FALSE;
if(pIndex == *ppLinkNode){
if(pIndex == pIndex->next){
*ppLinkNode = NULL;
}else{
prev = pIndex->next;
while(pIndex != prev->next)
prev = prev->next;
prev->next = pIndex->next;
*ppLinkNode = pIndex->next;
}
}else{
prev = pIndex->next;
while(pIndex != prev->next)
prev = prev->next;
prev->next = pIndex->next;
}
free(pIndex);
return TRUE;
}
STATUS delete_data(LINK_NODE** ppLinkNode, int data)
{
LINK_NODE* pIndex = NULL;
LINK_NODE* prev = NULL;
if(NULL == ppLinkNode || NULL == *ppLinkNode)
return FALSE;
pIndex = find_data(*ppLinkNode, data);
if(NULL == pIndex)
return FALSE;
if(pIndex == *ppLinkNode){
if(pIndex == pIndex->next){
*ppLinkNode = NULL;
}else{
prev = pIndex->next;
while(pIndex != prev->next)
prev = prev->next;
prev->next = pIndex->next;
*ppLinkNode = pIndex->next;
}
}else{
prev = pIndex->next;
while(pIndex != prev->next)
prev = prev->next;
prev->next = pIndex->next;
}
free(pIndex);
return TRUE;
}和添加數據一樣,刪除數據也要在兩個方面做出改變:
a)如果當前鏈表節點中只剩下一個數據的時候,刪除後需要設置為NULL
b)刪除數據的時候首先需要當前數據的前一個數據,這個時候就可以從當前刪除的數據開始進行遍歷
c) 刪除的時候需要重點判斷刪除的數據是不是鏈表的頭結點數據