计算机软件技术基础：第二讲-数据结构.doc

《计算机软件技术基础》 教案 - 1 -

第二章 数据结构基础

2.1 基本概念

程序 = 算法 + 数据结构

也就是说，计算机按照程序所描述的算法对某种结构的数据进行加工处理。

1． 数据结构

数 据：在计算机领域，指能够被计算机输入、存储、处理和输出的一切信息。

数 据 项：是数据的最小单位，有时也称为域（eld）。

线性结构：每个结点有且只有一个前驱结点和一个后继结点（第一和最

后一个结点除外）

逻辑结构 树型结构：每个结点有且只有一个前驱结点（树根结点除

非线性结构 外），但可以有任意多个后继结点。

图型结构：每个结点可以有任意多个前驱结点和任意多个后继

结点

数据结构 顺序存储结构： 将数据结构的数据元素按某中顺序存放在计算机存储器的连续存

储单元中。其结构简单，可节省存放指针的空间，但需要连续的存

储空间，当数据元素的数目不确定时，会造成存储空间的闲置。

链接存储结构：为数据结构的每个结点元素附加一个数据项，其中存放一个与

号和在存储器中位置。通过索引表来访问记录。

《计算机软件技术基础》 教案 - 2 -

散列存储结构：在记录的存储位置和它的关键字之间建立一个确定的对

应关系，使每个关键字和结构中一个唯一的存储位置相对应。

由关键字作某种运算后直接确定元素的地址。

在数据的逻辑结构中，树型结构（1:N）是图型结构（M:N）的特例（M=1），

线性结构（1:1）是树型结构（1:N）的特例（N=1）。

一种数据结构可以表示成一种或多种物理结构。在数据处理过程中，一个恰当的数据结构

起着非常重要的作用。

2． 算法

算 法：即解决特定问题的方法。

算法准则 可行性： 要执行的每一计算步骤都可在有限时间内完成

输入： 一般应具有 0 个或多个输入信息，它是算法所需的初始数据

输出： 一般应具有 0 个或多个输出信息，它是算法对输入信息的运算结果

正确性：指在合理的数据输入下，能在有限的运行时间内得到正确的结果。

算法评价 运行时间（时间复杂性）：指一个算法在计算机上运算所花费的时间

占用的存储空间（空间复杂性）：指一个算法在计算机存储器中所占用的存储空间

简单性 ：指容易验证其正确性，且便于编写、修改、阅读和调试

3． Pascal 语言简介

整型 integer 一个整型数据占用 2 个字节的存储单元

实型 real 一个实型数据占用 4 个字节的存储单元

结构类型 集合：集合与元素的位置无关，存储结构是顺序存储结构，逻辑结构是关系

《计算机软件技术基础》 教案 - 3 -

文件：文件中的成分在位置上是顺序排列的，但逻辑结构和存储结构可以有多

指针类型 是以存储单元的地址作为其值的一种数据类型，它也是一种整体变量，系统

Array [T

] of T

; Record

Set of 基类型

T

1:

下标类型,可以是除整型和实型外的

其它任何类型简单类型;

T

2:

成分(元素)类型,可以是任何类型

类型 1～n : 可以是任何类型

基类型：可以是除整型和

实型外的其它任何类型简

单类型;

（2） 语句

赋 值 语 句 ： 变量名：= 表达式；

转 向 语 句 ： goto 语句标号；

退出循环语句： exit；

返 回 语 句 ： return；

出错处理语句： error（字符串）；

复 合 语 句 ： begin 语句 1；语句 2；…；语句 n end；

条 件 语 句 ： if 条件 then 语句 1 [else 语句 2] ；

情 况 语 句 ： case 变量名 of

《计算机软件技术基础》 教案 - 4 -

repeat 循环语句： repeat 一组语句 until 条件；

2.2 线性表

1． 线性表的逻辑结构

线性表：是具有相同特征的数据元素的一个有限序列，除第一个和最后一个元素外，每个元素

逻辑结构： 是线性结构。

2． 线性表的存储结构

线性表的存储结构有两种： 顺序存储结构 和 链接存储结构 。

双向链表：每个结点有两个指针域，一个指向直接前驱，一个指向直接后驱。它形成

h

单链表

h r

循环链表

双向链表