数据结构 | 顺序表的基本实现_数据结构顺序表基本算法的实现

学习教材：《数据结构——从概念到C++实现》

分类专栏：数据结构与算法(C++)

文章目录

前言

正文

1 顺序表概述

1.1 线性表的逻辑结构

1.2 线性表的顺序存储结构

2 顺序表实现

---

前言

        最近刚在学习《数据结构与算法》，单纯地跟课、看书觉得并不能很好的掌握好这些知识点，所以决定尝试将学习的知识点归纳总结，也将其进行代码实现，强化对知识点的理解。即作为笔记、实践，又作为我的思路分享。因为初学，难免有不正确、不恰当之处，敬请指正！

正文

1 顺序表概述

        线性表（linear list）简称表，是 n（ n≥0）个数据元素的有限序列，跟据存储结构的不同可以分为顺序表和链表。

        线性表的顺序存储结构为顺序表（sequential list），其基本思路使用一段地址连续的存储单元依次存储线性表的数据元素，具有随机存取（random access）结构。

2 顺序表实现

        先定义出顺序表类，成员变量实现顺序表存储结构，成员函数实现线性表的基本操作。由于线性表的数据元素类型不确定，采用C++的模板机制，定义出模板类SeqList（本文类模板中的成员函数均使用类内声明、类外定义）。

// Sequential List
const int MaxSize = 100; // 规定顺序表最多可以接受多少元素，可以跟据实际情况修改
template<class DataType> // 定义模板类SeqList
class SeqList
{
public:
	// 建立空的顺序表
	SeqList(); 
	// 建立长度为length的顺序表
	SeqList(DataType arr[],int length);
	// 析构函数
	~SeqList() {};
	// 按位查找元素
	DataType Get(int i);
	// 按值查找元素，返回元素序号
	int Locate(DataType x);
	// 插入操作，在第i个位置插入值为x的元素
	void Insert(int i, DataType x);
	// 删除操作，删除第i个元素
	DataType Delect(int i);
	// 判断是否为空表
	int Empty();
	// 遍历操作，按序号依次输出各元素
	void PrintList();
	// 返回线性表长度
	int Length();
 
private:
	DataType m_Arr[MaxSize];
	int m_length;
};

2.1 建立空的顺序表

        在顺序表类中，成员函数m_length用于记录顺序表的长度，因此在建立空的顺序表时，只需要使用无参构造函数，将实例化对象的m_length置为0即可。

// 建立空的顺序表
template<class DataType>
SeqList<DataType>::SeqList()
{
	this->m_length = 0;
}

2.2 建立指定长度的顺序表

        建立指定长度的顺序表，需要给定的数据元素传入到顺序表中，并将传入元素个数作为顺序表的长度。将给定的数据元素存放在数组arr[ ]中，并将给定元素个数一并传入。通过使用有参构造函数，传入数组arr[ ]以及顺序表长度。

        同时，为避免传入的给定数据元素个数超出前面设定的MaxSize导致程序异常，使用throw关键字来显式地抛出异常。

// 建立长度为length的顺序表
template<class DataType>
SeqList<DataType>::SeqList(DataType arr[], int length)
{
	if (length > MaxSize) throw"参数非法";
	for (int i = 0; i < length; i++)
	{
		this->m_Arr[i] = arr[i];
	}
	this->m_length = length;
}

2.3 析构函数

        顺序表时静态存储分配，在顺序表变量退出作用域时，自动释放改变了所占内存单元，故无须销毁，析构函数为空即可。

2.4 按位查找元素

        顺序表中第 i 个元素在数组中下标为 i-1 的位置，因此使用顺序表人员实现按位查找。

// 按位查找元素
template<class DataType>
DataType SeqList<DataType>::Get(int i)
{
	if (i > this->m_length || i < 1) throw"参数非法";
	else return this->m_Arr[i - 1];
}

2.5 按值查找元素

        在顺序表中按值操作，需要对顺序表中的元素依次进行比较，如果查到到相应的值，则将元素的序号（不是数组下标）返回；否则返回0，即查找失败。

// 按值查找元素，返回元素序号
template<class DataType>
int SeqList<DataType>::Locate(DataType x)
{
	for (int i = 0; i < this->m_length; i++)
	{
		if (this->m_Arr[i] == x)
			return (i + 1);
	}
	return 0;
}

2.6 插入操作

        插入操作时，在表的第 i 个位置插入值为 x 的元素，将原有的第 i-1 个位置上的元素依次往后移动，使长度为 n 的顺序表的长度变为 n+1。

        且为避免输入的 i 不符合要求（即不满足 1 ≤ i ≤ m_length），使用throw关键字来显式地抛出异常。

// 插入操作，在第i个位置插入值为x的元素
template<class DataType>
void SeqList<DataType>::Insert(int i, DataType x)
{
	if (this->m_length == MaxSize) throw"上溢";
	if (i<1 || i>this->m_length) throw"插入位置错误";
	for (int j = this->m_length; j >= i; j--)
	{
		this->m_Arr[j] = this->m_Arr[j - 1];
	}
	this->m_Arr[i - 1] = x;
	this->m_length++;
}

2.7 删除操作

        删除操作时将表的第 i 个元素删除，使长度为 n 的顺序表变成长度为 n-1 的顺序表，且返回删除的元素的值。操作逻辑上，即将第i个元素删除后，后面的元素依次提到前面一个空出的位置上；顺序表长度也做了减1处理。

        且为避免输入的 i 不符合要求（即不满足 1 ≤ i ≤ m_length），使用throw关键字来显式地抛出异常。

