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

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

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

    有的时候,处于内存中的数据并不是连续的。那么这时候,我们就需要在数据结构中添加一个属性,这个属性会记录下面一个数据的地址。有了这个地址之后,所有的数据就像一条链子一样串起来了,那么这个地址属性就起到了穿线连结的作用。

    相比较普通的线性结构,链表结构的优势是什么呢?我们可以总结一下:

    (1)单个节点创建非常方便,普通的线性内存通常在创建的时候就需要设定数据的大小

    (2)节点的删除非常方便,不需要像线性结构那样移动剩下的数据

    (3)节点的访问方便,可以通过循环或者递归的方法访问到任意数据,但是平均的访问效率低于线性表

    那么在实际应用中,链表是怎么设计的呢?我们可以以int数据类型作为基础,设计一个简单的int链表:

    (1)设计链表的数据结构

typedef struct _LINK_NODE
{
    int data;
	struct _LINK_NODE* next;
}LINK_NODE;

    (2)创建链表

LINK_NODE* alloca_node(int value)
{
    LINK_NODE* pLinkNode = NULL;
	pLinkNode = (LINK_NODE*)malloc(sizeof(LINK_NODE));

	pLinkNode->data = value;
	pLinkNode->next = NULL;
	return pLinkNode;
}

    (3)删除链表

void delete_node(LINK_NODE** pNode)
{
    LINK_NODE** pNext;
    if(NULL == pNode || NULL == *pNode)
	    return ;

	pNext = &(*pNode)->next;
	free(*pNode);
	delete_node(pNext);
}

    (4)链表插入数据

STATUS _add_data(LINK_NODE** pNode, LINK_NODE* pDataNode)
{
    if(NULL == *pNode){
	    *pNode = pDataNode;
		return TRUE;
	}

	return _add_data(&(*pNode)->next, pDataNode);
}

STATUS add_data(const LINK_NODE** pNode, int value)
{
    LINK_NODE* pDataNode;
    if(NULL == *pNode)
	    return FALSE;

	pDataNode = alloca_node(value);
	assert(NULL != pDataNode);
	return _add_data((LINK_NODE**)pNode, pDataNode);
}

    (5)删除数据

STATUS _delete_data(LINK_NODE** pNode, int value)
{
    LINK_NODE* pLinkNode;
    if(NULL == (*pNode)->next)
	    return FALSE;

	pLinkNode = (*pNode)->next;
	if(value == pLinkNode->data){
	    (*pNode)->next = pLinkNode->next;
		free(pLinkNode);
		return TRUE;
	}else{
	    return _delete_data(&(*pNode)->next, value);
	}
}

STATUS delete_data(LINK_NODE** pNode, int value)
{
    LINK_NODE* pLinkNode;
    if(NULL == pNode || NULL == *pNode)
	    return FALSE;

    if(value == (*pNode)->data){
	    pLinkNode = *pNode;
		*pNode = pLinkNode->next;
		free(pLinkNode);
		return TRUE;
	}		

	return _delete_data(pNode, value);
}

    (6)查找数据

LINK_NODE* find_data(const LINK_NODE* pLinkNode, int value)
{
    if(NULL == pLinkNode)
	    return NULL;

	if(value == pLinkNode->data)
	    return (LINK_NODE*)pLinkNode;

	return find_data(pLinkNode->next, value);
}

    (7)打印数据

void print_node(const LINK_NODE* pLinkNode)
{
    if(pLinkNode){
	    printf("%d\n", pLinkNode->data);
		print_node(pLinkNode->next);
	}
}

    (8)统计数据

int count_node(const LINK_NODE* pLinkNode)
{
    if(NULL == pLinkNode)
	    return 0;

	return 1 + count_node(pLinkNode->next);
}

【预告: 下一篇博客介绍双向链表】

时间: 2024-12-26 05:21:20

一步一步写算法(之单向链表)的相关文章

一步一步写算法(之链表逆转)

