第三章数据结构与算法_线性结构(一)合编.ppt

?引子?线性表的定义与实现?堆栈?队列?应用实例 第三章 线性结构 第3章 线性结构 §3.1 引子 ? 在数据的逻辑结构中，一种常见而且简单的结构是线性结构，即数据元素之间构成一个有序的序列。这是一类比较有共性问题的抽象表示，如银行等候队列的管理、班级学生的管理、计算机中空闲内存的管理等。 ? 本章将介绍线性表的抽象含义，并分别讨论基于顺序存储和链式存储的线性表实现方法。同时将介绍两种典型且应用广泛的线性表：堆栈和队列。线性表的基本操作是插入和删除，堆栈是插入和删除操作值发生在同一端的线性表，而队列的插入和删除操作分别发生在有序序列的两端。 §3.2 线性表的定义与实现 1.线性表的定义 线性表(Linear List) ：是由n(n≧0)个数据元素(结点)a1，a2， …an组成的有限序列。该序列中的所有结点具有相同的数据类型。标的起始位置称为表头，表的结束位置称为表尾。其中数据元素的个数n称为线性表的长度。 当n=0时，称为空表。 当n0时，将非空的线性表记作： (a1，a2，…an) a1称为线性表的第一个(首)结点，an称为线性表的最后一个(尾)结点。 其中ai-1是ai的直接前驱;其中ai+1是ai的直接后继。 第3章 线性结构 线性表中的数据元素ai所代表的具体含义随具体应用的不同而不同，在线性表的定义中，只不过是一个抽象的表示符号。 ◆ 线性表中的结点可以是单值元素(每个元素只有一个数据项) 。 例1: 26个英文字母组成的字母表： (A，B，C、…、Z） 例2 ： 某校从1978年到1983年各种型号的计算机拥有量的变化情况：(6，17，28，50，92，188） 例3 ： 一副扑克的点数 (2，3，4，…，J，Q，K，A) 第3章 线性结构 §3.2 线性表的定义与实现 ◆ 线性表中的结点可以是记录型元素，每个元素含有多个数据项 ，每个项称为结点的一个域 。每个元素有一个可以唯一标识每个结点的数据项组，称为关键字。 例4 ： 某校2001级同学的基本情况：{(‘2001414101’，‘张里户’，‘男’，06/24/1983)， (‘2001414102’，‘张化司’，‘男’，08/12/1984) …， (‘2001414102’，‘李利辣’，‘女’，08/12/1984) } ◆ 若线性表中的结点是按值(或按关键字值)由小到大(或由大到小)排列的，称线性表是有序的。 第3章 线性结构 §3.2 线性表的定义与实现 线性表的抽象数据类型定义： 类型名称：线性表（list） 数据对象集：R = {ai-1, ai | ai-1, ai∈D, i=2,3,…,n } 操作集： List MakeEmpty( L ) 操作结果：构造一个空的线性表L； int Length( L ) 初始条件：线性表L已存在； 操作结果：若L为空表，则返回FALSE，否则返回线性表L的长度； ElementType FindKth( L, K, e ) 初始条件：线性表L已存在，1≦K≦ListLength(L)； 操作结果：用e返回L中第K个数据元素的值； 第3章 线性结构 §3.2 线性表的定义与实现 void Insert ( L, i, e ) 初始条件：线性表L已存在，1≦i≦ListLength(L) ； 操作结果：在线性表L中的第i个位置插入元素e； void Delete ( L, i ) 初始条件：线性表L已存在，1≦i≦ListLength(L) ； 操作结果：从线性表L中删除第i个位置的元素； int Find( L, ElementType X, i ) 初始条件：线性表L已存在； 操作结果：已知X，返回线性表L中与X相同的第一个元素的相应位序i；若不存在则返回空； 第3章 线性结构 §3.2 线性表的定义与实现 §3.2 线性表的定义与实现 2.线性表的顺序存储实现 顺序存储 ：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。 顺序存储的线性表的特点： ◆ 线性表的逻辑顺序与物理顺序一致; ◆ 数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。 第3章 线性结构 §3.2 线性表的定义与实现 设有非空的线性表：(a1，a2，…an) 。顺序存储如图所示。 第3章 线性结构 … a1 a2 … ai … an … Loc(a1) Loc(ai)+(i-1)* l 图2-1 线性表的顺序存储表示 在具体的机器环境下：设线性表的每个元素需占用l个存储单元，以所占的第一个单元的存储地址作为数据元