扫码获取更多资源

●线性表的类型定义

线性表是最简单、最基本、最常用的一种线性结构，它的主要基本操作是插入、删除和查 找等。

●线性表的定义

在日常生活中，线性表的例子不胜枚举。

例如，英文字母表（A,B,・・・，Z）是一个线性表，表中的每个字母都是一个数据元素。

又如，一副扑克牌点数（2,3,・・・，10,J,Q,K,A）是一个线性表，表中的数据元素是每张 牌的点数。

再如，下表给出的学生成绩表是一个线性表，表中的每个学生所对应的一行信息是一 个数据元素，由姓名、学号、性别和成绩四个数据项组成。

学号 姓名 性别 成绩

001 孙晨 男 95

002 钱晓 女 85

003 常依 女 90

004 吴伟 男 88

005 范佩 男 93

综合上述例子，可以得到线性表定义：

线性表(Linear List)是n(n>0)个具有相同属性的数据元素组成的有限序列，即表中的 数据元素属于同一个数据对象，且相邻的数据元素之间存在着“序偶”关系。

(1)数据元素个数n称为线性表的长度(n = 0时称为空表)；

(2)将非空线性表(n>0)记为：(a], a2, a3»…，a”…，an);

(3)数据元素aj(lWiWn在不同情况下可以不同。

线性表是一个相当灵活的数据结构，其长度可以根据需要增长或缩短，即对线性表的数 据元素不仅可以进行访问操作，还可以进行插入和删除等操作。

●线性表的抽象数据类型

ADT List (

Data:

D= (a, |ax GElemSet, i = 1,2, - ,n, nN。}(具有相同类型的数据元素集合) Relation:

R={|ai_lzaieD,i = 2z -.,n}(相邻数据元素具有前驱和后继的关系) Operation:InitList(SL)

操作结果：构造一个空线性表L。DestroyList(&L)

初始条件：线性表L已经存在。

操作结果：销毁L。ClearList(SL)

初始条件：线性表L已经存在。

操作结果：重置L为空表。ListLength(L)

初始条件：线性表L已经存在。

操作结果：返回L中的数据元素个数。GetElem(Lz i, &e)

初始条件：线性表L已经存在，且l〈i〈ListLength(L) 0 操作结果：用e返回L中的第i个数据元素的值。LocateElem(L,e)

初始条件：线性表L已经存在。

操作结果：在L中查找第1个其值与e相等的数据元素，并返回该元素在L中的位序； 如果L中没有这样的数据元素，则返回值为0。Listlnsert( &L, i, e)

初始条件：线性表L已经存在/且1 ^i^ListLength(L) + lo 操作结果：在L中第i个位置之前插入新的数据元素e。ListDelete(&L, 1,&e)

初始条件：线性表L已经存在，且lWiWListLength(L)。

操作结果：删除L的第i个数据元素，并用e返回其值，且令L的长度减1。 TraverseList(L)

初始条件：线性表L已经存在。

操作结果：依次访问L中的每个数据元素。ADT List

联系我们：