数据结构C语言描述教学课件完整版电子教案.ppt

;21世纪高等院校规划教材数据结构（C语言描述）;第一章 学习数据结构课程的意义;引入： 一般情况下，用计算机解决一个实际问题时，都是先对具体问题抽象，建立问题的求解模型，然后设计相应的算法，编写程序并上机调试，最后解决问题。 ;1.1 实例：高校选修课程管理 1.2 数据结构的主要内容 1.3 算法和算法分析 本章总结;1.1 实例：高校选修课程管理;1.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选修课程;第二步：根据上面给定的抽象数据类型定义，写出实现各种操作的算法描述。 下面以查询操作为例给出伪代码表示： int LocateList( 选修课程 L, 查询条件) { 对给定的查询条件进行分析，确定是对表中哪个数据项进行查询； 对表中元素按给定的查询条件进行查询； 若查询成功，返回记录的位置；否则返回0值，表示表中不存在满足给定条件的记录； };第三步：确定表中的记录的类型（结构体），表在内存中存储方式（按输入顺序存放）。 具体定义如下： struct kechengsrtuct {//选修课程名类型定义 char *kechengming ; // 课程名 int kechengdaima ; // 课程代码 } ; struct chengjistruct { // 成绩类型定义 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 ; // 表中记录的个数 } ; ;结论： 数据结构的实质就是一门研究非数值计算问题的程序设计中计算机的操作对象以及它们之间的关系和运算操作的一门学科。 ;1.1.3 学习本课程的意义 ;1.2 数据结构的主要内容 ;1.2.1 基本概念和术语 ;1.2.2 数据结构定义 ; 逻辑结构是对给定数据结构的一种描述方式，是从实际问题抽象出来的数据模型。主要描述数据元素，及元素之间存在的逻辑关系。 通常按元素间存在的逻辑关系的不同特征，将数据结构分为四类： ?????? ?集合结构 ???????线性结构 ???????树型结构 ??????? 图型结构;集合结构：数据元素之间除了同属于一个集合之外，没有其他关系的数据结构。;线性结构：数据元素之间存在“一对一”线性关系的数据结构。;树型结构：数据元素之间存在“一对多”逻辑关系的数据结构。;图型结构：数据元素之间存在“多对多”逻辑关系的数据结构。; 存储结构又称物理结构，就是数据结构在计算机中的存储方式。它包括数据元素在计算机中的存储方式，还包括元素之间关系在内存中的表示。 根据存储空间的不同分配方式将数据结构分为两类： ???? 顺序存储 链式存储 ; 顺序存储：所有元素存放在一片连续的存储空间中，逻辑上相邻的元素在内存中的物理位置也是相邻的。 注意：元素存放在连续的存储空间中，元素之间的逻辑关系由在内存中的物理位置来体现。 ; 链式存储：所有元素存放在可以不连续的存储单元中，以结点的形式存在，每个结点除了保存数据元素信息外，还通过指针来保存元素之间的关系。 注意：既元素存储在不连续的存储单元中，元素