上次在面试时被面试官问到学了哪些数据结构，那时简单答了栈、队列/(ㄒ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}
3、图形结构：在图形结构中，允许多个结点之间相关，称为&多对多&关系，可分为有向图和无向图
阅读(...) 评论()请输入您的评论
?&??&??&??&??&?
????????????
&计算机等级考试
&计算机技术与软件专业技术资格（水平）考试
&建筑工程考试
&职业资格考试8979人阅读
计算机基础（5）
数据结构是计算机存储、组织数据的方式。常见的数据结构分类方式如下图：
常用的线性结构有：线性表，栈，队列，循环队列，数组。线性表中包括顺序表、链表等，其中，栈和队列只是属于逻辑上的概念，实际中不存在，仅仅是一种思想，一种理念；线性表则是在内存中数据的一种组织、存储的方式。
顺序表将元素一个接一个的存入一组连续的存储单元中，在内存物理上是连续的。如下图：
顺序表存储密度较大，节省空间；但需要事先确定容量，在时间性能方面，读运算较快，时间复杂度为O(1)；查找运算为O(n/2)，和链表同样；插入运算和删除运算如果要操作中间一个元素，比如3，那么就需要把3后面的元素全部进行移动，因此时间复杂度相对链表要大一些，插入时间复杂度最好为O(0)或最坏为O(n)；删除时间复杂度为O([n-1]/2)；
链表拥有很多结点，每个结点前半部分是数据域，后半部分是指针域，指针域指针指向下一个结点；链表可分为单链表、循环链表和双链表。
从上图可以看出，单链表的上一个结点指针指向下一个结点，最后一个结点的指针域为null。
结点的删除：
删除一个结点，如删除上图中q结点，只需将p结点中的指针域指向a3，然后将a2释放掉（free）即可。
结点的插入：
插入一个结点，如插入上图中s结点，首先将s的指针域指向a2（也就是把s的next赋值为p的next），然后将p结点的指针域指向x即可（p的next指向x）。
循环链表与单链表唯一不同之处是，循环链表的最后一个结点指针不为空，而是指向头结点。结点的插入和删除和单链表非常相似，就不再示范了。
双链表拥有一前一后两个指针域，从两个不同的方向把链表连接起来，如此一来，从两个不同的方向形成了两条链，因此成为双链表。因此，双链表的灵活度要大于单链表。
结点的删除：
双链表的操作比单链表要稍显复杂（按照单链表思路来做其实也不难），如上图，要删除p节点，首先需要将a1的后驱指向a3，然后将a3的前驱指向a1，最后将p节点释放掉即可。
结点的插入：
如上图，插入q结点，首先要按照方向，将步骤拆分，首先将q节点的前驱指向p结点后驱，紧接着将x后驱指向a2；然后按照顺序完成图中所示的3、4步即可。（经@&&@&@&三位童鞋的指正，发现此处有误，正确插入方法可查看评论，为保留错误原文不做改动！不懂具体插入过程可移步：）
从空间性能来看，链表的存储密度要差一些，但在容量分配上更灵活一些。从时间性能来看，查找运算与顺序存储相同，插入运算和删除运算的时间复杂度为O(1)，要更优于顺序存储，但读运算则弱一些，为O([n+1]/2)，最好为1，最坏为n。
上面提到栈属于一个逻辑概念，栈的实现可以用顺序也可以用链式。它遵循先进后出原则，如下图：
Java中测试代码如下：
package com.snail.
import java.util.S
public class TestStack {
public static void main(String[] args) {
Stack&String& stack = new Stack&String&();
stack.push(&NO1&);
stack.push(&NO2&);
stack.push(&NO3&);
System.out.println(&初始数量：& + stack.size());
while(!stack.isEmpty()){
System.out.println(stack.pop());
System.out.println(&取完后的数量：& + stack.size());
输出结果顺序为：初始数量：3，NO3，NO2，NO1，取完后的数量：0。
队列遵循先进先出的原则，如下图：
Java中测试代码如下：
package com.snail.
* @author Zang XT
import java.util.Q
import java.util.LinkedL
public class TestQueue {
public static void main(String[] args) {
Queue&String& queue = new LinkedList&String&();
queue.offer(&NO1&);
queue.offer(&NO2&);
queue.offer(&NO3&);
System.out.println(&初始数量& + queue.size());
while((str=queue.poll())!=null){
System.out.println(str);
System.out.println(&取出后数量& + queue.size());
运行结果顺序为：初始数量3，NO1，NO2，NO3，取出后数量0。
队列还有一种形式为循环队列，如下图：
循环队列有两个指针，头指针head和尾指针tail，尾指针一般指向的不是队尾元素实际地址，而是指向实际地址的下一个空地址，因此，循环队列一般牺牲最后一个空间，用来计算该队列是否满了，判断方式是tail+1 = head，既该队列已满。
为了尽可能的说清楚，插了大量图片，希望理解。以后有时间将继续分析树、图等数据结构。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：354476次
积分：7527
积分：7527
排名：第2111名
原创：116篇
评论：1307条
(1)(1)(2)(5)(1)(1)(2)(5)(4)(4)(4)(4)(4)(4)(4)(4)(2)(4)(4)(5)(4)(4)(5)(7)(4)(4)(6)(5)(5)(3)(4)(1)只有一个根结点的数据结构不一定是线性结构?这句话是错误的,这怎么理解?
这个主要是考察 树的知识假如：二叉树只有一个根节点,但是他有非线性结构
为您推荐：
其他类似问题
扫描下载二维码}