//顺序表的各种操作（包括头删，尾删，插入，逆序，摧毁，清空等等） //头文件 #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; } } }
