顺序表
结构描述
#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;
}