Shoujun Diao
Writing
•
7 min read

单链表

Archive · written in 2008
C++ 数据结构
Table of Contents

顺序表无需为表示节点间的逻辑关系而增加额外的存储空间，存储利用率高；可以方便地随机存取表中的任一节点，存取速度快。这是顺序表的优点。但顺序表的缺点也很明显，一是插入或删除时，为了保持其它元素的相对次序不变，平均要移动一半元素，运行效率低；二是顺序表要求占用连续空间，如果静态分配，则难以确定合适的存储空间，如果动态分配，动态扩充数组空间时时间开销也比较大。

所以当插入或删除频繁，存储空间需求不定时，我们可以考虑单链表。

类定义

通常使用两个类，链表的节点（LinkNode）类和链表（List）类，协同表示单链表。有4种方法描述它们之间的关系。

复合类

在LinkNode类中声明友元，让LinkNode与List都能访问LinkNode类的私有数据成员。

class List;

class LinkNode {
	friend class List;
	private:
		int dada;
		LinkNode *link;
};

class List {
	public:
		//...
	private:
		LinkNode *first;
};

注意，友元关系不具备对称性。在LinkNode中声明List是它的友元，则List类的所有成员都可以直接使用LinkNode的私有成员。反之则不成立。

嵌套类

class List {
	public:
		//...
	private:
		class LinkNode {
			public:
				int data;
				LinkNode *link;
		};
		LinkNode *first;
};

基类和派生类

class LinkNode {
	protected:
		int data;
		LinkNode *link;
};

class List: public class LinkNode {
	private:
		LinkNode *first;
	public:
		//...
};

使用struct

struct LinkNode {
	int data;
	LinkNode* link;
}

class List {
	private:
		LinkNode *first;
	public:
		//...
};

插入与删除

插入

bool List::Insert(int i, int& x) {
	if (first == NULL || i == 0) {
		LinkNode *newNode = new LinkNode(x);
		if (newNode == NULL) {
			cerr << "存储分配错误！" << endl;
			exit(1);
		}
		newNode->link = first;
		first = newNode;
	} else {
		LinkNode *current = first;
		for (int k = 1; k < i; k++) {
			if (current == NULL) {
				break;
			} else {
				current = current->link;
			}
		}
		if (current == NULL && first != NULL) {
			cerr << "无效的插入位置！" << endl;
			return false;
		} else {
			LinkNode *newNode = new LinkNode(x);
			if (newNode == NULL) {
				cerr << "存储分配错误！" << endl;
				exit(1);
			}
			newNode->link = current->link;
			current->link = newNode;
		}
	}
	return true;
}

删除

bool List::Remove(int i, int& x) {
	LinkNode *del, *current;
	if (i <= 1) {
		del = first;
		first = first->link;
	} else {
		current = first;
		for (int k = 0; k < i - 1; k++) {
			if (current == NULL) {
				break;
			} else {
				current = current->link;
			}
		}
		if (current == NULL || current->link == NULL) {
			cerr << "无效的删除位置！" << endl;
			return false;
		}
		del = current->link;
		current->link = del->link;
	}
	x = del->data;
	delete del;
	return true;
}

带附加头节点

插入可以统一为下面的语句：

newNode->link = current->link;
current->link = newNode;

类似的，删除可以统一为：

del = current->link;
current->link = del->link;
delete del;

模板类

类定义

template <class T>
struct LinkNode {
	T data;
	LinkNode<T> *link;
	//仅初始化指针成员的构造函数
	LinkNode(LinkNode<T> *ptr = NULL) {
		link = ptr;
	}
	//初始化数据与指针成员的构造函数
	LinkNode(const T& item, LinkNode<T> *ptr = NULL) {
		data = item;
		link = ptr;
	}
};

template <class T>
//不用继承也可以实现
class List: public LinearList<T> {
	public:
		List() {
			first = new LinkNode<T>;
		}
		List(const T& x) {
			first = new LinkNode<T>(x);
		}
		Lsit(List<T>& L);
		~List() {
			makeEmpty();
		}
		void makeEmpty();
		int Length() const;
		LinkNode<T> *getHead() const {
			return first;
		}
		void setHead(LinkNode<T> *p) {
			first = p;
		}
		LinkNode<T> *Search(T x);
		LinkNode<T> *Locate(int i);
		T *getData(int i);
		void setData(int i, T& x);
		bool Insert(int i, T& x);
		bool Remove(int i, T& x);
		bool IsEmpty() const {
			return first->link == NULL ? true : false;
		}
		bool IsFull() const {
			return false;
		}
		void Sort();
		void input();
		void output();
		List<T>& operator=(List<T>& L);
	protected:
		LinkNode<T> *first;
};

