单链表中，每个元素占用一个结点，每个结点由两个域组成，分别是存放元素的数据域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; } ~~~