线性表(Linear List)

线性表(Linear List)

1. 线性表的概念

• 线性表是最基本、最简单、也是最常用的一种数据结构。
• 线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了哨位结点）。
• 在数据结构逻辑层次上细分，线性表可分为一般线性表和受限线性表。
  (1)一般线性表：就是我们通常所说的“线性表”，可以自由的删除或添加结点。
  (2)受限线性表：主要包括栈和队列，受限表示对结点的操作受限制。
• 注：我们说“线性”和“非线性”，只在逻辑层次上讨论，而不考虑存储层次，所以双向链表和循环链表依旧是线性表。

2. 线性表的结构特征及特点

• 线性表是一个有限序列。
• 线性表是一个含有n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。
• 一般地，一个线性表可以表示成一个线性序列(k1,k2,…,kn，其中k1是开始结点，kn是终端结点)。
• 在实际应用中，线性表都是以栈、队列、串等特殊线性表的形式来使用的。
• 注：在实现线性表数据元素的存储方面，一般可用顺序存储结构和链式存储结构两种方法。
  (1)顺序存储结构主要包括顺序表(即用一维数组作为表的存储结构)。
  (2)链式存储结构主要包括单链表、循环链表和双向链表。
  另外栈、队列和字符串也是线性表的特殊情况，又称为受限的线性结构。

3. 线性表的抽象类定义——应用了模板类来描述线性表抽象数据类型

• 文件：LinearList.h

  复制代码#ifndef LINEAR_LIST_H_ #define LINEAR_LIST_H_ template <class T> class LinearList { public: LinearList(){} //构造函数 virtual ~LinearList(){} //析构函数 public: virtual int Size()const = 0; //获取最大表项总数 virtual int Length()const = 0; //计算实际表项总数 virtual int Search(const T& x)const = 0; //搜索数据值为x的表项并返回表项序号 virtual int Locate(int i)const = 0; //获取第i个表项并返回表项序号 virtual bool GetData(int i, T& x)const = 0; //获取第i个表项的数据值保存至x，并返回获取成功与否 virtual bool SetData(int i, const T& x) = 0; //修改第i个表项的数据值为x virtual bool Insert(int i, const T& x) = 0; //在第i个表项后插入数据值为x的新表项 virtual bool Remove(int i, T& x) = 0; //删除第i个表项，并将被删表项的数据值保存至x virtual bool IsEmpty()const = 0; //判断表是否为空 virtual bool IsFull()const = 0; //判断表是否为满 virtual void Sort() = 0; //表排序——冒泡排序 virtual void InputFront() = 0; //前插法建立线性表 virtual void InputRear() = 0; //后插法建立线性表 virtual void Output()const = 0; //输出所有表项的数据值 virtual void Reverse() = 0; //线性表逆置 virtual void MakeEmpty() = 0; //清空线性表 virtual LinearList<T>& operator=(const LinearList<T>& L) = 0; //线性表间赋值操作——重载等号运算符 }; #endif /* LINEAR_LIST_H_ */

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  
  #ifndef LINEAR_LIST_H_
  #define LINEAR_LIST_H_
  template <class T>
  class LinearList
  {
  public:
  LinearList(){}
  //构造函数
  virtual ~LinearList(){}
  //析构函数
  public:
  virtual int Size()const = 0;
  //获取最大表项总数
  virtual int Length()const = 0;
  //计算实际表项总数
  virtual int Search(const T& x)const = 0;
  //搜索数据值为x的表项并返回表项序号
  virtual int Locate(int i)const = 0;
  //获取第i个表项并返回表项序号
  virtual bool GetData(int i, T& x)const = 0;
  //获取第i个表项的数据值保存至x，并返回获取成功与否
  virtual bool SetData(int i, const T& x) = 0;
  //修改第i个表项的数据值为x
  virtual bool Insert(int i, const T& x) = 0;
  //在第i个表项后插入数据值为x的新表项
  virtual bool Remove(int i, T& x) = 0;
  //删除第i个表项，并将被删表项的数据值保存至x
  virtual bool IsEmpty()const = 0;
  //判断表是否为空
  virtual bool IsFull()const = 0;
  //判断表是否为满
  virtual void Sort() = 0;
  //表排序——冒泡排序
  virtual void InputFront() = 0;
  //前插法建立线性表
  virtual void InputRear() = 0;
  //后插法建立线性表
  virtual void Output()const = 0;
  //输出所有表项的数据值
  virtual void Reverse() = 0;
  //线性表逆置
  virtual void MakeEmpty() = 0;
  //清空线性表
  virtual LinearList<T>& operator=(const LinearList<T>& L) = 0;
  //线性表间赋值操作——重载等号运算符
  };
  #endif
  /* LINEAR_LIST_H_ */
  

参考文献：
[1]《数据结构(用面向对象方法与C++语言描述)(第2版)》殷人昆——第二章
[2]《C/C++常用算法手册》秦姣华、向旭宇——第二章
[3] 百度搜索关键字：线性表

最后

以上就是无心夏天最近收集整理的关于线性表(Linear List)的全部内容，更多相关线性表(Linear内容请搜索靠谱客的其他文章。