12
算法的表示
一个算法的表示需要使用一些语言形式。传统的算 法表示方法为图形法，如流程图和N—S图 。
13
算法与计算机程序
算法是一组逻辑步骤，计算机程序是使用一些特殊 编程语言表达的某些算法。可能几种不同的计算机 程序，每一种用不同的编程语言实现，但遵循的逻 辑步骤是相同的。它都表达同样的算法，但是它们 不是同样的程序。
14
算法的评价
算法具有5个特性：有穷性、确定性、可行性、输入 和输出。
评价一个算法一般从正确性、运行时间、占用空间 和简单性4个方面进行。
15
2.2 数据结构基础
1. 数据结构的定义 数据结构研究和讨论三个方面的问题：数据集合中各数据
元素之间所固有的逻辑关系，即数据的逻辑结构；对数据进行 处理时，各数据元素在计算机中的存储关系，即数据的存储结 构；对各种数据结构进行的运算。
顺序文件是根据记录的序号或记录的相对位置来 进行存取的，其特点是当存取第i个记录时，必须先搜 索在它之前的i－1个记录；插入新的记录时，只能加 在文件的末尾；若要更新文件中的某个记录，则必须 将整个文件进行复制。顺序文件的主要优点是存取速 度快，因此多用于顺序存取设备(如磁带)。
6
2. 索引文件 索引文件是指在主文件之外再建立一个表示关键
数据结构和软件工程基础 知识
1 数据与文件 2 算法与数据结构 3 软件开发基础
1
1 数据与文件
1.1 数据组织的层次体系 1.2 基本文件组织方式
2
数据组织的层次体系
任何系统都有一个数据组织的层次体系。 在该层次体系中共分为位、字符、数据元、 记录、文件和数据库6层，每一后继层都是其 前驱层数据元组合的结果，最终实现一个综 合的数据集合。
文件是有名字的存储在某种介质上的一组信息的集合，即 文件由信息和介质组成。 5.数据库
数据库是一组有序数据的集合。
4
基本文件组织方式
文件是大量性质相同的记录的集合，文件存储在外存 储器中，如磁盘、光盘、磁带等。记录是文件中可存取的 基本数据单位，它由若干数据项组成，而数据项是文件中 最小的数据单位，通常由一个或多个数字位或字符组成， 用来表示记录的具体数值。文件在外存储器上组织方式的 类型主要有顺序文件、索引文件和直接存取文件。
8
2 算法与数据结构
2.1 算法的基本概念 2.2 数据结构基础 2.3 栈与队列的基本概念 2.4 排序与查找基本策略
9
算法的基本概念
1. 算法的定义 算法是一组明确的可执行步骤的有序集合。算法的
概念要求步骤集是有序的，这就要求算法中的各个 步骤必须拥有定义完好的顺序执行结构。
10
算法的特征： (1) 有穷性，一个算法必须保证执行有限步之后结束； (2) 确定性，算法的每一步骤必须有确定的定义； (3) 输入，一个算法有0个或多个输入，以描述运算
字与其物理记录之间对应关系的表，称为索引表。索 引表与主文件共同构成索引文件。索引文件的检索分 成两步完成，首先将索引表读入内存，再根据索引表 所指示的物理地址将记录所在的数据块读人内存进行 检索，如图所示。
7
3. 直接存取文件 直接存取文件又称为哈希(Hash)文件或散列文件，即利用哈
希函数及其处理冲突的方法，把文件散列到外存上，通常 是磁盘上。 对直接存取文件进行查找时，首先根据哈希函数求出哈希地 址，再将数据读入内存，然后在内存中进行顺序查找。直 接存取文件不能进行顺序查找，但插入数据方便，存取速 度快。
5
1. 顺序文件 顺序文件是按从头到尾的顺序进行存取操作的，
文件中的信息就像在一条长长的队列中排列一样。 顺序文件是最简单的文件，文件的各个记录按逻
辑顺序存放在外存的连续区中，即顺序文件中物理记 录的顺序和逻辑记录的顺序是一致的。如果文件按关 键字有序输入，则形成的顺序文件称为顺序有序文件； 否则称为顺序无序文件。
对象的初始情况，所谓0个输入是指算法本身定出 了初始条件； (4) 输出，一个算法有一个或多个输出，以反映对输 入数据加工后的结果。没有输出的算法是毫无意义 的； (5) 可行性，算法原则上能够精确地运行，而且人们 用笔和纸做有限次运算后即可完成。
11
算法的要素
正确性 精确 简单 抽象分级。
家庭成员的数据结构表示 B=(D,R) D=｛父亲，儿子，女儿｝ R=｛（父亲，儿子），（父亲，女儿）｝
17
数据结构的图形表示：
春
夏
秋
冬
父亲
儿子
女儿
18
线性结构
空的数据结构： 线性结构（线性表）：非空数据结构；有且只有一个根结点； 每个结点最多一个前件，也最多一个后件；在一个线性结构中 插入或删除任何一个结点后还应该是线性结构。 非线性结构：
19
3、数据的存储结构 数据的逻辑结构在计算机存储空间中的存放形式称为数据的 存储结构 常用的存储结构有顺序、链接、索引和散列四种结构。
顺序存储结构
20
链接存 储结构
21
(2) 树形存储结构 二叉树，用连续的存储单元保存结构如图：
22
(3) 图形存储结构
23
4. 数据结构、数据类型和抽象数据类型 数据结构是计算机科学与技术领域常用的一个字符在计算机中占8位，即一个字节。一个计算机系统
可以使用不只一种编码体制。 2.数据元
在数据的层次体系中，数据元是最低一层的逻辑单位，为了 形成一个逻辑单位,需要将若干位和若干字节组合在一起。 3.记录
将逻辑上相关的数据元组合在一起就形成一个记录。例如 一个学生记录(学号、姓名、性别、院系、班级)中包含的若干数 据元以及作为学生记录的一个值的若干数据项。记录是数据库 中存取的最低一层的逻辑单位。 4.文件
数据结构指相互有关联的数据元素的集合。比如向量和矩 阵。 2. 数据的逻辑结构：反映数据元素之间逻辑关系的数据结构。 数据是指由有限的符号组成的元素的集合，结构则是元素之间 的关系(前驱和后继)的集合。 用二元组表示：B=(D,R)
16
一年四季的数据结构表示： B=(D,R) D=｛春，夏，秋，冬｝ R=｛（春，夏），（夏，秋），（秋，冬）｝