luqingfei@C++

为中华之崛起而崛起!
兼听则明,偏听则暗。

『数据结构与算法』基本概念与术语

『数据』是计算机化的信息。它是对现实世界的事物采用计算机能够识别、存储和处理方式进行的描述。例如:整数、字符、声音、图像等都是『数据』。

『数据元素』是数据的基本单位,即数据集合中的个体。有些情况下也把『数据元素』称做结点或记录等。

『数据项』,一个数据元素可由一个或多个数据项组成,『数据项』是有独立含义的数据最小可使单位。有时也把『数据项』称做域、字段等。例如:学生管理系统中,可以把一个与学生有关的信息作为一个『数据元素』,它由学号、姓名、年龄等『数据项』,组成。

『数据结构』是相互之间存在一种或多种特定关系的『数据元素』的集合。数据元素之间的相互关系称为结构。

数据结构包括:逻辑结构和物理结构。

数据的逻辑结构只抽象地描述数据元素间的逻辑关系,而不管其在计算机中的存储表示方式。

数据的物理结构是数据的逻辑结构在计算机存储器里的实现。数据的物理结构也称为存储结构。

数据的逻辑结构分为:线性结构和非线性结构。

线性结构,各数据元素之间的逻辑关系可以用一个线性序列简单地表示出来,否则称为非线性结构。

线性结构有线性表、栈和队等。

非线性结构有树、图等。

『数据类型』是一个值的集合和定义在该值集上的运算集合的总称。这个概念最早出现在程序语言中,每个程序语言都提供若干数据类型,用于定义变量、常量或表达式可以取值的范围,以及可以施于它们的运算。

程序语言中的数据类型可以分为两类:
一类是原子类型,其值是不可分解的。例如C语言中的整型、实型、字符型等。
另一类是结构类型,其值是由若干万分按某种结构组成的,因此是可以分解的,并且它的万分还可以是结构的。例如:数组的值由若干分量组成。

数据结构与程序语言中的数据类型有关,但两者并非互相对应的。
一些最基本的数据结构,例如:记录、数组、字符串等在很多情况下程序语言自身已经提供相应的数据类型实现,即指程序语言本身提供了对这些结构的描述手段和对它们的操作。
但还有许多数据结构,在很多程序语言中并没有相应的数据类型,需要采用程序语言中提供的基本数据类型和供程序员构造结构化数据类型方法作为工具实现相应的数据结构。

抽象数据类型是指一个数学模型及定义在该模型上的一组操作。

算法是解决某一特定类型问题的有限运算序列。
一个算法应该具有下列特性:
(1)有究性。一个算法必须是在执行有限步之后结束。
(2)确定性。算法的每一步必须是确切地定义的,无二义性。
(3)可行性。算法应该是可行的,这意味着算法中描述的运算都是相当基本的,它们都是可以通过已经实现的基本运算执行有限次来实现的。
(4)输入。一个算法有0个或多个输入。
(5)输出。一个算法有一个或多个输出。

算法的设计可以避开具体的计算机程序语言,但算法的实现必须借助程序语言中提供的数据类型及其运算。
数据结构与算法是相辅相成的,它们是利用计算机解决实际问题时不可缺少的两个方面。

数据的运算是定义在数据的逻辑结构上的,但运算的具体实现要在存储结构上进行。

常用的运算有查找、插入、删除、更新和排序等。

一种数据结构的优劣是由实现其各种运算的算法体现的。
对数据结构的分析实质上也就是对实现其各种运算的算法的分析。

在算法正确的前提下,算法的执行时间和存储量需求是分析和评价一个算法的两个主要方面。

——复习《数据结构基础——谭洗强》第一章
这本书是我02年开始学的,当时学的还算认真,但学的也比较糊涂,现在重新复习一下。巩固一下自己的数据结构与算法的知识。

接下来,将会找一些比较经典的数据结构,算法来研究分析。

posted on 2009-03-26 22:31 luqingfei 阅读(757) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2009年2月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
1234567

统计

留言簿(6)

随笔分类(109)

随笔档案(105)

Blogers

Game

Life

NodeJs

Python

Useful Webs

大牛

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