C++ 顺序表实现及分析

本文主要是介绍C++ 顺序表实现及分析，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

• • 一、头文件声明部分
  • 二、源文件实现部分
  • 三、分析
  • • 1、初始化工作
    • 2、收尾工作
    • 3、打印出顺序表中元素
    • 4、调整容量
    • • Ⅰ该环节在全局规划的分析
      • Ⅱ环节内容分析
    • 5、尾插、头插、特定位置插入
    • 6、尾删、头删、特定位置删除
    • 7、查找元素
    • 8、特定位置修改

一、头文件声明部分

#ifndef __SEQLIST_H__
#define __SEQLIST_H__

#include<iostream>
#include<cassert>
using namespace std;
typedef int DataType;

class Seqlist
{
public:
	Seqlist();//初始化工作
	~Seqlist();//收尾工作
	void SeqlistPrint();//打印出顺序表中元素
	void AdjustCapacity();//调整容量
	//增删插查改
	void SeqlistPushBack(int val);//尾插
	void SeqlistPushFront(int val);//头插
	void SeqlistInsert(int pos, int val);//在特定位置插入元素
	
	void SeqlistPopBack();//尾删
	void SeqlistPopFront();//头删
	void SeqlistErase(int pos);//删除特定位置的元素

	int SeqlistFind(int val);//查找元素

	void SeqlistModify(int pos, int val);//修改特定位置的元素
private:
	DataType* m_arr;
	int m_size;
	int m_capacity;
};
#endif

二、源文件实现部分

#include "Seqlist.h"

Seqlist::Seqlist() //初始化工作
{
	this->m_arr = NULL;
	this->m_capacity = 0;
	this->m_size = 0;
}
Seqlist::~Seqlist()//收尾工作
{
	delete []this->m_arr;
	this->m_arr = NULL;
	this->m_capacity = 0;
	this->m_size = 0;
}
void Seqlist::SeqlistPrint()//打印出顺序表中元素
{
	for (int i = 0; i < this->m_size; i++)
	{
		cout << this->m_arr[i] << ' ';
	}
}
void Seqlist::AdjustCapacity()//调整容量
{
	if (this->m_capacity == this->m_size)
	{
		int newCapacity = this->m_capacity == 0 ? 4 : this->m_capacity << 1;
		try
		{
			DataType* tmp = new DataType[newCapacity];
			this->m_capacity = newCapacity;
			for (int i = 0; i < this->m_size; i++)
			{
				tmp[i] = this->m_arr[i];
			}
			delete []this->m_arr;
			this->m_arr = tmp;
		}
		catch (bad_alloc& e)
		{
			cout << "bad_alloc caught: " << e.what() << endl;
		}

		//或者像下面这样，开辟内存失败后，返回空指针
		//DataType* tmp = new(nothrow) DataType[newCapacity];
		//if (NULL == tmp)
		//{
		//	cout << "开辟内存失败" << endl;
		//	exit(-1);
		//}
		//this->m_capacity = newCapacity;
		//for (int i = 0; i < this->m_size; i++)
		//{
		//	tmp[i] = this->m_arr[i];
		//}
		//delete[]this->m_arr;
		//this->m_arr = tmp;
	}
}
//增删插查改
void Seqlist::SeqlistPushBack(int val)//尾插
{
	AdjustCapacity();
	this->m_arr[this->m_size] = val;
	this->m_size++;
	//this->SeqlistInsert(this->m_size, val);
}
void Seqlist::SeqlistPushFront(int val)//头插
{
	AdjustCapacity();
	int end = this->m_size - 1;
	for (int i = end; i >= 0; i--)
	{
		this->m_arr[i + 1] = this->m_arr[i];
	}
	this->m_arr[0] = val;
	this->m_size++;
	//this->SeqlistInsert(0, val);
}
void Seqlist::SeqlistInsert(int pos, DataType val)//在特定位置插入元素
{
	AdjustCapacity();
	assert(pos <= this->m_size && pos >= 0);

	int end = this->m_size - 1;
	for (int i = end; i >= pos; i--)
	{
		this->m_arr[end - 1] = this->m_arr[end];
	}
	this->m_arr[pos] = val;
	this->m_size++;
}

