首页 > 代码库 > 一步一步写算法(之双向链表)

一步一步写算法(之双向链表)

原文: 一步一步写算法(之双向链表)

【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱:feixiaoxing @163.com】


    前面的博客我们介绍了单向链表。那么我们今天介绍的双向链表,顾名思义,就是数据本身具备了左边和右边的双向指针。双向链表相比较单向链表,主要有下面几个特点:

    (1)在数据结构中具有双向指针

    (2)插入数据的时候需要考虑前后的方向的操作

    (3)同样,删除数据的是有也需要考虑前后方向的操作

    那么,一个非循环的双向链表操作应该是怎么样的呢?我们可以自己尝试一下:

    (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 = http://www.mamicode.com/value;>    (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 =http://www.mamicode.com/= pNode->data)>    (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;	}}
    注意:

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


【预告: 下面我们讨论的是循环单向链表】


一步一步写算法(之双向链表)