//顺序表的各种操作（包括头删，尾删，插入，逆序，摧毁，清空等等）
//头文件
#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 push_front(const Type &x);
void push_back(const Type &x);
void insert_pos(int pos,const Type &x);
int find(const Type &key);
void pop_front();
void pop_back();
void sort();
void insert_val(const Type &x);
void delete_pos(int pos);
void delete_val(const Type &x);
int length();
void clear();
void destory();
void reverse();
void quit_system(int &a);
private:
enum{ INIT_SIZE = 8 };
Type *base;
size_t capacity;
size_t size;
};
template<class Type> //构造函数
SeqList<Type>::SeqList(size_t sz)
{
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 << "数据表为空。" << endl;
return;
}
for (int i = 0; i<size; ++i)
{
cout << base[i] << " ";
}
cout << endl;
}
template<class Type> //头插
void SeqList<Type>::push_front(const Type &x)
{
if (isfull())
{
cout << "顺序表已满，不能插入." << endl;
return;
}
for (int i = size; i > 0; --i)
{
base[i] = base[i - 1];
}
base[0] = x;
size++;
}
template<class Type> //尾插
void SeqList<Type>::push_back(const Type &x)
{
if (isfull())
{
cout << "顺序表已满，不能插入." << endl;
return;
}
base[size] = x;
size++;
}
template<class Type> //按位置插
void SeqList<Type>::insert_pos(int pos,const Type &x)
{
if (pos<0 || pos>size)
{
cout << "插入的位置不正确。" << endl;
return;
}
if ( isfull() )
{
cout << "顺序表已满，不能插入." << endl;
return;
}
for (int i = size; i > pos; --i)
{
base[i] = base[i - 1];
}
base[pos] = x;
size++;
}
template<class Type> //查找
int SeqList<Type>::find(const Type &key)
{
for (int i = 0; i<size; ++i)
{
if (base[i] == key)
return i;
}
return -1;
}
template<class Type> //头删
void SeqList<Type>::pop_front()
{
if (isempty())
{
cout << "顺序表为空，不能删除。" << endl;
return;
}
for (int i = 0; i < size; ++i)
{
base[i] = base[i + 1];
}
size--;
}
template<class Type>
void SeqList<Type>::pop_back() //尾删
{
if (isempty())
{
cout << "顺序表为空，不能删除。" << endl;
return;
}
size--;
}
template<class Type> //排序
void SeqList<Type>::sort()
{
if (isempty())
{
return;
}
for (int i = 1; i < size; i++)
{
for (int j = 0; j < size - i; j++)
{
int temp;
if (base[j]>base[j + 1])
{
temp = base[j];
base[j] = base[j + 1];
base[j + 1] = temp;
}
}
}
}
template<class Type> //按值插入
void SeqList<Type>::insert_val(const Type &x)
{
push_back(x); //尾插
sort(); //排序
}
template<class Type> //按位置删除
void SeqList<Type>::delete_pos(int pos)
{
if (isempty())
{
cout << "顺序表为空，不能删除。" << endl;
return;
}
if (pos < 0 || pos >= size)
{
cout << "删除的位置不正确。" << endl;
return;
}
for (int i = pos; i < size; ++i)
{
base[i] = base[i + 1];
}
size--;
}
template<class Type> //按值删除
void SeqList<Type>::delete_val(const Type &x)
{
if (isempty())
{
cout << "顺序表为空，不能删除。" << endl;
return;
}
int pos=find(x);
if (pos == -1)
{
cout << "未找到该数。" << endl;
return;
}
delete_pos(pos);
}
template<class Type> //求长度
int SeqList<Type>::length()
{
return size;
}
template<class Type> //清除表
void SeqList<Type>::clear()
{
size = 0;
}
template<class Type> //摧毁表
void SeqList<Type>::destory()
{
base = NULL;
}
template<class Type> //逆序
void SeqList<Type>::reverse()
{
for (int i = 0,j = size - 1; i < size / 2; i++,j--)
{
int temp = base[i];
base[i] = base[j];
base[j] = temp;
}
}
template<class Type> //退出
void SeqList<Type>::quit_system(int &a)
{
a = 0;
}
//主函数
#include"SeqList.h"
void main()
{
SeqList<int> mylist;
int select = 1;
int Item;
int pos;
while (select)
{
cout << "************************************************************************" << endl;
cout << "* [1] show_list [2] quit_system *" << endl;
cout << "* [3] push_front [4] push_back *" << endl;
cout << "* [5] pop_front [6] pop_back *" << endl;
cout << "* [7] insert_pos [8] insert_val *" << endl;
cout << "* [9] delete_pos [10] delete_val *" << endl;
cout << "* [11] find [12] length *" << endl;
cout << "* [13] clear [14] destory *" << endl;
cout << "* [15] reverse(逆序) [16] sort(顺序) *" << endl;
cout << "************************************************************************" << endl;
cout << "请选择功能：";
cin >> select;
switch (select)
{
case 1:
mylist.show_list();
break;
case 2:
mylist.quit_system(select);
break;
case 3:
cout << "请输入您要插入的数(以-1结束)：";
while (cin >> Item,Item != -1)
{
mylist.push_front(Item);
}
break;
case 4:
cout << "请输入您要插入的数(以-1结束)：";
while (cin >> Item,Item !=-1)
{
mylist.push_back(Item);
}
break;
case 5:
mylist.pop_front();
break;
case 6:
mylist.pop_back();
break;
case 7:
cout << "请输入您要插入的位置：";
cin >> pos;
cout << "请输入您要插入的值：";
cin >> Item;
mylist.insert_pos(pos,Item);
break;
case 8:
cout << "请输入要插入的数：";
cin >> Item;
mylist.insert_val(Item);
break;
case 9:
cout << "请输入要删的位置：";
cin >> pos;
mylist.delete_pos(pos);
break;
case 10:
cout << "请输入要删的值:";
cin >> Item;
mylist.delete_val(Item);
break;
case 11:
cout << "请输入要查找的数：";
cin >> Item;
pos = mylist.find(Item);
if (pos != -1)
{
cout << "该数为第" << pos << "个数" << endl;
}
cout << "未找到该数。"<<endl;
break;
case 12:
cout <<"该顺序表长度为："<< mylist.length() << endl;
break;
case 13:
mylist.clear();
break;
case 14:
mylist.destory();
break;
case 15:
mylist.reverse();
break;
case 16:
mylist.sort();
break;
default:
break;
}
}
}
原文链接：https://www.f2er.com/datastructure/382665.html
