首页 > 其他分享 >单链表

单链表

时间：2024-07-18 14:42:32浏览次数：9  
标签：Pre Node 单链 void nullptr Next 节点

单链表

结构描述

#include <iostream>
#include <cstdlib>

using namespace std;

typedef int DataType;

//链表节点
typedef struct Node {
    DataType A;
    struct Node * Next;
}Node;

class SingleLinkedList {
private:
    Node * Head;
public:
    //尾插
    void PushBack(DataType X);
    //头插
    void PushFront(DataType X);
    //在第Pos个位置插入，若不存在该位置报错
    void InsertThisPos(int Pos, DataType X);

    //尾删
    void PopBack();
    //头删
    void PopFront();
    //删除第Pos位元素，若无该位置，则返回错误
    void DeleteThisPos(int Pos);
    // 把链表置为空表
    void MakeEmpty();
    
    //查找值为 Target的元素，若不存在，则返回空指针，存在则返回节点指针
    Node * SearchByValue(DataType Target);
    void ModifyByValue(DataType Value, DataType NewValue);

    //创建一个空表
    void Init();
    //判空，若空，则返回true，反之返回false
    bool IsEmpty();
    //打印链表
    void Print();
    //分配空间，根据参数X分配空间，分配成功则返回该节点的指针
    Node * BuyNode(DataType X);
};

初始化

建立一个空表，即把 Head 指向空。

void SingleLinkedList::Init() {
    Head = nullptr;
}

判空

判断链表是否为空，即 Head == nullptr 是否成立。

  • 若成立则返回 true

  • 否则返回 false

bool SingleLinkedList::IsEmpty() {
    return Head == nullptr;
}

打印

  • 表空：返回错误

  • 非空：从头指针向后遍历，一直遍历到表尾，即Cur == nullptr 时，并打印数据域。

void SingleLinkedList::Print() {
    //表空时返回错误
    if (IsEmpty()) {
        cout << "List Is Empty!\n";
        exit(-1);
    }
    //表非空时遍历链表，并打印每一位元素的值
    Node * Cur = Head;
    while (Cur != nullptr) {
        cout << Cur->A << "\n";
        Cur = Cur->Next;
    }
}

创建节点

根据参数 X ，创建一个数据域为 X ，指针域为空的节点 NewNode 并返回

Node * SingleLinkedList::BuyNode(DataType X) {
    //分配空间，并判断是否成功
    Node * NewNode = (Node *)malloc(sizeof (Node));
    if (NewNode == nullptr) {
        cout << "Malloc Failed!" << "\n";
        exit(-1);
    }
    
    //给节点赋值
    NewNode->A = X;
    NewNode->Next = nullptr;
    
    return NewNode;
}

头插

  1. 分配节点 NewNode；
  2. 把节点的指针域指向当前头节点，即 NewNode->Next = Head;
  3. 把头指针 Head 指向 NewNode
void SingleLinkedList::PushFront(DataType X) {
    Node * NewNode = BuyNode(X);
    NewNode->Next = Head;
    Head = NewNode;
}

尾插

  • 若表空：
    1. 分配节点；
    2. 把头指针指向该节点；
  • 表非空：
    1. 遍历，找到尾节点
    2. 分配节点，并把节点接在尾节点之后
void SingleLinkedList::PushBack(DataType X) {
    //表空
    if (IsEmpty()) {
        Head = BuyNode(X);
    }
    //非空
    else {
        Node * Cur = Head;
        //Cur->Next为空时，找到尾节点，退出循环
        while (Cur->Next != nullptr) {
            Cur = Cur->Next;
        }
        
        Node * NewNode = BuyNode(X);
        Cur->Next = NewNode;
    }
}

头删

  • 表空：报错
  • 非空：
    1. 用临时变量 Tmp 存放头节点;
    2. 把头节点向后移动一位，即 Head = Head->Next;
    3. 释放 Tmp 并置空，防止指针悬空
void SingleLinkedList::PopFront() {
    //表空
    if (IsEmpty()) {
        cout << "List Is Empty!\n";
        exit(-1);
    }
    
    //非空
    Node * Tmp = Head;
    Head = Head->Next;
    free(Tmp);
    Tmp = nullptr;
}

