第1.3章数据结构——线性结构.ppt

第一篇 数据结构 第3章 线性结构 章节内容 3.1 线性表 3.1.1 线性表的定义 线性表(Linear-list)是n(n≥0)个相同类型数据元素的有限序列。记为： (a1，a2, ..., an) 其中，数据元素个数n称为表的长度，n=0时，称此线性表为空表。一个非空线性表有如下一些结构特征： ① 有且只有一个根结点a1，它无前件。 ② 有且只有一个终端结点an，它无后件。 ③ 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。 线性表的结构仅涉及诸元素的线性相对位置，即第i个元素ai处在第i-1个元素ai-1的后面和第i+1个元素ai+1的前面，这种位置上的有序性就是一种线性关系，所以线性表是一种线性结构。 线性表中每个数据元素ai的具体含义，在不同情况下各不相同，它可以是一个数，或是一个符号，也可以是一页书，甚至是其它更复杂的信息。但在同一个线性表中的数据元素必须具有相同的特性(或者说具有相同的类型)。 线性表的逻辑结构：若线性表是非空表，则第一个元素a1无前趋，最后一个元素an无后继，其它元素ai(1in)均只有一个直接前驱ai-1和一个直接后继ai+1。下面给出几个线性表的例子： Example 3.1：线性表示例。 1、26个大写的英文字母表：(A，B，C，...，Z) 2、某校从1996年到2002年各种型号计算机拥有量的变化情况，可以用线性表给出： (200，220，250，300，400，700，1200) 3.1.2 线性表的基本运算 线性表是一个相当灵活的数据结构，它的长度可以根据需要增减，操作也比较灵活方便。线性表的基本操作有以下几种： (1) SETNULL(L)。初始化操作，设定一个空的线性表L。 (2) LENGTH(L)。求表长，求出线性表L中数据元素个数。 (3) GET(L，i)。取元素函数，若1≤i≤LENGTH(L)， 则函数值为给定线性表L中第i个数据元素，否则为空元素NULL。 (4) PRIOR(L，elm)。求前趋函数，若elm的位序大于1，则函数值为elm的前趋，否则为空元素。 (5) NEXT(L，elm)。求后继函数，若elm的位序小于LENGTH(L)，则函数值为elm的后继，否则为空元素。 (6) LOCATE(L，x)。定位函数，返回元素x在线性表L中的位置。若L中有多个x，则只返回第一个x的位置，若在L中不存在x，则返回0。 (7) INSERT(L，i，x)。插入操作，在线性表L中的第i个位置上插入元素x，运算结果使得线性表的长度增加1。 (8) DELETE(L，i)。删除操作，若1≤i≤LENGTH(L)，删除给定线性表L中的第i个数据元素，使得线性表的长度减1。 (9) EMPTY(L)。判空表函数，若L为空表，则返回布尔值“true”，否则返回布尔值“false”。 对线性表还有一些更为复杂的操作，如将两个线性表合并成一个线性表；把一个线性表拆分成两个或两个以上的线性表；重新复制一个线性表；对线性表中的元素按值的大小重新排序等。这些运算都可以通过上述基本运算来实现。 3.1.3 线性表的顺序存储 顺序表的定义 在计算机内可以用不同的方式来表示线性表，其中最简单和最常用的方式是用一组地址连续的存储单元依次存储线性表中的元素。线性表的顺序存储是最简单的存储结构，一般称为顺序表。 线性表的顺序存储结构就是将线性表的元素按其逻辑次序依次存放在一组地址连续的存储单元里。 设有线性表(a1，a2，...，an)，若1个数据元素只占1个存储单元，用Loc表示某元素的地址，则线性表中第i个数据元素的存储地址为： Loc(ai)= Loc(a1)+(i-1) 其中，Loc(a1)是线性表第一个数据元素的存储地址，通常称做线性表的起始地址或者基地址。若1个数据元素占d个存储单元，则有 Loc(ai)= Loc(a1)+(i-1)*d Loc(ai+1)= Loc(ai)+ d 可见，线性表中每个元素的存储地址是该元素在表中序号的线性函数。只要确定了线性表的起始地址，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。 在C语言中，可用一维数组来描述顺序存储结构。 顺序表的数据结构定义 # define maxsize 1024; //顺序表中最多容纳元素个