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

《数据结构(C语言描述)》

21世纪高等院校规划教材 数据结构(C语言描述)

ISDN 7-5084-3301-7 斯庆巴拉 主编 中国水利水电出版社

《数据结构(C语言描述)》

第一章 学习数据结构课程的意义学习重点 掌握学习本课程的意义 掌握本课程的主体框架和讨论范围 掌握如何对算法进行描述和分析

《数据结构(C语言描述)》

引入：一般情况下，用计算机解决一 个实际问题时，都是先对具体问题抽 象，建立问题的求解模型，然后设计 相应的算法，编写程序并上机调试， 最后解决问题。

《数据结构(C语言描述)》

1.1 实例：高校选修课程管理 1.2 数据结构的主要内容 1.3 算法和算法分析

本章总结

《数据结构(C语言描述)》

1.1 实例：高校选修课程管理1.1.1 问题描述 1.1.2 问题的分析 1.1.3 学习本课程的意义

《数据结构(C语言描述)》

1.1.1 问题描述表1-1是一所学校学生选修课程的选 修情况登记表。要求用计算机来完成对 学生选修课程的全程管理。 通常必备的功能有登记，修改、查 询和打印等。在本例中重点完成查询功 能。

《数据结构(C语言描述)》

表1-1 某学校学生选修课程情况登记表选修课程名 学号 姓名 系别 课程名 0351103 0351212 0351220 王杰 李丽 商立 计算机 计算机 计算机 摄影技术 电脑音乐 摄影技术 课程代码 501 502 501 学 分 等级 成绩 分数

3 1 3

04322330432118 0322140

赵燕张欣 王芳

机械机械 材料

三维动画三维动画 证券投资

303303 205

22 3

┇

┇

┇

┇

┇

┇

《数据结构(C语言描述)》

1.1.2 问题的分析利用计算机解决实际问题的步骤： 第一步：从具体问题抽象出一个适当的数据模 型。 第二步：进行算法设计。 第三步：实现抽象数据类型定义，即从编程语 言的角度确定抽象数据类型的存储形式和确定 抽象数据类型中每一种操作的具体实现算法。 第四步：编制相应的程序代码并进行调试。

《数据结构(C语言描述)》

第一步：抽象数据模型一般包括三部分：处理的数据对 象、对象间的关系和需要实现的操作。

常用以下格式描述： 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选修课程

《数据结构(C语言描述)》

第二步：根据上面给定的抽象数据类型定义，写出实 现各种操作的算法描述。 下面以查询操作为例给出伪代码表示： int LocateList( 选修课程 &L, 查询条件) { 对给定的查询条件进行分析，确定是对表中哪个数 据项进行查询； 对表中元素按给定的查询条件进行查询； 若查询成功，返回记录的位置；否则返回0值，表示 表中不

存在满足给定条件的记录； }

《数据结构(C语言描述)》

第三步：确定表中的记录的类型(结构体),表在内存 中存储方式(按输入顺序存放)。

具体定义如下：struct kechengsrtuct {//选修课程名类型定义 char *kechengming ; // 课程名 int kechengdaima ; // 课程代码 } ; struct chengjistruct { // 成绩类型定义 char *dengji ; // 成绩等级 int fenshu ; // 分数 } ;

《数据结构(C语言描述)》

struct student { // 表中学生记录类型定义 long int num ; // 学号 char *name ; // 姓名 char *xibie ; // 系别 kechengstruct kechent ; int xuefen ; // 学分 chengjistruct chengji ; } ; 表在内存中的存储类型定义： struct sqlist { student *A ; // 将记录顺序存放在一个一维数组中 int len ; // 表中记录的个数 } ;

《数据结构(C语言描述)》

结论： 数据结构的实质就是一门研究非 数值计算问题的程序设计中计算机的 操作对象以及它们之间的关系和运算 操作的一门学科。

《数据结构(C语言描述)》

1.1.3 学习本课程的意义数据结构作为一门独立的课程在国外是从1968 年开始设立的 。 瑞士著名计算机科学家N.Wirth提出的著名公式 “程序=算法+数据结构”。 数据结构是一门介于数学、计算机硬件和软件 三者之间的核心课程。 用一句话概括：本课程就是从实际问题抽象出 数据类型的手段。主要研究计算机所处理的数 据对象、对象间存在的关系及进行的各种操作。

《数据结构(C语言描述)》

1.2 数据结构的主要内容1.2.1 基本概念和术语 1.2.2 数据结构定义 1.2.3 逻辑结构的表示方法

《数据结构(C语言描述)》

1.2.1 基本概念和术语

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

《数据结构(C语言描述)》

1.2.2 数据结构定义

数据结构是指相互间存在一种或多种特定关系 的数据元素的集合。 数据 具有相同属性的数据元素的集合； 结构 数据元素间存在的一种或多种关系。对一个给定的数据结构进行分析时，一般从它 的逻辑结构、存储结构及对数据元素所进行的 操作三个方面进行讨论。(本课程的主要讨论 点)

《数据结构(C语言描述)》

逻辑结构是对给定数据结构的一种描 述方式，是从实际问题抽象出来的数据 模型。主要描述数据元素，及元素之间 存在的逻辑关系。 通常按元素间存在的逻辑关系的不同 特征，将数据结构分为四类： 集合结构

线性结构 树型结构 图型结构

《数据结构(C语言描述)》

集合结构：数据元素之间除了同属于一个集 合之外，没有其他关系的数据结构。组成集合的数据 元素之间不存在任 何的关系

例子：从大街上随意 的找五个人组成一个 小组，编号分别为1、 2、3、4、5,则这五 个人之间除了属于同 一组以外，相互间不 存在任何的关系。

本文来源：https://www.bwwdw.com/article/pl6i.html