专业的集团网站开发,外贸简单网站建设,ERP开发 网站开发,WordPress源码路由#x1f308;个人主页#xff1a;小田爱学编程 #x1f525; 系列专栏#xff1a;数据结构————带你无脑刨析 #x1f3c6;#x1f3c6;关注博主#xff0c;随时获取更多关于c语言的优质内容#xff01;#x1f3c6;#x1f3c6; #x1f600;欢迎来…
个人主页小田爱学编程 系列专栏数据结构————带你无脑刨析 关注博主随时获取更多关于c语言的优质内容 欢迎来到小田代码世界~ 喜欢的小伙伴记得一键三连哦 ૮(˶ᵔ ᵕ ᵔ˶)ა 目录 一.数据结构是啥 二.常见的数据结构 三.数据结构三要素 1.逻辑结构: 2.物理结构: 3.数据运算 四.数据结构基本概念 1.数据 2.数据元素 3.数据对象 4.数据结构 4.数据类型 5.抽象数据类型 6.逻辑结构 7.物理结构存储结构 8.算法 五.线性表 六.顺序表 1.顺序表的定义 2.顺序表的分类 1.静态顺序表 2.动态顺序表 3.创建文件 4.初始化 5.增加元素 6.删除元素 7.修改元素 8.查找元素 七.顺序表的局限性 一.数据结构是啥 数据结构是由“数据”和“结构”两词组合而来。 1234数据按照一定规律组织在一起结构 数据结构是计算机存储、组织数据的方式 数据结构算法程序
二.常见的数据结构
数组 链表 栈队列 树队散列表 图
三.数据结构三要素
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.创建文件 SeqList.h 数据的各种准备接口的各种准备 SeqList.c 函数如何实现 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-arrNULL;PS-sizeps-capcity0;
}
void SLPrint(SL*ps)
{
for (int i0;ips-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] -1ps-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(*▽*)ブ[●´︶●]
今天的分享到这里就结束啦如果觉得文章还不错的话可以三连支持一下您的支持就是我前进的动力
