数据结构_绪论

绪论之绪论

  突发奇想，在复习数据结构的同时写一些东西来加深理解。
  今年是2020年，希望提前进行考研复习，对2021的考试有所帮助。
  其实除了想记录数据结构的内容，计算机组成原理、前端、算法的一些东西都挺想记下来的，只为自己有益而写吧，目前的水平也帮不到别人。
  先写着，看看效果，好的话就接着写，反之就算了。
  另外，MarkDown还不会用，感觉像一个Latex，不学了，写一点是一点，不会的再查。

数据结构的基本概念

基本概念和术语

数据

数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。

其实这个在很多文献上都是这么说的。

数据元素

数据元素是数据的基本单位，通常作为一个小整体进行考虑和处理。
一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。

举个????：
数据元素->学生信息
数据项 ->(他 / 她)的学号、姓名、性别
最好是别混淆。

数据对象

数据对象是具有相同性质的数据元素的集合，是数据的一个子集。

数据类型

数据类型是一个值的集合和定义在此集合上的一组操作的总称。

1. 原子类型：其值不可再分的数据类型。
2. 结构类型：其值可以再分解为若干成分的数据类型。
3. 抽象数据类型（老师经常说的ADT）：抽象数据组织及与之相关的操作。

###抽象数据类型
抽象数据类型是指一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。
通常用：

1. 数据对象
2. 数据关系
3. 基本操作集

表示抽象数据类型。

数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构包括三方面的内容：

1. 逻辑结构
2. 存储结构
3. 数据的运算

其中，数据的逻辑结构和存储结构是密不可分的，一个算法的设计取决于所选定的逻辑结构，实现依赖于所采用的存储结构。

数据结构三要素

数据的逻辑结构

逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的。数据的逻辑结构分为线性结构和非线性结构。

数据的存储结构

存储结构是指数据结构在计算机中的表示，也称物理结构，它包括数据元素的表示和关系的表示。数据的存储结构是用计算机语言实现的逻辑结构，它依赖于计算机语言。主要的有四种：顺序存储、链式存储、索引存储和散列存储

顺序表是顺序存储的典型；
单链表是链式存储的典型；
索引存储我的理解是用索引项（关键字，地址）来存储，优点是检索速度快，缺点是耗费了空间，且在删增是会修改索引表，耗时较大；
散列存储又叫Hash存储，通过元素的关键字直接计算出该元素的存储地址。

小结

1. 可以用抽象数据类型定义一个完整的数据结构；
2. 有序表属于逻辑结构，而顺序表、哈希表、单链表不是：
   顺序表、哈希表和单链表表示几种数据结构，既描述逻辑结构，又描述存储结构和数据运算。而有序表是指关键字有序的线性表，可以链式存储也可以顺序存储，仅描述元素之间的逻辑关系。
3. 在存储数据时，通常不仅要存储各数据元素的值，而且要存储数据元素之间的关系；
4. 链式存储设计时，结点内的存储单元地址一定连续。

算法和算法评价

算法的基本概念

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。
算法的特性：

1. 有穷性
2. 确定性
3. 可行性
4. 输入
5. 输出

好算法的特性：

1. 正确性
2. 可读性
3. 鲁棒性
4. 效率与低存储量需求

算法效率的度量

时间复杂度

空间复杂度

这里面有很多东西可以说，但有点难说清，比如时间复杂度怎么算鸭，加法规则乘法规则什么的，其实我觉得都知道，只是用文字难说清，所以还是不说了。

????

//O(log2n)
void fun(int n){
   int i = 1;
   while(i <= n){
      i = i * 2;
   }
}

//O(log2n)
x = 2;
while(x < n / 2){
	x = 2 * x;
}

//O(n)
int fact(int n){
	if(n <= 1){
		return 1;
	}
	return n * fact(n - 1);
}

//O(max(m,n))
已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m + n的降序列表，则最坏情况下的时间复杂度

//O(nlog2n)
count = 0;
for(k = 1; k <= n; k *= 2){
	for(j = 1; j <= n; j++){
		count++;
	}
}

//O(n^1/2)
int func(int n){
	int i = 0,sum = 0;
	while(sum < n){
		sum += ++i;
	}
	return i;
}

//O(n^1/3)
void fun(int n){
	int i = 0;
	while(i * i * i <= n){
		i++;
	}
}
……………………

以上是一些例子，可以体会一下。

写在后面

  第一章的概念有点多而且很理论了，空间复杂度很难说，所以重点还是分析时间复杂度，虽然有些不在考纲内，不过这个理解性的记下来也很简单；
  感觉还行吧，如果我学会了用MarkDown画流程图之类的，以后的博客会有点意思的，第一章就先这样了，应该之后的数据结构不会像这样了...