信息系统项目管理师_2024年软考学习应考交流_信息系统项目管理师考试

标题: 软考程序员数据结构复习笔记 [打印本页]

作者: 铅笔小星 时间: 2008-9-11 12:27
标题: 软考程序员数据结构复习笔记
数据就是指能够被计算机识别、存储和加工处理的信息的载体。

　　数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中，10这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。

　　数据结构的定义虽然没有标准，但是它包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。这一段比较重要，我用自己的语言来说明一下，大家看看是不是这样。

　比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每个元素又包括很多字段(数据项)组成。那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点(其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。

　　而存储结构则是指用计算机语言如何表示结点之间的这种关系。如上面的表，在计算机语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一起，这两种表示法就成为两种不同的存储结构。(注意，在本课程里，我们只在高级语言的层次上讨论存储结构。)

　　第三个概念就是对数据的运算，比如一张表格，我们需要进行查找，增加，修改，删除记录等工作，而怎么样才能进行这样的操作呢? 这也就是数据的运算，它不仅仅是加减乘除这些算术运算了，在数据结构中，这些运算常常涉及算法问题。

　　弄清了以上三个问题，就可以弄清数据结构这个概念。

--------------------------------------------------------------------------------

　　通常我们就将数据的逻辑结构简称为数据结构，数据的逻辑结构分两大类：线性结构和非线性结构 (这两个很容易理解)

　　数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。

--------------------------------------------------------------------------------

　　下一个是难点问题，就是算法的描述和分析，主要是算法复杂度的分析方法及其运用。首先了解一下几个概念。一个是时间复杂度，一个是渐近时间复杂度。前者是某个算法的时间耗费，它是该算法所求解问题规模n的函数，而后者是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。

　　当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n)简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。

　　此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。

　　常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。

　　时间复杂度的分析计算请看书本上的例子，然后我们通过做练习加以领会和巩固。

数据结构习题一

--------------------------------------------------------------------------------

1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。

◆ 数据：指能够被计算机识别、存储和加工处理的信息载体。

◆ 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。

◆ 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。
◆ 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。

◆ 逻辑结构：指各数据元素之间的逻辑关系。

◆ 存储结构：就是数据的逻辑结构用计算机语言的实现。

◆ 线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。

◆ 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。

作者: 小米米 时间: 2011-7-3 09:00
好困啊

作者: facekiss 时间: 2011-7-5 23:55
谢谢分享了!

作者: 清风 时间: 2011-7-5 23:55
我的啦嘿嘿

作者: 游手好闲 时间: 2011-7-5 23:55
初来乍到，请多多关照。。。

作者: 游手好闲 时间: 2011-7-7 00:41
说的真有道理啊！

作者: 流星 时间: 2011-7-7 15:00
岂能尽如人意，但求无愧我心。

作者: 晚秋 时间: 2011-7-7 15:00
真是汗啊我的帖子好少啊加油

作者: 不变的信仰 时间: 2011-7-7 15:00
HOHO~~~~~~

作者: 蜗牛 时间: 2011-7-9 04:20
越办越好~~~~~~~~~`

作者: 清露 时间: 2011-7-9 04:20
#无语

作者: cherie 时间: 2011-7-9 16:18
先看看怎么样！

作者: 晚秋 时间: 2011-7-13 15:15
先看看怎么样！

作者: c1532 时间: 2011-7-25 23:40
我想要`~

作者: 流星 时间: 2011-7-27 05:43
自己知道了

作者: ctdsb2011 时间: 2011-7-27 05:43
努力~~各位。。。

作者: 查无此人 时间: 2011-7-27 05:43
我来看看！谢谢

作者: c1532 时间: 2011-8-2 06:02
不错，感谢楼主

作者: 在12 时间: 2011-8-2 06:02
回复一下

作者: c34 时间: 2011-8-2 06:02
楼主，支持！

作者: 红茶 时间: 2011-8-8 14:47
初来乍到，请多多关照。。。

欢迎光临信息系统项目管理师_2024年软考学习应考交流_信息系统项目管理师考试 (http://bbs.tuandui.org.cn/)