一.堆,栈,树,图,数组,链表,队列,哈希表
1..堆:是一种特殊的数据结构,可以看做是一棵树的数组对象。
特点:
1.堆中某个节点的值总是不大于或不小于父节点的值。
2.堆总是一个完全二叉树。
3.如果父节点是堆中最大的值,那么这个堆就叫大顶堆;反之则反。
4.因为堆有序的特点,一般用来做数组排序,称为堆排序。
2.栈:是一种特殊的线性表,仅能在线性表的一端操作,栈顶允许操作,栈底不允许操作。
特点:
1.先进后出,或者说是后进先出。
2.从栈顶放入元素的操作叫入栈,取出元素叫出栈。
3.树:是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合(有限集),n=0时称为空树。
特点:
1.每个节点有零个或多个子节点。
2.没有父节点的节点称为根节点。
3.每一个非根节点有且只有一个父节点。
4.除了根节点外,每个子节点可以分为多个不相交的子树。
4.图:图是由结点的有穷集合V和边的集合E组成。其中,为了与树形结构加以区别,在图结构中常常将结点称为顶点,边是顶点的有序偶对,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。
5.数组:数组是能在内存中连续储存多个元素的结构,他在内存中分配也是连续的,数组中的元素可以通过下标进行访问,数组下标从0开始。
优点:
1.按照索引查询元素速度快。
2.按照索引遍历数组方便。
缺点:
1.数组的大小固定后就无法扩容。
2.数组只能存储同一种类型的元素。
3.添加、删除元素慢,因为需要移动其他元素。
6.链表:是一系列存储数据元素的单元通过指针串联形成的。
特点:
1.因此链表单元至少有两个域,一个域是存储数据元素的内存空间,另一个或两个是指向其他单元的指针。这里具有一个数据域和多个指针域的存储单元通常称为节点(node)。
2.在内存中非连续,非顺序的数据存储结构。
优点:
1.不需要初始化容量,可以任意加减元素。
2.添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可,所以添加,删除很快。
缺点:
1.因为含有大量的指针域,占用空间较大。
2.查找元素需要遍历链表来查找,非常耗时。
7.队列:与栈一样,也是一种线性表,不同的是,队列可以在一端添加元素,在另一端取出元素,也就是:先进先出。从一端放入元素的操作称为入队,取出元素为出队。
8.哈希表:也叫散列表,是根据关键码和值 (key和value) 直接进行访问的数据结构,通过key和value来映射到集合中的一个位置,这样就可以很快找到集合中的对应元素。