数据结构课件：1-线性表ADT2012

1、1线性表线性表数据结构与算法分析& 线性表线性表 2.1 2.1 线性结构线性结构 2.2 2.2 线性表线性表ADTADT的设计与表示的设计与表示 2.3 2.3 线性表线性表ADTADT的应用举例的应用举例 3数据逻辑关系 数据元素可存在于非空有限集合中数据元素可存在于非空有限集合中2626个英文字母表个英文字母表（A A，B B，C C，Z Z）某校从某校从19781978年到年到19831983年各种型号计算机拥有量的年各种型号计算机拥有量的变化情况变化情况（6 6，1717，2828，5050，9292，188188）一个学校的学生健康情况登记表一个学校的学生健康情况登记表姓

2、名姓名学号学号性别性别年龄年龄班级班级健康状况健康状况张三050101男18计93健康李四050102男19计93一般4线性结构的线性结构的基本特征基本特征为为: : 1集合中必存在唯一的一个集合中必存在唯一的一个“第一元素第一元素”；2集合中必存在唯一的一个集合中必存在唯一的一个 “最后元素最后元素” ；3除最后元素在外，均有除最后元素在外，均有 唯一的后继唯一的后继；4除第一元素之外，均有除第一元素之外，均有 唯一的前驱唯一的前驱。 线性结构线性结构 是是 一个数据元素的一个数据元素的有序（次序）集有序（次序）集最简单的线性结构线性结构称为称为线性表线性表5Lists线性表是由数据项组成的

3、一种有限且有序的线性表是由数据项组成的一种有限且有序的序列序列.重要的概念重要的概念: 线性表中的每一个元素都有自己的线性表中的每一个元素都有自己的位置位置.每一个元素都有一种数据类型每一个元素都有一种数据类型线性表中不包含任何元素时，称为线性表中不包含任何元素时，称为空表空表。当前存储的元素数目称为线性表的当前存储的元素数目称为线性表的长度长度。线性表的开始结点称为线性表的开始结点称为表头表头（head）线性表的结尾结点称为线性表的结尾结点称为表尾表尾（tail）有序线性表有序线性表的元素按照值的递增顺序排列，而的元素按照值的递增顺序排列，而无序线无序线性表性表在元素的值与位置之间就没有特殊

4、的联系。在元素的值与位置之间就没有特殊的联系。我们将如何表示线性表我们将如何表示线性表?我们将实现什么操作呢我们将实现什么操作呢?6& 线性表线性表 2.1 2.1 线性结构线性结构 2.2 2.2 线性表线性表ADTADT的设计与表示的设计与表示 2.3 2.3 线性表线性表ADTADT的应用举例的应用举例 7抽象数据类型线性表线性表的定义如下：ADT List 数据对象数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 称 n 为线性表的表长表长; 称 n=0 时的线性表为空表空表。数据关系数据关系：R1 |ai-1 ,aiD, i=2,.,n 设线性表为

5、(a1，a2, . . . ，ai，. . . ，an), 称 i 为 ai 在线性表中的位序位序。8 基本操作：基本操作： 结构初始化操作结构初始化操作结构销毁操作结构销毁操作 引用型操作引用型操作 加工型操作加工型操作 9线性表 ADTtemplate class List public: virtual void clear() = 0; virtual bool insert(const Elem&) = 0; virtual bool append(const Elem&) = 0; virtual bool remove(Elem&) = 0; virtua

6、l void setStart() = 0; virtual void setEnd() = 0; virtual void prev() = 0; virtual void next() = 0; virtual int leftLength() const = 0; virtual int rightLength() const = 0; virtual bool setPos(int pos) = 0; virtual bool getValue(Elem&) const = 0; virtual void print() const = 0;1011前后的哥们，排队太久了，离开

