刨析数据结构(一)

2024-01-31 19:20
文章标签 数据结构 刨析

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

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


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

目录

一.数据结构是啥?

二.常见的数据结构

三.数据结构三要素

1.逻辑结构: 

2.物理结构:

3.数据运算:

四.数据结构基本概念

1.数据:

2.数据元素

3.数据对象

4.数据结构

4.数据类型

5.抽象数据类型

6.逻辑结构

7.物理结构(存储结构)

8.算法

 五.线性表

六.顺序表

1.顺序表的定义

2.顺序表的分类 

1.静态顺序表

2.动态顺序表

3.创建文件

4.初始化

5.增加元素:

6.删除元素

7.修改元素

8.查找元素

 七.顺序表的局限性


一.数据结构是啥?

     🌏数据结构是由“数据”和“结构”两词组合而来。

     🔥1,2,3,4(数据)按照一定规律组织在一起(结构)

     👨‍🚀数据结构是计算机存储、组织数据的方式

     🌏数据结构+算法=程序

二.常见的数据结构

  1. 数组 
  2. 链表 
  3. 队列 
  4. 散列表 

三.数据结构三要素

1.逻辑结构: 

 由数据元素之间的逻辑关系构成

2.物理结构:

由数据元素之间的逻辑关系构成

3.数据运算:

施加在数据上的运算包括运算的定义和实现。

四.数据结构基本概念

1.数据:

数据是能描述客观事物的数值,字符以及能输入机器且能被处理的各种符号集合

2.数据元素

组成数据结构的基本单位

3.数据对象

性质相同的数据元素的的集合,是数据的一个子集

4.数据结构

 数据结构:是相互之间存在一种或多种特定关系的数据元素的集合

4.数据类型

数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称

数据类型其实包含了数据结构,注意“一个值的集合”,这个值可以是原子类型的值集和结构类型的值集,而结构类型的值集就是数据结构。这里的数据结构指的是它的定义而不是它的实现

按值来分————————原子类型(不可再分) 结构类型(可以再分)

5.抽象数据类型

  抽象数据类型(Abstract Date Type,简称 ADT):指从问题中抽象出来的一个数据模型以及定    义在此数据模型上的一组操作,不考虑计算机的具体存储结构与运算的具体实现算法。

6.逻辑结构

 DS = ( D, S )   【Data Structure】 D:数据集合 R:关系集合

根据数据元素之间关系的不同特征,通常有下列4类基本结构,复杂程度依次递进。

①集合:结构中的数据元素之间除了同属于一个集合外,没有其他的关系。

②线性结构:线性结构中的数据元素之间是一对一的关系。

③树形结构:树形结构中的数据元素之间是一对多的关系。

④图状结构或网状结构:结构中的元素之间是多对多的关系。

7.物理结构(存储结构)

逻辑结构在计算机的存储映象

数据元素之间的关系在计算机中有两种不同的表示方法:顺序映像和非顺序映像。对应的两种不同的存储结构分别是顺序存储结构和链式存储结构

8.算法

对特定问题求解步骤的一种描述,是为解决一个或一类问题给出的一个确定的、有限长的操作

特性:有限性 确定性 可行性 输入 输出

评价算法性能:算法执行时间与占用存储的空间

算法复杂度,大方面来看分为时间复杂度空间复杂度

空间复杂度(规模有无关系)

 五.线性表

线性表(List):零个或多个数据元素的有限序列。

线性表的数据集合为{a1,a2,…,an},假设每个元素的类型均为DataType。其中,除第一个元素a1外,每一个元素有且只有一个直接前驱元素,除了最后一个元素an外,每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

在较复杂的线性表中,一个数据元素可以由若干个数据项组成。在这种情况下,常把数据元素称为记录,含有大量记录的线性表又称为文件

👍我们想从最简单的开始:顺序表

 🥇🥇🥇正片开始喽

六.顺序表

1.顺序表的定义

 类比:数组是顺序表的封装

