程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C++數據結構 順序表的實現(模板類的實現)

C++數據結構 順序表的實現(模板類的實現)

編輯:關於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;
		}
	}
}



 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved