数据结构链表详解(不仅顺序表可以,我链表也可以)

admin2024-05-15  0

目录

顺序表的缺点:

链表

链表的概念及其结构

链表的分类

链表的实现

链表形式:

节点的创建:

链表的增删:

尾插

头插

尾删

头删

查找 

打印

链表的重点

 1、尾删:则是需要找到尾节点,进行删除

2、头删:找到头节点的下一个节点,在删除头节点

在指定位置之前插入数据

在指定位置之后插入数据

删除pos之后的节点 

链表的摧毁

以上我们完成了链表的实现,可以尝试一下使用顺序表或链表实现通讯录!!!!


我们上节学习了顺序表的实现.

顺序表的缺点:

  • 任意位置插入或者删除元素的效率低:每次插入或者删除需要搬移元素;
  • 考虑空间的大小是否需要开辟空间

以下为顺序表与链表的不同点

数据结构链表详解(不仅顺序表可以,我链表也可以),第1张

链表

链表的概念及其结构

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

数据结构链表详解(不仅顺序表可以,我链表也可以),第2张

数据结构链表详解(不仅顺序表可以,我链表也可以),第3张

链表的分类

1. 单向或者双向

数据结构链表详解(不仅顺序表可以,我链表也可以),第4张

2. 带头或者不带头

数据结构链表详解(不仅顺序表可以,我链表也可以),第5张

3. 循环或者非循环

数据结构链表详解(不仅顺序表可以,我链表也可以),第6张

虽然链表的类型很多,但是我们实际中最常用还是两种结构:

数据结构链表详解(不仅顺序表可以,我链表也可以),第7张

链表的实现

#pragma once
//定义节点的结构
//数据 + 指向下一个节点的指针
typedef int SLTDataType;

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

void SLTPrint(SLTNode* phead);

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);

链表形式:

//定义节点的结构
//数据 + 指向下一个节点的指针
typedef int SLTDataType;

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

节点的创建:

链表是一个个节点连接起来的,所以我们的第一步应该动态申请节点

//开辟新结点
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)//判断开辟是否成功
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

链表的增删:

尾插

我们先要创建一个存放x的新节点,然后找到节点的尾,在将为节点的next指向新节点

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) {
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);//创建一个新节点
	if (*pphead==NULL) {
		*pphead = newnode;
	}
	else {
		//创建一个尾节点,找尾
		SLTNode* ptail = *pphead;
		while (ptail->next) {
			ptail = ptail->next;//找链表下一个为NULL的地址
		}
		//下一个为NULL,出循环
		ptail->next = newnode;
	}
}

头插

头插对于尾插简单不少,先创建新节点,将新节点的next指向头节点,然后将地址赋给头节点

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);//创建一个新节点
	if (*pphead == NULL) {
		*pphead = newnode;
	}
	else {
		newnode->next = *pphead;
		*pphead = newnode;//头节点为新的节点
	}
}

尾删

//尾删
void SLTPopBack(SLTNode** pphead) {
	assert(pphead && *pphead);
	if ((*pphead)->next == NULL) {//->的优先级高于();
		//只存在一个节点
		free(*pphead);
		*pphead = NULL;
	}
	else {
		//找尾节点
		SLTNode* pcur = *pphead;//保存尾节点的上一个节点
		SLTNode* ptail = *pphead;
		while (ptail->next) {
			pcur = ptail;
			ptail = ptail->next;
		}
		free(ptail);
		ptail = NULL;
		pcur->next = NULL;
	}
}

头删

//头删
void SLTPopFront(SLTNode** pphead) {
	assert(pphead && *pphead);
	SLTNode* pcur = (*pphead)->next;
	free(*pphead);

	*pphead = NULL;
	*pphead = pcur;
}

查找 

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x) {
			return pcur;
		}
		pcur = pcur->next;
	}
	//没有查找到
	return NULL;
}

打印

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

链表的重点

数据结构链表详解(不仅顺序表可以,我链表也可以),第8张

 这是一串链表,在链表中的增删查改,其实是需要关注其节点;

 1、尾删:则是需要找到尾节点,进行删除

如果我们将为释放掉,那尾节点的上一个节点,指向哪里,将会沦为野指针,是非常危险的,所以我们得创建一个指针,用来找到这个节点,这就是尾删的重点

