欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

单链表:带头结点和不带头结点 总结

程序员文章站 2024-03-21 13:06:22
...

写在前面:

       一直以来,带头结点和不带头节点的单链表的操作实现困扰着我。在没有理解和实现之前,光凭思考真的是很难理解清楚
1.两者之间代码的差异;
2.带不带头结点的区别;
3.带头结点之后,什么情况下形参必须传二级指针(或者一级指针的引用);

       所以,当我攻克掉这个难题之后,就准备一次性捋清楚这些点,一来以便自己回顾用;而来,也希望对陌生的有需要的你有相关的帮助。

       OK,先简单摆出代码:

不带头结点的单链表操作:

//SList.h
#pragma once

typedef int SLDataType ;

typedef struct SListNode
{
	int data ;
	struct SListNode* next ;
}SListNode ;

typedef struct SList
{
	struct SListNode* first ;
}SList ;

//初始化&销毁
void SListInit(SList* list) ;

//销毁
void SListDestroy(SList* list) ;

//头插
void SListPushFront(SList* list, SLDataType data) ;

//头删
void SListPopFront(SList* list) ;

//打印
void SListPrint(SList* list) ;

//尾插
void SListPushBack(SList* list, SLDataType data) ;

//尾删
void SListPopBack(SList* list) ;

//查找
SListNode* SListFind(SList* list, SLDataType data) ;

//在pos位置的节点后插入元素
void SListInsertAfter(SListNode* pos, SLDataType data) ;

//删除pos位置后的第一个节点
void SListEraseAfter(SListNode* pos) ;

//删除遇到的指定的第一个节点
void SListRemove(SList* list, SLDataType data) ;
//**************************************************
//SList.c
#include "SList.h"
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

//初始化
void SListInit(SList* list) 
{
	assert(list != NULL) ;
	list->first = NULL ;
}

//销毁
void SListDestroy(SList* list) 
{
	SListNode* next ;
	SListNode* cur ;
	for(cur=list->first; cur!=NULL; cur=next)
	{
		next = cur->next ;
		free(cur) ;
	}
	list->first = NULL ;
}

//头插
void SListPushFront(SList* list, SLDataType data) 
{
	SListNode* node = (SListNode*) malloc (sizeof(SListNode)) ;
	assert(node) ;
	node->data = data ;
	node->next = list->first ;
    //更新头指针的指向;
	list->first = node ;
}

//头删
void SListPopFront(SList* list) 
{
	SListNode* old_first = list->first ;
	assert(list) ; //有无链表
	assert(list->first != NULL) ; //有链表,链表里是否有元素,
	                              //若链表为空,则删除失败
	list->first = list->first->next ;
	free(old_first) ;
}

//打印
void SListPrint(SList* list) 
{
	SListNode* cur ;
	assert(list) ;
	for(cur=list->first; cur!=NULL; cur=cur->next)
	{
		printf("%d-->", cur->data) ;
	}
	printf("NULL\n") ;
}

//尾插
void SListPushBack(SList* list, SLDataType data)
{
	SListNode* node = (SListNode*) malloc (sizeof(SListNode)) ;
	SListNode* lastone = list->first ;
	assert(list != NULL) ;
	for( ; lastone->next != NULL; lastone=lastone->next)
	{}
	assert(node != NULL) ;
	node->data = data ;
	node->next = lastone ->next ;
	lastone->next = node ;
}

//尾删
void SListPopBack(SList* list)
{
	SListNode* cur ;
	SListNode* m ;
	assert(list != NULL) ;
	assert(list->first != NULL) ;
	if(list->first->next  == NULL)
	{
		//若链表为空,则尾删即为头删
		SListPopFront(list) ;
		return ;
	}
	for(cur=list->first; cur->next->next != NULL; cur=cur->next)
	{
	}//找到倒数第二个节点
    m = cur->next ;
	cur->next = m->next ;
	free(m) ;
}

//查找
SListNode* SListFind(SList* list, SLDataType data)
{
	SListNode* cur = list->first ;
	for( ; cur!=NULL; cur=cur->next)
	{
		if(cur->data == data) 
		{
			return cur ;
		}
	}
	return NULL ;
}

//在pos位置的节点后插入元素
void SListInsertAfter(SListNode* pos, SLDataType data) 
{
	SListNode* node = (SListNode*) malloc (sizeof(SListNode)) ;
	assert(node != NULL ) ;
	node->data = data ;
	node->next = pos->next ;
	pos->next = node ;
}

//删除pos位置后的第一个节点
void SListEraseAfter(SListNode* pos)
{
	SListNode* node = pos->next->next ;
	free(pos->next) ;
	pos->next = node ;
}

//删除遇到的指定的第一个节点
void SListRemove(SList* list, SLDataType data)
{
	SListNode* prev = NULL ;
	SListNode* cur = list->first ;
	while(cur != NULL && cur->data != data)
	{
		prev = cur ;
		cur = cur->next ;
	}
	//要删除的节点不存在
	if(cur == NULL )
	{
		return ;
	}
	//要删除的节点若就是第一个节点
	if(prev == NULL)
	{
		//即头删
		SListPopFront(list) ;
		return ;
	}
	prev->next = cur->next ;
	free(cur) ;
}

