- 1.什么是数据结构
- 1.数据结构的起源
- 2.数据结构相关基础概念
- 3. 数据结构的三个方面
- 2.数据结构的逻辑和存储关系
- 1.逻辑关系
- 2.存储(物理)关系
- 1.顺序结构
- 2.链式结构
- 3. 逻辑结构与存储结构的关系
- 3. 数据结构的运算
- 4.顺序表和链式表实现
- 5.功能受限的表结构
- 1.栈
- 2.队列
- 6.封装链表：
- 1、单链表
- 2、静态链表
- 3、循环链表
- 4、双向链表
1968年，美国高德纳教授，《计算机程序设计艺术》第一卷《基本算法》，开创了数据结构和算法的先河
数据结构是研究数据之间关系和操作的学科，而非计算方法
数据结构+算法=程序
数据结构+算法=程序 美国沃斯提出 这句话揭示了程序的本质
数据：所有能够到计算机中，能够被程序处理的描述客观事物的符号
数据项：有独立含义的数据的最小单位，也称为域
数据元素：组成数据的有一定含义的基本单位，也叫做节点、节点、记录
数据结构：相互之间存在一种或多种特定关系的数据元素的集合
算法：数据结构中所具备的功能、解决某种特定问题的方法
数据的逻辑关系
数据的存储关系
数据结构的运算
集合： 数据元素同属于同一个集体，但元素之间没有任何关系
线性结构：数据元素之间存在一对一关系
树型结构：数据元素之间存在一对多关系
图型结构：数据元素之间存在多对多关系
数据元素存储在连续的内存中，用数据元素的相对位置来表示关系
优点：支持随机访问、访问查找效率极高、适合用于查找数据频繁的结构
缺点：插入、删除时效率低不方便、内存空间利用率低、要求高
数据元素存储在彼此相互独立的内存中，每个独立的元素也叫做结点，每个结点中增加一项数据项用于存储其他相关结点的地址，以此表示结点之间的关系
优点:插入、删除更方便、空间利用率极高、对内存要求不高
缺点：不支持随机访问、只能从头到尾逐个访问
注意：逻辑结构、存储结构采用哪种根据实现难度、空间、时间要求、操作习惯等方面综合考虑选择合适的结构
线性表 顺序 链式
树 链式 顺序
图 顺序+链式
1、创建数据结构 create creat 2、销毁数据结构 destory 3、清空数据结构 clean 4、数据结构排序 sort 5、插入元素 insert 6、删除元素 delete 7、访问元素 access 8、查询元素 query 9、修改元素 modify 10、遍历数据结构 ergodic show print4.顺序表和链式表实现
顺序表
数据项：
存储元素的连续内存首地址
表的容量
当前元素的数量
运算：
创建、销毁、清空、插入、删除、访问、查询、修改、排序、遍历
注意：
1、要保持数据元素的连续性
2、不要越界
链式表：list
元素(结点)的数据项：
数据域：可以是任何类型的若干个数据项
指针域：指向下一个结点
由若干个结点通过指针域连接到一起就形成了链表
不带头结点的单链表：
第一个结点的数据域存储有效数据
缺点：添加、删除结点时，可能会修改指向第一个结点的指针，参数需要使用二级指针，才能更改指针的指向，比较麻烦
带头结点的单链表：
第一个结点的数据域不存储有效元素，仅仅只是使用它的指针域永远指向链表第一个数据有效的结点
对表结构的部分功能加以限制，形成特殊的表结构1.栈
只有一个进出口的表结构，先进后出，FILO
顺序栈：
数据域：
存储元素的连续内存首地址
栈的容量
栈顶的位置
运算：
创建、销毁、入栈、出栈、栈顶、栈满、栈空
栈的应用：
1、函数的调用、栈内存特点
2、生产者和消费者模型(仓库->栈)
3、表达式解析 3-3*20/2
链式栈：
栈结构数据项：
栈顶结点
结点数量
运算：
创建、销毁、入栈、出栈、栈空、栈顶
2.队列
有两个端口，一个端口只能入队，另一个只能出队
先进先出 FIFO
顺序队列：
数据项：
存储元素的连续内存首地址
容量
队头下标 //出队
队尾下标 //入队
运算：
创建、销毁、入队、出队、队空、队满、查队头、查队尾、数量
顺序队列的注意点：
由一维数组+队头下标front+队尾下标tail组成，入队tail++，出队front++，为了让队列能够反复使用，我们把队列想象成一个环，因此当front和tail+1后都需要用队列容量求余再重新赋值
front =(front+1)%cal; tail=(tail+1)%cal; 如何判断队空、队满： 额外申请一个元素的内存 队空：front ==tail 队满：（tail+1）%cal=front 代价是空了一个位置不能使用，计算数量时较为麻烦(最常考) 计算数量：(tail-front+cal)%cal
另一种方式是队列结构中多增加一项数据项用于记录队列中元素个数，判断空或满直接判断该数据项即可，更方便
链式队列：
由链表结点组成的队列结构
数据项：
队头指针
队尾指针
结点数量
运算：
创建、销毁、入队、出队、队空、队头、队尾
队列应用：
1、消息队列
2、树的层序遍历使用队列
3、图的广度优先遍历使用队列
4、封装线程池、数据池
尾添加的效率低、非法下标的判断效率也非常低
1、单链表 结点：
数据域
指针域
单链表数据项：
头结点
尾结点：
结点数量
2、静态链表
结点：
数据域
游标
静态链表的结点存储在连续的内存中，通过游标来访问下一个结点
这种链表在插入删除时需要修改游标的值，而不用申请、释放结点内存就可以达到类似链式结构的效果
牺牲了随机访问的功能、也没达到链表动态申请内存的效果，只是给没有指针的编程语言实现链表的一种方式，适用范围不大
3、循环链表
链表的最后一个结点的next不再指向NULL，而是指向头结点，这种链表称为单向循环链表，简称循环链表
它好处是可以通过任意结点来遍历整个链表
4、双向链表
结点：
前驱指针 prev
数据域
后继指针 next
