c++实现链表单双环链表

数据结构

链表

1.链表实质上是一个结构体,包含数据域和指针域,这两个实际上都是一个变量而已,只不过数据域存放的是节点的数据,指针域存放的是下一个节点的地址

2.我们新建一个链表节点的时候通常采取的语句类似于NumList* head=(NumList*)malloc(sizeof(NumList)),要注意,语句实际上分为两部分

​ 第一部分是NumList*head,表示定义了一个NumList类型的指针head,head是一个指针,不能存储任何东西,只能指向要存储的节点

​ 第二部分是(NumList*)malloc(sizeof(NumList))这里是创建了一个节点,这个节点是真正存储数据的地方,而让head等于它表示让head指针指向这个节点,指向之后就可以用head表示这个节点,head->next等等,但注意head本质上仍然是一个指针,只是用head引用所指的节点而已,所以head指向的位置是可以改变的,比如现在有一个尾指针tail指向尾节点,但我们让tail=head,这样表示尾指针tail指向头节点,之后用tail所指向的节点就也是头节点

3.注意链表在传进函数时是自动直接传的地址,所以直接传链表就可以在函数中修改,但指针不是,指针传进函数并不是传的指针的地址,所以在函数中对指针进行修改并不会真的影响到指针所指的位置,也就是节点在函数中被修改是真的被修改了,但指针这种并没有真的被修改,如果想修改就要加一个&表示传这个指针的地址进去比如传一个指针tail就要传&tail

数组也是直接传地址

//添加数据在链表末尾的函数,传进主函数中规定的头指针,尾指针,和要传的数字
//注意尾指针由于在函数当中有移动,所以前面要加上&也就是传入尾指针的地址,让函数可以对尾指针进行修改
//head不用传地址是因为head指针只起到坐标作用,并不xu'yao在函数中被修改,所以不需要传地址
void insertData(NumList* head,NumList* &tail,int listData) {
	NumList* temp = (NumList*)malloc(sizeof(NumList));
	temp->data = listData;
	temp->next = NULL;
	tail->next = temp;
	tail = tail->next;
}

打印链表

正常打印

直接用遍历的方式打印

递归打印

void PrintData(LNode* head) {
	cout << head->data << " ";
	PrintData(head->next);
}

反转链表

把链表倒过来

迭代方式实现

有两种方式

1.第一种是创建链表的时候定义了尾指针:头指针和尾指针指向的节点都不动,每次把头指针的下一个拼接在尾指针的后面,除了头节点以外假如有n个节点,那就只需要拼n-1次,一般头节点都会存储节点总个数,反转方式相当于head->1->2->3->4->5->tail,第一次修改为head->2->3->4->5->tail->1,以此类推直到head->tail->5->4->3->2->1

2.第二种是没有尾指针,那就定义一个指针p指向头节点a的下一个的下一个,然后头节点a的下一个指向头节点a,然后头指针修改为头节点a的下一个,定义一个q指针指向p的下一个,p节点的下一个指向头指针head当前的位置,然后头指针往后一个,p指针指向q节点,q指针指向p的下一个,也就是(*head->)0->( *p0->)1->( *p1->)2->3->4->5,第一次变换过程是先链表断开分为三个部分 NULL<-(*head->)0 ( *p0->)1 ( *p1->)2->3->4->5,然后NULL<-(*head->)0 <-( *p0->)1 ( *p1->)2->3->4->5,然后NULL<-0 <-(*head->)1 ( *p0->)2->( *p1->)3->4->5

第二次变换过程是NULL<-0 <-(*head->)1 ( *p0->)2 ( *p1->)3->4->5,然后NULL<-0 <-(*head->)1<-( *p0->)2 ( *p1->)3->4->5,然后NULL<-0 <-1<-(*head->)2 ( *p0->)3->( *p1->)4->5以此类推

//反转链表
void reverseLinkList(LNode* &head) {
	//定义指针p0p1分别指向当前要移动的节点和当前要移动的节点的下一个也就是断开的链表的第二串的开头
	LNode* p0, * p1;
	p0 = head->next;
	p1 = p0->next;
	head->next = NULL;
	while (p1 != NULL) {
		p0->next = head;
		head = p0;
		p0 = p1;
		p1 = p1->next;
	}
	p0->next = head;
	head = p0;
}

注意这种方式要看链表的头节点尾节点的性质而定,以下给出一个头插法反转链表的例子,这个例子当中头插法创建的链表head节点到倒数第二个节点是数据节点,最后一个节点是空节点

