头文件:
#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; }
显示:
清除:
查找:
头删:
头插:
求长度:
按位删除:
按位插入:
退出系统:
反转:
排序:
尾删:
尾插:
按值删除:
按值插入: