线性表电子教案

《线性表电子教案》由会员分享，可在线阅读，更多相关《线性表电子教案（71页珍藏版）》请在金锄头文库上搜索。

1、第二章 线性表,2.1线性表的定义及其运算 2.2线性表的顺序存储 2.3线性表的链式存储 2.4线性表的应用案例分析,1.线性表的顺序存储及其相关运算的实现 2.线性表的链式存储及其相关运算的实现,教学内容,教学重难点,引言：线性结构的特点,存在着唯一一个被称为“第一个”的元素，即起始元素；,存在着唯一一个被称为“最后一个”的元素，即终端元素；,除第一个元素外，集合中的每一个元素均只有一个直接前驱；,除最后一个元素外，集合中的每一个元素均只有一个直接后继。,2.1 线性表的定义和运算,线性表的定义 线性表的抽象数据类型,线性表的定义,线性表:n(n=0)个具有相同特性的数据元素的有限序列。通

2、常情况下线性表被记作：(a1,a2,a3,ai,an)。n为表长,n=0时为空表。,（a1 , a2 , ai-1 , ai , ai1 , , an）,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长,线性终点,1、数据元素的类型一致；,小结：线性表的特点,2、元素间的相对位置呈线性。,例5: 一群同学排队买演唱会门票，每人限购一张，排队人群是不是线性表？ 某同学前面放了三个书包占位。书包也算作是排队吗？,2.1 线性表的定义和运算,线性表的定义 线性表的抽象数据类型,ADT 线性表(List) 数据：线性表的数据对象为a1

3、,a2,an，要求数据元素具有相同的数据 类型； 关系：除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元 素外，其余元素有且仅有一个直接后继；元素间的关系是一对一的。 操作：InitList(*L); 初始化操作，建立一个空的线性表； ListEmpty(L); 若线性表为空，返回true；否则返回false； ClearList(*L); 将线性表清空； GetElem(L,I,*e); 将线性表L中第i个位置的元素值返回给e； LocateElem(L,e); 在线性表L中查找与给定值e相等的元素； ListInsert(*L,I,e); 在线性表L的第i个位置插入新元素e； L

