【数据结构】14_线性表的本质和操作

c/c++

浏览数:69

2020-6-15

生活中的智慧

幼儿园老师总会让小朋友以同样的排队秩序出行。

线性表(List)的表现形式

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

线性表(List)的抽象定义

  • 线性表是具体有相同类型的 n(>=0)个数据元素有限序列

(a0, a1, …, an-1)

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

线性表(List)的性质

  • a0 为线性表的第一个元素,只有一个后继
  • an-1 为线性表的最后一个元素,只有一个前驱
  • 除 a0 和 an-1 外的其他元素 ai 既有前驱,又有后继
  • 直接支持逐项访问和顺序访问

思考题:下面的关系可以用线性表描述的是

班级中同学的友谊关系 (不可以,图)
公司中的上下级关系 (不可以,树)
冬天图书馆用物品排队占座 (不可以,类型不同)
花名册上名字之间的关系 (视具体名字是否有序)

讨论

宫城:线性表可以说是生活”队列关系“的总结
木暮:对,我们学习之后就可以在程序中使用了
宫城:可是怎么使用一个线性表呢?
木暮:确实!还有就是程序中怎么生成一个线性表呢?

问题

线性表只是一个单纯的概念吗?
如何在程序中描述和使用一个线性表?

线性表的一些常用操作

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

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

template<typename T>
class List : public Object
{
public:
    virtual bool insert(const T &e) = 0;
    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) = 0;
    virtual int length() const = 0;
    virtual void clear() = 0;
};

编程实验:线性表抽象类的创建

文件:List.h

#ifndef LIST_H
#define LIST_H

#include "Object.h"

namespace DTLib
{

template<typename T>
class List : public Object
{
public:
    virtual bool insert(const T &e) = 0;
    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;
};

}

#endif // LIST_H

小结

  • 线性表是数据元素的有限并有序的集合
  • 线性表中的数据元素必须是类型相同的
  • 线性表可用于描述队列关系的问题
  • 线性表在程序中表现为一种特殊的数据类型
  • 线性表在 C++ 中表现为一个特殊的抽象类

以上内容整理于狄泰软件学院系列课程,请大家保护原创!

作者:TianSong