数据结构c版第2章线性表课件

1、1第第2章章 线性表线性表 线性表的逻辑结构线性表的逻辑结构 线性表的顺序存储及实现线性表的顺序存储及实现 线性表的链接存储及实现线性表的链接存储及实现 顺序表和单链表的比较顺序表和单链表的比较 线性表的其他存储及实现线性表的其他存储及实现本章的基本内容是：本章的基本内容是：22.1 线性表的逻辑结构线性表的逻辑结构学生成绩登记表学生成绩登记表姓姓 名名英语英语数据结构数据结构高数高数学号学号丁一丁一9678870101李二李二8790780102张三张三6786860103孙红孙红6981960104王冬王冬8774660105数据元素之间的关系是什么？数据元素之间的关系是什么？3线性表：线

2、性表：简称表，是简称表，是n n（n n00）个具有）个具有相同类型相同类型的数的数据元素的据元素的有限序列有限序列。线性表的长度：线性表的长度：线性表中数据元素的个数。线性表中数据元素的个数。空表：空表：长度等于零的线性表，记为：长度等于零的线性表，记为：L L=( )=( )。非空表非空表记为：记为：L L（a a1 1, , a a2 2 , , , , a ai i-1-1, , a ai i , , , , a an n) )线性表的定义线性表的定义其中，其中，a ai i（11i in n）称为数据元素；）称为数据元素；下角标下角标 i i 表示该元素在线性表中的位置或序号，称元素

3、表示该元素在线性表中的位置或序号，称元素 a ai i位于表的第位于表的第 i i 个位置，或称个位置，或称 a ai i是表中的第是表中的第 i i 个元素。个元素。4a1a3a4ana2线性表的图形表示线性表的图形表示线性表（线性表（a a1 1, , a a2 2 , , , , a ai i-1-1, , a ai i , , , , a an n) )的图形表的图形表示如下：示如下：5a1a3a4ana2线性表的特性线性表的特性1.1.有限性：线性表中数据元素的个数是有穷的。有限性：线性表中数据元素的个数是有穷的。2.2.相同性：线性表中数据元素的类型是同一的。相同性：线性表中数据元

4、素的类型是同一的。3.3.顺序性：线性表中相邻的数据元素顺序性：线性表中相邻的数据元素a ai i-1-1和和a ai i之间存之间存在序偶关系在序偶关系( (a ai i-1-1, , a ai i) )，即，即a ai i-1-1是是a ai i的前驱，的前驱， a ai i是是a ai i-1-1的后继；的后继；a a1 1 无前驱，无前驱，a an n无后继，其它每个元素有且仅无后继，其它每个元素有且仅有一个前驱和一个后继。有一个前驱和一个后继。 6线性表的抽象数据类型定义线性表的抽象数据类型定义见教材见教材P50P50线性表线性表ADTADT的几点说明的几点说明（1 1）对于不同的应

5、用，线性表的基本操作是不同的；）对于不同的应用，线性表的基本操作是不同的；（2 2）复杂的操作可以通过基本操作的组合来实现；）复杂的操作可以通过基本操作的组合来实现；（3 3）对不同的应用，操作的接口可能不同。）对不同的应用，操作的接口可能不同。7顺序表顺序表线性表的顺序存储结构线性表的顺序存储结构例：（例：（34, 23, 67, 43）存储要点存储要点用一段地址用一段地址连续连续的存储单元的存储单元依次依次存储线性表中的数据元素存储线性表中的数据元素34236743 42.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现8例：（例：（34, 23, 67, 4334, 23, 67

6、, 43）3434232367674343 4 4如何实现顺序表的内存分配？如何实现顺序表的内存分配？顺序表顺序表一维数组一维数组9顺序表顺序表线性表的顺序存储结构线性表的顺序存储结构例：（例：（34, 23, 67, 4334, 23, 67, 43）3434232367674343存储空间的起始位置存储空间的起始位置 4 4用什么属性来描述顺序表？用什么属性来描述顺序表？顺序表的容量（最大长度）顺序表的容量（最大长度）顺序表的当前长度顺序表的当前长度10如何描述顺序存储结构需要的三个属性？如何描述顺序存储结构需要的三个属性？ 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai a

