單鏈表中，每個元素占用一個結點，每個結點由兩個域組成，分別是存放元素的數據域element以及存放指向表中后繼結點地址的指針域Link。邏輯上相鄰的元素在物理上不一定相鄰，結點與節點不要求被存放在相鄰的存儲空間，結點間的相鄰關系通過指針來實現。 包含的函數：IsEmpty(), Length(), Find(), Search(), Insert(), Delete(), Update(), Clear()，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 SingleList; // 超前聲明SingleList template <class T> class Node { private: T element; // 數據域 Node<T> *Link; // 指針域 friend class SingleList<T>; // 結點類的友元，可訪問Node類中私有成員 /* data */ }; template <class T> class SingleList:public LinearList<T> { public: SingleList() { first = NULL; n = 0; } ~SingleList(); 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 clear(); void Output(ostream &out) const; /* data */ private: Node<T> *first; int n; }; template <class T> SingleList<T>:: ~SingleList() { Node<T> *p; while(first) { p = first -> Link; delete first; first = p; } } template <class T> int SingleList<T>::Length() const { return n; } template <class T> bool SingleList<T>::IsEmpty() const { return n == 0; } template <class T> bool SingleList<T>::Find(int i, T &x) const { if(i < 0 || i > n - 1) { // i不合法 cout << "Out of Bounds" << endl; return false; } Node<T> *p = first; for(int j = 0; j < i; ++j) p = p -> Link; // p最終為i的指針域 x = p -> element; return true; } template <class T> int SingleList<T>::Search(T x) const { int j; Node<T> *p = first; for(j = 0; p && p -> element != x; ++j) // p為空或p的數據域為x則提前停止循環 p = p -> Link; if(p) return j; // p不為NULL說明存在等于x的數據域 return -1; } template <class T> bool SingleList<T>::Insert(int i, T x) { if(i < -1 || i > n - 1) { // i不合法 cout << "Out of Bounds" << endl; return false; } Node<T> *q = new Node<T>; q -> element = x; Node<T> *p = first; for(int j = 0; j < i; ++j) p = p -> Link; // p最終為i的指針域 if(i > -1) { // 在a[i]后插入x，相當于a[i]和a[i + 1]之間多了一個q q -> Link = p -> Link; // q指向a[i]后的元素 p -> Link = q; // p指向q } else { // 在第一個元素前插入x，相當于在首個元素之前多了一個q q -> Link = first; // q指向首個元素 first = q; // 將q作為首個元素的指針域 } n++; return true; } template <class T> bool SingleList<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; } Node<T> *p = first, *q = first; for(int j = 0; j < i - 1; ++j) q = q -> Link; // q最終為i - 1的指針域 if(i == 0) first = first -> Link; // 刪除首個元素 else { p = q -> Link; // p指向a[i] q -> Link = p -> Link; // p -> Link為a[i + 1]，賦值完成后a[i - 1]直接指向a[i + 1] } delete p; n--; return true; } template <class T> bool SingleList<T>::Update(int i, T x) { if(i < 0 || i > n - 1) { // i不合法 cout << "Out of Bounds" << endl; return false; } Node<T> *p = first; for(int j = 0; j < i; ++j) p = p -> Link; // p最終指向a[i] p -> element = x; // 將x賦值給a[i] return true; } template <class T> void SingleList<T>::Output(ostream &out) const { Node<T> *p = first; while(p) { out << p -> element << " "; p = p -> Link; } out << endl; } int main(int argc, char const *argv[]) { SingleList<int> A; A.Insert(-1, 0); A.Insert(0, 1); A.Insert(1, 2); A.Insert(2, 3); A.Insert(3, 4); // A = {0, 1, 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(1, x); // x = a[1] cout << "a[1] == " << x << endl; A.Update(1, 5); // A = {0, 5, 2, 3, 4} A.Output(cout); A.Delete(1); // A = {0, 2, 3, 4} A.Output(cout); return 0; } ~~~