数据结构链表详解(不仅顺序表可以,我链表也可以),第9张

2、头删:找到头节点的下一个节点,在删除头节点

与尾删类似,我们需要考虑如果将phead删除,我们如何找到新的头节点

数据结构链表详解(不仅顺序表可以,我链表也可以),第10张

综上所述:链表的难度常常发生在其释放时,指针的丢失或者成为野指针,如果注意其,我们将事半功倍,减少bug的产生;


//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);

//销毁链表
void SListDesTroy(SLTNode** pphead);

在指定位置之前插入数据

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
	assert(pphead && *pphead);
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);//创建一个新节点
	if (pos == *pphead) {
		//头插
		SLTPushFront(*pphead, x);
	}
	else{
		SLTNode* prev = *pphead;
        //找到pos的上个节点
		while (prev->next != pos) {
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
}

在指定位置之后插入数据

void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	SLTNode* pcur = pos->next;
    //保存pos下一个节点,以防节点丢失
	pos->next = newnode;
	newnode->next = pcur;
}

删除pos之后的节点 

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

链表的摧毁

//销毁链表
void SListDesTroy(SLTNode** pphead) {
	assert(pphead && *pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;

	}
	*pphead = NULL;
}

总体展示:

#define _CRT_SECURE_NO_WARNINGS
#include"slist.h"
#include<assert.h>


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

//开辟新结点
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) {
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);//创建一个新节点
	if (*pphead==NULL) {
		*pphead = newnode;
	}
	else {
		//创建一个尾节点,找尾
		SLTNode* ptail = *pphead;
		while (ptail->next) {
			ptail = ptail->next;//找链表下一个为NULL的地址
		}
		//下一个为NULL,出循环
		ptail->next = newnode;
	}
}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);//创建一个新节点
	if (*pphead == NULL) {
		*pphead = newnode;
	}
	else {
		newnode->next = *pphead;
		*pphead = newnode;//头节点为新的节点
	}
}

//尾删
void SLTPopBack(SLTNode** pphead) {
	assert(*pphead && pphead);
	//只有一个节点,直接释放掉
	if ((*pphead)->next == NULL) //-> 优先级高于*
	{
		free(*pphead);
		*pphead = NULL;
	}
	else {
			//链表有多个节点

			SLTNode* prev = *pphead;
			SLTNode* ptail = *pphead;
			while (ptail->next) {
				prev = ptail;
				ptail = ptail->next;
		  }
			free(ptail);
			ptail = NULL;
			prev->next = NULL;
	}
}

//头删
void SLTPopFront(SLTNode** pphead) {
	//链表不能为空
	assert(pphead && *pphead);

	SLTNode* next = (*pphead)->next; //-> 优先级高于*
	free(*pphead);
	*pphead = NULL;
	*pphead = next;

}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x) {
			return pcur;
		}
		pcur = pcur->next;
	}
	//没有查找到
	return NULL;
}

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead&&*pphead);
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);//创建一个新节点
	//如果为头插
	if (pos == *pphead) {
		SLTPushFront(pphead,x);
	}
	else {
		SLTNode* prev = *pphead;
		while (prev->next != pos) {
			prev = prev->next;
		}
		//找到pos的上一个节点
		prev->next = newnode;
		newnode->next = pos;
	}
}

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	SLTNode* pcur = pos->next;
	pos->next = newnode;
	newnode->next = pcur;

}


//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	//pos是头结点/pos不是头结点
	if (pos == *pphead)
	{
		//头删
		SLTPopFront(pphead);
	}
	else {
		SLTNode* prev = *pphead;
		while (prev->next != pos) {
			prev = prev->next;
		}
		prev->next = pos->next;
		//减少创建一个节点保存pos->next的节点
		free(pos);
		pos = NULL;
	}
}

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

//销毁链表
void SListDesTroy(SLTNode** pphead) {
	assert(pphead&&*pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;

	}
	*pphead = NULL;
}

数据结构链表详解(不仅顺序表可以,我链表也可以),第11张

以上我们完成了链表的实现,可以尝试一下使用顺序表或链表实现通讯录!!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!