[理学]计算机组成原理复习要点总结.pptVIP

数据结构 主讲教师：高滢 gying@jlu.edu.cn 课程相关信息 教材：《数据结构》，刘大有等编著，高等教育出版社，2001年. 参考书目：清华大学出版社、高等教育出版社和机械出版社等出版的数据结构教材. 学时：主讲64学时＋实验36学时. 考核方式：考试 数据结构 计算机学科中一门重要的专业基础课。 是程序设计的重要基础，也是许多计算机专业课的基础，如算法分析、编译原理、操作系统、数据库系统等。 什么是数据结构，为什么学习数据结构？？ 第一章 绪论 1.1 数据结构概念 1.2 面向对象程序设计OOP与抽象数据类型ADT 1.3 算法概念和算法描述语言 1. 数据 数据是计算机程序要处理的“原料”，它可以被计算机识别、存储和加工处理。 包括：数值、文字、表格、图像、声音、源程序等。 例如，个人书库管理程序所要处理的数据可能是如下的表格。 数据元素 数据元素是组成数据的基本单位。 在程序中通常把一个数据元素作为一个整体来考虑和处理。 例如，在上表中，把其中的每一行（代表一本书）作为一个基本单位来考虑。 数据项 一个数据元素含有若干个数据项。 例如，在上表数据中，每个数据元素由登录号、书号、书名、作者、出版社和价格六个数据项构成。 数据项是构成数据的最小单位。 2. 逻辑结构 逻辑结构的形式化表示 例3 L=(N,R)， N={k1，k2，…，k9} R={r}，r={ k1,k2 ， k1,k3 ， k1,k4 ， k1,k7 ， k1,k8 ， k4,k5 ， k4,k6 ， k8,k9 } 存储结构分类 顺序存储结构 链接存储结构 索引存储结构 散列存储结构 4. 数据处理 数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。 进入八十年代以后，计算机主要用于数据处理。据有关统计资料表明，现在计算机用于数据处理的时间比例达到80%以上，随着时间的推移和计算机应用的进一步普及，计算机用于数据处理的时间比例必将进一步增大。 6. 数据结构的定义 按某种逻辑关系将一批数据元素组织起来； 按一定的存储方式把它们存储起来； 在数据上定义需要施加的操作。 教学计划 第一章 绪论 第二章 算法分析基础 第三章 面向对象程序设计与C++语言 第四章 线性表、堆栈、队列 第五章 数组、字符串和集合类 第八章 递归 第六章 树 第七章 图 第九章 排序 第十章 查找 第一章 绪论 1.1 数据结构概念 1.2 面向对象程序设计OOP与抽象数据类型ADT 1.3 算法概念和算法描述语言 “面向过程”程序设计：是围绕功能进行的。系统功能的实现是通过对若干个功能模块的调用来完成的。适用于设计小规模的专用软件包，软件的通用性、重用性、扩展性差。 “面向对象”程序设计：是以数据为中心。以“类”作为构造程序的基本单位，类具有封装、数据抽象、继承和多态性等特点。 有助于提高软件的重用性、扩展性、移植性，提高编程效率和程序自动化水平。 ADT Name is Data 构成该抽象类型所必需的基本数据项 Operations 构造函数 Initial Values: 赋给基本数据项的值 Process: 初始化对象 操作1 Input: 操作1要求用户输入的值 Preconditions: 系统执行操作1前数据所需的状态 Process: 对数据执行操作1 Output: 操作1结束后返回的数据 Postconditions: 执行操作1后数据的状态 第一章 绪论 1.1 数据结构概念 1.2 面向对象程序设计OOP与抽象数据类型ADT 1.3 算法概念和算法描述语言 计算机解决问题的步骤：首先，从具体问题中抽象出一个适当的数学模型；然后，设计解此模型的算法；最后，编出程序、进行测试、调试，直至得到最终解答。 计算机算法与数据结构密切相关:算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。 操作是由计算机来完成，这就要设计相应的插入、删除和修改的算法 。也就是说，数据结构还需要给出每种结构类型所包含操作的算法。 计算机处理问题，以适当的数据结构为基础，制定出的切实可行的方法和步骤——计算机算法。 1976年，沃斯提出