【数据结构】实现顺序表（c++）

数据结构 前端之家
前端之家收集整理的这篇文章主要介绍了【数据结构】实现顺序表（c++），前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。

头文件：



#pragma once

#include <iostream>
using namespace std;

template <class Type>
class SeqList
{

	public:
		SeqList(size_t sz = INIT_SIZE);
		~SeqList();
	public:
		bool isfull()const
		{
			return size > capacity;
		}
		bool isempty()const
		{
			return size == 0;
		}
	public:
		void show_list();
		void tail_insert(const Type &x);
		void head_insert(const Type &x);
		void sort();
		void head_delete();
		void tail_delete();
		void pos_insert(int pos,const Type &x);
		void val_insert(const Type &x);
		void pos_delete(int pos);
		int find(const Type &x);
		void val_delete(const Type &x);
		int length();
		void reverse();
		void clear();
		void destroy();
		void quit_system(Type &x);
	private:
		enum{ INIT_SIZE = 8 };
		Type *base;
		size_t size;
		size_t capacity;
};

// 构造函数
template<class Type>
SeqList<Type>::SeqList(size_t sz = INIT_SIZE)
{
	capacity = sz > INIT_SIZE ? sz : INIT_SIZE;
	base = new Type[capacity];
	size = 0;
}

// 析构函数
template<class Type>
SeqList<Type>::~SeqList()
{
	delete base;
}

// 显示
template<class Type>
void SeqList<Type>::show_list()
{
	if (size == 0)
	{
		cout << "the table is empty!" << endl;
		return;
	}
	for (int i = 0; i < size; ++i)
	{
		cout << base[i] << "  ";
	}
	cout << endl;
}

// 尾插
template<class Type>
void SeqList<Type>::tail_insert(const Type &x)
{
	// 判断表是否满
	if (isfull())
	{
		cout << "table is full,can not insert!" << endl;
		return;
	}
	// 进行尾插
	base[size] = x;
	size++;
}

// 头插
template<class Type>
void SeqList<Type>::head_insert(const Type &x)
{
	// 判断表是否满
	if (isfull())
	{
		cout << "the table is full,can not insert!" << endl;
		return;
	}
	// 把元素往后移
	for (int i = size; i > 0; --i)
	{
		base[i] = base[i - 1];
	}
	// 进行头插
	base[0] = x;
	size++;
}

// 排序
template<class Type>
void SeqList<Type>::sort()
{
	for (int i = 1; i < size; ++i)
	{
		for (int j = 0; j < size - i; ++j)
		{
			if (base[j]>base[j + 1])
			{
				int temp = base[j];
				base[j] = base[j + 1];
				base[j + 1] = temp;
			}
		}
	}
}

// 头删
template<class Type>
void SeqList<Type>::head_delete()
{
	if (isempty())
	{
		cout << "the table is empty,can not delete!" << endl;
		return;
	}
	for (int i = 0; i < size; ++i)
	{
		base[i] = base[i + 1];
	}
	size--;
}

// 尾删
template<class Type>
void SeqList<Type>::tail_delete()
{
	if (isempty())
	{
		cout << "the table is empty,can not delete!" << endl;
		return;
	}
	size--;
}

// 按位插入
template<class Type>
void SeqList<Type>::pos_insert(int pos,const Type &x)
{
	if (isfull())
	{
		cout << "the table is full,can not insert!" << endl;
		return;
	}
	if (pos<0 || pos>size)
	{
		cout << "the position is illegal!" << endl;
		return;
	}
	else
	{
		for (int i = size; i > pos; --i)
		{
			base[i] = base[i - 1];
		}
		base[pos] = x;
		size++;
	}
}

// 按值插入
template<class Type>
void SeqList<Type>::val_insert(const Type &x)
{
	if (isfull())
	{
		cout << "the table is full,can not insert!" << endl;
		return;
	}
	tail_insert(x);
	sort();
}

// 按位删除
template<class Type>
void SeqList<Type>::pos_delete(int pos)
{
	if (isempty())
	{
		cout << "the table is empty,can not delete!" << endl;
		return;
	}
	if (pos<0 || pos>size - 1)
	{
		cout << "the position is illegal!" << endl;
		return;
	}
	else
	{
		for (int i = pos; i < size; ++i)
		{
			base[i] = base[i + 1];
		}
		size--;
	}
}

// 查找
template<class Type>
int SeqList<Type>::find(const Type &x)
{
	for (int i = 0; i < size; ++i)
	{
		if (base[i] == x)
			return i;
	}
	cout << "the value is not exist!" << endl;
	return 0;
}

// 按值删除
template<class Type>
void SeqList<Type>::val_delete(const Type &x)
{
	if (isempty())
	{
		cout << "the table is empty,can not delete!" << endl;
		return;
	}
	int pos = find(x);
        if(pos == -1)
	{
		cout<<"the number is not exist!"<<endl;
	}
	else
	{
		for (int i = pos; i < size; ++i)
		{
			base[i] = base[i + 1];
		}
		size--;
	}
}

// 求表长
template<class Type>
int SeqList<Type>::length()
{
	return size;
}

// 反转表内容
template<class Type>
void SeqList<Type>::reverse()
{
	if (isempty())
	{
		cout << "the table is empty,can not operate!" << endl;
			return; 
	}
	int i = 0;
	int j = size - 1;
	while (i < j)
	{
		int temp = base[i];
		base[i] = base[j];
		base[j] = temp;
		++i;
		--j;
	}
}

