数据结构C语言学习笔记D4

数据结构C语言学习笔记D4

线性表之单链表

什么是单链表(single linked list)

链表，别名链式存储结构或单链表，用于存储逻辑关系为 “一对一” 的数据。与顺序表不同，链表不限 制数据的物理存储状态，使用链表存储的数据元素，其物理存储位置是随机的。

像上图： 数据元素随机存储，并通过指针表示数据之间逻辑关系的存储结构就是链式存储。

链表节点（node）

1. 数据元素本身，其所在的区域称为数据域 ；
2. 指向直接后继元素的指针，所在区域称指针域 ；
   
3. 链表实际存储的是一个一个节点，真正的数据元素包含在这些节点中。
   
   头节点，头指针和首元节点：
   
   1. 头指针：一个普通的指针永远指向链表第一个节点位置。头指针用于指明链表的位置，便于后期找到链表并使用表中数据；
   2. 节点：链表中的节点双细分为头节点、首元节点和其他节点：

   • 头节点：其实就是一个不存任何数据的空节点，通常作为链表的第一个节点，头节点不是必须的，它的作用只是为了方便解决某些实际问题；
   • 首元节点：由于头节点的缘故，通常作为链表的第一个存有数据的节点为首元节点，称谓，没有实际意义
   • 其它节点：链表中其它的节点
   • 注意：链表中有头节点时，头指针指向头节点rc之，若链表中没有头节点，则头指针指向首元节点。

链表的创建：

1. 声明一个头指针（如有必要，可以声明一个头节点）；
2. 创建多个存储数据节点，在创建的过程中，要随时与其前驱节点建立逻辑关系

单链表的优缺点：

单链表的优点：存储角度讲①元素的存储单元是任意的，可连续也可不连续。②不需要限定长度。对存储块要求降低
单链表的缺点：算法角度讲①其查找时间复杂度为O(n)，每次都得从头找起。②存放元素时需要另外开辟一个指针域的空间，malloc的释放要注意。

删指定节点：
q=p->next；p->data=q->data；p->next=q->next；free(q)；
分析：首先用指针变量q指向结点A的后继结点B，然后将结点B的值复制到结点A中，最后删除结点B。