数据结构

引入

数据结构是带有结构特性的数据元素的集合。

在面向过程编程中，我们通常使用顺序、选择、循环三种结构以及变量来进行编程。但是有些时候，这三种方法加上单一的变量在解答某些问题时显得相形见绌，所以这个时候就需要一些辅助的结构来帮助运算，这种结构就是数据结构。

数据结构在数据的存储和查找时总得较多，比如编程序存储一些数据时，不可能把这些数据存放在固定的空间里，因为这样会很浪费存储空间，这时就需要用到数据结构里的链表，动态存储。

图片.png

1、数组(线性表)：常用的数组有一二三维数组，数据集中有序排列在一块区域

优：便于查找

缺：不便于插入删除，添加元素（因为要移动其它元素）

2、链表：这种结构中以节点形式存储数据，一个节点包括数据位和地址位，数据位存储数据，地址位存储下一个数据的地址。物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现

优：不便于查找

缺：便于插入删除

3、栈：栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈。调用完后立即释放。（由系统自动分配释放）

优：读取速度快，而且数据可以共享。

缺：存在于栈中的数据大小及周期必须是确定的，缺乏灵活性。

4、堆：就是那些由new分配的内存块，他们的释放编译器不去管，由我们的应用程序去控制，一般一个new就要对应一个delete。如果程序员没有释放掉，那么在程序结束后，操作系统会自动收回。（可以说由程序员自身决定创建和释放）

优：可以动态分配内存大小，生存期也不必告诉编译器，因为它是在运行中动态分配内存的。

缺：缺点就是由于是在运行时动态分配内存的，所以读取速度较慢。

5、 队列：队列和栈类似，也是一种特殊的线性表。和栈不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。一般来说，进行插入操作的一端称为队尾，进行删除操作的一端称为队头。队列中没有元素时，称为空队列。（可以说先进先出，后进后出）

优：有序以便于查找等

缺：灵活度不够

6、树：树是典型的非线性结构，它是包括，2个结点的有穷集合K。在树结构中，有且仅有一个根结点，该结点没有前驱结点。在树结构中的其他结点都有且仅有一个前驱结点，而且可以有两个后继结点，m≥0。

优：查找，插入，删除都快

缺：算法复杂

7、哈希表：（散列表）

优：如果关键字已知则存取极快，插入快

缺：删除慢，如果不知道关键词则存取很慢，对存储空间使用不充分

8、图：是另一种非线性数据结构。在线性表中我们把数据元素叫元素，树中将数据元素叫结点，在图数据元素称之为顶点，而边是顶点的有序偶对。如果两个顶点之间存在一条边，那么就表示这两个顶点具有相邻关系。

优：能对现实世界建模

缺：算法慢且复杂

图片.png