数据结构之链表

云惠网小编 2021年11月24日03:18:42
评论
7009字阅读23分21秒
摘要

1.单链表的基本概念和性质:1.1:单链表概念:链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) +指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。以“结点的序列”表示线性表称作线性链表(单链表),单链表是链式存取的结构。1.2单链表的存储方法:链接方式存储的线性表简称为链表(Linked List)。链表的具体存储表示为:① 用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的,也可以是不连续的.

广告也精彩

2.单链表的基本概念和性质:

void SLTNodePrint(SLTNode* head)
{
SLTNode* probe = head;
while (cur)//不为空则继续遍历
{
cout << probe->val << "->";//打应其数据
probe =probe->next;
}
cout << "nullptr" << endl;
}

单链表pos位置删除:

SList.h

1.首先判断链表是不是空链表,如果是那么就return;

2.如果不为空那么我们定义一个指针变量记录头节点的下一个节点,在让下一个节点做新的头,在释放原来的头节点

单链表头删

实现思路

代码实现:

实现思路:


单链表的销毁:

对应代码实现:

单链表的头部插入:

实现思路:

单链表增删查改时间复杂度分析:

增:

链表是通过记录头部地址来进行寻找后面数值的,所以需要遍历链表操作,如果在头部增,只需要查找一次,时间复杂度是 O(1),在尾部增需要查找n次,时间复杂度是 O(n).

删:

要遍历找到想要删除的数值,进行删除,对于链表,我们没法使用二分查找,只能遍历查找,找到该节点后删除,平均查找次数是n/2,时间复杂度是 O(n).

查:

要遍历查找,同样只能遍历查找,平均查找次数是n/2,时间复杂度是 O(n).

改:

要遍历找到想要更改的数值,同样只能遍历查找,平均查找次数是n/2,时间复杂度是 O(n).
 

1.找到目标结点之前位置

2.提前保存目标结点后位置

3.销毁目标结点

4.链接原目标结点之前的位置与原目标结点之后的位置

对应代码:

SLTNode* CreateSLTNode(SLTDataType x)
{
SLTNode* newnode = new SLTNode(x);
newnode->next = nullptr;
newnode->val = x;
return newnode;
}

单链表

单链表的销毁:

3.单链表的遍历:

SLTNode* CreateSLTNode(SLTDataType x)//创建节点
{
SLTNode* newnode = new SLTNode(x);
newnode->next = nullptr;
newnode->val = x;
return newnode;
}
void SLTNodePushBack(SLTNode*&phead,SLTDataType x)
{
SLTNode* newnode = CreateSLTNode(x);
if (phead == nullptr) {//如果一个节点也没有则此时我们需要创建节点
phead = newnode;
return;
}
SLTNode* tail = phead;
while (tail->next)//找尾
{
tail = tail->next;
}
tail->next = newnode;//链接
}

单链表的查找:

如果觉得写的不错的话可以点个赞,如果有错误的话请在评论区留言谢谢!!!! 

typedef int SLTDataType;
struct SLTNode
{
SLTNode(SLTDataType x)
:next(nullptr),val(x)
{}
SLTNode* next;
SLTDataType val;
};

2.单链表的基本概念和性质:

 单链表的尾部插入

1.单链表中结点的定义

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
typedef int SLTDataType;
struct SLTNode
{
SLTNode(SLTDataType x)
:next(nullptr),val(x)
{}
SLTNode* next;
SLTDataType val;
};
void SLTNodePrint(SLTNode* phead);
void SLTNodePushBack(SLTNode*& phead,SLTDataType x);
void SLTNodePopBack(SLTNode*& phead);
void SLTNodePopFront(SLTNode*& phead);
void SLTNodePushFront(SLTNode*& phead,SLTDataType x);
SLTNode* SLTNodeFind(SLTNode* phead, SLTNode* pos);
void SLTNodeErase(SLTNode*& phead, SLTNode* pos);
void SListDestory(SLTNode*&phead);
void SLTNodeInsert(SLTNode* pos, SLTDataType x);
void SLTNodeEraseAfter(SLTNode* pos);

1.链表的分类:

void SLTNodePopBack(SLTNode*& phead)
{
if (phead == nullptr) {
return;
}
else if (phead->next == nullptr) {
free(phead);
phead = nullptr;
}
else{
SLTNode* prve = nullptr;
SLTNode* tail = phead;
while (tail->next)
{
prve = tail;
tail = tail->next;
}
prve->next = tail->next;
free(tail);
tail = nullptr;
}
}

 2.单链表的创建:

