数据结构第01章概论课件.ppt

数 据 结 构 与 算 法 ;;数据结构课程的地位;学时数：40 学 分： 2.5 教 材： 严蔚敏等，数据结构（C语言版），清华大学出版社（配题集） 参考书： [1] （美）霍罗维兹等， 《数据结构基础（C语言版）》，清华大学出版社，2009 [2] 严蔚敏等， 《数据结构(C语言版)》，人民邮电出版社，2011 [3] 殷人昆等，数据结构（用面向对象方法与C++描述），清华大学出版社，2002;内 容 安 排;第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第9章 查找 第10章 排序;第1章　绪　论;1.1 什么是数据结构;数据(data)——所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息 ）。 数据元素(data element)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。 数据项(Data item)——构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性 等）。;1.2 学习数据结构的意义;;集合结构： 仅同属一个集合 线性结构: 一对一（1:1) 树 结 构: 一对多（1:n) 图 结 构: 多对多 (m:n);数据的逻辑结构分类;学生成绩表;2;文件系统结构图;例如:在迷宫问题中,计算机之间所以能够找到迷宫的出口,是因为人们已将有哪些信誉好的足球投注网站出口的策略事先存入计算机中.在迷宫中,每走到一处,接下来可走的通路有三条,如图: 计算机处理的这类对象之间通常不存在线性关系,若将从迷宫入口处到出口的过程中所有可能的通路都画出来,则可以得到一棵倒长的”树”.”树根”是迷宫入口,”树叶”是出口或死路.”树”可以是某些非数值计算问题的数学模型.如下图：;入口;现实中的问题：计算机和人的对弈;1;现实中的问题：多叉路口交通灯的管理;;在应用程序中涉及到各种各样的数据，如何在计算机中组织、存储、传递数据，需要讨论它们的归类及它们之间的关系，从而建立相应的数据结构，依此实现软件功能。 综上，描述这类非数值计算问题的数学模型不是数学方程，而是树、表和图之类的数据结构。 因此从广义上讲，数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现。;（1） S=(D, R) D={ a, b, c, d, e, f } R={(a,e), (b,c), (c,a), (e,f), (f,d)}; d1 d5 d2 d4 d3 ;答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。;存储结构的描述;答：在数据的逻辑结构上定义的操作算法。 它在数据的存储结构上实现。;1.4 什么是抽象数据类型;1.4.1 数据类型与抽象数据类型的区别;1.4.2 抽象数据类型如何定义;例：给出自然数(Natural Number )的抽象数据类型定义。;1.4.3 抽象数据类型如何表示和实现;提示： 教材中例1-6和例1-7分别给出了抽象数据类型“三元组”的定义、表示和实现，请自己先试读一遍。 当课程内容学习到50%以后，你再回头看这个例子，会发现自己已能完全看懂了！;1.5 算法效率的度量;1.5.1 什么是算法？如何评判一个算法的好坏？;算法分析;例子： 选择排序 问题： 递增排序 解决方案：逐个选择最小数据 算法框架： for ( int i = 0; i n-1; i++ ) { //n-1趟 从a[i]检查到a[n-1]; 若最小整数在a[k], 交换a[i]与a[k]; } 细化：Select Sort ;void selectSort ( int a[ ], int n ) { //对n个整数a[0],a[1],…,a[n-1]按递增顺序排序 int i,j,k, temp ; for (i = 0; i n; i++ ) { k = i; //从a[i]查到a[n-1], 找最小整数, 在a[k] for (j = i+1; j n; j++ ) if ( a[j] a[k] ) k = j; //记录最小整数的下标k