T2-线性表(顺序表)

顺序表第二章：线性表主讲：周翔回顾请简述一下你对数据结构的理解请思考：在设计一个算法时需要考虑到哪些因素预习检查请概括一下线性表的概念请描述一下线性表的插入与删除操作本章目标3约瑟夫环重点了解掌握2线性的概念线性表的顺序存储线性表的链式存储1什么是线性表主要学习内容：线性表的概念及运算（逻辑结构）

线性表的顺序存储（物理结构）

线性表的链式存储（物理结构）一元多项式的表示及相加（应用）什么是线性表什么是线性表？线性表的定义线性结构是最简单、最常用的一种数据结构。特点：除第一个元素无直接前驱、最后一个元素无直接后继外，集合中其它每个数据元素均有惟一的直接前驱和惟一的直接后继。同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数有序性：线性表中相邻数据元素之间存在着序偶关系<ai,ai+1>线性表是一种具有线性结构的抽象数据类型。线性表的定义线性表：用数据元素的有限序列表示（a1,a2,…ai-1，ai,ai＋1

，…,an）n=0时称为数据元素线性起点ai的直接前趋ai的直接后继空表线性终点下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长线性表的定义a1a2a3a4a5定义：n(n≥0)个类型相同的数据元素的有限序列。n>0时，第一个元素无直接前驱，最后一个元素无直接后继，其余的每个数据元素只有一个直接前驱和一个直接后继。n=0时，为空表。表长：表中元素的个数n。表中元素类型相同。

线性表的逻辑结构图为线性表的定义线性表的逻辑特征线性表是一种最简单的数据结构，它有如下几个特征：（1）线性表中有且只有一个开始结点（头结点），这个开始结点没有前驱结点；（2）线性表中有且只有一个末尾结点（尾结点），这个末尾结点没有后继结点；（3）除去开始结点与末尾结点，其它结点都有一个前驱结点和一个后继结点。线性表的定义ADTLinearList{ 数据元素：D={ai|ai∈D0,i=1,2,…,n,n≥0,D0为某一数据对象} 数据关系：S={<ai,ai+1>|ai,ai+1∈D0，i=1,2,…,n-1｝ 基本操作： （1）InitList（L）将L初始化为空表。 （2）DestroyList(L)将L销毁。 （3）ClearList(L)将表L置为空表。

………}ADTLinearList线性表的抽象数据类型定义线性表的物理结构顺序存储结构顺序表非顺序存储结构（链式存储）单链表循环链表双向链表线性表的物理结构不管哪种存储方式，它们的结构都有如下特点：均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一个线性表来说，数据元素必须具有相同的数据类型和长度。有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元素之间的相对位置是线性的，即存在唯一的“第一个”和“最后一个”数据元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素（直接前驱），后面均只有一个数据元素（直接后继）。顺序表的定义顺序存储原理是什么？顺序表的定义所谓顺序存储，就是在存储器中分配一段连续的存储空间，逻辑上相邻的数据元素，其物理存储地址也是相邻的。如图所示的线性表中，d和b的物理地址为连续的0x001和0x002，其逻辑编号为连续的0和1。顺序表的定义存储地址

内存空间状态

逻辑地址

Loc(a1)a11Loc(a1)+(2-1)ka2

2………loc(a1)+(i-1)kai

i………loc(a1)+(n-1)kan

n...

loc(a1)+(maxlen-1)k顺序存储结构示意图空闲顺序表的定义存储地址

内存空间状态

逻辑地址

假设为1000‘e’01001‘g’11002‘r’21003‘s’31004‘n’41005‘k’5空闲顺序表的定义实际应用中应根据实际需要定义表中元素的数据类型，如int、char、float或是一种结构类型注意区分元素的序号和数组的下标，如a1的序号为1，而其对应的数组下标为0ADTSeqList{maxsize

100//线性表可能达到的最大长度ElemType

elem[maxsize] //线性表占用的数组空间int

last//记录线性表中最后一个元素在数组elem[]中的位置（下标值），空表置为-1}ADTSeqList102030405060elem0123456789last顺序表的基本操作基本操作初始化查找插入取值删除15432顺序表的基本操作——查找操作查找操作——两种基本查找运算：按序号查找GetData(L,i)：要求查找线性表L中第i个数据元素按内容查找Locate(L,e)：要求查找线性表L中与给定值e相等的数据元素若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如-1。顺序表的基本操作——查找操作253457

164809

012345tablei253457

164809

i253457

164809

i253457

164809

i查找成功i=4查找数字16顺序表的基本操作——查找操作2534571648

01234tablei2534571648

i2534571648

i2534571648

i2534571648

i查找失败i=-1查找数字50顺序表的基本操作——插入操作已知，线性表(25,34,57,16,48,09)，需在第3个元素之前插入一个元素“21”需要将第6个位置到第3个位置的元素依次后移一个位置，然后将“21”插入到第3个位置顺序表的基本操作——插入操作最好情况：表尾（i=L->last+2）插入元素不需要移动元素，直接在表尾插入最坏情况：在表头（i=1）插入元素表中所有元素都必须依次后移一个位置（n个）平均移动元素个数最坏（平均）时间复杂度为O(n)顺序表的基本操作——删除操作已知，线性表(25,34,57,16,48,09)，将第3个元素删除，顺序表的基本操作——删除操作最好情况：删除表尾（i=L->last+1）元素不需要移动元素，仅将表长度减1最坏情况：删除表头（i=1）元素表中余下元素都必须依次前移一个位置(n-1个)平均移动元素个数最坏（平均）时间复杂度为O(n)顺序表的基本操作查找、插入、删除算法的平均时间复杂度为：O(n)显然，顺序表的空间复杂度S(n)=O(1)（没有占用辅助空间）顺序表的基本操作——合并操作0821254962下标:0

1

2

3

4

0

1

2

3

4

5LA08LC16212537495462728290163754728290LB下标:

0

1

2

3

4

5

6

7

8

9

10

已知

：有两个顺序表LA和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个顺序表LC，要求LC也是非递减有序排列顺序表的基本操作——合并操作算法思想：设表LC是一个空表设两个指针i、j分别指向表LA和LB中的元素LB的元素小（LA.elem[i]>LB.elem[j]）：将LB.elem[j]插入到表LC中LA的元素小（LA.elem[i]≤LB.elem[j]）：将LA.elem[i]插入到表LC中如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中顺序表的基本操作——合并操作0821254962下标:0

1

2

3

4

0

1

2

3

4

5LA08<1608LCij21>161621<372125<372549>373749<544962>545462<7262处理剩余元素728290163754728290LBK下标:

0

1

2

3

4

5

6

7

8

9

10

顺序表的特点顺序表（顺序存储结构）的特点利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等顺序表的优缺点顺序表（顺序存储结构）的优点和缺点优点：无需为表示结点间的逻辑关系而增加额外