数据结构教程与题解.ppt

很多算法的时间复杂度不仅与问题的规模有关，还与所处理的数据集的状态有关，一般是根据数据集中可能出现的最坏或最好情况，估计出算法的最坏(Worst)时间复杂度或最好(Best)时间复杂度；或者对数据集的分布作出某种假定（如等概率），讨论算法的平均(Average)时间复杂度。例数组查找在数组A[n]中查找值为K的元素例for(i=0;in;i++)

if(A[i]==K)break最好：数组第一个，比较1次；最坏：数组最后一个，比较n次；平均：等概率时，比较(n+1)/2次。第37页,共38页，星期六，2024年，5月空间耗费，一般用S(n)表示，分析方法与时间复杂度类似，也常用渐进空间复杂度。(2)空间复杂度线性方程组求解An×n·Xn×1=Bn×1例S(n)＝n2＋2n＋c＝O(n2)设解2000阶线性方程组需要64M内存，则解4000阶方程组大致需要多少内存？（不用虚拟、覆盖等）例64×22＝64×4=256M第38页,共38页，星期六，2024年，5月(1)数值问题求面积、体积S=a×bV=a×b×c◆建模型◆设计解法◆编程数据对象比较简单，如整型、实型或布尔型等，数据结构的问题不突出，程序设计的主要精力集中在程序设计的技巧上，解决问题的关键是数值计算方法(算法)，程序以算法为中心。也要用到数据结构知识方程求根f(x)=a2x2＋a1x＋a0=0变量名？零系数？前后顺序？快慢？内存？数组压缩线性效率评价f(x)=anxn＋an?1xn?1＋…＋a1x＋a0=0第5页,共38页，星期六，2024年，5月赛程安排AEDBFC(2)非数值问题JIACBDHGFE族谱（血缘关系）学号姓名性别出生日期籍贯入学成绩所在班级00201杨润生男82/06/01广州56100计算机2

00102石磊男83/12/21汕头51200计算机1

……………档案管理数据对象非数值型，数据间关系复杂、处理复杂（不能用数学公式表示），如何有效表示关系、如何有效处理数据，成为问题的关键。选择合适的数据结构表示问题，再写出算法程序＝数据结构＋算法有序索引线性第6页,共38页，星期六，2024年，5月数据结构的研究问题：非数值数据之间的结构关系，及如何表示，如何存储，如何处理。第7页,共38页，星期六，2024年，5月1.2数据结构的概念1.2.1数据1.2.2数据类型1.2.3逻辑结构1.2.4存储结构1.2.5运算1.2.6算法1.2.7数据结构第8页,共38页，星期六，2024年，5月1.2.1数据数据(Data)：凡能被计算机存储、加工处理的对象。是计算机程序加工处理的对象和原料。数值型、非数值型，含有某种信息，信息的载体。信息：加工处理后的数据，数据的内涵，信息通过数据表示。数据元素(DataElement)：数据的基本单位，在程序中作为一个整体加以考虑和处理，常具有完整确定的实际意义。有时称元素、结点、顶点、记录。数据项(DataItem)：数据不可分割的最小标识单位，有独立含义，但常不具完整确定的实际意义，或不被当作一整体看待有时称字段、域。第9页,共38页，星期六，2024年，5月学号姓名性别出生日期籍贯入学成绩所在班级00201杨润生男82/06/01广州56100计算机200102石磊男83/12/21汕头51200计算机1

……………例学生信息表数据、数据元素和数据项反映了数据组织的三个层次，数据可由若干数据元素组成，数据元素又可由若干数据项组成。第10页,共38页，星期六，2024年，5月1.2.2数据类型数据类型(DataType)是具有相同性质的计算机数据的集合及在这个数据集合上的一组操作的总称，它显式或隐式地规定了数据的取值范围和操作特性。原子类型：值不可分解，一般由程序语言直接提供，int、char…结构类型：值可分解为若干成分(分量)，一般用户定义(借助语言有关数据组织功能，数组、结构…)抽象数据类型(Abstrac