|
|
#ifndef SEQLIST_HPP
|
|
|
#define SEQLIST_HPP
|
|
|
|
|
|
#include <iostream>
|
|
|
#include <stdexcept>
|
|
|
|
|
|
// 对吴版教材当中的一些设计和写法进行调整
|
|
|
template <typename T, int N>
|
|
|
class SeqList
|
|
|
{
|
|
|
T slist[N]; // 存放顺序表的数组
|
|
|
int last; // 已存表项的最后位置
|
|
|
public:
|
|
|
SeqList() { last = -1; } // 默认构造
|
|
|
int size() const { return last + 1; } // 计算表长度
|
|
|
int capcity() const { return N; } // 计算表容量
|
|
|
bool isempty() const { return last == -1; } // 判断表是否空
|
|
|
bool isfull() const { return last == N - 1; } // 判断表是否满
|
|
|
T &at(int i); // 取第i个元素之值
|
|
|
T &operator[](int i); // 重载下标运算符[]
|
|
|
int find(const T &x) const; // 寻找x在表中下标
|
|
|
bool insert(int i, const T &x); // x插入到表中下标为i的位置
|
|
|
bool remove(const T &x); // 删除第一个值为x的元素
|
|
|
void print() const; // 输出线性表内容
|
|
|
};
|
|
|
|
|
|
template <typename T, int N>
|
|
|
T &SeqList<T, N>::at(int i)
|
|
|
{
|
|
|
if (i < 0 || i > last)
|
|
|
{
|
|
|
throw std::out_of_range{"下标不合法!"}; // 抛出异常
|
|
|
// 如希望不抛出异常可以改为返回静态局部的引用
|
|
|
// static T temp{};
|
|
|
// return temp;
|
|
|
}
|
|
|
return slist[i];
|
|
|
}
|
|
|
|
|
|
template <typename T, int N>
|
|
|
int SeqList<T, N>::find(const T &x) const
|
|
|
{
|
|
|
int i{0};
|
|
|
while (i <= last && slist[i] != x)
|
|
|
++i; // 顺序查找是否有x
|
|
|
return i > last ? -1 : i; // 未找到返回-1，否则返回下标
|
|
|
}
|
|
|
|
|
|
template <typename T, int N>
|
|
|
bool SeqList<T, N>::insert(int i, const T &x)
|
|
|
{
|
|
|
if (i < 0 || i > last + 1 || isfull())
|
|
|
return false; // 插入位置不合理或者满，不能插入
|
|
|
++last;
|
|
|
for (int j{last}; j > i; j--)
|
|
|
slist[j] = slist[j - 1]; // 依次后移
|
|
|
slist[i] = x;
|
|
|
return true;
|
|
|
}
|
|
|
|
|
|
template <typename T, int N>
|
|
|
bool SeqList<T, N>::remove(const T &x)
|
|
|
{
|
|
|
int i{find(x)}; // 先去找x在哪个位置
|
|
|
if (i >= 0)
|
|
|
{
|
|
|
--last;
|
|
|
for (int j{i}; j <= last; j++)
|
|
|
slist[j] = slist[j + 1]; // 依次前移，保证表连续
|
|
|
return true;
|
|
|
}
|
|
|
return false; // 表中不存在
|
|
|
}
|
|
|
|
|
|
template <typename T, int N>
|
|
|
T &SeqList<T, N>::operator[](int i)
|
|
|
{
|
|
|
return slist[i]; // 和原生[]一样不检查下标
|
|
|
}
|
|
|
|
|
|
template <typename T, int N>
|
|
|
void SeqList<T, N>::print() const
|
|
|
{
|
|
|
for (int i{0}; i <= last; ++i)
|
|
|
std::cout << slist[i] << ' ';
|
|
|
std::cout << '\n';
|
|
|
}
|
|
|
|
|
|
#endif |
