順序表是在電腦記憶體中以數組的形式保存的線性表,是指用一組地址連續的存儲單元依次存儲數據元素的線性結構。 這樣的存儲方式使得線性表邏輯上相鄰的元素,其在物理存儲單元中也是相鄰的。只要知道了第一個元素的存儲地址,就可以知道線性表中任何一個元素的存儲地址。因此,線性表中的任何一個元素, 本文利用C++語 ...
順序表是在電腦記憶體中以數組的形式保存的線性表,是指用一組地址連續的存儲單元依次存儲數據元素的線性結構。
這樣的存儲方式使得線性表邏輯上相鄰的元素,其在物理存儲單元中也是相鄰的。只要知道了第一個元素的存儲地址,就可以知道線性表中任何一個元素的存儲地址。因此,線性表中的任何一個元素,
本文利用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() {
//要進行邊界條件檢查 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; }