购买
下载掌阅APP,畅读海量书库
立即打开
畅读海量书库
扫码下载掌阅APP

3.1 线性表的定义及抽象数据类型

线性表 (Linear_List)是最简单且最常用的一种线性结构。本节主要介绍线性表的逻辑结构及在线性表上的运算。

3.1.1 线性表的逻辑结构

线性表 是由n个类型相同的数据元素组成的有限序列,记为(a 1 ,a 2 ,…,a i-1 ,a i ,a i+1 ,…,a n )。其中,这里的数据元素可以是原子类型,也可以是结构类型。线性表的数据元素存在着序偶关系,即数据元素之间具有一定的次序。在线性表中,数据元素a i-1 在a i 的前面,a i 又在a i+1 的前面,可以把a i-1 称为a i 的直接前驱元素,a i 称为a i+1 的直接前驱元素。a i 称为a i-1 的直接后继元素,a i+1 称为a i 的直接后继元素。

线性表的逻辑结构如图3-1所示。

图3-1 线性表的逻辑结构

我们学过的英文单词就是简单的线性表,例如“China”、“Science”、“Structure”。其中每一个英文字母就是一个数据元素,每个数据元素之间存在着唯一的顺序关系。如“China”中字母C后面是字母h,字母h后面是字母i。

在较为复杂的线性表中,一个数据元素可以由若干个数据项组成,在表3-1所示的一所学校的教职工情况表中,一个数据元素由姓名、性别、出生年月、籍贯、学历、职称及任职时间7个数据项组成。数据元素也称为记录。

表3-1 教职工情况表

知识点 在线性表中,除了第一个元素a 1 ,每个元素有且仅有一个直接前驱元素;除了最后一个元素a n ,每个元素有且只有一个直接后继元素。

3.1.2 线性表的抽象数据类型

线性表的抽象数据类型包括数据对象集合和基本操作集合。

1.数据对象集合

线性表的数据对象集合为{a 1 ,a 2 ,…,a n },元素类型为DataType。

数据元素之间的关系是一对一的关系。除了第一个元素a 1 外,每个元素有且只有一个直接前驱元素,除了最后一个元素a n 外,每个元素有且只有一个直接后继元素。

2.基本操作集合

(1)InitList(&L):初始化操作,建立一个空的线性表L。这就像是在日常生活中,一所院校为了方便管理,建立一个教职工基本情况表,准备登记教职工信息。

(2)ListEmpty(L):若线性表L为空,返回1,否则返回0。这就像是刚刚建立了教职工基本情况表,还没有登记教职工信息。

(3)GetElem(L,i,&e):返回线性表L的第i个位置元素值给e。这就像在教职工基本情况表中,根据给定序号查找某个教师信息。

(4)LocateElem(L,e):在线性表L中查找与给定值e相等的元素,如果查找成功返回该元素在表中的序号表示成功,否则返回0表示失败。这就像在教职工基本情况表中,根据给定的姓名查找教师信息。

(5)InsertList(&L,i,e):在线性表L中的第i个位置插入新元素e。这就类似于经过招聘考试,引进了一名教师,这个教师信息登记到教职工基本情况表中。

(6)DeleteList(&L,i,&e):删除线性表L中的第i个位置元素,并用e返回其值。这就像某个教职工到了退休年龄或者调入其他学校,需要将该教职工从教职工基本情况表中删除。

(7)ListLength(L):返回线性表L的元素个数。这就像查看教职工基本情况表中有多少个教职工。

(8)ClearList(&L):将线性表L清空。这就像学校被撤销,不需要再保留教职工基本信息,将这些教职工信息全部清空。 fDH9MbCcTOnOhx6eBhOkYvFbdzlE+Wxf0EfHfWTKxZqRTFF1+dYY4hgB7CHXsSvN

点击中间区域
呼出菜单
上一章
目录
下一章
×