第三讲线性表的定义

《第三讲线性表的定义》由会员分享，可在线阅读，更多相关《第三讲线性表的定义（26页珍藏版）》请在装配图网上搜索。

1、第三讲 线性表的定义及逻辑结构本讲主要内容：本讲主要内容：一、线性表的定义一、线性表的定义二、线性表的逻辑结构二、线性表的逻辑结构三、线性表的抽象类型定义三、线性表的抽象类型定义1学生成绩登记表学生成绩登记表姓姓 名名英语英语数据结构数据结构高数高数学号学号丁一丁一9678870101李二李二8790780102张三张三6786860103孙红孙红6981960104王冬王冬87746601052职工工资登记表职工工资登记表姓姓 名名岗位津贴岗位津贴基本工资基本工资奖金奖金职工号职工号丁一丁一6002782000101李二李二3001901000102张三张三3001861000103孙红孙红

2、5002182000104王冬王冬3001901000105数据元素之间的关系是什么？数据元素之间的关系是什么？3线性表：线性表：简称表，是简称表，是n（n0）个具有）个具有相同类型相同类型的数的数据元素的据元素的有限序有限序列列。线性表的长度：线性表的长度：线性表中数据元素的个数线性表中数据元素的个数,一般用一般用n n表表示示,n0 。空表：空表：长度等于零的线性表，即长度等于零的线性表，即n=0,记为：记为：L=()。线性表的定义4非空表非空表记为：记为：L（a1,a2,ai-1,ai,an)ai（1in）称为数据元素；）称为数据元素；下角标下角标 i 表示该元素在线性表中的位置或序号表

3、示该元素在线性表中的位置或序号。a1是表中第一个元素是表中第一个元素,称为表头元素称为表头元素;a2是表中第二个元素是表中第二个元素;an是最后一个元素是最后一个元素,称为表尾元素称为表尾元素;线性表中各元素在位置上是有序的线性表中各元素在位置上是有序的,这种有序就称为这种有序就称为线性关系线性关系.线性表的定义5例如：例如：L1=()：L1L1是一个空的线性表；是一个空的线性表；L2=(a,b,c,d,e)：L2L2线线性性表表中中有有5 5个个元元素素，其其长长度度为为5 5。a a是是表表头头元元素素、e e是是表表尾尾元元素素。c c的的直直接接前前驱驱元元素素是是b b，c c的的直

4、直接接后后继继元元素素是是d d。a a元元素素的序号是的序号是1 1，c c元素的序号是元素的序号是3 3。线性表的定义6a1a3a4ana2线性表（线性表（a1,a2,ai-1,ai,an)的图形表示如下：的图形表示如下：线性表的图形表示元素元素ai 和和ai+1之间的先后关系用之间的先后关系用表示表示.7线性表（线性表（a1,a2,ai-1,ai,an)的二元组表示如的二元组表示如下：下：线性表的二元组表示线性表线性表L=(D,R),其中其中D=ai|1in,n0,ai 属于ElemType类型R=rR=|1in-1注意:ElemType类型是C+的类型标识符,代表某种类型.8a1a3a

5、4ana21.有限性：线性表中数据元素的个数是有穷的。有限性：线性表中数据元素的个数是有穷的。2.相同性：线性表中数据元素的类型是同一的。相同性：线性表中数据元素的类型是同一的。3.顺序性：线性表中相邻的数据元素顺序性：线性表中相邻的数据元素ai-1和和ai之间存在之间存在序偶关系序偶关系，即，即ai-1是是ai的前驱，的前驱，ai是是ai-1的后继；的后继；a1 无前驱，无前驱，an无后继，其它每个元素有且仅有一个前无后继，其它每个元素有且仅有一个前驱和一个后继。驱和一个后继。线性表的特性9线性表的抽象数据类型定义ADT List数据对象数据对象:D=ai|1in,n0,ai 属于属于Ele

