数据结构学习笔记3——顺序表的实现

顺序表（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;
}

运行结果：