文档介绍：公共基础知识 --------2004版
出版社:清华大学主编:雷振甲
第1章数据结构与算法
1. 1 算法
算法:是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的,此顺序将在有限的次数下终止。
算法必须满足以下五个特性
(1)有穷性---执行了有限条指令后一定要终止。
(2)确定性(无二义)---算法的每一步操作都必须有确切定义,不得有任何歧义性。
(3)可行性---算法的每一步操作都必须是可行的,即每步操作均能在有限时间内完成。
(4)输入数据---一个算法有零个或多个输入,这些输入取自于某个特定的对象集合。
(5)输出数据---一个算法有一个或多个输出,这些输出是同输入有着某些特定关系的量。
1. 1 算法
组成算法的基本要素:
:计算机算法就计算机能处理的操作所组成的指令序列。基本运算和操作:⑴算术运算:+,-,*,/
⑵逻辑运算:与、或、非
⑶关系运算:>,<,=,!=
⑷数据传输:赋值、输入、输出
:算法的成功即决于选用的操作,也取决于各操作之间的执行顺序。
算法中各操作之间的执行顺序称为算法的控制结构。
1. 1 算法
算法的复杂度:同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。
:时间复杂度就是指完成一个算法所需要的时间。算法效率的度量:采用时间复杂度。记为 T(n)=O(f(n))
:算法所需存储空间的度量,记作:
S(n)=O(f(n))
其中n为问题的规模(或大小)
1. 2 数据结构的基本概念
数据结构:数据结构(Data Structure)是相互之间存在一种或多种特定关系的数据元素的集合。或者说:数据结构是指带有结构的数据元素的集合。
数据结构主要研究以下问题:
:数据集合中各数据元素之间所固有的逻辑关系。
:数据结构在计算机中的表示称为数据的物理结构,又称为存储结构。
:对各种数据结构的运算。。
1. 2 数据结构的基本概念
逻辑结构---划分方法
一、集合结构中的数据元素除了同属于一种类型外,别无其它关系。
二、线性结构结构中的数据元素之间存在一对一的关系。
三、树型结构结构中的数据元素之间存在一对多的关系。
四、图状结构或网状结构结构中的数据元素之间存在多对多的关系。
1. 2 数据结构的基本概念
存储结构的基本组织方式:
(1)顺序存储(数组)
(2)链接存储(结构=数据域+指针域)
(3)索引存储(关键字+地址)
(4)散列存储(关键字到地址的映射)
数据结构概念小结:
(1)数据的逻辑结构、存储结构和数据的运算(算法)是数据结构三个方面的内容。
(2)程序设计的实质是对实际问题选择一个好的数据结构,加之设计一个好的算法。
1. 2 数据结构的基本概念
数据结构的图形表示:
数据集合中的每一个元素用中间标有元素值的方框表示,称为数据结点,并简称为结点。对于关系中的每一个二元组,用一条有向线段从前件指向后件结点。
如:
父亲
女儿
儿子
春
夏
秋
冬
1. 2 数据结构的基本概念
线性结构与非线性结构:
:如果一个非空的数据结构满足下列两个条件:(1)有且只有一个根结点;
(2)每一个结点最多有一个前件,也最多有一个后件。则称该数据结构为线性结构。线性结构又称线性表。
:如果一个数据结构不是线性结构,则称之为非线性结构。家庭成员间辈分关系的数据结构就属于非线性结构。