C语⾔中都有哪些常见的数据结构你都知道⼏个？
上次在⾯试时被⾯试官问到学了哪些数据结构，那时简单答了栈、队列/(ㄒoㄒ)/~~其它就都想不起来了，今天有空整理了⼀下⼏种常见的数据结构，原来我们学过的数据结构有这么多~
⾸先，先来回顾下C语⾔中常见的基本数据类型吧O(∩_∩)O
C语⾔的基本数据类型有：整型int，浮点型float，字符型char等等
添加描述
那么，究竟什么是数据结构呢？
数据结构是计算机存储、组织数据的⽅式。数据结构是指相互之间存在⼀种或多种特定关系的数据元素的集合
⼤部分数据结构的实现都需要借助C语⾔中的指针和结构体类型
下⾯，进⼊今天的重点啦O(∩_∩)O⼏种常见的数据结构
（1）线性数据结构：元素之间⼀般存在元素之间存在⼀对⼀关系，是最常⽤的⼀类数据结构，典型的有：数组、栈、队列和线性表
（2）树形结构：结点间具有层次关系，每⼀层的⼀个结点能且只能和上⼀层的⼀个结点相关，但同时可以和下⼀层的多个结点相关，称
为“⼀对多”关系，常见类型有：树、堆
（3）图形结构：在图形结构中，允许多个结点之间相关，称为“多对多”关系
下⾯分别对这⼏种数据结构做⼀个简单介绍：
1、线性数据结构：典型的有：数组、栈、队列和线性表
（1）数组和链表
a、数组：存放着⼀组相同类型的数据，需要预先指定数组的长度，有⼀维数组、⼆维数组、多维数组等
b、链表：链表是C语⾔中⼀种应⽤⼴泛的结构，它采⽤动态分配内存的形式实现，⽤⼀组任意的存储单元存放数据元素链表的，⼀般为每个元素增设指针域，⽤来指向后继元素
c、数组和链表的区别：
从逻辑结构来看：数组必须事先定义固定的长度，不能适应数据动态地增减的情况；链表动态地进⾏存储分配，可以适应数据动态地增减的情况，且可以⽅便地插⼊、删除数据项（数组中插⼊、删除数据项时，需要移动其它数据项）
从内存存储来看：（静态)数组从栈中分配空间（⽤NEW创建的在堆中）, 对于程序员⽅便快速，但是⾃由度⼩；链表从堆中分配空间, ⾃由度⼤但是申请管理⽐较⿇烦
从访问⽅式来看：数组在内存中是连续存储的，因此，可以利⽤下标索引进⾏随机访问；链表是链式存储结构，在访问元素的时候只能通过线性的⽅式由前到后顺序访问，所以访问效率⽐数组要低
（2）栈、队列和线性表：可采⽤顺序存储和链式存储的⽅法进⾏存储
顺序存储：借助数据元素在存储空间中的相对位置来表⽰元素之间的逻辑关系
链式存储：借助表⽰数据元素存储地址的指针表⽰元素之间的逻辑关系
a、栈：只允许在序列末端进⾏操作，栈的操作只能在栈顶进⾏，⼀般栈⼜被称为后进先出或先进后出的线性结构
顺序栈：采⽤顺序存储结构的栈称为顺序栈，即需要⽤⼀⽚地址连续的空间来存储栈的元素，顺序栈的类型定义如下：
添加描述
链栈：采⽤链式存储结构的栈称为链栈：
添加描述
b、队列：只允许在序列两端进⾏操作，⼀般队列也被称为先进先出的线性结构
循环队列：采⽤顺序存储结构的队列，需要按队列可能的最⼤长度分配存储空空，其类型定义如下：
添加描述
　链队列：采⽤链式存储结构的队列称为链队列，⼀般需要设置头尾指针只是链表的头尾结点：
添加描述
c、线性表：允许在序列任意位置进⾏操作，线性表的操作位置不受限制，线性表的操作⼗分灵活，常⽤操作包括在任意位置插⼊和删除，以及查询和修改任意位置的元素
顺序表：采⽤顺序存储结构表⽰的线性表称为顺序表，⽤⼀组地址连续的存储单元⼀次存放线性表的数据元素，即以存储位置相邻表⽰位序相继的两个元素之间的前驱和后继关系，为了避免移动元素，⼀般在顺序表的接⼝定义中只考虑在表尾插⼊和删除元素，如此实现的顺序表也可称为栈表：
添加描述
数组和链表线性表：⼀般包括单链表、双向链表、循环链表和双向循环链表
单链表：
添加描述
　双向链表：
添加描述
线性表两种存储结构的⽐较：
顺序表：
　优点：在顺序表中，逻辑中相邻的两个元素在物理位置上也相邻，查⽐较⽅便，存取任⼀元素的时间复杂度都为O(1)
　缺点：不适合在任意位置插⼊、删除元素，因为需要移动元素，平均时间复杂度为O(n)
链表：
　优点：在链接的任意位置插⼊或删除元素只需修改相应指针，不需要移动元素；按需动态分配，不需要按最⼤需求预先分配⼀块连续空空　缺点：查不⽅便，查某⼀元素需要从头指针出发沿指针域查，因此平均时间复杂度为O(n)
2、树形结构：结点间具有层次关系，每⼀层的⼀个结点能且只能和上⼀层的⼀个结点相关，但同时可以和下⼀层的多个结点相关，称为“⼀对多”关系，常见类型有：树、堆
（1）⼆叉树：⼆叉树是⼀种递归数据结构，是含有n(n>=0)个结点的有限集合，⼆叉树具有以下特点：
⼆叉树可以是空树；⼆叉树的每个结点都恰好有两棵⼦树，其中⼀个或两个可能为空；⼆叉树中每个结点的左、右⼦树的位置不能颠倒，若改变两者的位置，就成为另⼀棵⼆叉树
（2）完全⼆叉树：从根起，⾃上⽽下，⾃左⽽右，给满⼆叉树的每个结点从1到n连续编号，如果每个结点都与深度为k的满⼆叉树中编号从1⾄n的结点⼀⼀对应，则称为完全⼆叉树
a、采⽤顺序存储结构：⽤⼀维数组存储完全⼆叉树，结点的编号对于与结点的下标（如根为1，则根的左孩⼦为2*i=2*1=2，右孩⼦为
2*i+1=2*1+1=2）
添加描述
b、采⽤链式存储结构：
⼆叉链表：
添加描述
三叉链表：它的结点⽐⼆叉链表多⼀个指针域parent，⽤于执⾏结点的双亲，便于查双亲结点
添加描述
两种存储结构⽐较：对于完全⼆叉树，采⽤顺序存储结构既能节省空间，⼜可利⽤数组元素的下标值确定结点在⼆叉树中的位置及结点之间的关系，但采⽤顺序存储结构存储⼀般⼆叉树容易造成空间浪费，链式结构可以克服这个缺点
（3）⼆叉查树：⼆叉查树⼜称⼆叉排序树，或者是⼀课空⼆叉树，或者是具有如下特征的⼆叉树：
a、若它的左⼦树不空，则左⼦树上所有结点的值均⼩于根结点的值
b、若它的右⼦树不空，则右⼦树上所有结点的值均⼤于根结点的值
c、它的左、右⼦树也分别是⼆叉查树
（4）平衡⼆叉树：平衡⼆叉查树简称平衡⼆叉树，平衡⼆叉树或者是棵空树，或者是具有下列性质的⼆叉查树：它的左⼦树和右⼦树都是平衡⼆叉树，且左⼦树和右⼦树的⾼度之差的绝对值不超过1
添加描述
平衡⼆叉树的失衡及调整主要可归纳为下列四种情况：LL型、RR型、LR型、RL型
（5）树：树是含有n(n>=0)个结点的有限集合，在任意⼀棵⾮空树种： a、有且仅有⼀个特定的称为根的结点
b、当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,...,Tm，其中每⼀个集合本⾝⼜是⼀棵树，并且T1,T2,...,Tm称为根的⼦树（6）堆：堆是具有以下特性的完全⼆叉树，其所有⾮叶⼦结点均不⼤于（或不⼩于）其左右孩⼦结点。若堆中所有⾮叶⼦结点均不⼤于其左右孩⼦结点，则称为⼩顶堆（⼩根堆），若堆中所有⾮叶⼦结点均不⼩于其左右孩⼦结点，则称为⼤顶堆（⼤根堆）
添加描述
（7）并查集：并查集是指由⼀组不相交⼦集所构成的集合，记作：S={S1,S2,S3,...,Sn}
（8）B树
3、图形结构：在图形结构中，允许多个结点之间相关，称为“多对多”关系，可分为有向图和⽆向图-------------------------------------------------------------------------------------------------
⼀些相关的视频资料便于⼤家学习
C语⾔与数据结构的经典实战案例
结构体普及与应⽤
C语⾔玩转链表
C⾼级之结构体
循环链表及线性表的应⽤

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。