复习笔记
一、什么是数据结构
数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。
二、基本概念和术语
1数据
数据是对客观事物的符号表示，是计算机科学中所有能输入到计算机中并能被计算机程序处理的符号的总称。
2数据元素
数据元素是数据的基本单位。
3数据对象
数据对象是性质相同的数据元素的集合，是数据的一个子集。
4数据结构
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
(1)数据结构的基本结构
根据数据元素之间关系的不同特性，通常有下列四类基本结构：
①集合。数据元素属于“同一个集合”，并无其他复杂关系。
②线性结构。数据元素之间存在一个对一个的关系。
③树形结构。数据元素之间存在一个对多个的关系。
④图状结构或网状结构。数据元素之间存在多个对多个的关系。
【注意】区分这四种基本结构可以根据元素间的对应关系。
如图1-1所示为上述四类基本结构的关系图。
图1-1 四类基本结构的关系图
(2)数据结构的形式定义
数据结构的形式定义为：
Data_Structure=(D,S)
其中：D表示数据元素的有限集，S表示D上关系的有限集。
(3)数据结构在计算机中的表示
数据结构包括数据元素的表示和关系，在计算机中称为数据的物理结构(又称存储结构)。
其中，关系有两种表示方法：顺序映象和非顺序映象。这两种表示方法对应两种存储结构：顺序存储结构和链式存储结构。
a．顺序映象：用相对位置来表示数据元素之间的逻辑关系。
b．非顺序映象：用指针表示数据元素之间的逻辑关系。
程序设计和C语言
1.1 复习笔记
一、计算机程序
1程序就是一组计算机能识别和执行的指令
2计算机的一切操作都是由程序控制的
二、计算机语言
1定义
人和计算机交流信息，要解决语言问题。需要创造一种计算机和人都能识别的语言，这就是计算机语言。
2发展阶段
计算机语言经历了几个发展阶段：
(1)机器语言
(2)符号语言
(3)高级语言
三、C语言的发展及其特点
1概述
(1)C语言是国际上广泛流行的计算机高级语言。
(2)C语言的祖先是BCPL语言。
2发展
最初的C语言只是为描述和实现UNIX操作系统提供一种工作语言而设计的，后来逐步发展为一种高级编程语言，目前C语言使用的标准是1999年修正的C99。
3特点
(1)语言简洁、紧凑，使用方便、灵活
(2)运算符丰富
(3)数据类型丰富
(4)具有结构化的控制语句
(5)语法限制不太严格，程序设计自由度大
(6)C语言允许直接访问物理地址
(7)用C语言编写的程序可移植性好
(8)生成目标代码质量高，程序执行效率高
四、简单的C语言程序
(1)一个程序由一个或多个源程序文件组成
在一个源程序文件中可以包括3个部分：
①预处理指令
②全局声明
③函数定义
(2)函数是C程序的主要组成部分
①函数是C程序的基本单位。
②一个C语言程序是由一个或多个函数组成的，有且仅有一个main函数。
③一个小程序只包含一个源程序文件。
④函数既可以是库函数，也可以是用户自定义函数。
(3)函数的两个部分
①函数首部
函数首部包括函数名、函数类型、函数属性、函数参数(形式参数)名、参数类型。
②函数体
即函数首部下面的花括号内的部分。函数体一般包括两部分：声明部分和执行部分。
(4)程序总是从main函数开始执行的
(5)程序中对计算机的操作是由函数中的C语句完成的
(6)在每个数据声明和语句的最后必须有一个分号
(7)C语言本身不提供输入输出语句
(8)程序应当包含注释
五、运行C程序的步骤与方法
C程序运行步骤图如图1-1所示。其中实线表示操作流程，虚线表示文件的输入输出。
图1-1 C程序运行步骤图