7、n 空闲空闲表的长度表的长度一般情况下，一般情况下，( (a a1 1，a a2 2，, , a ai i-1-1，a ai i , , , , a an n) )的顺序存的顺序存储：储：(1)(1)存储空间的起始位置：数组名存储空间的起始位置：数组名 datadata(2)(2)顺序表的存储容量顺序表的存储容量: :数组长度数组长度MaxSizeMaxSize(3)(3)顺序表的当前长度：顺序表的当前长度：lengthlengthlength11区分：区分：“数组的长度数组的长度”和和“线性表的长度线性表的长度” 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空闲空闲表

8、的长度表的长度一般情况下，一般情况下，( (a a1 1，a a2 2，, , a ai i-1-1，a ai i , , , , a an n) )的顺序存的顺序存储：储：(1)(1)前者确定不变前者确定不变 后者变化后者变化(2)(2)线性表的长度线性表的长度=数组的长度数组的长度线性表的长度线性表的长度lengthlength数组的长度数组的长度MaxSizeMaxSize12如何求得任意元素的存储地址？从而读取任如何求得任意元素的存储地址？从而读取任意数据元素？意数据元素？ 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空闲空闲 表的长度表的长度一般情况下，一般情

9、况下，( (a a1 1，a a2 2，, , a ai i-1-1，a ai i , , , , a an n) )的顺序存的顺序存储：储：cLoc(ai)Loc(a1)13复习存储地址有关的内容复习存储地址有关的内容地址地址：存储器中每个存储单元都有自己的编号，这个：存储器中每个存储单元都有自己的编号，这个编号称为地址。编号称为地址。相对地址相对地址( (偏移地址）：选定一个参考单元作为基准单偏移地址）：选定一个参考单元作为基准单元（称为基地址，一般将基地址视为元（称为基地址，一般将基地址视为0 0），），任一存储单任一存储单元到基地址之间的单元数元到基地址之间的单元数，称为该存储单元相对

10、于基，称为该存储单元相对于基地址的相对地址。地址的相对地址。绝对地址绝对地址：任一存储单元的偏移地址，加上它的基准：任一存储单元的偏移地址，加上它的基准单元的绝对地址，即为该单元的绝对地址。单元的绝对地址，即为该单元的绝对地址。14复习存储地址有关的内容复习存储地址有关的内容在顺序表中，任意元素的在顺序表中，任意元素的相对地址相对地址就是该元素就是该元素在数组中的在数组中的下标下标，任意元素的绝对地址一般用，任意元素的绝对地址一般用loc(aloc(ai i) )表示。表示。15 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空闲空闲表的长度表的长度一般情况下，一般情况下

11、，( (a a1 1，a a2 2，, , a ai i-1-1，a ai i , , , , a an n) )的顺序存的顺序存储：储：cLoc(ai)Loc(a1)Loc(Loc(a ai i)=Loc()=Loc(a a1 1) + () + (i i -1)-1)c c计算任意元素的存储地址的时间是相等的，具计算任意元素的存储地址的时间是相等的，具有这一特点的存储结构称为有这一特点的存储结构称为随机存取随机存取结构结构16区分：存储结构和存取结构区分：存储结构和存取结构存储结构存储结构是数据及其逻辑结构在计算机中的表示是数据及其逻辑结构在计算机中的表示存取结构存取结构是在某种逻辑结构上

12、对查找操作时间性是在某种逻辑结构上对查找操作时间性能的描述能的描述“顺序表是一种随机存取的存储结构顺序表是一种随机存取的存储结构”的含义的含义为：为：在顺序表这种存储结构上进行查找操作，其时间在顺序表这种存储结构上进行查找操作，其时间性能为性能为O(1)O(1)。17 顺序表类的声明顺序表类的声明const int MaxSize=100; template /模板类模板类class SeqList public: SeqList( ) ; /构造函数构造函数 SeqList(T a , int n); SeqList( ) ; /析构函数析构函数 int Length( ); T Get(i

13、nt i); int Locate(T x ); void Insert(int i, T x); T Delete(int i); 18 顺序表类的声明顺序表类的声明 private: T dataMaxSize; int length;19template /模板的标志模板的标志T Max(T x, T y) return x=y? x: y; int i=Max(1, 2); double x=Max(1.2, 2.5); 函数函数Max Max 要返回两个参数中的最大者，如何定义要返回两个参数中的最大者，如何定义一个具有通用功能的函数一个具有通用功能的函数MaxMax，支持不同类型的，

14、支持不同类型的参数和返回值？参数和返回值？ 20构造函数的作用是初始化一个对象的成员变量。构造函数的作用是初始化一个对象的成员变量。构造函数的特点构造函数的特点: :1. 1. 构造函数必须与类名相同；构造函数必须与类名相同；2. 2. 必须声明为类的公有成员函数；必须声明为类的公有成员函数；3. 3. 不可以有返回值也不得指明返回类型；不可以有返回值也不得指明返回类型；4. 4. 构造函数可以重载。构造函数可以重载。21构造函数的作用构造函数的作用是什么是什么（W Whathat）？）？什么时候什么时候（W Whenhen）调用？）调用？由由谁谁（W Whoho）来调用？）来调用？WhatW

15、hat: :构造函数为成员变量分配存储空间并初始化构造函数为成员变量分配存储空间并初始化WhenWhen: :在声明一个对象变量是该类的一个实例时调用在声明一个对象变量是该类的一个实例时调用WhoWho: :由系统根据实参自动调用相应的构造函数由系统根据实参自动调用相应的构造函数22操作接口操作接口SeqList( )SeqList( )：创建一个空的顺序表：创建一个空的顺序表 算法描述：算法描述：SeqList:SeqList( )SeqList:SeqList( ) length=0; length=0; 顺序表的实现顺序表的实现无参构造函数无参构造函数 datadatalengthlen

16、gth0 023操作接口操作接口SeqList(T a , int n)SeqList(T a , int n)：创建一个：创建一个长度为长度为n n的顺序表的顺序表 顺序表的实现顺序表的实现有参构造函数有参构造函数顺序表顺序表 数组数组a35122433425351224334224template SeqList:SeqList(T a , int n) if (nMaxSize) throw 参数非法; for (i=0; i=MaxSizelength=MaxSize合理的插入位置：合理的插入位置：1ilength+11ilength+1（i i指的是指的是元素的序号元素的序号）顺序表

17、的实现顺序表的实现插入插入 4 43535121224244242a a1 1a a2 2a a3 3a a4 40 1 2 3 40 1 2 3 442422424121233335 5什么时候不能插入？什么时候不能插入？注意边界条件注意边界条件301. 1. 如果表满了，则抛出如果表满了，则抛出上溢上溢异常异常; ;2. 2. 如果元素的插入位置不合理，则抛出如果元素的插入位置不合理，则抛出位置位置异常异常; ;3. 3. 将最后一个元素至第将最后一个元素至第i i个元素分别向后移动个元素分别向后移动一个位置；一个位置；4. 4. 将元素将元素x x填入位置填入位置i i处；处；5. 5.

18、 表长加表长加1 1；算法描述算法描述伪代码伪代码顺序表的实现顺序表的实现插入插入31顺序表的实现顺序表的实现插入插入1 1 如果顺序表已满，如果顺序表已满，抛出上溢异常抛出上溢异常2 2 如果元素插入位如果元素插入位置不存在，抛出置不存在，抛出位置异常位置异常3 3 将最后一个元素将最后一个元素至第至第i i个元素（个元素（i i为插入位置）向为插入位置）向后移动一个位置后移动一个位置4 4 将元素插入到将元素插入到i i位位置置5 5 将顺序表的长度将顺序表的长度增增1 1template void SeqList:Insert(int i, T x)int j; if (length=M

19、axSize) throw 上溢上溢; if (ilength+1) throw 位置位置; for (j=length; j=i; j-) dataj=dataj-1; datai-1=x; length+;基本语句基本语句？32顺序表的实现顺序表的实现插入插入最好最好情况（情况（i i= =n n+1+1）：）： 基本语句执行基本语句执行0 0次，时间复杂度为次，时间复杂度为O O(1)(1)。最坏最坏情况（情况（i i=1=1）：）： 基本语句执行基本语句执行n n次，时间复杂度为次，时间复杂度为O O( (n n) )。平均平均情况（情况（11i in n+1+1）：）： 时间复杂度为

20、时间复杂度为O O( (n n) )。时间性能分析时间性能分析+ +- -+ += =1 11 1)=)=1 1( (n ni ii ii in np p+ +- -+ + += =1 11 1)=)=1 1( (1 11 1n ni ii in nn n2 2n n= =O O( (n n) )33操作接口操作接口T Delete(int i):将线性表中的第将线性表中的第i（1 i n)个个元素删除，并返回被删除元素的值元素删除，并返回被删除元素的值删除前：删除前：(a1, , ai-1,ai,ai+1,an)删除后：删除后：(a1,ai-1,ai+1, ,an) 顺序表的实现顺序表的实现

21、删删 除除a ai i-1-1和和a ai i之间的逻辑关系发生了变化之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化存储位置要反映这个变化34顺序表的实现顺序表的实现删删 除除例：（例：（35, 33, 12, 24, 4235, 33, 12, 24, 42），删除），删除i=2i=2的数据的数据 元素。元素。仿照顺序表的插入操作，完成：仿照顺序表的插入操作，完成：1. 1. 分析边界条件；分析边界条件；2. 2. 分别给出伪代码和分别给出伪代码和C+C+描述的算法；描述的算法；3. 3. 分析时间复杂度。分析时间复杂度。 5

22、53535a a1 1a a2 2a a3 3a a4 40 1 2 3 40 1 2 3 442422424121233334 4a a5 5121224244242351.1.如果顺序表已空，抛出下溢异常如果顺序表已空，抛出下溢异常2.2.如果元素删除位置不存在，抛出位置异常如果元素删除位置不存在，抛出位置异常3.3.取出被删除的元素取出被删除的元素4.4.将将下标下标为为i i，i+1n-1i+1n-1的元素依次移到的元素依次移到i-i-1,i,n-21,i,n-2的位置的位置5.5.将顺序表的长度减将顺序表的长度减1 1，返回被删除的元素，返回被删除的元素算法描述算法描述伪代码伪代码顺

23、序表的实现顺序表的实现删除删除36顺序表的实现顺序表的实现删除删除1.1.如果顺序表已空，如果顺序表已空，抛出下溢异常抛出下溢异常2.2.如果元素删除位置如果元素删除位置不存在，抛出位置不存在，抛出位置异常异常3.3.取出被删除的元素取出被删除的元素4.4.将将下标下标为为i i，i+1n-1i+1n-1的元素一的元素一次移到次移到i-1,i,n-i-1,i,n-2 2的位置的位置5.5.将顺序表的长度减将顺序表的长度减1 1，返回被删除的，返回被删除的元素元素template T SeqList:Delete(int i)int x,j; if (length=0) throw 下溢下溢;

24、if (ilength) throw 位置位置; x=datai-1; for (j=i; jlength; j+) dataj-1=dataj; length-; return x;基本语句基本语句？37顺序表的实现顺序表的实现删除删除最好最好情况（情况（i i= =n n）：）： 基本语句执行基本语句执行0 0次，时间复杂度为次，时间复杂度为O O(1)(1)。最坏最坏情况（情况（i i=1=1）：）： 基本语句执行基本语句执行n-1n-1次，时间复杂度为次，时间复杂度为O O( (n n) )。平均平均情况（情况（11i in n）：）： 时间复杂度为时间复杂度为O O( (n n) )

25、。时间性能分析时间性能分析1111()()2nniiinp n in in 38顺序表中的查找操作顺序表中的查找操作两种查找方法两种查找方法按按位置位置查找，即查找指定位置上查找，即查找指定位置上的元素的元素按按值值查找，即查找指定的值在顺查找，即查找指定的值在顺序表中的位置序表中的位置39顺序表的实现顺序表的实现按位查找按位查找操作接口操作接口T Get(int i):查找第查找第i i个元素并返回其个元素并返回其值值 0 0 i i-2 -2 i i-1 -1 n n-1 Max-1 -1 Max-1 a a1 1a ai i-1-1 a ai i a an n 空闲空闲 n n算法描述：算法描述：template T SeqList:Get(int i) if (ilength) throw 查找位置非法查找位置非法; else return datai-1;时间复杂度？时间复杂度？O(1)40顺序表的实现顺序表的实现按值查找按值查找操作接口操作接口int Locate(T x ):查找值为查找值为x x的元素并返回其的元素并返回其序号序号 535a1a2a3a40 1