链表简介

百度百科定义：
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
*定义：
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。

单向链表

单向链表简介

百度百科定义：
单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点；

C++教材(C++语言程序设计–刘瑞芳)单向链表源代码

#include <iostream>
using namespace std;
struct student {
	long num;
	char name[20];
	float score;
	//student* before;
	student* next;
};
int main() {
	student* head = NULL, *temp = NULL;
	head = new student;
	temp = head;
	int i = 1;
	while (temp->next) {
		temp->num = i;
		cout << "Please input name and score for No." << i << endl;
		cin >> temp->name >> temp->score;
		temp->next = NULL;
		i++;
		if (i != 5)//主要对temp->next进行赋值 及下一个结构体声明 这里是4个链表
		{
			temp->next = new student;
			temp = temp->next;
		}
	}
	temp = head;
	while (temp)
	{
		cout << temp->num << "  " 
			<< temp->name << "  " 
			<< temp->score << endl;
		temp = temp->next;
	}

	system("pause");
	return 0;
}

双向链表

双向链表简介

百度百科定义：
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

由教材中单向链表推导双向链表

观察上面单向链表源码发现:

1：单向主要产生于结构体构造及第一个while循环上
2：观察if语句发现，ta的主要作用是控制链表数目、对temp->next进行赋值 及下一个结构体声明
3：

first trying 失败

#include <iostream>
using namespace std;
struct student {
	long num;
	char name[20];
	float score;
	student* previous;
	student* next;
};
int main() {
	student *head = NULL,*end = NULL, *temp = NULL, *temp2 = NULL;
	head = new student;
	temp = head;
	int i = 1;
	while (temp->next) {
		
		temp2 = temp;

		temp->num = i;
		cout << "Please input name and score for No." << i << endl;
		cin >> temp->name >> temp->score;
		temp->previous = NULL;
		temp->next = NULL;

		i++;

		if (i != 2)
			temp->previous = temp2;

		if (i == 5) {
			end = temp;
		}
		else{
			temp->previous = temp2;
			temp->next = new student;
			temp = temp->next;
		}
	}

	temp = head;
	while (temp)
	{
		cout << temp->num << "  " 
			<< temp->name << "  " 
			<< temp->score << endl;
		temp = temp->next;
	}

	temp = end;
	while (temp)
	{
		cout << temp->num << "  "
			<< temp->name << "  "
			<< temp->score << endl;
		temp = temp->previous;
	}

	system("pause");
	return 0;
}

测试结果
死循环(为了减少敲键盘输入的时间，将所有输入存到txt中，复制粘贴即可)


调试过程
死循环原因初步估计为temp->previous赋值未出错，而单单是输出时导致死循环
验证：赋值与输出时均输出cout << temp->previous << endl;的值
结果

这个乱七八糟看不出来，索性直接visual studio调试，在局部变量窗口查看值的变化，发现赋值是成功的，但输出就是有问题。。。。
呃~上个厕所回来瞬间明白，错误原因应该是：每个链表的previous属性都存的自己这张链表的地址，导致赋值确实都成功但输出永远死循环。
second trying succeed

#include <iostream>
using namespace std;
struct student {
	long num;
	char name[20];
	float score;
	student* previous;
	student* next;
};
int main() {
	student *head = NULL, *end = NULL, *temp = NULL, *temp2 = NULL;
	head = new student;
	temp = head;
	int i = 1;
	while (temp->next) {

		temp->num = i;
		cout << "Please input name and score for No." << i << endl;
		cin >> temp->name >> temp->score;
		temp->previous = NULL;
		temp->next = NULL;

		i++;

		if (i != 2)//操作temp->previous
			temp->previous = temp2;

		if (i == 5) {//操作temp->next
			end = temp;
		}
		else{
			temp2=temp;
			temp->next = new student;
			temp = temp->next;
			temp->previous = temp2;
		}
	}

	temp = head;
	while (temp)
	{
		cout << temp->num << "  " 
			<< temp->name << "  " 
			<< temp->score << endl;
		temp = temp->next;
	}

	temp = end;
	while (temp)
	{
		cout << temp->num << "  "
			<< temp->name << "  "
			<< temp->score << endl;
		temp = temp->previous;
	}

	system("pause");
	return 0;
}

测试结果

循环链表

循环链表简介

*定义：
循环链表是一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。

由双向链表推导循环链表

观察双向链表发现只需在首尾略作修改即可
代码如下

#include <iostream>
using namespace std;
struct student {
	long num;
	char name[20];
	float score;
	student* previous;
	student* next;
};
int main() {
	student *head = NULL, *temp = NULL, *temp2 = NULL;
	head = new student;
	temp = head;
	int i = 1;
	head->previous = NULL;
	while (!head->previous) {

		temp->num = i;
		cout << "Please input name and score for No." << i << endl;
		cin >> temp->name >> temp->score;
		temp->previous = NULL;
		temp->next = NULL;

		i++;

		if (i != 2)//操作temp->previous
			temp->previous = temp2;

		if (i == 5) {//操作temp->next
			temp2 = temp;
			temp->next = head;
			temp = temp->next;
			temp->previous = temp2;
		}
		else {
			temp2 = temp;
			temp->next = new student;
			temp = temp->next;
			temp->previous = temp2;
		}
	}

	temp = head;
	for (int j = 1; j < 10; j++)//验证循环输出两个循环以上
	{
		cout << temp->num << "  "
			<< temp->name << "  "
			<< temp->score << endl;
		temp = temp->next;
	}
	system("pause");
	return 0;
}

调试结果