SList.cpp

链表的创建和遍历

#include"SList.h"
SLTNode* CreateSLTNode(SLTDataType x)
{
SLTNode* newnode = new SLTNode(x);
newnode->next = nullptr;
newnode->val = x;
return newnode;
}
void SLTNodePrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur)
{
cout << cur->val << "->";
cur = cur->next;
}
cout << "nullptr" << endl;
}
void SLTNodePushBack(SLTNode*&phead,SLTDataType x)
{
SLTNode* newnode = CreateSLTNode(x);
if (phead == nullptr) {
phead = newnode;
return;
}
SLTNode* tail = phead;
while (tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}
void SLTNodePopBack(SLTNode*& phead)
{
if (phead == nullptr) {
return;
}
else if (phead->next == nullptr) {
free(phead);
phead = nullptr;
}
else{
SLTNode* prve = nullptr;
SLTNode* tail = phead;
while (tail->next)
{
prve = tail;
tail = tail->next;
}
prve->next = tail->next;
free(tail);
tail = nullptr;
}
}
void SLTNodePopFront(SLTNode*& phead)
{
if (phead == nullptr) {
return;
}
else
{
SLTNode* next = phead->next;
free(phead);
phead = next;
}
}
void SLTNodePushFront(SLTNode*& phead,SLTDataType x)
{
SLTNode* newnode = CreateSLTNode(x);
if (phead == nullptr) {
phead = newnode;
}
else
{
newnode->next = phead;
phead = newnode;
}
}
SLTNode* SLTNodeFind(SLTNode* phead, SLTNode* pos)
{
assert(pos && phead);
SLTNode* cur = phead;
while (cur)
{
if (cur->val == pos->val)
{
return cur;
}
}
return nullptr;
}
void SLTNodeErase(SLTNode*& phead, SLTNode* pos)
{
assert(phead && pos);
if (pos == phead){
SLTNode* next = phead->next;
free(phead);
phead = next;
}
else{
SLTNode* cur = phead;
while (cur->next != pos)
{
cur = cur->next;
}
cur->next = cur->next->next;
free(pos);
pos = nullptr;
}
}
void SListDestory(SLTNode*&phead)
{
SLTNode* cur = phead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
phead = nullptr;
}
void SLTNodeInsert(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = CreateSLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
void SLTNodeEraseAfter(SLTNode* pos)
{
assert(pos);
SLTNode* next = pos->next;
pos->next = pos->next->next;
free(next);
}
void EraseCurrent(SLTNode*&phead,SLTNode* pos) {
assert(phead && pos);
if (phead == pos) {
SLTNode* next = phead->next;
free(phead);
phead = next;
}
else {
SLTNode* cur = phead;
SLTNode* prev = nullptr;//记录cur的前一个节点
while (cur) {
if (cur == pos) {
break;
}
prev = cur;
cur = cur->next;
}
if (cur) {
prev->next = cur->next;
free(cur);
cur = nullptr;
}
}
}

或者这种写法也是可以的:

 

void EraseCurrent(SLTNode*&phead,SLTNode* pos) {
assert(phead && pos);
if (phead == pos) {
SLTNode* next = phead->next;
free(phead);
phead = next;
}
else {
SLTNode* cur = phead;
SLTNode* prev = nullptr;//记录cur的前一个节点
while (cur) {
if (cur == pos) {
break;
}
prev = cur;
cur = cur->next;
}
if (cur) {
prev->next = cur->next;
free(cur);
cur = nullptr;
}
}
}

这个就比较暴力遍历一次链表,如果找到了就返回节点的指针,如果没有找到就返回NULL

对应图解:

1.2单链表的存储方法:

实现思路:

#include"SList.h"
void TestSList()
{
SLTNode* plist = nullptr;
/*SLTNodePushBack(plist, 1);
SLTNodePushBack(plist, 2);*/
SLTNodePushFront(plist, 0);
SLTNodePrint(plist);
}
int main()
{
TestSList();
}

SLTNode* SLTNodeFind(SLTNode* phead, SLTNode* pos)
{
assert(pos && phead);
SLTNode* cur = phead;
while (cur)
{
if (cur->val == pos->val)
{
return cur;
}
}
return nullptr;
}

代码汇总:

void SLTNodeErase(SLTNode*& phead, SLTNode* pos)
{
assert(phead && pos);
if (pos == phead){
SLTNode* next = phead->next;
free(phead);
phead = next;
}
else{
SLTNode* cur = phead;
while (cur->next != pos)
{
cur = cur->next;
}
cur->next = cur->next->next;
free(pos);
pos = nullptr;
}
}

单链表尾删

努力的图片 的图像结果

2.单链表内部结构:

链接方式存储的线性表简称为链表(Linked List)。

链表的具体存储表示为:

① 用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的,也可以是不连续的)

② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址(或位置)信息(称为指针(pointer)或链(link))

链式存储是最常用的存储方式之一,它不仅可用来表示线性表,而且可用来表示各种非线性的数据结构。

1.定义一个指针变量变量cur整个链表,在定义一个指针变量next记录cur的下一个节点

2.free(cur),在让cur指向下一个节点,即cur=next;

链表的创建和遍历

1.链表的分类:

对应代码:

单链表头删

1.如果链表一个元素也没有则return

2.如果链表只有一个节点则将其置空,并将头节点置空

3.如果链表不止一个节点,我们则定义一个指针变量tail找尾,定义一个指针变量prev记录tail的前一个节点将prev->next指向tail->next,也就是prev->next=tail->next;在将尾部的节点释放


SLTNode* CreateSLTNode(SLTDataType x)
{
SLTNode* newnode = new SLTNode(x);
newnode->next = nullptr;
newnode->val = x;
return newnode;
}
void SLTNodePushFront(SLTNode*& phead,SLTDataType x)
{
SLTNode* newnode = CreateSLTNode(x);
if (phead == nullptr) {
phead = newnode;
}
else
{
newnode->next = phead;
phead = newnode;
}
}

1.如果链表没有头结点,新结点直接成为头结点。

2.如果有头节点则需要先找到链表当前的尾结点,并将新结点插入到链表尾部。

 单链表的尾部插入

代码实现:

单链表的头部插入:

实现思路:

 总结:

单个节点:

1.单向或者双向

2. 带头或者不带头

3. 循环或者非循环

4. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。2. 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单

在目标位置处插入数据元素流程如下:
1、从头结点开始,提供cur指针定位到目标位置
2、从堆空间申请新的Node结点
3、将新结点插入目标位置,并连接相邻结点的逻辑关系。

 

1.如果链表没有头结点,新结点直接成为头结点。

2.否则新结点的next直接指向当前头结点,并让新结点成为新的头结点。

单链表的查找:

 da

链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。

以“结点的序列”表示线性表称作线性链表(单链表),单链表是链式存取的结构。

单链表pos位置删除:

单链表pos位置后面插入:

目录

对应图解:

void SLTNodeInsert(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = CreateSLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}

单链表尾删

void SListDestory(SLTNode*&phead)
{
SLTNode* cur = phead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
phead = nullptr;
}

1.1:单链表概念:

实现思路:

实现思路:

Test.cpp

单链表pos位置后面插入:

对应代码实现:

void SLTNodePopFront(SLTNode*& phead)
{
if (phead == nullptr) {//如果一个节点也没有就不用删了
return;
}
else
{
SLTNode* next = phead->next;
free(phead);
phead = next;
}
}

对应代码:

本文转自 https://blog.csdn.net/qq_56999918/article/details/121464075

腾讯云618
云惠网小编
cgb2110-day06 java

cgb2110-day06

文章目录一,模拟用户登录过程--1,需求--2,测试--3,程序优化二,SQL攻击/注入--1,概述--2,解决方案--3,修改代码--4,两种传输器的区别三,练习新的传输器--1...
JAVA 初级程序员常见问题分析 java

JAVA 初级程序员常见问题分析

1、怎么样可以尽快拿到offer?针对心仪的企业、岗位进行调查。可以上招聘网站看看其岗位要求,以及企业的面试题。然后针对性的学习其要求的技术。这样有针对性的准备,投其所好,就可更快...
关于数据库学习的一些知识盲区 java

关于数据库学习的一些知识盲区

一.SQL拼接方法的安全风险 1. SQL注入问题(SQL Inject),使用字符串拼接构造SQL就会引起SQL注入。 2. SQL注入是存在安全风险的 3. 例如:在图书管理系...
szu-exp 安卓开发实验3我的校园 java

szu-exp 安卓开发实验3我的校园

发扬开源精神... 给个赞吧giegiejiejie们 实验目的与要求: 目的:掌握安卓中活动的编写、自定义用户界面的开发、碎片开发、广播机制以及数据持久化技术等;并能通过对课堂知...
腾讯云618

发表评论