成员函数

template <class T>
List<T>::List(List<T>& L) {
	T value;
	LinkNode<T> *srcptr = L.getHead();
	LinkNode<T> *destptr = first = newLinkNode<T>;
	while (srcptr->link != NULL) {
		value = srcptr->link->data;
		destptr->link = new LinkNode<T>(value);
		destptr = destptr->link;
		srcptr = srcptr->link;
	}
	destptr->link = NULL;
};

template <class T>
void List<T>::makeEmpty() {
	LinkNode<T> *q;
	while (first->link != NULL) {
		q = first->link;
		first->link = q->link;
		delete q;
	}
};

template <class T>
int List<T>::Length() const {
	LinkNode<T> *p = first->link;
	int count = 0;
	while (p != NULL) {
		p = p->link;
		count ++;
	}
	return count;
};

template <class T>
LinkNode<T> *List<T>::Search(T x) {
	LinkNode<T> *current = first->link;
	while (current != NULL) {
		if (current->data == x) {
			break;
		} else {
			current = current->link;
		}
	return current;
};

template <class T>
LinkNode<T> *List<T>::Locate(int i) {
	if (i < 0) {
		return NULL;
	}
	LinkNode<T> *current = first;
	int k = 0;
	while (current != NULL && k < i) {
		current = current->link;
		k++;
	}
	return current;
};

template <class T>
T *List<T>::getData(int i) {
	if (i <= 0) {
		return NULL;
	}
	LinkNode<T> *current = Locate(i);
	if (current == NULL) {
		return NULL;
	} else {
		return &current->data;
	}
};

template <class T>
void List<T>::setData(int i, T& x) {
	if (i <= 0) {
		return;
	}
	LinkNode<T> *current = Locate(i);
	if (current == NULL) {
		return;
	} else {
		current->data = x;
	}
};

template <class T>
bool List<T>::Insert(int i, T& x) {
	LinkNode<T> *current = Locate(i);
	if (current == NULL) {
		return false;
	}
	LinkNode<T> *newNode = new LinkNode<T>(x);
	if (newNode == NULL) {
		cerr << "存储分配错误！" << endl;
		exit(1);
	}
	newNode->link = current->link;
	current->link = newNode;
	return true;
}

template <class T>
bool List<T>::Remove(int i, T& x) {
	LinkNode<T> *current = Locate(i - 1);
	if (current == NULL || current->link == NULL) {
		return false;
	}
	LinkNode<T> *del = current->link;
	current->link = del->link;
	x = del->data;
	delete del;
	return true;
};

template <class T>
void List<T>::output() {
	LinkNode<T> *current = first->link;
	while (current != NULL) {
		cout << current->data <<endl;
		current = current->link;
	}
};

template <class T>
List<T>& List<T>::operator=(List<T>& L) {
	T value;
	LinkNode<T> *srcptr = L.getHead();
	LinkNode<T> *destptr = first = new LinkNode<T>;
	while (srcptr->link != NULL) {
		value = srcptr->link->data;
		destptr->link = new LinkNode<T>(value);
		destptr = destptr->link;
		srcptr = srcptr->link;
	}
	destptr->link = NULL;
	return *this;
}

最后重载函数的例子用到了this指针，注意，友元函数不是类的成员，不会给它传this指针，静态成员函数也不能得到this指针。

前插与后插

前插法得到的链表中各节点中数据的逻辑顺序与输入数据的顺序正好相反，而后插法得到的则完全一致。

//前插
template <class T>
void List<T>::inputFront(T endTag) {
	LinkNode<T> *newNode;
	T val;
	first = new LinkNode<T>;
	if (first == NULL) {
		cerr << "存储分配错误！" << endl;
		exit(1);
	}
	cin >> val;
	while (val != endTag) {
		newNode = new LinkNode<T>(val);
		if (newNode == NULL) {
			cerr << "存储分配错误！" << endl;
			exit(1);
		}
		newNode->link = first->link;
		first->link = newNode;
		cin >> val;
	}
};

//后插
template <class T>
void List<T>::inputRear(T endTag) {
	LinkNode<T> *newNode, *last;
	T val;
	first = new LinkNode<T>;
	if (first == NULL) {
		cerr << "存储分配错误！" << endl;
		exit(1);
	}
	cin >> val;
	last = first;
	while (val != endTag) {
		newNode = new LinkNode<T>(val);
		if (newNode == NULL) {
			cerr << "存储分配错误！" << endl;
			exit(1);
		}
		last->link = newNode;
		last = newNode;
		cin >> val;
	}
	last->link = NULL;
};

典型应用：多项式运算

利用链表来表示多项式，不存在存储溢出的问题，可应对项数在计算过程中动态增长的情况，而且插入和删除某项只需要修改节点的指针即可，不像在顺序方式中，可能移动大量数据项。

类定义

#ifndef POLYNOMAL_H
#define POLYNOMAL_H
#include<iostream.h>
struct Term {
	float coef;
	int exp;
	Term *link;
	Term (float c, int e, Term *next = NULL) {
		coef = c;
		exp = e;
		link = next;
	}
	Term *InsertAfter(float c, int e);
	friend ostream& operator << (ostream&, const Term&);
};

class Polynomal {
	public:
		Polynomal() {
			first = new Term(0, -1);
		}
		Polynomal(Polynomal& R);
		int maxOrder();
		Term *getHead() const {
			return first;
		}
	private:
		Term *first;
		friend ostream& operator<<(ostream&, const Polynomal&);
		friend istream& operator>>(istream&, Polynomal&);
		friend Polynomal operator+(Polynomal&, Polynomal&);
		friend Polynomal operator*(Polynomal&, Polynomal&);
};

Term *Term::InsertAfter(float c, int e) {
	link = new Term(c, e, link);
	return link;
};

ostream& operator<<(ostream& out, const Term& x) {
	if (x.coef == 0.0) {
		return out;
	}
	out << x.coef;
	switch (x.exp) {
		case 0: 
			break;
		case 1: 
			out << "X";
			break;
		default:
			out << "X^" << x.exp;
			break;
	}
	return out;
};

Polynomal::Polynomal(Polynomal& R) {
	first = new Term(0, -1);
	Term *destptr = first, *srcptr = R.getHead()->link;
	while (srcptr != NULL) {
		destptr->link = InsertAfter(srcptr->coef, srcptr->exp);
		srcptr = src->link;
		destptr = destptr->link;
	}
};

int Polynomal::maxOrder() {
	Term *current = first;
	while (current->link != NULL) {
		current = current->link;
	}
	return current->exp;
};

istream& operator >> (istream& in, Polynomal& x) {
	Term *rear = x.getHead();
	int c, e;
	while (1) {
		cout << "Input a term(coef, exp):" << endl;
		in >> c >> e;
		if (e < 0) {
			break;
		}
		rear = rear->InsertAfter(c, e);
	}
	return in;
};

ostream& operator << (ostream& out, Polynomal& x) {
	Term *current = x.getHead()->link;
	cout << "The polynomal is:" << endl;
	bool h = true;
	while (current != NULL) {
		if (h = false && current->coef > 0.0) {
			out << "+";
		}
		h = false;
		out << *current;
		current = current->link;
	}
	out << endl;
	return out;
};
#endif

加法

Polynomal operator + (Polynomal& A, Polynomal& B) {
	Term *pa, *pb, *pc, *p;
	float temp;
	Polynomal C;
	pc = C.first;
	pa = A.getHead()->link;
	pb = B.getHead()->link;
	while (pa != NULL && pb != NULL) {
		if (pa->exp == pb->exp) {
			temp = pa->coef + pb->coef;
			if (fabs(temp) > 0.001) {
				pc = pc->InsertAfter(temp, pa->exp);
			}
			pa = pa->link;
			pb = pb->link;
		} else if (pa->exp < pb->exp) {
			pc = pc->InsertAfter(pa->coef, pa->exp);
			pa = pa->link;
		} else {
			pc = pc->InsertAfter(pb->coef, pb->exp);
			pb = pb->link;
		}
	}
	if (pa != NULL) {
		p = pa;
	} else {
		p = pb;
	}
	while (p != NULL) {
		pc = pc->InsertAfter(p->coef, p->exp);
		p = p->link;
	}
	return C;
};

Polynomal operator * (Polynomal& A, Polynomal& B) {
	Term *pa, *pb, *pc;
	int AL, BL, i, k, maxExp;
	Polynomal C;
	pc = C.getHead();
	AL = A.maxOrder();
	BL = B.maxOrder();
	if (AL != -1 || BL != -1) {
		maxExp = AL + BL;
		float *result = new float[maxExp + 1];
		for (i = 0; i < maxExp; i ++) {
			result[i] = 0.0;
		}
		pa = A.getHead()->link;
		while (pa != NULL) {
			pb = B.getHead()->link;
			while (pb != NULL) {
				k = pa->exp + pb->exp;
				result[k] = result[k] + pa->coef * pb->coef;
				pb = pb->link;
			}
			pa = pa->link;
		}
		for (i = 0; i <= maxExp; i ++) {
			if (fabs(result[i]) > 0.001) {
				pc = pc->InsertAfter(result[i], i);
			}
		}
		delete[] result;
	}
	pc->link = NULL;
	return C;
}
循环列表
顺序表