数据结构
集合结构
各个元素属于同一个集合，元素之间平等
线性结构
数据元素之间是一对一的关系,数组就是这种结构
- 线性表的顺序表示：用一组连续的储存单位构成的
-
链式表示：用一组任意的存储单位来存放数据
- 需要存储一个知道后继元素的指针
- 数据域-存放自身数据
链表分为，单向列表和双向列表
- 单向链表：头指针指向头结点，其他元素指针指向下个结点，尾结点指针为NULL
- 双向链表：头指针指向头结点，其他元素包含两个方位的指针，尾结点指针为NULLL
-
循环表：尾指针指向头结点，单向和双向链表都能做循环链表
==总结：双向链表查询更快，但是维护起来，增删没有单向链表快，因为有两个指针需要维护==
树形结构
元素之间存在一对多的层次关系
图形结构
数据元素多对多
java中的基本数据类型
- int
- double
- long
- float
- short
- byte
- character
-
boolean
数据的物理结构（储存结构）
有序：在储存器中占用的是一片连续的储存空间
- 索引存储、
- 散列存储
链表：地址不连续，随意储存
栈应用（先进后出）
- 顺序栈：计算机中连续的储存单元构成的栈
- 栈链：由本身内容和后继指针组成，无栈满问题，空间可扩充，删除插入都在栈顶执行
==判断栈是否为空==
st.top==-1
栈和队列的应用
1数制转换
将十进制数N转换为r进制的数，N=3467，r=8为例
N | N/8(整除) | N%8(整除) | |
---|---|---|---|----
3467 | 433 | 3 | 低
433 | 54 | 1 |
54 | 6 | 6 |
6 | 0 | 6 | 高
所以3467(十进制)=6613(八进制)
转换进制数按从低位到高位，输出通常是高位到地位，因此可以用栈来实现
算法思想:
当N>0是将N%r压入栈中，当N的0时将栈内容依次释放
2栈实现括号匹配
Satck<> s = new SequenceSatck();
实现思想：
- 左括号进栈
- 右括号检查栈是否为空，不为空取得栈首元素比较，匹配成功，释放栈首元素，继续循环数组中的数据并执行switch比较
表达式求值(难)
队列应用
Queue<> s = new SequenceQueue()
模拟排队任务处理
队列批量任务处理
串、矩阵和广义表
串的顺序存储与实现
串的顺序存储结构用数组来存储串中的字符序列
-
字符串的连接与扩容：
- 首先比较存入串的长度与当前串的长度对比，可以容纳则直接存储
- 无法存储，则将当前串长度加长，赋值一个新的字符数组，数组长度为当前串长度+新增串长度
- 恢复当前串的内容，并将新串的内容加入当前串尾部
矩阵（java中多维数组）
广义表
广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表
树和二叉树
树（Tree）是若干个结点组成的有限集合，其中必须有一个结点是根结点，其余结点划分为若干个互不相交的集合，每一个集合还是一棵树，但被称为根的子树。注意，当树的结点个数为0时，我们称这棵树为空树
==特点：==
- 一个节点最多只能有一个父节点
- 一个节点除了子节点和父节点不能有其他兄弟节点
顺序存储和链式存储
- 空间角度
就是开辟一段连续的空间，用来存顺序表，这一段空间所有的位置都用来存储我们需要的数据信息，没有空间的浪费。所以利用率达到了100%【也就是存储密度是1】。然而链式结构中的节点不仅存储了数据，还保存了指针，然而指针并没有存储我们用到的数据，所以说，链式存储的存储密度是小于1的
- 时间性能角度
- 读取：顺序存储只要通过指针直接读取就可以，链式存储却要通过next的指针获取下个元素，一次次访问
- 插入和删除：顺序存储要在操作后改变后面元素的角标维护等，而链式存储只需要改变next指针即可
