Java教程

【数据结构初阶】链表详解(一)无哨兵位单向非循环链表

本文主要是介绍【数据结构初阶】链表详解(一)无哨兵位单向非循环链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

链表概念及结构

概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

在这里插入图片描述

  • 链式结构在逻辑上是连续的,但是在物理上不一定连续
  • 现实中的结点一般都是从堆上申请出来的
  • 从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续

实际上链表的结构非常多样,组合起来有8种链表结构。

1.单向或双向
在这里插入图片描述
2.带头或者不带头

在这里插入图片描述
3. 循环与非循环

在这里插入图片描述
本文介绍的是 无头单向非循环链表

在这里插入图片描述
无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

SListNode结点结构体

链表是由一个一个结点链接起来的,所以在创建一条链表前,首先要创建一个结点。结点由两部分组成:数据域和指针域。

typedef int SLTDataType;

typedef struct SListNode {
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

函数接口

// 动态申请一个结点
SLTNode* BuySListNode(SLTDataType x);
// 单链表打印
void SListPrint(SLTNode* phead);
// 单链表尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);
// 单链表头插
void SListPushFront(SLTNode** pphead, SLTDataType x);
// 单链表尾删
void SListPopBack(SLTNode** pphead);
// 单链表头删
void SListPopFront(SLTNode** pphead);
// 单链表查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SLTNode* pos);
// 单链表的销毁
void SListDestroy(SLTNode** pphead);

下面对以上功能进行实现。

打印单链表

打印单链表,需要从头指针指向的位置开始,依次向后打印,直到指针指向NULL,结束打印。

void SListPrint(SLTNode* phead) {
	SLTNode* cur = phead;
	while (cur != NULL) {
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

单链表尾插

void SListPushBack(SLTNode** pphead, SLTDataType x) {
	assert(pphead);

	SLTNode* newnode = BuySListNode(x);

	if (*pphead == NULL) {
		*pphead = newnode;
	}
	else {
		SLTNode* tail = *pphead;
		while (tail->next != NULL) {
			tail = tail->next;
		}
		tail->next = newnode;
	}

}

注意:

  1. 此处的 assert(pphead);是为了防止传入的不是二级指针。
  2. 对单链表增加一个结点时,都要用到申请一个新的结点,所以我们不妨把该功能封装成一个函数。
SLTNode* BuySListNode(SLTDataType x) {
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL) {
		printf("malloc fail\n");
		exit(-1);
	}

	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

单链表头插

void SListPushFront(SLTNode** pphead, SLTDataType x) {
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

单链表尾删

注意点:

  1. 需要二级指针
  2. 对空链表,一个结点,两个及两个以上的结点分情况讨论
void SListPopBack(SLTNode** pphead) {
	assert(*pphead != NULL);

	// 一个结点
	if ((*pphead)->next == NULL) {
		free (*pphead);
		*pphead = NULL;
	}
	else {
		// 两个及两个以上结点
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL) {
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

单链表头删

注意:

  1. 需要判断是否为空链表。
  2. 更新头指针
void SListPopFront(SLTNode** pphead) {
	assert(*pphead != NULL);

	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

查找结点

遍历一遍链表,找到则返回当前结点,否则返回 NULL。

SLTNode* SListFind(SLTNode* phead, SLTDataType x) {
	for (SLTNode* cur = phead; cur != NULL; cur = cur->next) {
		if (cur->data == x) {
			return cur;
		}
	}
	return NULL;
}

单链表在pos位置之后插入x

这里首先引出一个问题,为什么需要选择在pos之后插入,而不是在pos之前插入呢?
其实是有原因的。如果只是在pos之后插入,无需遍历链表就可以操作;如果要在pos之前进行插入,需要遍历一遍链表,然而时间开销大(相比),O(N)。

注意点

  1. 判断是否属于尾插
  2. 插入结点的顺序 !!! 不可颠倒
    newnode->next = pos->next;
    pos->next = newnode;
void SListInsertAfter(SLTNode* pos, SLTDataType x) {
	SLTNode* newnode = BuySListNode(x);
	if (pos->next == NULL) {
		// 尾插
		pos->next = newnode;
	}
	else {
		newnode->next = pos->next;
		pos->next = newnode;
	}
}

单链表删除pos位置之后的值

void SListEraseAfter(SLTNode* pos) {
	assert(pos && pos->next);

	SLTNode* next = pos->next->next;
	free(pos->next);
	pos->next = NULL;
	pos->next = next;
}

单链表销毁

注意
单链表的销毁需要对结点进行逐个销毁。
为什么???
就凭他是一个一个在堆上开辟出来的,不像动态开辟的顺序表,在内存里是一段连续的内存空间。如果只对链表进行 free(*pphead)操作,是会造成内存泄漏的!!!

void SListDestroy(SLTNode** pphead) {
	SLTNode* cur = *pphead;
	while (cur) {
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

最后…

其实单链表没有那么可怕,可怕的是老师上课讲的稀里糊涂(狗头保命hhh),大家只要想象成火车的一节节车厢就好啦~~~

小汽车,嘟嘟嘟!!!
请添加图片描述

最后,如果喜欢博主的话,不妨点个关注哦! 码文不易,感恩ღ( ´・ᴗ・` )比心

这篇关于【数据结构初阶】链表详解(一)无哨兵位单向非循环链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!