第数据结构概论精要.ppt

（Java版） 计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题： 信息的表示 信息的处理 而信息的表示又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。 正所谓“道可道，非常道”。编程之道就如武学之道，VB，VC，delphi等开发工具的技巧好比各门各派的武功招式，算法和数据结构好比内功心法和武学原理。内力深厚，任何招式到了手上都能够化腐朽为神奇；掌握了武学原理，更能做到无招胜有招。 程序（Program）=算法(Algorithm)+数据结构(Data Structure) 课程简介-1 “数据结构”是计算机及相关专业的一门重要的专业技术基础课程，也是一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法；介绍了常用的多种查找和排序技术，并对其进行性能分析和比较，内容非常丰富。 课程简介-2 数据结构是介于数学、计算机硬件和计算机软件之间的一门课程。一般的前序课程是离散数学和程序设计基础，后序课程有高级程序设计、编译原理、操作系统、数据库、人工智能等 学习本课程的必要性 提高复杂程序设计的能力 培养算法设计能力 设计优秀程序的基础 分析程序的基础 计算机专业的核心基础专业课程 计算机专业人员必须学会学好的课程 为后继课程打基础 学习目标 要求学生掌握各种数据结构的逻辑特点存贮方法，基本运算 要求学生掌握常用的查找，排序的原理与技术方法 要求学生能够对具体问题选择适当的结构，并编写出结构清晰的程序 学习目标 具体来说，就是通过本课程学习，要求掌握数据结构和算法的基本概念和技术，从而能够对于给定问题选择合适的数据结构，并设计相应的操作算法。掌握向量、线性表、栈和队列、树和二叉树、图等典型数据结构及相关算法，以及排序、查找等重要技术。 学习方法 上机操作的重要性 多看书，勤思考 计算机学习中英语学习的重要性 网络资源的利用 要把握住重点和难点内容 学好理论，更要注重实践 第1章 数据结构概论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型和数据结构 1.4 学习数据结构的意义 1.5 算法和算法分析 数值计算解决问题的一般步骤： 数学模型→选择计算机语言→编出程序→测试→最终解答。 数值计算的关键是：如何得出数学模型（方程）？ ——实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学语言加以描述。 程序设计人员比较关注程序设计的技巧。 非数值计算问题： 数据元素之间的相互关系一般无法用数学方程加以描述 例1 书目自动检索系统 例2 人机对奕问题 例3 多叉路口交通灯管理问题 求解非数值计算的问题： 主要考虑的是设计出合适的数据结构及相应的算法。 即：首先要考虑对相关的各种信息如何表示、组织和存储？ 因此，可以认为：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。 二、数据结构课程的形成和发展： 形成阶段： 60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。 1968年美国唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。 发展阶段： 数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。 70年代后期，我国高校陆续开设该课程。 三、《数据结构课程》所处的地位： 地位： “数据结构”在计算机科学中是一门综合性的专业基础课。 数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。 数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。 1.2 基本概念和术语 几个概念： 1、数据的定义 定义一：数据是客观事物的符号表示。 ? 例：张三的C语言考试成绩为92分，92就是该同学的成绩数据。 定义二：能输入到计算机中并被计算机程序处理的符号的总称。 例：图像、声音等。 总结：现实世界信息的分析、复制、传播首先要符号化，这样才便于处理，尤其是便于计算机的处理。家长、社会要了解一个学生的学习成绩和能力，要看他的学习档案，而学习档案即是说明该学生学习情况的数据。 2、数据元素、数据项