什么是数据结构


数据结构

数据结构是计算机中存储、组织数据的方式。通常情况下,精心选择的数据结构可以带来最有效率算法。
利用代码解决实际问题,最重要的是解决问题的效率,主要是两个因素:

  • 空间的分配效率(物理存储结构)
  • 算法的巧妙程度(逻辑结构:一对一线性、一对多树性、多对多关系网)
    • 数据对象在计算机中的组织方式
    • 数据对象必定与一系列加在其上的操作相关联
      (完成这些操作所用的方法就是算法)

抽象数据类型

抽象数据类型的两个要素(数据对象集、数据集合相关联的操作集)

首先理解”抽象”的意义:

  • 描述数据类型的方法不依赖于具体实现,这种描述,与存放数据的机器无关,与存放数据的物理结构无关,与实现操作的算法和编程语言无关。只描述数据对象集和相关操作集”是什么”,并不涉及如何实现的问题。
  • 好的描述,就是提高函数、算法的包容性,尽可能让多的种类的数据类型参与计算。

算法

什么是算法?

  • 一个有限的指令集
  • 接受一些输入(亦可无)
  • 产生输出结果
  • 一定在有限的步骤后停止
  • 每一条指令必须有明确的的目标,在计算机的处理范围之内,“描述”时,不依赖于任何一种计算机语言以及实现手段。

什么是好的算法?(两个指标)

  • 空间复杂度S(n)——根据算法写成的程序在执行时占用存储空间的长度。
  • 时间复杂度T(n)——根据算法写成的程序在执行时消耗时间的长度。
    (两者都与数据规模有关)
    一、空间复杂度
void PrintN(int N){………………//这个是函数,下面是它的功能
    if(N){………………………………………//若N不为0,则就执行
        PrintN(N-1);……………//此行的意义就是调用自己,即再进行判断,再执行功能
        printf("%d/n",N);//此行执行无关上一行
    }
}

如果说N = 1000000000000,则就出现系统报错,原因是,函数在每一次调用时都是需要申领空间的,数据规模太大就导致内存爆满。当然存在不需要申领空间的方式实现该目的,所以这也是我们需要注意的地方。
二、时间复杂度

代码一:
  double f(int n,double a[],double x){
     int i;
     double p = a[0];
         for(i = n; i > 0; i++);{
             p += (a[i]*pow(x,i));
         }
     return p;
   }

代码二:
   double f(int n, double a[], double x){
       int i;
       double p = a[n];
       for(i = n; i>0; i--){
           p = a[i - 1] + x*p;
       }
   return p;
   }

若果说n为10000000000,代码一的用时必定比代码二的用时多,原因是前者的乘法运算量远远大于后者,并且乘除法用时是要多于加减法的。程序运行的总用时,是各个环节时间的累积

原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/288339.html

(0)
上一篇 2022年9月9日
下一篇 2022年9月9日

相关推荐

发表回复

登录后才能评论