《数据结构-课件》由会员分享，可在线阅读，更多相关《数据结构-课件（112页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性表,主讲：赵红丹 Email:,课前导学,2.1 线性表的类型定义 2.2 线性表的顺序表示与实现 2.3线性表的链式表示与实现 2.4 一元多项式的表示及相加,学习目标,1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系。 2. 熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。 3. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。 4. 结合线性表类型的定义增强对抽象数据类型的理解。,重点和难点,链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求，分清链表中指针 p 和结点 *p
2、之间的对应关系，区分链表中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。,线性结构的特点,在数据元素的非空有限集中 存在唯一一个被称做“第一个”的数据元素； 存在唯一一个被称做“最后一个”的数据元素； 除第一个数据元素之外，每个元素都只有一个前驱； 除最后一个数据元素之外，每个元素都只有一个后继。,线性表的定义,一个线性表是n个数据元素的有限序列。 除了第一个元素没有直接前驱和最后一个元素没有直接后继之外，其余的每个数据元素只有一个直接前驱和一个直接后继。,线性表的特征,有穷性：由有限个元素组成，元素个数n表长度，n=0空表。设线性表为 (a1，a2, . . . ，ai
3、，. . . ，an), 称 i 为 ai 在线性表中的位序。 有序性：线性表元素之间存在序偶关系，1in时 ai的直接前驱是ai-1，a1无直接前驱 ai的直接后继是ai+1，an无直接后继 同一性：线性表属于同类数据元素组成，每一个对象都属于同一数据对象,抽象数据类型线性表的定义如下：,ADT List 数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 数据关系：R1 |ai-1 ,aiD, i=2,.,n 基本操作： （1）InitList（&L） 操作结果：将L初始化为空表。 （2）DestroyList(&L) 操作前提：线性表L已存在。操作结果：将L销毁。
4、 （3）ClearList(&L) 操作前提：线性表L已存在 。操作结果：将表L置为空表。,（4）EmptyList（L） 操作前提：线性表L已存在。 操作结果：如果L为空表则返回真，否则返回假。 （5）ListLength（L） 操作前提：线性表L已存在。 操作结果：如果L为空表则返回0，否则返回表中的元素个数。 （6）GetItem(L,i,&e) 操作前提： 表L已存在，1=inum 或者（*p）.num。,2.2线性表的顺序存储结构,定义：线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素。 使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中。采用顺序
5、存储结构的线性表通常称为顺序表。 假设线性表中有n个元素，每个元素占L个单元，第一个元素的地址为loc(a1)，则可以通过如下公式计算出第i个元素的地址Loc(ai)：loc(ai+1) =loc(ai)+Lloc(ai) =loc(a1)+(i-1)L (2-2) 其中loc(a1) 称为基址。,线性表的顺序存储结构是一种随即存取的存储结构，只要确定了起始位置，就可以访问表中的任何一个元素。,数据结构学习的误区,只动眼、耳，不动手 学习数据结构的有效方法是动手，动脑。 (2)有的同学认为，数据结构是C语言的延续，这是一种错误的想法。C语言仅仅是一个程序设计工具，而数据结构则是程序设计的思想和
6、灵魂，在学习数据结构的过程中经常会接触到C语言的知识，这只不过是借用C语言这个工具来表达数据结构的思想而已，我们也可以不选用C语言，而选择其它语言，如PASCAL、JAVA等，所以，不应该把数据结构当成C语言来学习。 死记硬背分析每一种数据结构的特点、存储方式和操作算法，养成提出问题、分析问题和解决问题的思维习惯，提升自己分析问题和解决问题的能力。,课程回顾,线性表的顺序存储结构 线性表的初始化 线性表插入操作,顺序存储结构的C语言定义,#define LIST_INT_SIZE 100 #define LISTINCREAMENT 10 typedef struct ElemType *el
7、em； / 线性表占用的数组空间。int length； / 线性表的长度int listsize； /当前分配的存储容量 SeqList；,线性表的基本操作在顺序表中的实现,InitList(&L) / 结构初始化,LocateElem(L, e ) / 查找,ListInsert(&L, i, e) / 插入元素,ListDelete(&L, i) / 删除元素,线性表的初始化操作,顺序线性表的操作 顺序表容易实现访问操作，可随机存取元素。但插入和删除操作主要是移动元素。 初始化操作 算法思想：构造一个空表。设置表的起始位置、表长及可用空间。,算法： Status InitList_Sq(
8、SqList *L) /构造一个空的线性表 L-elem=(ElemType )malloc(LIST_INIT_SIZE*size of(ElemType); If (! L-elem) exit(OVERFLOW); /存储分配失败 L-length=0; /空表长度为0 L-listsize= LIST_INIT_SIZE; /初始存储容量 return OK; /InitList_Sq,二、线性表的顺序表插入操作 ListInsert(&L, i, e),首先分析，“插入元素”使线性表的逻辑结构发生什么变化？假设在线性表的第i个元素之前插入一个元素e。 由于顺序表是以“存储位置相邻”
9、表示“元素之间的前驱和后继关系”，则必须“移动元素”来体现“元素之间发生的变化”。,(a1, , ai-1, ai, , an) 改变为, ,(a1, , ai-1, e, ai, , an),算法思想：,1）检查i值是否超出所允许的范围（1in+1），若超出，则进行“超出范围”错误处理； 2）将线性表的第i个元素和它后面的所有元素均向后移动一个位置； 3）将新元素写入到空出的第i个位置上； 4）使线性表的长度增1。,Status ListInsert_Sq(SqList *L, int i, ElemType e) / 在顺序表L的第 i 个元素之前插入新的元素e,/ i 的合法范围为 1i
10、L.length+1ElemType *p,*q;if (i L.length+1) return ERROR; / 插入位置不合法if (L-length = L- listsize) q = ,newbase=(ElemType*)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(ElemType); If(!newbase) return OVERFLOW;/ 当前存储空间已满L- elem=newbase;L- list size+=LISTINCREMENT;,考虑移动元素的平均情况:,假设在第 i 个元素之前插入的概率为 则在
11、长度为n 的线性表中插入一个元素所需移动元素次数的期望值为：,若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：,线性表操作ListDelete(&L, i, &e)的实现：,首先分析：,删除元素时， 线性表的逻辑结构发生什么变化？,(a1, , ai-1, ai, ai+1, , an) 改变为,ai+1,an, ,表的长度减少,(a1, , ai-1, ai+1, , an),算法思想：,1）检查i值是否超出所允许的范围（1in），若超出，则进行“超出范围”错误处理； 2）将线性表的第i个元素后面的所有元素均向前移动一个位置； 3）使线性表的长度减1。,Stat
12、us ListDelete_Sq (SqList *L, int i, ElemType *e) / ListDelete_Sq,for (+i; i elemi-1= L- elemi; / 被删除元素之后的元素左移 -L- length; / 表长减1 return OK;,*e= L-elemi-1; / 被删除元素的值赋给 ek= L- length-1; / 表尾元素的位置,if (i L.length) return ERROR; / 删除位置不合法,考虑移动元素的平均情况:,假设删除第 i 个元素的概率为 , 则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值为：,若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：,int LocateElem_Sq(SqList L, ElemType e,) / 在顺序表中查询第一个满足判定条件的数据元素，/ 若存在，则返回它的位序，否则返回 0 / LocateElem_Sq,
