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