C++——链表详解

本次博客，我将记录对链表的理解

《算法导论》上是这样定义链表的：
链表（linked list）是一种这样的数据结构，其中的各对象按线性顺序排列。数组的线性顺序是由数组下标决定的，然而与数组不同的是，链表的顺序是由各个对象里的指针决定的。

我们可以画张图来解释：

打个比方，一个用来存钱的抽屉，抽屉里不仅存有钱，还放着一张指明下一个抽屉位置的纸条，那么图中的data就可以理解为money，next就可以理解为纸条，这样，多个抽屉就形成了一个链式结构，形成链表

创建链表节点

根据以上的描述，链表节点可以按如下的方式进行创建：

struct ListNode{
	int data;
	ListNode *next;
}listnode;

data存储数据，next指针指向下一个节点
此外，链表中存储的数据可以多种多样，举个例子：

struct Birthday{
	int year;
	int month;
	int day;
};

struct ListNode{
	string name;
	int Student_number;
	Birthday birth;
	ListNode *next;
	ListNode *last;
}listnode;

创建链表
一个单向链表是有一个头和一个尾的

ListNode* ListCreate(int n){
	ListNode *head,*p1,*end;
	head=new ListNode;
	end=head;
	for(int i=0;i<n;i++){
		p1=new ListNode;
		p1->data=i;
		end->next=p1;
		end=p1;
	}
	end->next=NULL; //链表的尾部next指向空
	return head;
}

其中参数n即为链表中的节点数

遍历链表

void print(ListNode *head){		//将链表的头作为参数
	ListNode *temp;
	temp=head->next;
	while(temp!=NULL){
		cout<<temp->data<<' ';
		temp=temp->next;
	}
}

查找某个节点

ListNode* Find(ListNode *head,int n){	//n表示查找第n个节点
	ListNode *p=head;
	for(int i=0;i<n&&p!=NULL;i++){
		p=p->next;
	}
	if(p==NULL){
		cout<<"找不到/(ㄒoㄒ)/~~"<<endl;
	}
	return p;
}

修改某节点的数据

void ListChange(ListNode *head,int n,int temp){
	ListNode *p=head;
	for(int i=0;i<n&&p!=NULL;i++){
		p=p->next;
	}
	if(p!=NULL){
		p->data=temp;
	}
	else cout<<"找不到节点/(ㄒoㄒ)/~~"<<endl;
}

插入新节点

ListNode* ListInsert(ListNode *head,int n,int data){
	ListNode *p=head;
	ListNode *in=new ListNode;
	for(int i=0;i<n&&p!=NULL;i++){
		p=p->next;
	}
	if(p!=NULL){
		in->data=data;
		in->next=p->next;
		p->next=in;
	}
	else cout<<"找不到/(ㄒoㄒ)/~~"<<endl;
}

删除某节点

void ListDelete(ListNode *head,int n){
	ListNode *p=head,*p1=head;
	for(int i=0;i<n&&p!=NULL;i++){
		p1=p;
		p=p->next;
	}
	if(p!=NULL){
		p1->next=p->next;
		delete p;
	}
	else cout<<"找不到节点/(ㄒoㄒ)/~~"<<endl;
}

最后，给出全部代码：

#include<iostream>
using namespace std;
struct ListNode{
	int data;
	ListNode *next;
}listnode;

ListNode* ListCreate(int n){
	ListNode *head,*p1,*end;
	head=new ListNode;
	end=head;
	for(int i=0;i<n;i++){
		p1=new ListNode;
		p1->data=i;
		end->next=p1;
		end=p1;
	}
	end->next=NULL; //链表的尾部next指向空
	return head;
}

ListNode* Find(ListNode *head,int n){
	ListNode *p=head;
	for(int i=0;i<n&&p!=NULL;i++){
		p=p->next;
	}
	if(p==NULL){
		cout<<"找不到/(ㄒoㄒ)/~~"<<endl;
	}
	return p;
}

ListNode* ListInsert(ListNode *head,int n,int data){
	ListNode *p=head;
	ListNode *in=new ListNode;
	for(int i=0;i<n&&p!=NULL;i++){
		p=p->next;
	}
	if(p!=NULL){
		in->data=data;
		in->next=p->next;
		p->next=in;
	}
	else cout<<"找不到/(ㄒoㄒ)/~~"<<endl;
}

void print(ListNode *head){
	ListNode *temp;
	temp=head->next;
	while(temp!=NULL){
		cout<<temp->data<<' ';
		temp=temp->next;
	}
	cout<<endl;
}

void ListChange(ListNode *head,int n,int temp){
	ListNode *p=head;
	for(int i=0;i<n&&p!=NULL;i++){
		p=p->next;
	}
	if(p!=NULL){
		p->data=temp;
	}
	else cout<<"找不到节点/(ㄒoㄒ)/~~"<<endl;
}

void ListDelete(ListNode *head,int n){
	ListNode *p=head,*p1=head;
	for(int i=0;i<n&&p!=NULL;i++){
		p1=p;
		p=p->next;
	}
	if(p!=NULL){
		p1->next=p->next;
		delete p;
	}
	else cout<<"找不到节点/(ㄒoㄒ)/~~"<<endl;
}
int main()
{
	int n=6;
	
	//创建一个长度为6的链表 
	ListNode *head=new ListNode;
	head=ListCreate(n);
	print(head);
	
	//修改第二个节点为999 
	ListChange(head,2,999); 
	print(head);
	
	//在第三个节点后面插入新节点，数据为1000 
	ListInsert(head,3,1000);
	print(head);
	
	//删除第三个节点
	ListDelete(head,3);
	print(head); 
	
	return 0;
}

输出结果为：

0 1 2 3 4 5
0 999 2 3 4 5
0 999 2 1000 3 4 5
0 999 1000 3 4 5

本文完