顺序表

结构描述

#include <iostream>
#include <cstdlib>
#define MAX 100
using namespace std;

typedef int DataType;

class SeqList {
private:
    DataType * A;
    int Size;
public:

    //在当前位置插入
    void InsertThisPos(int Pos, DataType X);

    //删除当前位置的元素
    void DeleteThisPos(int Pos);

    //排序
    void SelectionSort();

    //查找
    int SearchByValue(DataType Value);
    DataType SearchByPos(int Pos);
    DataType GetMax();
    DataType GetMin();

    //修改
    void ModifyByValue(DataType NowValue, DataType NewValue);
    void ModifyByPos(int Pos, DataType NewValue);

    //初始化
    void Init();
    //判空
    bool IsFull();
    //判满
    bool IsEmpty();
    //打印
    void Print();
    //交换
    void Swap(DataType & X, DataType & Y);
    //下标合法性
    bool PosOK(int Pos);
};

初始化

创建一个一个一个空表，把空间分配好，把 Size 的初值设置为 0。

void SeqList::Init() {
    A = (DataType *)malloc(sizeof (DataType) * MAX);
    Size = 0;
    //The sizeof (*A) * MAX is the size of Array that named A.
    memset(A, 0, sizeof (*A) * MAX);
}

判空、判满、打印、下标合法

判空： Size == 0
判满： Size == MAX
打印： 遍历、逐个打印
下标合法：下标取值在 \([0, Size - 1]\) 之间，若合法，返回 true 反之返回 false

bool SeqList::IsFull() {
    return MAX == Size;
}
bool SeqList::IsEmpty() {
    return 0 == Size;
}
void SeqList::Print() {
    int i;
    for (i = 0; i < Size; i++) {
        printf("A[%d] == %d%c", i, A[i], i % 10 == 0? '\n': ' ');
    }
}
bool SeqList::PosOk(int Pos) {
    return Pos >= 0 && Pos < Size;    
}

插入

• 表满：报错
• 非满：
  • 下标不合法：报错
  • 合法执行操作：
  • 把 Pos 及其之后的元素向后挪动一位;
  • 在 Pos 位上插入 X;
  • Size 增加 1;

void SeqList::InsertThisPos(int Pos, DataType X) {
    if (Pos > Size || Pos < 0) {
        cout << "Position Error!" << endl;
        exit(-1);
    }

    //下标正常
    for (int i = Size; i > Pos; i--) {
        A[i+1] = A[i];
    }
    A[Pos] = X;
    Size++;
}

尾插

直接调用插入函数，把位置设置为 Size

void SeqList::PushBack(DataType X) {
    InsertThisPos(Size, X);
}

删除

• 表空或下标不合法：报错
• 非空且下标合法：
  • 从 Pos 开始，把所有的位都向前挪动一位：
    A[Pos] = A[Pos + 1]
A[Size - 2] = A[Size - 1]
Size--

void SeqList::DeleteThisPos(int Pos) {
    //表空，或者下标不合法
    if (IsEmpty() || !PosOK(Pos)) {
        cout << "List Is Empty!" << endl;
        exit(-1);
    }

    int i;
    for (i = Pos; i < Size - 1; i++) {
        A[i] = A[i + 1];
    }

    Size--;
}

排序

• 表空：报错
• 非空：任选一种排序算法

查找

按下标查找：

• 表空或下标不合法：报错
• 非空且下标合法：直接返回该下标所在的值

DataType SeqList::SearchByPos(int Pos) {
    if (IsEmpty() || !PosOK(Pos)) {
        cout << "List Is Empty or Position Error!" << endl;
        exit(-1);
    }

    return A[Pos];
}

按值查找：

• 表空：报错
• 非空且下标合法：遍历对比，找到返回下标，找不到返回 -1

int SeqList::SearchByValue(DataType Value) {
    if (IsEmpty()) {
        cout << "List Is Empty!" << endl;
        exit(-1);
    }

    int i;
    for (i = 0; i < Size; i++) {
        if (A[i] == Value) {
            return i;
        }
    }

    return -1;
}

获取最大、最小值

• 表空：报错
• 非空：遍历打擂，寻找最大/小值，或者先排序，然后找最大/小值

DataType SeqList::GetMax() {
    if (IsEmpty()) {
        cout << "List Is Empty!" << endl;
        exit(-1);
    }

    int i;
    int Max = 0;
    for (i = 1; i < Size; i++) {
        if (A[Max] < A[i]) {
            Max = i;
        }
    }

    return A[Max];
}

DataType SeqList::GetMin() {
    if (IsEmpty()) {
        cout << "List Is Empty!" << endl;
        exit(-1);
    }

    int i;
    int Min = 0;
    for (i = 1; i < Size; i++) {
        if (A[Min] > A[i]) {
            Min = i;
        }
    }

    return A[Min];   
}

修改

按照下标修改：

• 检测下标合法性
• 修改：修改成功后给出提示

void SeqList::ModifyByPos(int Pos, DataType X) {
    //检测下标
    if (IsEmpty() || !PosOK(Pos)) {
        cout << "List Is Empty or Position Error!" << endl;
        exit(-1);
    }

    A[Pos] = X;
    cout << "修改成功" << endl;
}

按值修改：

• 查找：查找不成功报错（查找方法中有下标合法性检测，这里不用考虑）
• 修改：修改成功后给出提示

void SeqList::ModifyByValue(DataType NowValue, DataType NewValue) {
    int Tmp = SearchByValue(NowValue);
    if (Tmp == -1) {
        cout << "Value is Not Exist" << NowValue << endl;
        exit(-1);
    }

    A[Tmp] = NewValue;
}

踩坑记录

第一步初始化的时候，使用 memset() 函数的时候就踩了个大坑，想使用 memset() 函数把数组 A 初始化一下，结果把数组的大小给错写成了指针 A 的大小。

错误

// 一个DataType的大小
memset(A, 0, sizeof (*A));
//一个DataType * 的大小。
memset(A, 0, sizeof (A));

在插入的条件中，把表长 Size 和数组长 MAX 给搞混了

if (Pos > MAX || Pos < 0) {
    cout << "Position Error!" << endl;
    exit(-1);
}

应该用

if (Pos > Size || Pos < 0) {
    cout << "Position Error!" << endl;
    exit(-1);
}

同样的，在判下标合法与否的操作中也犯了同样的错误

bool SeqList::PosOK(int Pos) {
    return Pos >= 0 && Pos < MAX;
}

应当改为：

bool SeqList::PosOK(int Pos) {
    return Pos >= 0 && Pos < Size;
}