原文:一步一步写算法(之链表逆转) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     链表逆转是面试环境中经常遇到的一道题目,也是我们在实际开发中可能会遇到的开发需求.和线性逆转不一样,单向链表的节点需要一个一个进行处理.为了显示两者之间的区别,我们分别对线性内存和链表进行逆转:     (1)普通连续内存数据的反转分析 STATUS normal_revert(int array[], int length) { int* pDa

一步一步写算法(之链表重合)

原文:一步一步写算法(之链表重合) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     链表重合是一个好玩的问题.原题目是这样的:有两个链表,那么如何判断这两个链表是不是重合的?至于这个链表在什么时候重合的,这不重要,关键是判断这个链表究竟有没有重合.究竟有什么方法呢?     最简单的方法就是查看两者有没有共同点.那么依次判断就行了. int find_node_in_link(LINK_NODE* pLink, LINK_NODE

一步一步写算法(之链表排序)

原文:一步一步写算法(之链表排序) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     相比较线性表的排序而言,链表排序的内容稍微麻烦一点.一方面,你要考虑数据插入的步骤:另外一方面你也要对指针有所顾虑.要是有一步的内容错了,那么操作系统会马上给你弹出一个exception.就链表的特殊性而言,适合于链表的排序有哪些呢?     (1)插入排序    (适合)     (2)冒泡排序    (适合)     (3)希尔排序    (适

一步一步写算法(之循环单向链表)

原文:一步一步写算法(之循环单向链表) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     前面的博客中,我们曾经有一篇专门讲到单向链表的内容.那么今天讨论的链表和上次讨论的链表有什么不同呢?重点就在这个"循环"上面.有了循环,意味着我们可以从任何一个链表节点开始工作,可以把root定在任何链表节点上面,可以从任意一个链表节点访问数据,这就是循环的优势.     那么在实现过程中,循环单向链表有什么不同?     1)打印链

一步一步写算法(之 算法总结)

原文:一步一步写算法(之 算法总结) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]       自10月初编写算法系列的博客以来,陆陆续续以来写了几十篇.按照计划,还有三个部分的内容没有介绍,主要是(Dijkstra算法.二叉平衡树.红黑树).这部分会在后面的博客补充完整.这里主要是做一个总结,有兴趣的朋友可以好好看看,欢迎大家提出宝贵意见.       (1) 排序算法     快速排序           合并排序     堆排序

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

原文:一步一步写算法(之双向链表) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     前面的博客我们介绍了单向链表.那么我们今天介绍的双向链表,顾名思义,就是数据本身具备了左边和右边的双向指针.双向链表相比较单向链表,主要有下面几个特点:     (1)在数据结构中具有双向指针     (2)插入数据的时候需要考虑前后的方向的操作     (3)同样,删除数据的是有也需要考虑前后方向的操作     那么,一个非循环的双向链表操作应该

一步一步写算法(之二叉树深度遍历)

原文:一步一步写算法(之二叉树深度遍历) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     深度遍历是软件开发中经常遇到的遍历方法.常用的遍历方法主要有下面三种:(1)前序遍历:(2)中序遍历:(3)后序遍历.按照递归的方法,这三种遍历的方法其实都不困难,前序遍历就是根-左-右,中序遍历就是左-根-右,后续遍历就是左-右-根.代码实现起来也不复杂.     1)前序遍历 void preorder_traverse(TREE_NOD

一步一步写算法(之克鲁斯卡尔算法 下)

原文:一步一步写算法(之克鲁斯卡尔算法 下) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     前面在讨论克鲁斯卡尔的算法的时候,我们分析了算法的基本过程.基本数据结构和算法中需要解决的三个问题(排序.判断.合并).今天,我们继续完成剩下部分的内容.合并函数中,我们调用了两个基本函数,find_tree_by_index和delete_mini_tree_from_group,下面给出详细的计算过程. MINI_GENERATE_T

一步一步写算法(之线性结构的处理)

原文:一步一步写算法(之线性结构的处理) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     我们知道,在内存中的空间都是连续的.也就是说,0x00000001下面的地址必然是0x00000002.所以,空间上是不会出现地址的突变的.那什么数据结构类型是连续内部空间呢,其实就是数组,当然也可以是堆.数组有很多优势,它可以在一段连续空间内保存相同类型的数据,并且对这些数据进行管理.所以从这个意义上说,掌握了数组才能说明你数据结构入门了.