数据结构绪论课件

1、数据结构数字媒体技术教研室课程介绍程序设计基础课程群程序设计语言C，C+，Java，Python，学习如何向计算机传达指令并获取执行结果数据结构Data Structures研究数据及其关系的学科学习为问题建立模型2算法：如何处理数据以达到想要的结果参考书籍数据结构与算法分析：C语言描述Mark Allen Weiss机械工业出版社算法Robert Sedgewick，Kevin Wayne人民邮电出版社34学时安排总学时：64理论教学：32学时上机实验：32学时学分：45课程考核平时成绩课程作业实验实验报告+程序代码纪律考勤+课堂纪律全勤加分无故迟到、缺勤扣分期末考试闭卷笔试基础算法基本数据

2、结构课程主题绪论线性表栈和队列串、数组和广义表树和二叉树图查找排序Topic 1 绪论1. 绪论1.1 数据结构的研究内容1.2 基本概念和术语1.3 抽象数据类型的表示与实现1.4 算法和算法分析1.1 数据结构的研究内容计算“桑弘羊以计算用事，侍中。”核算数目，根据已知量算出未知量计算的逻辑有哪些已知量？已知量之间、已知量与未知量之间有何种关系？数学模型：某体系内各数量之间的关系1.1 数据结构的研究内容计算机能够执行数值计算和逻辑计算的机器数值计算：加减乘除乘方开放微积分等逻辑计算：与，或，非，大于，小于，等于第一台通用计算机ENIAC（1946），用于弹道计算1112用计算机求解问题求

3、解过程建立数学模型设计算法编写程序运行程序13建立模型是求解问题必不可少之第一步用计算机求解问题数学模型采用数学语言概括或近似地表述出的一种数学结构以描述某个事物系统的特征或数量依存关系【思考】在以往的学习经历中，是否针对一个问题探求过其数学模型？14【例】某班共有学生34人，其中男生人数比女生人数的一半多10人。求男、女生各多少人？已知量：总人数，男女生人数差额未知量：男女生各自人数数量间关系：二元一次方程组解：设有男生x人，女生有y人x + y = 34x - y/2 = 10数学模型两类问题数值问题应力计算，人口增长估算，弹道计算，数学模型：方程，方程组不在本课程研究范围内：数值分析非数

4、值问题博弈，控制，管理，媒体，无法用数学方程描述系统特征和数量关系数学模型：数据结构161.1 数据结构的研究内容典型非数值处理举例学生学籍管理系统人机对弈问题最短路径问题17【例1.1】学生学籍管理系统P1-2数量学生基本信息(学号，姓名，性别，)按顺序依次存放于学生基本信息表根据需要在表中查找每个学生信息条目之间呈线性关阳 060214202薛林 060214215王诗萌 060214216冯子晗 【例1.2】人机对弈问题P2计算机将对弈策略预先存储好必须考虑对弈过程中所有可能出现的情况棋局发展趋势预测操作对象：格局20多种选择多种选择【例1.2】人机对弈问题当前

5、格局衍生出多个后续格局形似一棵倒长的树数学模型：树结构表示的格局关系算法：博弈规则和策略22【例1.3】最短路径问题P2城市A和B之间有多条道路，但交通费不同，如何选择最廉价的线路？抽象为图的最短路径问题23ABECD100301010502060【例1.3】最短路径问题顶点代表城市边代表通路边的权值代表交通费顶点A到B的路径：ABAD+DBAE+EC+CB 路径上各边权值之和即费用25ABECD100301010502060【例1.3】最短路径问题图结构多对多的网状结构26ABECD1003010105020601.1 数据结构的研究内容非数值问题的数学模型不再是方程或方程组而是数据结构线性

6、结构树形结构图结构271.1 什么是数据结构数据结构的定义相互之间存在一种或多种特定关系的数据元素的集合一门研究非数值计算程序设计问题中计算机操作对象以及它们之间关系和操作的学科P3281.1 什么是数据结构29【思考】怎样为一个游戏场景建立模型（即数据结构）？1. 绪论1.1 数据结构的研究内容1.2 基本概念和术语1.3 抽象数据类型的表示与实现1.4 算法和算法分析1.2 基本概念和术语数据、数据元素、数据项和数据对象数据结构数据类型和抽象数据类型311.2.1 数据、数据元素、数据项和数据对象P332数据(Data)能够输入计算机并处理的符号总称思考：哪些是数据？简单数据：整数，实数，

7、字符，复合数据：学生信息、棋盘格局、城市间道路总体概念P3数据元素（DatA Element）34一个数据单元某本书的信息，某个格局，某条通路数据元素是程序的操作对象作为整体考虑和处理排序，查找，遍历，P3数据项（Data Item）35数据元素内部具有实际意义的分支项书：书名，作者，ISBN，类别，联系人：姓名，手机号，住址，逻辑上不可再分，再分则无意义数据对象（Data Object）36性质相同的元素集合整数集合字母集合学生信息集合1.2.2 数据结构37相互之间存在一种或多种关系的数据元素的集合结构 ：数据元素之间的关系逻辑结构存储结构逻辑结构38从逻辑关系上描述数据基于人类认知不考虑

8、如何用计算机表示从具体问题抽象出来的数学模型两个要素数据元素关系：数据元素间的逻辑关系四类基本数据结构集合元素之间没有任何关系线性结构一对一关系树一对多关系图多对多关系逻辑结构40理解基本的逻辑结构P4最下(1)(2)(3)(4)存储结构41数据结构在计算机中的表示存储各数据元素结点（Node）存储数据元素之间的关系顺序存储结构链式存储结构顺序存储结构一个班所有学生按学号顺序安排宿舍该班第一个宿舍编号为401第一位学生学号为1001宿舍按顺序安排，宿舍号无间隔，每寝恰好住6人思考：如何通过某生学号x计算其所在宿舍号R(x)？R(x) = 401 + (x - 1001) / 6 顺序存储结构4

9、3借助元素在内存中的相对位置表示元素之间的逻辑关系逻辑结构相邻的元素在内存中也相邻已知一个元素在内存中的位置，可以推算相邻元素的位置P5顺序存储结构44例：如果已知首元素A地址为base各元素占用空间大小为L则第n个元素所在的内存地址为：base + L * (n - 1)ABCD0300A0300 + L * 1B0300 + L * 2C0300 + L * 3D顺序存储结构存在的问题顺序存储结构需要一块大小恰好合适的存储空间存储空间不能灵活扩展和收缩并非所有逻辑结构都能用顺序存储结构来表示链式存储结构结点各结点随机分配存储空间无需占用连续的整块存储空间结点之间的关系每个结点除了存储数据元素外，附加额外的指针字段来保存后继结点所在的内存地址无法通过计算来获得