数据结构第二章前半

1、1第二章 线性表2.1 线性表的定义和抽象数据类型线性表的定义和抽象数据类型2.2 线性表的顺序存储结构线性表的顺序存储结构2.4 线性表的链式存储结构线性表的链式存储结构第二章 线性表2.3 线性表应用举例线性表应用举例2.5 线性表操作在单链表上的实现线性表操作在单链表上的实现2第二章 线性表2.1 线性表的定义和抽象数据类型线性表的定义和抽象数据类型 2.1.1 2.1.1 线性表的定义线性表的定义2.1.2 2.1.2 线性表的抽象数据类型线性表的抽象数据类型2.1.3 2.1.3 操作举例操作举例3第二章 线性表线性结构非线性结构顺序存储结构链式存储结构索引结构散列结构 逻辑结构存储

2、结构数据结构线性表广义表堆栈和队列树图2.1.1 线性表的定义 1.1.相关知识回顾相关知识回顾 A=( a1，a2，a3， . . , an ) (1) 当当1in时，时，ai的直接前驱为的直接前驱为ai-1, ai的直接后继为的直接后继为ai+1 。(2) 除了第一个元素与最后一个元素除了第一个元素与最后一个元素,序列中任何一个元序列中任何一个元 素有且仅有一个直接前驱元素素有且仅有一个直接前驱元素,有且仅有一个直有且仅有一个直 接后接后 继元素。继元素。 2 2. .线性关系线性关系除了第一个数据元素与最后那个数据元素外，其余每个元除了第一个数据元素与最后那个数据元素外，其余每个元素有且

3、仅有一个直接前驱元素，有且仅有一个直接后继元素有且仅有一个直接前驱元素，有且仅有一个直接后继元素，数据元素之间存在着一对一的关系，我们将这种逻辑素，数据元素之间存在着一对一的关系，我们将这种逻辑关系称为线性关系。关系称为线性关系。5第二章 线性表 数据元素之间具有的逻辑关系为线性数据元素之间具有的逻辑关系为线性关系的数据元素集合称为关系的数据元素集合称为线性表线性表。 线性表(Linear List)是具有相同特性的数据元素的一个有限序列。 3 3. .线性表的定义线性表的定义6第二章 线性表 线性表的长度：表中元素的个数，用n表示空表：n=0 的线性表 线性表一般表示为： (a 1, a 2

4、, , a i, a i+1, a n) a 1：表头元素；a n：表尾元素 a i是第i个数据元素，i 是在表中的位序; 直接前驱元素是a i-1；直接后继元素a i+1 一个线性表可以用一个标识符来命名，如用A命名线性表，则： A=(a 1, a 2, , a i, a i+1, a n)7第二章 线性表 4 4. .线性表的形式化定义线性表的形式化定义 二元组： linear_list=(A,R) 元素类型ElemType是一种通用数据类型标识符，可以通过typedef语句在使用前将其定义为任一具体类型。如，整数 typedeftypedefintElemType ; 有序表：存在按值的

5、升序或降序排列的字段（有序字段）；不存在则为无序表 A = (a1，a2，a3， . . , an) 数列：数列： ( 25， 12， 78， 34， 100， 88)99001 张张 华华 女女17 99002 李李 军军 男男18 99003 王小明王小明 男男17 99050 刘刘 末末 女女19 学号学号 姓名姓名性别性别年龄年龄其其 他他 a1a2a3 a50 a1 a2 a3 a4 a5 a6 字母表：字母表： ( A， B， C， , X, Y, Z) a1 a2 a3 a24 a25 a26数据文件：数据文件： 一个数据元素一个数据元素是一个整数是一个整数 一个数据元素一个数据

6、元素是一个英文字母是一个英文字母 一个数据元素一个数据元素是一个数据记录是一个数据记录9第二章 线性表2.1.2 线性表的抽象数据类型 由一组数据结构和在该组数据结构由一组数据结构和在该组数据结构上的一组操作所组成上的一组操作所组成抽象数据类型抽象数据类型(Abstract Data Type (Abstract Data Type 简称简称ADT)ADT)10第二章 线性表 数据部分：用标识符L表示一个线性表，可采用顺序、链接、散列等任一方式存储到计算机中，其存储类型用标识符ListType表示 操作部分：对线性表所作的各种操作运算，如插入、删除、求表的长度、判断表是否为空等11第二章 线性

7、表抽象数据类型线性表线性表的定义如下：ADT LinearList is Data Data：一个线性表L(a 1, a 2, , a i, a i+1, a n)当L=( )时为空表空表end LinearListOperationOperation： 操作描述请见后续页操作描述请见后续页12第二章 线性表 void InitList(ListType &L )；操作结果：操作结果：构造一个空的线性表 L。初始化操作初始化操作13第二章 线性表 清除操作清除操作void ClearList(ListType &L )；操作结果：操作结果：清除线性表L中的所有元素，使之成为一个

