数据结构简述

数据结构概述

常用的数据结构有栈，队列，链表，二叉树，红黑树，散列表和位图。

数据结构优点缺点栈顶部元素的插入和取出快除了顶部数据，其他元素都很慢队列顶部和尾部的元素插入和取出快其他元素都很慢链表插入、删除快速查找慢二叉树插入、删除、查找都快删除算法复杂红黑树插入、删除、查找都快算法复杂散列表插入、删除、查找都快数据散列，对存储空间浪费位图节省存储空间不方便描述的复杂的数据关系 栈

栈（堆栈）Stack，允许在同端进行插入（Push）删除（Pop）的特殊线性表。有栈顶（Top），栈底（Bottom），栈顶进行浮动。栈中元素个数为0，为空栈。是先进后出（FILO）线性表。

什么叫线性表???

一个线性表是n个数据元素的有限序列。一个数据元素可以是若干个数据项组成，此时的数据元素成为记录，含有大量记录的线性表叫做文件。

线性表的顺序表示指用一组连续的存储单元（逻辑相邻物理上一定相邻）依次存储线性表中的数据元素。 线性表的链式表示指用一组任意的存储单元（逻辑相邻物理上不一定相邻）存储线性表中的数据元素。

队列

队列是一种只允许在表的前端（队头）进行删除操作（出队）且在表的后端（队尾）进行插入操（入队）作的线性表。没有元素的队列空队列。是一种先进先出（FIFO）线性表。

链表

链表是由一系列节点组成的数据结构，节点在运行过程中可以动态生成。每个节点包含两个部分，存储数据的叫做数据域，存储其他节点地址的叫做指针域。由于链表的数据是随机存储的，插入的时间复杂度O(1)，效率高于线性表和顺序表；链表查找一个节点需要遍历链表中所有的元素，时间复杂度O(n),而线性表和顺表中查找一个节点的时间复杂度O(log n)和O(1)。

顺序表是什么有哪些？

不同结构的插入和查找的时间复杂度的计算和区别。

单向链表

单向链表（单链表）的链接方向是单向的，访问要从头部开始顺序读取。

一个单向链表的节点分为两个部分，1是数据区，用来保存数据，2是指针区，用来存储下一个节点的地址。，最后一个节点的指针是null。

双向链表

双向链表的每个节点的指针域都有两个指针，分别指向其的直接后继和直接前驱节点。这样我们可以从两个方向访问和处理节点数据。

循环链表

表中最后一个节点的指针域指向头结点，整个链表形成一个环。单向的。

是否有双向循环和单向循环链表之分？

散列表

散列表（Hash Table）也叫做哈希表。是根据数据的关键码值（Key-Value）对数据进行存取的数据结构。散列表通过映射函数把关键码值映射到表中的一个位置来加快查找。这个映射函数叫散列函数，存放记录的数组叫作散列表。

• 常用构建散列函数

  • 直接定址法：取关键字或关键字的某个线性函数值为散列地址，即h(key)=key或h(key)=a*key+b,其中a,b为常数。
  • 平方取值：取关键字平方后的中间几位数为散列地址
  • 折叠法：将关键字分割成位数相同的几部分，然后取这几部分的叠加和作为散列地址
  • 除留余数法：取关键字被某个不大于散列表长度m的数p除后得的余数为散列地址。h(key)=key/p, (p