1、第02讲 线性表类型定义与顺序表数据结构第 2 次课章节名称2.1 线性表的类型定义2.2 线性表的顺序表示和实现目的要求1. 理解线性表的概念；准确掌握线性的基本操作；能够利用基本运算构造出较复杂的运算，以解决实际问题。2. 理解并熟练掌握线性表的顺序存储结构以及线性表的基本操作算法；熟练地通过上机编程练习掌握对线性表顺序存储的操作算法。主要内容与时间概算序号主要内容时间概算1线性表的定义和基本操作15分2利用基本运算构造出较复杂的运算 25分3线性表的顺序存储结构15分4线性表顺序存储的典型操作的算法实现45分 共计100分重点难点重点：1. 线性表的逻辑结构特征和线性表上定义的基本运算；
2、2. 线性表的顺序存储结构以及基本操作算法；难点：1. 利用基本运算构造出较复杂的运算；2. 线性表顺序存储操作的算法实现。方法手段采用教员课堂讲授、学员上机实验实施教学。在教学过程中应准确解释各个基本概念，清晰地阐明基本概念的内涵和相互联系，授课中应对于重/难点作详细分析，举例阐明讲解解题思路，解题过程，并结合课堂讲授的内容实施上机实验教学任务。（续表）课 堂 提 问1. 什么是线性表？并举出实例。2. 如何表示顺序表中任意一个数据元素的存储位置？3. 如何实现顺序表的插入操作？可分哪几种情况？本 次 课 内 容 总 结1. 线性表是一种典型的线性结构；2. 线性表的基本操作；3. 如何利用
3、基本运算解决较复杂的运算问题；4. 线性表的顺序存储结构表示；5、顺序表的操作；思考题作业题线性表顺序存储结构插入删除操作时，需要移动大量元素，如何克服？参考资料数据结构辅导与提高，徐孝凯编著，清华大学出版社数据结构习题解答与考试指导，梁作娟等编著，清华大学出版社授课内容第2章 线性表2.1 线性表的类型定义一、线性表的定义线性表是由n（n0）个类型相同的数据元素组成的有限序列。通常表示成下列形式：L=(a1,a2,.,ai-1,ai,ai+1,.,an)其中：L为线性表名称，习惯用大写书写；ai为组成该线性表的数据元素，习惯用小写书写。线性表中数据元素的个数被称为线性表的长度，当n=0时，线
4、性表为空，又称为空线性表。举例：La=（34，89，765，12，90，-34，22）数据元素类型为int。Ls=(Hello,World,China,Welcome)数据元素类型为string。Lb=(book1,book2,.,book100) 数据元素类型为下面的结构类型：struct bookinfoint No; /图书编号char *name; /图书名称char *auther; /作者名称.; 二、线性表的逻辑特征1. 非空的线性表中，有且仅有一个开始结点 a1无没有直接前趋，并且仅有一个直接后继 a2；2. 有且仅有一个终端结点 an 无没有直接后继，并且仅有一个直接前趋 a
5、n-1；3. 其余的内部结点 ai(2in-1)都有且仅有一个直接前趋 ai-1 和一个直接后继 ai+1；三、抽象数据类型线性表的定义ADT List 数据对象：D=ai | ai ElemSet, i = 1,2,3,n, n0数据关系：R1= | ai-1 , aiD, i = 2,n线性表的基本操作InitList(&L)操作结果：构造一个空的线性表L。DestroyList(&L)初始条件：线性表L已存在。 操作结果：销毁线性表。ClearList(L)初始条件：线性表L已存在。 操作结果：将L重置为空表。ListEmpty(L)初始条件：线性表L已存在。 操作结果：若L为空表，则返
6、回 TRUE，否则返回FALSE。ListLength(L)初始条件：线性表L已存在。 操作结果：返回L中数据元素个数。GetElem(L，i，&e)初始条件：线性表L已存在，1iListLength(L)。操作结果：用e返回L中第i数据个元素的值。 LocateElem(L，e，compare( )初始条件：线性表L已存在，compare( )是数据元素判定函数。操作结果：返回L中第1个与e满足关系compare( )的数据元素的位序。 不存在，则返回值为0。PriorElem(L， cur_e， &pre_e)初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素，且不是第一个，则
7、用pre_e返回它的前驱，否则操作失败，pre_e无定义。NextElem (L，cur_e，&next_e)初始条件：线性表L已存在。操作结果：若cur_e是L的数据元 素，且不是最后一个， 则用next_e返回它的后继，否则操作作失败， next_e无定义。ListInsert(&L，i，e)初始条件：线性表L已存在，1iListLength(L)+1。操作结果：在L中第i个位置之前插入新数据元素e，L长度加1。ListDelete(&L，i，&e)初始条件：线性表L已存在且非空，1i ListLength(L)。 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。ListT
8、raverse(L，visit( )初始条件：线性表L已存在。 操作结果：依次对L的每个数据元素调用函数visit( )。一旦visit( )失败， 则操作失败。ADT List四、利用上述定义的操作完成更复杂的操作例1：假设有两个集合A和B分别用两个线性表LA和LB表示。（即：线性表中的数据元素即为集合中的成员），现要求一个新集合 AAB分析：问题可演绎为，要求对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存于线性表LA中的数据元素插入到线性表LA中。则思路即为： 1从线性表LB中依次取得每个数据元素；2依值在线性表LA中进行查访； 3若不存在，则插入之。void union(
9、List &La, List Lb) /将所有在线性表Lb中但不在La中的元素插入到La La_len = ListLength(La); Lb_len = ListLength(Lb); / 求线性表的长度 for (i = 1; i = Lb_len; i+) GetElem(Lb, i, &e); / 取Lb中第i个元素赋给e if ( !LocateElem(La, e, equal( ) ListInsert(&La, + La_len, e); / La中不存在和 e 相同的元素，则插入之 / union例2：假已知一个非纯集合B，(即B中包含有相同元素）试构造一个纯集合A，使A中
10、只包含B中所有值各不相同的数据元素。（假设B均为有序序列）分析：则思路即为：1创建一个空的线性表LA;2从线性表LB中依次取得每个数据元素；3依值在线性表LA中进行查访； 4若不存在，则插入之。void purge(List &La, List Lb) / 构造La，使其只包含Lb中所有值不相同的元素 InitList(&LA); La_len = ListLength(La); Lb_len = ListLength(Lb); / 求线性表的长度 for (i = 1; i elem=(Elemtype *)malloc(LIST_MAX_LENGTH *sizeof(Elemtype);
11、/分配空间if (L-elem=NULL) return ERROR; /分配空间不成功L-length=0; /将当前线性表长度置0return OK; /成功返回OK（2）销毁线性表Lvoid DestroyList(SEQLIST *L) if (L-elem) free(L-elem); /释放线性表占据的所有存储空间（3）清空线性表Lvoid ClearList(SEQLIST *L)L-length=0; /将线性表的长度置为0（4）求线性表L的长度int GetLength(SEQLIST L) return (L.length);（5）判断线性表L是否为空int IsEmpty
12、(SEQLIST L) if (L.length=0) return TRUE; else return FALSE;（6）获取线性表L中的某个数据元素的内容int GetElem(SEQLIST L,int i,Elemtype *e) if (iL.length) return ERROR; /判断i值是否合理*e=L.elemi-1; /数组中第i-1的单元存储着线性表中/第i个数据元素的内容return OK;（7）在线性表L中检索值为e的数据元素int LocateELem(SEQLIST L,Elemtype e) for (i=0;ilength=LIST_MAX_LENGTH)
13、 return ERROR; /检查是否有剩余空间if (iL-length+1) return ERROR; /检查i值是否合理for (j=L-length-1;j=i-1;i+) /将线性表第i个元素之后的所有元素向后移动L.-elemj+1=L-elemj;L-elemi-1=e; /将新元素的内容放入线性表的第i个位置，L-length+;return OK;插入算法分析：假设pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时所需移动元素次数的期望值(平均次数)为式：不失一般性，我们可以假定在线性表的任何位置上插入或删除元素都是等概率的，即： pi = 1
14、/(n+1)， qi = 1/n ，则式可化简为：（9）将线性表L中第i个数据元素删除int ListDelete(SEQLIST *L,int i,Elemtype *e) if (IsEmpty(L) return ERROR; /检测线性表是否为空if (iL-length) return ERROR; /检查i值是否合理*e=L-elemi-1; /将欲删除的数据元素内容保留在e所指示的存储单元中for (j=i;jlength-1;j+) /将线性表第i+1个元素之后的所有元素向前移动L-elemj-1=L-elemj;L-length-;return OK; 删除算法分析：假设qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素时所需移动元素次数的期望值(平均次数)为式：不失一般性，我们可假定在线性表的任何位置上删除元素都是等概率的，即： pi = 1/(n+1)，qi = 1/n ，则式（2-3）（2-4）可分别化简为 算法ListInsert_Sq, ListDelete_Sq的时间复杂度为均O(n)。备注：
