单链表的实现（带头结点与不带头结点）c++语言

本人弱鸡，在学数据结构，学到链表这一章，思索实践搜集资料了好几天才对单链表有了一些理解。现在整理一些代码与感悟，希望看到这篇文章也同样在学链表的童鞋能有所感悟，少走些弯路。

结点类（我比较喜欢用结构体，这样可避免友元的问题，也比较清晰）：

template <class T>
struct chainNode {
	T data;
	chainNode<T> *link;
	chainNode(chainNode <T> *pre = NULL) { link = pre; }
	chainNode(const T& item, chainNode<T> *pre = NULL) {
		data = item;
		link = pre;
	}
};

注意上述结构体中的两个构造函数，first = new chainNode<T>; 调用的便是第一个构造函数，这个first指针指向的便是不带值的头结点（头结点也可以带值，但不算是我们期待的链表中的值）。

first = new chainNode<T>(x),这调用的是第二个构造函数，这时候链表便不带头结点。

List类：

template <class T>
class List {
public:
	List() { first = new chainNode<T>; } //带头结点
	List(const T& x) { first = new chainNode<T>(x); } //这是不带头结点的
	List(List<T> &L); //复制构造函数
	~List() { makeEmpty(); }
	chainNode<T>* locate(int i); //返回链表中第i个元素的地址
	void makeEmpty(); //将链表清空
	bool IsEmpty() const { return first->link == NULL ? true : false; }
	void inputFront(T endTag);
	void inputRear(T endTag);
	int length() const; //计算带有头结点的链表的长度
	int search(T &x); //返回链表第一个x是第几个值
	void find(int k, T& x); //找到链表中第k个元素，并把它的值赋给x
	void output(ostream& out);
	bool remove(int k, T& x);
	bool insert(int k, T& x);
	void reverse();
private:
	chainNode<T> *first; // 链表头指针
};

请看构造方法List(),就如原先说的一样，我建立的便是带头结点的链表。带头结点的目的是为了让链表的一些操作比如插入的形式一致，不必根据插入的不同情况而分情况讨论。

以下是各个方法的具体实现（有关键注释，就不一一赘述了）：

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

	
}

template<class T>
void List<T>::makeEmpty()
{
	chainNode<T> *q;
	while (first->link != NULL) //留了一个first结点
	{
		q = first->link;
		first->link = q->link;
		delete q;
	}
}

template<class T>
void List<T>::inputFront(T endTag)
{
	cout << "前插法生成链表 " << endl;
	chainNode<T> *newNode;
	T val;
	makeEmpty();
	cout << "请输入第一个结点的值：" << endl;
	cin >> val;
	while (val != endTag) {
		newNode = new chainNode<T>(val); //创建新结点
		if (newNode == NULL) { cerr << "存储分配错误！" << endl; exit(1); }
		newNode->link = first->link;
		first->link = newNode;
		cout << "请输入值：";
		cin >> val;
	}
}

template<class T>
void List<T>::inputRear(T endTag)
{
	chainNode<T> *p, *q;
	T val;
	makeEmpty();
	cout << "请输入链表的第一个值" << endl;
	cin >> val;
	q = first;
	while (val != endTag) {
		p = new chainNode<T>(val);
		if (p == NULL) {cerr << "存储分配错误" << endl;exit(1);}
		q->link = p;
		q = p;
		cout << "请输入值: ";
		cin >> val;
	}
	q->link = NULL;

}

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

template<class T>
int List<T>::search(T & x)
{
	chainNode<T> *p = first->link;
	int i = 1;
	while (p -> data != x )
	{
		p = p->link;
		i++;
	}
	return i;
}

template<class T>
void List<T>::find(int k, T & x)
{
	if (k < 0) { cout << "k不合法，无法find第k个元素"; return; }
	chainNode<T> *p = first->link;
	for (int i = 1; i < k; i++) {
		p = p->link;
	}
	x = p->data;
}

template<class T>
void List<T>::output( ostream& out) 
{
	chainNode <T>* current = first->link ;
	//for (current = first->link; current !=NULL; current = current->link) {
		//out << current->data << " ";
	//}
	while (current !=NULL) {
		cout << current->data << " ";
		current = current->link;
	}
}
template<class T>
bool List<T>::remove(int k, T & x)
{ //将链表中的第i个元素删去，通过引用型x返回该元素的值
	chainNode<T> * current = locate(k - 1);
	if (current == NULL || current->link == NULL) return false;
	chainNode<T>* del = current->link; //这是那个被删除的结点
	current->link = del->link;
	x = del->data;
	delete del;
	return true;
}
template<class T>
bool List<T>::insert(int k, T & x)
{//将新元素x插入在链表中第k个结点之后
	chainNode<T>* current = locate(k);
	if (current == NULL) return false;
	chainNode<T> * newNode = new chainNode<T>(x); //生成新结点
	if (newNode == NULL) { cerr << "存储分配错误！" << endl; exit(1); }
	newNode->link = current->link;
	current->link = newNode;
	return true;
	
}
template<class T>
void List<T>::reverse()  //带有头节点的链表反序
{
	chainNode<T> *p, *q, *t;
	p = first->link;
	q = first->link->link;
	t = NULL;
	while (q != NULL) {
		t = q->link;
		q->link = p;
		p = q;
		q = t;
	}
	first->link->link= NULL; //设置末结点
	first->link = p; //改变first结点
}
//重载<<
template <class T>
ostream& operator<< (ostream& out,  List<T>& x) {
	x.output(out);
	return out;
}

注意以上的所有代码，我都是以头文件的形式存在的。

看看测试类：

#include "stdafx.h"
#include "chain.h"
using namespace std;


int main()
{
	List<int> l;
	cout <<"链表是否为空    "<< l.IsEmpty() << endl;
	l.inputFront(5);
	//cout << l.IsEmpty() << endl;
	//cout << l << endl;
	//l.makeEmpty();
	//cout << l << "makeEmpty()" << endl;
	//nt i = 8;
	//int j;
	/*l.insert(0, i);
	cout << l << endl;
	l.remove(1, j);
	cout << l << endl;
	cout << j << endl;
	cout << l.locate(1) << endl;
	cout << l.locate(2) << endl;
	cout << l.locate(3) << endl;
	cout << l.locate(4) << endl;
	*/
	cout << l << endl;
	l.inputRear(5);
	cout << "后插法生成的链表为：" << endl;
	cout << l << endl;
	cout << "链表的长度为： " << l.length() << endl;
	int j = 2;
	int i = l.search(j);
	cout << "j = " << j << "是链表中第" << i << "个元素" << endl;
	l.find(j, i);
	cout << "链表中第" << j << "个值为 " <<i << endl;
	l.reverse();
	cout << l << endl;
	cout << "反序完成" << endl;
    return 0;
}

看看运行结果（这是我人生中的第一个完整的链表，说实话我好激动......）：

注意两个生成链表的方法是输入关键值的时候停止。

好了，终于写完了。只要肯花时间，只要问题不太难，我相信我们都能解决！

原文链接：https://blog.csdn.net/weixin_41423387/article/details/82955061