[数据结构与算法]单链表的实现

对链表的理解：

单链表由头节点，尾节点和中间的多个节点组成，每个节点由两中数据组成，一个为数据区域另一个为指针区域，数据区域用来保存存入的数据，指针区域用来保存下一个节点的地址，从而将多个节点连接成完整的链条（一环扣一环），头节点的数据区域不用存入数据，将最后一个节点的指针区域定义为空（NULL），以此作为最后一个节点。

1 图示为:

2 链表的初始化

在实现将元素插入链表的前提下先将链表初始化才能实现链表元素的插入

//初始化链表
bool initLinkList(linkList*& list) {
	list = new linkNode;	//生成头节点
	if (!list) return false; //节点生成失败返回false
	list->next = NULL;
	return true;
}

?3?跟据以上情况分析可以定义一个结构体来表示链表：

//linkList表示为链表表头，linkNode表示为链表节点
typedef struct linkNode {
	int date;
	struct linkNode* next; 
}linkList,linkNode;

对于上面结构体的定义里面指针域的名称为什么和定义的结构体的别名（linkNode）相同，个人的理解是因为:? 指针域保存的是下一个节点的地址而下一个节点的名称是（linkNode）只有结构体名称和指针域名称是同一个结构体的别名才能进行保存。（如果有什么理解错误请批评指正）。

4 前插法实现链表元素的插入

算法实现思路：

在头节点后面插入（先让头节点和第一个节点断开，后将插入的节点的指针域保存第一个节点的地址，头节点的指针域保存插入节点的地址）就可以实现元素的前端插入。

代码实现：

//在头部插入元素
bool linkListInsertFront(linkList*& list, linkNode* l) {
	if (!list || !l)return false; //如果链表或节点为空则返回false

	l->next = list->next;
	list->next = l;
	return true;
}

//测试前插法的代码段
	struct linkNode *w;

	cout << "前插法向链表中插入元素" << endl;
	for (int i = 0;i < 4;i++) {
		w = new linkNode;
		w->date = i;
		linkListInsertFront(list, w);
	}
	printLinkList(list);
	cout << endl;

?代码运行效果：

向链表中插入的元素是0，1，2，3，输出的时候是反向输出说明代码运行结果是对的因为（例如：插入 1 以后?在插入 2 ，1 就必须往后面移动）所以输出的时候是 3，2，1，0。

5 尾插法实现链表元素的插入

尾插法和前插法的插入形式有所不同（尾插法是先找到链表的最后一个节点，找到最后一个节点后将要插入的节点的指针域定义为空（NULL），将找到的最后一个节点的指针域保存要插入节点的地址）就可以实现尾部插入。

代码实现：

//尾插入元素
bool linkListInsertBack(linkList*& list, linkNode* l) {
	linkNode* s;
	s = list;
	if (!list || !l)return false; //如果链表或节点为空则返回false
	while (s->next)s = s->next;

	l->next = NULL;
	s->next=l;
	return true;
}


//测试尾插法的代码
	cout << "尾插法向链表尾部插入元素" << endl;
	for (int i = 0;i < 2;i++) {
		w = new linkNode;
		w->date = i;
		linkListInsertBack(list, w);
	}
	printLinkList(list);
	cout << endl<<endl;

代码的运行效果：

运行效果和前插法的运行效果相反（就不再展示运行效果图）

6 任意位置插入实现链表元素的插入

任意位置插入是以上两种插入的综合，先输入要插入的位置，后遍历链表找到相应的位置后，将节点插入到相应的位置即可，插入的方法也是先将链表断裂，将插入位置的前一个节点的指针域保存要插入节点的地址，要插入节点的指针域保存下一个节点的地址即可，就可以实现完整的链表。

代码实现：

//在链表的任意位置插入元素
bool linkListInsertEverwhere(linkList*& list, linkNode* l,int e) {
	int index=0;
	if (!list || !l)return false; //如果链表为空或插入的节点为空则返回false
	linkNode* p;  //定义一个临时指针变量
	p = list;  //指向头节点
	while (p && index < e-1) {
		p = p->next;
		index++;
	}
	if (!p || index > e-1) { //如果指针为空或者插入的元素超出了链表的范围
		return false;
	}
	l->next = p->next;
	p->next = l; 
	return true;
}

提醒：以上几种插入方法在遍历链表时都要从头节点开始遍历，因为插入元素时可能插入的是第一个位置所以要存留头节点，要让头节点指针域保存，新节点的地址，新节点的指针域要保存次下一个节点的地址，所以要从头节点开始遍历。

7? 对链表中的元素进行删除

第一种删除方法是跟据链表中元素的位置进行删除

代码实现：

