C++數據結構 順序表的實現(模板類的實現)
利用模板類實現順序表的操作
實現的功能:
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();
break;
case 15:
//int a;
//a = mylist.length();
mylist.sort(/*0,a-1*/);
break;
default:
break;
}
}
}
