资源描述：
《算法与数据结构讲义第2章新ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、线性结构的基本特征为:1．集合中必存在唯一的一个“第一元素”；2．集合中必存在唯一的一个“最后元素”；3．除最后元素在外，均有唯一的后继；4．除第一元素之外，均有唯一的前驱。线性结构是一个数据元素的有序（次序）集线性表是一种最简单的线性结构2.1线性表的类型定义2.3线性表类型的实现链式存储2.4一元多项式的表示2.2线性表类型的实现顺序存储2.1线性表的类型定义线性表是一种最简单的数据结构，它是一种线性结构。线性表是n(n>=0)个数据元素的有限序列，通常记为：(a1，a2，…ai-1，ai，ai+1，…an)其中:同一线性表中的数
2、据元素必须具有相同数据类型，ai是线性表的第i个元素，称i为数据元素ai的序号相邻数据元素间存在序偶关系：将ai-1称为ai的直接前趋，ai+1称为ai的直接后继。a1是表中第一个元素，它没有前趋；an是最后一个元素无后继；其余有且仅有一个直接前趋，有且仅有一个直接后继n为表长，n＝0时称为空表（）。2.1线性表的逻辑结构线性表的数据元素，或者叫结点，或者叫记录，是独立的信息。它可以是一个数：例某校从1978年到1983年各种型号的计算机拥有量的变化情况可以用线性表表示为：（6，17，28，50，92，188）或一个符号，如英文字母表（A
3、，B，…，Z）；也可以由若干个数据项组成：如：学生健康情况登记表如下：姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17神经衰弱线性表的其他表示方式:二元组表示L=，其中D={a1,a2,a3,...an} S={R}R={,,…} 图示表示a1a3a2a4an-1an….抽象数据类型线性表的定义如下：ADTList{数据对象：D＝{ai
4、ai∈ElemSet,i=1,2,...,n,n≥0
5、}{称n为线性表的表长;称n=0时的线性表为空表。}数据关系：R1＝{
6、ai-1,ai∈D,i=2,...,n}{设线性表为(a1，a2,...，ai，...，an),称i为ai在线性表中的位序。}基本操作：结构初始化操作结构销毁操作引用型操作加工型操作}ADTListInitList(&L)操作结果：构造一个空的线性表L。初始化操作结构销毁操作DestroyList(&L)初始条件：操作结果：线性表L已存在。销毁线性表L。ListEmpty(L)ListLength(L)PriorElem(L,cur_e,&pre_e
7、)NextElem(L,cur_e,&next_e)GetElem(L,i,&e)LocateElem(L,e,compare())ListTraverse(L,visit())引用型操作:ListEmpty(L)初始条件：操作结果：线性表L已存在。若L为空表，则返回TRUE，否则FALSE。（线性表判空）ListLength(L)初始条件：操作结果：线性表L已存在。返回L中元素个数。（求线性表的长度）PriorElem(L,cur_e,&pre_e)初始条件：操作结果：线性表L已存在。若cur_e是L的元素，但不是第一个，则用pre_e
8、返回它的前驱，否则操作失败，pre_e无定义。（求数据元素的前驱）NextElem(L,cur_e,&next_e)初始条件：操作结果：线性表L已存在。若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。（求数据元素的后继）GetElem(L,i,&e)初始条件：操作结果：线性表L已存在，且1≤i≤LengthList(L)。用e返回L中第i个元素的值。（求线性表中某个数据元素）LocateElem(L,e,compare())初始条件：操作结果：线性表L已存在，e为给定值，compar
9、e()是元素判定函数。返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。（定位函数）ListTraverse(L,visit())初始条件：操作结果：线性表L已存在，Visit()为某个访问函数。依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。（遍历线性表）加工型操作ClearList(&L)PutElem(&L,i,&e)ListInsert(&L,i,e)ListDelete(&L,i,&e)ClearList(&L)初始条件：操作结果：线性表L已存在。将L重置为
10、空表。（线性表置空）PutElem(&L,i,&e)初始条件：操作结果：线性表L已存在，且1≤i≤LengthList(L)。L中第i个元素赋值同e的值。（改变数据元素的值）ListInser