template<class DataType>
DataType SeqList<DataType>::Delect(int i)
{
	DataType x;
	if (this->m_length == 0) throw"上溢";
	if (i<1 || i>this->m_length) throw"删除位置错误";
	x = this->m_Arr[i - 1];
	for (int j = i; j < this->m_length; j++)
	{
		this->m_Arr[j - 1] = this->m_Arr[j];
	}
	this->m_length--;
	return x;
}

2.8 判断空表

        顺序表类成员变量 m_length 中存储着顺序表的长度，判断空表操作只需判断长度 m_length 为0即可。

// 判断是否为空表
template<class DataType>
int SeqList<DataType>::Empty()
{
	if (this->m_length != 0)
		return 1;
	else return 0;
}

2.9 遍历操作

        在顺序表中，遍历操作即按下标一次输出各元素，因此使用循环语句实现。

// 遍历操作，按序号依次输出各元素
template<class DataType>
void SeqList<DataType>::PrintList()
{
	for (int i = 0; i < this->m_length; i++)
	{
		cout << this->m_Arr[i] << " " ;
	}
	cout << endl;
}

2.10 返回顺序表长度

        如判断空表中所述，返回顺序表长度同样只需返回成员函数 m_length 的值即可。

template<class DataType>
int SeqList<DataType>::Length()
{
	return this->m_length;
}

3 全部代码

#pragma once
#include<iostream>
#include<string>
using namespace std;
 
// Sequential List
// 规定顺序表最多可以接受多少元素
const int MaxSize = 100;
template<class DataType> // 定义模板类SeqList
class SeqList
{
public:
	// 建立空的顺序表
	SeqList(); 
	// 建立长度为length的顺序表
	SeqList(DataType arr[],int length);
	// 析构函数
	~SeqList() {};
	// 按位查找元素
	DataType Get(int i);
	// 按值查找元素，返回元素序号
	int Locate(DataType x);
	// 插入操作，在第i个位置插入值为x的元素
	void Insert(int i, DataType x);
	// 删除操作，删除第i个元素
	DataType Delect(int i);
	// 判断是否为空表
	int Empty();
	// 遍历操作，按序号依次输出各元素
	void PrintList();
	// 返回线性表长度
	int Length();
 
private:
	DataType m_Arr[MaxSize];
	int m_length;
};
 
// 建立空的顺序表
template<class DataType>
SeqList<DataType>::SeqList()
{
	this->m_length = 0;
}
 
// 建立长度为length的顺序表
template<class DataType>
SeqList<DataType>::SeqList(DataType arr[], int length)
{
	if (length > MaxSize) throw"参数非法";
	for (int i = 0; i < length; i++)
	{
		this->m_Arr[i] = arr[i];
	}
	this->m_length = length;
}
 
// 按位查找元素
template<class DataType>
DataType SeqList<DataType>::Get(int i)
{
	if (i > MaxSize || i < 1) throw"参数非法";
	else return this->m_Arr[i - 1];
}
 
// 按值查找元素，返回元素序号
template<class DataType>
int SeqList<DataType>::Locate(DataType x)
{
	for (int i = 0; i < this->m_length; i++)
	{
		if (this->m_Arr[i] == x)
			return (i + 1);
	}
	return 0;
}
 
// 插入操作，在第i个位置插入值为x的元素
template<class DataType>
void SeqList<DataType>::Insert(int i, DataType x)
{
	if (this->m_length == MaxSize) throw"上溢";
	if (i<1 || i>this->m_length) throw"插入位置错误";
	for (int j = this->m_length; j >= i; j--)
	{
		this->m_Arr[j] = this->m_Arr[j - 1];
	}
	this->m_Arr[i - 1] = x;
	this->m_length++;
}
 
// 删除操作，删除第i个元素
template<class DataType>
DataType SeqList<DataType>::Delect(int i)
{
	DataType x;
	if (this->m_length == 0) throw"上溢";
	if (i<1 || i>this->m_length) throw"删除位置错误";
	x = this->m_Arr[i - 1];
	for (int j = i; j < this->m_length; j++)
	{
		this->m_Arr[j - 1] = this->m_Arr[j];
	}
	this->m_length--;
	return x;
}
 
// 判断是否为空表
template<class DataType>
int SeqList<DataType>::Empty()
{
	if (this->m_length != 0)
		return 1;
	else return 0;
}
 
// 遍历操作，按序号依次输出各元素
template<class DataType>
void SeqList<DataType>::PrintList()
{
	for (int i = 0; i < this->m_length; i++)
	{
		cout << this->m_Arr[i] << " " ;
	}
	cout << endl;
}
 
template<class DataType>
int SeqList<DataType>::Length()
{
	return this->m_length;
}
 
 
// 测试代码
/*void test01()
{
	int r[5] = { 1,2,3,4,5 };
	SeqList<int> s(r, 5);
	cout << "当前线性表的数据为： ";
	s.PrintList();
	cout << "插入数据中......" << endl;
	s.Insert(3, 7);
	cout << "当前线性表的长度为：" << s.Length() << endl;
	cout << "当前线性表的数据为： ";
	s.PrintList();
	int num = 0;
	cout << "请输入查找的数据：" << endl;
	cin >> num;
	int i = s.Locate(num);
	if (i == 0)cout << "查找失败！！" << endl;
	else cout << "元素：" << num << "的位置为：" << i << endl;
	
	cout << "请输入查找元素的序号：" << endl;
	cin >> num;
	cout << "第" << num << "个元素为：" << s.Get(num) << endl;
	cout << "请输入要删除的元素序号：" << endl;
	cin >> num;
	i = s.Delect(num);
	cout << "删除的元素为：" << i << "，删除后线性表的数据为：" << endl;
	s.PrintList();
}*/
 
int main()
{
	// test01(); // 测试代码
	return 0;
}

初学数据结构与算法，若有不正确之处，敬请指正啦~