为什么学习数据结构

计算机是什么

计算机是一种处理数据的机器

输入=〉存储 =〉输出
        ||
       处理

计算机处理数据的分类

数值数据:整数、浮点数等数值类型。与这类数据相关的问题有:线性方程的求解,矩阵求逆,微分方程求解等。在计算机发展初期,人们使用计算机主要是解决这类问题。现在主要是在解决工程学、经济学的问题中使用。

处理这类数据的知识叫做:数值计算。

计算机处理数据的分类

非数值数据:这类数据的类型多样,比如:文字,图像,声音,视频等等。这类数据的数据量巨大。随着计算机应用领域的扩大和软、硬件的发展,这类数据所占的比例越来越多,也越来越重要。(据统计,当今处理非数值性问题占用了90%以上的机器时间。)数据元素之间的相互关系一般无法用数学方程加以描述。

如何描述此类数据,并对此类数据进行有效的处理,成为了严峻的问题。解决此类问题的知识,被称为:数据结构。

非数值问题求解

著名的瑞士计算机科学家沃思(N.Wirth)教授曾提出:

算法+数据结构=程序

解决非数值问题的关键不再是分析数学和计算方法,而是要设计出适当的数据结构来存储数据,并在此基础上设计出有效的算法,来对数据进行需要的处理。

例子:电话号码查询问题

设计一个查询某个城市的私人电话号码的程序。要求对任意给出的一个姓名,若该人有电话号码,则迅速找到其电话号码;否则指出该人没有电话号码。

要解此问题首先构造一张电话号码登记表。表中每个结点存放两个数据项: 姓名和电话号码。要写出好的查找算法,取决于这张表的结构及存储方式。最简单的方式是将表中结点顺序地存储在计算机中。查找时从头开始依次查对姓名,直到找出正确的姓名或是找遍整个表均没有找到为止。

这种查找算法对于一个不大的单位或许是可行的,但对一个有成千上万私人电话的城市就不实用了。

例子:田径赛的时间安排问题

假设某校的田径选拔赛共设六个项目的比赛,即跳高、跳远、标枪、铅球、100米和200米短跑,规定每个选手至多参加三个项目的比赛。现有五名选手报名比赛,选手所选择的项目如参赛选手比赛项目表所示。现在要求设计一个竞赛日程安排表,使得在尽可以短的时间内安排完比赛。

跳高

跳远

标枪

铅球

100米

200米

A

B

C

D

E

关于数据结构课程

这门课程是计算机相关专业的核心课程,在众多的计算机系统软件和应用软件中都要用到各种数据结构。仅掌握计算机语言是难以应付众多复杂的课题的,要想有效地使用计算机语言,必须学好数据结构的有关知识。 学习内容:

后继课程:数据库,操作系统等都要数据结构知识

如何学习数据结构

数据结构课程理论结合实践,难度比较大

1new.png

参考资源

C语言基础

使用C语言进行课堂讲授

C语言中的重点:

参考资料:

离散数学基础

这是数据结构的理论基础

主要相关知识:

参考资料

数据结构中的基本概念

数据结构的基本概念

数据的逻辑结构

数据元素之间的逻辑关系,也称数据的逻辑结构(Logical Structure)

数据的逻辑结构是从逻辑关系上描述数据,与数据的存储无关,是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

逻辑结构的表示

B = (K, R)

K:数据元素的集合,比如:{a, b, c, d,e}

R:数据元素之间的关系的集合,比如:{<a,b>, <b,c>,<c,d>,<d,e>}

<a,b>:a是b的前驱节点,b是a的后继节点

2.png

逻辑数据结构分类

数据的存储结构

数据元素及其逻辑关系在计算机存储器内的表示,称为数据的存储结构(Storage Structure)

数据的存储结构是逻辑结构用计算机语言的实现(亦称为映象),它依赖于计算机语言。对机器语言而言,存储结构是具体的。一般,只在高级语言的层次上讨论存储结构。

数据的基本存储结构

四种基本存储结构,既可单独使用,也可组合起来对数据结构进行存储映像。

同一逻辑结构可以采用不同的存储结构来表示。选择何种存储结构来表示相应的逻辑结构,视具体要求而定,主要考虑运算方便及算法的时空要求。

存储密度:数据所占空间与数据结构所占空间的比。一定≤1

数据的运算

数据的运算,即对数据施加的操作。

数据的运算定义在数据的逻辑结构上,每种逻辑结构都有一个运算的集合。

最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。所谓抽象的操作,是指我们只知道这些操作是"做什么",而无须考虑"如何做"。只有确定了存储结构之后,才考虑如何具体实现这些运算。

数据结构

数据结构就是指按一定的逻辑结构组成的一批数据,使用某种存储结构将这批数据存储于计算机中,并在这些数据上定义了一个运算集合。

数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。

存储结构是数据结构不可缺少的一个方面:同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。【例】线性表是一种逻辑结构,若采用顺序方法的存储表示,可称其为顺序表;若采用链式存储方法,则可称其为链表;若采用散列存储方法,则可称为散列表。

数据的运算也是数据结构不可分割的一个方面:在给定了数据的逻辑结构和存储结构之后,按定义的运算集合及其运算的性质不同,也可能导致完全不同的数据结构。

【例】若对线性表上的插入、删除运算限制在表的一端进行,则该线性表称之为栈;若对插入限制在表的一端进行,而删除限制在表的另一端进行,则该线性表称之为队列。 更进一步,若线性表采用顺序表或链表作为存储结构,则对插入和删除运算做了上述限制之后,可分别得到顺序栈或链栈,顺序队列或链队列。

