数据结构线性表

《数据结构线性表》由会员分享，可在线阅读，更多相关《数据结构线性表（41页珍藏版）》请在金锄头文库上搜索。

1、上堂课要点回顾上堂课要点回顾? ?数据结构数据结构数据结构数据结构 = = 数据的逻辑结构数据的逻辑结构数据的逻辑结构数据的逻辑结构 + + 数据的存储结构数据的存储结构数据的存储结构数据的存储结构 + + 数据的运算数据的运算数据的运算数据的运算? ?程序程序程序程序 = = 算法算法算法算法 + + 数据结构数据结构数据结构数据结构?算法的时间效率分析算法的时间效率分析时间复杂度时间复杂度数据结构课程内容数据结构课程内容第第第第 二二二二 次次次次 课课课课阅读：朱战立，第阅读：朱战立，第17-26页、页、第第26-29页页练习：练习： 作业作业2Chapter 2 Chapter 2 线

2、性表线性表线性表线性表2.1 线性表抽象数据类型线性表抽象数据类型 2.2 线性表的顺序表示和实现线性表的顺序表示和实现 顺序表顺序表 2.3 线性表的链式表示和实现线性表的链式表示和实现 链表链表 2.4 静态链表（略）静态链表（略） 2.5 应用实例应用实例2.1 2.1 线性表抽象数据类型线性表抽象数据类型什么是线性表？什么是线性表？例例1. 例例2. 例例3. 学生操行等级表学生操行等级表姓名学号性别年龄操行等级张三 李四 王五姓名学号性别年龄操行等级张三 李四 王五 00101 00102 00103女 男 男女 男 男 19 20 20优 良 优优 良 优定义定义: 一个线性表是一

3、个线性表是n(n0) 个相同类型数据元 素的有限序列，可以在该结构中任意位置插入 和删除数据元素。个相同类型数据元 素的有限序列，可以在该结构中任意位置插入 和删除数据元素。 其中，其中，n为线性表的长度，为线性表的长度， n0，为空表；，为空表； n0，非空表，表示为，非空表，表示为 ai，0in-1（ 其中（ 其中ai是是抽象的数据元素抽象的数据元素） 或） 或数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋 ai的直接后继的直接后继下标，下标，是元素的序号， 表示元素在表中的位置是元素的序号， 表示元素在表中的位置n为元素总个 数，即表长为元素总个 数，即表长线性终点线性终点线性

4、表抽象数据类型的定义：线性表抽象数据类型的定义：ADT List 数据元素数据元素： ai，i=0,1,n-1 (n0)，类型为，类型为DataType。 结构结构：对所有的数据元素：对所有的数据元素ai(0in-2)存在次序关系存在次序关系 , a0无前趋，无前趋，an-1无后继。无后继。 逻辑操作逻辑操作：设：设L为为 List 型的线性表型的线性表 ListInitiate(L) /构造一个空的线性表L。 ListLength(L)/返回线性表L中的当前元素个数。 ListInsert(L,i,x)/在线性表L的第i个位置前插入一个值 为x 的新元素，插入成功返回1，失败返回0。 0in

5、，插入后表L的长度为n+1。 ListDelete(L,i,x) /删除线性表L的第i个元素，0in-1， 被删除的元素通过x带回。删除成功返回1，失败返回 0。删除后表L的长度为n-1。 ListGet(L,i,x) /取线性表L中的第i个元素，并由参数x 带回，0in-1。2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现 顺序表顺序表顺序存储结构顺序存储结构定义：用一组地址定义：用一组地址连续连续的存储单元依次存放 线性表中的各个数据元素。的存储单元依次存放 线性表中的各个数据元素。特点：逻辑结构上相邻的元素其物理位置也 相邻。特点：逻辑结构上相邻的元素其物理位置也 相邻。顺序

6、表顺序表（Sequential List）用顺序存储结构存储的线性表简称为顺序表。）用顺序存储结构存储的线性表简称为顺序表。若每个数据元素占若每个数据元素占l个存储单元，则有：个存储单元，则有： Loc(ai)=Loc(a0)+i*l （0in-1）因此，顺序表是一种）因此，顺序表是一种随机存取随机存取的存储结构。的存储结构。存储地址存储地址n1i1 20元素序号元素序号bb+(n-1)b+ib+2b+1an1aia2a1a0内 存内 存则元素则元素ai的地址为：的地址为： Loc(ai)=Loc(a0)+i若每个数据元素 只占一个存储单元，若每个数据元素 只占一个存储单元，顺序表数据类型定义

7、顺序表数据类型定义（借用一维数组）（借用一维数组）#define MaxSize 100/定义顺序表最大元素个数定义顺序表最大元素个数 typedef int DataType；/ 抽象数据元素类型抽象数据元素类型 /DataType类型可根据实际情况而定，这里假设为类型可根据实际情况而定，这里假设为int typedef struct DataType list MaxSize；/存储空间存储空间list用于用于 /存放表元素存放表元素 int size；/顺序表顺序表当前当前数据元素个数数据元素个数n SeqListSeqList ；/顺序表类型定义顺序表类型定义SeqList.h文件实现

