顺序表(array based list 或者sequential list)是线性表(list)的一种,用数组实现。
文件结构如下:
其中,Public.h、Tools.h、Tools.cpp为提供辅助功能的文件:Public.h包含常用的头文件,Tools.h和Tools.cpp实现了异常机制Assert();
List.h中实现线性表的抽象类模板,不包含数据成员,成员函数都是虚函数(当然构造函数除外);
ArrayBasedList.h和ArrayBasedList_Def.h实现顺序表的模板类定义,其继承自List.h中的线性表模板;
main.cpp为主函数,实现顺序表的调用和测试。
List.h:
/********************************************************/
// 用模板实现线性表(List)的基类定义
/********************************************************/
#pragma once
#include "Public.h"
template<class dataType>
class List
{
private:
void operator= (const List&) {}
List(const List&) {}//构造函数不可为虚函数
public:
List() {} //默认构造函数,构造函数不可为虚函数
virtual ~List(){} //析构函数,基类一般总是需要虚析构函数,以便基类指针指向派生类时,删除基类指针时收回空间
// 清除内容,使线性表为空
virtual void clear() = 0; //纯虚函数,被派生类的实现覆盖,任何对象都不能调用当前版本
// 在当前位置插入元素
virtual void insert(const dataType& item) = 0;
// 在末尾追加元素
virtual void append(const dataType& item) = 0;
// 删除当前元素,返回其值
virtual dataType remove() = 0;//不能返回引用,因为该元素已经被删除了,只能返回值
// 将当前位置设为线性表的开始
virtual void moveToStart() = 0;
// 将当前位置设为线性表的末尾
virtual void moveToEnd() = 0;
// 将当前位置左移一格,若当前已经在开始位置则无改变
virtual void prev() = 0;
// 将当前位置右移一格,若当前已经在结束位置则无改变
virtual void next() = 0;
// 线性表中已经存储的元素的个数
virtual int length() const = 0; //size_t或unsigned int不是更好?
// 获取当前的位置
virtual int currPos() const = 0;
// 将当前位置的元素移动到某个特定位置
virtual void moveToPos(int pos) = 0;
// 获取当前的元素
virtual const dataType& getValue() const = 0; //const引用
};
ArrayBasedList.h
/********************************************************/
// 用模板实现顺序表(Array-Based List)的定义
// 继承基类线性表template<class dataType> class List
/********************************************************/
#pragma once
#include "List.h"
#define LIST_MAX_SIZE 100
template<class dataType>
class Alist:public List<dataType> //模板继承
{
private:
int maxSize; //顺序表的最大容量
int listSize; //当前存储的元素的个数
int curr; //当前位置,类似于数组下标
dataType* listArray;//存储成员的数组
public:
//带有一个默认实参的构造函数
Alist(int size = LIST_MAX_SIZE);
//析构函数
~Alist();
// 清除内容,使线性表为空
void clear(); //纯虚函数,被派生类的实现覆盖,任何对象都不能调用当前版本
// 在当前位置插入元素
void insert(const dataType& item);
// 在末尾追加元素
void append(const dataType& item);
// 删除当前元素,返回其值
dataType remove();//不能返回引用,因为该元素已经被删除了,只能返回值
// 将当前位置设为线性表的开始
void moveToStart();
// 将当前位置设为线性表的末尾
void moveToEnd();
// 将当前位置左移一格,若当前已经在开始位置则无改变
void prev();
// 将当前位置右移一格,若当前已经在结束位置则无改变
void next();
// 线性表中已经存储的元素的个数
int length() const; //size_t或unsigned int不是更好?
// 获取当前的位置
int currPos() const;
// 将当前位置的元素移动到某个特定位置
void moveToPos(int pos);
// 获取当前的元素
const dataType& getValue() const; //const引用
// 打印所有成员
void printList(ostream& os) const;
};
ArrayBasedList_Def.h:
/********************************************************/
// 用模板实现顺序表(Array-Based List)的定义
// 继承基类线性表 template<class dataType> class List
// 本头文件实现Alist<class dataType>的成员函数
/********************************************************/
#pragma once
#include "ArrayBasedList.h"
//构造函数
template <class dataType>
Alist<dataType>::Alist(int size = LIST_MAX_SIZE) : maxSize(size), listSize(0), curr(0)
{
listArray = new dataType[maxSize];
}
//析构函数
template<class dataType>
Alist<dataType>::~Alist()
{
//其他的数据成员不用清零?
delete[] listArray;
}
// 清除内容,使线性表为空
template<class dataType>
void Alist<dataType>::clear()
{
delete[] listArray;
listArray = new dataType[maxSize];
listSize = 0;
curr = 0;
}
// 在当前位置插入元素
template<class dataType>
void Alist<dataType>::insert(const dataType& item)
{
//参数检查
Assert(listSize < maxSize,"链表已满,不能插入!");
//将curr右边的元素(包括curr)右移1位
for (int index = listSize-1; index >= curr; index--)
{
listArray[index + 1] = listArray[index];
}
//在curr处填上新元素
listArray[curr] = item;
listSize++;
}
// 在末尾追加元素
template<class dataType>
void Alist<dataType>::append(const dataType& item)
{
//参数检查
Assert(listSize < maxSize, "链表已满,不能插入!");
listArray[listSize] = item;
listSize++;
}
// 删除当前元素,返回其值
template<class dataType>
dataType Alist<dataType>::remove()
{
// 参数检查
Assert(listSize > 0,"链表为空,无值可删");
//存储待删除值
dataType curValue = listArray[curr];
//当前位置之后的值左移一位
for (int index = curr+1; index < listSize; index++)
{
listArray[index - 1] = listArray[index];
}
//元素个数减1
listSize--;
return curValue;
}
// 将当前位置设为线性表的开始
template<class dataType>
void Alist<dataType>::moveToStart()
{
curr = 0;
}
// 将当前位置设为线性表的末尾
template<class dataType>
void Alist<dataType>::moveToEnd()
{
curr = listSize-1;
}
// 将当前位置左移一格,若当前已经在开始位置则无改变
template<class dataType>
void Alist<dataType>::prev()
{
if (curr !=0)
{
curr--;
}
}
// 将当前位置右移一格,若当前已经在结束位置则无改变
template<class dataType>
void Alist<dataType>::next()
{
if (curr != listSize - 1)
{
curr++;
}
}
// 线性表中已经存储的元素的个数
template<class dataType>
int Alist<dataType>::length() const
{
return listSize;
}
// 获取当前的位置
template<class dataType>
int Alist<dataType>::currPos() const
{
return curr;
}
// 将当前位置动到某个特定位置
template<class dataType>
void Alist<dataType>::moveToPos(int pos)
{
Assert((pos < listSize) && (pos >= 0), "目标位置越界");
curr = pos;
}
// 获取当前的元素
template<class dataType>
const dataType& Alist<dataType>::getValue() const
{
Assert(curr >= 0 && curr < listSize, "当前位置越界");
return listArray[curr];
}
// 打印所有成员
template<class dataType>
void Alist<dataType>::printList(ostream& os) const
{
for (int index = 0; index != listSize; index++)
{
os << listArray[index] << endl;
}
}
main.cpp
/********************************************************/
// 主函数
// 用于测试编写的各函数与数据结构
/********************************************************/
#include "Public.h"
#include "Tools.h"
#include "ArrayBasedList_Def.h"
int main()
{
/********************************************************/
// 3,《数据结构与算法分析》Clifford 4.1.1顺序表的实现
/********************************************************/
Alist<int> iList;
iList.insert(1);
iList.insert(2);
iList.insert(3);
iList.insert(4);
cout << "after insert" << endl;
iList.printList(cout);
iList.clear();
cout << "after clear" << endl;
iList.printList(cout);
iList.append(1);
iList.append(2);
iList.append(3);
iList.append(4);
cout << "after append" << endl;
iList.printList(cout);
// 在类外手动打印全部元素,会改变curr的位置
cout << "手动打印" << endl;
iList.moveToStart();
while (true)
{
cout << iList.getValue() << endl;
if (iList.currPos() == iList.length()-1)
{
break;
}
else
{
iList.next();
}
}
system("pause");
return 0;
}
运行结果: