实用数据结构基础（第五版） 课件全套 王中华 第01--10章-绪论--- 多维数组和广义表.pptx

第1章绪论

第1章绪论1.1数据结构概述1.2数据的逻辑结构 1.3数据的存储结构1.4算法和算法的效率1.5实验预备知识 2

重难点数据结构中的常用基本概念和术语四种逻辑结构及其描述四种存储结构，及其与算法的关系算法的描述和复杂度分析算法时间和空间复杂度的计算方法C++中的引用变量和引用参数C语言复习：指针、结构体、文件、数字菜单3

1.1数据结构概述1.1.1数据结构研究的内容什么是数据结构？数据——特指数据元素，现实世界中存在的一个独立个体的相关信息(结构体变量、对象、记录)，也称之为结点。结构——数据元素之间存在的关系。逻辑结构：指数据元素之间的逻辑关系。存储结构：也称物理结构，指数据的逻辑结构在计算机中的实现。算法——解决问题方法(步骤)的描述。4数据结构＝数据＋(逻辑、存储)结构＋少量算法

1.1.1数据结构研究的内容所谓数据元素，就是C语言中的结构体变量例如：书籍元素——Book结构体类型可以根据需要，在Book结构体中增加出版社、出版年份、版本号和印数等成员。5typedefstruct{charisbn[16];chartitle[32];charauthor[16];intpages;doubleprice;}Book;数据项

1.1.1数据结构研究的内容所谓数据元素，就是C语言中的结构体变量例如：学生元素——Student结构体类型可以根据需要，将成员score定义为数组，以便存储多门课程的成绩；还可以将成员age改名为birthday，将其定义为日期类型等。6typedefstruct{charstuId[16];charname[16];chargender;intage;doublescore;}Student;数据项

1.1.2典型数据结构举例用计算机解决具体实际问题的步骤：(1)从问题抽象出适当的数学模型(对象、关系)；(2)分析逻辑结构(提取数据元素、建立逻辑关系)(3)根据逻辑结构的主要操作，确定存储结构(4)基于选定的存储结构，设计求解数学模型的算法(解决问题的方法)；(5)编写程序、运行并调试，直到解决问题。7

1.1.2典型数据结构举例数据存储结构的选择，依赖于逻辑结构；算法的设计，必须基于数据的存储结构；例如：8

1.1.2典型数据结构举例——线性结构【例1-1】学生入学情况登记表9

1.1.2典型数据结构举例——树形结构【例1-2】井字棋对弈问题10

七桥问题1.1.2典型数据结构举例——图形结构【例1-3】七桥问题11欧拉回路

1.2数据的逻辑结构——四种集合结构树形结构(一对多)12线性结构(一对一)图形结构(多对多)ABCDEF没有前驱，有且仅有一个后继。没有后继，有且仅有一个前驱。ABECDFGRABCDEGHFIJK一个双亲，多个孩子。边为邻接关系

1.2数据的逻辑结构——四种(1)集合结构数据元素之间，除了“同属于一个集合”的关系外，别无其它关系。(2)线性结构(线性表、栈、队列、串)数据元素之间，存在着“一对一”的关系。(3)树形结构(树、二叉树)数据元素之间，存在着“一对多”的关系。(4)图形结构(图、网)数据元素之间，存在着“多对多”的关系。13

1.2.1基本概念数据(Data)数据是信息的载体，是对客观事物的符号表示。通俗的说，凡是能被计算机识别、存取和处理的符号、图形、图像、声音、视频信号等都可以称之为数据。数据元素(DataElement)数据元素是对现实世界中，某个独立个体的数据描述，是数据的基本单位。数据元素俗称为结点(Node)，也称其为记录(record)，在计算机中常作为一个整体来处理。14

1.2.1基本概念数据项(DataItem)数据项是不可分割的、具有独立意义的最小数据单位，是对数据元素属性的描述。数据项也称为域，或字段(Field)。数据对象(DataObject)数据对象是相同数据元素的集合；例如：在“学生入学情况登记表”中，数据对象是全体学生记录(数据元素)的集合。数据的逻辑结构(DataStructure)相互之间存在特定关系的数据元素的集合。15

1.2.1基本概念直接前驱每个数据元素的前面，紧挨着它的那个元素，称为它的直接前驱，可简称为前驱(precursor)。直接后继每个数据元素的后面，紧挨着它的那个元素，称为它的直接后继，可简称为后继(next)。线性结构中，第一条记录没有直接前驱，称为开始结点；最后一条记录没有直接后继，称为终端结点。16ABCDEF开始结点终端结点

1.2.2逻辑结构的描述数据元素之间的逻辑关系，