基本的数据结构
2018-10-31 本文已影响0人
A_9c74
数据元素相互之间的关系称为结构。有四类基本结构：集合、线性结构、树形结构、图状结构。
1、集合结构：除了同属于一种类型外，别无其它关系。
3、线性结构：元素之间存在一对一关系常见类型有: 数组,链表、队列、栈，它们之间在操作上有所区别。例如：链表可在任意位置插入或删除元素，而队列在队尾插入元素，队头删除元素，栈只能在栈顶进行插入，删除操作。
3、树形结构：元素之间存在一对多关系,常见类型有：树(有许多特例：二叉树、平衡二叉树、查找树等)
4、图形结构:元素之间存在多对多关系，图形结构中每个结点的前驱结点数和后续结点多个数可以任意。
image.png
一、数组和链表
数组：
存放着一组相同类型的数据，需要预先指定数组的长度，有一维数组、二维数组、多维数组等
链表：
：链表是C语言中一种应用广泛的结构，它采用动态分配内存的形式实现，用一组任意的存储单元存放数据元素链表的，一般为每个元素增设指针域，用来指向后继元素
数组和链表的区别：
从逻辑结构来看：数组必须事先定义固定的长度，不能适应数据动态地增减的情况；链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项（数组中插入、删除数据项时，需要移动其它数据项）
从内存存储来看：（静态)数组从栈中分配空间（用NEW创建的在堆中）, 对于程序员方便快速,但是自由度小；链表从堆中分配空间, 自由度大但是申请管理比较麻烦`
从访问方式来看：数组在内存中是连续存储的，因此，可以利用下标索引进行随机访问；链表是链式存储
栈、队列和线性表：可采用顺序存储和链式存储的方法进行存储
顺序存储：借助数据元素在存储空间中的相对位置来表示元素之间的逻辑关系
链式存储：借助表示数据元素存储地址的指针表示元素之间的逻辑关系
栈：
只允许在序列末端进行操作，栈的操作只能在栈顶进行，一般栈又被称为后进先出或先进后出的线性结构
顺序栈：采用顺序存储结构的栈称为顺序栈，即需要用一片地址连续的空间来存储栈的元素，顺序栈的类型定义如下：
image.png
链栈：采用链式存储结构的栈称为链栈：
image.png
队列：
只允许在序列两端进行操作，一般队列也被称为先进先出的线性结构
循环队列：采用顺序存储结构的队列，需要按队列可能的最大长度分配存储空空，其类型定义如下：
image.png
链队列：采用链式存储结构的队列称为链队列，一般需要设置头尾指针只是链表的头尾结点：
image.png
线性表：
允许在序列任意位置进行操作，线性表的操作位置不受限制，线性表的操作十分灵活，常用操作包括在任意位置插入和删除，以及查询和修改任意位置的元素
顺序表：采用顺序存储结构表示的线性表称为顺序表，用一组地址连续的存储单元一次存放线性表的数据元素，即以存储位置相邻表示位序相继的两个元素之间的前驱和后继关系，为了避免移动元素，一般在顺序表的接口定义中只考虑在表尾插入和删除元素，如此实现的顺序表也可称为栈表：
image.png
线性表：一般包括单链表、双向链表、循环链表和双向循环链表
二、树形结构结点间具有层次关系，每一层的一个结点能且只能和上一层的一个结点相关，但同时可以和下一层的多个结点相关，称为“一对多”关系，常见类型有：树、堆
二叉树：
二叉树是一种递归数据结构，是含有n(n>=0)个结点的有限集合，二叉树具有以下特点：
二叉树可以是空树；二叉树的每个结点都恰好有两棵子树，其中一个或两个可能为空；二叉树中每个结点的左、右子树的位置不能颠倒，若改变两者的位置，就成为另一棵二叉树
完全二叉树：从根起，自上而下，自左而右，给满二叉树的每个结点从1到n连续编号，如果每个结点都与深度为k的满二叉树中编号从1至n的结点一一对应，则称为完全二叉树
