博客

C语言：单链表——初识链表

  • Post author:
  • Post category:其他



目录


写在前面：


序言——数组的缺陷


什么是链表


节点


链表头


创建新的节点


重头戏——插入节点


链表的遍历


链表的查找（搜索）


链表的删除


链表的清除


总结


写在后面


参考资料


写在前面：

本文适合初学者学习，鉴于本人能力有限以及希望读者可以在最短的时间内获得最高的收益的原则，本人不阐述过多的专业术语以及底层知识，简明扼要，精简文字，避免文章晦涩冗长。


本文需要用到的知识：指针，结构，typedef，动态内存分配（malloc和free）

序言——数组的缺陷

大家刚开始接触数组时会觉得数组很方便，可以储存大量数据，但随着学习的深入，数组的功能已经不再能满足我们的需求，数组的缺点也慢慢凸显出来：

1、数组在使用前必须确定元素个数，不够灵活；

2、对于插入元素和删除元素操作，往往会使得数组中很大一部分元素要前移或后移，不够高效；

3、对于一个既定的数组，其只能储存单一类型的变量；

为了解决这些问题，我们可以使用

可变数组

来解决，但这种方法实际运用中并不常见，我们不再赘述。我们更推荐使用

链表（Linked List）

来解决这些问题。

什么是链表

链表是一些包含数据的独立数据结构（即节点）的集合，链表中的节点通过指针相连，程序通过指针来访问节点以及节点中的数据。

相信大家对网络游戏并不陌生，我们以网络游戏为喻，以求读者能够获得更好的理解。游戏中往往会有一些回报丰厚的“悬赏任务”，经常是“剥洋葱式”的模式，先去某地做某事，完成后再告诉你下一个任务地点以及任务内容，如此循环，直到做完最后一个任务便可以得到“赏金”。我们的链表也是如此，在下面的介绍中您能慢慢体会到。


节点

链表的节点为struct类型，例如： 

    struct Node{
        //数据域
		int num; 
        //指针域 
		struct Node *next;
	};

这便是一个简单的节点，我们将节点中储存数据的内存区域称为数据域，储存指针的内存区域称为指针域。指针域的存在使得我们连接链表的各个节点成为了可能。


链表头

对于一个链表，我们需要知道它的起始地址，就如同使用数组时我们需要知道它的数组名一样重要（数组名即为数组的起始地址），其作用也相当于数组的数组名，于是我们定义一个

根指针

，其指向链表中的第一个节点。

一般来说

，我们不初始化表头中的数据，也不使用表头中的数据。我们可以这样定义根指针： 

struct Node * headList=NULL;

我们先令其指向NULL，避免其成为野指针。


创建新的节点

	 //创建节点
	 int cnum;
	 cin>>cnum;
	 struct Node* newNode =(struct Node*)malloc(sizeof (struct Node));
	 newNode->num=cnum;
	 newNode->next=NULL;

创建新的节点，我们采用动态内存分配的方式，将上述代码段放入循环中，便可以不断创建新的节点以保存输入的数据，显而易见，这样创造节点并不能满足我们的需求，因为它并没有将每个创造的节点之间连接起来。由于插入的方式较多，笔者将创建和插入分开一一阐述。


重头戏——插入节点

新建节点而不插入是没有意义的，没有联系的节点就像孤岛散落在世界各地一样，互相之间没有一点联系。这时就要发挥指针的强大作用了，如果我们在访问到一个节点时，可以同时获取到下一个节点的地址，那么不就可以实现连续的访问节点（遍历）了吗？于是我们在创建节点之后，要选择合适的方式进行插入，将节点连接在合适的位置，常见插入方式有

头插法

和

尾插法

等，下面我们以尾插法为例进行演示（尾插法即将新的节点连接在链表最后一个节点的后面，头插法即将新的节点连接在链表头和原来的第一个节点之间） 

	 //插入节点 
	 int cnum;
	 cin>>cnum;
	 struct Node* newNode =(struct Node*)malloc(sizeof (struct Node));
	 newNode->date=cnum;
	 newNode->next=NULL;
	 //找到末尾节点 
	 struct Node * tail=headList; 
	 if(tail){
		 while(tail->next){
		 	tail=tail->next;//当tail指向的节点中的next不为NULL时，则没有找到末尾节点，使tail指向下一个节点 
		 }
		 //将新的节点连接在末尾 
		 tail->next=newNode;
	}else
		headList=newNode;//当tail为空指针时，即链表为空时，我们使表头指向新建的节点，即链表的第一个节点