尾删

  • 表空：报错
  • 非空：
    • 只有一个节点：直接置空即可
    • 有多个节点：
      1. 找到倒数第二个节点 Cur；
      2. 用临时变量保存尾节点，即 Tmp = Cur->Next；
      3. 把 Cur 的指针域指向 nullptr
      4. 释放 Tmp
void SingleLinkedList::PopBack() {
    //表为空
    if (IsEmpty()) {
		cout << "List Is Empty!\n";
        exit(-1);
    }
    
    //只有一个节点
    if (Head->Next == nullptr) {
        free(Head);
        Head = nullptr;
    }
    //有两个及以上个节点
    else {
        Node * Cur = Head;
        //找倒数第二个节点
        while (Cur->Next->Next != nullptr) {
            Cur = Cur->Next;
        }
        //保存倒数第一个节点
        Node * Tmp = Cur->Next;
        //把倒数第二个节点指向空指针，Tmp指向尾节点，故其指针域为空指针
        Cur->Next = Tmp->Next;
        //释放
        free(Tmp);
        Tmp = nullptr;
    }
}

插入元素

在 Pos 处插入元素（模拟数组下标，从0开始计数）

  • 若存在该位置，则插入元素
    1. 若 Pos 为0，即在链表头插入，直接调用头插方法
    2. 若 Pos 大于0，则遍历链表，循环变量 i 从 1 开始，考虑下标为 1 到尾的节点
    3. 用 Pre 变量存放 第 i - 1 号位的节点指针，循环条件为 i < Pos && Pre != nullptr，如果 Pre 为空，即指向了链表的最后，若此时 i != Pos ，则下存在，返回错误
    4. 若 i == Pos，则该位置存在，直接分配节点并插入即可 。有点双指针的意思
  • 不存在该位置，则返回错误；
void SingleLinkedList::InsertThisPos(int Pos, DataType X) {
    if (Pos == 0) {
        PushFront(X);
    }
	else {
        int i;
        Node * Pre;
        for (i = 1, Pre = Head; i < Pos && Pre != nullptr; i++, Pre = Pre->Next) {
            ;
        }
        //退出循环时，不是i == Pos, 就是 Pre == nullptr
        if (Pos == i && Pre != nullptr) {
            Node * NewNode = BuyNode(X);
            NewNode->Next = Pre->Next;
            Pre->Next = NewNode;
        }
        else {
            cout << Pos << " Posiont is not exist!\n";
            exit(-1);
        }
    }
}

删除元素

  • 表空：报错
  • 非空：
    • 删除第0个元素时，直接调用头删方法
    • 有多个元素时：
      1. 和插入一样，用一个 Pre 指针指向要删除元素的前一位，即 Pre = Head, i = 1
      2. 遍历链表，直至 i == Pos || Pre->Next == nullptr 时退出循环，Pre->Next == nullptr时，说明要删除的元素是尾指针的指针域，即空指针，这显然是错误的，所以可以以此来作为遍历的出口条件
      3. 若第 Pos 个元素存在，则删除该元素
void SingleLinkedList::DeleteThisPos(int Pos) {
    //判空
    if (IsEmpty()) {
        cout << "List Is Empty!\n";
    	exit(-1);
    }
    
    //非空，删除第0个元素
    if (Pos == 0) {
        PopFront();
    }
    else {
        //非空，删除第N个元素（N > 0）
        int i = 0;
        Node * Pre = nullptr;
        for (i = 1, Pre = Head; Pre->Next != nullptr && i < Pos; i++, Pre = Pre->Next) {
            ;
        }
        
        if (i == Pos && Pre->Next != nullptr) {
            Node * Tmp = Pre->Next;
            Pre->Next = Tmp->Next;
            free(Tmp);
            Tmp = nullptr;
        }
        else {
            cout << Pos << " Position is not exist!\n";
        }
    }
    
}

根据值查找元素

  • 表空：返回错误
  • 非空：遍历链表，逐一比较，直到第一个与目标值相等的元素时，返回该节点的指针。若直至表尾仍未发现该元素，则返回一个空指针。
Node * SingleLinkedList::SearchByValue(DataType Target) {
    if (IsEmpty()) {
        cout << "List Is Empty!\n";
        exit(-1);
    }
    
    Node * Cur = Head;
    while (Cur != nullptr) {
        if (Cur->A == Target) {
            return Cur;
        }
        Cur = Cur->Next;
    }
    
    return nullptr;
}

