单链表知识点

亦凉 2023-10-12 13:43 43阅读 0赞

**目录**

1.1 链表的概念以及结构

1.2 链表的分类

1.3 链表的实现

--------------------

你不会的东西，觉得难得东西，一定不要躲，先搞明白后精湛。

--------------------

### 1.1 链表的概念以及结构 ###

链表是一种 **物理存储结构上非连续** 、非顺序的存储结构，数据元素的 **逻辑顺序** 是通过链表中的 **指针链** **接** 次序实现的 .（地址不一定连续）

### 1.2 链表的分类 ###

（1）**单向或者双向**

（2）**带头或者不带头**

（3）**循环或者非循环**

### 1.3 链表的实现 ###

单向，无头，不循环

SList.h

#pragma once
    #include <stdio.h>
    #include <assert.h>
    #include <stdlib.h>
    #include <string.h>
    
    
    typedef int SLTDateType;
    
    //单链表中，定义一个结构体，结构体里面有两个结构体成员，一个是数据，一个是指针(指针指向一个结构体)，
    // 这个指针的类型是一个结构体,这个结构体又和自己类型一样，所以结构体有的自引用
    typedef struct SListNode
    {
    	SLTDateType date;//数据
    	struct SListNode* next;//储存下一个节点的地址
    }SListNode;
    //知识点结构体的自引用方式
    
    //单链表不需要初始化，因为单链表刚开始只有一个指针
    void SListPrint(SListNode* phead);//打印
    //尾插
    void SListPushBack(SListNode** pphead, SLTDateType x);
    //头插
    void SListPushFront(SListNode** pphead, SLTDateType x);
    //尾删
    void SListPopBack(SListNode** pphead);//需要传递的是头部结构体的地址的地址，当尾删的时候，如果单链表就有一个值，那么进行尾删的时候，需要改变头部结构体地址
    //头删
    void SListPopFront(SListNode** pphead);
    //查找
    SListNode* SListFind(SListNode* phead, SLTDateType x);
    //前插入
    void SListInsert(SListNode** pphead, SListNode* pos, SLTDateType x);
    //后插入
    void SListInsertAfter(SListNode* pos, SLTDateType x);
    //删除
    void SListErase(SListNode** pphead, SListNode* pos);
    //删除后面
    void SListEraseAfter(SListNode** pphead);
    //销毁
    void SListDestory(SListNode** pphead);

SList.c

