本文共 2067 字，大约阅读时间需要 6 分钟。
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
这就跟我们学习使用一门语言是相似的，我们需要记住各种不同类型的数据结构的定义再用代码去实现。不同的数据结构之间的结构差别是很大的，我们需要加深印象以快速的分辨出他们之间的异同。
当你能熟练记住各种数据结构的定义的时候，此时只是说明你记住了。编程是一门实操性很强的技能，我们需要通过不断的练习才能说我们是真正的学会了！自己编码实现的过程能让我们对底层的实现原理更加深刻。
这个环节属于数据结构的实际应用。每个数据结构被创造出来都是为了解决相应的问题。每个问题的性质都不一样，也没有通用的数据结构。我们要分析问题的性质，根据问题的特点选择最合适的数据结构。
时间复杂度表示程序的运行时间与数据规模增长的变化趋势，也叫渐进时间复杂度。时间复杂度一般有最差时间复杂度、最好时间复杂度和平均时间复杂度。
举个例子
#includeint 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//空间复杂度是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,我们下期见！
转载地址：http://ltden.baihongyu.com/