第二章线性表——链式存储结构(3)

定义:

链式存储 :用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。

 

存储链表中结点的一组任意的存储单元可以是连续的,也可以是不连续的,

甚至是零散分布在内存中的任意位置上的。

 

 

链表中结点的逻辑顺序和物理顺序不一定相同。

 

为了正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其直接后继结点的地址(或位置),

称为指针(pointer)或链(link),这两部分组成了链表中的结点结构,

链表是通过每个结点的指针域将线性表的n个结点按其逻辑次序链接在一起的。

每一个结只包含一个指针域的链表,称为单链表。

为操作方便,总是在链表的第一个结点之前附设一个头结点(头指针)head指向第一个结点。头结点的数据域可以不存储任何信息(或链表长度等信息)。

 

二 、结点的描述与实现

C语言中用带指针的结构体类型来描述
typedef  struct  Lnode
{   ElemType  data;     /*数据域,保存结点的值 */
struct   Lnode  *next;      /*指针域*/
}LNode;        /*结点的类型 */

结点的实现

结点是通过动态分配和释放来的实现,即需要时分配,不需要时释放。

实现时是分别使用C语言提供的标准函数:malloc() ,realloc(),sizeof() ,free() 。

 

 最常用的基本操作及其示意图

⑴ 结点的赋值

1 LNode *p;
2 
3 p=(LNode*)malloc(sizeof(LNode));
4 
5 p->data=20; p->next=NULL ;

 

⑵  常见的指针操作

第二章线性表——链式存储结构(3)

 

 

 

 

 

 

 

 

 

 

 

 

第二章线性表——链式存储结构(3)

 

上一篇:C语言 创建单链表


下一篇:数据结构学习