数据结构
数据结构是什么
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
怎么学习数据结构
理解和熟记数据结构的定义
这就跟我们学习使用一门语言是相似的，我们需要记住各种不同类型的数据结构的定义再用代码去实现。不同的数据结构之间的结构差别是很大的，我们需要加深印象以快速的分辨出他们之间的异同。
熟练使用各种数据结构进行编程
当你能熟练记住各种数据结构的定义的时候，此时只是说明你记住了。编程是一门实操性很强的技能，我们需要通过不断的练习才能说我们是真正的学会了！自己编码实现的过程能让我们对底层的实现原理更加深刻。
根据情景使用合适的数据结构
这个环节属于数据结构的实际应用。每个数据结构被创造出来都是为了解决相应的问题。每个问题的性质都不一样，也没有通用的数据结构。我们要分析问题的性质，根据问题的特点选择最合适的数据结构。
时间复杂度
时间复杂度表示程序的运行时间与数据规模增长的变化趋势，也叫渐进时间复杂度。时间复杂度一般有最差时间复杂度、最好时间复杂度和平均时间复杂度。
举个例子
#include <stdio.h>
int findNumIndex(int n,int nums[]){
for(int i = 0;i < sizeof(&nums) ;i ++){
if(nums[i] == n){
return i;
}
}
return -1;
}
int main(){
int nums[] = {1,2,3,4,5,6,7,8};
int index = findNumIndex(3,nums);
printf("numIndex = %d\n",index);
return 0;
}
我们分析findNumIndex这个函数的代码。我们假定一行代码的执行时间为time，findNumIndex函数的代码一共需要执行 nums.length * 2 + 1个time。不难看出，我们代码的执行时间跟数组的长度和n的值是正相关的，数组越长，我们的代码执行时间也越长，n的位置越往后或者不存在，代码的执行时间越长。接下来我们计算下时间复杂度。
最好情况下，n永远都是nums的第一个元素。时间复杂度为3 * time
最差情况下，n不存在nums之中，时间复杂度为 nums.length * 2 + 1
平均时间复杂度，有n+1种情况，每种情况需要遍历的次数不一致。得出(1+2+3+4……+n+n)/(n+1) = n(n+3)/2(n+1)
你以为这就结束了？
在计算时间复杂度的时候，我们需要记住常数是可以忽略不记的。同时使用符号O来表示时间复杂度。
以上时间复杂度简化下为：
最好：O(1)
最坏：O(n)
平均：O(n)
常见的算法时间复杂度：O(1),O(n),O(n2),O(log n),O(n * log n)
空间复杂度
空间复杂度用来描述我们代码在执行过程中额外开辟的空间。
空间复杂度的计算原则跟时间复杂度是一致的。
举个例子：
#include <stdio.h>
//空间复杂度是O(1)的，没有额外开辟其他的地址空间。常数忽略
int findNumIndex(int n,int nums[]){
for(int i = 0;i < sizeof(&nums) ;i ++){
if(nums[i] == n){
return i;
}
}
return -1;
}
// 空间复杂度为O(n)，额外开辟的空间跟nums的长度正相关
int * copyNums(int nums[],int * p){
p = (int *)malloc(sizeof(&nums) * sizeof(int));
for(int i = 0;i < sizeof(&nums);i ++){
*(p + i) = nums[i];
}
return p;
}
数据的内存分布方式
在内存当中，数据的分布方式有两种，一种是顺序结构，一种是链式结构。
顺序结构
数据的内存位置在内存中是连续的。即是一块规整的内存空间，每个逻辑上相邻的元素在物理上也是相邻的。优点是支持数据的数据的随机访问，数据访问速度快。缺点是在内存分配是要求是分配的内存空间连续的，元素更新代价大。常见的数据结构有数组。
链式结构
数据在内存当中的位置是不确定的。逻辑上相邻的元素在物理上可能不相邻，元素之间的连续访问需要通过指针去记录下一个元素的物理位置。优点是可以充分利用内存空间，允许内存是散乱的。缺点是需要花费额外的空间去保存元素的位置，不支持随机访问，元素增加删除代价小。常见的额数据结构有链表等。
非常感谢你能看到这里，欢迎关注我的vx公众号：BitLegend,我们下期见！
