《数据结构》陈慧南_第02章线性表.ppt

数据结构
Data Structures in C++
南京邮电大学计算机学院
第2章线性表
南京邮电大学计算机学院
线性表ADT
线性表的顺序表示
线性表的链接表示
多项式的算术运算
南京邮电大学计算机学院
线性表ADT
南京邮电大学计算机学院
线性表的定义
线性表是n(0)个元素a0,a1,…,an-1 的线性序列,记为: (a0,a1,…,an-1)。其中n是线性表中元素的个数,称为线性表的长度;n=0时称为空表。
ai是表中下标为i的元素(i=0,1,…,n-1),称ai是ai+1的直接前驱元素,ai+1是ai的直接后继元素。
线性表是动态数据结构,它的表长可以改变。
南京邮电大学计算机学院
线性表ADT
ADT LinearList {
数据:
0个或多个元素的线性序列(a0,a1,...,an-1),其最大允许长度为MaxListSize。
运算:
Create(): 创建一个空线性表。
Destroy():撤消一个线性表。
IsEmpty():若线性表空,则返回true;否则返回false。
Length(): 返回表中元素个数。
南京邮电大学计算机学院
Find(i,x):在x中返回表中下标为i的元素ai。若不存在,则返回false,否则返回true。
Search(x):若x不在表中,则返回-1,否则返回x在表中的下标。
Insert(i,x):在元素ai之后插入x。若i=-1,则x插在第一个元素a0前。若插入成功,则返回true,否则返回false。
Delete(i):删除元素ai。若删除成功,则返回true,否则返回false。
Update(i,x):将元素ai的值修改为x。若修改成功,则返回true,否则返回false。
Output(out):把表送至输出流
} // 插入x 到表:(a0,a1,...,an-1)
南京邮电大学计算机学院
线性表类
template <class T>
class LinearList
{
public:
……
virtual bool Find(int i,T& x) const=0;
virtual bool Insert(int i,T x)=0;
virtual bool Delete(int i)=0;
……
protected:
int n; //线性表的长度
};
南京邮电大学计算机学院
线性表的顺序表示
南京邮电大学计算机学院
顺序存储结构
顺序存储表示
是用一组地址连续的存储单元依次存储线性表中元素。
顺序表
顺序表示的线性表称为顺序表
a0 a1 … ai … an-1 …
0 1 … i … n-1 … maxLength-1
南京邮电大学计算机学院