数据结构笔记

数据结构

集合结构

各个元素属于同一个集合，元素之间平等

线性结构

数据元素之间是一对一的关系,数组就是这种结构

• 线性表的顺序表示：用一组连续的储存单位构成的
• 链式表示：用一组任意的存储单位来存放数据
  1. 需要存储一个知道后继元素的指针
  2. 数据域-存放自身数据

链表分为，单向列表和双向列表

• 单向链表：头指针指向头结点，其他元素指针指向下个结点，尾结点指针为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();

实现思想：

1. 左括号进栈
2. 右括号检查栈是否为空，不为空取得栈首元素比较，匹配成功，释放栈首元素，继续循环数组中的数据并执行switch比较
   
   

表达式求值(难)

队列应用

Queue<> s = new SequenceQueue()

模拟排队任务处理

队列批量任务处理

串、矩阵和广义表

串的顺序存储与实现

串的顺序存储结构用数组来存储串中的字符序列

• 字符串的连接与扩容：
  1. 首先比较存入串的长度与当前串的长度对比，可以容纳则直接存储
  2. 无法存储，则将当前串长度加长，赋值一个新的字符数组，数组长度为当前串长度+新增串长度
  3. 恢复当前串的内容，并将新串的内容加入当前串尾部
     
     

矩阵（java中多维数组）

广义表

广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表

树和二叉树

树（Tree）是若干个结点组成的有限集合，其中必须有一个结点是根结点，其余结点划分为若干个互不相交的集合，每一个集合还是一棵树，但被称为根的子树。注意，当树的结点个数为0时，我们称这棵树为空树
==特点：==

1. 一个节点最多只能有一个父节点
2. 一个节点除了子节点和父节点不能有其他兄弟节点
   
   

顺序存储和链式存储

• 空间角度

就是开辟一段连续的空间，用来存顺序表，这一段空间所有的位置都用来存储我们需要的数据信息，没有空间的浪费。所以利用率达到了100%【也就是存储密度是1】。然而链式结构中的节点不仅存储了数据，还保存了指针，然而指针并没有存储我们用到的数据，所以说，链式存储的存储密度是小于1的

• 时间性能角度

1. 读取：顺序存储只要通过指针直接读取就可以，链式存储却要通过next的指针获取下个元素，一次次访问
2. 插入和删除：顺序存储要在操作后改变后面元素的角标维护等，而链式存储只需要改变next指针即可