前言
线性表是属于线性结构，线性结构的基本特点是除第一个元素无直接前驱，最后一个无直接后继之外，其他的每个数据元素都有一个前驱和后继。
线性表是什么？
线性表是最基本且最常用的一种线性结构。同时也是其他数据结构的基础。
线性表(Linear List):全称线性存储结构，其数据元素之间的关系是 一对一 的关系。即除第一个元素无直接前驱，最后一个无直接后继之外，其他的每个数据元素都有一个前驱和后继。
如何理解在内存中的线性表
在内存中的线性表，我们可以简单的理解为一根绳子，将所有的数据按顺序全部都串在一起了。
而绳子的头部就是线性表的第一个元素，绳子的尾部为线性表的最后一个元素。
在记录四 初识数据结构中,谈到了数据的存储结构分为了顺序存储结构和链式存储结构。下面，我们用这两种结构去了解一下。
顺序存储结构：一片连续的空间，数据依次存储在空间中，空间内存地址逐渐增大。这种存储结构称为顺序存储结构，简称顺序表。
顺序存储结构
链式存储结构: 空间不连续，数据通过媒介来找到下一个数据。空间的内存地址是随机分配的。但通常内存地址也是增大的。这种存储结构称为链式存储结构，简称链表。
链式存储结构
线性表的抽象数据类(C++)
namespace list{//线性表命名空间
/**状态枚举定义**/
enum Status{
SUCCESS,FAIL,MEMORY_ALLOCATION_FAILED,ARRAY_OUT_OF_BOUNDS,OTHER_ERROR
/**枚举定义说明
* SUCCESS:操作成功
* FAIL:操作失败
* MEMORY_ALLOCATION_FAILED:内存分配失败
* ARRAY_OUT_OF_BOUNDS:数组下标越界
* OTHER_ERROR:其它错误
*/
};
/**顺序表抽象数据类型定义**/
template<typename T> //模板
class ListSelf
{
protected:
/**
* 构造一个顺序表,动态申请内存。
*/
virtual Status init() = 0;
/**
* 销毁顺序表，回收内存。
*/
virtual Status destroy() = 0;
public:
/**
* 在相应的位置上插入新的数据
*/
virtual Status insert(T elem,size_t index) = 0;
/**
* 在线性表的末尾插入新的数据
*/
virtual Status insert(T elem) = 0;
/**
* 取出线性表的数据元素
*/
virtual T at(size_t index) = 0;
/**
* 返回数据的索引下标
*/
virtual int local(T elem) = 0;
/**
* 修改指定位置的数据
*/
virtual Status updateIndex(T newElem,size_t index)=0;
/**
* 修改匹配的数据
*/
virtual Status update(T oldElem,T newElem) = 0;
/**
* 在相应的位置上删除数据
*/
virtual Status removeIndex(size_t index) = 0;
/**
* 移除线性表中相同的元素
*/
virtual Status remove(T elem) = 0;
/**
* 返回查找元素的直接前驱
*/
virtual T * prior(T elem) = 0;
/**
* 返回查找元素的直接后驱
*/
virtual T * next(T elem) = 0;
/**
* 返回线性表中元素的个数
*/
virtual size_t size() = 0;
/**
* 将线性表重置为空表，清空所有数据
*/
virtual void clear() = 0;
/**
* 判断线性表是否为空表，如果是空表，返回true，否则返回false
*/
virtual bool isEmpty() = 0;
/**
* 遍历线性表
*/
virtual Status show() = 0;
}; //抽象类结束
/**
* 链式存储结构抽象类
*/
template<typename T>
class LinkSelf{
protected:
/**
* 构造一个链表头
*/
virtual Status init() = 0;
/**
* 销毁链表，回收内存。
*/
virtual Status destroy() = 0;
public:
/**
* 向链表中添加数据
*/
virtual Status add(T elem) = 0;
/**
* 修改链表中的数据
*/
virtual Status update(T oldElem,T newElem) = 0;
/**
* 删除链表中的数据
*/
virtual Status remove(T elem) = 0;
/**
* 链表中结点的个数
*/
virtual size_t size() = 0;
/**
* 返回查询结点的上一个结点的指针
*/
virtual T * prior(T elem) = 0;
/**
* 返回查询结点的下一个结点的指针
*/
virtual T * next(T elem) = 0;
/**
* 返回头指针
*/
virtual T * header() = 0;
/**
* 返回尾部指针
*/
virtual T * tail() = 0;
/**
* 为链表进行排序
*/
virtual Status sort() = 0;
/**
* 清空链表
*/
virtual void clear() = 0;
/**
* 遍历整个链表
*/
virtual Status show() = 0;
};//链式存储结构抽象类结束
/**
*顺序存储结构类
*/
template<typename T,size_t SIZE>
class OrderList : public ListSelf<T>{//OrderList : 顺序表类 继承 线性表抽象类(ListSelf)
};//顺序存储结构类结束
/**
*链式存储结构类
*/
template<typename T>
class LinkedList : public LinkSelf<T>{//LinkedList : 单链表类 继承 链表抽象类(LinkSelf)
};//链式存储结构类结束
}//命名空间结束
线性表还没有结束
(emmmm，很尴尬的一件事情。我觉得我不能在晚上学习。因为我发现我在晚上学习，我会失眠。大脑里面想了许许多多的东西。大部分都是关于程序的。所以，我决定晚上不写了。)
(有没有发现今天的字数特别少。是的。因为我昨天晚上4点睡得。6点自己就起床了。昨天晚上只睡了两个小时。看了几个小时的STL源码解析。想要在看看大神们是如何实现数据结构的。为了自己的狗命。晚上还是少敲代码。。)
(明天再写吧。明天应该最主要的应该是顺序结构的实现。明天是要码代码的哦。)
网友评论