带头结点的单链表简单操作:

//带头结点的单链表的实现
#pragma once

#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
typedef int DataType;

typedef struct ListNode{
	DataType _data;
	struct ListNode* next;

}Node,* PNode;


PNode buy_new_node(int x)
{
	PNode _node = (PNode)malloc(sizeof(Node));
	_node->_data = x;
	_node->next = NULL;
	return _node;

}

//初始化
void init(PNode head)
{

	PNode node = buy_new_node(0);
	head->next = node;

}
//头插
void push_front(PNode* head,DataType x)
{
	assert(*head != NULL);
	PNode _node = buy_new_node(x);
	_node->_data = x;
	_node->next = (*head)->next;
	(*head)->next = _node;

}


//头删
void pop_front(PNode* head)
{
	assert(*head != NULL);
	PNode tmp = (*head)->next;
	(*head)->next = (*head)->next->next;
	free(tmp);

}

//尾插
void push_back(PNode head,DataType x)
{
	assert(head != NULL);
	//r如果链表为空,那么就是进行头插
	if ((head->next) == NULL)
	{
		push_front( &head, x);
	}
	//链表不为空
	PNode cur = NULL;
	for (cur = head->next; cur->next != NULL; cur = cur->next)
	{}
	PNode _node = buy_new_node(x);
	_node->_data = x;
	_node->next = cur->next;
	cur->next = _node;

}


//尾删
void pop_back(PNode head)
{
	assert(head != NULL);
	//如果只有一个元素 ,那么进行头删
	if ((head->next->next) == NULL)
	{
		pop_front(&head);
	}
	//否则
	PNode cur = NULL;
	for (cur = head->next; cur->next->next != NULL; cur = cur->next)
	{}
	PNode tmp = cur->next;
	cur->next = tmp->next;
	free(tmp);



}
//pos位置之后插入  更改头插和头删的代码


//打印
void print(PNode head)
{
	assert(head != NULL);
	if (head->next == NULL)
		return;


	PNode cur = NULL;
	for (cur = head->next;cur->next!=NULL;cur=cur->next)
	{
		printf("%d--> ", cur->_data);
	}
	printf("NULL");

}

OK,先简单的展示出相关代码,暂时解决掉第一个问题。下来我们分析第二个问题:带不带头结点操作的区别又在哪里呢?

第一点:

不带头节点: p1->p2->p3 ->p1->p2->p3-> p1…
       我们先创建头指针,初始化的时候只需要将头指针赋NULL就可以了;大家想想,如果在这种情况下,我们进行头删操作,最后一步必须得做的事就是: 更新头指针的指向
或者换句话说,一旦对首元节点(头指针指向首元结点)进行操作,首尾工作必定得进行更新

带头节点:head-> p1->p2->p3 ->p1->p2->p3-> p1…
       与上边相反,每次进行涉及到首元结点的操作后,更新的过程就会很简单。我们不需要再去移动头指针,只需要固定的更新头结点中的指针域就可以了。

第二点:

再者,带头节点可以方便,快速的定位链表第1个节点。
比如循环链表的时候,删除p1 的时候:

head->next = p2;
p3->next = head->next; 
free(p1);

思路很清晰,链表开始的第1个节点现在就是head->next 即 p2

否则没有头节点:

p3->next = p1->next;
free(p1); 

会不会有一种链表第1个节点到底是哪个的感觉?

第三点:

不带头结点的单链表对于第一个节点的操作与其他节点不一样,需要特殊处理,这增加了程序的复杂性和出现bug的机会,因此,通常在单链表的开始结点之前附设一个头结点。

       
Ok,趁热打铁,最后我们分析带头结点后的传参二级指针(或一级指针的引用)问题。
这个问题一度困扰我很久,想明白之后其实也觉得没什么。
1.我们先分析什么时候需要形参是二级指针?
答: 在对带头结点的单链表进行涉及到头指针的操作,例如头插,头删等操作时,形参必须是二级指针。

2.为什么?
大家还记得最初学习的时候,我们应该都写过一个交换两个数字的swap()函数吧。我们形参如果是 int a ,int b;实参传swap(a,b),我们发现执行swap()之后,并没有达到交换的结果。原因就是在swap函数中形参是实参的一份临时拷贝,swap栈帧销毁之后,对应产生的临时变量也就销毁了。那么,我们是怎么解决的呢?

//我们形参这么去定义
swap(int *a,int* b);
...
...
//实参传的是两个数对应的地址
swap(&a,&b);

对。我们实参传递的是这两个int类型的地址。
我们想要修改int类型的变量,形参必须得传int类型的地址,形参用int ※接收;
那么同理,我们现在想要修改头结点中的指针域(指向首元结点),是node※类型。那么我们就理应传地址过去,形参对应的用 node※※接收。

node* head;
push_front(&head, 1);  //head取址,形参用二级指针接收

形参的类型是由传递的实参决定的。

到这里,三个问题都已经做出了相应的解答,希望可以对有需要的您有所帮助。也欢迎大家在评论区补充指正。