第二章第二章 线性表线性表重点：重点：n理解线性表的逻辑结构特性n熟练掌握线性表的顺序存储结构的描述方 法，以及在该存储结构下的基本操作n熟练掌握线性表的链式存储结构的描述方 法，灵活使用单链表、双链表、循环链表 ，学会在相应存储结构下实现其各种基本 算法及相关的时间性能分析n一元多项式的表示和相加1第二章 线性表难点：难点：n n能够从时间和空间复杂度的角度综合比较能够从时间和空间复杂度的角度综合比较 线性表两种存储结构的不同特点及其应用线性表两种存储结构的不同特点及其应用 场合场合n n使用本章所学的基本知识设计有效算法，使用本章所学的基本知识设计有效算法， 解决与线性表相关的应用问题解决与线性表相关的应用问题2第二章第二章 线性表线性表2.1 2.1 线性表的类型定义线性表的类型定义 2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现 2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现2.3.1 2.3.1 线性链表线性链表2.3.2 2.3.2 循环链表循环链表2.3.3 2.3.3 双向链表双向链表 2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加3第二章第二章 线性表线性表 线性结构的特点：线性结构的特点：在数据元素的非空有限集中，在数据元素的非空有限集中， 1 1）存在唯一的一个被称为存在唯一的一个被称为“ “第一个第一个” ”的数据元素的数据元素 2 2）存在唯一的一个被称为存在唯一的一个被称为“ “最后最后一个一个” ”的数据元素的数据元素 3 3）除第一个之外，集合中的每个数据元素均只有）除第一个之外，集合中的每个数据元素均只有 一个一个前驱前驱 4 4）除最后一个之外，集合中的每个数据元素均只）除最后一个之外，集合中的每个数据元素均只 有一个有一个后继后继41. 1. 线性表：线性表： 定义定义：简称为表，是零个或多个元素的有穷序列简称为表，是零个或多个元素的有穷序列 ，通常可以表示成，通常可以表示成( (a a1 1, , a a2 2, , , , a an n)( )(n n 0) 0) 表的长度表的长度：表中所含元素的个数：表中所含元素的个数 n n 空表空表：长度为零的表：长度为零的表 表项表项：表中的元素：表中的元素 a ai i 位位序序：数据元素：数据元素 a ai i 在在线性表中的位置线性表中的位置2.1 线性表的类型定义51. 1. 线性表：线性表： 线性表中的数据元素在不同的情况下可以有不线性表中的数据元素在不同的情况下可以有不 同的具体含义，它可以是一个数、一个符号，同的具体含义，它可以是一个数、一个符号， 也可是其它更复杂的信息也可是其它更复杂的信息 例例1 1. 26. 26个字母个字母( (A, B, , Z)A, B, , Z) 例例2 2. . 班级人数班级人数(33, 32, 35, 30)(33, 32, 35, 30) 例例3 3. . 学生情况登记表：数据元数为记录，有若学生情况登记表：数据元数为记录，有若 干个数据项组成（如姓名，学号，性别，年龄干个数据项组成（如姓名，学号，性别，年龄 ) ) 2.1 线性表的类型定义62. 2. 线性表的特点线性表的特点： 线性表中的数据元素是各种各样的，但同一线性表线性表中的数据元素是各种各样的，但同一线性表 中的元素必定具有相同特性，即属于中的元素必定具有相同特性，即属于同一数据对象同一数据对象 相邻数据元素之间存在相邻数据元素之间存在序偶序偶关系关系( (a a1 1, , a a2 2, , , , a ai-1i-1, , a ai i, , a ai+1i+1, , , , a an n) )a ai-1i-1是是 a ai i的的直接前驱元素，直接前驱元素，a ai+1i+1是是a ai i的直接后继元素的直接后继元素 相当相当灵活灵活，长度可以增长或缩短，长度可以增长或缩短2.1 线性表的类型定义73. 3. 线性表的基本运算线性表的基本运算 在线性表中在线性表中插入插入一个元素一个元素； 在线性表中在线性表中删除删除某个元素某个元素； 在线性表中在线性表中查找某个特定查找某个特定元素；元素； 在线性表中在线性表中查找查找某个元素的某个元素的后继后继元素；元素； 在线性表中在线性表中查找查找某个元素的某个元素的前驱前驱元素；元素； 创建创建空线性表；空线性表； 判别判别一个线性表是否为空表。一个线性表是否为空表。 由基本运算可以构成其它较为复杂的运算由基本运算可以构成其它较为复杂的运算2.1 线性表的类型定义84. 4. 抽象数据类型线性表的定义抽象数据类型线性表的定义（P19P19） ADT List 数据对象：D=ai |aiElemSet, i=1, 2, , n, n 0数据关系：R1=| ai-1, ai D, i=1, 2, , n基本操作：InitList( ;2 2）依值在线性表）依值在线性表LALA中进行查访中进行查访; ;3 3）若不存在，则插入之。）若不存在，则插入之。2.1 线性表的类型定义14用用C C语言描述得如下算法：语言描述得如下算法： void union(List );Lb_lenLb_len = =ListLength(LbListLength(Lb); / ); / 求线性表的长度求线性表的长度for (i = 1; i L.length+1) return ERROR; / if (iL.length+1) return ERROR; /非法的位置非法的位置 if (L.length=if (L.length=L.listsizeL.listsize) /) /当前空间已满当前空间已满newbasenewbase = ( = (ElemTypeElemType *) *)realloc(L.elemrealloc(L.elem, , ( (L.listsize+LISTINCREMENTL.listsize+LISTINCREMENT)*)*sizeof(ElemTypesizeof(ElemType) ) ; ;if (! if (!newbasenewbase) exit (OVERFLOW);) exit (OVERFLOW);L.elemL.elem = = newbasenewbase; ;L.listsizeL.listsize= =L.listsize+INCREMENTL.listsize+INCREMENT; ; 2930312.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现q=q=for (p= -p) for (p= -p) *(p+1)=*p; / *(p+1)=*p; /插入位置后移插入位置后移* *q=e;q=e;L.length+; L.length+;return OK; return OK;/ /ListInsert_SqListInsert_Sq322.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现Status Status ListDelete_Sq(SqListListDelete_Sq(SqList if (iL.length) return ERROR;p= p=e=*p; e=*p;q=L.Elem+L.length-1; q=L.Elem+L.length-1;for (+p; p=1; j-) for (j=m; j=1; j-)L.Elemi+jL.Elemi+j=L.Elemi+j-1;=L.Elemi+j-1;L.ElemiL.Elemi=w;=w; /exchange1 /exchange1392.3 2.3 线性表的链式表示及实现线性表的链式表示及实现 顺序表的缺陷顺序表的缺陷：插入：插入/ /删除耗费大量时间删除耗费大量时间 线性链表线性链表：用一组任意单元表示数据元素和数据元：用一组任意单元表示数据元素和数据元 素之间的关系（这些单元可以是连续的，也可以是素之间的关系（这些单元可以是连续的，也可以是 不连续的）不连续的）其其结点结点由两部分信息组成：由两部分信息组成：（1 1）数据域数据域：存储数据元素信息；：存储数据元素信息；（2 2）指针域指针域：存储直接后继的存储位置（地址）。：存储直接后继的存储位置（地址）。402.3 2.3 线性表的链式表示及实现线性表的链式表示及实现 2.3.1 2.3.1 单链表单链表：数据域数据域指针域指针域存储地址存储地址 数据域数据域 指针域指针域1 1LiLi 43 437 7QianQian 13 1313 13SunSun 1 119 19WangWang NULL NULL25 25WuWu 37 3731 31ZhaoZhao 7 737 37ZhengZheng 19 1943 43ZhouZhou 25 253131头指针头指针HH412.3 2.3 线性表的链式表示及实现线性表的链式表示及实现 单链表单链表：线性链表的逻辑状态线性链表的逻辑状态LiZhaoQianSunZhouWuZhengWang HH4243442.3 2.3 线性表的链式表示及实现线性表的链式表示及实现 单链表单链表：a1ana2.头指针H头结点H非空表非空表空表空表45 单链表结构 2.3 2.3 线性表的链式表示及实现线性表的链式表示及实现462.3 2.3 线性表的链式表示及实现线性表的链式表示及实现 头结点头结点头结点是链表的开始结点之前的一个附加结点。头结点是链表的开始结点之前的一个附加结点。 使用头结点的使用头结点的好处好处在于：在于： （1 1）由于开始结点位置被存放在头结点的指针域）由于开始结点位置被存放在头结点的指针域 中，所以在链表的第一个位置上的操作就和在中，所以在链表的第一个位置上的操作就和在 表的其它位置上的操作一致，无须进行特殊处表的其它位置上的操作一致，无须进行特殊处 理理 （2 2）无论链表是否为空，其头指针是指向结点的）无论链表是否为空，其头指针是指向结点的 非空指针（空表中头结点的指针域为空），因非空指针（空表中头结点的指针域为空），因 此空表和非空表的处理也就统一了此空表和非空表的处理也就统一了47 线性链表的定义线性链表的定义 typedeftypedef intint DataTypeDataType; ; /* /* 定义元素类型为整型，也定义元素类型为整型，也 可定义为其他类型可定义为其他类型 * */ / structstruct LNodeLNode; ;/* /* 单链表结点类型单链表结点类型 * */ / typedeftypedef structstruct LNodeLNode * *PNodePN