线性表分为:顺序存储结构和连存储结构
顺序存储结构的优点:
1.空间利用率高,几乎不需要额外的空间开销.
2.数据的逻辑结构和物理结构完全一致.
3.结点地址计算的时间和线性表的规模大小无关.
4.可以用一维数组实现存储.
但是有两个致命的缺点:
1.顺序存储结构的存储空间是静态分配,必须有足够大的连续存储空间,如果不能则无法实现存储.在建立顺序表时,存储空间大小有时无法确切估计,估计过大回会使空闲区段的部分空间长期闲置,估计过小则会在操作中因空间不够而产生溢出.
2.插入操作和产出操作在大多数情况下,引起大量节点的频繁移动,降低了算法的时间效率.
因此:顺序存储结构 比较适合规模较小,长度变化不大且不很频繁的线性表存储实现.
克服线性表顺序存储结构的方法采用链表存储结构,链表存储结构的存储分配方式灵活,有效性好.用链表存储结构存储的线性表称为"链表".
链表分为:单链表,循环链表和双向链表.
下面就介绍一下单链表的基本操作.
链存储结构的存储分配以节点为单位,每个节点由节点数据和指针构成.
单链表的结点通常定义成两个域:结点数据和指针域.
指向首节点的指针称为头指针,存放在一个已命名的的头指针变量中,例如:H.头指针变量名就是单链表名,
typedef struct node{
int data;
struct node *next;
}LINKLIST;
这个结点类型的两个域分别命名为data何next.
理解这个几个常用的概念
指针:结点的存储地址
指针变量:存放指针的变量,例如:p,其值是指针
指针所指结点:以该指针为地址进行存储的结点,引用结点就是获得指向它的指针.
假定p是指向某结点的指针变量,在非形式语言中 ,通过p引用指向的结点,表示为(p),结点域的引用方式表示为"域名(指针)",例如:data(p)表示引用结点(p)的数据域,next(p)表示引用结点(p)的指针域.在C语言中,结点的引用方式是*p;域引用方式是p->data,p->next.
结点域:结点中的数据(自己的理解)
为了便于操作单链表,在单链表的首节点前增加一个附加结点,成为头结点,并且让头指针始终指向头结点,这种形式的单链表成为带头结点的单链表,
头结点的数据域不存放任何结点数据,必要时可以存放特殊意义的附加信息,例如标记性信息,计数信息等.头结点的指针域存放首节点的指针,当链表为空时,首结点指针的值为空(也就是头结点的指针域为NULL).
以上就是对单链表的定义和相关概念的解释.
此文介绍来自<>一书的定义.也是学习数据结构的开始,如果大家有好的建议和好的相关资料,希望大家给提出来,共同进步.
