c++双向链表操作示例(创建双向链、双向链表中查找数据、插入数据等)

时间:2021-05-20

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

(1)定义双向链表的基本结构
复制代码 代码如下:
typedef struct _DOUBLE_LINK_NODE
{
int data;
struct _DOUBLE_LINK_NODE* prev;
struct _DOUBLE_LINK_NODE* next;
}DOUBLE_LINK_NODE;

(2)创建双向链表节点
复制代码 代码如下:
DOUBLE_LINK_NODE* create_double_link_node(int value)
{
DOUBLE_LINK_NODE* pDLinkNode = NULL;
pDLinkNode = (DOUBLE_LINK_NODE*)malloc(sizeof(DOUBLE_LINK_NODE));
assert(NULL != pDLinkNode);

memset(pDLinkNode, 0, sizeof(DOUBLE_LINK_NODE));
pDLinkNode->data = value;
return pDLinkNode;
}

(3)删除双向链表
复制代码 代码如下:
void delete_all_double_link_node(DOUBLE_LINK_NODE** pDLinkNode)
{
DOUBLE_LINK_NODE* pNode;
if(NULL == *pDLinkNode)
return ;

pNode = *pDLinkNode;
*pDLinkNode = pNode->next;
free(pNode);
delete_all_double_link_node(pDLinkNode);
}

(4)在双向链表中查找数据
复制代码 代码如下:
DOUBLE_LINK_NODE* find_data_in_double_link(const DOUBLE_LINK_NODE* pDLinkNode, int data)
{
DOUBLE_LINK_NODE* pNode = NULL;
if(NULL == pDLinkNode)
return NULL;

pNode = (DOUBLE_LINK_NODE*)pDLinkNode;
while(NULL != pNode){
if(data == pNode->data)
return pNode;
pNode = pNode ->next;
}

return NULL;
}

(5)双向链表中插入数据
复制代码 代码如下:
STATUS insert_data_into_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data)
{
DOUBLE_LINK_NODE* pNode;
DOUBLE_LINK_NODE* pIndex;

if(NULL == ppDLinkNode)
return FALSE;

if(NULL == *ppDLinkNode){
pNode = create_double_link_node(data);
assert(NULL != pNode);
*ppDLinkNode = pNode;
(*ppDLinkNode)->prev = (*ppDLinkNode)->next = NULL;
return TRUE;
}

if(NULL != find_data_in_double_link(*ppDLinkNode, data))
return FALSE;

pNode = create_double_link_node(data);
assert(NULL != pNode);

pIndex = *ppDLinkNode;
while(NULL != pIndex->next)
pIndex = pIndex->next;

pNode->prev = pIndex;
pNode->next = pIndex->next;
pIndex->next = pNode;
return TRUE;
}

(6)双向链表中删除数据
复制代码 代码如下:
STATUS delete_data_from_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data)
{
DOUBLE_LINK_NODE* pNode;
if(NULL == ppDLinkNode || NULL == *ppDLinkNode)
return FALSE;

pNode = find_data_in_double_link(*ppDLinkNode, data);
if(NULL == pNode)
return FALSE;

if(pNode == *ppDLinkNode){
if(NULL == (*ppDLinkNode)->next){
*ppDLinkNode = NULL;
}else{
*ppDLinkNode = pNode->next;
(*ppDLinkNode)->prev = NULL;
}

}else{
if(pNode->next)
pNode->next->prev = pNode->prev;
pNode->prev->next = pNode->next;
}

free(pNode);
return TRUE;
}

(7)统计双向链表中数据的个数
复制代码 代码如下:
int count_number_in_double_link(const DOUBLE_LINK_NODE* pDLinkNode)
{
int count = 0;
DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode;

while(NULL != pNode){
count ++;
pNode = pNode->next;
}
return count;
}

(8)打印双向链表中数据
复制代码 代码如下:
void print_double_link_node(const DOUBLE_LINK_NODE* pDLinkNode)
{
DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode;

while(NULL != pNode){
printf("%d\n", pNode->data);
pNode = pNode ->next;
}
}

今天我们讨论的双向链表是非循环的,大家可以考虑一下如果改成循环双向链表,应该怎么写?如果是有序的循环双向链表,又该怎么写?

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章