4、istDelete(*L,I,*e); 删除线性表L中第i个元素，并用e返回其值； ListLength(L); 返回线性表L的元素个数。 ,例：求两个线性表A和B的合并，即将存在于B中但不存在于A中的元素插 入到A中即可。,void UnionList(List *La,List Lb); int La_len,Lb_len; ElemType e; La_len=ListLength(*La); Lb_len=ListLength(Lb); for(int i=1;i=Lb_len;i+) GetElem(Lb,i,e); if (!LocateElem(*La,e) ListInsert

5、(La,+La_len,e); ,复杂的个性化操作由基本操作组合实现,2.2 线性表的顺序存储,顺序表的定义 顺序表的存储结构 基本运算的实现,顺序表的定义,顺序表：采用顺序存储结构存储的线性表的简称，即把线性表的元素按逻辑次序依次存放在一组地址连续的存储单元中。,顺序表的特点：逻辑上相邻，物理上也相邻。,顺序表的实现：借助于C语言中的一维数组。,int c20;,则：LOC( M3 ) = 98 + 5 (3-0) =113,若已知表中首元素在存储器中的地址，则其他元素存放地址亦可求出，计算方法是： 设首元素a1的存放地址为LOC(a1)(称为首地址)， 设每个元素占用C个存储单元，则表中任

6、一数据元素的存放地址为： LOC(ai) = LOC(a1) + C *(i-1) (1=i=n),顺序表中数据元素的地址计算：,例1：一个一维数组M，下标的范围是0到9，每个数组元素占用相邻的5个存储单元。设存储数组元素M0的第一个单元的地址是98，则M3的第一个单元的地址是多少？,2.2 线性表的顺序存储,顺序表的定义 顺序表的存储结构 基本运算的实现,补充1：关于typedef C/C+中允许使用typedef关键字来指定一个新的数据类型名。 例1：typedef char ElemType; 则：char c; 等价于 ElemType c; 例2：typedef struct stu

7、dent int num; char name10; STU; 则：struct student x; 等价于 STU x;,补充2：关于C+中的引用运算符 C+语言中提供一种引用运算符“ 当执行语句swap(a,b)时，实参a和b的值发生了交换。,原本参数值的传递是单向的，只能由实参传递给形参。,顺序表的存储结构定义,# define MaxSize 50 typedef int ElemType; typedef struct SequenceList ElemType data MaxSize; int length; SqList; SqList sl;,顺序表的存储结构定义,# de

8、fine MaxSize 50 typedef int ElemType; typedef struct SequenceList ElemType data MaxSize; int length; SqList;,Sl,SqList *sl;,sl=(SqList *)malloc(sizeof(SqList); 或者： sl=new SqList;,2.2 线性表的顺序存储,顺序表的定义 顺序表的存储结构 基本运算的实现,1、初始化顺序表,void InitList(SqList * ,2、建立顺序表,void CreatList(SqList *l,ElemType a ,int n)

9、 int i; for(i=0;idatai=ai; l-length=n; ,3、销毁顺序表 DestroyList(l); 4、判断顺序表是否为空 ListEmpty(l); 5、求顺序表的长度 ListLength(l); 6、输出顺序表 DispList(l); 7、求顺序表中某个数据元素的值 GetElem(l,i,e);,8、顺序表的插入算法 要求在顺序表的第i个数据元素之前插入一个数据元素x，使长度为n的线性表(a1,a2,ai,an)变为长度为n+1的线性表(a1,a2,.,ai-1,x,ai,an)。,注意事项,1、第i个元素在数组中的下标是i-1; 2、移动方向：从最后一个

10、元素开始，否则会相互覆盖； 3、用来存放的数组要足够大，有接受x的空间； 4、注意讨论插入点i的合法性。,void ListInsert (SqList *sl,int i,int x) int j; if (isl-length+1) printf(“error!”); else if (sl-lengthMaxSize) printf(“overflow!”); else for (j=sl-length-1;j=i -1;j-) sl-dataj+1=sl-dataj; sl-datai-1=x; sl-length+; ,算法分析,顺序表上的插入运算，时间主要消耗在了数据的移动上，在第

11、i个位置上插入 x ，从 ai 到 an 都要向下移动一个位置，共需要移动 ni1个元素。,共有 n1个位置可以插入。设在第i个位置上作插入的概率为Pi，则平均移动数据元素的次数：,设：Pi=1/ (n+1) ，即为等概率情况，则：,显然时间复杂度为O(n) 。,9、顺序表的删除算法 要求在顺序表中删除第i(1=i=n)个元素，使长度为n的线性表(a1,a2,ai,an)变为长度为n-1的线性表(a1,a2,.,ai-1,ai+1,an)。,算法,void ListDele(SqList *sl,int i) int j; if (isl-length) printf(“not exit!”)

12、; else for(j=i;jlength-1;j+) sl-data j -1=sl-data j ; sl-length- -; ,算法分析,与插入运算相同，其时间主要消耗在了移动表中元素上，删除第i个元素时，其后面的元素 ai+1an 都要向上移动一个位置，共移动了 n-i 个元素，所以平均移动数据元素的次数：,在等概率情况下，pi =1/ n，则：,显然该算法的时间复杂度为O(n)。,10、删除顺序表中的重复元素 清除顺序表中的重复元素，即删除重复元素中的多余元素，只保留其中序号最小的一个。例如:顺序表(2,4,4,3,2,4)清除重复元素后变为(2,4,3).,算法思路：让一个整型

13、变量 i 从头到尾扫描顺序表中的元素序号，当i定值于一个元素序号后，再用另一个整型变量 j 反向扫描元素序号n-1,i+1。当 j 定值于某一个序号后，就可以比较ai与aj，若ai=aj，则删除aj。所以，算法可用二重循环实现，外、内层的循环控制变量分别为i和j。,void DelSame(SqList *sl) int i,j; for(i=0;ilength;i+) j=sl-length-1; while(ji) if(sl-datai=sl-dataj) ListDele(sl,j+1); j - -; else j - -; ,直接调用删除函数,11、顺序表的划分算法 将顺序表 (a

14、1，a2，. ，an) 重新排列为以 a1 为界的两部分：a1 前面的值均比 a1 小，a1 后面的值都比 a1 大 。a1 也称为基准。,基本思路：从第二个元素开始到最后一个元素，逐一向后扫描：(1)当前数据元素 ai比 a1 大时，表明它已经在 a1 的后面，不必改变它与 a1 之间的位置，继续比较下一个。(2)当前结点若比 a1 小，说明它应该在 a1 的前面，此时将它上面的元素都依次向下移动一个位置，然后将它置入最上方。,void ListPart (SqList *sl) int i,j,x,y; x=sl-data0; for(i=1;ilength-1;i+) if(sl-dat

15、aidatai; for(j=i-1;j=0;j-) sl-dataj+1=sl-dataj; sl-data0=y; ,本节小结,线性表顺序存储结构特点：逻辑关系上相邻的 两个元素在物理存储位置上也相邻； 优点：可以随机存取表中任一元素；存储空间使用紧凑; 缺点：在插入，删除某一元素时，需要移动大量元素;预先分配空间需按最大空间分配，利用不充分;表容量难以扩充 为克服这一缺点，我们引入另一种存储形式：,2.3 线性表的链式存储,效率低，大量时间花费在元素位置的移动上；,临时扩大存储空间有困难，存储分配只能预先进行；,必须占用内存连续的地址空间。,顺序存储结构的缺陷,链表存储结构的特点,不需要用地址连续的存储单元来实现 ；,不要求逻辑上相邻的两个数据元素物理上也相邻 ；,通过“链”建立起数据元素之间的逻辑关系 ；,对线性表的插入、删除不需要移动数据元素。,引言,2.3 线性表的链式存储,什么是单链表？ 基于单链表的相关运算的实现,什么是单链表？,链表：通过一组任意的存储单元来存储线性表中的数据元素。,数据域,指针域,由于每个结点都只有一个指针域，如此构