6、mType类型类型/ElemType是是C+的类型标识符的类型标识符数据关系数据关系:R=|ai,ai+1D,i=1,n-1线性表的抽象数据类型定义线性表的抽象数据类型定义10基本运算基本运算:InitList(&L)初始化线性表：构造一个空的线性表初始化线性表：构造一个空的线性表L。前置条件前置条件：表不存在：表不存在 输入输入：无：无 功能功能：表的初始化：表的初始化 输出输出：无无 后置条件后置条件：建一个空表：建一个空表线性表的抽象数据类型定义线性表的抽象数据类型定义11DestroyList(&L)销毁线性表销毁线性表:释放线性表释放线性表L占用的内存空间。占用的内存空间。前置条件前

7、置条件：表已存在：表已存在 输入输入：无：无 功能功能：销毁表：销毁表 输出输出：无：无 后置条件后置条件：释放表所占用的存储空间：释放表所占用的存储空间线性表的抽象数据类型定义线性表的抽象数据类型定义12ListEmpty(L)判判断断线线性性表表是是否否为为空空：若若L为为空空表表，则则返返回回真真，否则返回假。否则返回假。前置条件前置条件：表已存在：表已存在 输入输入：无：无 功能功能：判断表是否为空：判断表是否为空 输出输出：若是空表，返回：若是空表，返回1，否则返回，否则返回0 后置条件后置条件：表不变：表不变线性表的抽象数据类型定义线性表的抽象数据类型定义13ListLength(

8、L)求线性表的长度：返回求线性表的长度：返回L中元素的个数。中元素的个数。前置条件前置条件：表已存在：表已存在 输入输入：无：无 功能功能：求表的长度：求表的长度 输出输出：表中数据元素的个数：表中数据元素的个数 后置条件后置条件：表不变：表不变线性表的抽象数据类型定义线性表的抽象数据类型定义14DispList(L)输输出出线线性性表表：当当线线性性表表L不不为为空空时时，顺顺序序显显示示L中各结点的值域。中各结点的值域。前置条件前置条件：表已存在：表已存在 输入输入：无：无 功能功能：顺序显示：顺序显示L中各结点的值域中各结点的值域 输输出出：若若是是空空表表，直直接接返返回回；否否则则顺

