《数据库第二章线性表教学ppt》由会员分享，可在线阅读，更多相关《数据库第二章线性表教学ppt（88页珍藏版）》请在金锄头文库上搜索。
1、数 据 结 构,李 鑫 辽宁工程技术大学电信学院,2018/9/11,数据结构,2,第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第9章 查找 第10章 排序,目 录,2018/9/11,数据结构,3,数据结构课程的起点：,什么是 线性结构？,2018/9/11,数据结构,4,第2章 线性表,2.1 线性表的逻辑结构 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 应用举例,2018/9/11,数据结构,5,线性结构的定义：,若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只
2、有一个直接前趋和一个直接后继。 可表示为：（a1 , a2 , , an）,简言之，线性结构反映结点间的逻辑关系是 的。,特点 只有一个首结点和尾结点； 特点 除首尾结点外，其他结点只有一个直接前驱和一个直接后继。,线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是-,线性表,一对一 (1:1),2018/9/11,数据结构,6,（a1, a2, ai-1，ai, ai1 ，, an）,2.1 线性表的逻辑结构,线性表的定义：用数据元素的有限序列表示,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数
3、，即表长。n0,空表,线性终点,2018/9/11,数据结构,7,（ A, B, C, D, , Z）,例2 分析学生情况登记表是什么结构。,分析：数据元素都是同类型（记录），元素间关系是线性的。,分析： 数据元素都是同类型（字母）， 元素间关系是线性的。,注意：同一线性表中的元素必定具有相同特性 ！,例1 分析26 个英文字母组成的英文表是什么结构。,2018/9/11,数据结构,8,“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。,是指各元素具有相同的数据类型,试判断下列叙述的正误：,2018/9/11,数据结构,9,课堂讨论：,线性表表各种操作
4、算法的“通式” 该如何书写？ 采用抽象数据类型来表示,2018/9/11,数据结构,10,线性表的抽象数据类型定义（见教材P19）,ADT List 数据对象：D=ai | aiELemSet, i=1,2,n,n0 数据关系：R1= | ai 1, ai D, i=2,n 基本操作：,初始化、撤销、清空、判空； 求表长、表头、表尾、前趋、后继； 读元素、查找（含定位）、遍历； 插入、删除, ADT List,2018/9/11,数据结构,11,线性表的基本操作如何表示？ （见教材P19）,InitList( /删除第i个元素用e返回其值，L长度减1,练习：有一个线性表L=（a, c,a,d,
5、b）,求下列操作,ListLength(L)=,5,返回假（0）,GetELem(L,3,e)=,e=a,LocateELem(L,a)=,1,ListInsert(L, 4, e)=,执行后线性表L变成（a,c,a,e,d,b）,ListDeLete(L,3)=,执行后线性表L变成（a,c, e,d,b）,2018/9/11,数据结构,13,抽象数据类型操作的典型例子,教材例2-1：求两个线性表的“并”，即：线性表LA和LB分别表示两个集合A和B，要求一个新的集合A为：LA = LA U LB?,算法至少有两种： LA和LB都是无序表，则从LB中取元素逐一与LA中所有元素比较，相同则不插入L
6、A中； 若LA和LB已经是有序表，则“归并”的时间效率可以大大提高。,2018/9/11,数据结构,14,归并的算法,1、从LB中取每一元素 GetELem（LB ，e）,2、依值在LA中查找 LocateELem（LA ，e,equaL()）,3、若不存在，则插入 ListInsert（LA ，n+1，e）,2018/9/11,数据结构,15,void union(List if(!LocateELem(La，e，equaL)ListInsert(La，+La_Len，e),算法时间复杂度？,时间复杂度为： O( ListLength(La) * ListLength(Lb) ),例2-2
7、巳知线性表LA和线性表LB中的数据元素按值 非递减有序排列， 现要求将LA和LB归并为一个新的线性表LC， 且LC中的元素仍按值非递减有序排列。 此问题的算法如下：,void MergeList(List La，List Lb，List ,2018/9/11,数据结构,18,算法时间复杂度？,时间复杂度为： O( ListLength(La) * ListLength(Lb) ),void MergeList(List La，List Lb，List ,19,whiLe(i=La-Len) GetELem(La，i+，ai);ListInsert(Lc，+k，ai); whiLe(j=Lb-L
8、en) GetELem(Lb，j+，bj);ListInsert(Lc，+k，bi);,插入La/Lb剩余元素,时间复杂度为 O( ListLength(La) + ListLength(Lb) ),思考：时间复杂度为？,分析两者的时间复杂度,算法2.1的时间复杂度为O （ ListLength（LA）* ListLength（LB） ） 算法2.2的时间复杂度为O （ ListLength（LA）+ ListLength（LB） ）,课后练习,已知一个非纯集合B，试构造一个纯集合A，使A中只包含B中所有值各不相同的数据元素,2018/9/11,数据结构,22,2.2 线性表的顺序表示和实现,
9、1 顺序表的表示 2 顺序表的实现 3 顺序表的运算效率分析,2018/9/11,数据结构,23,1 顺序表的表示,用一组地址连续的存储单元依次存储线性表的元素。,把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。,线性表的顺序表示又称为顺序存储结构或顺序映像。,顺序存储定义：,顺序存储方法：,特点：,逻辑上相邻的元素，物理上也相邻,可以利用数组Vn来实现,注意：在C语言中数组的下标是从0开始，即：Vn的有效范围是从 V0Vn-1,2018/9/11,数据结构,24,1. 逻辑上相邻的数据元素，其物理上也相邻； 2. 若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利
10、用数组Vn的下标）。,设首元素a1的存放地址为LOC(a1)（称为首地址）， 设每个元素占用存储空间（地址长度）为L字节， 则表中任一数据元素的存放地址为：LOC ( ai+1 ) = LOC( ai ) + L LOC ( ai ) = LOC( a1 ) + L *（i -1）,对上述公式的解释如图所示,线性表顺序存储特点：,2018/9/11,数据结构,25,地址 内容 元素在表中的位序,1,i,2,n,空闲区,i+1,L,b=LOC(a1),b + L,b +(i-1)L,b +(n-1)L,b +(max-1)L,LOC ( ai ) = LOC( a1 ) + L *（i -1）,
11、线性表的顺序存储结构示意图,下标起点是1,2018/9/11,数据结构,26,设有一维数组，下标的范围是到，每个数组元素用相邻的个字节存储。存储器按字节编址，设存储数组元素的第一个字节的地址是98，则的第一个字节的地址是多少？,答案：113,但此题要注意下标起点是从0开始： LOC( M3 ) = 98 + 5 (4-1) =113,解：已知地址计算通式为：,LOC(ai) = LOC(a1) + L *（i-1）,例1,2018/9/11,数据结构,27,char V30; void buiLd() /*字母线性表的生成，即建表操作*/ int i; V0=a; for( i=1; i=n-
12、1; i+ ) Vi=Vi-1+1; ,核心语句： 法1 Vi= Vi-1+1; 法2 Vi=a+i; 法3 Vi=97+i;,例2,用数组V来存放26个英文字母组成的线性表（a，b，c，z），写出在顺序结构上生成和显示该表的C语言程序。,省略了incLude语句,2018/9/11,数据结构,28,void main(void) /*主函数，字母线性表的生成和输出*/ n=26; /* n是表长，是数据元素的个数，而不是V的实际下标*/ buiLd( ); dispLay( ); ,void dispLay( ) /*字母线性表的显示，即读表操作*/ int i; for( i=0; i=i
13、; j-) aj+1=a j ; a i =x; n+;,/ 元素后移一个位置,/ 插入x,/ 表长加1,核心语句：,2)插入,2018/9/11,数据结构,31,在线性表的第i个位置前插入一个元素的示意图如下：,插入25,2018/9/11,数据结构,32,实现步骤： 将第i+1 至第n 位的元素向前移动一个位置； 表长减1。 注意：事先需要判断，删除位置i 是否合法? 应当符合条件：1in 或 i=1, n,删除线性表的第i个位置上的元素,for ( j=i+1; j=n; j+ ) aj-1=aj; n-;,/ 元素前移一个位置,/ 表长减1,核心语句：,3)删除,2018/9/11,数
14、据结构,33,删除顺序表中某个指定的元素的示意图如下：,顺序表插入和删除的完整程序请同学们自编。,2018/9/11,数据结构,34,3 顺序表的运算效率分析,算法时间主要耗费在移动元素的操作上，因此 计算时间复杂度的基本操作（最深层语句频度）T(n)= O (移动元素次数) 而移动元素的个数取决于插入或删除元素的位置.,思考：若插入在尾结点之后，则根本无需移动（特别快）； 若插入在首结点之前，则表中元素全部要后移（特别慢）； 应当考虑在各种位置插入（共n+1种可能）的平均移动次数才合理。,讨论1：若在长度为 n 的线性表的第 i 位前 插入一个元素，则向后移动元素的次数f(n)为:f(n) =,n i + 1,时间效率分析:,2018/9/11,数据结构,