void Seqlist::SeqlistPopBack()//尾删
{
	assert(this->m_size > 0);
	this->m_size--;
	//this->SeqlistErase(this->m_size - 1);
}
void Seqlist::SeqlistPopFront()//头删
{
	assert(this->m_size > 0);
	for (int i = 0; i < this->m_size; i++)
	{
		this->m_arr[i] = this->m_arr[i + 1];
	}
	this->m_size--;
	//this->SeqlistErase(0);
}
void Seqlist::SeqlistErase(int pos)//删除特定位置元素
{
	assert(pos < this->m_size && pos >= 0);
	for (int i = pos; i < this->m_size; i++)
	{
		this->m_arr[i] = this->m_arr[i + 1];
	}
	this->m_size--;
}

int Seqlist::SeqlistFind(DataType val)//查找元素
{
	for (int i = 0; i < this->m_size; i++)
	{
		if (val == this->m_arr[i])
		{
			return i;
		}
	}
	return -1;
}

void Seqlist::SeqlistModify(int pos, DataType val)//修改特定位置元素
{
	assert(pos < this->m_size&& pos >= 0);
	this->m_arr[pos] = val;
}

三、分析

1、初始化工作

完成m_arr、m_capacity、m_size的初始化；

2、收尾工作

释放m_arr后即置空。实际上，我认为，后面将m_capacity和m_size都置为0其实没有必要，因为实际上销毁这个顺序表对象后，我要用顺序表时，会重新实例化一个的。并且销毁对象，一般来说就是delete对象指针时，或函数结束时。

3、打印出顺序表中元素

依次打出即可。

4、调整容量

Ⅰ该环节在全局规划的分析

在增加和插入元素的环节中，当容量与实际现有大小将要（解释一下“将要”：还有一个元素之差时。因为增加和插入环节一次只能插入一个）相等时，需要调整容量。直接封装出去。

Ⅱ环节内容分析

• 首先要注意new的使用，new存在失败的情况，于是我做了相关处理，有两个解决方案，第一个是代码处未注释掉的内容，new在失败后会扔出一个异常；第二个是代码处注释掉的内容，通过使用语句“std::nothrow”让new在失败后返回一个空指针而不是异常，回顾：在C语言中malloc失败后，返回的就是空指针。
• 其次注意在new成功后的扩容操作，我们创建了一个临时的容量，转移数据，释放原容量，指针替换。

5、尾插、头插、特定位置插入

• 尾插：正因为数组是从0开始的，而数组的大小是从1开始的，于是我们可以在最后数组m_size的位置插入新元素。最后m_size加一。
• 头插：先有一个原地移动数组（出了第一个元素外）的操作，在数组第一个元素的位置上覆盖上新元素。
• 特定位置插入：同样是先原地移动数组后，覆盖上新元素。使用断言来防止输入的pos不规范。
• 补充：完全可以通过限制特定位置插入的功能来实现尾插和头插。注释部分即是这样实现的。

6、尾删、头删、特定位置删除

• 尾删：直接使用m_size减一的举措来达到目的，这都要归功于我们通过m_size来限制数组的访问范围的操作。
• 头删：首先通过原地向前移动数组来覆盖掉第一个元素，然后通过m_size减一来限制访问数组权限。
• 特定位置删除：原地移动数组覆盖。使用断言来防止输入的pos不规范。
• 补充：同“尾插、头插、特定位置插入”环节中的补充思想一样。

7、查找元素

如果用二分查找效率更高，但是我们需要先对数组进行排序，排序在不同的情境下会起到截然相反的效果，有时是使数据更有序的行为，但有时是破环原来数据的顺序的行为。并且实际上，我对二分查找的边界问题还是处于不解状态，于是选择使用遍历进行查找元素的操作，找到返回位置，没找到返回-1；并且使用断言来防止输入的pos不规范。

8、特定位置修改

首先用断言对输入的pos进行检查，在pos这个位置进行覆盖修改。

这篇关于C++ 顺序表实现及分析的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！