線性表的順序表示是用一組地址連續的存儲單元依次存儲線性表中的元素。邏輯上相鄰的元素在存儲空間內頁相鄰。若已知順序表中每個元素占k個存 儲單元第一個元素a[0]在計算機內存中的首地址是loc(a[0])，則表中一個元素a[i]在內存中的存儲地址為loc(a[i]) = loc(a[0]) + i * k； 包含的函數：IsEmpty(), Length(), Find(), Search(), Insert(), Delete(), Update(), Output()。 此代碼用于復習c++類，繼承，模板類實現，函數作用已經在注釋中。 優點：存儲空間利用率高，可以隨機存取元素。 缺點：遇到插入和刪除操作頻繁的應用時效率大大降低，分配空間時分配多了浪費，分配少了又要溢出。 實現代碼： ~~~ #include "iostream" #include "cstdio" #include "cstring" #include "algorithm" using namespace std; template <class T> class LinearList { public: virtual bool IsEmpty() const = 0; // 為空則返回true virtual int Length() const = 0; // 返回長度 virtual bool Find(int i, T &x) const = 0; // 若a[i]存在則x = a[i]，返回true，不存在返回flase virtual int Search(T x) const = 0; // 若存在等于x的元素則返回下標，否則返回-1 virtual bool Insert(int i, T x) = 0; // i == -1則x插在第一個元素之前， 否則x插在a[i]后，插入成功返回true virtual bool Delete(int i) = 0; // 刪除元素a[i]，刪除成功返回true virtual bool Update(int i, T x) = 0; // 修改元素a[i]為x，若修改成功則返回true virtual void Output(ostream &out) const = 0; /* data */ protected: int n; }; template <class T> class SeqList:public LinearList<T> { public: SeqList(int mSize); ~SeqList() {delete []elements;} bool IsEmpty() const; int Length() const; bool Find(int i, T &x) const; int Search(T x) const; bool Insert(int i, T x); bool Delete(int i); bool Update(int i, T x); void Output(ostream &out) const; /* data */ private: int maxLength, n; T *elements; }; template <class T> SeqList<T>::SeqList(int mSize) { maxLength = mSize; elements = new T[maxLength]; n = 0; } template <class T> bool SeqList<T>::IsEmpty() const { return n == 0; } template <class T> int SeqList<T>::Length() const { return n; } template <class T> bool SeqList<T>::Find(int i, T &x) const { if(i < 0 || i > n - 1) { // i不合法 cout << "Out of Bounds" << endl; return false; } x = elements[i]; return true; } template <class T> int SeqList<T>::Search(T x) const { for(int i = 0; i < n; ++i) if(elements[i] == x) return i; return -1; } template <class T> bool SeqList<T>::Insert(int i, T x) { if(i < -1 || i > n - 1) { // i不合法 cout << "Out of Bounds" << endl; return false; } if(n == maxLength) { // 數組滿了 cout << "OverFlow" << endl; return false; } for(int j = n - 1; j > i; --j) elements[j + 1] = elements[j]; elements[i + 1] = x; n++; return true; } template <class T> bool SeqList<T>::Delete(int i) { if(!n) { // 數組已經為空 cout << "UnderFlow" << endl; return false; } if(i < 0 || i > n - 1) { // i不合法 cout << "Out of Bounds" << endl; return false; } for(int j = i + 1; j < n; ++j) elements[j - 1] = elements[j]; n--; return true; } template <class T> bool SeqList<T>::Update(int i, T x) { if(i < 0 || i > n - 1) { // i不合法 cout << "Out of Bounds" << endl; return false; } elements[i] = x; return true; } template <class T> void SeqList<T>::Output(ostream &out) const { for(int i = 0; i < n; ++i) out << elements[i] << " "; out << endl; } template <class T> void Union(SeqList<T> &A, SeqList<T> &B) { T x; for(int i = 0; i < B.Length(); ++i) { B.Find(i, x); if(A.Search(x) == -1) A.Insert(A.Length() - 1, x); } } int main(int argc, char const *argv[]) { SeqList<int> A(20), B(20); for(int i = 0; i < 5; ++i) A.Insert(i - 1, i); // A = {0, 1, 2, 3, 4} cout << "順序表A為：" << endl; A.Output(cout); for(int i = 5; i < 10; ++i) B.Insert(i - 6, i); // B = {5, 6, 7, 8, 9} cout << "順序表B為：" << endl; B.Output(cout); A.Update(1, 5); // A = {0, 5, 2, 3, 4} cout << "順序表A為：" << endl; A.Output(cout); int flag = A.Search(2); // 元素中是否有2 if(flag != -1) cout << "有等于2的元素" << endl; else cout << "無等于2的元素" << endl; int x; A.Find(2, x); // x = a[2]; cout << "a[2] == " << x << endl; B.Insert(-1, 0); // B = {0, 5, 6, 7, 8, 9} cout << "順序表B為：" << endl; B.Output(cout); B.Insert(3, 2); // B = {0, 5, 6, 7, 2, 8, 9} cout << "順序表B為：" << endl; B.Output(cout); B.Delete(4); // B = {0, 5, 6, 7, 8, 9} cout << "順序表B為：" << endl; B.Output(cout); Union(A, B); // 合并A, B到A A = {0, 2, 3, 4, 5, 6, 7, 8, 9} cout << "順序表A為：" << endl; A.Output(cout); return 0; } ~~~