资源描述：
《《数据结构与算法》第2课时 线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构与算法（C++语言版）第2章线性表线性表的类型定义基本概念线性表是由n（n≥0）个类型相同的数据元素组成的有限序列，通常表示为L=(a1,…,ai–1,ai,ai+1,…,an)。其中，L为线性表名称，ai为组成该线性表的数据元素，ai–1领先于ai，ai领先于ai+1，称ai–1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2,…,n–1时，ai有且仅有一个直接后继；当i=2,3,…,n时，ai有且仅有一个直接前驱。线性表的长度就是线性表中元素的个数n（n≥0）。当n=0时，称为空表。在非空表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素
2、，an是最后一个数据元素，ai是第i个数据元素。称i为数据元素ai在线性表中的位序。线性表的类型定义例如，某大学生命科学学院的学生名册可视为一个线性表，如图2.1所示，表中每个数据元素由学号、姓名、性别、年龄、院名称、系名称等数据项组成。从图2.1可以看出，学生名册线性表是一个相当灵活的数据结构，它的长度可根据需要增长或者缩短，即对线性表的数据元素不仅可访问，还可进行插入、删除等操作。线性表的类型定义抽象数据类型描述ADTLinearList{数据集合：D={ai
3、ai/ElemSet,i=1,2,…,n,n≥0}数据关系：R={
4、ai-1,ai/D,i=2
5、,…,n}数据操作：Init_List(&L)//初始化线性表,引用参数,操作对象本身输入：空。输出：构造一个空的线性表L。Destroy_List(&L)//撤销线性表输入：线性表L。输出：撤销线性表L。Clear_List(&L)//清空线性表输入：线性表L。输出：线性表L重置为空表。线性表的类型定义List_Empty(L)//判断线性表是否为空输入：线性表L。输出：若线性表L为空表，则返回TRUE，否则返回FALSE。List_Length(L)//求线性表的长度输入：线性表L。输出：线性表L中数据元素个数。Get_Elem(L,i,&e)//取线性表中第i个数据元素
6、的值输入：线性表L，1≤i≤ListLength(L)。输出：用e返回线性线L中第i个数据元素的值。LocateElem(L,e,compare())//返回给定值在线性表中的位置输入：线性表L，compare()是数据元素相等判定函数。输出：线性表L中第1个与e满足相等关系的数据元素的位序。若这样的数据元素不存在，则返回值为0。线性表的类型定义Prev_Elem(L,cur_e,&pre_e)//返回当前元素的前一个元素值输入：线性表L。输出：若cur_e是线性表L的数据元素，且不是第一个，则用pre_e返回它的直接前驱元素；否则操作失败，pre_e无定义。Next_Ele
7、m(L,cur_e,&next_e)//返回当前元素的后一个元素值输入：线性表L。输出：若cur_e是线性表L的数据元素，且不是最后一个，则用next_e返回它的直接后继元素；否则操作失败，next_e无定义。线性表的类型定义Insert_List(&L,i,e)//在线性表的第i个位置之前插入数据元素输入：线性表L，1≤i≤ListLength(L)+1。输出：在线性表L中第i个位置之前插入新的数据元素e，线性表L的长度加1。Delete_List(&L,i,&e)//删除线性表中第i个数据元素输入：线性表L非空，1≤i≤ListLength(L)。输出：删除L中第i个数据
8、元素，并用e返回其值，线性表L的长度减1。Traverse_List(L,visit())//遍历线性表输入：线性表L。输出：依次对线性表L的每个数据元素调用visit()进行访问。一旦visit()失败，则操作失败。}ADTLinearList线性表的类型定义线性表抽象类线性表的类型定义异常类NoMem和OutOfBounds如果分配内存失败，应引发一个异常。有时异常可能由new引发，而有时则需要编程者来引发。为了在所有情形下都能引发一个异常，本节定义一个异常类NoMem，非法操作将会简单地引发一个类型为NoMem的异常。另外，在删除操作中，为了从一个表中删除第k个元素，需
9、要先确认表中包含第k个元素，然后再删除这个元素。如果表中不存在第k个元素，则应出现一个越界异常，定义为OutOfBounds，每当正在执行的函数中任何一个参数超出所期望的范围时，就引发这种类型的异常。线性表的类型定义线性表的顺序存储结构基本概念线性表的顺序表示线性表的顺序表示，是指用一组地址连续的存储单元依次存储线性表中的数据元素。设a1的存储地址为Loc(a1)，每个数据元素占用d个字节存储单元，则第i个数据元素的地址为Loc(ai)=Loc(ai)+(i–1)×d，1≤i≤n，如图所示：线性表的顺序
