【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱: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);
}
【预告: 下一篇博客介绍双向链表】
分享到:
相关推荐
04.单向链表以及单向链表的应用.ppt
C#单向链表的实现的源码
1.随机产生或键盘输入一组元素,建立一个带头结点的单向链表(无序)。 2.遍历单向链表。 3.把单向链表中元素逆置(不允许申请新的结点空间)...利用算法5建立两个非递减有序单向链表,然后合并成一个非递增链表。
链表结点插入算法
单向链表类定义及测试文件 对应于数据机构与算法分析(c++版)第三版或第二版 作者Clifford A.Shaffer 重庆大学使用教材
一个java实例,用来描述java算法中链表的使用。
数据结构,c语言实现的单向链表。代码分享 struct LinkNode { int data; struct LinkNode *next; }; typedef struct LinkNode *Lnode;
西南交通大学 数据结构实验报告 单向链表 参考解答
#资源达人分享计划#
已知head指向一个带头结点的单向链表, 链表中每个结点包含数据域(data)和指针域(next)。 请编写函数实现如图所示链表逆置
链表有单向链表、双向链表、循环链表三种。单向循环链表是一种特殊的链表结构,它的尾节点的后继节点指向头结点,使得链表形成一个环。 解决约瑟夫问题的算法可以分为两个部分:建立链表和删除链结点。首先,建立一...
从键盘输入若干整数,直到输入0时停止,按输入整数顺序建立单向链表存储结构。然后用字符界面菜单提供以下功能: 1.插入元素--输入i, e,在单向链表第i个元素之前插入元素e,输出插入e后的单向链表(已知有效的插入...
利用单链表实现基排序算法
* 单向链表增删改查操作 * */ public class LinkTest { public static void main(String[] args) { Link l=new Link(); l.addNode("A"); l.addNode("B"); l.addNode("C"); l.addNode("D"); l.addNode("E")...
仅遍历一次单向链表,找出中间结点,经典C算法,
各种数据结构、算法及实用的C#源代码.C#,单向链表(Simply Linked List)快速排序(Quick Sort)算法与源代码.单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部...
每敲一次代码都会有新的收获,基本功不扎实啥也干不了。单向链表的插入,删除,创建,遍历是数据结构的基本操作。里边的算法值得学习。下面我们就来学习一下单向链表结点的逐个删除的方法。
链表逆置是计算机科学中一个重要的算法问题,它涉及到链表数据结构的操作和算法设计。在本文中,我们将详细讨论...链表可以分为单向链表、双向链表和循环链表等不同类型,但在链表逆置问题中,我们通常讨论单向链表。
今天小编就为大家分享一篇关于数据结构与算法:单向链表实现与封装,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
单向链表的存储特点及其实现,单向链表的插入 删除算法及其应用算法的程序实现