概要
本文包括利用c++编写的顺序表的类模板以及其可视化界面。
整体架构流程
-
在sqList.h头文件中定义一个SqList类模板，并在类模板中声明构造函数、析构函数和要实现的成员函数；
-
在sqList.cpp文件中给出所有函数的定义；
-
在顺序表.cpp文件中完成可视化界面的设计。
技术名词解释
顺序表是一种基本的线性数据结构，它采用连续的存储空间来存储元素。顺序表中的元素按照顺序依次存储，每个元素在内存中占据固定大小的存储空间。
在顺序表中，元素的插入、删除和访问操作相对简单高效。通过使用数组或固定大小的内存块，顺序表可以实现随机访问，即通过下标直接访问任意位置的元素，时间复杂度为O(1)。
顺序表的特点包括：
-
索引访问：顺序表支持通过索引直接访问元素，通过下标可以快速访问顺序表中的元素。
-
连续存储：顺序表使用连续的存储空间，元素在内存中的存储位置是相邻的。这也使得顺序表在内存中占用的空间比较大，并且在插入和删除元素时需要移动其他元素。
-
定长限制：顺序表的长度在创建时就确定了，无法动态调整大小。如果需要增加或减少容量，需要重新创建一个更大或更小的顺序表，并将元素复制到新表中。
-
插入和删除效率低：在顺序表中插入或删除元素时，需要移动其他元素来保持顺序表的连续性。这涉及到元素的复制或移动操作，时间复杂度为O(n)，其中n是元素个数。
顺序表适用于对访问频繁、插入和删除操作较少的场景，例如按位置随机查找元素的需求较多的情况。然而，如果需要频繁进行插入和删除操作，顺序表的性能可能较差，需要考虑使用其他数据结构，如链表。
C++类模板是一种通用的编程工具，用于创建可以适应多种数据类型的类或函数。类模板允许在定义类时使用参数化类型，这样可以根据不同的类型生成具体的类。
类模板使用 <template> 关键字定义，并在尖括号内指定一个或多个模板参数。模板参数可以是类型、常量或其他模板，用于在类的定义中表示占位符。
实现代码
sqList.h文件：
#pragma once
#include<iostream>
#include<ctime>
using namespace std;
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 ListDisplay(); //输出表元素
};
sqList.cpp文件：
#include"sqList.h"
template <class T>
SqList<T>::SqList(int m) //构造函数，创建容量为m的空表
{
elem = new T[m];
if (!elem)
throw "内存分配失败";
length = 0;
listsize = 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 "表长超过表空间,创建失败";
srand((unsigned int)time(NULL));
for (int i = 0; i < n; i++)
elem[i] = rand() % 101;
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个元素的值
{
if (length <= 0)
throw "下溢";
if (i<1 || i>length)
throw "删除位置异常";
T a = elem[i - 1];
for (int j = i - 1; j < length - 1; j++)
elem[j] = elem[j + 1];
length--;
return a;
}
template <class T>
T SqList<T>::GetElem(int i) //获取第i个元素的值
{
if (length <= 0)
throw "空表无法获取元素值";
if (i<1 || i>length)
throw "访问位置异常";
return elem[i - 1];
}
template <class T>
int SqList<T>::Locate(T e) //元素定位
{
for (int i = 0; i < length; i++)
if (elem[i] == e)
return i + 1;
return 0;
}
template <class T>
void SqList<T>::Clear() //清空表
{
length = 0;
}
template <class T>
int SqList<T>::Empty() //测表空
{
if (length == 0)
return 1;
return 0;
}
template <class T>
int SqList<T>::Full() //测表满
{
if (length == listsize)
return 1;
return 0;
}
template <class T>
int SqList<T>::Length() //测表长
{
return length;
}
template <class T>
void SqList<T>::ListDisplay() //输出表元素
{
if (length == 0)
cout << "空表！！！" << endl;
else
for (int i = 0; i < length; i++)
cout << "表中第" << (i + 1) << "个元素值为：" << elem[i] << endl;
}
顺序表.cpp文件：
#include"sqList.h"
//使用类模板时需要把函数的声明和定义都写在.h头文件中,如果非要分开写，需要把.cpp源文件引入
#include"sqList.cpp"
#include<conio.h>
#define ListSize 10
void menu() {
cout << "***************************************" << endl;
cout << "***** 1.创建具有n个元素的线性表 *****" << endl;
cout << "***** 2.在表中第i个位置插入元素 *****" << endl;
cout << "***** 3.删除表中第i个元素的值 *****" << endl;
cout << "***** 4.获取第i个元素的值 *****" << endl;
cout << "***** 5.元素定位 *****" << endl;
cout << "***** 6.清空表 *****" << endl;
cout << "***** 7.测表空 *****" << endl;
cout << "***** 8.测表满 *****" << endl;
cout << "***** 9.测表长 *****" << endl;
cout << "***** 0.输出表元素 *****" << endl;
cout << "***** 其他键退出 *****" << endl;
cout << "***************************************" << endl;
}
int main() {
//创建顺序表对象
SqList<int> sqlist(ListSize);
while (true) {
//菜单
menu();
//用户选择
try {
char key = _getch();
switch (key) {
case '1'://1.创建具有n个元素的线性表
{
system("cls");
cout << "*****1.创建具有n个元素的线性表*****" << endl;
int n;
cout << "请输入元素个数n：" << endl;
cin >> n;
sqlist.CreateList(n);
cout << "创建成功！" << endl;
}
break;
case '2'://2.在表中第i个位置插入元素
{
system("cls");
cout << "*****2.在表中第i个位置插入元素*****" << endl;
int i, e;
cout << "请输入插入位置i：" << endl;
cin >> i;
cout << "请输入插入元素：" << endl;
cin >> e;
sqlist.Insert(i, e);
cout << "插入成功！" << endl;
}
break;
case '3'://3.删除表中第i个元素的值
{
system("cls");
cout << "*****3.删除表中第i个元素的值 *****" << endl;
int i;
cout << "您想删除第几个元素？" << endl;
cin >> i;
int e = sqlist.Delete(i);
cout << "已删除第" << i << "个元素：" << e << endl;
}
break;
case '4'://4.获取第i个元素的值
{
system("cls");
cout << "*****4.获取第i个元素的值 *****" << endl;
int i;
cout << "您想获取第几个元素？" << endl;
cin >> i;
int e=sqlist.GetElem(i);
cout << "获取成功！" << endl;
cout << "表中第" << i << "个元素值为：" << e << endl;
}
break;
case '5'://5.元素定位
{
system("cls");
cout << "*****5.元素定位 *****" << endl;
int e;
cout << "请输入需要定位的元素：" << endl;
cin >> e;
if (sqlist.Locate(e)) {
cout << "定位成功！" << endl;
cout << "该元素在表中第" << sqlist.Locate(e) << "个位置" << endl;
}
else {
cout << "表中不存在该元素" << endl;
}
}
break;
case '6'://6.清空表
{
system("cls");
cout << "*****6.清空表 *****" << endl;
cout << "是否清空？按“1”清空，其他键取消操作" << endl;
char clear;
clear = _getch();
if (clear == '1') {
sqlist.Clear();
cout << "清空成功！" << endl;
}
else {
cout << "取消操作成功！" << endl;
}
}
break;
case '7'://7.测表空
{
system("cls");
cout << "*****7.测表空 *****" << endl;
cout << (sqlist.Empty() ? "表空" : "表非空") << endl;
}
break;
case '8'://8.测表满
{
system("cls");
cout << "*****8.测表满 *****" << endl;
cout << (sqlist.Full() ? "表满" : "表未满") << endl;
}
break;
case '9'://9.测表长
{
system("cls");
cout << "*****9.测表长 *****" << endl;
cout << "该表长度为：" << sqlist.Length() << endl;
}
break;
case '0'://0.输出表元素
{
system("cls");
cout << "*****0.输出表元素 *****" << endl;
sqlist.ListDisplay();
}
break;
default:
{
system("cls");
cout << "欢迎下次使用！" << endl;
system("pause");
return 0;
}
break;
}
}
catch (const char* s) {
cout << s << endl;
}
system("pause");
system("cls");
}
system("pause");
return 0;
}
小结
本文代码使用的IDE工具为Visual Studio 2019。本文代码中“创建具有n个元素的线性表”的功能是利用随机生成的随机数来对顺序表进行填充。作者是个菜鸟，欢迎各位大佬留言指错。
