1_Intro数据结构.ppt

* 1.4 算法和算法分析 算法存储空间的度量 算法存储空间度量的基本做法 　　用程序执行中需要的辅助空间的大小作为存储空间度量的依据，是问题规模n的函数。 　　程序执行中程序本身和基本数据所需的工作单元计算空间复杂度时不算。 算法空间复杂度 　　S(n)=O(f(n)) 称为算法的空间复杂度。 * 程序 = 算法 + 数据结构 + 程序设计方法 + 程序开发环境 数据结构与程序设计的关系 * 数据结构与程序设计语言的关系 运算符号 语句 标准库函数 输入和输出 动态内存空间的申请和释放 参数传递 预定义常量和类型 数据结构可以通过程序语言提供的数据类型来表示和实现，即利用已经存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。 用伪码和类C语言作为工具来描述各数据结构中基本操作的算法实现。 * 数据结构的研究问题： 非数值数据之间的结构关系， 及如何表示，如何存储，如何处理。 本课程讨论的问题： 应用中常遇到的几种数据间的结构关系， 及如何表示,如何存储，如何处理。 数据结构课程的主要内容 * 对每种数据结构，主要讨论如下两方面的问题： 1） 数据的逻辑结构，基本操作；  2） 数据的存储结构，基本操作的实现； 数据的逻辑结构： 数据之间的结构关系，是具体关系的抽象。 数据结构的基本操作： 指对数据结构的加工处理 数据的存储结构 (物理结构)： 数据元素及其关系在计算机内存中的表示 数据结构基本操作的实现： 基本操作在计算机上的实现（方法) 数据结构课程的主要任务 * 本章小结 本次课程应掌握的内容 数据结构的基本概念 抽象数据类型的定义 算法及其评价 作业 1.8 1.9 1.11 参考书目 1. Mark Allen Weiss, Data Structures and Problem Solving Using C++, published by Addison Wesley Longman, 2000. 2. Robert L.Kruse, Alexander J.Ryba Data Structures and Programming in C++ , 高等教育出版社。 西安电子科技大学计算机学院 - School of Computer Science Engineering, Xidian University, China 数据结构 – Data Structures 西安电子科技大学软件学院 数据结构Data Structures 王黎明 wanglm@mail.xidian.edu.cn * 关于本课程 课程性质：必修 考核方式：考试(闭卷)成绩(80%)+平时成绩(20%)　3.5学分 课程实验成绩(程序验收＋报告)100% 1学分 学习要求： ① 禁旷课、迟到； ② 课前请关闭手机或调至振动，严禁课堂接听或拔打电话； ③ 要独立思考，按时完成作业。在自己不会解答时可参考其他资料或他人答案，在分析别人的处理思路之后自己动手，鼓励相互讨论，严禁抄袭； ④ 上机实验前应先就要处理的问题写出自己的解决思路和大纲，严禁在机房游戏、网上聊天、流览不相关的网页； ⑤ 上机程序要现场验收、严禁拷贝他人程序及报告。 * 本课程的内容框架 数据结构 基础数据结构 应用数据结构 非线性结构 线性结构 线 性 表 栈 队 列 串 数 组 广 义 表 树 二 叉 树 图 查 找 内 部 排 序 外 部 排 序 文 件 动 态 存 储 管 理 * 课程特点 理论 　　本课程不是以掌握应用性知识为目的，而是以掌握基本理论，基本方法，基本技能为目的。让学生把握解决什么样的问题，用什么思想，采用什么方法解决，以及用什么方法最优解决等一系列问题。 概念 　　本课程要求学生不但应该深刻理解某些概念的所有要素,同时也要求理解为什么要引入某些概念，这些概念的形成过程，以及引入这些概念解决什么样的问题。 * 课程特点(续) 很强的连贯性 　　　本课程结构紧凑，每部分所述问题层层推进，逐步深入。全课程始终是以数据间的关系即“结构”为主线索展开。其中“基本数据结构”部分围饶数据结构三要素即逻辑结构、物理结构、运算特性展开，辅以一定该数据结构基本应用的讲述；而“应用数据结构部分”以基本概念、基本方法、性能分析的顺序展开，使全课程大量庞杂的内容条理分明，轮廓分明。 容易混淆 　　本课程中有一些容易混淆的基本概念，也有很多算法，状态等等一系列问题都容易混淆。比如要解决某类问题，也许有很多方法和很多途径，每种方法和途径适用于什么场合，各自存在什么优缺点（