数据结构-线性表剖析.pptx

2 线性表 信息学院暑期培训 2 线性表 线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。在这种结构中： ① 存在一个唯一的被称为“第一个”的数据元素； ② 存在一个唯一的被称为“最后一个”的数据元素； ③ 除第一个元素外，每个元素均有唯一一个直接前驱； ④ 除最后一个元素外，每个元素均有唯一一个直接后继。 2.1 线性表的逻辑结构 线性表(Linear List) ：是由n(n≧0)个数据元素(结点)a1，a2， …an组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。 当n=0时，称为空表。 当n0时，将非空的线性表记作： (a1，a2，…an) a1称为线性表的第一个(首)结点，an称为线性表的最后一个(尾)结点。 2.1.1 线性表的定义 a1，a2，…ai-1都是ai(2≦i≦n)的前驱，其中ai-1是ai的直接前驱; ai+1，ai+2，…an都是ai(1≦i ≦n-1)的后继，其中ai+1是ai的直接后继。 2.1.2 线性表的逻辑结构 线性表中的数据元素ai所代表的具体含义随具体应用的不同而不同，在线性表的定义中，只不过是一个抽象的表示符号。 ◆ 线性表中的结点可以是单值元素(每个元素只有一个数据项) 。 例1: 26个英文字母组成的字母表： (A，B，C、…、Z） 例2 ： 某校从1978年到1983年各种型号的计算机拥有量的变化情况：(6，17，28，50，92，188） 例3 ： 一副扑克的点数 (2，3，4，…，J，Q，K，A) 2.1.2 线性表的逻辑结构 ◆ 线性表中的结点可以是记录型元素，每个元素含有多个数据项 ，每个项称为结点的一个域 。每个元素有一个可以唯一标识每个结点的数据项组，称为关键字。 例4 ： 某校2001级同学的基本情况：{(‘2001414101’，‘张里户’，‘男’，06/24/1983)， (‘2001414102’，‘张化司’，‘男’，08/12/1984) …， (‘2001414102’，‘李利辣’，‘女’，08/12/1984) } ◆若线性表中的结点是按值(或按关键字值)由小到大(或由大到小)排列的，称线性表是有序的。 2.1.3 线性表的抽象数据类型定义 ◆ 线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。 ◆ 对线性表的数据元素可以访问、插入和删除。 2.1.3 线性表的抽象数据类型定义 ADT List { 数据对象： 数据关系： 基本操作： InitList(L) /*初始化线性表*/ DestroyList(L) /*销毁线性表*/ ListEmpty(L) /*判断是否为空线性表*/ ...... } 2.1.3 线性表的抽象数据类型定义 2.2 线性表的顺序存储 顺序存储 ：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。 顺序存储的线性表的特点： ◆ 线性表的逻辑顺序与物理顺序一致; ◆ 数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。 设有非空的线性表：(a1，a2，…an) 。顺序存储如图2-1所示。 2.2.1 线性表的顺序存储结构 在具体的机器环境下：设线性表的每个元素需占用L个存储单元，以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系： LOC(ai+1)=LOC(ai)+L 线性表的第i个数据元素ai的存储位置为： LOC(ai)=LOC(a1)+(i-1)*L 2.2 线性表的顺序存储 在高级语言(如C语言)环境下：数组具有随机存取的特性，因此，借助数组来描述顺序表。除了用数组来存储线性表的元素之外，顺序表还应该有表示线性表的长度属性，所以用结构类型来定义顺序表类型。 #define OK 1 /*预定义正确标识*/ #define ERROR -1 /*预定义错误标识*/ #define MAX_SIZE 100 /*预定义数组长度*/ typedef int Status ; /*声明元素类型*/ typedef int ElemType ; /*声明数据