-
Notifications
You must be signed in to change notification settings - Fork 25
/
数据结构.c
62 lines (54 loc) · 2.63 KB
/
数据结构.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
什么是数据结构
数据结构不是一门研究数据计算的学科,而是研究数据与数据之间关系的。
数据结构的起源:美国的高纳德教授,于1968年开设一门《基本算法》的课程,开创的数据结构和算法的先河。
提出一个公式:数据结构 + 算法 = 程序
数据结构的基本概念:
数据:能够输入计算机的描述客观事物的符号。
数据项:描述事物的其中一项指标。
数据元素:用于描述一个完整的事物。
数据结构:由数据元素和元素之间的关系构成的一个整体。
算法:数据结构所具备的功能(解决问题的方法)。
四种基本类型的数据结构
集合:元素之间没有任何关系
线性表:元素之间存在一对一关系(数组)
数组、链表、功能受限的表(栈,队列)
树:元素之间存在一对多关系
普通树、二叉树、完全二叉树、满二叉树、有序二叉树
图:元素之间存在多对多关系
邻接表、表的遍历(深度优先、广度优先)、最短路径
数据结构的存储方式(物理结构):
顺序:在一块连续的内存空间上存储元素与元素之间的关系
优点是查找速度快(随机访问),不易产生内存碎片,但是对内存要求高,添加删除不方便。
非顺序(链式):元素随机存储内存空间中,元素中存储指向其他元素的地址。
优点是对内存要求低,添加删除方便,查找速度慢,不能随机访问,容易产生内存碎片。
逻辑结构和存储结构的关系
表:顺序/链式
树:顺序/链式
图:混合
每种逻辑结构用什么物理结构存储并没有明确规定,通常是根据难易程度、时间和空间上的要求,选择最合适的存储物理结构。
数据结构的运算
1、创建
2、销毁
3、添加元素
4、删除元素
5、修改元素
6、查找元素
7、排序
8、遍历
9、访问
表:
顺序表(存储结构)
1、设计数据结构
2、分析所具备的算法
3、实现算法
4、使用算法
链式表(存储结构)
功能受限的表:
栈(逻辑结构)
限制为只有一个端口进出元素,就导致先进后出的特性。
顺序栈
链式栈
队列(逻辑结构)
限制为只有2个端口进出元素,一个只管进,另一个只管出,就导致先进先出和特征。
顺序队列
链式队列