《算法与数据结构》全套PPT课件.pptx

算法与数据结构教师：课程简介第一章 绪论算法与数据结构学习数据结构有什么用？编写高质量的程序(1) 能够分析研究计算机加工的对象的特性，选择合适的逻辑结构、存储结构并设计相应的算法；(2) 提高处理复杂程序设计问题的能力，要求编写的程序结构正确、清晰、易读；(3) 掌握算法的时间复杂度和空间复杂度的分析技术。算法与数据结构数据结构课程的重要性后续课程（数据库、操作系统、人工智能、编译等）的基础硕士研究生入学考试课程2002年前：专业课两张卷，各100分 (多数高校数据结构占100分)2003--2008：专业课一张卷，150分 (部分高校只考数据结构，如华中 科大、北京交大、江苏大学等)2009----专业基础综合一张卷全国统考 (4科，数据结构占45分)2013----专业基础综合一张卷 全国统考/自主命题 (暨南大学、深圳大学等只考数据结构 )算法与数据结构教材与参考书教材：算法与数据结构(c++语言版)， 冯广慧，电子工业出版社参考书：算法与数据结构考研试题精析（第3版）陈守孔，机械工业出版社 数据结构 – C语言版 严蔚敏 清华大学出版社数据结构与算法分析 – C++ 描述（第3版）Mark Allen Weiss著 人民邮电出版社D.E.Knuth. The Art of Computer Programming. Addison-Wesley Educational Publishers Inc算法与数据结构授课与考核方式授课方式理论课时： 48 学时实验课时： 16 学时考核方式平时考勤及实验 %期末考试笔试 %要求：诚信代码保证每周至少独立编写一个算法（实验作业）算法与数据结构课程简介第一章 绪论算法与数据结构第一章 绪论1.1 什么是数据结构1.2 基本概念和术语1.3 算法和算法分析 1.4 抽象数据类型 算法与数据结构例1.1 学生信息管理系统 在这类问题中：(1) 计算机处理的对象是各种表；(2) 元素之间的逻辑关系是线性关系；(3) 施加于对象上的操作有遍历、查找、插入、删除等。 算法与数据结构例1.2 人机博弈 在这类问题中：(1) 计算机处理的对象是树型结构；(2) 元素间的关系是一种一对多的层次关系；(3) 施加于对象上的操作有遍历、查找、插入、删除等。算法与数据结构例1.3 哥尼斯堡七桥问题 在这类问题中：(1) 计算机处理的对象是各种图；(2) 元素间的关系是复杂的图形或网状关系，是一种多对多的关系；(3) 施加于对象上的操作有遍历、查找、插入、删除等。算法与数据结构什么是数据结构没有标准的定义，但有共识数据结构：简单地说，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。算法与数据结构第一章 绪论1.1 什么是数据结构1.2 基本概念和术语1.3 算法和算法分析 1.4 抽象数据类型 算法与数据结构1.2 基本概念和术语1．数据（Data）是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。2．数据元素（Data Element）是数据中的一个“个体”，是数据的基本单位。在有些情况下数据元素也称为元素、结点、顶点、记录等。数据元素用于完整地描述一个对象。如：一个学生记录、棋盘中的一个格局、图中的一个顶点等。3．数据项(Data Item)是组成数据元素的有特定意义的不可分割的最小单位。如构成一个数据元素的字段、域、属性等都可称之为数据项。数据元素是数据项的集合。如：学生信息表中的学号、姓名、性别、专业等。算法与数据结构1.2 基本概念和术语4．数据对象(Data Object)是具有相同性质的数据元素的集合，是数据的一个子集。如：整数数据对象是集合N = { 0，±1，±2， … }，字母字符数据对象是字符集合C={a，b，…，z}，学生数据对象等。5．数据结构（Data Structure）通过抽象的方法研究一组有特定关系的数据的存储与处理，数据结构主要研究三个方面的内容。(1) 数据之间的逻辑关系，即数据的逻辑结构；(2) 数据及其逻辑关系如何在计算机中存储实现，即数据的存储结构；(3) 在某种存储模式下，对数据施加的操作是如何实现的，即运算实现。算法与数据结构线性表 栈和队列 线性结构 字符串 数据的逻辑结构 树 非线性结构图顺序链式索引散列 数据的存储结构 数据的运算：检索、排序、插入、删除、修改等 数据结构的三要素算法与数据结构1.2 基本概念和术语6．数据的逻辑结构集合结构：元素间的次序是任意的。元素之间除了“属于同一集合”的联系外没有其他的关系。线性结构：数据元素的有序序列。除了第一个和最后一个元素外，其余元素都有一个前趋和一个后继