修改链表元素值

  • 查找：
    • 表空：返回错误
    • 非空：找到返回，找不到返回空
  • 修改：根据查找到的结果修改；
    • 查找返回空：给出提示消息，并退出程序
    • 查找返回元素节点指针：修改该元素的值
void SingleLinkedList::ModifyByValue(DataType Target, DataType NewValue) {
    Node * Ret = SearchByValue(Target);
    if (Ret == nullptr) {
        cout << "The Target Is Not Exist!\n";
        exit(-1);
    }
    
    Ret->A = NewValue;
}

摧毁

  • 表空：返回错误
  • 不空：一直头删，直至表空
void SingleLinkedList::MakeEmpty() {
    if (IsEmpty()) {
        cout << "List Is Empty!\n";
        exit(-1);
    }
    
    while (!IsEmpty()) {
        PopFront();
    }
}

标签：Pre,Node,单链,void,nullptr,Next,节点
From： https://www.cnblogs.com/codels/p/18309480

相关文章

  • 重生之“我打数据结构，真的假的？”--2.单链表
    1.单链表介绍（不带头节点）1.1.链表的概念概念：链表是一种物理存储结构上非连续、非顺序的存储结构，但链表在逻辑上是连续的，顺序的，而数据元素的逻辑顺序是通过链表中的指针连接次序实现的。1.2.链表的结构typedefstructSListnode{ datatypedata; structSListnode*next;......
  • 单链表算法 - 链表的中间节点
    .-力扣（LeetCode）.-备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界IT名企DreamOffer。https://leetcode.cn/problems/middle-of-the-linked-list/description/思路1: 思路2:代码:/***Definitionforsingly-linkedlist.*struct......
  • 数据结构（单链表（1））
    前言线性表中有着许多的结构，如顺序表和链表。而单链表则是链表的最基础的一种形式，下面就让我们对其做一个了解。概念概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。结构我们可以将单链表的结构想象成火车的......
  • 单链表详解（1）
    一、顺序表的弊端1.往顺序表中间插入元素时时间要移动顺序表的一部分，当顺序表足够大时，这时时间复杂度会时O(n),运行效率会降低；2.顺序表在空间不够时增容用到realloc函数，这个函数需要拷贝原数据，申请新空间，释放旧空间，这也降低了运行效率；3.顺序表增容后可能存在空间浪费的问题......
  • 线性表——单链表
    #include<bits/stdc++.h>usingnamespacestd;typedefstructLNode{ intdata; structLNode*next;}LNode,*List;//初始化voidInitList(List&L){ L=(LNode*)malloc(sizeof(LNode)); L->next=NULL;}//头插voidListInsertHead(List&L,inte)......
  • 【数据结构】—— 单链表(single linked list)
    文章目录1、单链表的定义优点和缺点单链表的构成2、单链表的创建初始化：3、单链表的接口实现打印尾插头插尾删头删查找在指定位置之前插入在指定位置之后插入删除指定位置的节点删除指定位置之后的节点销毁链表4、源代码1、单链表的定义单链表（SinglyLinkedList......
  • 单链表在Python中的实现技巧详解
    概要链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个数据域和一个指向下一个节点的指针。链表的优点是插入和删除操作非常高效，特别是在需要频繁修改数据结构的情况下。本文将详细介绍如何在Python中创建单链表，并包含相应的示例代码，帮助全面掌握这一基础而重要......
  • 【LeetCode 0024】【链表】交换单链表相邻两个节点
    SwapNodesinPairsGivena linkedlist,swapeverytwoadjacentnodesandreturnitshead.Youmustsolvetheproblemwithout modifyingthevaluesinthelist’snodes(i.e.,onlynodesthemselvesmaybechanged.)Example1:**Input:**head=[1,2,3......
  • 【LeetCode 0141】【链表】【双指针之快慢指针】判断给定单链表是否存在环
    LinkedListCycleGivenhead,theheadofalinkedlist,determineifthelinkedlisthasacycleinit.Thereisacycleinalinkedlistifthereissomenodeinthelistthatcanbereachedagainbycontinuouslyfollowingthe next pointer.Internal......
  • 数据结构——单链表
    1、结构体typedefstructNode{ intdata;//数据域 structNode*next;//后继指针}Node,*List; 注意：单链表最后一个节点的next域未NULL2、头插（重点）//头插,考试重点boolInsert_head(Listplist,intval){ assert(plist!=NULL); if(plist==NULL) retur......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99