下面我们来解释上述代码，首先我们创建一个新的节点，再定义一个指针变量tail，使其从表头开始遍历整个链表，我们希望找到链表的尾部，依据尾部的next指针指向NULL的特点，我们设计了如上循环，找到尾结点后，我们令尾结点的next指针指向新的节点，以此建立原链表和新建节点之间的关系，即实现了新节点的插入。需要注意的是，要特别的判断tail指针是否本身就是空指针，若其本身就是空指针，则说明链表为空，这时只要使表头指向新建的节点即可。

链表的遍历

链表的遍历通过指针的相互连接来实现，每次使指针后移到下一个节点即可，遍历到尾结点时指针为NULL，退出循环遍历。 

		while(headList){
			cout<<headList->num<<endl;
			headList=headList->next;
	}


链表的查找（搜索）

对于一个数组，我们有很多的方式对其进行搜索，常见方式有线性搜索，以及效率更高的二分查找等等。对于单链表，我们介绍一种常用的类似于数组的线性查找的简单搜索方式： 

	 struct Node * findNode=headList;
	 int aim_num;
	 bool flag=true;
	 cin>>aim_num;
	 while(findNode){
	 	if(findNode->num==aim_num){
	 		cout<<"找到了\n";
	 		flag=false;
	 		break;
	 	}
	 	if(findNode->next==NULL)//遍历到最后一个节点仍然没有找到 
	 		break;
	 	else
	 		findNode=findNode->next;
	 }
	 if(flag)
	 	cout<<"找不到";


链表的删除

上文已经提到，数组在删除中间某个元素时会导致该元素后的元素全部前移，以至于效率非常低下。而在链表中，我们该如何去删除一个节点呢？首先，基于上述已经实现的链表的搜索，我们可以通过指针定位到我们希望删除的那个节点。

如图，我们该如何将这个节点从链表中删除掉？我们不妨称我们要删除的节点为目标节点，要删除目标节点很简单，我们只要令其上一个节点中的next指针指向目标节点的下一个节点而不是目标节点即可。

此外，你是否还记得我们是如何新建节点的？没错，是通过动态内存申请建立的，当我们不再使用这个节点（删除节点）时，我们还需要通过free（）函数来释放这部分内存。删除操作的代码如下： 

	struct Node * findNode=head;
	struct Node * p=NULL;
	int aim_num;
	cin>>aim_num;
	while(findNode){
	 	if(findNode->num==aim_num){
	 		p->next=findNode->next;
	 		free(findNode);
	 		cout<<"成功删除\n";
	 		break;
	 	}
	 	if(findNode->next==NULL){//遍历到最后一个节点仍然没有找到 
	 		cout<<"没有找到，删除失败\n";
	 		break; 
	 		} 
	 	else{
	 			p=findNode;
	 			findNode=findNode->next;
	 		}
	 }

我们新建一个指针p，其始终指向目标节点的上一个节点，这样当我们找到目标节点的时候，就可以通过指针p对上一个节点进行操作，使其中的next指针指向目标节点中next指向的地址。但是这样做是有漏洞的，当我们要删除的目标节点是链表的第一个节点时，不难发现，p指针为NULL，而NULL的”->”（arrow）操作是无效的。为了解决这个问题，我们只需要做以下修改即可： 

	struct Node * findNode=headList;
	struct Node * p=NULL;
	int aim_num;
	cin>>aim_num;
	while(findNode){
	 	if(findNode->num==aim_num){
	 		//判断p是否为空指针 
	 		if(p)
	 			p->next=findNode->next;
	 		else
	 			headList=findNode->next;//删除第一个节点，我们要让表头指向原来的第二个节点 
	 		free(findNode);
	 		cout<<"成功删除\n";
	 		break;
	 	}
	 	if(findNode->next==NULL){//遍历到最后一个节点仍然没有找到 
	 		cout<<"没有找到，删除失败\n";
	 		break; 
	 		} 
	 	else{
	 			p=findNode;
	 			findNode=findNode->next;
	 		}
	 }


链表的清除

当我们不再使用这个链表时，需要对其所在的内存进行释放，方式也很简单，遍历一遍即可。 

	 struct Node* p=headList;
	 struct Node* q=p;
	 while(p){
	 	q=p->next;
	 	free(p);
	 	p=q;
	 }

我们定义两个指针，当我们想要free掉p指针所指的节点时，我们提前让q指针指向该节点的下一个节点，在释放p所指的节点之后，我们令p=q，即令p指针指向刚刚释放的节点的下一个节点，如此循环往复，一直到释放掉最后一个节点的内存时，p=NULL，循环退出，链表清除完成。

