C++ 顺序表的基本操作

顺序表的基本操作:


"seqlist.h"头文件

#ifndef SEQLIST_H_INCLUDED
#define SEQLIST_H_INCLUDED

#include <iostream>
#include <stdlib.h>
using namespace std;

template <class Type>
class SeqList
{
public:
    SeqList(size_t sz = INIT_SIZE);
    bool IsFull() const
    {
        return size >= capacity;
    }
    bool IsEmpty() const
    {
        return size == 0;
    }
    void show_list();
    void push_back(const Type& x);
    void push_front(const Type& x);
    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& x);
    int length() const;
    void clear();
    void destory();
    void resver();
    void sort();

private:
    enum{INIT_SIZE = 10};
    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>
void SeqList<Type>::show_list()
{
	for(int i=0; i<size; ++i)
	{
		cout<<base[i]<<" ";
	}
	cout<<endl;
}

template<class Type>
void SeqList<Type>::push_back(const Type &x)
{
	if(IsFull())
	{
		cout<<"顺序表已满,不能插入!"<<endl;
		return;
	}
	base[size++] = x;
}

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>::pop_back()
{
    if(IsEmpty())
	{
		cout<<"顺序表为空,不能删除!"<<endl;
		return;
	}
	size--;
}

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>::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>
void SeqList<Type>::insert_val(const Type& x)
{
    int pos = find(x);
    if(pos == -1)
    {
        return;
    }
	for(int i=size; i>=pos; --i)
	{
		base[i+1] = base[i];
	}
	base[pos] = x;
	size++;
}

template<class Type>
void SeqList<Type>::delete_pos(int pos)
{
	for(int i=pos; i<size; ++i)
	{
		base[i] = base[i+1];
	}
	size--;
}

template<class Type>
void SeqList<Type>::delete_val(const Type &x)
{
	int pos = find(x);
	if(pos == -1)
	{
		return;
	}
    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;
	}
	return -1;
}

template<class Type>
int SeqList<Type>::length() const
{
	return size;
}

template<class Type>
void SeqList<Type>::clear()
{
	size = 0;
}

template<class Type>
void SeqList<Type>::destory()
{
	delete []base;
	base = NULL;
}


template<class Type>
void SeqList<Type>::resver()
{
	for(int i=0; i<size/2; ++i)
	{
		int temp =base[i];
		base[i] = base[size-i-1];
		base[size-i-1] = temp;
	}
	for(int i=0; i<size; ++i)
    {
        cout<<base[i]<<" ";
    }
	cout<<endl;
}

template<class Type>
void SeqList<Type>::sort()
{
	for(int j=0; j<size-1; ++j)
    {
        for(int i=0; i<size-1-j; ++i)
        {
            if(base[i]>base[i+1])
            {
                int temp = base[i];
                base[i] = base[i+1];
                base[i+1] =  temp;
            }
        }
    }
    for(int i=0;i<size;++i)
    {
        cout<<base[i]<<" ";
    }
	cout<<endl;
}
#endif // SEQLIST_H_INCLUDED
主函数:

#include "SeqList.h"

int main()
{
    SeqList<int> mylist;
    int select = 1;
    int Item;
    int pos;
    while(select)
    {
        system("CLS");
        cout<<"*************************************"<<endl;
        cout<<"* [0]quit_system      [1]show_list  *"<<endl;
        cout<<"* [2]push_back        [3]push_front *"<<endl;
        cout<<"* [4]pop_back         [5]pop_front  *"<<endl;
        cout<<"* [6]insert_pos       [7]insert_val *"<<endl;
        cout<<"* [8]delete_pos       [9]delete_val *"<<endl;
        cout<<"* [10]find            [11]length    *"<<endl;
        cout<<"* [12]clear           [13]destory   *"<<endl;
        cout<<"* [14]resver          [15]sort      *"<<endl;
        cout<<"*************************************"<<endl;
        cout<<"请输入你的选择:>";
        cin>>select;
        switch(select)
		{
        case 1:
			mylist.show_list();
			system("pause");
			break;
		case 2:
			cout<<"请输入要插入的值(-1结束):>";
			while(cin>>Item, Item!=-1)
			{
				mylist.push_back(Item);
			}
			break;
		case 3:
			cout<<"请输入要插入的值(-1结束):>";
			while(cin>>Item, Item!=-1)
			{
				mylist.push_front(Item);
			}
			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);
			break;
		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;
			pos = mylist.find(Item);
			cout<<pos<<endl;
			system("pause");
			break;
		case 11:
			pos = mylist.length();
			cout<<pos<<endl;
			system("pause");
			break;
		case 12:
			mylist.clear();
			break;
		case 13:
			mylist.destory();
			break;
		case 14:
			mylist.resver();
			system("pause");
			break;
		case 15:
			mylist.sort();
			system("pause");
			break;
		default:
			break;
        }
    }
    return 0;
}



郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。