2.顺序表的分类 

  静态顺序表.动态顺序表

1.静态顺序表

2.动态顺序表

3.创建文件

  1. SeqList.h :数据的各种准备,接口的各种准备

  2. SeqList.c : 函数如何实现

  3.   test.c:测试操作是否成功

4.初始化

typedef int SLDataType
typedef struct SeqList
{SLDataType*arr//数据的底层结构int capacity;//顺序表的空间大小int size;//有效个数
}SL
void SLInit(SL*ps)//顺序表的初始化
void SLDestory(SL*ps)//顺序表的销毁
void SLInit(SL*ps)
{PS->arr=NULL;PS->size=ps->capcity=0;
}
void SLPrint(SL*ps)
{ 
for (int i=0;i<ps->size;i++){printf("%d ",ps->arr[i]);}
printf("\n")
}

5.增加元素:

void SLPushBack(SL*ps,SLDataType X)//头插
void SLPushDate(SL*ps,SLDataType X)//尾插
void SLInsert(SL* ps, int pos, SLDataType x);//中间插
void SLCheckCapacity(SL* ps) //扩容
void SLCheckCapacity(SL* ps) {if (ps->size == ps->capacity) {int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));if (tmp == NULL) {perror("realloc fail!");exit(1);}//扩容成功ps->arr = tmp;ps->capacity = newCapacity;}
}//空间不够,扩容SLCheckCapacity(ps);//空间足够,直接插入ps->arr[ps->size++] = x;
}//尾插
void SLPushFront(SL* ps, SLDataType x) {assert(ps);//判断是否扩容SLCheckCapacity(ps);//旧数据往后挪动一位for (int i = ps->size; i > 0; i--) {ps->arr[i] = ps->arr[i - 1]; }ps->arr[0] = x;ps->size++;//头插
void SLInsert(SL* ps, int pos, SLDataType x) {assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);//pos及之后的数据往后挪动一位,pos空出来for (int i = ps->size; i > pos;i--){ps->arr[i] = ps->arr[i - 1]; }ps->arr[pos] = x;ps->size++;
}任意位置插

 6.删除元素

void SLPopBack(SL* ps);
void SLPopFront(SL* ps);
void SLErase(SL* ps, int pos);
void SLPopBack(SL* ps) {assert(ps);assert(ps->size);ps->size--; //ps->arr[ps->size - 1] = -1==ps->size--//尾删
void SLPopFront(SL* ps) {assert(ps);assert(ps->size);for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}//头删
void SLErase(SL* ps, int pos) {assert(ps);assert(pos >= 0 && pos < ps->size);//pos以后的数据往前挪动一位for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}指定位置删除

 7.修改元素

void SLModify(SL* ps, int pos, SLDataType x)
void SLModify(SL* ps1, int pos, SLDataType x)
{assert(ps1);assert(0 <= pos && pos < ps1->size);ps1->arr[pos] = x;
}

8.查找元素

void SLFind(SL* psl, SLDatatype x)
void SLFind(SL* ps, SLDatatype x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;}}return -1;
}

 七.顺序表的局限性

1.中间/头部的插⼊删除,时间复杂度为O(N)

2.增容需要申请新空间,拷⻉数据,释放旧空间。会有不小的消耗
3.增容⼀般是呈2倍的增⻓,势必会有⼀定的空间浪费。例如当前容量为100,满了以后增容到
200,我们再继续插⼊了5个数据,后⾯没有数据插入了,那么就浪费了95个数据空间

这种的局限性已经被我们的计算机前辈给解决了,如果你想知道怎么解决,请持续关注😀

🥇🥇🥇  新的专栏:数据结构————"带你无脑刨析"博主正在火速创作中,可以关注博主一下   哦!φ(゜▽゜*)♪o(* ̄▽ ̄*)ブ[●´︶`●]

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

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



http://www.chinasem.cn/article/664804

相关文章

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

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

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-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

【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 内置的一些数据结构

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

浙大数据结构: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