第二章线性表
第 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的序号，每一个元素在线性表 中的位置，仅取决于它的序号；
2.1线性表的定义 线性表的其他表示方式 1、二元组表示 L=,其中:D={a,a2,a3, S={R}R={,≤a2,a3>,…} 2、图形表示 a1 a2 ai ai ai. an 顶点:表示数据 边:表示是数据间的顺序结构关系
第 6 页 2.1.1 线性表的定义 1、 二元组表示 L = ，其中：D = { a1， a2， a3，, ...， an } S = {R} R = { , , … } 线性表的其他表示方式: 2、图形表示 顶点：表示数据 边：表示是数据间的顺序结构关系 a1 a2 ai-1 ai ai+1 an
212线性表的基本操作 1.初始化线性表 L InitLis&L) 2.销毁线性表 L Destory List(&L) 3.清空线性表 L ClearlList(&L) 4.求线性表L的长度 ListLength(L) 5判断线性表L是否为空 ListEmpty(L) 6获取线性表L中的某个数据元素内容 GetElen(Ll&e) 7.检索值为e的数据元素 LocateELem(Le) 8.返回线性表L中cur_e的直接前驱元素 Prior elem( Lcur e&pree) 9.返回线性表L中cure的直接后继元素 ExteEm(L,cure,& next e) 10.在线性表L中插入一个数据元素 ListInsert(&Lle) (sis ListLength (L)+1) 11.删除线性表L中第个数据元素 List Delete(&L,&e) sis ListLength(L) 12输出线性表L中的每个数据元素 ListTraverse(L)
第 7 页 2.1.2 线性表的基本操作 1. 初始化线性表L InitList(&L) 2. 销毁线性表L DestoryList(&L) 3. 清空线性表L ClearList(&L) 4. 求线性表L的长度 ListLength(L) 5. 判断线性表L是否为空 ListEmpty(L) 6. 获取线性表L中的某个数据元素内容 GetElem(L,i,&e) 7. 检索值为e的数据元素 LocateELem(L,e) 8. 返回线性表L中cur_e的直接前驱元素 PriorElem(L,cur_e,&pre_e) 9. 返回线性表L中cur_e的直接后继元素 NextElem(L,cur_e,&next_e) 10. 在线性表L中插入一个数据元素 ListInsert(&L,i,e) (1≦i≦ ListLength(L)+1) 11. 删除线性表L中第i个数据元素 ListDelete(&L,i,&e) (1≦i≦ ListLength(L)) 12. 输出线性表L中的每个数据元素 ListTraverse(L)
212线性表的基本操作 说明: 1、上面列出的操作,只是线性表的一些常用 的基本操作; 2、不同的应用,基本操作可能是不同的; 3、线性表的复杂操作可通过基本操作实现;
第 8 页 2.1.2 线性表的基本操作 说明: 1、上面列出的操作，只是线性表的一些常用 的基本操作； 2、不同的应用，基本操作可能是不同的； 3、线性表的复杂操作可通过基本操作实现；
212线性表的基本操作 【例2-1】假设线性表L=(2356,8976,18)i=3x=56y=88, 则对L的一组操作及结果如下 ◆ ListLength(L); ∥果为5 ◆ GetElem(L,j,e) ∥e的值为89 ◆ Priorelem(L,x,&pre_x)/pex的值为23 ◆ Nextelem(L,x,& next x)∥/ next x的值为89 ◆ Locateelem(L1,x) ∥结果为2 ◆ ListInser(&L,iy)W所得结果为(23,56,88,89,76,18) ◆ ListDelete(&L,i+1,&e)∥所得结果为(23,56,.88,76,18) e的值为89
第 9 页 2.1.2 线性表的基本操作 【例2-1 】假设线性表L=(23,56,89,76,18),i=3,x=56,y=88, 则对L的一组操作及结果如下： ◆ListLength(L); ◆GetElem(L,i,e) ◆PriorElem(L,x,&pre_x) ◆NextElem(L,x,&next_x) ◆LocateElem(L,x) ◆ListInsert(&L,i,y) ◆ListDelete(&L,i+1,&e) //结果为5 //e的值为89 //pre_x的值为23 //next_x的值为89 //结果为2 //所得结果为(23,56,88,89,76,18) //所得结果为(23,56,88,76,18) e的值为89
212线性表的基本操作 【例2-2】利用两个线性表La和Lb分别表示两个集合A和 B,现要求一个新的集合A=AUB。 【分析】这个问题相当于对线性表作如下操作: 扩大线性表La,将存在于线性表Lb中而不存在于线性表La中 的数据元素插入到线性表La中去。 【具体步骤】 (1)从线性表Lb中取得一个数据元素; (2)依该数据元素的值在线性表La中进行查访; (3)若线性表La中不存在和其值相同的数据元素,则将从Lb中 删除的这个数据元素插入到线性表La中; (4)重复以上操作直至Lb为空表
第 10 页 2.1.2 线性表的基本操作 【例2-2 】利用两个线性表La和Lb分别表示两个集合A和 B，现要求一个新的集合A=A∪B。 【分析 】这个问题相当于对线性表作如下操作： 扩大线性表La，将存在于线性表Lb中而不存在于线性表La中 的数据元素插入到线性表La中去。 【具体步骤 】 （1）从线性表Lb中取得一个数据元素； （2）依该数据元素的值在线性表La中进行查访； （3）若线性表La中不存在和其值相同的数据元素，则将从Lb中 删除的这个数据元素插入到线性表La中； （4）重复以上操作直至Lb为空表