抽象数据类型(Abstract Data Type)

ADT是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。

一个ADT可描述为:

ADT ADT-Name{
    数据对象:
       ……
    数据元素之间逻辑关系:
       ……
    操作:
        Operation1://操作1
        Operation2://操作2
        ……
  }

算法和算法的度量

算法

为了求解某问题,必须给出一系列的运算规则,这一系列的运算规则是有限的,表达了求解问题方法和步骤,这就是一个算法。 一个算法可以用自然语言描述,也可以用高级程序设计语言描述,也可以用伪代码描述。本课程采用C语言对算法进行描述。实验中采用C/C++都可以。

例子

写一个算法,计算n!

让i=1, s=1
如果i>n则转第6步
s = s * i
i = i +1
转第2步
计算结束,s为n!的值

还有其他算法吗?

五个重要特性

算法的正确性

评价算法的好坏

求解同一计算问题可能有许多不同的算法,究竟如何来评价这些算法的好坏以便从中选出较好的算法呢?选用的算法首先应该是“正确”的。

主要考虑如下三点:

算法的选择

一个占存储空间小、运行时间短、其它性能也好的算法是很难做到的。原因是上述要求有时相互抵触:要节约算法的执行时间往往要以牺牲更多的空间为代价;而为了节省空间可能要耗费更多的计算时间。

因此我们只能根据具体情况有所侧重:

算法执行时间的分析

一个算法所耗费的时间=算法中每条语句的执行时间之和

每条语句的执行时间=语句的执行次数(频度)×语句执行一次所需时间

算法转换为程序后,每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。

若要独立于机器的软、硬件系统来分析算法的时间耗费,则设每条语句执行一次所需的时间均是单位时间,一个算法的时间耗费就是该算法中所有语句的频度之和。

例子:求矩阵乘积

   1 void mult(int a[n][n], int b[n][n], int c[n][n]) 
   2 {
   3     int i, j, k;
   4     for (i=0; i<n; ++i) {  /* n+1 */
   5         for (j=0; j<n; ++j) { /* n(n+1)*/
   6             c[i][j] = 0;  /*n2*/
   7             for (k=0; k<n; ++k) /*n2(n+1)*/
   8                 c[i][j] += a[i][k]*b[k][j];  /* n3 */
   9         }
  10     }
  11 }

所有语句的频度之和 T(n)=(n+1)+n(n+1)+n2+n2(n+1) +n3

问题规模和算法的时间复杂度

算法求解问题的输入量称为问题的规模,一般用一个整数表示。比如:矩阵乘积问题的规模是矩阵的阶数。

一个算法的时间复杂度T(n)是该算法的时间耗费,是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时,时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。

比如:矩阵乘积算法的时间复杂度T(n) ,当n趋向无穷大时,显然有

6.png

这表明,当n充分大时,T(n)和n3之比是一个不等于零的常数。即T(n)和n3是同阶的,或者说T(n)和n3的数量级相同。记作T(n)=O(n3)是矩阵乘积算法的渐近时间复杂度。

大O表示法

若T(n)和f(n)是定义在正整数集合上的两个函数,则T(n)=O(f(n))表示存在正的常数C和n0,使得当n≥n0时都满足0≤T(n)≤C·f(n)。

常见的时间复杂度按数量级递增排列依次为:常数0(1)、对数阶0(log2n)、线形阶0(n)、线形对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、…、k次方阶0(nk)、指数阶0(2n)。显然,时间复杂度为指数阶0(2n)的算法效率极低,当n值稍大时就无法应用。

例子

有两个算法A1和A2求解同一问题,时间复杂度分别是T1(n)=100n2,T2(n)=5n3

那么,当输入量n<20时,有T1(n)>T2(n),后者花费的时间较少。

随着问题规模n的增大,两个算法的时间开销之比5n3/100n2=n/20亦随着增大。即当问题规模较大时,算法A1比算法A2要有效地多。

渐近时间复杂度O(n2)和O(n3)评价了这两个算法在n较大时的时间性能

例子

    Temp=i;
    i=j;
    j=temp; 

T(n)=O(1)

例子

x=0; 
y=0;
for(k-1;k<=n;k++)
    x++;
for(i=1;i<=n;i++)
     for(j=1;j<=n;j++)
         y++; 

T(n)=O(n2)

例子

 x=1;
 for(i=1;i<=n;i++)
     for(j=1;j<=i;j++)
         for(k=1;k<=j;k++)
             x++; 

T(n)=O(n3/6+低次项)=O(n3)

数据初始状态影响执行时间

算法的时间复杂度不仅仅依赖于问题的规模,还与输入实例的初始状态有关。

在数值A[0..n-1]中查找给定值k的算法大致如下:

for(i=0;i<n && A[i]!=k; i++);
   return i;

冒泡排序

各种情况下的算法性能

算法的空间复杂度

算法所需空间包括:

若输入数据所占空间只取决于问题本身,和算法无关,则只需要分析除输入和程序之外的辅助变量所占额外空间。

算法的时间复杂度和空间复杂度合称为算法的复杂度。

总结

数据结构(包括逻辑结构,存储结构,运算)

算法(时间复杂度,空间复杂度)

数据结构概述 (last edited 2008-02-23 15:34:57 by localhost)

ch3n2k.com | Copyright (c) 2008 czk. 浙ICP备06000584号