9、顺序序显显示示表表中各结点的值域中各结点的值域 后置条件后置条件：表不变：表不变线性表的抽象数据类型定义线性表的抽象数据类型定义15GetElem(L,I,&e)求线性表中某个数据元素值：用求线性表中某个数据元素值：用e 返回返回L中第中第i(1iListLength(L)个元素的值。个元素的值。前置条件前置条件：表已存在：表已存在 输入输入：元素的序号：元素的序号i 功能功能：在表中取序号为：在表中取序号为i的数据元素的数据元素 输出输出：若：若i合法，返回序号为合法，返回序号为i的元素值，否则抛出异常的元素值，否则抛出异常 后置条件后置条件：表不变：表不变线性表的抽象数据类型定义线性表的抽

10、象数据类型定义16LocateElem(L,e)按按元元素素值值查查找找:返返回回L中中第第1个个值值域域与与e相相等等的的位位序序。若若这这样样的元素不存在，则返回值为的元素不存在，则返回值为0。前置条件前置条件：表已存在：表已存在 输入输入：数据元素：数据元素e 功能功能：在线性表中查找值等于：在线性表中查找值等于e的元素的元素 输出输出：若查找成功，返回：若查找成功，返回e在表中的序号，否则返回在表中的序号，否则返回0 后置条件后置条件：表不变：表不变线性表的抽象数据类型定义线性表的抽象数据类型定义17ListInsert(&L,i,e)插插入入数数据据元元素素：在在L的的第第i(1iL

11、istLength(L)+1)个个元元素之前插入新的元素素之前插入新的元素e，L的长度增的长度增1。前置条件前置条件：表已存在：表已存在输入输入：插入：插入i；待插入的元素；待插入的元素e功能功能：在表的第：在表的第i个位置处插入一个新元素个位置处插入一个新元素e输出输出：若插入不成功，抛出异常：若插入不成功，抛出异常 后后置置条条件件：若若插插入入成成功功，表表中中增增加加一一个个新新元元素素，表表长增长增1线性表的抽象数据类型定义线性表的抽象数据类型定义18ListDelete(&L,i,&e)删删除除数数据据元元素素：删删除除L的的第第i(1iListLength(L)个个元元素，并用素

12、，并用e返回其值，返回其值，L的长度减的长度减1。前置条件前置条件：表已存在：表已存在输入输入：删除位置：删除位置i功能功能：删除表中的第：删除表中的第i个元素个元素 输出输出：若删除成功，用：若删除成功，用e返回被删元素，否则抛出返回被删元素，否则抛出异常异常 后后置置条条件件：若若删删除除成成功功，表表中中减减少少一一个个元元素素，表表长长减减1线性表的抽象数据类型定义线性表的抽象数据类型定义19进一步说明进一步说明:（1 1）线性表的基本操作根据实际应用是而定；）线性表的基本操作根据实际应用是而定；（2）复杂的操作可以通过基本操作的组合来实现；）复杂的操作可以通过基本操作的组合来实现；（

13、3）对不同的应用，操作的接口可能不同。）对不同的应用，操作的接口可能不同。线性表的抽象数据类型定义线性表的抽象数据类型定义20线性表的抽象数据类型定义线性表的抽象数据类型定义例例1 1：有一个线性表：有一个线性表L=(a,c,a,d,b)L=(a,c,a,d,b)，求求ListLength(L)ListLength(L)、ListEmpty(L)ListEmpty(L)、GetElem(L,3,e)GetElem(L,3,e)、LocateElem(L,a)LocateElem(L,a)、ListInsert(L,4,e)ListInsert(L,4,e)、ListDelete(L,3)Lis

14、tDelete(L,3)等基本运算的执行结果。等基本运算的执行结果。21线性表的抽象数据类型定义线性表的抽象数据类型定义解答：ListLength(L)=5ListEmpty(L)=0GetElem(L,3,e)，e=aLocateElem(L,a)=1ListInsert(L,4,e),L=(a,c,a,e,d,b)ListDelete(L,3),L=(a,c,e,d,b)22线性表的抽象数据类型定义线性表的抽象数据类型定义例例2 2：假设有两个集合：假设有两个集合A A和和B B分别用两个线性表分别用两个线性表LALA和和LBLB表示，即线性表中的数据元素为集合中的成员。表示，即线性表中的

15、数据元素为集合中的成员。编写一个算法求一个新的集合编写一个算法求一个新的集合C=ABC=AB，即将两个集，即将两个集合的并集放在线性表合的并集放在线性表LCLC中。中。CBA23线性表的抽象数据类型定义线性表的抽象数据类型定义思路如下：思路如下：先创建一个新的线性表先创建一个新的线性表LCLC，将，将LALA中的所有元素复制中的所有元素复制到到LCLC中，然后扫描线性表中，然后扫描线性表LBLB，若，若LBLB的当前元素不在的当前元素不在线性表线性表LALA中，则将其插入到线性表中，则将其插入到线性表LCLC中。中。24线性表的抽象数据类型定义线性表的抽象数据类型定义算法：算法：void un

16、ionList(List LA,List LB,List&LC)void unionList(List LA,List LB,List&LC)int lena,i;int lena,i;ElemType e;ElemType e;InitList(LC);/InitList(LC);/创建一个空的线性表创建一个空的线性表LCLCfor(i=1;i=ListLength(LA);i+)for(i=1;i=ListLength(LA);i+)GetElem(LA,i,e);/GetElem(LA,i,e);/取得取得LALA中第中第i i个元素的值个元素的值ListInsert(LC,i,e);L

17、istInsert(LC,i,e);/将该值插入到将该值插入到LCLC中对应的位置上中对应的位置上 25线性表的抽象数据类型定义线性表的抽象数据类型定义Lena=ListLength(LA);/Lena=ListLength(LA);/取得线性表取得线性表LALA的长度的长度for(i=1;i=ListLength(LB);i+)for(i=1;i=ListLength(LB);i+)GetElem(LB,i,e);/GetElem(LB,i,e);/取取LBLB中第中第i i个数据元素，赋给个数据元素，赋给e eif(!LocateElem(LA,e)if(!LocateElem(LA,e)ListInsert(LC,+lena,e);ListInsert(LC,+lena,e);/若若LALA中不存在和中不存在和e e相同者，则插入到相同者，则插入到LCLC中中 算法的时间复杂度为算法的时间复杂度为O(nO(n2 2)26