[理学]2009年社会工作实务初级模拟试题.ppt

第一章 绪论 课程背景 计算机=软件 + 硬件 软件=程序+文档（软件工程的观点） 程序=算法+数据结构（Niklaus Wirth，图灵奖获得者) ‘数据结构’=‘计算机程序设计技巧(Kunth，图灵奖获得者) 熟悉c语言≠写出‘好’的程序 学习数据结构=编写高水平的程序 《数据结构》：计算机类专业8大核心课程之一 注：教育部计算机教指委认定的8大核心课程：计算机语言、数据结构、离散数学、计算机网络、计算机组成原理、操作系统、数据库、软件工程 图灵奖：1966年设置，每年奖励1-2名杰出的计算机科学家，被誉为计算机领域的诺贝尔奖 基本学习方法 教材和参考书 教材 数据结构（c语言版）秦锋编著 中国科技大学出版社 主要参考书 《数据结构例题详解及课程设计指导》 秦锋、袁志祥等 中国科技大学出版社 《数据结构C语言版》严蔚敏、吴伟民 清华大学出版社 《C程序设计》谭浩强 清华大学出版社 本章主要内容 什么是数据结构 基本概念和术语 算法 1.1 什么是数据结构 早期的计算机主要用于数值计算 现在的计算机更多地是用于非数值数据处理（字符、表格、图像） 对非数值数据的处理：分析数据的逻辑特征→抽象出合适的数学模型→合理地存储到计算机→设计出算法→编写出程序 例1 学生信息查询系统 首先要构造学生信息表，表1-1表达出学生数据的逻辑关系，它就是一个数学模型，这张表如何构造、在计算机内如何存储将直接影响查找算法的设计以及算法的效率 学生信息表的特点 每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格 表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构，现实中这类关系的数据有很多。。 通常的操作 插入某个学生的信息 删除某个学生的信息 更新某个学生的信息 按条件查找某个学生的信息 例2 人机对弈 中国象棋、国际象棋的人机大战，核心技术是人编写的对弈程序。对弈步骤和过程可以用树型结构表达出来（数学模型） 树型结构的特点 所处理的数据之间具有层次关系，这是我们所说的树形结构,还有如：基因遗传关系等，它是一种非线性结构。 对它的操作有：建立树形结构、存储树、访问树中的每个结点 例3 排课子系统 排课系统中各门课程的先后关系可以用一个图表达出来，这个图表达了数据的逻辑关系（数学模型） 在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。如何安排每学期的课程？ 计算机专业课程的开设情况如下表所示： 课程先后关系的图型描述 图结构的特点 关系比较复杂，用例1和例2的结构表达不出来，必须用图结构描述（离散数学中的图论） 通过实施创建图结构，存储图结构，可以对图结构中的顶点进行线性排序，从而找出每学期应该上的课程。 现实中，这类关系的数据非常多。如：网络规划、交通、通讯规划等，这里典型的非线性关系。 结论 操作对象的关系复杂多样 操作不再是单纯的数值计算，更多的是非数值问题求解，需要对数据（不是数值）进行分析、组织及管理。 必须对数据进行有效的组织、存储，才能对数据进行有效的操作 1.2 基本概念和术语 数据 是对客观事物的符号表示。在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合 数据元素 是数据集合中的一个实体，是计算机程序中加工处理的基本单位（记录、结构体） 数据元素的分类 简单型数据元素 由一个数据项组成，数据项就是数据中不可再分割的最小单位 复杂型数据元素 复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息 数据结构的定义 数据结构是相互之间存在一种或多种特定 关系的数据元素的集合。 常见的数据结构 线性结构 树形结构 图形结构 数据结构主要研究 数据的逻辑结构 数据的存储结构 对数据的操作（运算算法） 数据结构的定义 逻辑结构 数据结构中所说的“关系”实际上是指数据元素之间的逻辑关系，又称此为逻辑结构 存储结构（物理结构） 是指数据结构在存储器中的具体实现。与孤立的数据元素表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表示清楚数据元素之间的逻辑结构 数据运算 对数据施加的操作。运算的定义依赖于逻辑结构，但运算的实现必依赖于存储结构（真正理解） 常见的存储结构 顺序存储结构： 特点是借助于数据元素的相对存储位置来表示