填装产大 Help 计算机专业 80 网上教学改革 数据结构（本） 授课教师：范颖
计算机专业 网上教学改革 数 据 结 构（本） 授课教师：范颖
一、第二章线性表解析 本章课程主要介绍线性表的定义，顺序存储结 构和链式存储结构的有关概念。能够利用C语言 的数组和指针实现对顺序表的相关操作。能够 利用C语言的结构变量和指向结构体的指针实现 对链表的相关操作。 www.open.ha.cn
www.open.ha.cn 一、第二章线性表解析 ▪ 本章课程主要介绍线性表的定义，顺序存储结 构和链式存储结构的有关概念。能够利用C语言 的数组和指针实现对顺序表的相关操作。能够 利用C语言的结构变量和指向结构体的指针实现 对链表的相关操作
一、第二章线性表解析 1、线性表的逻辑结构及存储结构是什么？ 线性表是一种最常用的数据结构，数据元素之 间的关系表现为：除第一个元素无直接前驱， 最后一个元素无直接后继外，其余元素均有且 仅有一个直接前驱和一个直接后继。 线性表的存储结构有两种实现方法式： (1)顺序存储结构 (2)链式存储结构 www.open.ha.cn
www.open.ha.cn 一、第二章线性表解析 ▪ 1、线性表的逻辑结构及存储结构是什么？ ▪ 线性表是一种最常用的数据结构，数据元素之 间的关系表现为：除第一个元素无直接前驱， 最后一个元素无直接后继外，其余元素均有且 仅有一个直接前驱和一个直接后继。 ▪ 线性表的存储结构有两种实现方法式： （1）顺序存储结构 （2）链式存储结构
一、第二章线性表解析 2、顺序存储结构是什么样子的，如何实现线性 表的相关操作？ 用顺序存储方法存储的线性表简称为顺序表。 数组是典型的顺序存储结构，因此可以采用数组 来存储线性表。结构如下： 下标 i-l 0 MAX-I 数组元素 n a ai-1 ai an 我们需要掌握的实现是线性表的插入和删除。 www.open.ha.cn
www.open.ha.cn 一、第二章线性表解析 ▪ 2、顺序存储结构是什么样子的，如何实现线性 表的相关操作？ ▪ 用顺序存储方法存储的线性表简称为顺序表。 ▪ 数组是典型的顺序存储结构，因此可以采用数组 来存储线性表。结构如下： n a1 …… ai-1 ai 下标 数组元素 …… an …… 0 1 i-1 i n MAX-1 ▪ 我们需要掌握的实现是线性表的插入和删除
一、第二章线性表解析 顺序表插入的操作： 向线性表中位置插入一个元素。从a开始逐次将 an,an-1,…, a:向后平移一个存储位置，然 后将x存入到a门中。 下标 i-1 MAX-1 数组元素 n al 年· ai-1 ai an 下标 0 1 i-1 i+1 n+l MAX-1 数组元素 n+1 al 。●。。 ai-1 X ai an 顺序表插入的步骤，请查看“1-顺序表插入.Sw”。 www.open.ha.cn
www.open.ha.cn 一、第二章线性表解析 ▪ 顺序表插入的操作： 向线性表中位置i插入一个元素。从an开始逐次将 an，an-1 ，……，ai向后平移一个存储位置，然 后将x存入到a[i]中。 ▪ 顺序表插入的步骤，请查看“1-顺序表插入.swf”。 n a1 …… ai-1 ai 下标 数组元素 …… an …… 0 1 i-1 i …… MAX-1 n+1 a1 …… ai-1 x 下标 数组元素 ai an …… 0 1 i-1 i i+1 n+1 MAX-1
一、第二章线性表解析 顺序表删除的操作： 删除线性表中位置的元素。逐次将a+1, a+2,…,an个元素向前平移一个存储位置， 使后面的数据元素逐次覆盖它的直接前驱。 下标 i-1 i+ n MAX-1 数组元素 n al ai-1 ai ai+1 an 。象888。 下标 0 1 l MAX-1 数组元素 n-1 al 中年。。中 ai-1 a钟l an 顺序表删除的步骤，请查看“2-顺序表删除.swf”。 www.open.ha.cn
www.open.ha.cn 一、第二章线性表解析 ▪ 顺序表删除的操作： 删除线性表中位置i的元素。逐次将ai+1， ai+2，……，an个元素向前平移一个存储位置， 使后面的数据元素逐次覆盖它的直接前驱。 ▪ 顺序表删除的步骤，请查看“2-顺序表删除.swf”。 n a1 …… ai-1 ai 下标 数组元素 ai+1 …… an 0 1 i-1 i …… MAX-1 n-1 a1 …… ai-1 ai+1 下标 数组元素 …… an …… 0 1 i-1 i n-1 MAX-1 i+1 …… n
一、第二章线性表解析 3、链表存储结构是什么样子的，如何实现线性 表的相关操作？ 链接方式存储的线性表简称为链表。 ■链表结点结构如图 data next data域：存放结点值的数据域， ■ next域：存放结点的直接后继的地址（位置) 的指针域（链域)。 链表通过每个结点的链域将线性表的个结点按 其逻辑顺序链接在一起的。 head al a2 an www.open.ha.cn
www.open.ha.cn 一、第二章线性表解析 ▪ 3、链表存储结构是什么样子的，如何实现线性 表的相关操作？ ▪ 链接方式存储的线性表简称为链表。 ▪ 链表结点结构如图： ▪ data域：存放结点值的数据域。 ▪ next域：存放结点的直接后继的地址（位置） 的指针域（链域）。 ▪ 链表通过每个结点的链域将线性表的n个结点按 其逻辑顺序链接在一起的。 data next head a1 a2 …… an ^
一、第二章线性表解析 (1)链表的建立 ■ 链表的建立有两种方法：尾插法和头插法。 尾插法算法思路：从一个空表开始，重复读入 数据，生成新结点，将读入数据存放在新结点 的数据域中，然后将新结点插入到当前链表的 表尾上，直到读入结束标志为止。 尾插法的步骤，请查看“3-尾插法建立单链表 .swf'。 www.open.ha.cn
www.open.ha.cn 一、第二章线性表解析 ▪ （1）链表的建立 ▪ 链表的建立有两种方法：尾插法和头插法。 ▪ 尾插法算法思路：从一个空表开始，重复读入 数据，生成新结点，将读入数据存放在新结点 的数据域中，然后将新结点插入到当前链表的 表尾上，直到读入结束标志为止。 ▪ 尾插法的步骤，请查看“3-尾插法建立单链表 .swf”
f 一、第二章线性表解析 (1)链表的建立 尾插法过程：指针变量q始终指向尾结点，p指针 开辟单元，生成结点。 ①q->next=p; ②q=p; 新结点 head al An N p q www.open.ha.cn
www.open.ha.cn 一、第二章线性表解析 ▪ （1）链表的建立 ▪ 尾插法过程：指针变量q始终指向尾结点，p指针 开辟单元，生成结点。 ① q->next=p; ② q=p; head a1 …… an ^ k ^ p q ① ① 新结点
一、第二章线性表解析 (1)链表的建立 头插法算法思路：从一个空表开始，重复读入 数据，生成新结点，将读入数据存放在新结点 的数据域中，然后将新结点插入到当前链表的 表头上，直到读入结束标志为止。 头插法的步骤，请查看“4-头插法建立单链表 swf"。 www.open.ha.cn
www.open.ha.cn 一、第二章线性表解析 ▪ （1）链表的建立 ▪ 头插法算法思路：从一个空表开始，重复读入 数据，生成新结点，将读入数据存放在新结点 的数据域中，然后将新结点插入到当前链表的 表头上，直到读入结束标志为止。 ▪ 头插法的步骤，请查看“4-头插法建立单链表 .swf”