数据结构——单链表

目录

一、链表

二、单链表的实现

2.1 打印单链表的内容

2.2 开辟新的节点

2.3 单链表的尾插

2.4 单链表的头插

2.5 单链表的尾删

2.6 单链表的头删

2.7 单链表的查找

2.8 在指定位置之前插入数据

2.9 在指定位置之后插入数据

2.10 删除指定的节点

2.11 删除指定的节点之后节点

2.12.销毁单链表

三、完整代码

总结

---

前言

之前我们了解了数据结构中线性表的顺序表的知识，今天我们来了解线性表中链表的知识。

---

一、链表

void SListDesTroy(SLTNode** pphead) {
	assert(pphead);
	assert(*pphead);
 
	SLTNode* pucr = *pphead;
	while (pucr) {//循环销毁
		SLTNode* next = pucr->next;
		free(pucr);
		pucr =next;
	}
	*pphead = NULL;
 
}

由于每个节点都是我们动态开辟出来的，所以我们要进行依次的销毁

三、完整代码

Slist.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
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** pphead, SLTDataType x);
//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);

Slist.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Slist.h"
 
//打印单链表的内容
void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL");
}
 
//新的节点
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;
		return;
	}
	SLTNode* pucr = *pphead;
	while (pucr->next)
	{
		pucr = pucr->next;
	}
	pucr->next = newnode;
}
 
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
 
}
 
//尾删
void SLTPopBack(SLTNode** pphead) {
	assert(pphead);
	assert(*pphead);
	if ((*pphead)->next == NULL) {
		free(*pphead);
		*pphead = NULL;
		return;
	}
	SLTNode* ptail = *pphead;
	SLTNode* prev = NULL;
	while (ptail->next != NULL) {
		prev = ptail;
		ptail = ptail->next;
	}
	prev->next = NULL;
	free(ptail);
	ptail = NULL;
}
 
//头删
void SLTPopFront(SLTNode** pphead) {
	assert(pphead);
	assert(*pphead);
	SLTNode* ptail = *pphead;
	*pphead = ptail->next;
	free(ptail);
	ptail = NULL;
 
}
 
 
//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x) {
	assert(pphead);
	SLTNode* pucr =* pphead;
	while (pucr) {
		if (pucr->data == x) {
			return pucr;
		}
		pucr = pucr->next;
	}
	return NULL;
}
 
在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
	assert(pphead);
	assert(pos);
	assert(*pphead);
 
	SLTNode* newNode=SLTBuyNode(x);
	if (pos == *pphead) {
		SLTPushFront(pphead, x);
		return;
	}
	SLTNode* prev = *pphead;
	while(prev->next != pos){
		prev = prev->next;
	}
	prev->next = newNode;
	newNode->next = pos;
}
 
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
	assert(pos);
	SLTNode* newNode = SLTBuyNode(x);
	
	newNode->next = pos->next;
	pos->next = newNode;
}
 
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos) {
	assert(pphead);
	assert(pos);
	assert(*pphead);
	SLTNode* prev = *pphead;
	if (prev == pos) {
		SLTPopFront(pphead);
		return;
	}
	while (prev->next != pos) {
		prev = prev->next;
	}
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}
 
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {
	assert(pos);
	assert(pos->next);
 
	SLTNode* del = pos->next;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}
 
//销毁链表
void SListDesTroy(SLTNode** pphead) {
	assert(pphead);
	assert(*pphead);
 
	SLTNode* pucr = *pphead;
	while (pucr) {
		SLTNode* next = pucr->next;
		free(pucr);
		pucr =next;
	}
	*pphead = NULL;
 
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Slist.h"
 
void Slisttest1()
{
	SLTNode * pf =NULL;
	SLTPushBack(&pf, 1);
	SLTPushBack(&pf, 2);
	SLTPushBack(&pf, 3);
	SLTPushBack(&pf, 4);
	SLTPushFront(&pf, 5);
	SLTPushFront(&pf, 7);
	SLTPushFront(&pf, 6);
	SLTPushFront(&pf, 8);
	//SLTPopFront(&pf);
	SLTNode *p=SLTFind(&pf,8);
	//在指定位置前后插入数据
	//SLTInsert(&pf, p, 0);
	//SLTInsertAfter(p, 5);
 
	//SLTErase(&pf, p);
	//SLTEraseAfter(p);
 
	SListDesTroy(&pf);
	
	SLTPrint(pf);
}
 
 
int main() {
	Slisttest1();
	return 0;
}
 

---

总结

上述文章我们讲了单链表的实现，希望对你有所帮助。