考研数据结构单链表的增删改查看这一篇就够了

目录

一. 单链表的特点

1.1 解引用拓展 🤖

二. 单链表的操作

2.1不带头节点的操作

2.1.1 打印 

2.1.1.1 创建结点

2.1.2 尾插（需要二级指针）

注意形参的值不改变实参：（精髓部分）

2.1.3 头插

2.1.4 尾删

2.1.5 头删

2.1.6 在pos前插入

2.1.7 删除pos位置 

---

一. 单链表的特点

单链表的结点是随机的不是逻辑上相邻即物理上相邻的。用指针指向下一个节点的地址。

1.1 解引用拓展 🤖

解引用有两种，* ->

*p的意思是：是取p所指向内存的值，取多少大小的值，取决于结构体前的数据类型，如int                         取四个字节，char取一个字节。

p->的意思是： 结构体用->,取决于->后面是什么值，如果是->val则取data域的值，->next则                       取下个结点的地址。相当于（*p）.next

 

二. 单链表的操作

单链表分为带头结点和不带头结点 ☆*: .｡. o(≧▽≦)o .｡.:*☆

2.1不带头节点的操作

2.1.1 打印 

打印不用二级指针的原因是：打印不用改变外部结构体指针，只用遍历打印就好了，当要改变结构体指针就要用二级指针。

void SLTPrint(SLNode* phead)
{SLNode* cur = phead;while (cur != NULL){printf("%d->", cur->val);cur = cur->next;}printf("NULL\n");
}

2.1.1.1 创建结点

SLNode* CreateNode(SLNDataType x)
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->val = x;newnode->next = NULL;return newnode;
}

2.1.2 尾插（需要二级指针）

void SLTPushBack(SLNode** pphead, SLNDataType x)
{SLNode* newnode = CreateNode(x);if (*pphead == NULL){*pphead = newnode;}else{// 找尾SLNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

 

注意形参的值不改变实参：（精髓部分）

接下来是很多人都迷迷糊糊搞不懂的地方。

当前函数定义的可以直接修改，不是当前当前函数定义的，无论是外部函数，还是malloc出来的空间，访问时都要用指针去通过地址修改。全局变量可以直接修改。

形参不不能改变实参的，要传实参的地址才能改变形参。

想用形参pphead改变外部指针phead（实参） ，先将实参的地址&plist，传给实参pphead，这时pphead代表的是plist地址（&plist），*pphead解引用所以*pphead代表是plist，这里是要改变SNode*，所以要node**。这里是要修改结构体的指针plist，所以是需要结构体指针的地址&plist传给*pphead。

如果要改变外部定义的结构指针SLNode*，要用二级指针SLNode**。

如果要改变外部定义的结构体Node，就要一级指针Node*。

2.1.3 头插

void SLTPushFront(SLNode** pphead, SLNDataType x)
{SLNode* newnode = CreateNode(x);newnode->next = *pphead;*pphead = newnode;
}

2.1.4 尾删

删后n-1个不需要二级指针，直接free（）；

但是只有一个空间的时候，删掉，plist就成了没有指向空间的野指针，所以需要将plist置空，需要改变结构体指针。 

 

void SLTPopBack(SLNode** pphead)
{// 温柔的检查//if (*pphead == NULL)//	return;// 空assert(*pphead);// 1、一个节点// 2、一个以上节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{// 找尾/*SLNode* prev = NULL;SLNode* tail = *pphead;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;*/SLNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}
}

 

2.1.5 头删

void SLPopFront(SLNode** pphead) {assert(pphead);if ((*pphead)== NULL) {free(*pphead);*pphead= NULL;}else {/**pphead = (*pphead)->next;free(*pphead);*/SLNode* tmp = *pphead;*pphead = (*pphead)->next;free(tmp);}}

 

2.1.6 在pos前插入

2.1.7 删除pos位置 

不带头结点的完整代码 

//头文件SList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>typedef int SLDataType;
typedef struct SListNode {SLDataType val;struct SListNode* next;}SLNode;
void SLPrint(SLNode* phead);
void SLPushBack(SLNode** pphead, SLDataType x);
void SLPopBack(SLNode** pphead);
void SLPushFront(SLNode** pphead, SLDataType x);
void SLPopFront(SLNode** pphead);//SList.c
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include"SList.h"
#include<assert.h>
//打印
void SLPrint(SLNode* phead) {assert(phead);while (phead!= NULL) {printf("%d->", phead->val);phead = phead->next;}printf("NULL\n");
}
//创建新节点SLNode* CreateNode(SLDataType x) {SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));while (newnode == NULL) {perror("malloc fail");exit(-1);}newnode->val = x;newnode->next = NULL;return newnode;}//尾插
void SLPushBack(SLNode** pphead, SLDataType x) {SLNode* newnode = CreateNode(x);		//调用函数,实参没有数据类型if (*pphead == NULL) {*pphead = newnode;}else {SLNode* tail = *pphead;while (tail->next != NULL) {tail = tail->next;}newnode->next = NULL;tail->next = newnode;}}
//尾删
void SLPopBack(SLNode** pphead) {assert(*pphead);if ((*pphead)->next == NULL) {free(*pphead);*pphead = NULL;}else {SLNode* pre = NULL;SLNode* tail = *pphead;while (tail->next != NULL) {pre = tail;tail = tail->next;}free(tail);tail = NULL;pre->next = NULL;}}
//头插
void SLPushFront(SLNode** pphead, SLDataType x) {SLNode* newnode = CreateNode(x);/*if (*pphead == NULL) {*pphead = newnode;}*/    //可以不要newnode->next = *pphead;*pphead= newnode;
}
//头删
void SLPopFront(SLNode** pphead) {assert(pphead);if ((*pphead)== NULL) {free(*pphead);*pphead= NULL;}else {/**pphead = (*pphead)->next;free(*pphead);*/SLNode* tmp = *pphead;*pphead = (*pphead)->next;free(tmp);}}//Test.c 文件
#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"void Test1() {SLNode* splist=NULL;SLPushBack(&splist, 1);SLPushBack(&splist, 2);SLPushBack(&splist, 3);SLPushBack(&splist, 4);SLPrint(splist);SLPopBack(&splist);SLPopBack(&splist);SLPrint(splist);SLPushFront(&splist, 1);SLPushFront(&splist, 2);SLPushFront(&splist, 3);SLPushFront(&splist, 4);SLPrint(splist);SLPopFront(&splist);SLPopFront(&splist);SLPrint(splist);
}
int main() {Test1();return 0;}