刨析数据结构(二)

2024-02-03 01:44
文章标签 数据结构 刨析

本文主要是介绍刨析数据结构(二)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

🌈个人主页：小田爱学编程
🔥 系列专栏：数据结构————"带你无脑刨析"
🏆🏆关注博主，随时获取更多关于数据结构的优质内容！🏆🏆

😀欢迎来到小田代码世界~
😁 喜欢的小伙伴记得一键三连哦 ૮(˶ᵔ ᵕ ᵔ˶)ა

一.线性表的链式储存

链表：线性表的链式储存方式，逻辑结构不一定连续，物理结构不一定连续

描述：由数据域和指针域组成

🌏头结点：点是为了操作方便而设立的，放在第一个元素结点之前，不保存任何有意义的数据

🌏头节点：即为指向第一个节点的地址 

🔥链表分类：八种

👨‍🚀 以单链表（不带头单向不循环链表）

 二.单链表

1.优缺点

🔥任意位置插入删除，时间复杂度小
🔥没有增容问题，插入一个开辟一个空间

🔥不支持随机访问

2.创建

//定义链表
typedef int SLTDataType;//数值域
//链表是由节点组成
typedef struct SListNode
{SLTDataType data;//int datastruct  SListNode* next;//它用来存储当前节点的下一个节点的地址
}SLTNode;//typedef struct SListNode SLTNode;

3.打印

void SLTPrint(SLTNode* phead) {SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}
SLTNode* plist = node1;
SLTPrint(plist);

 

3.申请空间

SLTNode* SLTBuyNode(SLTDataType x) {SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL) {perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}

4.增加元素

尾插：

void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = SLTBuyNode(x);//链表为空，新节点作为pheadif (*pphead == NULL) {*pphead = newnode;return;}//链表不为空，找尾节点SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptail就是尾节点ptail->next = newnode;
}

头插：

void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = SLTBuyNode(x);//newnode *ppheadnewnode->next = *pphead;*pphead = newnode;
}

在指定位置插入

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);//要加上链表不能为空assert(*pphead);SLTNode* newnode = SLTBuyNode(x);//pos刚好是头结点if (pos == *pphead) {//头插SLTPushFront(pphead, x);return;}//pos不是头结点的情况SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev -> newnode -> posprev->next = newnode;newnode->next = pos;
}

5.删除元素

 尾删

void SLTPopBack(SLTNode** pphead) {assert(pphead);//链表不能为空assert(*pphead);//链表不为空//链表只有一个节点，有多个节点if ((*pphead)->next == NULL) {free(*pphead);*pphead = NULL;return;}SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;//销毁尾结点free(ptail);ptail = NULL;
}

 头删

