文档介绍：VB教程数据线性构造
第二章 数据构造
1 什么是数据构造
程序=数据构造+算法
例1 书目自动检索系统
登录号：
书名：
作者名：
分类号：
出版单位：
出版时间：
价格：
书目卡片
书目文件
按书名
按作者名
按分类号
索引表
线性表
数据构造定义: 是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科
2 根本概念和术语
数据〔data)—所有能输入到计算机中去的描述客观事物的符号
数据元素〔data element〕—数据的根本单位，也称节点〔node〕或记录〔record〕
数据项〔data item〕—有独立含义的数据最小单位，也称域(field)
数据构造〔data structure)—数据元素和数据元素关系的集合
根据数据元素间关系的基本特性，有四种基本数据结构
（集合）——数据元素间除“同属于一个集合”外，无其它关系
线性结构——一个对一个，如线性表、栈、队列
树形结构——一个对多个，如树
图状结构——多个对多个，如图
数据的逻辑构造—只抽象反映数据元素的逻辑关系
数据的存储〔物理〕构造—数据的逻辑构造在计算机存储器中的实现
数据的逻辑结构与存储结构密切相关
算法设计 逻辑结构
算法实现 存储结构
存储结构分为：
顺序存储结构——借助元素在存储器中的相对位置来表示
数据元素间的逻辑关系
链式存储结构——借助指示元素存储地址的指针表示数据
元素间的逻辑关系
元素n
……..
元素i
……..
元素2
元素1
Lo
Lo+m
Lo+(i-1)*m
Lo+（n-1)*m
存储地址
存储内容
Loc(元素i)=Lo+（i-1)*m
顺序存储
1536
元素2
1400
元素1
1346
元素3
∧
元素4
1345
h
存储地址
存储内容
指针
1345
元素1
1400
1346
元素4
∧
…….
……..
…….
1400
元素2
1536
…….
……..
…….
1536
元素3
1346
链式存储
h
数据的逻辑结构
数据的存储结构
数据的运算：检索、排序、插入、删除、修改等
线性结构
非线性结构
顺序存储
链式存储
线性表
栈
队
树形结构
图形结构
数据结构的三个方面：
数据类型—高级语言中指数据的取值范围及其上可进展的操作的总称
例 C语言中，提供int, char, float, double等根本
数据类型，数组、构造体、共用体、枚举
等构造数据类型，还有指针、空(void)类
型等。用户也可用typedef 自己定义数据类型
typedef struct
{ int num;
char name[20];
float score;
}STUDENT;
STUDENT stu1,stu2, *p;
3 算法的描述和算法分析简介
算法〔algorithm〕—解决某一特定问题的具体步骤的描述，是指令的有限序列
算法特性—
算法的描述
算法的评价—衡量算法优劣的标准
正确性(correctness)
可读性(readability)
强健性(robustness)
效率与低存储量