//根据位置删除链表中的元素
bool deleteLinkList(linkList*& list, int e) {
	int index = 0;
	if (!list)return false;
	linkNode* p, * q;
	p = list;
	while (index < e - 1 && p->next) {
		p = p->next;
		index++;
	}
	if (!p->next || index > e - 1 || e < 0) {
		return false;
	}
	q = p->next;
	p->next = q->next;
	delete q;
	return true;
}

第二种方法是跟据元素的值将元素从链表中删除：

//根据元素的值删除链表中的元素
bool deleteLinkListWhere(linkList*& list, int e) {
	if (!list)return false;
	linkNode* p = NULL, * q = NULL;
	p = list;
	while (p->date != e && p->next) {
		q = p;
		p = p->next;
	}
	if (!p || p->date != e)return false;
	q->next = p->next;
	delete p;
	return true;
}

第三中是直接将列表销毁：

//销毁链表法二
bool destoryLinkList1(linkList*& list) {
	int i = 0;
	if (!list)return false;
	linkNode* p, * q;
	p = list;

	while (p) {
		q = p;
		p = p->next;
		delete q;
	}
	return true;
}

8? 对链表中元素进行查询：

第一种是跟据元素的位置查询该位置元素的值：

代码实现：

//根据位置删除链表中的元素
bool deleteLinkList(linkList*& list, int e) {
	int index = 0;
	if (!list)return false;
	linkNode* p, * q;
	p = list;
	while (index < e - 1 && p->next) {
		p = p->next;
		index++;
	}
	if (!p->next || index > e - 1 || e < 0) {
		return false;
	}
	q = p->next;
	p->next = q->next;
	delete q;
	return true;
}

第二中是跟据元素的值查询元素在该链表中的位置：

//根据元素的值查找元素的位置
bool sortWhere(linkList*& list, int e,int &q) {
	int i = 0;
	if (!list) return false;
	linkNode* p;
	p = list->next;
	i = 1;
	while (p->date != e && p->next) {
		p = p->next;
		i++;
	}
	if (!p->next || p->date != e)return false;
	q = i;
	return true;
}

提醒：以上的查询方法遍历链表时从第一个节点开始，应为第一个节点中的数据域中没有保存数据的值，从第一个节点到最后一个节点数据域中都有保存元素的值。

9? 遍历链表将链表中的值打印出来：

//打印链表中的元素
void printLinkList(linkList*& list) {
	linkNode* p;
	p = list->next;
	while(p){
		cout << p->date<<" ";
		p = p->next;
	}
}

10? 据体完整单链表的实现代码：

头文件的编写：

#pragma once
#include<iostream>

using namespace std;

//linkList表示为链表表头，linkNode表示为链表节点
typedef struct linkNode {
	int date;
	struct linkNode* next;
}linkList,linkNode;

//初始化链表
bool initLinkList(linkList*& list) {
	list = new linkNode;	//生成头节点
	if (!list) return false; //节点生成失败返回false
	list->next = NULL;
	return true;
}

//在头部插入元素
bool linkListInsertFront(linkList*& list, linkNode* l) {
	if (!list || !l)return false; //如果链表或节点为空则返回false

	l->next = list->next;
	list->next = l;
	return true;
}

//在尾部插入元素
bool linkListInsertBack(linkList*& list, linkNode* l) {
	linkNode* s;
	s = list;
	if (!list || !l)return false; //如果链表或节点为空则返回false
	while (s->next)s = s->next;

	l->next = NULL;
	s->next=l;
	return true;
}

//在链表的任意位置插入元素
bool linkListInsertEverwhere(linkList*& list, linkNode* l,int e) {
	int index=0;
	if (!list || !l)return false;
	linkNode* p;  //定义一个临时指针变量
	p = list;  //指向头节点
	while (p && index < e-1) {
		p = p->next;
		index++;
	}
	if (!p || index > e-1) { //如果指针为空或者插入的元素超出了链表的范围
		return false;
	}
	l->next = p->next;
	p->next = l; 
	return true;
}

//在链表的任意位置插入元素
bool linkInsert(linkList*& list, int i, int &e) {
	int j;
	linkNode* p, * s;
	p = list;
	j = 0;
	while (p && j < i - 1) {
		p = p->next;
		j++;
	}
	if (!p || j > i - 1) {
		return false;
	}
	s = new linkNode;
	s->date = e;
	s->next = p->next;
	p->next = s;
	return true;
}

//在链表中查找元素
bool sortLinkList(linkList*& list, int i,int &e) {
	int j=0;
	if (!list) return false;
	linkNode* p;
	p = list->next;
	j = 1;
	while (p && j < i) {
		p = p->next;
		j++;
	}
	if (!p || j > i) {
		return false;
	}
	e = p->date;
	return true;
}

//根据元素的值查找元素的位置
bool sortWhere(linkList*& list, int e,int &q) {
	int i = 0;
	if (!list) return false;
	linkNode* p;
	p = list->next;
	i = 1;
	while (p->date != e && p->next) {
		p = p->next;
		i++;
	}
	if (!p->next || p->date != e)return false;
	q = i;
	return true;
}

