• 认真地记录技术中遇到的坑!

线性表回顾

算法数据结构 悠悠 5个月前 (06-04) 213次浏览 0个评论

概述

定义

线性表(linear list)也称为有序表,一个线性表是n个具有相同特性的数据元素的有限序列,它的每一个实例都是元素的一个有序集合。

线性表是最基本、最简单、也是最常用的一种数据结构。
线性表回顾

基本操作

一个线性表应该具有一系列基本方法,可以用下面的抽象数据类型来进行描述:

// 线性表的抽象数据描述

#ifndef LINEAR_LIST
#define LINEAR_LIST

#include <ostream>

template<class T>
class LinearList
{
   public:
    // 若表为空,则返回true,否则返回false
    virtual bool empty() const = 0;

    // 返回线性表的大小(元素个数)
    virtual int size() const = 0;

    // 返回线性表中索引为index的元素
    virtual T& get(int index) const = 0;

    // 返回线性表中第一次出现的element的索引,如果element不存在,则返回-1
    virtual int index_of(const T& element) const = 0;

    // 删除索引为index的元素,索引大于index的元素其索引减1(往前移动一个位置)
    virtual void erase(int index) = 0;

    // 将element插入线性表中索引为index的位置上,索引大于或等于index的元素其索引加1(往后移动一个位置)
    virtual void insert(int index, const T& element) = 0;

    // 从左到右输出表元素
    virtual void output(std::ostream& out) const = 0;
};

#endif

特性

线性表有下列特性:

  • 在非空表中每个数据元素都有一个确定的位置
  • 线性表的相邻元素之间存在着序偶关系
  • 线性表中必存在唯一的一个“第一元素”
  • 线性表中必存在唯一的一个“最后元素”
  • 除最后一个元素之外,其他元素均有唯一的后继(后件)
  • 除第一个元素之外,其他元素均有唯一的前驱(前件)
  • 一个数据元素可由多个数据项组成

数组描述的线性表

可以使用数组来存储线性表元素,简单的可以如下所示描述线性表:

  • 使用一维数组来存储表元素
  • 使用数组的顺序下标来描述线性表的元素顺序
  • 使用变量list_size来记录当前存储的线性表元素个数
  • 使用array_length描述数组长度
  • 通过为数组动态分配内存来存储元素,当数组空间不足是,动态倍增数组长度

相应的具体实现可以参考以下代码实现细节:array_list.h

vector描述

在C++中,可以使用STL提供的技术数组的类vector来描述线性表,这个类已经提供了丰富的对数组的操作,我们只需要将它们封装成线性表的通用方法即可。

具体实现可以参考:vector_list

单向链表描述的线性表

在链式描述中:

  • 数据对象实例的每一个元素都用一个单元或节点来描述
  • 每一个节点都明确包含另一个相关节点的位置信息
  • 使用节点的关联信息(指针,链)来描述元素之间的顺序

单向链表描述线性表的实现参考:chain.h

性能比较

array,vector,chain描述的线性表,在内存和空间的比较有如下优劣关系:

  • array空间满是倍增,占有率不住25%时,减半,vector按照1.5倍倍增,链表不会有数据冗余
  • 应用设计选择描述方法时,三者在空间需求上的差异不是决定性因素
  • 链表get()时间复杂度O(list_size),其他为O(1)
  • index_of链表用时大约是array的6倍
  • 插入和删除时,链表用时大约是array 的33倍和46倍
  • 列表的插入位置随机,访问内存随机,导致高速缓存失效
  • 因为数组描述时,数组元素的访问是连续内存空间,会比链表快很多
  • 尽管链表在性能上表现不好,但是链表可以描述一些复杂数据结构,他们表现比数组优秀

栈是一种特殊的线性表,其插入和删除操作都在表的同一端进行,这一端称为栈顶,另一端称为栈底。满足先进后出(FILO)原则。
线性表回顾
栈的抽象数据描述如下:

#pragma once

template <class T>
class Stack
{
public:
    virtual ~Stack() {}
    // 如果栈为空则返回true
    virtual bool empty() const = 0;

    // 返回栈中的元素个数
    virtual int size() const = 0;

    // 返回栈顶元素
    virtual T& top() = 0;

    // 删除栈顶元素(出栈)
    virtual void pop() = 0;

    // 往栈顶插入元素(入栈)
    virtual void push(const T& element) = 0;
};

栈和线性表类似也可以有多种描述方式:

队列

队列和栈一样,也是一种特殊的线性表,队列的插入和删除操作分别在线性表的两端进行,因此,队列是一个先进先出(FIFO)的线性表。
线性表回顾
队列的抽象数据描述如下:

#pragma once

template <class T>
class Queue
{
public:
    virtual ~Queue() {}

    // 如果队列为空则返回true
    virtual bool empty() const = 0;

    // 返回队列中的元素个数
    virtual int size() const = 0;

    // 返回队列头部的元素
    virtual T& front() = 0;

    // 返回队列尾部的元素
    virtual T& back() = 0;

    // 删除队列头部的元素(出队列)
    virtual void pop() = 0;

    // 往队列尾部插入元素(入队列)
    virtual void push(const T& element) = 0;
};

队列的两种实现方式参考:array_queue.hlinked_queue.h

考虑到队列的特定,我们一般使用环形的线性表来进行描述。


转载请注明出处 线性表回顾
喜欢 (1)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址