概要

  本文包括利用c++编写的顺序表的类模板以及其可视化界面。

整体架构流程

  1. 在sqList.h头文件中定义一个SqList类模板，并在类模板中声明构造函数、析构函数和要实现的成员函数；
  2. 在sqList.cpp文件中给出所有函数的定义；
  3. 在顺序表.cpp文件中完成可视化界面的设计。

技术名词解释

  • 顺序表：

        顺序表是一种基本的线性数据结构，它采用连续的存储空间来存储元素。顺序表中的元素按照顺序依次存储，每个元素在内存中占据固定大小的存储空间。

        在顺序表中，元素的插入、删除和访问操作相对简单高效。通过使用数组或固定大小的内存块，顺序表可以实现随机访问，即通过下标直接访问任意位置的元素，时间复杂度为O(1)。

顺序表的特点包括：

  1. 索引访问：顺序表支持通过索引直接访问元素，通过下标可以快速访问顺序表中的元素。

  2. 连续存储：顺序表使用连续的存储空间，元素在内存中的存储位置是相邻的。这也使得顺序表在内存中占用的空间比较大，并且在插入和删除元素时需要移动其他元素。

  3. 定长限制：顺序表的长度在创建时就确定了，无法动态调整大小。如果需要增加或减少容量，需要重新创建一个更大或更小的顺序表，并将元素复制到新表中。

  4. 插入和删除效率低：在顺序表中插入或删除元素时，需要移动其他元素来保持顺序表的连续性。这涉及到元素的复制或移动操作，时间复杂度为O(n)，其中n是元素个数。

        顺序表适用于对访问频繁、插入和删除操作较少的场景，例如按位置随机查找元素的需求较多的情况。然而，如果需要频繁进行插入和删除操作，顺序表的性能可能较差，需要考虑使用其他数据结构，如链表。

  • c++类模板

        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个元素的线性表”的功能是利用随机生成的随机数来对顺序表进行填充。作者是个菜鸟，欢迎各位大佬留言指错。

点击阅读全文
# c++ # visualstudio # 数据结构
Logo
腾讯云开发者社区

腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。

更多推荐

cover

动物识别系统 python实现+UI

avatar 腾讯云开发者社区

Linux下安装MySQL8.0(超详细)

Linux下安装MySQL8.0(超详细)

avatar 腾讯云开发者社区
cover

Linux——创建编写并编译一个C程序

avatar 腾讯云开发者社区