第二章线性表
第 1 页
学习的义 线性表是最简单、也是最基本的一种线性数据结 构。其存储表示法主要有两种:顺序存储结构和链 式存储结构。这一部分内容和方法掌握了,有助于 理解和掌握后续章节的内容,如栈队列串是特殊的 线性表,数组和广义表是线性表的扩展;有助于理 解和掌握树和图等复杂的数据结构存储结构和图等 复杂结构的操作算法,因为树和图的存储结构大多 或是这两种存储结构的扩充,或是它们的组合,因 此这一章的内容非常重要,同学们要很好地学习理 解和掌握
第 2 页 线性表是最简单、也是最基本的一种线性数据结 构。其存储表示法主要有两种：顺序存储结构和链 式存储结构。这一部分内容和方法掌握了，有助于 理解和掌握后续章节的内容，如栈队列串是特殊的 线性表，数组和广义表是线性表的扩展；有助于理 解和掌握树和图等复杂的数据结构 存储结构和图等 复杂结构的操作算法，因为树和图的存储结构大多 或是这两种存储结构的扩充，或是它们的组合，因 此这一章的内容非常重要，同学们要很好地学习理 解和掌握。 ◆学习的意义：
团今主墨胸容 2.1线性表的类型定义 2.4有序表 2.1.1线性表的定义 2.5顺序表和链表的综合比较 2.1.2线性表的基本操作 2.2线性表的顺序表示和实现 221顺序表—线性表的顺序存储表示 222顺序表中基本操作的实现 223顺序表其他算法举例 2.3线性表的链式表示和实现 23.1单链表和指针 232单链表的基本操作 233单链表的其他基本操作 234循环链表 23.5双向链表
第 3 页 2.1 线性表的类型定义 2.4 有序表 2.1.1 线性表的定义 2.5 顺序表和链表的综合比较 2.1.2 线性表的基本操作 2.2 线性表的顺序表示和实现 2.2.1 顺序表——线性表的顺序存储表示 2.2.2 顺序表中基本操作的实现 2.2.3 顺序表其他算法举例 2.3 线性表的链式表示和实现 2.3.1 单链表和指针 2.3.2 单链表的基本操作 2.3.3 单链表的其他基本操作 2.3.4 循环链表 2.3.5 双向链表 ◆主要内容：
2.1线性表的类型定义 21.1线性表的定义 线性表是n个类型相同数据元素的有限序列,表中相邻的数据元 素之间存在“序偶”关系。通常记作(a1a2,a3 a 例1、数学中的数列(11,13,15,17,19,21) 例2、英文字母表(A,B,C,D,E..Z)。 例3、某单位的电话号码簿。 姓名电话号码 蔡颖 63214444 陈红 63217777 刘建平 63216666 王小林 63218888 张力 63215555
第 4 页 线性表是n 个类型相同数据元素的有限序列，表中相邻的数据元 素之间存在“序偶”关系。通常记作（a1 , a2 , a3 , …, an ）。 姓名 电话号码 蔡颖 63214444 陈红 63217777 刘建平 63216666 王小林 63218888 张力 63215555 ... 2. 1 线性表的类型定义 例1、数学中的数列（11，13，15，17，19，21） 例2、英文字母表（A, B, C, D, E Z ）。 例3、某单位的电话号码簿。 2.1.1 线性表的定义
21线性表的定义 特性:设A=(an,a2…,a,,11,…,an)是一线性表 线性表的数据元素可以是各种各样的,但同一线性表中的元素必须是同一 类型的; >在表中a1领先于a;,a1领先于a1,称a1是a1的直接前驱,a1是a1的 直 接后继; >在线性表中,除第一个元素和最后一个元素之外,其他元素都有且仅有 个直接前驱,有且仅有一个直接后继,具有这种结构特征的数据结构 称为线性结构。线性表是一种线性数据结构; >线性表中元素的个数n称为线性表的长度,n=0时称为空表; >a是线性表的第i个元素,称i为数据元素1的序号,每一个元素在线性表 甲的位置,仅取决于它的序号
第 5 页 2.1.1 线性表的定义 特性：设 A=（a1 , a2 , ... , ai -1 , ai , ai+1, …, an ）是一线性表 ➢ 线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一 类型的； ➢ 在表中ai-1 领先于ai ，ai领先于ai+1，称ai-1是ai 的直接前驱，ai+1是ai的 直 接后继； ➢ 在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有 一个直接前驱，有且仅有一个直接后继，具有这种结构特征的数据结构 称为线性结构。线性表是一种线性数据结构； ➢ 线性表中元素的个数n 称为线性表的长度，n=0 时称为空表； ➢ ai是线性表的第i 个元素，称i 为数据元素ai的序号，每一个元素在线性表 中的位置，仅取决于它的序号；