数据结构 比较链表和数组
本帖最后由 hack_hu 于 2018-12-2 16:27 编辑数据结构 比较链表和数组
https://img-blog.csdnimg.cn/20181201203853979.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Mjg4ODQ3,size_16,color_FFFFFF,t_70
思维导图
计算机的资源是有限的 ， 而人对计算机的需求是无限的 。 好的数据机构和算法便是为了更好的满足计算机使用者的需求 ， 而这也是计算机操作系统意义所在。 在学习数据结构的同时 ， 了解一定的计算机操作系统知识有助于更好的理解其意义所在。 而了解数据结构和算法 会更容易明白操作系统的工作原理。
广义上讲 ， 数据结构是数据的存储结构 ， 而算法就是操作数据的方法 。
数据结构和算法的目的在于 提高计算机的资源利用率 ， 实现 “ 快 ” 和 “ 省 ”。 让同一功能的代码用更快的速度运行 ， 这在处理大量数据的程序中尤为重要 ， 那不同的需求的数据该以怎样的结构存储在计算机中能够更加节省资源呢 ？这便是数据结构和算法的意义所在 ， 这在大数据时代尤为重要。
复杂度分析事后统计法
[*]采用代码执行所消耗的计算机资源以及运行时间 ， 对程序代码进行实际的有数据的分析。
[*]不足之处 ： 受硬件的影响较大 ， 不同机器跑出来的结果可能完全不同 。 严重依赖测试环境以及数据规模 ， 很难达到真正的场景实现 ， 而且比较浪费资源。
大 O 复杂度表示法
[*]代码执行的时间 简称 ： 时间复杂度 （ 全名 渐进时间复杂度 ）
[*]只关心执行时间最长的那段代码 。 （ 在分析中忽略计算的常数项 、 以及常量系数 ）
[*]只关心量级最大的那段代码的复杂度。 （ 如 ： 双重循环以及单循环 ， 无论中间的普通代码如何 考虑量级更大的那个 即 双重循环 ）
[*]乘法法则 ： 被嵌套的代码等于外嵌套代码的乘积复杂度
[*]
常见复杂度O (1) 普通代码 ， 不存在任何 循环 、递归语句
例 ：
int flag = 0 , temp=0;
O （ long n ）
示例 ： 时间复杂度为 long ₂nvoid LongN(int n)
{
int i = 1;
while (i < n)
{
i = i*i;
}
}
O ( m + n ) 、 O ( m * n ) 多个不同规模数据 ， 实际复杂度由数据规模来决定
示例 ：void MandN(int m, int n) // 时间复杂度为 O(m+n)
{
int sum = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
sum += j;
}
}
}
最好时间复杂度 。 即 在最理想的情况下执行代码的时间复杂度 。
最差时间复杂度 。 即 在最坏情况下执行代码的时间复杂度 。
平均时间复杂度 。 即 把所有可能的情况乘上相应的概率除以一共有多少种可能 （ 数学上叫做 加权平均数 ）。
均摊时间复杂度 。 一般出现在比较极端的情况下 。 在处理数据时大多数是较低时间复杂度 ， 只有个别情况下时间复杂度较高 。 这时我们把个别较高复杂度分摊给较低时间复杂度 ， 再进行计算平均时间复杂度 ， 使得复杂度的分析更为合理化。
综合分析 冒泡排序
#include <stdio.h>
#include <malloc.h>
void Bubble_Sort(int num[] , int length) // 定义一个冒泡排序的函数
{
int flag = 0 , temp=0;
for (int i = 0; i <length-1; i++)
{
//printf("%d ", sizeof(num) / (sizeof(int) - 1));
for (int j = i+1; j < length; j++)
{
if (num>num) // 按照从小到大排序
{
temp = num;
num = num;
num = temp;
flag = 1; // 若进行了 1 次 排序则改变标记
//printf("是否执行 ");
}
}
if (flag == 0)
break; // 若数组本就是有序的则直接结束循环
}
}
int main()
{
int num[] = { 7 , 4 , 6 , 2 , 3 , 8};
int length = sizeof(num) / sizeof(num[0]);
Bubble_Sort(num , length);
/*
注意 ： 当将数组作为实参传递到另一个函数中时, 另一个函数的形参相当于一个指针变量, 因为将数组的名作为实参时, 就是将数字的首地址作为实参 ,
这样是得不到准确的数组的长度的, 建议的操作是在定义数组的函数中计算数组的长度, 在以实参的形式传递出去, 这样其他的函数变可以获得数组的长度
*/
for (int i = 0; i < length; i++)
{
printf("%d ",num);
}
return 0;
}
分析 ： 最好 时间复杂度 O( n ) 即数组本就是有序排列 只需要循环一次 ， 最差时间复杂度 O( n2 ) , 平均情况时间复杂度 O( n2 ) ，均摊时间复杂度 O(n2)
数组和链表
你可能需要先了解 :
C 语言 初探链表
C 语言 学习第二弹
数组 ， 支持下标随机访问 ， 所以时间复杂度是 O( 1 ) , 但当进行 增删 操作时数组的时间复杂度为 O （ n ）， 执行效率较低
[*]C 、 C++ 、 C# 、 Java 等语言为什么 数组是从 0 开始 ， 而部分语言例如 ：MatLab (数组从1开始)。 历史原因占了大多数 ， 因为 前者都是由 C 语言发展过来的 ， 而 C 中的数组是 从 0 开始
链表 ， 每次访问都要从头开始查找 ， 因此时间复杂度为 O( n ) ， 但进行 增删 操作时 只要改变 插入 or 删除 结点的指针指向即可 ， 所以链表 增删 操作的时间复杂度为 O( 1 )。
通过时间复杂度分析可以明显的看出两者的优势以及劣势 。 在 对数据的访问较为频繁 ，而 增删 操作较少时采用数组存储数据是更为高效的 ， 反之 ， 当需要对数据进行频繁的 增删 操作而较少直接访问数据进行改查时 ， 使用链表会更为高效。 分享快乐 // 冒泡排序
#include <stdio.h>
#include <malloc.h>
void Bubble_Sort(int num[] , int length) // 定义一个冒泡排序的函数
{
int flag = 0 , temp=0;
for (int i = 0; i <length-1; i++)
{
//printf("%d ", sizeof(num) / (sizeof(int) - 1));
for (int j = i+1; j < length; j++)
{
if (num>num) // 按照从小到大排序
{
temp = num;
num= num;
num = temp;
flag = 1; // 若进行了 1 次 排序则改变标记
}
}
if (flag == 0)
break; // 若数组本就是有序的则直接结束循环
}
}
int main()
{
int num[] = { 7 , 4 , 6 , 2 , 3 , 8};
int length = sizeof(num) / sizeof(num);
Bubble_Sort(num, length);
for (int i = 0; i < length; i++)
{
printf("%d ",num);
}
return 0;
}
页:
[1]