数据结构线性表PPT.ppt
线性结构的线性结构的特点特点： 在数据元素的非空有限集合中：在数据元素的非空有限集合中：l存在存在的一个被称作的一个被称作“”的数据元素的数据元素l存在存在的一个被称作的一个被称作“”的数据元素的数据元素l除第一个外，集合中的每个数据元素均除第一个外，集合中的每个数据元素均l除最后一个外，集合中的每个数据元素均除最后一个外，集合中的每个数据元素均2.1 线性表的类型定义线性表的类型定义2.3 线性表类型的实现线性表类型的实现 链式映象链式映象2.4 一元多项式的表示一元多项式的表示2.2 线性表类型的实现线性表类型的实现 顺序映象顺序映象2.5 小结及习题小结及习题l定义定义：一个线性表是：一个线性表是n n个数据元素的个数据元素的有限有限序序列列niaaaa,21如例例1 英文字母表（英文字母表（A,B,C,Z)是一个线性表是一个线性表例例2学号姓名年龄001张三18002李四19数据元素数据元素l特征特征：u元素个数元素个数n(n0) 称为称为表长度，表长度，n=0空表空表,记为（）或记为（）或u1in时时uai的的直接前驱直接前驱是是ai-1，a1无直接前驱无直接前驱uai的的直接后继直接后继是是ai+1，an无直接后继无直接后继u元素同构元素同构（属于同一数据对象（属于同一数据对象)抽象数据类型线性表线性表的定义如下：ADT List 数据对象数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 其中n 为线性表的表长表长; 数据关系数据关系：R1 |ai-1 ,aiD, i=2,.,n 设线性表为设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称称 i 为为 ai 在线性表中的在线性表中的位序位序。 基本操作：基本操作： 结构初始化操作结构初始化操作结构销毁操作结构销毁操作 引用型操作引用型操作 加工型操作加工型操作 ADT List InitList( &L )操作结果：操作结果：构造一个空的线性表L。初始化操作初始化操作 结构销毁操作结构销毁操作DestroyList( &L )初始条件：操作结果：线性表 L 已存在。销毁线性表 L。 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的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。（求数据元素的后继）GetElem( L, i, &e ) 初始条件： 操作结果：线性表L已存在，且 1iLengthList(L)用 e 返回L中第 i 个元素的值。（求线性表中某个数据元素）LocateElem( L, e)初始条件：操作结果：线性表L已存在，e为给定值。返回L中第中第1个个与e相等相等的元素的位序。若这样的元素不存在，则返回值为0。（定位函数） ListTraverse(L, visit( )初始条件：操作结果：线性表L已存在。Visit() 为某个访问函数。依次依次对L的每个元素调用函数visit( )。一旦visit( )失败，则操作失败。（遍历线性表）ClearList( &L )初始条件：操作结果：线性表L已存在。将L重置为空表。（线性表置空）加工型操作加工型操作 ListInsert( &L, i, e )初始条件：操作结果：线性表L已存在， 且 1iLengthList(L)+1在L的第i个元素之前插入插入新的元素e，L的长度增1。（插入数据元素）ListDelete(&L, i, &e)初始条件：操作结果：线性表L已存在且非空， 1iLengthList(L)删除L的第i个元素，并用e返回其值，L的长度减1。（删除数据元素） 假设:有两个集合集合 A 和和 B 分别用两个线性表线性表 LA 和和 LB 表示，即：线性表中的数据元素即为集合中的成员。 现要求一个新的集合现要求一个新的集合AAB。例例 2-1 要求对线性表作如下操作：扩大线性表 LA，将存在于线性表存在于线性表LB 中中而不存在于线性表不存在于线性表 LA 中中的数据元素插入到线性表插入到线性表 LA 中中去。上述问题可演绎为：1从线性表LB中依次察看每个数据元素;2对其查看在线性表LA中是否存在; 3若不存在，则插入之。GetElem(LB, i,e) LocateElem(LA, e) ListInsert(LA, +n, e)操作步骤：操作步骤： GetElem(Lb, i, e); / 取取Lb中第中第i个数据元素赋给个数据元素赋给e if (!LocateElem(La, e) ) ListInsert(La, +laLen, e); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之void union(List &La, List Lb) laLen = ListLength(La); / 求线性表的长度求线性表的长度 lbLen = ListLength(Lb); for (i = 1; i = lbLen; i+) / union算法时间复杂度时间复杂度：O(m*n) 已知已知一个 B，试构造构造一个 A，使使 A 包含包含 B 中所有出现过中所有出现过的数据元素的数据元素。仍选用线性表线性表表示集合。例例 2-2集合集合 B集合集合 A从集合 B 取出物件放入集合 A且集合A中同样物件不能有两件以上同样物件不能有两件以上因此，算法的策略应该和例算法的策略应该和例2-1相似相似void purge (List &La, List Lb) laLen=ListLength(La); lbLen=ListLength(Lb); / union GetElem(Lb, i, e); / 取取Lb中第中第 i 个数据元素赋给个数据元素赋给 e if (LocateElem(La, e) =0) ListInsert(La, +La_len, e); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之for (i = 1; i = lbLen; i+) InitList(La); / 构造(空的)线性表LA算法时间复杂度时间复杂度：O(m2) 若线性表中的数据元素相互之间可以比较比较，并且数据元素在线性表中依值非递减依值非递减或非递增非递增有序有序排列，即 aiai-1 或 aiai-1(i = 2,3, n)，则称该线性表为试改变结构，以有序表有序表表示集合。例如例如:（2，3，3，5，6，6，6，8，12）对集合 B 而言， 值相同的数据元素必定相邻值相同的数据元素必定相邻对集合 A 而言， 数据元素依值从小至大的顺序插入数据元素依值从小至大的顺序插入因此，数据结构改变了，数据结构改变了， 解决问题的策略也相应要改变。解决问题的策略也相应要改变。例例 2-2 已知已知一个非纯集合非纯集合 B，试构造构造一个纯集合纯集合 A，使使 A 包含包含 B 中所有出现过的数据元素中所有出现过的数据元素。 （用非递减有序的顺序表表示A、B）void purge(List &La, List Lb) InitList(La); La_len = ListLength(La); Lb_len =ListLength(Lb); / 求线性表的长度求线性表的长度 for (i = 1; i = Lb_len; i+) / purge GetElem(Lb, i, e); / 取取Lb中第中第i个数据元素赋给个数据元素赋给 eif (en!=e) ListInsert(La, +La_len, e); en = e; / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之算法时间复杂度时间复杂度：O(m)则则 归并两个“其数据元素按值非递减有其数据元素按值非递减有序排列序排列”的有序表 LA 和 LB，求得有序表 LC 也具有同样特性。设设 La = (a1, , ai, , an), Lb = (b1, , bj, , bm) Lc = (c1, , ck, , cm+n)且且已由(a1, , ai-1)和(b1, ,bj-1)归并得归并得 (c1, , ck-1)jijjiikbabbaac例例 2-3k = 1, 2, , m+n1初始化初始化 LC 为空表；为空表；基本操作：2分别从分别从 LA和和LB中取得当前元素中取得当前元素 ai 和和 bj；3若若 aibj，则将，则将 ai 插入到插入到 LC 中，否则将中，否则将 bj 插入到插入到 LC 中；中；4重复重复 2 和和 3 两步，直至两步，直至 LA 或或 LB 中元素中元素 被取完为止；被取完为止；5将将 LA 表或表或 LB 表中剩余元素复制插入到表中剩余元素复制插入到 LC 表中。表中。void MergeList(List La, List Lb, List &Lc) / 本算法将非递减的有序表 La 和 Lb 归并为 Lc / merge_listwhile (i = La_len) & (j = Lb_len) / La 和和 Lb 均不空均不空 while (i=La_len) / 若 La 不空while (j=Lb_len) / 若 Lb 不空InitList(Lc); / 构造空的线性表 Lci = j = 1; k = 0;La_len = ListLength(La);Lb_len = ListLength(Lb); / La 和 Lb 均非空，i = j = 1, k = 0 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai = bj) / 将 ai 插入到 Lc 中 ListInsert(Lc, +k, ai); +i; else / 将 bj 插入到 Lc 中 ListInsert(Lc, +k, bj); +j; while (i = La_len) / 当La不空时 GetElem(La, i+, ai); ListInsert(Lc, +k, ai); / 插入插入 La 表中剩余元素表中剩余元素 while (j = Lb_len) / 当Lb不空时 GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / 插入插入 Lb 表中剩余元素表中剩余元素152743365380122.2 线性表的顺序表示和实现线性表的顺序表示和实现用一组用一组地址连续地址连续的存储单元的存储单元依次依次存储线性表的数据元素。存储线性表的数据元素。 2001 2003 2005 2007 2009 2011 2013 2015 2017 .0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 10 0 0 0 0 0 0 0 0 0 0 0 0 0 1 00 0 0 0 0 0 0 0 0 0 0 0 0 1 1 10 0 0 0 0 0 0 0 0 0 0 0 0 1 0 00 0 0 0 0 0 0 0 0 0 1 0 0 0 0 10 0 0 0 0 0 0 0 0 1 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 1 10 0 0 0 0 0 0 0 0 1 0 1 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0a9线性表的这种线性表的这种机内表示机内表示称做
