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

《《数据结构(C语言描述)》学习数据结构的意义》由会员分享，可在线阅读，更多相关《《数据结构(C语言描述)》学习数据结构的意义（36页珍藏版）》请在金锄头文库上搜索。

1、21世纪高等院校规划教材 数据结构（C语言描述）ISDN 7-5084-3301-7 斯庆巴拉 主编 中国水利水电出版社第一章 学习数据结构课程的意义学习重点n掌握学习本课程的意义n掌握本课程的主体框架和讨论范围n掌握如何对算法进行描述和分析引入：一般情况下，用计算机解决一 个实际问题时，都是先对具体问题抽 象，建立问题的求解模型，然后设计 相应的算法，编写程序并上机调试， 最后解决问题。 n1.1 实例：高校选修课程管理n1.2 数据结构的主要内容n1.3 算法和算法分析n本章总结1.1 实例：高校选修课程管理n1.1.1 问题描述n1.1.2 问题的分析n1.1.3 学习本课程的意义1.1

2、.1 问题描述表1-1是一所学校学生选修课程的选 修情况登记表。要求用计算机来完成对 学生选修课程的全程管理。通常必备的功能有登记，修改、查 询和打印等。在本例中重点完成查询功 能。 学号姓名系别选修课程名 学 分成绩课程名课程代码等级分数0351103王杰计算机摄影技术5013 0351212李丽计算机电脑音乐5021 0351220商立计算机摄影技术5013 0432233赵燕机械三维动画3032 0432118张欣机械三维动画3032 0322140王芳材料证券投资2053 表1-1 某学校学生选修课程情况登记表 1.1.2 问题的分析 利用计算机解决实际问题的步骤：n第一步：从具体问题

