数据结构培训资料.ppt

《数据结构培训资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第1章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析电子计算机的主要用途：早期：主要用于数值计算。解决问题的步骤：数学模型→解题算法→选择计算机语言编程→测试→最终解答关键：如何得出数学模型当今：扩大到非数值计算领域。计算机的操作对象的关系更加复杂，数据元素间的相互关系有时无法用数学方程来描述。所处理的数据量大且具有一定的关系；而对其的操作也不再是单纯的数值计算，更多地是对其进行组织、管理和检索等。例1：学籍档案管理假设一个学籍档案管理系统应包含如下表所示的学生信息：特点：每个学生的信息占据一行，所有学生的信息按学

2、号顺序依次排列构成一张表格；每列的数据类型一样；表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；对它的操作通常是插入、删除、更新、按条件检索某个学生的信息等等。例2：输出n个对象的全排列输出3个对象的全排列可以使用下图所示的形式描述：特点：在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构；对它的操作有：建立树形结构，输出最低层结点内容等等。例3：制定教学计划制定教学计划时，需考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表所示：课

3、程先后关系如图：c1c9c4c2c12c10c11c5c3c6c7c8c1c9c4c2c12c10c5c3c6c7c8c11特点：课程之间的先后关系用图结构描述；通过实施创建图结构，按要求将图结构中的顶点进行线性排序。结论要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点、之间的关系，在计算机中的表示方式及各种操作的具体实现手段。因此，《数据结构》研究的主要内容是：数据元素之间的逻辑关系数据的存储结构采用何种操作实现算法的效率更高程序设计：为计算机处理问题编制一组指令集。算法：处理问题的策略。数据结构：问题的数学模型。程序设计的实质是对确

4、定的问题选择一种好的结构，加上设计一种好的算法。程序=算法+数据结构“Programs=Algorithm+DataStructures”瑞士学者NiklausWirth于1976年出版的书名。课程任务：1.讨论现实世界中数据的各种逻辑结构及在计算机中的存储结构；2.进行各种非数值运算的算法。课程目的：掌握数据组织、存储和处理的常用法，为进行软件开发或后续专业课程学习打下良好的基础。课程内容：数据结构的基本概念、线性表、栈和队列、串和数组、树形结构、图结构、查找、排序和文件等内容。第1章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1

5、.4算法和算法分析1.数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机处理的符号的总称。计算机程序加工的“原料”。例：一个利用数值分析方法解代数方程的程序，其处理对象是整数和实数；一个编译程序或文字处理程序的处理对象是字符串。还有声音、图象、视频等等通过编码都属于数据的范畴。2.数据元素是数据的基本单位。数据中的一个“个体”，数据结构中讨论的基本单位。在计算机中通常作为一个整体进行考虑和处理。例：一个整数“5”；一个字符“N”；图中的一个顶点等。复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。例：一个学生的基本信息就

6、是一个数据元素，其中的学号、姓名等被称为“数据项”。因此数据项是数据结构中讨论的最小单位。数据元素是数据项的集合，数据项是数据的不可分割的最小单位。3.数据对象性质相同的数据元素的集合。是数据的子集。例：整数数据对象是集合N={0，±1，±2，…}。英文字母数据对象是集合C={‘A’，……，‘Z’}。如何选定数据对象将依问题而定！譬如，在学生管理系统中，可能以一个班级的学生记录作为数据对象，也可能以一个年级的学生记录作为数据对象。4.数据的逻辑结构讨论计算机系统中数据的组织形式及其相互关系。即相互之间存在一种或多种特定关系的数据元素的集合。数据逻辑结构的形式定义

7、：数据逻辑结构是一个二元组：Data_structure={D,R}其中，D是数据元素的有限集，R是D上的关系的集合。例：在计算机科学中，复数可取如下定义：复数数据的逻辑结构Complex=(C,R)其中：C是含两个实数的集合{c1,c2};R={P}，而P是定义在集合C上的一种关系{}，其中有序偶表示c1是复数的实部，c2是复数的虚部。4数据的逻辑结构例：list=(D,S1),tree=(D,S2),graph=(D,S3)D={a,b,c,d,e}S1={,,,}S2={,

8、c>,,