224链式存储线性表的基本运算 特点:用一组任意的存储单元(可以是连续的,也可以是不 连续的)存放线性表的数据元素。线性表最常用的链式存 储方式如下图所示: head 35 41 60 96入 由于线性表的这种链式存储结构通过指针域将所有元 素关联成为一个长链,因此称为单链表
特点：用一组任意的存储单元(可以是连续的,也可以是不 连续的)存放线性表的数据元素。线性表最常用的链式存 储方式如下图所示： head 35 41 60 ….. 96 ∧ 由于线性表的这种链式存储结构通过指针域将所有元 素关联成为一个长链，因此称为单链表。 2.2.4 链式存储线性表的基本运算
链表中的基本概念: 头指针:存放链表第一个结点内存地址的指针变量,链 表的关键数据; 头结点:为了方便链表操作,在链表的第一个实际结点 之前附设的结点,该结点只使用指针域; 首元结点:链表中的第一个实际结点; a a a 首元 头指针结点 不带头结点的单链表 head a 2 3 an∧ 头结点 带头结点的单链表
❖链表中的基本概念： • 头指针：存放链表第一个结点内存地址的指针变量，链 表的关键数据； • 头结点：为了方便链表操作，在链表的第一个实际结点 之前附设的结点，该结点只使用指针域； • 首元结点：链表中的第一个实际结点； head a1 a2 a3 ….. an ∧ 带头结点的单链表 a1 a2 a3 ….. an ∧ 不带头结点的单链表 head 头指针 头结点 首元 结点
线性表的链式存储结构可用C语言中的“结构指针”来描 述 struct nodetype Elem Type data /*data数据项用于存放结点的数据值* struct nodetype米next /*next数据项存放下一个结点的指针米/ data next 注:后面讨论具体算法实现时,以 ElemType为整型为例 进行介绍,即有 typedef Elem Type int
struct nodetype { ElemType data； /*data数据项用于存放结点的数据值*/ struct nodetype *next； /*next数据项存放下一个结点的指针*/ } ； • 线性表的链式存储结构可用C语言中的“结构指针”来描 述 • 注：后面讨论具体算法实现时，以ElemType为整型为例 进行介绍,即有typedef ElemType int。 data next
2241单链表的初始化运算 初始化操作是建立一个空链表。即链表中仅有 个头结点,且头结点的指针域为空。 head ∧带头结点的空链表 具体实现过程如下: 第一步:申请头结点空间,用head变量记下头结点空间 的内存地址; 第二步:给头结点的指针数据项(next数据项)赋值为 空指针。 第三步:将单链表的头指针(head变量的值)返回给 主调函数
•具体实现过程如下： 第一步：申请头结点空间，用head变量记下头结点空间 的内存地址； 第二步：给头结点的指针数据项（next数据项）赋值为 空指针。 第三步：将单链表的头指针（head变量的值）返回给 主调函数。 初始化操作是建立一个空链表。即链表中仅有 一个头结点，且头结点的指针域为空。 head ∧ 带头结点的空链表 2.2.4.1 单链表的初始化运算
2241单链表的初始化运算 初始化操作是建立一个空链表。即链表中仅有 个头结点,且头结点的指针域为空。 head ∧带头结点的空链表 具体算法如下: typedef struct nodetype nodetype nodetype*k initiO inodetype * head head=(nodetype*)malloc(sizeof(nodetype)) /*为头结点申请空间*/ if (head! =NULL) head->next=NULL return(head) /*将头结点的指针域初始化为NULL米/
具体算法如下： typedef struct nodetype nodetype; nodetype* initl() {nodetype *head; head=(nodetype*)malloc(sizeof(nodetype))； /*为头结点申请空间*/ if(head!=NULL) head->next=NULL； return(head); /*将头结点的指针域初始化为NULL*/ } 初始化操作是建立一个空链表。即链表中仅有 一个头结点，且头结点的指针域为空。 head ∧ 带头结点的空链表 2.2.4.1 单链表的初始化运算