7、一会，待会我还站在你们中间哈12线性表实现中的一些概念我们在线性表中将实现对我们在线性表中将实现对当前位置当前位置的支持的支持.为了为了定义当前位置的概念，假设线性表由左、定义当前位置的概念，假设线性表由左、右两个分离部分组成右两个分离部分组成. 其中任一部分或两者可以为空其中任一部分或两者可以为空.这两个部分被一个这两个部分被一个栅栏栅栏（fence）分开分开.13List ADT ExamplesList: MyList.insert(99);Result: Iterate through the whole list:for (MyList.setStart(); MyList.getV

8、alue(it); MyList.next() DoSomething(it);14List Find Function/ Return true iff K is in listbool find(List& L, int K) int it; for (L.setStart(); L.getValue(it); L.next() if (K = it) return true; / Found it return false; / Not found15& 线性表线性表 2.1 2.1 线性结构线性结构 2.2 2.2 线性表线性表ADTADT的设计与表示的设计与表示 2.

9、3 2.3 线性表线性表ADTADT的应用举例的应用举例 16 假设:有两个集合集合 A 和和 B， 现要求一个新的集合现要求一个新的集合AAB。例例 17AB181、问题分析和任务定义 分析并确定要处理的对象（数据）是什么分析并确定要处理的对象（数据）是什么 分析并确定要实现的功能是什么分析并确定要实现的功能是什么 分析并确定处理后的结果如何显示分析并确定处理后的结果如何显示通过键盘输入两组整数，并通过键盘输入两组整数，并分别存储分别存储A和和B中中AAB把把A中的元素显示在显示器上中的元素显示在显示器上19测试数据 （11，12，13，14） A（11，10，8） BAB A （11，12

10、，13，14，10，8）（11，12，13，11） A（11，10，A） Berror 202、数据类型和系统设计 对问题描述中涉及的操作对象定义相应对问题描述中涉及的操作对象定义相应的抽象数据类型，并设计合适的算法的抽象数据类型，并设计合适的算法两个集合两个集合 A 和和 B 分别用两个线性表分别用两个线性表 LA 和和 LB 表示，即：线性表中的数据元素表示，即：线性表中的数据元素即为集合中的成员。即为集合中的成员。扩大线性表扩大线性表 LA，将存在于线性表将存在于线性表LB 中中而不存在于线性表而不存在于线性表 LA 中的数据元素插中的数据元素插入到线性表入到线性表 LA 中去。中去。2

11、1 virtual void init() const = 0; virtual bool append(const Elem&) = 0; virtual void setStart() = 0; virtual void next() = 0; virtual bool getValue(Elem&) const = 0; Elem int22程序的流程程序的流程程序由三个模块组成：程序由三个模块组成： 输入模块：完成两个集合的输入，存入变量输入模块：完成两个集合的输入，存入变量La和和Lb中。中。 计算模块：设计一个求集合并的函数，计算模块：设计一个求集合并的函数， vo

12、id union(List& La, List& Lb) ，两个集合，两个集合作为函数参数，计算结果通过第一个参数返回。作为函数参数，计算结果通过第一个参数返回。 输出模块：屏幕上显示计算的结果。输出模块：屏幕上显示计算的结果。231从线性表LB中依次察看每个数据元素;2依值在线性表LA中进行查访; 3若不存在，则插入之。setstartgetvalue（e）next（）（） find（LA，e） setstartgetvalue（e）next（）（） append( e )操作步骤：操作步骤：243、编码实现和静态检查 25void union(List& La, L

13、ist& Lb) int it,k; Status status; for (Lb.setStart(); Lb.getValue(it); Lb.next()/从线性表Lb中依次取出数据元素 status=False; for (La.setStart(); La.getValue(k); La.next()/从线性表La中依次取出数据元素 if (k = it) status=True; /存在if (status!=True) status = La.append(it); /添加if(status!=success)break; /添加失败则退出26要点回顾要点回顾 从问题中的数据中发现其线性特征 线性表ADT的设计 线性表ADT的表示 基于线性表ADT