沈阳农业大学信息与电气工程学院数据结构课件 第一章.ppt

第一章 绪论 数 据 结 构 主 讲 人：杨 涛 教材：严蔚敏, 吴伟民编著.数据结构(C语言版). 清华大学出版社,1997 参考书： 1. 晋良颖.数据结构.人民邮电出版社，2003 2. 徐孝凯.数据结构实用教程.清华大学出版社，1999 3. 严蔚敏等.数据结构题集(C语言版).清华大学出版社 4. 李春葆.数据结构(C语言篇)习题与解析.清华大学出版社 5. 前言考试研究室.全真题解—数据结构与程序设计分册.人民邮电出版社 6. R.F.Gilberg, B.A.Forouzan. Data Structures A Pseudocode approach with C++. 人民邮电出版社，2001 第一章 绪 论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 第一章 绪 论 计算机科学是一门研究用计算机进行信息表示和信息处理的科学（算法的科学）。 早期计算机主要应用于科学计算，特点是数据类型简单、算法复杂，侧重于建立程序，称之为数值计算。 现在计算机处理对象可以是数字、字符、表格、声音、图象等各种信息。 非数值计算的数据十分丰富，而且通常有一定的结构。 小 结 数据的逻辑结构、存储结构和有关操作的算法； 数据的逻辑结构的二元组表示；集合、线性结构、树型结构和图型结构 数据的存储结构：顺序、链接、索引和散列 算法及复杂性 时间复杂性 空间复杂性 习题与练习 一、名词解释 数据 数据项 数据元素 数据结构 数据逻辑结构 数据物理结构 算法 算法的时间复杂性 二、简答题 1. 算法分析的目的是什么？ 2. 什么是算法的最坏和平均时间复杂性？ 三、分析下列算法的时间复杂性: 1．sum=0; for (i=1;i=n;i++) { sum=sum+i; } 2．i=1; while(i=n) i=i*10; 3．sum=0; for(i=0;in;i++) for(j=0;jn;j++) sum=sum+Array[i][j]; 四、设有数据结构（D,R)，其中 D={d1,d2,d3,d4}, R={r}, r={(d1,d2),(d2,d3), (d3,d4)}. 试按图论中图的画法惯例画出其逻辑结构图。 最坏情况：1+2+3+…+n-1 =n(n-1)/2 最坏情况时间复杂度为:O(n2)(初始序列自大至小有序) 平均时间复杂度（不易求出）和最坏时间复杂度（易求，常用），对于一个算法来说，在平均和最坏两种情况下的时间复杂度的数量级形式往往是相同的。 算法的空间复杂度 一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间三个方面。 算法的空间复杂度: 算法在运行过程中临时占用的存储空间的大小，记作: S(n)=O(f(n)) ，其中n为问题的规模(或大小) 算法的空间复杂度较易计算，它包括局部变量所占用的存储空间和系统为实现递归（如果是递归算法的话）所使用的堆栈两部分。一般也以数量级的形式给出。 设计算法时，应从时间复杂度、空间复杂度、算法的简单性等几个方面综合考虑，要考虑算法的使用效率、算法的结构化和易读性以及所使用机器的硬软件环境等因素，才能设计出比较好的算法。 * * 第一章 绪论 对非数值数据进行组织，不仅要研究处理对象的特性，还需要研究它们之间的关系（结构） 因此，为了编写出一个“好”的程序，除了要掌握所用的计算机语言外，还必须分析待处理的对象的特征及各对象之间存在的关系，这就是《数据结构》这门课所要研究的问题。 1.1什么是数据结构 非数值计算的处理程序要解决三方面的问题： （1） 要对所加工的对象进行逻辑组织； （2）如何把加工对象存储到计算机中； （3）数据运算 例：电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够给出不存在的信息。 逻辑结构的选取（选取数据元素；元素间关系的选取—顺序关系）。 存储结构的选取（顺序存储或链式存储等）。 算法设计（顺序存