《数据结构(C语言描述)》第1章学习数据结构的意义

21世纪高等院校规划教材数据结构（C语言描述）ISDN7-5084-3301-7斯庆巴拉主编中国水利水电出版社第一章学习数据结构课程的意义学习重点掌握学习本课程的意义掌握本课程的主体框架和讨论范围掌握如何对算法进行描述和分析引入：一般情况下，用计算机解决一个实际问题时，都是先对具体问题抽象，建立问题的求解模型，然后设计相应的算法，编写程序并上机调试，最后解决问题。1.1实例：高校选修课程管理1.2数据结构的主要内容1.3算法和算法分析本章总结1.1实例：高校选修课程管理1.1.1问题描述1.1.2问题的分析1.1.3学习本课程的意义1.1.1问题描述表1-1是一所学校学生选修课程的选修情况登记表。要求用计算机来完成对学生选修课程的全程管理。通常必备的功能有登记，修改、查询和打印等。在本例中重点完成查询功能。学号姓名系别选修课程名学分成绩课程名课程代码等级分数0351103王杰计算机摄影技术50130351212李丽计算机电脑音乐50210351220商立计算机摄影技术50130432233赵燕机械三维动画30320432118张欣机械三维动画30320322140王芳材料证券投资2053┇┇┇┇┇┇表1-1某学校学生选修课程情况登记表1.1.2问题的分析利用计算机解决实际问题的步骤：第一步：从具体问题抽象出一个适当的数据模型。第二步：进行算法设计。第三步：实现抽象数据类型定义，即从编程语言的角度确定抽象数据类型的存储形式和确定抽象数据类型中每一种操作的具体实现算法。第四步：编制相应的程序代码并进行调试。第一步：抽象数据模型一般包括三部分：处理的数据对象、对象间的关系和需要实现的操作。常用以下格式描述：ADT选修课程{数据对象：D={ai|ai∈记录类型，i=1,2,…,n,n≥0}数据关系：R={Ri|Ri∈记录间关系，i=1,2,…,m,m≥0}基本操作：DengjiList(&L)完成功能：对学生选修情况进行登记EditList(&L)完成功能：对选修情况登记表进行修改LocateList(&L,查询条件)完成功能：根据给定的查询条件，从登记表中查找满足条件的记录PrintList(L)完成功能：打印学生选修情况登记表}ADT选修课程第二步：根据上面给定的抽象数据类型定义，写出实现各种操作的算法描述。下面以查询操作为例给出伪代码表示：intLocateList(选修课程&L,查询条件){对给定的查询条件进行分析，确定是对表中哪个数据项进行查询；对表中元素按给定的查询条件进行查询；若查询成功，返回记录的位置；否则返回0值，表示表中不存在满足给定条件的记录；}第三步：确定表中的记录的类型（结构体），表在内存中存储方式（按输入顺序存放）。具体定义如下：structkechengsrtuct{//选修课程名类型定义char*kechengming;//课程名intkechengdaima;//课程代码};structchengjistruct{//成绩类型定义char*dengji;//成绩等级intfenshu;//分数};structstudent{//表中学生记录类型定义longintnum;//学号char*name;//姓名char*xibie;//系别kechengstructkechent;intxuefen;//学分chengjistructchengji;};表在内存中的存储类型定义：structsqlist{student*A;//将记录顺序存放在一个一维数组中intlen;//表中记录的个数};结论：数据结构的实质就是一门研究非数值计算问题的程序设计中计算机的操作对象以及它们之间的关系和运算操作的一门学科。1.1.3学习本课程的意义数据结构作为一门独立的课程在国外是从1968年开始设立的。瑞士著名计算机科学家N.Wirth提出的著名公式“程序=算法+数据结构”。数据结构是一门介于数学、计算机硬件和软件三者之间的核心课程。用一句话概括：本课程就是从实际问题抽象出数据类型的手段。主要研究计算机所处理的数据对象、对象间存在的关系及进行的各种操作。1.2数据结构的主要内容1.2.1基本概念和术语1.2.2数据结构定义1.2.3逻辑结构的表示方法1.2.1基本概念和术语数据是对客观事物的符号表示，是一种信息的载体，是所有能输入到计算机中并被识别、存储和加以处理的信息的总称。数据元素是数据的基本单位。一个数据元素也可以由若干个数据项组成。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据类型是对计算机中表示的数据对象、对象特征及该数据对象上的一组操作的描述。抽象数据类型是指一个数学模型及定义在该数学模型上的一组操作。定义取决于它的逻辑特性，与其在计算机内部如何表示（存储）和实现无关。1.2.2数据结构定义数据结构是指相互间存在一种或多种特定关系的数据元素的集合。数据⇒具有相同属性的数据元素的集合；结构⇒数据元素间存在的一种或多种关系。对一个给定的数据结构进行分析时，一般从它的逻辑结构、存储结构及对数据元素所进行的操作三个方面进行讨论。（本课程的主要讨论点）逻辑结构是对给定数据结构的一种描述方式，是从实际问题抽象出来的数据模型。主要描述数据元素，及元素之间存在的逻辑关系。通常按元素间存在的逻辑关系的不同特征，将数据结构分为四类：集合结构线性结构树型结构图型结构集合结构：数据元素之间除了同属于一个集合之外，没有其他关系的数据结构。例子：从大街上随意的找五个人组成一个小组，编号分别为1、2、3、4、5，则这五个人之间除了属于同一组以外，相互间不存在任何的关系。组成集合的数据元素之间不存在任何的关系线性结构：数据元素之间存在“一对一”线性关系的数据结构。学号姓名系别学分…0351103王杰计算机3…0351212李丽计算机1…┇┇┇┇…例：学生基本情况登记表中每条学生记录都按一定的顺序排列，除了第一条和最后一条以外，每条记录都只有唯一的前驱和后继元素。元素之间是1：1关系，都只有唯一的前驱和唯一的后继树型结构：数据元素之间存在“一对多”逻辑关系的数据结构。例：一个大学的人事档案管理。每个系有多个专业，但一个专业只能属于一个系；一个专业有多名学生，但一个学生只能属于一个专业学院数学系计算机系外语系应用专业网络专业软件专业教师学生元素之间的关系是1：n，每个元素都只有唯一的前驱元素，但可以有多个后继元素图型结构：数据元素之间存在“多对多”逻辑关系的数据结构。例：五个城市间的交通图。从1可以直达5，也可以经过2、3到达5，或也可以经过2、4到5。12345元素之间的关系是m:n，每个元素都可以有多个前驱元素和多个后继元素存储结构又称物理结构，就是数据结构在计算机中的存储方式。它包括数据元素在计算机中的存储方式，还包括元素之间关系在内存中的表示。根据存储空间的不同分配方式将数据结构分为两类：顺序存储链式存储第一方面第二方面顺序存储：所有元素存放在一片连续的存储空间中，逻辑上相邻的元素在内存中的物理位置也是相邻的。注意：元素存放在连续的存储空间中，元素之间的逻辑关系由在内存中的物理位置来体现。例：对一个由（1，2，3，4，5）五个元素组成的数据结构采用顺序存储，则内存中的存储示意图如下所示：元素1元素2元素3元素4元素5┇起始地址链式存储：所有元素存放在可以不连续的存储单元中，以结点的形式存在，每个结点除了保存数据元素信息外，还通过指针来保存元素之间的关系。注意：既元素存储在不连续的存储单元中，元素间的关系通过结点中的指针信息来体现。元素1元素4元素3元素2┇例：对一个由（1，2，3，4）四个元素组成的数据结构采用链式存储，则内存中的存储示意图如下所示：1.2.3逻辑结构的表示方法二元组表示法表示形式为：D=（K，R）其中，K={a1,a2,…,an}，为数据元素的集合R={r1,r2,…,rm}，为元素之间关系的集合r1={x,y|其中，x,y∈K}…x,y序偶表示：元素x和元素y之间存在关系，并且称元素x为元素y的前驱，元素y为元素x的后继。如果元素x既是元素y的前驱，也是元素y的后继，既x,y且y,x，则用（x,y）形式表示。图形表示法用圆圈来代表数据元素，用带箭头的连线来表示元素之间的关系，如图所示。abcde二元组表示法：D1=(K,R)其中，K={a,b,c,d,e}R={r}r={a,b,b,c,c,d,d,e}1.3算法和算法分析1.3.1算法定义1.3.2算法分析1.3.1算法定义算法是对特定问题求解步骤的一种描述，是一组指令的有限序列，其中每一条指令都代表解题过程中的一个或者多个操作。算法特点：有穷性、确定性、可行性、输入、输出算法描述可以有多种方式，如：用流程图描述、用自然语言描述、还可用数学语言或特定的符号进行描述。本书中所有算法都是用C语言来进行描述。1.3.2算法分析算法的设计要求如下：正确性可读性健壮性效率与低存储量的需求其中，效率指的是算法执行的时间。存储量需求指的是算法执行过程中所需要的最大存储空间，通常主要考虑算法所需的辅助存储空间。这四个设计要求中最主要的是算法的执行时间和执行时所占的存储空间大小。算法的执行时间是指一个算法在计算机上运行时所花费的时间。=简单操作所需要的时间∗简单操作的次数影响算法执行时间的两个因素：（1）每个简单操作执行时所需时间与机器有关，而与算法无关。⇒讨论算法中包含的简单操作的执行次数。（2）另外一个与算法的执行时间相关的是问题的规模。通常算法的执行时间用时间复杂度表示：T(n)=O(f(n))其中，n为问题的规模T（n）为时间复杂度此式子表示，随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。所以只要求出简单操作的次数关于n的增长率即可，然后用n的最高数量级来表示算法的时间复杂度。例：for(j=1;j=n;j++)for(k=1;k=m;k++){++x;s+=x;}分析：各个简单操作的执行次数如下所示：for(j=1;j=n;j++)//次数为1+（n+1）+nfor(k=1;k=n;k++)//执行次数为（1+（n+1）+n）n{++x;//执行次数为n*ns+=x;}//执行次数为n*n简单操作的执行次数之和为：4n2+4n+2，用n的最高数量级表示，时间复杂度为：O（n2）。衡量一个算法性能的另一个标准就是算法执行时所占的存储空间的大小。一般一个算法所占的存储空间包括存储算法所占用的存储空间、算法的输入/输出数据所占用的存储空间和程序运行过程中临时占用的存储空间这三个方面。其中，只有算法执行过程中所占的临时空间与算法有着密切关系。通常一个算法在执行过程中所占用的临时存储空间的大小由空间复杂度来衡量，记作：S（n）=O（f（n））其中，n为问题的规模；S（n）为空间复杂度。通常用n的最高数量级来表示。本章总结：本章介绍了学习数据结构课程的意义、本课程的主题框架及相关内容和如何对算法进行评价。数据结构主要研究计算机所处理的数据对象、对象之间存在的各种关系及进行的各种操作，是用计算机来解决实际问题与编写相应程序两者之间的纽带。数据结构从定义上可以理解为数据+结构。其中，数据指的是所要处理的若干个数据元素的集合；结构指的是数据元素之间的关系。按逻辑结构可分为集合结构、线性结构、树型结构和图型结构四种。按存储结构可分为顺序存储和链式存储两种。算法是解决问题步骤的一种描述，它有有穷性、确定性、可行性、输入和输出等五个特点。一个好的算法应该满足正确性、可读性、健壮性和效率与低存储量需求等四个要求，其中算法的执行效率和低存储量需求是衡量一个算法的最主要的标准。通常用时间复杂度来衡量算法的执行时间，用空间复杂度来衡量算法执行过程中所占用的临时存储空间的大小。它们都是问题的规模n的一个函数，所以用n的最高数量级来表示。