文档介绍：本章主题:线性表的有关概念和基本运算
教学目的:掌握线性表的概念和类型定义
教学重点:线性表的顺序存储结构和链式存储结构
教学难点:线性表的基本运算
第2章线性表
2017/12/5
1
线性表(Linear list)是最简单且最常用的一种数据结构。这种结构具有下列特点:存在一个唯一的没有前驱的(头)数据元素;存在一个唯一的没有后继的(尾)数据元素;此外,每一个数据元素均有一个直接前驱和一个直接后继数据元素。
通过本章的学习,读者应能掌握线性表的逻辑结构和存储结构,以及线性表的基本运算以及实现算法。
本章学习导读
2017/12/5
2
线性表由一组具有相同属性的数据元素构成。数据元素的含义广泛,在不同的具体情况下,可以有不同的含义。
1 . 线性表的定义
线性表L是n(n≥0)个具有相同属性的数据元素a1,a2,a3,…,an组成的有限序列,其中序列中元素的个数n称为线性表的长度。
当n=0时称为空表,即不含有任何元素。
常常将非空的线性表(n>0)记作:
(a1,a2,…an)
这里的数据元素 ai(1≦i≦n)只是一个抽象的符号,其具体含义在不同的情况下可以不同。
线性表的基本概念
2017/12/5
3
例1、26个英文字母组成的字母表
(A,B,C、…、Z)
例2、从1978年到1983年各种型号的计算机拥有量的变化情况。
(6,17,28,50,92,188)
例3、
2017/12/5
4
从以上例子可看出线性表的逻辑特征是:
在非空的线性表,有且仅有一个开始结点a1,它没有直接前趋,而仅有一个直接后继a2;
有且仅有一个终端结点an,它没有直接后继,而仅有一个直接前趋a n-1;
其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋a i-1和一个直接后继a i+1。
线性表是一种典型的线性结构。
数据的运算是定义在逻辑结构上的,而运算的具体实现则是在存储结构上进行的。
2017/12/5
5
2 . 线性表的基本运算
数据结构的运算是定义在逻辑结构层次上的,而运算的具体实现则是建立在存储结构上的。
(1) 初始化线性表Initlist(L)
将线性表L置为空表。
(2) 求线性表的长度Getlen(L)
求解并返回线性表所含元素的个数n。若线性表为空,则返回整数0。
(3) 按序号取元素Getelem(L,i)
读取线性表L第i个数据元素,要求满足1≤i≤Getlen(L)。
2017/12/5
6
(4) 按值查找Locate(L,x)
在线性表L中查找值为x的数据元素,若查找成功则返回第一个值为x的元素的序号或地址; 否则,在L中未找到值为x的数据元素,返回一特殊值(例如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),删除后表长减1。
2017/12/5
7
线性表的顺序结构及运算实现
线性表有两种基本的存储结构:顺序存储结构和链式存储结构。

顺序表具有以下两个基本特点:
(1) 线性表的所有元素所占的存储空间是连续的。
(2) 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
由于线性表的所有数据元素属于同一数据类型,所以每个元素在存储器中占用的空间(字节数)相同。因此,要在此结构中查找某一个元素是很方便的,即只要知道顺序表首地址和每个数据元素在内存所占字节的大小,就可求出第i个数据元素的地址。
2017/12/5
8
假设线性表中的第一个数据元素的存储地址(首地址)为LOC(a1),每一个数据元素占k个字节,则各元素的存储地址有如下关系:
LOC(a2)=LOC(a1)+k
LOC(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)在计算机中的结构如下:
2017/