8、顺序表数据结构SeqList.h文件实现顺序表数据结构main( ) main( ) SeqListSeqList myListmyList；/创建一个顺序表创建一个顺序表 SeqListSeqList *L= ); 顺序表的初始化顺序表的初始化/时间复杂度：O（1)void ListInitiate（SeqList L） /顺序表的初始化或置顺序表的初始化或置L为空表，即将为空表，即将size置为置为0 L.size=0； main( ) main( ) SeqListSeqList myListmyList； ListInitiate(myListListInitiate(myList);

9、 ); myListmain()LListInitiate()0功能不可实现！功能不可实现！int ListLength（SeqList L） / size是表长，求表长需返回是表长，求表长需返回size return L.size; int ListLength（SeqList *L） / size是表长，求表长需返回是表长，求表长需返回size return L-size; 求顺序表的表长求顺序表的表长/时间复杂度：O（1)或或int ListGet ( SeqList L, int i, DataType *x)/x是输出型参数是输出型参数 if (iL.size-1) /非法位置非法位

10、置 printf(“i错误错误!n”); return 0; *x=L.listi; /通过通过x返回第返回第i个元素个元素 return 1; 取数据元素取数据元素/时间复杂度：O（1) ？O（n）O（1)顺序表的插入（前插）顺序表的插入（前插）顺序表的插入（前插）顺序表的插入（前插）在表中的第在表中的第i个元素之个元素之前前插入一个 新的数据元素插入一个 新的数据元素x，使长度为，使长度为n的线性 表（的线性 表（a0,a1,ai-1,ai,an-1)变成长度 为变成长度 为n+1的线性表 （的线性表 （a0,a1,ai-1,x,ai,an-1)。插入元素前插入元素前size插入元素后插入

11、元素后an-1aia0 ai-1MaxSize-10 1 i-1 ini+1a1sizean-1aia0 ai-1a1i-1MaxSize- -10 1 n-1inx可插入位置：可插入位置：可插入位置：可插入位置：sizean-1aia0 ai-1a1i-1MaxSize- -10 1 n-1in0i sizex所以，插入操作：（所以，插入操作：（1）若）若 in，则非法，返回，则非法，返回0 。（2）表满时（）表满时（size=Maxsize）不能 插入。若）不能 插入。若i=0，表中元素全部后移（特别慢），表中元素全部后移（特别慢）若若i=size，无需移动（特别快）当，无需移动（特别快）

12、当i=size时时插入过程动态演示插入过程动态演示? ?插入算法：插入算法：插入算法：插入算法：int ListInsert(SeqList *L, int i, DataType x) int j; if ( L-size=MaxSize)/若表空间溢出，退出运行若表空间溢出，退出运行 printf(“表已满不能插入！表已满不能插入！n”); return 0; if ( iL-size)/非法位置，退出运行非法位置，退出运行 printf(“i值不合法！值不合法！n”); return 0; for ( j=L-size; ji; j-) L-listj=L-listj-1;/元素后移元素

13、后移 L-listi=x;/插入插入x (L-size)+;/表长加表长加1 return 1; ?插入算法的时间复杂度分析插入算法的时间复杂度分析 元素移动的次数 期望值设在第元素移动的次数 期望值设在第i个元素之前插入一个元素的概率为个元素之前插入一个元素的概率为Pi； 在第； 在第i个元素之前进行插入时，元素的移动次数为：个元素之前进行插入时，元素的移动次数为： n- -1- -i+1=n- -i； 可插入的位置； 可插入的位置i： 0i n ，共有，共有n+1个。 平均移动次数为：个。 平均移动次数为：)(0inpEniiis= =不失一般性，我们可以假定在线性表的任 何位置上插入元素

14、都是等概率的，则不失一般性，我们可以假定在线性表的任 何位置上插入元素都是等概率的，则 Pi= 1/(n+1), 所以，所以，22)0)(1( 11)(110nnn ninnEniis=+=+= =由上式可见，在顺序表中插入一个数据元素， 平均约需移动表中一半元素。若表的长度为由上式可见，在顺序表中插入一个数据元素， 平均约需移动表中一半元素。若表的长度为n，则 插入算法的时间复杂度为，则 插入算法的时间复杂度为O(n)。删除删除线性表的删除运算是使长度为线性表的删除运算是使长度为n的 线性表（的 线性表（a0,a1,ai-1,ai, ai+1,an-1)变成长 度为变成长 度为n-1的线性表

15、（的线性表（a0,a1,ai-1,ai+1,an-1)。size删除元素前an-1aia0 ai-1a1an-2ai+1i-1MaxSize- -10 1 n-2in-1 ni+1size删除元素后an-1ai+1a0 ai-1MaxSize-10 1 i-1 in-1i+1a1n-2ai+2可删除位置：可删除位置：0i size-1所以，删除操作： （所以，删除操作： （1）若）若 isize-1，则 非法，返回，则 非法，返回0 。 （。 （2）若）若size= =0，表空，不能删除，返回，表空，不能删除，返回0。删除过程动态演示删除过程动态演示删除过程动态演示删除过程动态演示? ?删除算法删除算法删除算法删除算法：int ListDelete (SeqList *L, int i, DataType *x) int j; if (L-sizeL-size-1) /非法位置非法位置 printf(“删除位置删除位置i错误错误! n”); return 0; *x=L-listi;