大三上软件工程课件.pdfVIP

内容提纲

◼线性表的概念与操作

◼线性表顺序

◼线性表链式

◼特殊线性表

栈、队列

串

向量、矩阵、级数、多项式

2012-02-15

四种逻辑结构

集合结构树形结构

线性结构图状结构

2012-02-15

线性表的概念与操作

◼线性表：有限个同类元素的一维序列

最基本、最简单最常用的数据结构

最基本的线性结构

其特例：空表a(i-1),a(i)

◼特征：“序偶”

必存在唯一的一个必存在唯一的一个必存在唯一的一个“首元素”

必存在唯一的一个“尾元素”

除尾元外，均有唯一的后继:Succ()

除首元外，均有唯一的前驱:Prev()

——有始有终，先后有序，且唯一

2012-02-15

线性表的例子

◼英文字母表（A,B,…,Z）

首=A，尾=B，Succ(J)=K,Prev(N)=M

每个字母：一个字符（原子类型）

◼学生（学生记录线性表）

首=学生1，尾=学生N……

（此处按不同规则存在不同排序）

一条学生记录：一个数据元素（结构类型）

2012-02-15

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

ADTLinearList

{

数据元素：D={a|a∈D,i=1,2,…，n,n≥0,

ii0

D为某一数据集合}

0

关系：Ｓ＝｛a,a|a,a∈D,i=1,2,…,n-1｝

ii+1ii+10

基本操作：

A.面向线性表”整体“的操作

B.以某个”元素“为目标的操作

2012-02-15

A.面向线性表”整体“的操作：

（1）InitList（L

操作前提：L为未初始化线性表。

操作结果：将L初始化为空表。

（2）DestroyList(L)

操作前提：线性表L已存在。

操作结果：将L销毁。

3ClearList(L)

操作前提：线性表L已存在。

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

4IsEmptyList（L

操作前提：线性表L已存在。

操作结果：如果L为空表则返回true，否则返回false。

（5）ListLength（L

操作前提：线性表L已存在。

操作结果：如果L为空表则返回0，否则返回表中的元素个数。

2012-02-15

B.以某个”元素“为目标的操作：

6HasElement(L,i)

操作前提：表L已存在，i为合法序号

操作结果：如果i位置有元素返回真，否则返回假。

7GetElement(L,i)

操作前提：表L存在且序号i合法

操作结果：返回线性表L中第i个元素的值。

8InsertElement(L,i,e)

操作前提：表L已存在且序号i合法且e为合法元素值。

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

9DeleteElement(L,i)

操作前提：表L已存在且非空且序号i合法。

操作结果：删除L的第i个数据元素，L的长度减1。

”序号i合法“指1≤i≤ListLength(L)或0≤i≤ListLength(L)-1

2012-02-15

C.InsertElement的特例：

（10）AddElement(L,e)

操作前提：表L已