线性表 - 链式存储结构 - 单链表
单链表
链接存储方法
链接方式存储的线性表简称为链表(Linked List)
链表的具体存储表示为
① 用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的 也可以是不连续的)
② 链表中结点的逻辑次序和物理次序不一定相同 为了能正确表示结点间的逻辑关系 在存储每个结点值的同时 还必须存储指示其后继
结点的地址(或位置)信息(称为指针(pointer)或链(link))
注意
链式存储是最常用的存储方式之一 它不仅可用来表示线性表 而且可用来表示各种非线性的数据结构
链表的结点结构
┌──┬──┐
│data│next│
└──┴──┘
data域 存放结点值的数据域
next域 存放结点的直接后继的地址(位置)的指针域(链域)
注意
①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的
②每个结点只有一个链域的链表称为单链表(Single Linked List)
【例】线性表(bat cat eat fat hat jat lat mat)的单链表示如示意图
头指针head和终端结点指针域的表示
单链表中每个结点的存储地址是存放在其前趋结点next域中 而开始结点无前趋 故应设头指针head指向开始结点
注意
链表由头指针唯一确定 单链表可以用头指针的名字来命名
【例】头指针名是head的链表可称为表head
终端结点无后继 故终端结点的指针域为空 即NULL
单链表的一般图示法
由于我们常常只注重结点间的逻辑顺序 不关心每个结点的实际位置 可以用箭头来表示链域中的指针 线性表(bat cat fat hat
jat lat mat)的单链表就可以表示为下图形式
单链表类型描述
typedef char DataType; //假设结点的数据域类型为字符
typedef struct node{ //结点类型定义
DataType data; //结点的数据域
struct node *next;//结点的指针域
}ListNode;
typedef ListNode *LinkList;
ListNode *p;
LinkList head;
注意
①LinkList和ListNode *是不同名字的同一个指针类型(命名的不同是为了概念上更明确)
②LinkList类型的指针变量head表示它是单链表的头指针
③ListNode *类型的指针变量p表示它是指向某一结点的指针
指针变量和结点变量
┌────┬────────────┬─────────────┐
│ │ 指针变量 │ 结点变量 │
├────┼────────────┼─────────────┤
│ 定义 │在变量说明部分显式定义 │在程序执行时 通过标准 │
│ │ │函数malloc生成 │
├────┼────────────┼─────────────┤
│ 取值 │ 非空时 存放某类型结点 │实际存放结点各域内容 │
│ │ 的地址 │ │
├────┼────────────┼─────────────┤
│操作方式│ 通过指针变量名访问 │ 通过指针生成 访问和释放│
└────┴────────────┴─────────────┘
①生成结点变量的标准函数
p=( ListNode *)malloc(sizeof(ListNode));
//函数malloc分配一个类型为ListNode的结点变量的空间 并将其首地址放入指针变量p中
②释放结点变量空间的标准函数
free(p);//释放p所指的结点变量空间
③结点分量的访问
利用结点变量的名字*p访问结点分量
方法一 (*p) data和(*p) next
方法二 p ﹥data和p ﹥next
④指针变量p和结点变量*p的关系
指针变量p的值——结点地址
结点变量*p的值——结点内容
(*p) data的值——p指针所指结点的data域的值
(*p) next的值——*p后继结点的地址
*((*p) next)——*p后继结点
注意
① 若指针变量p的值为空(NULL) 则它不指向任何结点 此时 若通过*p来访问结点就意味着访问一个不存在的变量 从而引起程序的错
误
② 有关指针类型的意义和说明方式的详细解释 【参考C语言的有关资料】
lishixinzhi/Article/program/sjjg/201311/23313