void SLTPopFront(SLTNode** pphead) {assert(pphead);//链表不能为空assert(*pphead);//让第二个节点成为新的头//把旧的头结点释放掉SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}

🔥指定位置删除:注意删除的逻辑

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(*pphead);assert(pos);//pos刚好是头结点，没有前驱节点，执行头删if (*pphead == pos) {//头删SLTPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;
}
void SLTEraseAfter(SLTNode* pos) {assert(pos);//pos->next不能为空assert(pos->next);//pos  pos->next  pos->next->nextSLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}

6.修改元素

//给一个数据，找到这个数据所在的节点，并用新数据修改
void SListChangeDate(SLTNode*pphead, SLTDataType x, SLTDataType y)
//不需要改变节点的地址，所以值传递即可 
//x是查找的数据，y是新的数据，用来修改查找的数据                                              
{SLTNode*cru = pphead;while (cru != NULL)//如果没有节点，根本不会进入循环去找{if (cru->data == x){cru->data = y;break;//修改完数据后，就跳出循环}else{cru = cru->next;}}if (cru == NULL)//如果循环完单链表，没有找到要修改的那个数据{printf("要修改的数据不存在，请重新修改数据\n");}else{printf("修改成功\n");}
}

7.查找元素

SLTNode* SLTFind(SLTNode** pphead, SLTDataType x) {assert(pphead);//遍历链表 SLTNode* pcur = *pphead;while (pcur) //pcur != NULL{if (pcur->data == x) {return pcur;}pcur = pcur->next;}//没有找到return NULL;
}

8.销毁链表

void SListDesTroy(SLTNode** pphead) {assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

三.双向链表

1.注意

🔥带头双向循环链表

🔥当链表中只要头节点的时候，为空链表

🔥头节点是不能删除的，指向可以改变

🔥不需要改变头节点的指向，不需要传二级指针

🔥二级指针对实参会产生影响 

 2.创建

typedef int LTDataType;
typedef struct ListNode {LTDataType data;struct ListNode* prev;struct ListNode* next;
}LTNode;

3.打印

LTNode* LTInit() {LTNode* phead = LTBuyNode(-1);return phead;
}

4.增加元素

尾插（不需要找尾操作）

//尾插
void LTPushBack(LTNode* phead, LTDataType x) {assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev(ptail)  newnodenewnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}

 头插

//头插
void LTPushFront(LTNode* phead, LTDataType x) {assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->nextnewnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

任意位置插入

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x) {assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}
//删除pos位置的数据
void LTErase(LTNode* pos) {assert(pos);//pos->prev pos  pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}

5.删除元素

头删

void LTPopFront(LTNode* phead) {assert(phead);assert(phead->next != phead);LTNode* del = phead->next;LTNode* next = del->next;//phead del nextnext->prev = phead;phead->next = next;free(del);del = NULL;
}

 尾删

void LTPopBack(LTNode* phead) {assert(phead);//链表为空：只有一个哨兵位节点assert(phead->next != phead);LTNode* del = phead->prev;LTNode* prev = del->prev;prev->next = phead;phead->prev = prev;free(del);del = NULL;
}

 任意位置删除

void LTErase(LTNode* pos) {assert(pos);//pos->prev pos  pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}

6.修改元素

void DeleteNode(LTNode** pHead, LTNode* toBeDeleted) {if (pHead == NULL || toBeDeleted == NULL) {return;}LTNode* head = *pHead;// 要删除的节点是头节点if (head == toBeDeleted) {*pHead = toBeDeleted->next;}// 调整前驱节点的next指针if (toBeDeleted->prev != NULL) {toBeDeleted->prev->next = toBeDeleted->next;}// 调整后继节点的prev指针if (toBeDeleted->next != NULL) {toBeDeleted->next->prev = toBeDeleted->prev;}free(toBeDeleted);
}

7.查找元素

LTNode* LTFind(LTNode* phead, LTDataType x) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x) {return pcur;}pcur = pcur->next;}return NULL;
}

8.销毁链表

void LTDesTroy(LTNode* phead) {//哨兵位不能为空assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//链表中只有一个哨兵位free(phead);phead = NULL;
}

🥇这是博主年前的最后一篇文章哦，年后再继续更新，年后会开启新的刷题专栏！😊

🥇还有不到不到一周就过年喽！祝大家新的一年财源滚滚，学习进步，身体健康，咱们明年见！ 

 🎁🎁🎁今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，您的支持就是我前进的动力！

这篇关于刨析数据结构(二)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/672638。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...
浙大数据结构：04-树7 二叉搜索树的操作集

浙大数据结构：04-树7 二叉搜索树的操作集

这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
阅读更多...
【数据结构入门】排序算法之交换排序与归并排序

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客，我们学习了排序算法中的插入排序和选择排序，接下来我们将继续探索交换排序与归并排序，这两个排序都是重头戏，让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换，让较大的元素逐渐向右移动，从而将最大的元素移动到最右边。 动画演示： 1.1.2 具体步
阅读更多...
数据结构：线性表的顺序存储

数据结构：线性表的顺序存储

文章目录 🍊自我介绍🍊线性表的顺序存储介绍概述例子 🍊顺序表的存储类型设计设计思路类型设计 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入
阅读更多...
[数据结构]队列之顺序队列的类模板实现

[数据结构]队列之顺序队列的类模板实现

队列是一种限定存取位置的线性表，允许插入的一端叫做队尾（rear），允许删除的一端叫做队首（front）。 队列具有FIFO的性质 队列的存储表示也有两种方式：基于数组的，基于列表的。基于数组的叫做顺序队列，基于列表的叫做链式队列。 一下是基于动态数组的顺序队列的模板类的实现。 顺序队列的抽象基类如下所示：只提供了接口和显式的默认构造函数和析构函数，在派生类中调用。 #i
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2