欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

一、线性表的本质和操作

程序员文章站 2022-07-02 07:53:31
1、线性表 线性表( )的表现形式 零个或多个数据元素组成的集合 数据元素在位置上是有序排列的 数据元素的个数是有限的 数据元素的类型必须相同 线性表的抽象定义: 线性表是具有相同类型的$n(\geq0)$ 个数据元素的有限序列 $$(a_0, a_1, ..., a_{n 1})$$ $a_i$是 ......

1、线性表

线性表(List)的表现形式

  • 零个或多个数据元素组成的集合
  • 数据元素在位置上是有序排列的
  • 数据元素的个数是有限的
  • 数据元素的类型必须相同

线性表的抽象定义:

线性表是具有相同类型的\(n(\geq0)\) 个数据元素的有限序列

\[(a_0, a_1, ..., a_{n-1})\]

\(a_i\)是表项(数据元素), \(n\)是表长度

2、线性表的性质

  • \(a_0\)为线性表的第一个元素,只有一个后继
  • \(a_{n-1}\)为线性表的最后一个元素,只有一个前驱
  • \(a_0\)\(a_{n-1}\)外的其它元素\(a_i\),既有前驱,又有后继
  • 直接支持逐项访问和顺序存取

3、线性表的程序实现

线性表的常用操作

  • 将元素插入线性表
  • 将元素从线性表中删除
  • 获取目标位置处元素的值
  • 设置目标位置处元素的值
  • 获取线性表的长度
  • 清空线性表

线性表在程序中的表现形式为一种特殊的数据类型

创建一个线性表抽象类模板

template<typename T>
class List : public Object
{
public:
    virtual bool insert(int i, const T& e) = 0;
    virtual bool remove(int i) = 0;
    virtual bool set(int i, const T& e) = 0;
    virtual bool get(int i, T& e) const = 0;
    virtual int length() const = 0;
    virtual void clear() =0;
}

4、小结

线性表是数据元素的有序并且有限的集合

线性表的数据元素必须是类型相同的

线性表可用于描述排队关系的问题

线性表在程序中表现为一种特殊的数据类型

线性表在C++中表现为一个抽象类