//根据位置删除链表中的元素
bool deleteLinkList(linkList*& list, int e) {
	int index = 0;
	if (!list)return false;
	linkNode* p, * q;
	p = list;
	while (index < e - 1 && p->next) {
		p = p->next;
		index++;
	}
	if (!p->next || index > e - 1 || e < 0) {
		return false;
	}
	q = p->next;
	p->next = q->next;
	delete q;
	return true;
}

//根据元素的值删除链表中的元素
bool deleteLinkListWhere(linkList*& list, int e) {
	if (!list)return false;
	linkNode* p = NULL, * q = NULL;
	p = list;
	while (p->date != e && p->next) {
		q = p;
		p = p->next;
	}
	if (!p || p->date != e)return false;
	q->next = p->next;
	delete p;
	return true;
}

//链表的销毁
bool destoryLinklist(linkList*& list) {
	if (!list)return false;
	linkNode* p;
	p = list;
	while (p){
		list = list->next;
		delete p;
		p = list;
	}
	return true;
}

//销毁链表法二
bool destoryLinkList1(linkList*& list) {
	int i = 0;
	if (!list)return false;
	linkNode* p, * q;
	p = list;

	while (p) {
		q = p;
		p = p->next;
		delete q;
	}
	return true;
}

//打印链表中的元素
void printLinkList(linkList*& list) {
	linkNode* p;
	p = list->next;
	while(p){
		cout << p->date<<" ";
		p = p->next;
	}
}

main 文件的实现：

#include<iostream>
#include<stdlib.h>
#include"link_list.h"

using namespace std;

int main(void) {
	linkList* list;
	initLinkList(list);

	struct linkNode *w;

	cout << "前插法向链表中插入元素" << endl;
	for (int i = 0;i < 4;i++) {
		w = new linkNode;
		w->date = i;
		linkListInsertFront(list, w);
	}
	printLinkList(list);
	cout << endl;
	

	/*cout << "尾插法向链表尾部插入元素" << endl;
	for (int i = 0;i < 2;i++) {
		w = new linkNode;
		w->date = i;
		linkListInsertBack(list, w);
	}
	printLinkList(list);
	cout << endl<<endl;
	*/

	/*cout << "任意位置插入元素" << endl;
	int i;
	cout << "请输入插入的位置:";
	cin >> i;
	w = new linkNode;
	w->date = i;
	if (linkListInsertEverwhere(list, w, i)) {
		cout << "插入成功" << endl;
	}
	else {
	cout << "插入失败";
}
	cout << endl;
	printLinkList(list);
	cout << endl;
	*/
	
	/*int i, j;
	cout << "请输入插入的位置:";
	cin >> i;
	cout << "输入插入的元素的大小:";
	cin >> j;
	if (linkInsert(list, i, j)) {
		cout << "插入成功" << endl;
	}
	else {
		cout << "插入失败";
	}
	cout << endl;
	printLinkList(list);
	cout << endl << endl;
	*/


   /* //根据位置查找链表中的元素
	cout << "请输入要查找元素的位置:";
	int e,i;
	cin >> i;
	if (sortLinkList(list, i, e)) {
		cout << "查找成功!" << endl;
		cout << e << endl;
	}
	else {
		cout << "查找失败!" << endl;
	}
	*/


	/*//根据元素的值查找元素的位置
	cout << "输入要查找的元素:";
	int i, j;
	cin >> i;
	if (sortWhere(list, i, j)) {
		cout << "查找成功!" << endl;
		cout << "在链表中的位置为: " << j << endl;
	}
	else {
		cout << "查找失败!" << endl;
	}
	*/

	
	/*//根据元素的值查找元素的位置
	cout << "请输入要删除元素的位置:";
	int e;
	cin >> e;
	if (deleteLinkList(list, e)) {
		cout << "删除成功!" << endl;
	}
	else {
		cout << "删除失败!" << endl;
	}
	cout << "剩余元素:";
	printLinkList(list);
	cout << endl << endl;
	*/


	/*//根据元素的值删除链表中的元素
	cout << "请输入要删除的元素:";
	int e;
	cin >> e;
	if (deleteLinkListWhere(list, e)) {
		cout << "删除成功!" << endl;
	}
	else {
		cout << "删除失败!" << endl;
	}
	cout << "剩余元素:";
	printLinkList(list);
	cout << endl << endl;
	*/

	/*//销毁链表
	if (destoryLinklist(list)) {
		cout << "链表销毁成功" << endl;
	}
	else {
		cout << "链表销毁失败" << endl;
	}
	cout << "剩余元素:";
	printLinkList(list);
	*/


	system("pause");
	return 0;
}

还可以添加多种工能（如在指定位置插入元素等）本人不在一一给出。

如果有什么错误请批评指正。