资源描述
数据结构（C语言版）,任课教师：冯向阳,教学计划安排,开课周次：1-16周周一：5、6节，松1318周四：1、2节，松1318上机实践：周四：1、2节(第3周16周)158期终考试形式：闭卷考试,教学计划安排,本课程的内容及学习的基本方法,本课程讲述的主要内容：将分别讲述数据结构的基本概念、线性表、栈和队列、数组、树型结构、图结构、查找、排序等内容。学习本课程的基本方法：上课认真听讲。仔细阅读教材及课件的讲授内容，体会并灵活掌握数据结构中的基本概念和知识点。仔细阅读教材及课件中的大量例题，多做算法练习。,本课程成绩计算,平时成绩占10%上机实践实验占20%期终考试占70%E-mail地址：fengxy网络硬盘URL：,第1章绪论,学习要点熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。了解抽象数据类型的定义、表示和实现方法。熟悉类C语言的书写规范、表示和实现方法。理解算法五个要素的确切含义和对算法正确性的理解。掌握计算语句频度和估算算法时间复杂度的方法。,数据结构的发展史,数据结构作为一门独立的课程在国外是从1968年才开始设立的。1968年美国唐欧克努特教授开创了数据结构的最初体系，他所著的计算机程序设计技巧第一卷基本算法是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。随着计算机技术的不断发展，数据结构广泛应用于计算机科学的各个领域。编译程序利用堆栈、符号表和语法分析树；操作系统由过程并列表和文件支持，并利用由可用空间的并列表或表格组成的存储管理模式；人工智能程序利用堆栈、队列、集、搜索树、表格和图；数据库利用串、并列表、树、环和表格。,数据结构讨论的范畴,数据结构是计算机相关专业的一门重要的专业基础课。它主要研究计算机加工对象的逻辑结构、在计算机中的表示形式以及实现各种基本操作的算法。它是学习操作系统、编译原理、数据库原理等计算机专业核心课程的基础。掌握好这门课程的内容，是学习计算机其他相关课程的必备条件。NikalausWirth(Pascal语言之父)Algorithm+DataStructures=Programs,问题求解,程序编写,数据结构,程序设计,算法,数据结构讨论的范畴,数据处理的种类,数值数据,非数值数据,数值(整数,实数)字符字符串文字图形图象声音,数值性计算,数值性计算：数值计算问题的数学模型通常可以用一组线性或非线性的代数方程组或微分方程组来描述。即使是不需要用计算机求解的简单问题也需要一个数学模型来描述。鸡兔同笼问题：二元一次方程组房屋设计或桥梁设计中的结构应力分析：线性代数方程组天气预报：环流模式方程,数值性计算,例已知：游泳池的长len和宽wide，求面积area,(2)设计求解问题的方法(3)编程main()intlen,wide,area;scanf(“%d%d%n”,(1)建模型：问题涉及的对象：游泳池的长len，宽wide，面积area；对象之间的关系：area=lenwide,非数值性计算,非数值性计算：当操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，就需要对之进行非数值性处理。当计算机进入非数值计算领域，特别是用在管理上的时候，计算机的操作对象之间的关系就无法用数学方程加以描述了。应用举例1学籍档案管理假设一个学籍档案管理系统应包含如下页的表1-1所示的学生信息。,表1-1学生基本情况,非数值性计算(举例1),非数值性计算(举例1),特点：每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格。表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构。对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。,非数值性计算(举例2),1,12,21,123,132,312,213,231,321,3个对象的全排列过程,应用举例2：输出n个对象的全排列可以使用下页所示的图示描述。,非数值性计算(举例2),特点：在求解过程中，所处理的数据之间具有层次关系，这就是我们所说的树形结构。对它的操作有：建立树形结构，输出最底层结点内容等等。应用举例3制定教学计划在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下页的表1-2所示。,非数值性计算(举例3),表1-2计算机专业学生的必修课程,非数值性计算(举例3),C4,C5,C2,C1,C9,C3,C7,C10,C11,C6,C8,C12,图1-2课程先后关系的图形描述形式,非数值性计算(举例3),特点：课程之间的先后关系用图结构描述。通过实施创建图结构，按要求将图结构中的顶点进行线性排序。结论：以上所举例子中的数学模型正是数据结构要讨论的问题。因此，简单地说，数据结构是一门讨论描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现的学科。,基本概念和术语(数据),数据(data)数据是对客观事物的符号表示。在计算机科学中，其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合。例如，一个个人书库管理程序所要处理的数据可能是下表所示的表格。,基本概念和术语(数据元素),数据元素(dataelement)数据元素也称为结点，是数据集合中的一个实体，是数据结构中讨论的基本单位。数据元素按其组成可分为简单型数据元素和复杂型数据元素。前者由一个数据项组成；后者由多个数据项组成，它通常携带着一个概念的多方面信息。,基本概念和术语(数据项),数据项(dataitem)一般情况下，一个数据元素中含有若干个字段，也称为数据项。数据元素是数据项的集合。数据项是数据结构中讨论的最小单位。,数据项之间的关系,数据项和数据项之间存在次序关系例如，一个含12位数的十进制数可以用三个4位的十进制数来表示。3214,6587,9345=a1(3214),a2(6587),a3(9345)在a1、a2和a3之间存在次序关系：、3214,6587,93456587,3214,9345a1a2a3a2a1a3,数据项之间的关系(续),数据项和数据项之间存在次序关系又例，2行3列的二维数组a1,a2,a3,a4,a5,a6行的次序关系:row=,列的次序关系:col=,基本概念和术语(数据结构),数据结构(datastructure)数据结构是以数据项为元素的一种结构。数据结构的组成是由各数据项之间的关系和用来存储、恢复这些数据项的存取函数来确定的。为了叙述上的方便和避免产生混淆，通常把数据的逻辑结构(logicstructure)统称为数据结构，把数据的物理结构统称为存储结构(storagestructure)。,数据的逻辑结构,数据的逻辑结构(logicstructure)数据元素和数据元素之间的逻辑关系成为数据的逻辑结构。如下的表格数据中，各数据元素之间在逻辑上有一种线性关系。,数据的逻辑结构的分类,数据的逻辑结构可归结为以下四类：线性结构：结构中的数据元素之间存在一个对一个的关系。树形结构：结构中的数据元素之间存在一个对多个的关系。图状结构：结构中的数据元素之间存在多个对多个的关系。集合：结构中的数据元素除了同属于一个集合的关系外，别无其他关系。,数据的逻辑结构的分类(续),数据的逻辑结构可归结为以下四类：线性结构树形结构图状结构集合结构,数据结构的形式定义,数据结构的形式定义为：数据结构是一个二元组：Data_Structure=(D,S)其中:D是数据元素的有限集，S是D上关系的有限集。严格地讲，以上定义仅是数据的逻辑结构的定义。例如，在计算机科学中，复数可看成一种数据结构Complex=(C,R)其中，C是含两个实数的集合c1,c2；R=P，而P是定义在集合C上的一种关系，其中有序偶表示c1是复数的实部，c2是复数的虚部。,数据的存储结构,数据的存储结构(storagestructure)是指数据结构在计算机中存储器中的具体实现。与孤立的数据元素的表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表示清楚数据元素之间的逻辑关系。数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。,数据的存储结构(续),顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构。链式存储结构：特点是借助于指示数据元素地址的指针来表示数据元素之间的逻辑结构。在不同的编程环境中，存储结构可有不同的描述方法。用高级语言程序设计语言进行编程时，通常可用该语言提供的数据类型来描述。,数据类型,数据类型：是指程序设计语言中各变量可取的数据类型。数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密切相关。一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。可以认为，数据类型是在程序设计中已经实现了的数据结构。另一方面，在程序设计过程中，当需要引入某种新的数据类型时，总是借助编程语言所提供的数据类型来描述数据的存储结构。,C+的基本数据类型及取值的范围,抽象数据类型,抽象数据类型(AbstractDataType简称ADT)：ADT是指一个数学模型以及定义在此数学模型上的一组操作。ADT的两个重要特征：数据抽象：用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口(即外界使用它的方法)。数据封装：将实体的外部特征和其内部实现细节分离，并且对外部用户隐蔽其内部实现细节。ADT需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。,抽象数据类型的格式定义,ADT的格式定义：和数据结构的形式定义相对应，ADT可用一个三元组表示：ADT_Data_Structure=(D,S,P)其中:D是数据对象，S是D上的关系集，P是对D的基本操作集。ADT可用以下格式来定义：ADT抽象数据类型名数据对象：数据关系：基本操作：ADT抽象数据类型名,抽象数据类型(举例),例如，抽象数据类型复数的定义：ADTComplex数据对象：D=e1,e2|e1,e2RealSet数据关系：R1=|e1是复数的实数部分，|e2是复数的虚数部分基本操作：InitComplex(case值n：语句序列n；break；default：语句序列n+1;,算法描述语言(续),在算法描述中可以使用的选择结构语句形式有：开关语句2switch(表达式)case条件1：语句序列1；break;case条件n：语句序列n；break；default：语句序列n+1;,算法描述语言(续),在算法描述中可以使用的循环结构语句形式有：for循环语句for(表达式1；循环条件表达式；表达式2)语句；while循环语句while(循环条件表达式)语句；do-while循环语句do语句序列；while(循环条件表达式)；,算法描述语言(续),在算法描述中可以使用的结束语句形式有：函数结束语句return表达式；return;case或循环结束语句break；异常结束语句exit(异常代码)；在算法描述中可以使用的输入输出语句形式有：输入语句scanf(格式串，表达式1，表达式n)；输出语句printf(格式串，表达式1，表达式n)；方括号()中的内容是可以省略的部分。,算法描述语言(续),在算法描述中使用的注释格式有：单行注释/文字序列在算法描述中可以使用的扩展函数有：求最大值max(表达式1，表达式n)；这个函数返回参数表中n个表达式计算结果中的最大值。求最小值min(表达式1，表达式n)；这个函数返回参数表中n个表达式计算结果中的最小值。,算法描述语言(举例),【算法1-1】用类C描述将三个数值排序的算法：voidThree_Sort(int*x,int*y,int*z)/将x,y,z三个指针所指示的内容按从大到小的顺序重新排列if(*y*xi=n;+i)for(j=1;j=n;+j)ci,j=0;for(k=1;k=n;+k)ci,j+=ai,k*bk,j;基本操作：乘法操作时间复杂度：O(n3),算法的时间复杂度(举例2),例二：在下列程序段中Voidselect_sort(inta,intn)/将a中的整数序列重新排列成自小至大的顺序for(i=0;in1;+i)j=i;for(k=i+1;kn;+k)if(akaj)j=k;if(j!=i)ajai;基本操作：比较(数据元素)操作时间复杂度：O(n2),算法的时间复杂度(举例3),例三：在下列程序段中i=1;while(i=n)i=i*5;基本操作：乘法操作假设基本操作的执行次数为y，则：5y=n，y取最大值时，5y=n即基本操作的最多执行次数为y=log5n时间复杂度：O(log5n),算法的空间复杂度,空间复杂度类似于算法的时间复杂度，算法的存储空间的需求可以设计成一个以问题的规模n为自变量的函数S(n)=O(g(n)。这个函数表示随问题规模n的增大，算法运行所需存储量的增长率和函数g(n)的增长率相同。称函数S(n)为算法的空间复杂度。算法的存储量包括：输入数据所占空间；程序本身所占空间；辅助变量所占空间。,算法的空间复杂度(续),空间复杂度辅助空间就是除算法代码本身和输入输出数据所占据的空间外，算法临时开辟的存储空间单元。若输入数据所空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。若所需存储量依赖于特定的输入，除特别指明外，通常按最坏的情况考虑。,第1章基本知识结构图,绪论,数据结构概念的引出,基本概念和术语,抽象数据类型,算法和算法分析,数据,数据元素,数据对象,数据结构,数据类型,存储结构,抽象数据类型的定义,抽象数据类型的表示,抽象数据类型的实现,算法设计的要求,算法设计的度量,算法存储空间的需求,课后作业,1.数据结构和数据类型两个概念之间有区别吗？2.简述线性结构与非线性结构的不同点。3.分析下面各程序段的时间复杂度。,2.s=0;for(i=0;in;i+)for(j=0;jn;j+)s+=Bij;sum=s;,1.for(i=0;in;i+)for(j=0;jm;j+)Aij=0;,x=0;for(i=1;in;i+)for(j=1;j=n-i;j+)x+;,4.i=1;while(i=n)i=i*3;,
展开阅读全文