本篇开始链表学习。今天主要是单链表&OJ题目。
单链表
前面的博文我们讲了顺序表。顺序表的优势就是【物理空间的连续】，就只需要一个指针指向开始位置，用数组下标去访问即可。但是这也是它的劣势。当插入和删除数据需要挪动数据。
无论是【顺序表】还是【链表】里的数据，任何类型都可。所以用typedef。
在开始阶段，线性表可能是物理空间上连续【顺序表】，可能是逻辑顺序上连续【链表】。链表的优势就是，删除和插入数据不需要挪动，空间可以一块一块的释放，不会影响其他节点。链表每个节点都是独立的。
【链表】的种类很多，今天先介绍【无头单项不循环链表】----【单链表】。
主函数test.c
#include"SList.h"
int main() { SLNode* phead = NULL;//结构体指针变量存放结构体的地址 头节点 test1(&phead);//测试尾插 test2(&phead);//测试头插 test3(&phead);//测试尾删 test4(&phead);//测试头删 return 0; }
test1
void test1(SLNode** pphead)//测试尾插 { SLPushBack(pphead, 10); SLPushBack(pphead, 20); SLPushBack(pphead, 30); SLPushBack(pphead, 40); SLPrint(*pphead); }
test2
void test2(SLNode** pphead)//测试头插 { SLPushFront(pphead, 77); SLPushFront(pphead, 66); SLPushFront(pphead, 55); SLPushFront(pphead, 33); SLPrint(*pphead); }
test3
void test3(SLNode** pphead)//测试头删 { SLPopFront(pphead); SLPopFront(pphead); SLPopFront(pphead); SLPrint(*pphead); }
test4
void test4(SLNode** pphead)//测试尾删 { SLPopBack(pphead); SLPopBack(pphead); SLPrint(*pphead); }
头文件&函数声明SList.h
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h>
- 创建单链表
//创建单链表 typedef int SLNDataType;//单链表节点数据类型 typedef struct SListNode//创建节点 { SLNDataType val; struct SListNode* next; }SLNode;
？为什么 SListNode 还未创建好，就可以在结构体内部使用这个 SListNode 了
因为next是一个结构体指针变量，主体是指针变量，无影响。但是如果是 struct SListNode next;不可以，结构体嵌套结构体是不可以的。
- 打印数据
//打印数据 void SLPrint(SLNode* phead);
- 尾插
1. //尾插 2. void SLPushBack(SLNode** pphead, SLNDataType x);
- 头插
1. //头插 2. void SLPushFront(SLNode** pphead, SLNDataType x);
- 头删
1. //头删 2. void SLPopFront(SLNode** pphead);
- 尾删
1. //尾删 2. void SLPopBack(SLNode** pphead);
函数实现SList.c
#include"SList.h"
打印SLPrint
- 不要让phead移动
void SLPrint(SLNode* phead) { assert(phead); SLNode* tail = phead; printf("phead->"); while (tail->next != NULL) { printf("%d->", tail->val); tail = tail->next; } printf("NULL"); printf("\n"); }
创建节点CreateNode
//创建链表的节点---结构体 SLNode* CreateNode(SLNDataType x) { SLNode* newnode = (SLNode*)malloc(sizeof(SLNode)); if (newnode == NULL) { perror("malloc"); exit(-1);//直接终止程序 //return; } newnode->val = x; newnode->next = NULL; return newnode; }
尾插SLPushBack
- 二级指针的使用，不然就会链接不起来，出了函数栈帧局部变量就销毁了。
- 改变外部的变量，一定有一个解引用的操作
- 多情况的考虑
//尾插 void SLPushBack(SLNode** pphead, SLNDataType x) { //assert(*pphead); SLNode* newnode = CreateNode(x); //无节点 if (*pphead == NULL) { *pphead = newnode; } //多个节点 else { SLNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } }
头插SLPushFront
- 代码书写的先后顺序
- 二级指针
//头插 void SLPushFront(SLNode** pphead, SLNDataType x) { //assert(*pphead); SLNode* newnode = CreateNode(x); newnode->next = *pphead; *pphead = newnode; }
头删SLPopBck
- 代码书写的先后顺序
- 二级指针
//头删 void SLPopFront(SLNode** pphead) { assert(*pphead); SLNode* tail = *pphead; *pphead = (*pphead)->next; free(tail); tail = NULL; }
尾删SLPopFront
- 多种情况的考虑
//尾删 void SLPopBack(SLNode** pphead) { assert(*pphead); //一个节点 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLNode* tail = *pphead; SLNode* prve = tail; while (tail->next != NULL) { prve = tail; tail = tail->next; } prve->next = NULL; free(tail); tail = NULL; } }
易错点
- 断言❌
- 无节点/一个节点/多节点的考虑❌
- 传值调用/传址调用（二级指针使用）❌
- 记住：要修改头节点（头节点是结构体指针变量的指向必须用二级指针❌
- 空间的释放（不是释放指针变量，释放的是指针指向的空间）❌
- *pphead&*pphead->next辨析❌
- 野指针的诞生❌
代码---------→【唐棣棣 (TSQXG) - Gitee.com】
联系---------→【邮箱：2784139418@qq.com】
