【单链表】无头单项不循环（1）-阿里云开发者社区

【单链表】无头单项不循环（1）

2023-11-17 590

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【单链表】无头单项不循环（1）

本篇开始链表学习。今天主要是单链表&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】