【数据结构3】链表之单链表

发布于：2022-12-14 ⋅ 阅读:(534) ⋅ 点赞:(0)

文章目录

1.链表概念

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

2.链表结构

链表分为一下几种：
1.单向、双向
2.带头、不带头
3.循环、非循环
今天讲解的是单向链表
单链表结构

typedef struct SListNode
{
	SLTDateType date;
	struct SListNode* next;
}SLTNode;

结构体需要的内容
1.需要存放的数据。
2.指向下一个数据的指针，若无指针数据则置为空。

3.创建节点函数

SLTNode* BuySLTNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		printf("malloc faile");
		exit(-1);
	}
	newnode->date = x;
	newnode->next = NULL;
	return newnode;
}

思路
1.申请一块空间存放要存放的数据和指向空的指针的内存；

4.单链表插入和删除

4.1头插

void SLTPushFront(SLTNode** pphead, SLTDateType x)
{
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

思路
1.申请一块空间存放数据和指向空的指针的内存
2.将头节点的地址放在新节点存放地址的指针中
3.将新节点的地址赋给指向头节点的指针中

4.2尾插

void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
	SLTNode* newnode = BuySLTNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

思路
1.申请一块空间存放数据和指向空的指针的内存
2.分为两种情况存放数据
a.单链表为空
直接将新节点的地址赋给头节点
b.单链表不为空
b.1先找出尾节点
b.2再将新节点的地址赋给尾节点的指针中

4.3头删

void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead != NULL);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

思路
1.先判断链表是否为空
2.将头节点中存放下一个地址的指针赋给一个临时指针
3.释放头节点
4.将临时指针赋给头节点

4.4尾删

void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead != NULL);
	
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		SLTNode* prev = NULL;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}
}

思路
1.判断链表是否为空
2.判断链表的数据是否大于一个
a.是 直接将头节点释放并置为空
b.不是 创建2个指针一个tail和prev
b.1tail寻找尾节点，prev尾部节点的前一个节点
b.2将尾节点释放并置空
b.3将尾节点的前一个节点的指针置空

4.5指定位置插入

void SLTInsert(SLTNode** pphead,SLTNode* pos, SLTDateType x)
{
	assert(pos != NULL);
	SLTNode* newnode = BuySLTNode(x);
	if (pos == *pphead)
	{
		newnode->next = *pphead;
		*pphead = newnode;

	}
	else
	{
		SLTNode* posprev = *pphead;
		while (posprev->next != pos)
		{
			posprev = posprev->next;
		}
		posprev->next = newnode;
		newnode->next = pos;
	}
	
}

思路
1.判断要插入的位置是不是头节点的前面
a.是
将头节点赋给新节点的指针，再将新节点赋给头节点
b.不是
创建一个指针posprev记住要插入节点的前一个节点，然后将新节点的地址赋给posprev，再将pos的地址赋给新节点的指针
注意：要和寻找函数配合使用

4.6指定位置删除

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pos != NULL);
	assert(*pphead != NULL);
	if (pos == *pphead)
	{
		SLTNode* cur = (*pphead)->next;
		free(*pphead);
		*pphead = cur;
	}
	else
	{
		SLTNode* posprev = *pphead;
		while (posprev->next != pos)
		{
			posprev = posprev->next;
		}
		posprev->next = pos->next;
		free(pos);
	}
}

思路
1.断言判断指针是否为空
2.判断要删除的是不是头节点
a.是
先创建一个临时指针cur记住头节点的指针里面的地址
再释放头节点
最后将临时指针赋给头节点

5.单链表打印和寻找

5.1打印

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

5.2寻找

SLTNode* SLTFind(SLTNode* phead,SLTDateType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->date == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

思路
1.遍历链表 找到返回地址 没找到返回NULL

6.单链表销毁

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

所有malloc的地址都要销毁

完整版代码

1.test.c

#include"SList.h"
void TestSlistNode1()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);

	SLTPrint(plist);

	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);

	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	//SLTPopFront(&plist);

	SLTDestory(&plist);
}
void TestSlistNode2()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);


	SLTNode* pos1 = SLTFind(plist, 2);
	printf("%p->%d\n", pos1, pos1->date);


	SLTNode* pos2 = SLTFind(plist, 3);
	SLTInsert(&plist, pos2, 30);
	SLTPrint(plist);

	SLTNode* pos3 = SLTFind(plist, 1);
	SLTInsert(&plist, pos3, 10);
	SLTPrint(plist);

	SLTNode* pos4 = SLTFind(plist, 10);
	SLTErase(&plist, pos4);
	SLTNode* pos5 = SLTFind(plist, 30);
	SLTErase(&plist, pos5);
	SLTPrint(plist);

	SLTDestory(&plist);
}
int main()
{
	//TestSlistNode1();
	TestSlistNode2();
	return 0;
}

2.SList.c

#include"SList.h"
SLTNode* BuySLTNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		printf("malloc faile");
		exit(-1);
	}
	newnode->date = x;
	newnode->next = NULL;
	return newnode;
}
void SLTPrint(SLTNode* phead)
{
	while (phead)
	{
		printf("%d->", phead->date);
		phead = phead->next;
	}
	printf("NULL\n");
}
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
	SLTNode* newnode = BuySLTNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
void SLTPushFront(SLTNode** pphead, SLTDateType x)
{
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead != NULL);
	SLTNode* tail = *pphead;
	SLTNode* prev = NULL;
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}
}
void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead != NULL);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}
SLTNode* SLTFind(SLTNode* phead,SLTDateType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->date == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}
void SLTInsert(SLTNode** pphead,SLTNode* pos, SLTDateType x)
{
	assert(pos != NULL);
	SLTNode* newnode = BuySLTNode(x);
	if (pos == *pphead)
	{
		newnode->next = *pphead;
		*pphead = newnode;

	}
	else
	{
		SLTNode* posprev = *pphead;
		while (posprev->next != pos)
		{
			posprev = posprev->next;
		}
		posprev->next = newnode;
		newnode->next = pos;
	}
	
}
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pos != NULL);
	assert(*pphead != NULL);
	if (pos == *pphead)
	{
		SLTNode* cur = (*pphead)->next;
		free(*pphead);
		*pphead = cur;
	}
	else
	{
		SLTNode* posprev = *pphead;
		while (posprev->next != pos)
		{
			posprev = posprev->next;
		}
		posprev->next = pos->next;
		free(pos);
	}
}
void SLTDestory(SLTNode** pphead)
{
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

3.SList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType date;
	struct SListNode* next;
}SLTNode;


void SLTPrint(SLTNode* phead);
void SLTPushBack(SLTNode** pphead, SLTDateType x);
void SLTPushFront(SLTNode** pphead, SLTDateType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
SLTNode* SLTFind(SLTNode* phead,SLTDateType x);
void SLTInsert(SLTNode** pphead, SLTNode* pos,SLTDateType x);
void SLTErase(SLTNode** pphead, SLTNode* pos);
void SLTDestory(SLTNode** pphead);
SLTNode* BuySLTNode(SLTDateType x);

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布