资源描述：
《03《数据结构》第三讲 线性表(上) (1)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《数据结构》第三讲线性表（上）2009年9月27日周亚建zhouyajian@gmail.comSchoolofComputerScienceandEngineering,BUPTOverviewofLastClass数据结构的概念非数值数据的表示、存储和操作了解抽象数据类型的表示与实现理解算法和算法分析掌握计算语句频度和估算算法时间复杂度的方法2/61本次课程学习目标学习完本次课程，您应该能够掌握下列的知识和技能：线性表的概念：线性表的表示逻辑结构特性线性表的存储：顺序存储结构和链式存储结构线性表的操作：基本
2、操作及算法实现分析顺序存储结构的时间和空间复杂度3/61本章课程内容（第二章线性表）2.1线性表的类型定义2.2线性表的顺序表示和表现2.3线性表的链式表示与实现2.4一元多项式的表示及相加4/61线性表线性表是一种最常用且最简单的线性结构。5/61什么是线性结构简言之，线性结构是一个数据元素的有序（次序）集合。它有四个基本特征：集合中必存在唯一的一个“第第元一元素素”；集合中必存在唯一的一个“最后元素”；除最后元素之外，其它数据元素均有唯一的“后继”；除第一元素之外，其它数据元素均有唯一的“前驱”。注意：这里
3、的“有序”仅指在数据元素之间存在一个“领先”或“落后”的次序关系，而非指数据元素“值”的大小可比性。6/61线性表的类型定义2.1线性表的类型定义2.2线性表的顺序表示和表现2.3线性表的链式表示与实现2.4一元多项式的表示及相加7/61线性表的类型定义线性表（LinearList）：由n（n≧0）个数据元素（结点）a，1a，…，a组成的有限序列。2n其中数据元素的个数n定义为表的长度。（有n-1个有序对）当n=0时称为空表，常常将非空的线性表（n>0）记作：(a，a，…，a)12n这里的数据元素a（1≦i≦n）只是一个
4、抽象的符号，其具体含义i在不同的情况下可以不同。8/61线性表的例子例1、26个英文字母组成的字母表是一个线性表（A，B，C，…，Z）例2、同一花色的13张扑克牌可以构成一个线性表（2，3，4，…，J，Q，K，A）9/61线性表的逻辑特征从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点a，它没有直接前趋，1而仅有一个直接后继a；2有且仅有一个终端结点a，它没有直接后继，而仅有一个直接前n趋a；n-1其余的内部结点a（2≦i≦n-1）都有且仅有一个直接前趋a和一ii-1个直接后继a。i+110/61线
5、性表的类型定义线性表是一种典型的线性结构数据的运算定义在逻辑结构上而运算的具体实现则在存储结构上进行。11/56线性表的类型定义抽象数据类型线性表的定义如下：bo2-1.c,main2-1.cADTList{数据对象：D＝{a
6、a∈ElemSet，i=1,2,...,n,n≥0}ii数据关系：R1＝{
7、a,a∈D,i=2,...,n}i-1ii-1i基本操作：InitList(&L)//{结构初始化}操作结果：构造一个空的线性表L。DestroyList(&L)//{销毁结构}初始条件：线性表L已存在。操作结果：销
8、毁线性表L。12/56线性表的类型定义//{引用型操作}ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中元素个数。PriorElem(L，cur_e，&pre_e)初始条件：线性表L已存在。操作结果：若cur_e是L中的数据元素，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。NextElem(L,cur_e,&next_e)初始条件：线性表L已存在。操作结果：若cur_e是L中的数据元素
9、，则用next_e返回它的后继，否则操13/56作失败，next_e无定义。线性表的类型定义//{引用型操作}GetElem(L,i,&e)初始条件：线性表L已存在，1≤i≤LengthList(L)。操作结果：用e返回L中第i个元素的值。LocateElem(L,e,compare())初始条件：线性表L已存在，compare()是元素判定函数。操作结果：返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。ListTraverse(L,visit())初始条件：线性表L已存在，viit(
10、isit()为元素的访问函数。操作结果：依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。14/56线性表的类型定义容易看出以上7个操作的结果都没有改变线性表中的数据元素和数据元素之间的关系，因此它们都是“引用型”的操作，函数中的“
