[数据结构与算法]C++顺序表的基本操作算法

#include <iostream>
using namespace std;

char pause;

typedef int T;
template <class T>
class SqList
{
private:
    T *elem;      // 表首址
    int length;   // 表长
    int listsize; // 表容量
public:
    SqList(int m);           // 构造函数，创建容量为m的空表
    ~SqList();               // 构造函数，删除表空间
    void CreateList(int n);  // 创建具有n个元素的线性表
    void Insert(int i, T e); // 在表中第i个位置插入元素
    T Delete(int i);         // 删除表中第i个元素
    T GetElem(int i);        // 获取第i个元素的值
    int Locate(T e);         // 元素定位
    void Clear();            // 清空表
    int Empty();             // 测表空
    int Full();              // 测表满
    int Length();            // 测表长
    void ListDisp();         // 输出表元素
};
template <class T>
SqList<T>::SqList(int m)
{                    // 构建函数，创建一表容量为m的空表
    elem = new T[m]; // 申请表空间
    length = 0;      // 空表，表长为0
    listsize = m;    // 表容量为m
}
template <class T>
SqList<T>::~SqList()
{                  // 析构函数
    delete[] elem; // 释放表空间
    length = 0;
    listsize = 0;
}
template <class T>
void SqList<T>::CreateList(int n)
{ // 创建表长度为n的顺序表
    if (n > listsize)
        throw "参数非法";
    cout << "请依次输入" << n << "个元素：" << endl;
    for (int i = 1; i <= n; i++)
        cin >> elem[i - 1];
    length = n;
}
template <class T>
void SqList<T>::Insert(int i, T e)
{ // 在第i个位置差入元素，如不能插入，显示异常信息
    if (length > listsize)
        throw "上溢";
    if (i < 1 || i > length + 1)
        throw "插入位置异常";
    for (int j = length; j >= i; j--)
        elem[j] = elem[j - 1];
    elem[i - 1] = e;
    length++;
}
template <class T>
T SqList<T>::Delete(int i)
{ // 删除表中第i个位置元素，如不能删除，显示异常信息
    T x;
    if (length == 0)
        throw "下溢";
    if (i < 1 || i > length)
        throw "删除位置异常";
    x = elem[i - 1];
    for (int j = i; j < length; j++)
        elem[j - 1] = elem[j];
    length--;
    return x;
}
template <class T>
int SqList<T>::Locate(T e)
{ // 元素定位，若找到，返回该元素在表中的位序；未找到，返回0
    for (int i = 0; i < length - 1; i++)
        if (elem[i] == e)
            return i + 1; // 找到
    return 0;             // 未找到
}
template <class T>
void SqList<T>::Clear()
{
    length = 0;
}
template <class T>
T SqList<T>::GetElem(int i)
{ // 获取第i个元素的值
    T e;
    if (i < 1 || i > length)
        throw "位置不合法";
    e = elem[i - 1];
    return 0;
}
template <class T>
int SqList<T>::Empty()
{                    // 判表空。若空，返回1；否则，返回0
    if (length == 0) // 表空
        return 1;
    return 0; // 表空
}
template <class T>
int SqList<T>::Full()
{                           // 判表满。若满，返回1；否则，返回0
    if (length == listsize) // 表满
        return 1;
    return 0; // 表不满
}
template <class T>
int SqList<T>::Length()
{
    return length;
}
template <class T>
void SqList<T>::ListDisp()
{ // 遍历输出表
    for (int i = 0; i < length; i++)
    {
        cout << i + 1 << "\t";
        cout << elem[i] << endl;
    }
}

int main()
{
    int i;
    T e;
    SqList<int> L(20); // 建立容量为20、元素类型为整型的空顺序表
    system("cls");     // 执行系统命令cls，清屏
    int choice;
    do
    {
        cout << "1-创建顺序\n";
        cout << "2-在链表第i个位置插入元素\n";
        cout << "3-删除顺序表中第i个位置的元素\n";
        cout << "4-返回第i个元素的值\n";
        cout << "5-元素定位\n";
        cout << "6-清空表\n";
        cout << "7-测表空\n";
        cout << "8-测表满\n";
        cout << "9-测表长\n";
        cout << "10-显示表\n";
        cout << "11-退出\n";
        cout << "Enter choice:";
        cin >> choice;
        switch (choice)
        {
        case 1: // 创建表
            cout << "请输入要创建的顺序表中元素的个数：";
            cin >> i;
            cout << endl;
            L.CreateList(i);
            break;
        case 2: // 元素插入
            cout << "请输入插入位置：";
            cin >> i;
            cout << endl;
            cout << "请输入插入元素的值：";
            cin >> e;
            cout << endl;
            L.Insert(i, e);
            break;
        case 3: // 元素删除
            cout << "请输入删除位置：";
            cin >> i;
            cout << endl;
            L.Delete(i);
            cin.get(pause);
            system("pause");
            break;
        case 4: // 返回第i个元素值
            cout << "请输入要查询的元素位置";
            cin >> i;
            e = L.GetElem(i);
            cout << "第" << i << "个元素值为：" << e << endl;
            cin.get(pause);
            system("pause");
        case 5: // 按值进行元素查询
            cout << "请输入要查询的元素值：";
            cin >> e;
            i = L.Locate(e);
            cout << "查询元素" << e << "位于在表中的位置为：" << i << endl;
            cin.get(pause);
            system("pause");
            break;
        case 6: // 清空表
            L.Clear();
            cout << "表已清空" << endl;
            cin.get(pause);
            system("pause");
            break;
        case 7: // 测表空
            i = L.Empty();
            if (i)
                cout << "表空" << endl;
            else
                cout << "表不空" << endl;
            cin.get(pause);
            system("pause");
            break;
        case 8: // 测表满
            i = L.Full();
            if (i)
                cout << "表满" << endl;
            else
                cout << "表未满" << endl;
            cin.get(pause);
            system("pause");
            break;
        case 9: // 测表长
            i = L.Length();
            cout << "表长为：" << i << endl;
            cin.get(pause);
            system("pause");
            break;
        case 10: // 遍历输出表
            L.ListDisp();
            cout << endl;
            cin.get(pause);
            system("pause");
            break;
        case 11: // 退出
            break;
        default: // 非法选项
            cout << "Invalid choice\n";
            break;
        }
    } while (choice != 11);
    return 0;
}