前言：

顺序表的本质其实就是使用一个数组对数据进行存储，我们在此博客中，基于C++的类与对象来实现顺序表。

一、构成：

顺序表由三个部分组成，一个数组，一个用来表示数组容量的整型和一个表示已存放数据数量的整型。

讯享网

所以我们的成员变量就如下：

typedef int ElemType; class SqList { private: ElemType* data; int size; int capacity; };

我们需要实现的功能有：插入，删除，打印，查找，更改。同时，我们对类的内部操作还有初始化，扩容，销毁等操作。

二、包含

在使用C++实现顺序表的时候，我们只需要包含一个头文件<iostream>,但是们可以提前展开命名空间std。

讯享网#include<iostream> using namespace std;

三、函数实现

1）初始化

初始化在此可以作为类的构造函数，其参数可以使用一个缺省参数。

SqList(int n = 4) { data = (ElemType*)malloc(sizeof(ElemType) * n); size = 0; capacity = n; }

函数说明：构造函数SqList在对象实例化的时候自动调用，在实例化的时候，缺省参数n可以传值，也可以用默认值，为data开辟一块空间，并且将size初始化为0，容量capacity初始化为n。

2）销毁

销毁在此处可以作为类的析构函数，类生命周期结束时自动调用。

讯享网~SqList() { free(data); data = nullptr; capacity = 0; size = 0; }

函数说明：将data的空间释放，data指向空，容量和大小都设为0.

3）扩容

该函数不被类外调用，所以可将其放在private修饰，其作用时当顺序表满了时，将顺序表扩容一倍。

 void boarden() { ElemType* tmp = (ElemType*)realloc(data, sizeof(ElemType) * capacity * 2); if (tmp) { data = tmp; capacity = capacity * 2; } else perror("boarden error!"); }

函数说明：要先用tmp储存并且验证是否扩容成功，以免造成扩容失败同时原内存丢失。

4）插入

在数组的第pos个位置插入数据

思路：将pos位置及以后的数据往后推移一个位置，再将数据填到对应位置。但是推移的时候，必须从后面往前面推移，而不是从前往后推，否则会将原来的数据覆盖。

讯享网void insert(int pos, int val) { if (size == capacity) boarden(); for (int i = size - 1; i >= pos - 1; i--) { data[i + 1] = data[i]; } data[pos - 1] = val; size++; }

5）删除

删除pos位置的数据

思路：将pos位置之后的数据往前面运动即可，从pos+1位置到第size个位置。注意此时必须从前往后移动，否则原来数据会被覆盖。

 

void del(int pos) { if (size) { for (int i = pos - 1; i < size; i++) { data[i] = data[i + 1]; } size -= 1; } else perror("Delete Fail,Empty List"); }

6）查找

查找并返回第一个大小为val的位置

思路：遍历并比对其值

讯享网int find(ElemType val) { for (int i = 0; i < size; i++) { if (data[i] == val) return i + 1; } }

7）打印

将顺序表按序打印出来

思路：遍历并打印其值

void print() { for (int i = 0; i < size; i++) cout << data[i] << " "; cout << endl; }

四、源码分享

讯享网#include<iostream> using namespace std; typedef int ElemType; class SqList { private: ElemType* data; int size; int capacity; void boarden() { ElemType* tmp = (ElemType*)realloc(data, sizeof(ElemType) * capacity * 2); if (tmp) { data = tmp; capacity = capacity * 2; } else perror("boarden error!"); } public: SqList(int n = 4) { data = (ElemType*)malloc(sizeof(ElemType) * n); size = 0; capacity = n; } ~SqList() { free(data); data = nullptr; capacity = 0; size = 0; } void insert(int pos, int val) { if (size == capacity) boarden(); for (int i = size - 1; i >= pos - 1; i--) { data[i + 1] = data[i]; } data[pos - 1] = val; size++; } void del(int pos) { if (size) { for (int i = pos - 1; i < size; i++) { data[i] = data[i + 1]; } size -= 1; } else perror("Delete Fail,Empty List"); } void print() { for (int i = 0; i < size; i++) cout << data[i] << " "; cout << endl; } int find(ElemType val) { for (int i = 0; i < size; i++) { if (data[i] == val) return i + 1; } } };