数据结构-线性表

凌阳教育

一般来说，用计算机解决一个具体问题时，大致需要经过以下几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序，进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找住这些操作对象之间含有的关系，然后用数学的语言加以描述。例如，求解梁架结构中应力的数学模型为线性方程组；预报人口增长情况的数学模型为微分方程。然而，更多的非数值计算问题无法用书写方程加以描述。

2.线性表

线性结构的特点是：在数据元素的非空有限集中，（1）存在惟一的一个被称做“第一个”的数据元素；（2）存在惟一的一个被称做“最后一个”的数据元素；（3）除第一个之外，集合中的每个数据元素均只有一个前驱；（4）除最后一个之外，集合中每个数据元素只有一个后继。

线性表的类型定义

数据表示最常见且最简单的一种数据结构。简言之，一个线性表是n个数据元素的有限序列。至于每个元素的具体含义，在不同的情况下各不相同，它可以是一个数或一个符号，也可以是一页书，甚至其他更复杂的信息。例如：26个英文字母的字母表：

（A,B,C,…,Z）

是一个线性表，表中的数据元素是单个字母字符。又如，某校从1978年到1983年各种型号的计算机拥有量的变化情况，可以用线性表的形式给出：

（6,17,28,50,92,188,）

表中的数据元素是整数。

在稍复杂的线性表中，一个数据元素可以是由若干个数据项组成。在这种情况下，常把数据元素成为记录，含有大量记录的线性表又称为文件。

例如，一个学校的学生健康情况登记表如图所示，表中每个学生的情况为一个记录，它由姓名、学号、性别、年龄、班级和健康状况等6个数据项组成。

姓名	学号	性别	年龄	班级	健康状况
王小林	790631	男	18	计91	健康
陈红	790632	女	20	计92	一般
李建平	790633	男	21	计93	健康
张立立	7900634	男	17	计94	神经衰弱

学生健康情况登记

综合上述3个例子可见，线性表中的数据元素可以是各种各样的，但同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。若将线性表记为

（a1，…，ai-1,ai,ai+1，…，an）

则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2，…，n-1时，有且仅有一个直接后继，当i=2,3，…，n时，ai有且仅有一个直接前驱。

线性表中元素的个数n(n≥0)定义为线性表的长度，n=0时为空表。在非空表中的每个数据元素都有一个确定的位置，如ai是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素，称i为数据元素ai在线性表中的位序。

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

抽象数据类型线性表的定义如下：

ADT List

数据对象：D={ai|ai?ElemSet，i=1,2，…，n，n≥0}

数据关系：R1={《ai-1，ai>| ai-1，ai?D，i=2，…，n}

基本操作：

InitList（&L）

操作结果：构造一个空的线性列表L。

DestroyList（&L）

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

操作结果：销毁线性表L。

ClearList（&L）

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

操作结果：将L重置为空表。

ListEmpty（L）

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

操作结果：若L为空表，则返回TRUE，否则返回FALSE。

GetElem（L，i，&e）

初始条件：线性表L已存在，1≤i≤ListLength（L）。

操作结果：用e返回L中第i个数据元素的值。

LocateElem（L，e，compare）

厨师条件：线性表L已存在，compare（）是数据元素判定函数。

操作结果：返回L中第1个与e满足条件compare（）数据元素的位序。若这样的数据元素不存在，则返回值为0.

PriorElem（L，cur-e，&pre-e）

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

操作结果：若cur-e是L的数据元素，且不是第一个，则用pre-e返回它的前驱，否则操作失败，pre-e无定义。

NextElem（L，cur-e，&pre-e）

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

操作结果：若cur-e是L的数据元素，且不是第一个，则用pre-e返回它的后继，否则操作失败，pre-e无定义。

ListInsert（&L，i，e）

初始条件：线性表L已存在，1≤i≤ListLength（L）+1.

操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1.

ListDelete（&L，i，e）

初始条件：线性表L已存在且非空，1≤i≤ListLength（L）。

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

ListTraverse（L，visit）

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

操作结果：依次对L的每个数据元素调用visit（）。一旦visit（）失败，则操作失效。

}ADT List

对上述定义的抽象数据类型线性表，还可进行一些更复杂的操作，例如，将两个或两个以上的线性表合并成一个线性表；把一个线性表拆开成两个或两个以上的线性表；重新复制一个线性表等。

凌阳教育，全国唯一一家原厂式嵌入式培训机构，专业从事嵌入式人才培训13年，最近新开课程信息安全工程师培训，想了解更多嵌入式资料下载或者是凌阳教育的动态，请访问凌阳教育官网www.sunplusedu.com。

yangzikai

回复 1# 凌阳教育


        lihai