#define _CRT_SECURE_NO_WARNINGS 1
    #include "SList.h"
    
    
    //打印
    void SListPrint(SListNode* phead)
    {
    	//assert(phead);//这里不需要断言，因为单链表可能是空链表
    	SListNode* cur = phead;
    	while (cur != NULL)
    	{
    		printf("%d->", cur->date);
    		cur = cur->next;
    	}
    	printf("NULL\n");
    }
    
    //一个节点的创建
    SListNode* BuySListNode(SLTDateType x)
    {
    	SListNode* newnode = (SListNode*)malloc(sizeof(SLTDateType));
    	if (newnode == NULL)
    	{
    		printf("malloc fail\n");
    		exit(-1);
    	}
    	else
    	{
    		newnode->date = x;
    		newnode->next = NULL;
    	}
    	return newnode;
    }
    
    //尾插
    void SListPushBack(SListNode** pphead, SLTDateType x)//当链表是空的时候，尾插，相当于头插，需要改变头部的地址，改变地址，需要传递头部地址的地址【形参的改变不影响实参】
    //需要改变谁，就需要传谁的地址
    {
    	assert(pphead);
    	SListNode* newnode = BuySListNode(x);
    	if (*pphead == NULL)
    	{
    		*pphead = newnode;
    	}
    	else
    	{
    		SListNode* tail = *pphead;
    		while (tail->next != NULL)
    		{
    			tail = tail->next;
    		}
    		tail->next = newnode;
    	}
    }
    //头插//改变头部地址就需要传二级指针
    void SListPushFront(SListNode** pphead, SLTDateType x)
    {
    	assert(pphead);
    	SListNode* newnode = BuySListNode(x);
    	newnode->next = *pphead;
    	*pphead = newnode;
    }
    
    
    //尾删//要把倒数第二个值的next变成NULL，所以需要倒数第二个结构体的地址，才能改变(形参的改变，不改变实参)【每一个结构体，相当于结构体传参】
    //没有节点，一个节点，许多节点
    void SListPopBack(SListNode** pphead)
    {
    	assert(pphead);
    	if (*pphead == NULL)//空
    	{
    		return;
    	}
    	else if ((*pphead)->next == NULL)
    	{
    		free(*pphead);
    		*pphead = NULL;
    	}
    	else
    	{
    		SListNode* prev = NULL;
    		SListNode* tail = *pphead;
    		while (tail->next != NULL)
    		{
    			prev = tail;//倒数第二个
    			tail = tail->next;//倒数第一个
    		}
    		free(tail);
    		tail = NULL;
    		prev->next = NULL;
    	}
    }
    //头删
    void SListPopFront(SListNode** pphead)
    {
    	assert(pphead);
    	if (*pphead == NULL)
    	{
    		return;
    	}
    	else//一个值和很多值
    	{
    		SListNode* front = NULL;
    		front = (*pphead)->next;
    		free(*pphead);
    		*pphead = front;
    	}
    }
    
    //查找
    SListNode* SListFind(SListNode* phead, SLTDateType x)
    {
    	SListNode* cur = phead;
    	while (cur != NULL)
    	{
    		if (cur->date == x)
    		{
    			return cur;
    		}
    		cur = cur->next;
    	}
    	return NULL;
    }
    
    //插入,在某个数字前插入//首先用find找某个数的地址，然后再在地址处插入。,
    void SListInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
    {
    	assert(pphead);
    	assert(pos);
    	if (*pphead == pos)
    	{
    		SListPushFront(pphead, x);
    	}
    	else
    	{
    		SListNode* prev = *pphead;
    		while (prev->next != pos)
    		{
    			prev = prev->next;
    		}
    		SListNode* newnode = BuySListNode(x);
    		prev->next = newnode;
    		newnode->next = pos;
    	}
    }
    //在insert之后插入
    void SListInsertAfter(SListNode* pos, SLTDateType x)
    {
    	assert(pos);
    	SListNode* next = pos->next;
    	SListNode* newnode = BuySListNode(x);
    	pos->next = newnode;
    	newnode->next = next;
    }
    
    //删除
    void SListErase(SListNode** pphead, SListNode* pos)
    {
    	assert(pphead);
    	assert(pos);
    	if (*pphead == pos)
    	{
    		SListPopFront(pphead);
    	}
    	else
    	{
    		SListNode* prev = *pphead;
    		while (prev->next != pos)
    		{
    			prev = prev->next;
    		}
    		prev->next = pos->next;
    		pos = NULL;
    		free(pos);
    	}
    }
    
    //删除后面
    void SListEraseAfter(SListNode* pos)
    {
    	assert(pos);
    	if (pos->next == NULL)
    	{
    		return;
    	}
    	else
    	{
    		SListNode* next = pos->next;
    		pos->next = next->next;
    		free(next);
    		next = NULL;
    	}
    }
    
    //销毁
    void SListDestory(SListNode** pphead)
    {
    	assert(pphead);
    	SListNode* cur = *pphead;
    	SListNode* next = NULL;
    	while (cur->next != NULL)
    	{
    		next = cur->next;
    		free(cur);
    		cur = NULL;
    	}
    	*pphead = NULL;
    }

> 单链表，刚开始定义的是结构体的指针，不需要结构体初始化；但是顺序表刚开始定义的是结构体，需要结构体初始化。（顺序表初始化的时候，值是空的，但是容量以及大小都是有的）（单链表，没有值的时候，结构体指针（头部地址）是NULL）