chapter01复合

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数 据 结 构,吕建明,严蔚敏，吴伟民，数据结构（,C,语言版），清华大学出版社，200,8,年；,殷人昆等，数据结构（用面向对象方法与,c+,描述），清华大学出版社,2000,傅清祥，王晓东，算法与数据结构，电子工业出版社，,2001,；,吴文虎，王建德，实用算法的分析与程序设计，电子工业出版社，,1998,；,William F,.,，,William T,.,，,Data Structures with C+,，,Prentice Hall,，,Inc,.,，,1996,；,Clifford A,.,S,.,，,Data Structures and Algorithm Analysis,，,Prentice Hall,，,Inc,.,，,1997,。,http:/202.38.193.234/sjjg/,教学安排：,总学时数：,72,学时,主要参考资料：,教学对象：,计算机科学与工程专业的学生；,计算机软件专业的学生；,计算机辅修专业的学生；,电类联合班的学生；,网络教育学院计算机专业的学生；,各类成人教育及自学考试人员；,工程技术人员。,课程内容：,第一章绪论,第二章线性表,第三章栈和队列,第四章串,第五章数组和广义表,第六章树和二叉树,第七章图,第八章动态存储管理,第九章查找,第十章内部排序,第十一章外部排序,第十二章文件,第一章 绪论,1.1,背景,计算机加工处理的对象,:,数值、字符、表格、图像、声音、视频等各种具有一定结构的复杂的数据。,程序设计的过程：,数据结构设计：研究数据的特性以及数据之间存在的关系,算法：处理数据的运算过程,“,数据结构与算法”是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。,“,数据结构与算法”作为一门独立的课程，它不仅是计算机科学中的一门专业基础课，而且也是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。,1.2“,数据结构”研究什么,“数据结构”,是研究,非数值计算,的程序设计问题中计算机的,操作对象,以及,它们之间的,关系和操作,的学科,。,数据,数据结构,现实世界,程序,操作对象,在图书馆内有各种名目的卡片：有按书名编排的，有按作者编排的，还有按分类编排的，等等。若利用,计算机实现自动检索,，则计算机处理的对象便是这些目录卡片上的书目信息。在书目自动检索系统中可以建立一张按登录顺序排列的书目文件和,3,张分别按书名、作者名和分类号顺序排列的索引表，如下图所示。,例一：图书馆的书目检索系统自动化问题。,001,高等数学,樊映川,S01,002,理论力学,罗远祥,L01,003,高等数学,华罗庚,S01,004,线性代数,栾汝书,S02,高等数学,001,003,理论力学,002,线性代数,004,樊映川,001,华罗庚,003,栾汝书,004,L01,002,S01,001,003,数据结构,线性表,（,具有相同特性的数据元素的列表）,例二：计算机和人对弈问题。棋局的派生关系。,数据结构,树,。（课本,P2,）,例三：多叉路口交通灯的管理问题。,数据结构,图,。（课本,P3,）,例四：人际关系网络。,数据结构图,。（课本,P3,）,例四：考勤登记。,数据结构数组,例五：文本检索。,数据结构串,例六：个人简历。,数据结构广义表。,“数据结构”,是研究,非数值计算,的程序设计问题中计算机的,操作对象,以及,它们之间的,关系和操作,的学科,。,1.3,基本概念和术语,1,）,数据,：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。,例如，整数、实数、字符串、图像和声音等。,2,）,数据元素,：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。如棋局，书目信息等,3,）,数据项,：数据元素可由若干数据项组成。数据项是数据不可分割的最小单位。例如，一本书的书目信息为一个数据元素，而书目信息中的每一项（如书名、作者名等）为一个数据项。,4,）,数据对象,：是性质相同的数据元素的集合，是数据的一个子集。,例如，字母字符数据对象集合,C=A,B,Z,。,5,）,数据结构,：是相互之间存在一种或多种特定关系的数据元素的集合。,其形式定义为：,(,一个二元组,),Data_Structure=(D,S),其中：,D,是数据元素的有限集，,S,是,D,上关系的有限集。,根据数据元素之间关系的不同特性通常有下列,4,类基本结构：,集合,：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。,线性结构,：结构中的数据元素之间存在一个对一个的关系。,树形结构,：结构中的数据元素之间存在一个对多个的关系。,图状结构或网状结构,：结构中的数据元素之间存在多个对多个的关系。,集合,线性,树,图,图,1.2 4,类基本结构关系图,6,）,数据类型,：是指在程序语言中，一个值的集合和定义在这个值集上的一组操作的总称。是数据结构在程序语言中的描述。,按“值”的不同特性，在高级程序语言中可分为：,原子类型：其值不可分解。,例如，,C,语言中的基本类型（整型、实型、字符型和 枚举类型）、指针类型和空类型。,结构类型：其值是由若干成分按某种结构组成的，故可分解，并且其成分可以是非结构的，也可以是结构的。,例如，数组的值由若干分量组成，每个分量可以是整数，也可以是数组等。,7,）,抽象数据类型,（,ADT,）：,是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型是对,数据类型,的逻辑抽象，突出数据的逻辑特性，而与其在计算机内部的表示和实现无关。应重点掌握使用,ADT,来,定义和表示数据结构,的方法。,其形式,定义,为：（一个三元组）,（,D,S,P,）,其中，,D,是数据对象，,S,是,D,上的关系集，,P,是对,D,的基本操作集。,书写格式：,ADT,抽象数据类型名,数据对象：,数据关系：,基本操作：,ADT,抽象数据类型名,其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为：,基本操作名（参数表）,初始条件：,操作结果：,ADT Triplet,数据对象：,D=e1,e2,e3|e1,e2,e3,ElemSet,数据关系：,R1=,基本操作：,Get(T,i,&e),初始条件：三元组,T,已存在,1=i=n0,时满足,T(n,)=,Mf(n,),也即是随问题规模,n,的增大，算法执行时间的增长率不超出,f(n,),的增长率,.,这种时间度量称做算法的,渐进时间复杂度,(,asymptotic time complexity,),，简称,时间复杂度,。,例如，在两个,N,N,矩阵相乘的算法中，乘法是基本操作，已知算法如下：,for(i=1;i=n;+i),for(j=1;j=n;+j),cij=0;,for(k=1;k=n;+k),cij+=aik*bkj;,n,n,n,T(n)=O(,n,3,),。,例如，在两个,N,N,矩阵相乘的算法中，乘法是基本操作，已知算法如下：,for(i=1;i=n;+i),for(j=1;j=n;+j),cij=0;,for(k=1;k=n;+k),cij+=aik*bkj;,n,n,n,T(n)=O(,n,3,),。,O(f,)+,O(g,)=,O(max(f,g,),O(f,)+,O(g,)=,O(f+g,),O(f)O(g,)=,O(fg,),如果,g(N,)=,O(f(N,),则,O(f,)+,O(g,)=,O(f,),O(cf(N,)=,O(f(N,),，其中,c,是一个正常数,f=,O(f,),例如，,for(i=1;i=n;+i),for(j=1;j=n;+j),cij=0;,for(k=1;k=n,0,时，满足,T(n,)b),f=,O(f,),算法时间复杂度计算（续）,算法复杂度的计算关键是要找到,f(n,),for(i=1;i=n;+i),for(j=1;j=n;+j),cij=0;/b,for(k=1;k=n;+k),cij+=aik*bkj;/a,cij,=,cij,*,cij,;,/c,T(n)=O(a*,n+b,)*,n+c,)*n)=O(an,3,+bn,2,+cn)=O(n,3,),。,确定问题规模参数,n,查找和,n,相关的操作,计算算法时间,简化表达,