总结

链表就像藏宝游戏，会有一个线索将你指向某地，之后取得另一个线索再将你指向某地…….上述一些代码看起来比较繁琐，实际是笔者为了便于初学者理解故意为之（例如while循环，使用for循环会精简一些，但理解不便），下面笔者会将上述几个功能通过函数封装： 

# include <iostream>
# include <cstdio>
# include <cstdlib>
using namespace std;
	typedef	struct myNode{
		int num;//数据域 
		struct myNode *next;//指针域 
	} Node; 
void List_creat(Node ** pheadList);
void NewNode(Node * headList,int cdate) ;
void  Tail_inter(Node ** headList,int cdate);
void  traversal_list(Node * pheadList);
void  Search_node(Node * headList,int aim_num);
void  Remove_node(Node * headList,int aim_num);
void  Clear_list(Node * headList);
int main()
{
	Node * mylist;
	List_creat(&mylist);
	Tail_inter(&mylist,1);
	Tail_inter(&mylist,3);
	Tail_inter(&mylist,5);
	Tail_inter(&mylist,7);
	Tail_inter(&mylist,9);
	traversal_list(mylist);
	cout<<"搜索链表中是否有7这个数据"<<endl;
	Search_node(mylist,7);
	cout<<"搜索链表中是否有10这个数据"<<endl;
	Search_node(mylist,10);
	//从链表中删除7这个数据 
	Remove_node(mylist,7);
	//再搜索7这个数据
	Search_node(mylist,7);
	//我们再来遍历这个链表看看
	cout<<endl<<"再次遍历\n";
	traversal_list(mylist);
	//回收内存
	Clear_list(mylist) ;
	return 0;
}

//创建表头 
void List_creat(Node ** pheadList)
{
	*pheadList=NULL;
}

//创建节点
void NewNode(Node * headList,int cdate) 
{
	Node* newNode =(Node*)malloc(sizeof (Node));
	newNode->num=cdate;
	newNode->next=NULL;
}

//尾插法插入节点
void  Tail_inter(Node ** pheadList,int cdate)
{
	Node* newNode =(Node*)malloc(sizeof (Node));
	newNode->num=cdate;
	newNode->next=NULL;
	Node * tail=*pheadList; 
	 if(tail){
		 while(tail->next){
		 	tail=tail->next;
		 }
		 tail->next=newNode;
	}else
		*pheadList=newNode;
}

//遍历链表 
void  traversal_list(Node * headList)
{
		while(headList){
			cout<<headList->num<<endl;
			headList=headList->next;
	}
}

//搜索节点
void  Search_node(Node * headList,int aim_num)
{
	Node * findNode=headList;
	 bool flag=true;
	 while(findNode){
	 	if(findNode->num==aim_num){
	 		cout<<"找到了\n";
	 		flag=false;
	 		break;
	 	}
	 	if(findNode->next==NULL)//遍历到最后一个节点仍然没有找到 
	 		break;
	 	else
	 		findNode=findNode->next;
	 }
	 if(flag)
	 	cout<<"找不到\n";
}

//删除节点
void  Remove_node(Node * headList,int aim_num)
{	Node * findNode=headList;
	Node * p=NULL;
	while(findNode){
	 	if(findNode->num==aim_num){
	 		//判断p是否为空指针 
	 		if(p)
	 			p->next=findNode->next;
	 		else
	 			headList=findNode->next;//删除第一个节点，我们要让表头指向原来的第二个节点 
	 		free(findNode);
	 		cout<<"成功删除\n";
	 		break;
	 	}
	 	if(findNode->next==NULL){//遍历到最后一个节点仍然没有找到 
	 		cout<<"没有找到，删除失败\n";
	 		break; 
	 		} 
	 	else{
	 			p=findNode;
	 			findNode=findNode->next;
	 		}
	 }
	
}

//清除链表
void  Clear_list(Node * headList)
{
	Node* p=headList;
	Node* q=p;
	while(p){
	 	q=p->next;
	 	free(p);
	 	p=q;
	 }
}

新建节点函数并没有被用到，出于种种原因，笔者仍将其保留。

运行结果

写在后面

本文代码并不完美，而且稍显繁琐，主要是为了给初学者以详细的阐述，如果有技术性错误，欢迎各位不吝赐教，私信指出，谢谢！

参考资料

《C和指针》 Kenneth A.Reek 著

《算法竞赛入门经典（第二版）》 刘汝佳 著


版权声明：本文为m0_61911953原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。