一、数据结构的分类

数据结构就是存在的一种或多种特定关系的数据元素的集合。

1.1 逻辑结构

逻辑结构：数据对象中数据元素之间的相互关系。

1.1.1 线性结构

对于线性结构中元素存取方法的不同又可以分为：

• 直接存取结构（直接存取，无需先访问前驱）：数组、链表等
• 顺序存取结构（只能从表的一端或两端按序逐个访问到指定元素）：栈、队列等
• 字典结构（支持关键码索引）：哈希表

---

1.1.2 非线性结构

跟据元素之间关系的不同，又可以分为层次结构和群结构：

• 层次结构（按照层次划分的元素集合）：比如树形结构
  

• 群结构（所有数据元素之间无顺序关系）：比如集合结构、图结构
  
  

提示：还有一种图的特殊形式：即网络结构，他给每条边都赋予了一个权值，指明了遍历图时经过此边的消耗。

---

1.2 物理结构

物理结构：数据的逻辑结构在计算机中的存储形式。

数据结构的四种存储结构（物理结构）

1. 顺序存储
   把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系由存储单元的邻接位置关系来体现。
2. 链式存储
   把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。很显然这样的存储关系并不能反映其逻辑关系，因此需要指针存放与其相关联的数据元素的地址。
3. 索引存储
   该方法在存储元素信息的同时，还建立附加的索引表。索引表中的索引项由关键码和地址构成，关键码唯一标识元素，地址指示结点所在的物理位置。如：
4. 散列存储
   根据节点的关键码，通过一个函数计算，直接得到该节点的存储地址。

总结：

• 以上四种基本的存储结构既可以单独使用，也可以组合起来对数据结构进行存储映像。
• 同一个逻辑结构采用不同的物理结构，可以得到不同的存储表示。选择何种物理结构来表示相应的逻辑结构，主要考虑运算时间和空间要求以及算法的简单性。

---

二、如何选择数据结构

如何转换？
当面对一个实际问题时，我们首先遇到的问题是如何将复杂的信息转换成数据结构。核心技术就是分解与抽象。
先将具体问题抽象成数据结构（逻辑）：

1. 划分出数据的层次：数据（所有学生信息），数据元素（每个学生的信息），数据项（学生姓名等）
2. 通过抽象，舍弃数据元素的具体内容，得到数据的逻辑结构。（可以使用数组、链表、哈希表等作为逻辑结构）
3. 通过分解将处理要求划分成各种功能，再通过抽象舍弃实现细节，得到运算的定义。（录取->增，开除->删等）

再从抽象的数据结构（逻辑）到具体实现（存储+运算）：
通过增加对实现细节的考虑进一步得到存储结构和实现运算，从而完成设计任务。

如何选择？
当为解决某一问题而选择数据结构时，应当执行以下三个步骤：

1. 分析问题，确定算法遇到的资源限制（内外存空间和执行时间限制）
2. 确定必须支持的基本运算，度量每个运算所受到的资源限制。基本运算包括：增、删、查。
3. 选择最接近这些资源开销的数据结构。

提示：根据这三个步骤选择数据结构，实际上贯彻了一种以数据为中心的设计观点。

---

三、算法性能分析与度量

3.1 大O渐进表示法（大O阶）

---

3.2 时间复杂度

算法中基本操作的执行次数，为算法的时间复杂度（不是算法执行所需的时间）

实例一：O(M+N)

---

实例二：O(1)

---

实例三：最坏情况

当一个算法随着输入不同时间复杂度也不同，时间复杂度做悲观的预期，看最坏的情况。所以函数strchr的时间复杂度为 O(N)

---

实例四：冒泡排序

//冒泡排序
void BubbleSort(int *arr, int n){

	int i = 0;
	int j = 0;
	int tmp = 0;
	
	for ( i = n - 1; i > 0; i--)
	{
		bool exchange = false;
		for ( j = 0; j < i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
				exchange = true;
			}
		}
		if (!exchange)
		{
			return;
		}
	}
}

冒泡排序的时间复杂度：O(n^2)

---

实例五：二分查找法（折半查找法）

//二分查找法
int BinarySearch(int *a, int arrsize, int k){

	int left = 0;
	int right = arrsize-1;
	
	while (left <= right)
	{
		int mid = (right + left) / 2;
		if (k < a[mid])
		{
			right = mid-1;
		}
		else if (k > a[mid])
		{
			left = mid+1;
		}
		else
		{
			return mid;
		}
	}
	return -1;
}

二分查找法的时间复杂度：O(logN)

---

实例六：递归法求斐波那契数

//递归法求斐波那契数
int Fib(int k){
	if (k < 3)
	{
		return 1;
	}
	else
	{
		return Fib(k - 1) + Fib(k - 2);
	}
}

递归法求斐波那契数的时间复杂度：O(2^N)

---

3.3 空间复杂度

空间复杂度算的是算法运行额外需要的变量的个数（不是额外需要的字节数）

实例一：冒泡排序

---

实例二：递归法求斐波那契数

• 空间是可以重复利用，不累计的（函数执行完毕释放栈帧，循环中的变量出作用域被销毁）
• 递归函数的空间复杂度=递归调用的层数 * 每次递归需要的额外变量个数
• 时间是一去不复返，累计的
• 递归函数的时间复杂度=递归调用的次数 * 每次递归的执行次数

---

3.4 常见复杂度的对比

---

3.5 相关例题

例题一：消失的数字

//消失的数字
int func(int* arr, int arrsize){
	int i = 0;
	int num = 0;
	
	for (i = 0; i < arrsize; i++)
	{
		num ^= i;
		num ^= arr[i];
	}
	num ^= arrsize;
	return num;
}

例题二：旋转字符串

int main(){
//旋转数组	
	int arr2[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
	int k = 3;
	int arrsize = sizeof(arr2) / sizeof(arr2[0]);

	printf("before:\n");
	for (int i = 0; i < arrsize; i++)
	{
		printf("%d ", arr2[i]);
	}
	printf("\n");

	k = k % arrsize;
	Reverse(arr2, 0, arrsize - 1 - k);
	Reverse(arr2, arrsize - k, arrsize - 1);
	Reverse(arr2, 0, arrsize - 1);

	printf("after:\n");
	for (int i = 0; i < arrsize; i++)
	{
		printf("%d ", arr2[i]);
	}
	printf("\n\n");

	system("pause");
	return 0;
}

void Reverse(int* arr, int left, int right){

	int tmp = 0;

	while (left < right)
	{
		tmp = arr[left];
		arr[left] = arr[right];
		arr[right] = tmp;
		left++;
		right--;
	}
}