数据结构
0 Word Count: 3.2k(words) Read Count: 12(minutes) 数据结构与算法
数据结构
数据
1
| 数据是表述客观事务的符号，是计算机中可以被操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据不仅仅包括整型、实型等数值类型，还包括字符以及声音、图像、视频等非数值类型。
|
数据元素
1
| 是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。
|
数据项
1
| 一个数据元素可以由若干个数据项组成。数据项是数据不可分割的最小单位。
|
数据对象
1
| 数据对象是性质相同的数据元素的集合，是数据的子集。
|
数据结构
1
2
3
4
5
6
7
8
| 数据结构没有官方统一定义
"数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。"
Sartaj Sahni，《数据结构、算法与应用》
"数据结构是ADT(抽象数据类型Abstract Data Type)的物理实现"
Clifford A.Shaffer，《数据结构与算法分析》
"数据结构(data structure) 是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法。"
中文维基百科
在计算机中数据元素并不是孤立杂乱无序的，而是具有内在联系的数据集合。数据元素之间存在的一种或多种特定关系，也就是数据的组织形式--《大话数据结构》
|
数据怎么组织 跟数据的规模有关系，不一样的规模处理起来的难度不一样。
解决问题方法的效率，跟数据的组织方式有关。
逻辑结构与物理结构
逻辑结构
1.集合结构
1
| 集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系。各个数据是“平等”的，他们的共同属性是“同属于一个集合”
|
2.线性结构
3.树形结构
4.图形结构
物理结构
1.顺序存储结构
1
2
| 是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。
要建立一个有9个整型数据的数组时，计算机就在内存中找了片空地，按照一个整型所占位置的大小乘以9，开辟一段连续的空间，于是第一个数组数据就放在第一个位置，第二个数据放在第二个，这样依次摆放。
|
2.链式存储结构
1
| 把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。数据元素的存储关系并不能反映其逻辑关系，因此需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置
|
逻辑结构是面向问题的，而物理结构就是面向计算机的，其最基本的目标就是将数据及其逻辑关系存储到计算机的内存中。
抽象数据类型
数据类型
1
| 数据类型是指一组性质相同的值的集合及定义在此集合上的一些操作的总称
|
抽象数据类型
1
| Abstract Data Type，ADT：是指一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。
|
算法（Algorithm）
1
2
3
4
5
6
7
8
9
| 算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
一个有限指令集
接受一些输入
产生输出
一定在有限步骤之后终止
每一条指令必须：
有充分明确的目标，不可以有歧义
计算机能处理的范围之内
描述应不依赖于任何一种计算机语言以及具体的实现手段
|
算法的五个基本特性
1
2
3
4
5
| 输入、输出、有穷性、确定性和可行性
·输入和输出：算法具有零个或多个输入，至少有一个输出或输出
·有穷性：算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成
·确定性：算法的每一步骤都具有确定的含义，不会出现二义性。算法在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结果。算法的每个步骤被精确定义而无歧义
·可行性：算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。
|
算法设计的要求
1
2
3
4
5
6
7
8
| 正确性：指算法至少应该具有输入。输出和加工处理无歧义性。能正确反映问题的需求、能够得到问题的正确答案。
1.算法程序没有语法错误。
2.算法程序对于合法的输入数据能够产生满足要求的输出的结果
3.算法程序对于非法的输入数据能够得出满足规格说明的结果。
4.算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果
可读性：算法设计的另一个目的是为了便于阅读、理解和交流。
健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。
时间效率高和存储量低
|
时间与空间复杂度
算法效率的度量方法
1
2
3
4
5
6
7
| 1.事后统计法:通过统计,监控,利用计算机计时器对不同算法的运行时间进行比较,从而确定算法效率的高低,但是有非常大的局限性.
2.事前分析估算:在计算机程序编制前,依据统计方法对算法进行估算.
一个高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：
1.算法采用的策略、方法 算法好坏的根本
2.编译产生的代码质量 软件来支持
3.问题的输入规模
4.机器执行指令的速度 计算机硬件性能
|
事后统计法:
1
2
3
4
5
6
|
public static long fun1(long n ){
if(n<=1) return n;
return fun1(n-1)+fun1(n-2);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public static int fun2(int n){
if(n<=1) return n ;
int first=0;
int second=1;
for(int i=0;i<n-1;i++){
int sum=first+second;
first=second;
second=sum;
}
return second;
}
public static void main(String[] args){
System.out.println(fun1(n:4));
}
|
事前分析估算:
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
| public void cal01(int age){
6
if(age>58){
System.out.println("阿姨");
}else if(age>28){
System.out.println("小姐姐");
}else{
System.out.println("美少女");
}
}
int cal02(int n){
int sum=0;
int i=1;
for(;i<=n;i++){
sum=sum+i;
}
return sum;
}
public void cal03(int n){
for(int i=0;i<n;i++){
System.out.println("崔源耕");
}
}
public void cal04(int n){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){n(1+n+n+n)
System.out.println("Cui");
}
}
}
public void cal05(int n){
for(int i=0;i<n;i++){
for(int j=0;i<20;j++){
System.out.println("Cui");
}
}
}
public void cal06(int n){
int i=1;
while(i<n){
i=i*2;
}
}
public void cal07(int n){
for(int i=1;i<n;i=2i){
for(int j=0;j<n;j++){
System.out.println("ayi");
}
}
}
|
空间复杂度
1
| S(n) 根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。
|
时间复杂度
1
2
3
4
5
6
| T(n)=O(f(n))
T(n)表示代码执行时间;
n表示数据规模的大小;
f(n)表示每行代码执行的次数总和.
因为这是一个公式,所有用f(n)来表示.公式中的O,表示代码的执行时间T(n)与f(n)成正比.
大O时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度
|
函数的渐近增长
1
| 算法A 要做2n+3次操作 算法B要做3n+1次操作
|
| 次数 | 算法A（2n+3） | 算法A‘（2n） | 算法B（3n+1） | 算法B’（3n） |
|---|
| n=1 | 5 | 2 | 4 | 3 |
| n=2 | 7 | 4 | 7 | 6 |
| n=3 | 9 | 6 | 10 | 9 |
| n=10 | 23 | 20 | 31 | 30 |
| n=100 | 203 | 200 | 301 | 300 |
1
2
| 输入规模n在没有限制的情况下，只要超过一个数值N，这个函数就总是大于另一个函数，我们称函数是渐近增长的
函数的渐近增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n>N,f(n)总是比g(n)大，那么，我们说f(n)的增长渐近快于g(n)。
|
线性表
1
2
3
4
5
6
7
8
9
| 一个线性表是0个或n个具有相同特性的数据元素的有限且有序数列
数组按照顺讯存储在连续位置的存储器中
数组与列表相比,在特定位置添加或者删除元素成本过高
优点:
空间利用率高
查询速度高效,通过下标来直接存取
缺点
插入和删除比较慢,比如:插入或者删除一个元素时,整个表需要遍历移动元素来重新排一次排序
不可以增长长度,有空间限制,当需要存取的元素个数可能多于顺序表的元素个数时,会出现"溢出"问题,当元素个数远少于预先分配空间时,空间浪费巨大
|
选择排序
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
|
public class SortNum {
public static void main(String[] args) {
int arr[] = { 4, 7, 3, 9, 1 };
int min = -1;
int temp = 0;
for (int i = 0; i < arr.length - 1; i++) {
min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
if (min != i) {
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
for(int num :arr) {
System.out.print(num+"\t");
}
}
}
|
二分（折半）查找法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public static int binarySearch(int[] arr, int num) {
int startIndex = 0;
int endIndex = arr.length - 1;
Arrays.sort(arr);
while (startIndex <= endIndex) {
int midIndex = startIndex + (endIndex - startIndex) / 2;
if (num == arr[midIndex]) {
return midIndex;
} else if (num > arr[midIndex]) {
startIndex = midIndex + 1;
} else {
endIndex = midIndex - 1;
}
}
return -1;
}
|