// 清除表
template<class Type>
void SeqList<Type>::clear()
{
	size = 0;
}

// 摧毁表
template<class Type>
void SeqList<Type>::destroy()
{
	base = NULL;
}

// 退出系统
template<class Type>
void SeqList<Type>::quit_system(Type &x)
{
	x = 0;
}



主函数：



// 用c++实现顺序表

#include "SeqList.h"

int main()
{
	SeqList<int> mylist;
	int input = 1;
	int insert;
	int pos;
	while (input)
	{
		cout << "*********************************************************************" << endl;
		cout << "*     [1] show_list                       [2] tail_insert           *" << endl;
		cout << "*     [3] head_insert                     [4] sort                  *" << endl;
		cout << "*     [5] head_delete                     [6] tail_delete           *" << endl;
		cout << "*     [7] pos_insert                      [8] val_insert            *" << endl;
		cout << "*     [9] pos_delete                      [10] find                 *" << endl;
		cout << "*     [11] val_delete                     [12] length               *" << endl;
		cout << "*     [13] reverse                        [14] clear                *" << endl;
		cout << "*     [15] destroy                        [16] quit_system          *" << endl;
		cout << "*********************************************************************" << endl;
		cout << "please choose:";
		cin >> input;
		switch (input)
		{
		case 1:
			mylist.show_list();
			break;
		case 2:
			cout << "please enter the number to be inserted(-1 end):" << endl;
			while (cin >> insert,insert != -1)
			{
				mylist.tail_insert(insert);
			}
			break;
		case 3:
			cout << "please enter the number to be inserted(-1 end):" << endl;
			while (cin >> insert,insert != -1)
			{
				mylist.head_insert(insert);
			}
			break;
		case 4:
			mylist.sort();
			break;
		case 5:
			mylist.head_delete();
			break;
		case 6:
			mylist.tail_delete();
			break;
		case 7:
			cout << "please enter the position you want to insert:" << endl;
			cin >> pos;
			cout << "please enter the number to be inserted:" << endl;
			cin >> insert;
			mylist.pos_insert(pos,insert);
			break;
		case 8:
			cout << "please enter the number to be inserted:" << endl;
			cin >> insert;
			mylist.val_insert(insert);
			break;
		case 9:
			cout << "please enter the position you want to delete:" << endl;
			cin >> pos;
			mylist.pos_delete(pos);
			break;
		case 10:
			cout << "please enter the number to be found:" << endl;
			cin >> insert;
			cout << mylist.find(insert) << endl;
			break;
		case 11:
			cout << "please enter the number you want to delete:" << endl;
			cin >> insert;
			mylist.val_delete(insert);
			break;
		case 12:
			cout << mylist.length() << endl;
			break;
		case 13:
			mylist.reverse();
			break;
		case 14:
			mylist.clear();
			break;
		case 15:
			mylist.destroy();
			break;
		case 16:
			mylist.quit_system(input);
			break;
		default:
			break;

		}
	}

	return 0;
}


显示：



清除：




查找：




头删：




头插：





求长度：



按位删除：




按位插入：



退出系统：




反转：




排序：




尾删：



尾插：




按值删除：




按值插入：


原文链接：https://www.f2er.com/datastructure/382666.html

猜你在找的数据结构相关文章

【数据结构】键树
键树的基本概念 键树又称数字查找树（Digital Search Tree）。 它是一棵度大于等于2的树，...
【数据结构】绪论
[TOC] 基本概念 数据： 数据 是对客观事物的符号表示，在计算机科学中指所有能输入到计算机...
【数据结构】证明法
[TOC] 反证法 基本概念： 一般地，假设原命题不成立（即 在原命题的条件下，结论不成立），...
数据结构与算法系列之目录
最近抽空整理了&quot;数据结构和算法&quot;的相关文章。在整理过程中，对于每种数...
【数据结构】数组
[TOC] 矩阵在计算机图形学、工程计算中占有举足轻重的地位。在数据结构中考虑的是如何用最...
[操作系统]操作系统中断机制
1.当中断发生时，cpu立即进入核心态 2.当中断发生后，当前进程进入暂停状态，操作系统内核...
[日常] 浏览器前进后退与数据结构的思想
一张图保存一下 红点是当前地址 白色箭头是新打开页面 黑色箭头是后退页面 栈的思想 , 后退...
[算法] 开放寻址法解决哈希冲突方式
开放寻址法：又称开放定址法，当哈希冲突发生时，从发生冲突的那个单元起，按照一定的次序...
二叉树的基本概念介绍与代码实现（多图+代码）
@ 树的基本概念 图1 树的结点 结点：使用树结构存储的每一个数据元素都被称为“结点”。例...
史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)
1.准备工作 首先包含头文件，定义链表结构体，产生随即链表的范围，定义全局头尾节点。 #i...
LinuxWindowsCentOSUbuntuNginxWebServiceScalaMemcacheApacheRedisDockerBashAzureTomcatLNMPShell数据结构服务器运维网络安全
xebugnodemondocker-copydcoselasticsearcwindows-contdocker-windodocker-awsamazon-cloudenvoyproxyhashicorp-vaswisscomdevkafka-pythonzscalerphoton-osdocker-swarmkamongoogle-cloudconcoursewso2-ampersistent-vapi-managerprocess-manamanjarojenkins-workhypriotremoteapikeystonejsbitcoindbitcoin-test