用C++ 实现顺序表的封装: (使用模板)
判表空, 判表满,获取 顺序表已占用长度, 显示表内信息;
头插, 尾插, 头删, 尾删;
特定位置插入数据, 特定数据处插入数据;
特定位置删除数据, 特定数据处删除数据;
查找特定位置数据, 查找特定数据所在位置;
表内数据排序;
去掉表内重复数据, 删除表内所有数据, 删除顺序表;
清屏;
#ifndef _MYSEQLIST_H
#define _MYSEQLIST_H
#include <cstdlib>
#include <iostream>
using namespace std;
template<typename Type> //定义模板类
class SeqList
{
public:
SeqList(int sz = DEFAULT_SIZE);
~SeqList();
bool is_empty()const;
bool is_full()const;
int len_list()const;
void show_list()const;
bool push_back(const Type &x);
bool push_front(const Type &x);
bool pop_back();
bool pop_front();
bool insert_pos(int idex, Type &x);
bool insert_value(Type &value, Type &x);
bool delete_pos(int idex);
bool delete_value(Type &value);
Type &find_pos(int idex)const;
int find_value(Type &x)const;
void sort();
void resever();
void clear();
void remove_all();
void destory();
private:
enum{DEFAULT_SIZE = 8};
int capacity; //初始申请顺序表长度
int size; //表内实际存放数据长度
Type *base; //存放数据的数组
};
template<typename Type>
SeqList<Type>::SeqList(int sz) //构造函数
{
capacity = sz > DEFAULT_SIZE ? sz : DEFAULT_SIZE;
base = new Type[capacity];
size = 0;
}
template<typename Type>
SeqList<Type>::~SeqList() //析构函数
{
delete []base;
base = NULL;
capacity = size = 0;
}
template<typename Type>
bool SeqList<Type>::is_empty()const //判顺序表是否为空
{
return size == 0;
}
template<typename Type>
bool SeqList<Type>::is_full()cons //判顺序表是否已满 t
{
return size >= capacity;
}
template<typename Type>
int SeqList<Type>::len_list()const //获取表的长度
{
return size;
}
template<typename Type>
void SeqList<Type>::show_list()const //显示表内数据
{
int i = 0;
for (i = 0; i < size; ++i) {
cout<<base[i]<<" ";
}
cout<<endl;
}
template<typename Type>
bool SeqList<Type>::push_back(const Type &x) //尾插
{
if (!is_full()) {
base[size++] = x;
return true;
}
return false;
}
template<typename Type>
bool SeqList<Type>::push_front(const Type &x) //头插
{
int i = 0;
if (!is_full()) {
for(i = size - 1; i >= 0; --i) {
base[i + 1] = base[i];
}
base[0] = x;
size++;
return true;
}
return false;
}
template<typename Type>
bool SeqList<Type>::pop_back() //尾删
{
if (!is_empty()) {
size--;
return true;
}
return false;
}
template<typename Type>
bool SeqList<Type>::pop_front() //头删
{
int i = 0;
if (!is_empty()) {
for (i = 1; i< size; ++i) {
base[i - 1] = base[i];
}
size--;
return true;
}
return false;
}
template<typename Type>
bool SeqList<Type>::insert_pos(int idex, Type &x) //特定位置插入数据
{
int i = 0;
if (is_full() || idex < 1 || idex > size + 1) {
return false;
}
for (i = idex - 1; i < size; ++i) {
base[i + 1] = base[i];
}
base[idex - 1] = x;
size++;
return true;
}
template <typename Type>
bool SeqList<Type>::insert_value(Type &value, Type &x) //特定数据处插入数据
{
int idex = 0;
int i = 0;
if (is_full()) {
return false;
}
for (i = 0; i < size; ++i) {
if (base[i] = value) {
idex = i;
break;
}
}
for (i = idex; i < size; ++i) {
base[i + 1] = base[i];
}
base[idex] = x;
size++;
return true;
}
template <typename Type>
bool SeqList<Type>::delete_pos(int idex) //特定位置删除数据
{
int i = 0;
if (is_empty() || idex < 1 || idex > size) {
return false;
}
for (i = idex; i < size; ++i) {
base[i - 1] = base[i];
}
size--;
return true;
}
template <typename Type>
bool SeqList<Type>::delete_value(Type &value) //特定数据处删除数据
{
int idex = 0;
int i = 0;
if (is_empty()) {
return false;
}
for (i = 0; i < size; ++i)
{
if (base[i] = value) {
idex = i;
break;
}
}
for (i = idex; i < size - 1; ++i) {
base[i] = base[i + 1];
}
size--;
return true;
}
template <typename Type>
Type &SeqList<Type>::find_pos(int idex)const //查找特定位置数据
{
if (is_empty() || idex < 1 || idex > size) {
cout<< "Can not find the value!"<<endl;
return base[-1];
}
return base[idex - 1];
}
template <typename Type>
int SeqList<Type>::find_value(Type &x)const //查找特定数据所在位置
{
int i = 0;
if(!is_empty()) {
for (i = 0; i < size; ++i) {
if (base[i] == x) {
return i + 1;
}
}
}
cout<< "Can not find the value!"<<endl;
return -1;
}
template <typename Type>
void SeqList<Type>::sort() //表内数据排序
{
int i = 0;
int j = 0;
Type temp = 0;
for (i = 1; i < size; ++i) {
j = i - 1;
temp = base[i];
while (temp < base[j]) {
base[j + 1] = base[j];
j--;
}
base[j + 1] = temp;
}
}
template <typename Type>
void SeqList<Type>::resever() //去掉表内重复数据
{
int i = 0;
int j = 0;
Type temp;
for (i = 0; i < size - 1; ++i) {
temp = base[i];
for (j = i + 1; j < size; ++j) {
if (base[j] == temp) {
delete_pos(j + 1);
}
}
}
}
template <typename Type>
void SeqList<Type>::clear() //清屏
{
system("clear");
}
template <typename Type>
void SeqList<Type>::remove_all() //删除表内所有数据
{
while (size) {
size--;
}
}
template <typename Type>
void SeqList<Type>::destory() //删除整个顺序表
{
remove_all();
delete []base;
}
#endif
------------------------------------------------------------------------------------------------------------
//顺序表测试程序
#include <cstdlib>
#include "myseqlist.h"
int main(int argc, const char *argv[])
{
int sz = 0;
int select = 0;
int item = 0;
int idex = 0;
int value = 0;
int value1 = 0;
cout<<"请输入初始化所需顺序表的长度:";
cin>>sz;
SeqList<int> mylist(sz);
while(1)
{
cout<<"*****************************************************"<<endl;
cout<<"* [1] push_back(-1结束) [2] push_fornt(-1结束) *"<<endl;
cout<<"* [3] show_list [0] quit system *"<<endl;
cout<<"* [4] pop_back [5] pop_fornt *"<<endl;
cout<<"* [6] insert_pos [7] insert_value *"<<endl;
cout<<"* [8] delete_pos [9] delete_value *"<<endl;
cout<<"* [10] find_pos [11] find_value *"<<endl;
cout<<"* [12] sort [13] resever *"<<endl;
cout<<"* [14] clear [15] length *"<<endl;
cout<<"* [16] remove_all [17] destroy *"<<endl;
cout<<"*****************************************************"<<endl;
cout<<"请选择: ";
cin>>select;
switch(select)
{
case 0:
cout<<"Bye Bye!"<<endl;
exit(-1);
case 1:
cout<<"请输入要插入的数据(以-1结束): "<<endl;
while(cin>>item, item != -1)
{
mylist.push_back(item);
}
break;
case 2:
cout<<"请输入要插入的数据(以-1结束):"<<endl;
while(cin>>item, item != -1)
{
mylist.push_front(item);
}
break;
case 3:
mylist.show_list();
break;
case 4:
mylist.pop_back();
break;
case 5:
mylist.pop_front();
break;
case 6:
cout<<"请依次输入要插入的位置和数据:"<<endl;
cin>>idex>>value;
mylist.insert_pos(idex, value);
break;
case 7:
cout<<"请依次输入要插入位置的数据和要插入的数据:"<<endl;
cin>>value>>value1;
mylist.insert_value(value, value1);
break;
case 8:
cout<<"请输入要删除的位置:"<<endl;
cin>>idex;
mylist.delete_pos(idex);
break;
case 9:
cout<<"请输入要删除位置的数据:"<<endl;
cin>>value;
mylist.delete_value(value);
break;
case 10:
cout<<"请输入要查找的位置:"<<endl;
cin>>idex;
cout<< mylist.find_pos(idex)<<endl;
break;
case 11:
cout<<"请输入要查找的数据:"<<endl;
cin>>value;
cout<< mylist.find_value(value)<<endl;
break;
case 12:
mylist.sort();
break;
case 13:
mylist.resever();
break;
case 14:
mylist.clear();
break;
case 15:
cout<<mylist.len_list()<<endl;
break;
case 16:
mylist.remove_all();
break;
case 17:
mylist.destory();
break;
default:
cout<<"请重新输入:"<<endl;
}
}
return 0;
}