数据结构2----线性表顺序存储和链式存储的实现(霜之小刀)

2019-11-11 05:24:43

字体：大中小

来源：转载

供稿：网友

欢迎转载和引用，若有问题请联系若有问题，请联系 Email : lihn1011@163.com QQ:2279557541

定义

所谓线性表，其实就是具有“线”一样性质的表，所谓线一样的性质，也就是具有n个数据元素的优先序列。其中n>=0

抽象数据模型

/** * 抽象的线性表接口 * 其中DataType表示线性表中所存储的数据类型 */template<class DataType>class ListInterface{public: /** * @brief 用于判断当前线性表是否为空 * @return true:为空 false:不为空 */ virtual bool IsEmpty() = 0; /** * @brief 获取当前线性表的长度 * @return 表的长途 */ virtual unsigned int GetLength() = 0; /** * @brief 获取线性表中的一个数据 * @param i数据所在的位置，也就是第几个数据 * @param data 若数据获取成功，则用于传出数据 * @return 数据是否获取成功 */ virtual bool GetItem(unsigned int i, DataType& data) = 0; /** * @brief 查找某个数据在线性表中的位置 * @param data 要查找的数据 * @return -1：查找失败 else 查找的数据在线性表中的位置 */ virtual int FindItem (DataType data) = 0; /** * @brief 删除线性表中的所有数据 */ virtual void Clear(); /** * @brief 向线性表中插入数据 * @param i 要插入线性表的位置 * @param data 要插入的数据 * @return 是否插入成功 */ virtual bool InsertItem(unsigned int i, DataType data) = 0; /** * @brief 删除线性表中的某个数据 * @param i 要删除的数据所处的位置 * @return 是否删除成功 */ virtual bool DeleteItem(unsigned int i) = 0;};

其实线性表是可以拥有更多操作的，但是这里只列出了我认为最常用的一些。虽然抽象完成了，但是要写具体实现，这里就有点问题了，因为线性表的物理结构有两种，分别为

顺序存储结构链式存储结构

顺序存储结构的实现方式

我们发现这个线性表的顺序存储结构有以下特点

表中数据的多少只需修改m_length即可改变。无论表中当前数据有多少，实际的存储数据的区域都不会发生变化，也就是有多余的内存空间会被浪费。最大容量有限制，如果要动态，则会增加拷贝和内存管理工作，效率底下。插入删除一个元素时，需要移动操作点后面的所有数据，效率底下。获取表中某个数据时，可以直接索引，效率非常高。

链式存储结构的实现方式

/** * 线性列表的顺序存储实现 * 未考虑max_size溢出的情况 */template<class DataType,int max_size>class QueueList:public ListInterface<DataType>{public: QueueList() { m_length = 0; } /** * @brief 用于判断当前线性表是否为空 * @return true:为空 false:不为空 */ virtual bool IsEmpty() { return m_length?true:false; } /** * @brief 获取当前线性表的长度 * @return 表的长途 */ virtual unsigned int GetLength() { return m_length; } /** * @brief 获取线性表中的一个数据 * @param i数据所在的位置，也就是第几个数据 * @param data 若数据获取成功，则用于传出数据 * @return 数据是否获取成功 */ virtual bool GetItem(unsigned int i, DataType& data) { if(i >= m_length)return false; data = m_data_list[i]; return true; } /** * @brief 查找某个数据在线性表中的位置 * @param data 要查找的数据 * @return -1：查找失败 else 查找的数据在线性表中的位置 */ virtual int FindItem (DataType data) { for(int i = 0; i < m_length; i++) { if(data == m_data_list[i]) { return i; } } return -1; } /** * @brief 删除线性表中的所有数据 */ virtual void Clear() { m_length = 0; } /** * @brief 向线性表中插入数据 * @param i 要插入线性表的位置 * @param data 要插入的数据 * @return 是否插入成功 */ virtual bool InsertItem(unsigned int i, DataType data) { if(i <= m_length) { for(int idx = m_length;idx > i; idx--) { m_data_list[idx] = m_data_list[idx-1]; } m_data_list[i] = data; m_length++; return true; } return false; } /** * @brief 删除线性表中的某个数据 * @param i 要删除的数据所处的位置 * @return 是否删除成功 */ virtual bool DeleteItem(unsigned int i) { if(i >= m_length) { return false; } for(int idx = i; idx < m_length; idx++) { m_data_list[idx] = m_data_list[idx+1]; } m_length--; return true; }private: DataType m_data_list[max_size]; unsigned int m_length;public: void Show() { qDebug()<<"start========"; for(int i = 0; i < m_length; i++) { DataType data; GetItem(i, data); qDebug()<<data; } qDebug()<<"end========"; }};template<class DataType>class LinkedList:public ListInterface<DataType>{public: LinkedList():m_length(0),m_head(NULL) { } /** * @brief 用于判断当前线性表是否为空 * @return true:为空 false:不为空 */ virtual bool IsEmpty() { return m_length?true:false; } /** * @brief 获取当前线性表的长度 * @return 表的长途 */ virtual unsigned int GetLength() { return m_length; } /** * @brief 获取线性表中的一个数据 * @param i数据所在的位置，也就是第几个数据 * @param data 若数据获取成功，则用于传出数据 * @return 数据是否获取成功 */ virtual bool GetItem(unsigned int i, DataType& data) { if(i >= m_length)return false; LinkStu* p = m_head; while(i--) { p=p->m_next; } data = p->m_data; return true; } /** * @brief 查找某个数据在线性表中的位置 * @param data 要查找的数据 * @return -1：查找失败 else 查找的数据在线性表中的位置 */ virtual int FindItem (DataType data) { int finded_idx = 0; LinkStu* p = m_head; while(p) { if(data == p->m_data) { return finded_idx; } finded_idx++; } return -1; } /** * @brief 删除线性表中的所有数据 */ virtual void Clear() { while(DeleteItem(0)); m_length = 0; } /** * @brief 向线性表中插入数据 * @param i 要插入线性表的位置 * @param data 要插入的数据 * @return 是否插入成功 */ virtual bool InsertItem(unsigned int i, DataType data) { if(i <= m_length) { LinkStu* new_link = new LinkStu(); new_link->m_data = data; if(i == 0) { new_link->m_next = m_head; m_head = new_link; } else { LinkStu* p = m_head; LinkStu* pre_p = m_head; for(int idx = 0; idx != i; idx++) { pre_p = p; p = p->m_next; } pre_p->m_next = new_link; new_link->m_next = p; } m_length++; return true; } return false; } /** * @brief 删除线性表中的某个数据 * @param i 要删除的数据所处的位置 * @return 是否删除成功 */ virtual bool DeleteItem(unsigned int i) { if(i >= m_length) { return false; } if(i == 0) { LinkStu* p = m_head; m_head = m_head->m_next; delete p; } else { LinkStu* p = m_head; LinkStu* pre_p = m_head; for(int idx = 0; idx != i; idx++) { pre_p = p; p = p->m_next; } pre_p->m_next = p->m_next; delete p; } m_length--; return true; }private: struct LinkStu { DataType m_data; LinkStu* m_next; LinkStu():m_next(NULL){} }; unsigned int m_length; LinkStu* m_head;};表中数据的增减会直接增加或减少内存的占用量。逻辑上表的大小是无限的。插入删除一个元素时，只要找到了元素的位置，操作效率非常高。获取表中某个数据时，效率较低。

上一篇：bzoj 3687: 简单题（dp+bitset）

下一篇：The 10th Zhejiang Provincial Collegiate Programming Contest