C/C++教程

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++ 顺序表实现及分析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!