《计算机软件基础》第二章 线性数据结构（2-2-4）链式存储线性表的基本运算

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 单链表的初始化运算

2242单链表的创建运算 创建单链表方法有两种:尾接法和头插法 尾接法:从空链表开始,将各结点从链表的尾部依次链 接到链表中;由于该方法是将数据元素从链表的尾部接入, 因此,需用一个变量记住当前尾结点,修改尾结点的指针 域使其指向新结点。 p 尾结点 head a 2 k ∧

尾接法：从空链表开始，将各结点从链表的尾部依次链 接到链表中；由于该方法是将数据元素从链表的尾部接入， 因此，需用一个变量记住当前尾结点，修改尾结点的指针 域使其指向新结点。 ···· · head a1 a2 ak ∧ 尾结点 p 2.2.4.2 单链表的创建运算 创建单链表方法有两种：尾接法和头插法

2242单链表的创建运算 创建单链表方法有两种:尾接法和头插法 尾接法:从空链表开始,将各结点从链表的尾部依次链 接到链表中;由于该方法是将数据元素从链表的尾部接入, 因此,需用一个变量记住当前尾结点,修改尾结点的指针 域使其指向新结点。 p 尾结点 head a 2 k ∧ 新结点 申请新结点空间

尾接法：从空链表开始，将各结点从链表的尾部依次链 接到链表中；由于该方法是将数据元素从链表的尾部接入， 因此，需用一个变量记住当前尾结点，修改尾结点的指针 域使其指向新结点。 2.2.4.2 单链表的创建运算 创建单链表方法有两种：尾接法和头插法。 ···· · head a1 a2 ak ∧ 尾结点 新结点 申请新结点空间 p s

2242单链表的创建运算 创建单链表方法有两种:尾接法和头插法 尾接法:从空链表开始,将各结点从链表的尾部依次链 接到链表中;由于该方法是将数据元素从链表的尾部接入, 因此,需用一个变量记住当前尾结点,修改尾结点的指针 域使其指向新结点。 p 尾结点 head a 2 k ∧ 新结点 对其data数据项进行初始化 a

尾接法：从空链表开始，将各结点从链表的尾部依次链 接到链表中；由于该方法是将数据元素从链表的尾部接入， 因此，需用一个变量记住当前尾结点，修改尾结点的指针 域使其指向新结点。 2.2.4.2 单链表的创建运算 创建单链表方法有两种：尾接法和头插法。 ···· · head a1 a2 ak ∧ 尾结点 新结点 ak+1 对其data数据项进行初始化 p s

2242单链表的创建运算 创建单链表方法有两种:尾接法和头插法 尾接法:从空链表开始,将各结点从链表的尾部依次链 接到链表中;由于该方法是将数据元素从链表的尾部接入, 因此,需用一个变量记住当前尾结点,修改尾结点的指针 域使其指向新结点。 p 尾结点 head a 2 k ∧ 对其next数据项进行初始化,使之为 新结点 空NULL ak+∧

尾接法：从空链表开始，将各结点从链表的尾部依次链 接到链表中；由于该方法是将数据元素从链表的尾部接入， 因此，需用一个变量记住当前尾结点，修改尾结点的指针 域使其指向新结点。 2.2.4.2 单链表的创建运算 创建单链表方法有两种：尾接法和头插法。 ···· · head a1 a2 ak ∧ 尾结点 新结点 ak+1 ∧ 对其next数据项进行初始化，使之为 空NULL p s

2242单链表的创建运算 创建单链表方法有两种:尾接法和头插法 尾接法:从空链表开始,将各结点从链表的尾部依次链 接到链表中;由于该方法是将数据元素从链表的尾部接入, 因此,需用一个变量记住当前尾结点,修改尾结点的指针 域使其指向新结点。 p 尾结点 head a 2 k 新结点 将新结点链接到链表尾结点之后,即 ak+∧ p→next=s;

尾接法：从空链表开始，将各结点从链表的尾部依次链 接到链表中；由于该方法是将数据元素从链表的尾部接入， 因此，需用一个变量记住当前尾结点，修改尾结点的指针 域使其指向新结点。 2.2.4.2 单链表的创建运算 创建单链表方法有两种：尾接法和头插法。 ···· · head a1 a2 ak 尾结点 新结点 ak+1 ∧ 将新结点链接到链表尾结点之后，即 p->next=s; p s