资源描述：
《数据结构02.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、本章主题：线性表的有关概念和基本运算教学目的：掌握线性表的概念和类型定义教学重点：线性表的顺序存储结构和链式存储结构教学难点：线性表的基本运算第2章线性表2021/7/171线性表（Linearlist）是最简单且最常用的一种数据结构。这种结构具有下列特点：存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的没有后继的（尾）数据元素；此外，每一个数据元素均有一个直接前驱和一个直接后继数据元素。通过本章的学习，读者应能掌握线性表的逻辑结构和存储结构，以及线性表的基本运算以及实现算法。本章学习导读2021/7/172
2、线性表由一组具有相同属性的数据元素构成。数据元素的含义广泛，在不同的具体情况下，可以有不同的含义。1.线性表的定义线性表L是n（n≥0）个具有相同属性的数据元素a1，a2，a3，…，an组成的有限序列，其中序列中元素的个数n称为线性表的长度。当n=0时称为空表，即不含有任何元素。常常将非空的线性表(n>0)记作：(a1，a2，…an)这里的数据元素ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。2.1线性表的基本概念2021/7/173例1、26个英文字母组成的字母表（A，B，C、…、Z）例
3、2、从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）例3、2021/7/174从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。2021/7/1
4、752.线性表的基本运算数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现则是建立在存储结构上的。(1)初始化线性表Initlist(L)将线性表L置为空表。(2)求线性表的长度Getlen(L)求解并返回线性表所含元素的个数n。若线性表为空，则返回整数0。(3)按序号取元素Getelem(L,i)读取线性表L第i个数据元素，要求满足1≤i≤Getlen(L)。2021/7/176(4)按值查找Locate(L,x)在线性表L中查找值为ｘ的数据元素，若查找成功则返回第一个值为x的元素的序号或地址;否则，在L中
5、未找到值为ｘ的数据元素，返回一特殊值（例如0），表示查找失败。(5)插入元素Inselem(L,i,x)在线性表L的第i个位置上插入一个值为x的新元素，这样使原序号为i,i+1,...,n的数据元素的序号变为i+1,i+2,...,n+1，要求1≤i≤Getlen(L)+1，插入后原表长增1。(6)删除元素Delelem(L,i)在线性表L中删除序号为i的数据元素，删除后使序号为i+1,i+2,...,n的元素变为序号i,i+1,...,n-1，要求1≤i≤Getlen(L)，删除后表长减１。2021/7/1772
6、.2线性表的顺序结构及运算实现线性表有两种基本的存储结构：顺序存储结构和链式存储结构。1.线性表的顺序存储结构顺序表具有以下两个基本特点：(1)线性表的所有元素所占的存储空间是连续的。(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。由于线性表的所有数据元素属于同一数据类型，所以每个元素在存储器中占用的空间（字节数）相同。因此，要在此结构中查找某一个元素是很方便的，即只要知道顺序表首地址和每个数据元素在内存所占字节的大小，就可求出第i个数据元素的地址。2021/7/178假设线性表中的第一个数据元素的存储
7、地址（首地址）为LOC(a1)，每一个数据元素占k个字节，则各元素的存储地址有如下关系：LOC（a2）=LOC(a1)＋kLOC（a3）=LOC(a2)＋k……LOC（ai）=LOC(ai-1)＋k （2≤i≤n）……因此，线性表中第i个元素ai在计算机中的存储地址为：LOC(ai)=LOC(a1)+(i-1)×k（1≤i≤n）即在顺序存储结构中，线性表中每一个数据元素在计算机存储空间中的存储地址由该元素在线性表中的序号惟一确定。一般来说，长度为n的线性表(a1，a2，…，an)在计算机中的结构如下：2021/
8、7/1792021/7/1710在具体实现时，一般用高级语言中的数组来对应连续的存储空间。设最多可存储MaxLen个元素，在C语言中可用数组data[MaxLen]来存储数据元素，为保存线性表的长度需定义一个整型变量length。线性表的第l，2，…，n个元素分别存放在此数组下标为0，1，…，length-1数组元素中，如下图所示2021/7/1711这样，
