利用模板类实现顺序表的操作
实现的功能:
1.尾插，2.头插，3.显示，4.尾删，5.头删，6.按位置，7.插按值插，8.按位置删，9.按值删，10.按值查，11.求表长，12.清除数据，13.摧毁该顺序表，14.反转，15.排序(冒泡排序，快速排序)。
头文件源代码:
?
#pragma once // 防止重复编译
#include
using namespace std;
template
class SeqList { public: SeqList(size_t sz=INIT_SIZE); public: bool isfull()const {return size>=capacity;} bool isempty()const {return size==0;} public: void push_back(const Type &x); //尾插 void push_front(const Type &x); //头插 void show_list(); //显示 void pop_back(); //尾删 void pop_front(); //头删 void insert_pos(int pos,const Type &x);//按位置插 void insert_val(const Type &x); //按值插 void delete_pos(int pos); //按位置删 void delete_val(const Type &x); //按值删 int find(const Type &key); //按值查 int length()const; //求表长 void clear(); //清除数据 void destroy(); //摧毁该顺序表 void reserv(); //反转 void sort(/*int low,int high*/); //排序 private: enum{INIT_SIZE=8}; Type *base; size_t capacity; size_t size; }; template
SeqList
::SeqList(size_t sz) { capacity = sz > INIT_SIZE ? sz : INIT_SIZE; base = new Type[capacity]; size = 0; } template
void SeqList
::push_back(const Type &x) { if(isfull()) { cout<<"顺序表已满,不能插入!"<
void SeqList
::push_front(const Type &x) { if(isfull()) { cout<<"顺序表已满,不能插入!"<
0; --i) { base[i] = base[i-1]; } base[0] = x; size++; } template
void SeqList
::show_list() { for(int i=0; i
%3Cbase%5Bi%5D%3C%3C%22%20%22%3B%0A%09%7D%0A%09cout%3C%3Cendl%3B%0A%7D%0A%0Atemplate%3Cclass%20Type%3E void SeqList
::pop_back() { if(isempty()) { cout<<"顺序表已满"<
void SeqList
::pop_front() { int i; for(i = 0;i
void SeqList
::insert_pos(int pos,const Type &x) { if(pos<0 || pos>size) { cout<<"要插入的位置非法!"<
pos; --i) { base[i] = base[i-1]; } base[pos] = x; size++; } template
void SeqList
::insert_val(const Type &x) { int pos; pos = find(x); insert_pos(pos,x); } template
void SeqList
::delete_pos(int pos) { int i; for(i = pos;i
void SeqList
::delete_val(const Type &x) { int pos = find(x); if(pos == -1) { return; } for(int i=pos; i
int SeqList
::find(const Type &key) { for(int i=0; i
int SeqList
::length()const { cout<<"表长是:"<
void SeqList
::clear() { while(size) { base[size--] = NULL; } } template
void SeqList
::destroy() { int i; delete base; base = NULL; capacity = 0; size = 0; } template
void SeqList
::reserv() { int i = 0; int m = size - 1; for(;i<=((size-1)/2);++i) { int tmp = base[i]; base[i] = base[m]; base[m] = tmp; m--; } } template
void SeqList
::sort()//排序 { for (int i=0;i<=size;i++) for (int j=i+1;j<=size-1;j++) { if(base[i]>base[j]) { int tmp = base[j]; base[j]=base[i]; base[i]=tmp; } } } /* template
///快速排序 void SeqList
::sort(int low,int high) { if(low >= high) { return; } int first = low; int last = high; int key = base[first]; //用字表的第一个记录作为枢轴 while(first < last) { while(first < last && base[last] >= key) { last--; } base[first] = base[last];//将比第一个小的移到低端 while(first < last && base[first] <= key) { first++; } base[last] = base[first];//将比第一个大的移到高端 } base[first] = key;//枢轴记录到位 sort(low, first-1); sort(first+1, high); } */
?
?
主函数:
?
#include"SeqList.h"
int main()
{
SeqList
mylist;
int select = 1;
int Item;
int pos;
while(select)
{
cout<<"**************************************"<
"; cin>>select; switch(select) { case 1: cout<<"请输入要插入的值(-1结束):>"; while(cin>>Item, Item!=-1) { mylist.push_back(Item); } break; case 2: cout<<"请输入要插入的值(-1结束):>"; 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<<"请输入要插入的位置:>"; cin>>pos; cout<<"请输入要插入的值:>"; cin>>Item; mylist.insert_pos(pos,Item); break; case 7: cout<<"请输入要插入的值:>"; cin>>Item; mylist.insert_val(Item); case 8: cout<<"请输入要删除的位置:>"; cin>>pos; mylist.delete_pos(pos); break; case 9: cout<<"请输入要删除的值:>"; cin>>Item; mylist.delete_val(Item); break; case 10: cout<<"请输入要查找的值:>"; cin>>Item; int pos; pos = mylist.find(Item); break; case 11: mylist.length(); break; case 12: mylist.clear(); break; case 13: mylist.destroy(); break; case 14: mylist.reserv()