3、抽象出一个适当的数据模 型。 n第二步：进行算法设计。 n第三步：实现抽象数据类型定义，即从编程语 言的角度确定抽象数据类型的存储形式和确定 抽象数据类型中每一种操作的具体实现算法。 n第四步：编制相应的程序代码并进行调试。 第一步：抽象数据模型一般包括三部分：处理的数据对 象、对象间的关系和需要实现的操作。常用以下格式描述： ADT 选修课程 数据对象：D=ai | ai记录类型，i=1,2,n , n0数据关系：R=Ri | Ri记录间关系，i=1,2,m , m0基本操作：DengjiList ( / 课程名 int kechengdaima ; / 课程代码 ;struct cheng

4、jistruct / 成绩类型定义 char *dengji ; / 成绩等级 int fenshu ; / 分数 ;struct student / 表中学生记录类型定义 long int num ; / 学号 char *name ; / 姓名 char *xibie ; / 系别 kechengstruct kechent ; int xuefen ; / 学分 chengjistruct chengji ; ;表在内存中的存储类型定义： struct sqlist student *A ; / 将记录顺序存放在一个一维数组中 int len ; / 表中记录的个数 ; 结论：数据结构的

5、实质就是一门研究非 数值计算问题的程序设计中计算机的 操作对象以及它们之间的关系和运算 操作的一门学科。 1.1.3 学习本课程的意义 n数据结构作为一门独立的课程在国外是从1968 年开始设立的 。n瑞士著名计算机科学家N.Wirth提出的著名公式 “程序=算法+数据结构”。n数据结构是一门介于数学、计算机硬件和软件 三者之间的核心课程。 n用一句话概括：本课程就是从实际问题抽象出 数据类型的手段。主要研究计算机所处理的数 据对象、对象间存在的关系及进行的各种操作 。 1.2 数据结构的主要内容 n1.2.1 基本概念和术语 n1.2.2 数据结构定义 n1.2.3 逻辑结构的表示方法 1.

6、2.1 基本概念和术语 n数据是对客观事物的符号表示，是一种信息的载 体，是所有能输入到计算机中并被识别、存储和 加以处理的信息的总称。 n数据元素是数据的基本单位。一个数据元素也可 以由若干个数据项组成 。n数据对象是性质相同的数据元素的集合，是数据 的一个子集。 n数据类型是对计算机中表示的数据对象、对象特 征及该数据对象上的一组操作的描述。n抽象数据类型是指一个数学模型及定义在该数学 模型上的一组操作。定义取决于它的逻辑特性， 与其在计算机内部如何表示（存储）和实现无关 。 1.2.2 数据结构定义 n数据结构是指相互间存在一种或多种特定关系 的数据元素的集合。数据具有相同属性的数据元素

7、的集合；结构数据元素间存在的一种或多种关系 。n对一个给定的数据结构进行分析时，一般从它 的逻辑结构、存储结构及对数据元素所进行的 操作三个方面进行讨论。（本课程的主要讨论 点） 逻辑结构是对给定数据结构的一种描 述方式，是从实际问题抽象出来的数据 模型。主要描述数据元素，及元素之间 存在的逻辑关系。通常按元素间存在的逻辑关系的不同 特征，将数据结构分为四类：集合结构线性结构树型结构图型结构集合结构：数据元素之间除了同属于一个集 合之外，没有其他关系的数据结构。例子：从大街上随意 的找五个人组成一个 小组，编号分别为1、 2、3、4、5，则这五 个人之间除了属于同 一组以外，相互间不 存在任何

8、的关系。 组成集合的数据 元素之间不存在任 何的关系线性结构：数据元素之间存在“一对一”线性关 系的数据结构。学号姓名系别学分0351103王杰计算机30351212李丽计算机1例：学生基本情况登记表中每 条学生记录都按一定的顺序排 列，除了第一条和最后一条以 外，每条记录都只有唯一的前 驱和后继元素。元素之间是1：1关系 ，都只有唯一的前驱 和唯一的后继树型结构：数据元素之间存在“一对多”逻辑关 系的数据结构。例：一个大学的人事档案管理。每个系有多个专业， 但一个专业只能属于一个系；一个专业有多名学生， 但一个学生只能属于一个专业元素之间的关系是1 ：n，每个元素都只 有唯一的前驱元素， 但

9、可以有多个后继元 素图型结构：数据元素之间存在“多对多”逻辑关 系的数据结构。例：五个城市间的交通图。从1可以直达5，也可以经 过2、3到达5，或也可以经过2、4到5。元素之间的关 系是m:n，每个 元素都可以有 多个前驱元素 和多个后继元 素存储结构又称物理结构，就是数据 结构在计算机中的存储方式。它包括数 据元素在计算机中的存储方式，还包括 元素之间关系在内存中的表示。根据存储空间的不同分配方式将数 据结构分为两类：顺序存储链式存储第一方面第二方面顺序存储：所有元素存放在一片连续的存 储空间中，逻辑上相邻的元素在内存中的物理 位置也是相邻的。注意：元素存放在连续的存储空间中，元素之 间的逻

10、辑关系由在内存中的物理位置来体现。 例：对一个由（ 1，2，3，4，5 ）五个元素组成 的数据结构采用 顺序存储，则内 存中的存储示意 图如下所示：元素1元素2元素3元素4元素5起始地址链式存储：所有元素存放在可以不连续的 存储单元中，以结点的形式存在，每个结点除 了保存数据元素信息外，还通过指针来保存元 素之间的关系。注意：既元素存储在不连续的存储单元中 ，元素间的关系通过结点中的指针信息来体现 。 元素1 元素4 元素3 元素2 例：对一个由（1，2 ，3，4）四个元素组 成的数据结构采用链 式存储，则内存中的 存储示意图如下所示 ：1.2.3 逻辑结构的表示方法 n二元组表示法 表示形式

11、为：D=（K，R） 其中，K=a1 , a2 , , an ，为数据元素的集合R=r1 , r2 , , r m ，为元素之间关系的集合r1= | 其中，x,yK 序偶表示：元素x和元素y之间存在关系， 并且称元素x为元素y的前驱，元素y为元素x的后继 。如果元素x既是元素y的前驱，也是元素y的后继， 既且，则用（x,y）形式表示。n图形表示法用圆圈来代表数据元素，用带箭 头的连线来表示元素之间的关系，如 图所示。二元组表示法：D1=( K , R )其中，K=a,b,c,d,e R=rr = , , , 1.3 算法和算法分析 n1.3.1 算法定义 n1.3.2 算法分析 1.3.1 算法

12、定义 n算法是对特定问题求解步骤的一种描述，是一组指令 的有限序列，其中每一条指令都代表解题过程中的一 个或者多个操作。n算法特点：有穷性、确定性、可行性、输入、输出n算法描述可以有多种方式，如：用流程图描述、用自 然语言描述、还可用数学语言或特定的符号进行描述 。本书中所有算法都是用C语言来进行描述 。1.3.2 算法分析 算法的设计要求如下：正确性可读性健壮性效率与低存储量的需求其中，效率指的是算法执行的时间。存 储量需求指的是算法执行过程中所需要的最 大存储空间，通常主要考虑算法所需的辅助 存储空间。 这四个设计要求中最主要的是算法的执 行时间和执行时所占的存储空间大小。 算法的执行时间

13、是指一个算法在计算机上 运行时所花费的时间。=简单操作所需要的时间简单操作的次数影响算法执行时间的两个因素：（1）每个简单操作执行时所需时间与机 器有关，而与算法无关。讨论算法中包含的 简单操作的执行次数。（2）另外一个与算法的执行时间相关的 是问题的规模。 通常算法的执行时间用时间复杂度表示 ：T(n) = O( f ( n ) )其中，n为问题的规模T（n）为时间复杂度此式子表示，随着问题规模n的增大， 算法执行时间的增长率和f(n)的增长率相同 。所以只要求出简单操作的次数关于n的增 长率即可，然后用n的最高数量级来表示算 法的时间复杂度。 例： for (j=1;j=n;j+)for

14、(k=1;k=m;k+) +x;s+=x; 分析：各个简单操作的执行次数如下所示： for (j=1;j=n;j+)/次数为1+（n+1） +n for (k=1;k=n;k+)/执行次数为（1+（n+1）+n） n +x; /执行次数为n*ns+=x; /执行次数为n*n简单操作的执行次数之和为：4n2+4n+2，用 n的最高数量级表示，时间复杂度为：O（n2）。衡量一个算法性能的另一个标准就是算法执行 时所占的存储空间的大小。一般一个算法所占 的存储空间包括存储算法所占用的存储空间、 算法的输入/输出数据所占用的存储空间和程序 运行过程中临时占用的存储空间这三个方面。 其中，只有算法执行过

15、程中所占的临时空间与 算法有着密切关系。通常一个算法在执行过程中所占用的临时存 储空间的大小由空间复杂度来衡量，记作：S（n）= O（f（n）其中，n为问题的规模；S（n）为空间复杂度 。通常用n的最高数量级来表示。 本章总结：n本章介绍了学习数据结构课程的意义、本课程 的主题框架及相关内容和如何对算法进行评价 。n 数据结构主要研究计算机所处理的数据对象、 对象之间存在的各种关系及进行的各种操作， 是用计算机来解决实际问题与编写相应程序两 者之间的纽带。n数据结构从定义上可以理解为数据+结构。其 中，数据指的是所要处理的若干个数据元素的 集合；结构指的是数据元素之间的关系。按逻 辑结构可分为集合结构、线性结构、树型结构 和图型结构四种。按存储结构可分为顺序存储 和链式存储两种。 算法是解决问题步骤的一种描述，它有有 穷性、确定性、可行性、输入和输出等五个特 点。一个好的算法应该满足正确性、可读性、 健壮性和效率与低存储量需求等四个要求，其 中算法的执行效率和低存储量需求是衡量一个 算法的最主要的标准。通常用时间复杂度来衡 量算法的执行时间，用空间复杂度来衡量算法 执行过程中所占用的临时存储空间的大小。它 们都是问题的规模n的一个函数，所以用n的最 高数量级来表示。