# include<iostream>
using namespace std;
//定义节点结构体,包括数据域和指针域
struct LNode {
	int data;
	struct LNode* next;
};
//传进一个头节点,每次插在头节点前面,并更新头指针
//头插法,但注意头插法是倒着输入数据的
void insertData(LNode*& head, int listData) {
	LNode* temp = (LNode*)malloc(sizeof(LNode));
	temp->data = listData;
	temp->next = head;
	head = temp;
}
//反转链表
void reverseLinkList(LNode*& head) {
	//定义指针p0p1分别指向当前要移动的节点和当前要移动的节点的下一个也就是断开的链表的第二串的开头
	LNode* p0, * p1;
	p0 = head->next;
	p1 = p0->next;
	head->next = NULL;
	while (p1 != NULL) {
		p0->next = head;
		head = p0;
		p0 = p1;
		p1 = p1->next;
	}
}
int main() {
	LNode* head = (LNode*)malloc(sizeof(LNode));
	head->next = NULL;
	int listData;
	cin >> listData;
	while (listData != 0) {
		insertData(head, listData);
		cin >> listData;
	}
	reverseLinkList(head);
	LNode* p = head;
	while (p != NULL) {
		cout << p->data << " ";
		p = p->next;
	}
}

单向链表

只有一个指针域,只能单向的遍历

有两种添加的方法,尾插法和头插法

尾插法

定义两个指针,头指针一直指着头,这是链表的坐标所在,不能动,尾指针每次加一个节点就要更新,确保会一直停留在结尾节点,每次添加数据就添加在尾指针后面

# include<iostream>
using namespace std;
//定义节点结构体,包括数据域和指针域
struct LNode {
	int data;
	struct LNode* next;
};
//定义添加数据的函数,参数为链表的尾指针和要添加的数据
//尾指针要在函数中更新,所以尾指针要传地址进来
void insertData(LNode*& tail, int listData) {
	//创建一个局部指针temp用来进行每一次的节点增加时指向要增加的那个节点
	LNode* temp = (LNode*)malloc(sizeof(LNode));
	//把listData赋值给temp的数据域
	temp->data = listData;
	//让尾节点的指针域指向temp节点,也就是把temp节点添加到链表中
	tail->next = temp;
	//让最后一个节点temp的指针域指向空
	temp->next = NULL;
	//把尾指针指向此时的最后一个节点temp,更新尾指针
	tail = temp;
}
int main() {
	//创建变量listData来存储每次要加入节点的数据
	int listData;
	//创建头指针和尾指针,分别指向头节点和尾节点
	LNode* head= (LNode*)malloc(sizeof(LNode));
	//由于一开始链表没有数据,所以头指针和尾指针都指向头节点
	LNode* tail = head;
	//一般把头节点的数据域设置为链表中除了头节点以外节点的个数
	head->data = 0;
	//把头节点指针域设置为空
	head->next = NULL;
	cin >> listData;
	//这里是输入的数据以0结尾作为例子
	while (listData != 0) {
		//添加节点
		insertData(tail, listData);
		//添加完节点后节点数+1那么就让头节点数据域加一
		head->data++;
		//输入数据
		cin >> listData;
	}
	//遍历指针p,一开始指向头节点的下一个,从这里开始一个一个遍历链表
	LNode* p = head->next;
	while (p != NULL) {
		cout << p->data << " ";
		p = p->next;
	}
}

头插法

定义一个头节点,每次在头节点前面插入一个节点,每次更新头指针

# include<iostream>
using namespace std;
//定义节点结构体,包括数据域和指针域
struct LNode {
	int data;
	struct LNode* next;
};
//传进一个头节点,每次插在头节点前面,并更新头指针
//头插法,但注意头插法是倒着输入数据的
void insertData(LNode*& head, int listData) {
	LNode* temp = (LNode*)malloc(sizeof(LNode));
	temp->data = listData;
	temp->next = head;
	head = temp;
}
int main() {
	LNode* head = (LNode*)malloc(sizeof(LNode));
	head->next = NULL;
	int listData;
	cin >> listData;
	while (listData != 0) {
		insertData(head, listData);
		cin >> listData;
	}
	LNode* p = head;
	while (p->next != NULL) {
		cout << p->data << " ";
		p = p->next;
	}
}

双向链表

//定义添加数据的函数,参数为链表的尾指针和要添加的数据
//尾指针要在函数中更新,所以尾指针要传地址进来
void insertData(LNode*& tail, int listData) {
	//创建一个局部指针temp用来进行每一次的节点增加时指向要增加的那个节点
	LNode* temp = (LNode*)malloc(sizeof(LNode));
	//把listData赋值给temp的数据域
	temp->data = listData;
	//让尾节点的指针域指向temp节点,也就是把temp节点添加到链表中
	tail->next = temp;
	temp->pre = tail;
	//让最后一个节点temp的指针域指向空
	temp->next = NULL;
	//把尾指针指向此时的最后一个节点temp,更新尾指针
	tail = temp;
}

环链表

只需要尾节点的指针域指向头节点