本文主要是介绍数据结构C语言学习笔记D4,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
线性表之单链表
什么是单链表(single linked list)
链表,别名链式存储结构或单链表,用于存储逻辑关系为 “一对一” 的数据。与顺序表不同,链表不限 制数据的物理存储状态,使用链表存储的数据元素,其物理存储位置是随机的。
像上图: 数据元素随机存储,并通过指针表示数据之间逻辑关系的存储结构就是链式存储。
链表节点(node)
- 数据元素本身,其所在的区域称为数据域 ;
- 指向直接后继元素的指针,所在区域称指针域 ;
- 链表实际存储的是一个一个节点,真正的数据元素包含在这些节点中。
头节点,头指针和首元节点:
- 头指针:一个普通的指针永远指向链表第一个节点位置。头指针用于指明链表的位置,便于后期找到链表并使用表中数据;
- 节点:链表中的节点双细分为头节点、首元节点和其他节点:
- 头节点:其实就是一个不存任何数据的空节点,通常作为链表的第一个节点,头节点不是必须的,它的作用只是为了方便解决某些实际问题;
- 首元节点:由于头节点的缘故,通常作为链表的第一个存有数据的节点为首元节点,称谓,没有实际意义
- 其它节点:链表中其它的节点
- 注意:链表中有头节点时,头指针指向头节点rc之,若链表中没有头节点,则头指针指向首元节点。
链表的创建:
- 声明一个头指针(如有必要,可以声明一个头节点);
- 创建多个存储数据节点,在创建的过程中,要随时与其前驱节点建立逻辑关系
单链表的优缺点:
单链表的优点:存储角度讲①元素的存储单元是任意的,可连续也可不连续。②不需要限定长度。对存储块要求降低
单链表的缺点:算法角度讲①其查找时间复杂度为O(n),每次都得从头找起。②存放元素时需要另外开辟一个指针域的空间,malloc的释放要注意。
删指定节点:
q=p->next;p->data=q->data;p->next=q->next;free(q);
分析:首先用指针变量q指向结点A的后继结点B,然后将结点B的值复制到结点A中,最后删除结点B。
这篇关于数据结构C语言学习笔记D4的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!