8、空表。14第二章 线性表int LenthList (ListType &L);初始条件：操作结果：线性表 L 已存在。返回 L 中元素个数，若空则返回0。求长度操作求长度操作15第二章 线性表bool EmptyList (ListType &L);初始条件：操作结果：线性表 L 已存在。若 L 为空表，则返回真(true)，否则返回假(false)。 线性表判空操作线性表判空操作16第二章 线性表ElemType GetList (ListType &L, int pos); 初始条件： 操作结果：线性表 L 已存在，返回L中第pos个元素的值。若pos出界，则打印

9、出错信息（求线性表中某个数据元素）且 1posLengthSize(L)17第二章 线性表void TraverseList (ListType &L);初始条件：操作结果：线性表 L 已存在。按照 L 中元素的逻辑顺序访问每个元素，且每个元素仅被访问一次（遍历线性表）18第二章 线性表bool FindList(ListType &L, ElemType& item)；初始条件：操作结果：线性表 L 已存在，itemitem为给定值查找 L 中值中值与item相等的元素若成功返回真，由item返回该元素的值，否则返回假。（查找函数）19第二章 线性表bool Upda

10、teList (ListType &L, const ElemType& item)；初始条件：操作结果：线性表 L 已存在，itemitem为给定值从L中中查找值值与item相等的元素若成功则用item的值更新该元素的值，并返回真；否则返回假。（更新函数）20第二章 线性表bool InsertList (ListType &L, ElemType& item,int pos);初始条件：操作结果：线性表 L 已存在把item的值插入到L中第pos个位置，若pos=-1，则插入表尾。插入操作后表L 的长度增1。（插入数据元素）21第二章 线性表bool Del

11、eteList (ListType &L, ElemType& item,int pos);初始条件：操作结果：线性表 L 已存在且非空从L中删除满足某种条件的元素，若成功则返回true，否则返回false。删除操作后表L 的长度减1。（删除数据元素）22第二章 线性表 排序操作排序操作void SortList (ListType &L )；操作结果：操作结果：对L中的元素按值的升序重新排列，重排后改变了元素之间的原有逻辑关系，按值的升序建立了新的逻辑关系23第二章 线性表2.1.3 操作举例P50 e.g.线性表 L1=(25,38,19,42,33) , i=2,

12、 x=60, y=42 LenthList(L1) =5 EmptyList (L1) =false GetList (L1,i) =38 InsertList (L1,x,6) = (25,38,19,42,33,60) InsertList (L1,54,1) = (54,25,38,19,42,33,60) DeleteList (L1,y,0) = (54,25,38,19,33,60) DeleteList (L1,y,3) = (54,25,19,33,60) SortList (L1) = (19,25,33,54,60) InsertList (L1,35,0) = (19,2

13、5,33,35,54,60)24第二章 线性表2.2 线性表的顺序存储和操作实现线性表的顺序存储和操作实现 2.2.1 2.2.1 线性表的顺序存储结构线性表的顺序存储结构2.2.2 2.2.2 顺序存储下的线性表操作的实现顺序存储下的线性表操作的实现2.2.3 2.2.3 线性表顺序存储空间的动态分配线性表顺序存储空间的动态分配 2.2.1 线性表的顺序存储结构线性表的顺序存储结构 若假设每个数据元素占用若假设每个数据元素占用k个存储单元，并且已知第一个个存储单元，并且已知第一个元素的存储位置元素的存储位置LOC(a1)，则有，则有 LOC(ai) = LOC(a1)+(i-1) ka1a2

14、a3 and1 d2 d3 dn ( a1，a2，a3， . . , an ) 用一组地址连续的存储单元依次存储线性表中的数用一组地址连续的存储单元依次存储线性表中的数据元素，数据元素之间的逻辑关系通过元素的存储位置据元素，数据元素之间的逻辑关系通过元素的存储位置直接反映直接反映。 一一. 构造原理构造原理26第二章 线性表 线性表的存储结构有顺序、链接、散列等多种方式 顺序存储结构是最简单、最常见的一种 设线性表的元素类型为ElemType，则每个元素所占用存储空间大小为sizeof(ElemType)，整个线性表所占用存储空间的大小为n*sizeof(ElemType)，其中n为线性表的长

