当前位置:首页 » 数据结构精品文章 » 正文

数据结构知识点总结(七)

2146 人参与  2018年09月10日 21:13  分类 : 数据结构精品文章  评论

数据的逻辑结构分为线性结构和非线性结构两大类,这两类结构各自的特点是什么?

线性结构的特点是:在结构中所有数据成员都处于一个序列中,有且仅有一个开始成员和一个终端成员,并且所有数据成员都最多有一个直接前驱和一个直接后继。例如,一维数组、线性表等就是典型的线性结构。

非线性结构的特点是:一个数据成员可能有零个、一个或多个直接前驱和直接后继。例如,树、图或网络等都是典型的非线性结构。

什么是数据结构? 有关数据结构的讨论涉及哪三个方面?

数据结构是指数据以及相互之间的关系。记为:数据结构 = { D, R }。其中,D是某一数据对象,R是该对象中所有数据成员之间的关系的有限集合。

有关数据结构的讨论一般涉及以下三方面的内容:

  数据成员以及它们相互之间的逻辑关系,也称为数据的逻辑结构,简称为数据结构;

  数据成员极其关系在计算机存储器内的存储表示,也称为数据的物理结构,简称为存储结构;

  施加于该数据结构上的操作。

数据的逻辑结构是从逻辑关系上描述数据,它与数据的存储不是一码事,是与计算机存储无关的。因此,数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型,是数据的应用视图。

数据的存储结构是逻辑数据结构在计算机存储器中的实现(亦称为映像),它是依赖于计算机的,是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算,每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。

什么是算法? 算法的5个特性是什么?

通常,定义算法为"为解决某一特定任务而规定的一个指令序列"

一个算法应当具有以下特性:

 有输入。一个算法必须有0个或多个输入。它们是算法开始运算前给予算法的量。这些输入取自

于特定的对象的集合。它们可以使用输入语句由外部提供,也可以使用赋值语句在算法内

给定。

 有输出。一个算法应有一个或多个输出,输出的量是算法计算的结果。

 确定性。算法的每一步都应确切地、无歧义地定义。对于每一种情况,需要执行的动作都应严格地、

清晰地规定。 

 有穷性。一个算法无论在什么情况下都应在执行有穷步后结束。

 有效性。算法中每一条运算都必须是足够基本的。就是说,它们原则上都能精确地执行,甚至人们

仅用笔和纸做有限次运算就能完成。 

一个求时间复杂度问题的分析

n>=10,下面程序段的时间复杂度是( )。

        for(i=10; i<n; i++)        
        {
             j=k=0;
            while (j+k<=i)
             if(j>k) k++;
            else  j++;
        }

AOlog2n  BO(n)    CO(nlog2n)   DO(n2) 

解答:

1)我们看内部的while 循环还是走了一个i;

2k j 走,jk走,但是k+j还走了一个 i

3)那么 执行的次数 10 11 .... +n= (1+2 +....+n) - (1 + 2 + 3 +....+9) = n*(n-1)/2 常数

4)因此 时间复杂度为o(n^2)

在一个具有n个结点的有序单链表中,插入一个新的结点并使之仍然有序的时间复杂度是( )。

A. O(n)    B. O(log2n)     C. O(1)    D. O(n^2)

条件: 有序链表

可以从头查起,链表要一个一个的走,一个一个的比较,则时间复杂度为O(n)

时间复杂度分析

        (1)         
        int i = 1;
         while(i<=n)
         {i=i*3;}
        (2)
         int i,j;
         for(i=0;i<n;i++)
         {
           for(j=0;j<n;j++)
            {x++}
          }

解答:

本题是求复杂度的问题,同时又是用计算机语言(C语言)描述的程序,这就要求大家能读懂程序,有清楚时间复杂读的概念。

算法与数据结构主要是考察大家对实际问题的提炼,并实现大家对自己设计算法的分析,从而将时间复杂度大的算法改成时间需求小的算法。

大家不要以为现在的计算机的cpu是奔腾,双核了,算法的时间复杂度就无关了,这是错误的。

请看一个简单的例子:求斐波那契函数的递归算法

      int f( int n)    
       {
          if(n == 1) return 1;
          if(n == 2) return 1;
          return f(n-1)+f(n-2);
       }

1)这个时间复杂度:可以估算一下,把这个问题可以看成一个树,如果是一个完全二叉树则是2^n,但 是这不是个完全二叉树,可以看成一个完全二叉树。大家可以找一下组合数学,这个复杂度大约为[(1+2.236)/2]^n 约等于(1.6)^n;

2)可以看出:如果计算机的执行一次加法的耗时为t  即使t非常小,但是仍然是一个常量, lim[t * (1.6)^n] = t * lim(1.6^n)  n趋于无穷时,运算时间为无穷,因此即使再好的机器,没有好的算法,也是死慢。

3)上述两个问题的时间复杂度为O(n)  O(n^2) ;

来源:我是码农,转载请保留出处和链接!

本文链接:http://www.54manong.com/?id=343

数据结构  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!