順序表是在計算機內存中以數組的形式保存的線性表，是指用一組地址連續的存儲單元依次存儲數據元素的線性結構。
這樣的存儲方式使得線性表邏輯上相鄰的元素，其在物理存儲單元中也是相鄰的。只要知道了第一個元素的存儲地址，就可以知道線性表中任何一個元素的存儲地址。因此，線性表中的任何一個元素，
本文利用C++語言，在Windows平台 Visual Studio 2013開發環境下實現
1：動態增容 2：打印單鏈表 3：尾插 4：尾刪 5：頭插 6：頭刪 7：查找數據 8：在某位置後插入數據 9：刪除某位置的數據 10：找到並刪除x
****************************************************************************************************/
/*
功能：應用C++語言實現順序表的各項操作
基本的成員函數：
構造函數、拷貝構造函數、賦值運算符的重載、析構函數
** 1：動態增容
** 2：打印單鏈表
** 3：尾插
** 4：尾刪
** 5：頭插
** 6：頭刪
** 7：查找數據
** 8：在某位置後插入數據
** 9：刪除某位置的數據
** 10：刪除x
**
** By ：Lynn-Zhang
**
*/
/*****************************************************************************************************/
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
#include <assert.h>
typedef int DataType;
class SeqList
{
public:
SeqList(); //構造函數
SeqList(const SeqList & sList); //拷貝構造
SeqList& operator=(const SeqList& sList); //賦值運算符重載
~SeqList(); //析構函數
void CheckCapacity(); // 測容/擴容
void Print(); // 打印順序表
void PushBack(const DataType & x); // 尾插
void PopBack(); // 尾刪
void PushFront(const DataType & x); // 頭插
void PopFront(); // 頭刪
int Find(const DataType & x); //查找數據
void Insert(size_t pos, const DataType & x); //固定位置插入數據
void Erase(size_t pos); //刪除某位置的數據
int Remove(const DataType & x); //刪除數據x
private:
DataType* _array; //數據塊指針
size_t _size; //定義當前有效數據的個數
size_t _capicity; //容量
};
基本的成員函數
SeqList::SeqList()
:_array(NULL)
, _size(0)
, _capicity(0)
{}
SeqList::SeqList(const SeqList & sList)
:_array(new DataType[sList._size])
, _size(sList._size)
, _capicity(sList._capicity)
{
memcpy(_array, sList._array, sizeof(DataType)*_size);
}
SeqList& SeqList::operator=(const SeqList& sList)
{
if (&sList != this)
{
DataType *tmp = new DataType[sList._size];
delete[] _array;
_array = tmp;
_size = sList._size;
_capicity = sList._capicity;
memcpy(_array, sList._array, sizeof(DataType)*_size);
}
return *this;
}
SeqList::~SeqList()
{
if (_array != NULL)
{
delete[] _array;
_size = 0;
_capicity = 0;
}
}
測容，如果容量不夠要進行擴容
void SeqList::CheckCapacity()
{
if (_size >= _capicity)
{
_capicity = 2 * _capicity + 5;
_array = (DataType *)realloc(_array, _capicity*sizeof (DataType ));
}
}
打印順序表
void SeqList::Print()
{
for (int i = 0; i < _size; ++i)
{
cout << _array[i] << " " ;
}
cout << endl;
}
在尾部添加數據
void SeqList::PushBack(const DataType & x)
{
CheckCapacity(); //添加數據前要進行測容
_array[_size++] = x ; //這裡注意：添加完數據意思要給size加1
}
尾刪
void SeqList::PopBack()
{<br> //要進行邊界條件檢查
if (_size == 0)
{
cout << "This SeqList is Empty !" << endl;
return;
}
else
{
_array[--_size]=NULL ;
}
}
頭插
void SeqList::PushFront(const DataType & x) //頭插
{
if (_size == 0)
{
PushBack(x );
return;
}
else
{
CheckCapacity();
int key = _size;
while (key)
{
_array[key--] = _array[key - 1];
}
_array[0] = x;
_size++;
}
}
頭刪
void SeqList::PopFront() //頭刪
{
if (_size == 0||_size==1)
{
PopBack();
}
else
{
for (int i = 0; i < _size-1;i++)
{
_array[i] = _array[i + 1];
}
--_size;
}
}
固定位置插入數據
void SeqList::Insert(size_t pos , const DataType& x)
{
assert( pos<_size); //需檢驗pos的合法性
CheckCapacity();
if (pos == _size - 1) //在最後一個位置插入數據等於尾插
{
PushBack(x );
return;
}
else
{
for (int i = _size; i > pos; --i)
{
_array[i] = _array[i - 1];
}
_array[pos ] = x ;
_size++;
}
}
查找數據
int SeqList::Find(const DataType & x)
{
assert(_array != NULL);
for (int i = 0; i < _size; i++)
{
if (_array[i] == x )
return i;
}
return -1;
}
固定位置刪除數據
void SeqList::Erase(size_t pos )
{
assert(_array!= NULL);
assert( pos < _size);
if (pos == _size - 1)
{
PopBack();
return;
}
if (pos == 0)
{
PopFront();
return;
}
for (int i = pos; i < _size-1; i++)
{
_array[i] = _array[i + 1];
}
--_size;
}
刪除x
int SeqList::Remove(const DataType & x) //刪除x
{
assert(_array);
int pos=Find(x );
if (pos != -1)
{
Erase(pos);
return 1;
}
else
{
return -1;
}
}
測試用例
//void Test1()
//{
// SeqList list1;
// list1.PushBack(1);
// list1.PushBack(2);
// list1.PushBack(3);
// list1.PushBack(4);
// list1.PushBack(5);
//
// list1.Print();
//
// SeqList list2;
// list2.PushBack(0);
// list2.PushBack(9);
// list2.PushBack(8);
// list2.PushBack(7);
// list2.PushBack(6);
// list2.Print();
//
// list1 = list2;
// list1.Print();
//
// SeqList list3(list1);
// list3.Print();
//}
void Test2()
{
SeqList list1;
//list1.PushFront(0);
//list1.Print();
list1.PushBack(1);
list1.PushBack(2);
list1.PushBack(3);
list1.PushBack(4);
list1.PushBack(5);
list1.Print();
//list1.PopFront();
//list1.Print();
/*list1.Insert(2, 0);
list1.Print();*/
//cout <<"該數字出現在：_array["<< list1.Find(5) <<"]"<< endl;
//list1.Erase(2);
int ret=list1.Remove(7);
if (ret == -1)
{
cout << "not exit !" << endl;
}
else
{
list1.Print();
}
}
int main()
{
//Test1();
Test2();
system("pause" );
return 0;
}