15、度27第二章 线性表 线性表的顺序存储结构通常利用数组来实现 设用具有ElemType类型的数组listMaxSize存储线性表 A(a 1, a 2, , a i, a i+1, a n)，且起始存储位置为 list，则第 i 个元素的存储位置为：list + (i-1)* sizeof (ElemType) 数组 list 的下标的上界MaxSize决定了线性表的最大长度28第二章 线性表 用一组地址连续地址连续的存储单元 依次存放依次存放线性表中的数据元素 0 1 i-1 i n-1 线性表的线性表的起始地址起始地址，称作线性表的基地址基地址 a1 a2 ai ai+1 an MaxSi

16、ze-1在程序设计语言中，一维数组的表示：在程序设计语言中，一维数组的表示：Pascal 语言：语言： A1.n A1, A2, Ai, AnC 语言：语言： An A0, A1, Ai, An-1Fortran 语言：语言： An A1, A2, Ai, An 线性表的顺序存储结构的特点线性表的顺序存储结构的特点1. 优点：优点：2. 缺点：缺点：(1) 构造原理简单、直观，易理解。构造原理简单、直观，易理解。(2) 元素的存储地址可以通过一个简单的解析式计算元素的存储地址可以通过一个简单的解析式计算 出来。出来。(1) 存储分配需要事先进行。存储分配需要事先进行。(2) 需要一片地址连续的

17、存储空间。需要一片地址连续的存储空间。(3) 基本操作基本操作(如插入删除如插入删除)的时间效率的时间效率 较低。较低。31第二章 线性表顺序存储结构的程序设计语言描述：顺序存储结构的程序设计语言描述：struct List ; ElemType listMaxsize; / 存储数组 /Maxsize为常量整数为常量整数int size; / 存储线性表的长度32第二章 线性表/动态存储动态存储struct List int MaxSize; ElemType *list;int size; 33第二章 线性表2.2.2 顺序存储下的线性表操作的实现1、初始化线性表：动态分配空间，置为空表v

18、oid InitList (List& L)L.MaxSize = 10;/初始定义为10L.list = new ElemTypeL.MaxSize; if (NULL = L.list) /判断分配空间是否成功exit(1);L.size = 0;/置为空表34第二章 线性表2、删除线性表中所有元素即：只需将其长度置为0void ClearList (List& L)if (L.list != NULL) delete L.list; L.list = NULL;L.MaxSize = 0;L.size = 0;35第二章 线性表3、得到线性表的长度即：返回线性表L的siz

19、e域的值int LenthList (List& L)return L.size ;36第二章 线性表4、检查线性表是否为空即：判断其长度是否为0， “是”返回true，“否”返回false bool EmptyList (List& L)return (L.size = = 0) ;37第二章 线性表5、得到线性表中指定序号的元素即：使用L.listpos-1从L中取出第pos个元素ElemType GetList (List& L, int pos)if (pos L.size)cerr “pos is out range!”endl;exit (1);return

20、 L.listpos-1;38第二章 线性表6、遍历线性表即：依次访问L中list0-listn-1的每一个元素void TraveseList (List& L)for (int i=0; iL.size; i+) coutL.listi ;coutendl;39第二章 线性表7、从线性表中查找具有给定值的第一个元素即：找到 i，使得item = L.listi，则由item返回该元素的整体值，且该函数返回 1bool FindList (List& L, ElemType& item)for (int i=0; iL.size; i+) if (L.listi =

21、=item) item = L.listi; return true; return false;40第二章 线性表8、更新线性表中具有给定值的第一个元素即：找到 i，使得item = L.listi，则用item的值修改该元素的值，且该函数返回 truebool UpdateList (List& L, const ElemType& item)for (int i=0; iL.size; i+) if (L.listi = =item)L.listi item;return true; return false;41第二章 线性表 (7)(8)的算法中，运行时间主要取决于比

22、较元素的次数 最好：第一个元素list0等于待查找或待更新的元素，则仅此一次就结束操作，对应的时间复杂度为O(1) 最坏：最后一个元素listn-1等于待查找或待更新的元素，则需n次比较才结束操作，对应的时间复杂度为O(n)42第二章 线性表 平均：当元素值互不相同，且以平均概率1/n等于待查找或待更新的元素时，则需要比较元素的平均次数为 所以平均情况下对应的时间复杂度为O(n) 若查找失败，即依次同线性表中所有 n 个元素比较后仍找不到与给定值相等的元素，则算法执行return false 语句后结束，其时间复杂度为O(n) 小结：小结：无论查找成功或失败，顺序查找线性表的时间复杂度均为O(n)1112ninin43第二章 线性表9、向线性表中按给定条件插入一个元素当pos=0时，将元素item加到有序表的恰当位置，使其插入后仍然有序。用顺序查找法确定插入的恰当位置。A= (25,36,40,48,55,72,83)插入16，则(16,25,36,40,48,55,72,