数据结构与算法-全套PPT课件.pptx

学习本课程目的? 训练数据抽象能力 ；— 从问题提炼出数据? 训练算法设计与描述能力 ； — 用算法描述问题 ? 掌握常用数据结构与基本运算 ；Wirth公式：算法 + 数据结构 = 程序 学好本课程的意义问题：教师向机房里100台学生电脑发送文件。 UDP广播方式特点：速度快，但是容易发生数据丢失 TCP单播方式特点：保证到达，但速度慢 我的改进方式：特点：保证到达，且不慢 常识如何学好本课程？常识：为什么人们痛恨插队？数据结构：有n个元素组成的队列，在第i各元素之前插入一个元素，需要向后移动多少的元素？ 人脑变电脑问题：求1到100的和。i=1 s=1i=2 s=3i=3 s=6i=4 s=10i=5 s=15…… 考试方式按章节考随堂考电脑上考计相对分随时做好考试准备 相对计分举例亲：考试时千万别偷懒哟！学生正确完成题目数得分A20100B1890C1260D1050 注意两个区别区别本课程与数学课区别本课程与程序设计 课程主要内容： ? 二元关系、数据结构的概念、算法及其效率分析； ? 顺序表及其运算、应用(栈、队列)； ? 数组与矩阵压缩存储； ? 链表及其运算、广义表； ? 树与二叉树 (表示、存储、运算、应用)； ? 图 (概念、存储、遍历、典型应用)； ? 查找技术 (顺序表、索引表、散列表、树表、字符串匹配)； ? 排序方法(交换、插入、选择、归并、基数、拓扑、 外部排序)。 第一章 绪 论1.1 数据抽象与二元关系 一、数据抽象 二、集合的笛卡尔积 三、二元关系1.2 数据结构的基本概念 一、什么是数据结构 二、数据结构的表示 三、抽象数据类型1.3 算法描述与算法分析 一、算法的基本特征 二、算法描述 三、算法设计的常用方法 四、算法的时间复杂度与空间复杂度 1.1 数据抽象与二元关系一、数据抽象1. 数据抽象是数据处理中首先要解决的问题—— 得到数据模型问题1.1 统计全年级学生的成绩，要求： ① 按学分积排序输出全年级学生的姓名、学号、班级、成绩； ② 按①排序的基础上，按总学分排序输出学生的信息学生集合抽象若干学生记录(姓名、学号、班级、成绩)；元素间的关系抽象学生之间的成绩高低关系。抽象结果 ：学生成绩表 1.1 数据抽象与二元关系问题1.2 某设备的部件构成关系如下： 部件编号 部件组成 p1 p1 p2 p2 p3 p1, p2 p4 p1, p3 p5 p2, p3 p6 p3, p4 p7 p2, p6, p8 p8 p5, p6问：如何安排这些部件的加工流程 ？ 1.1 数据抽象与二元关系数据抽象：部件抽象数据元素；组成关系抽象数据元素之间的前后关系；抽象结果 ：数据元素间的关系图(图结构)；选择算法：存储关系图，采用拓扑分类方法处理 —— 以顺序存储表示实现处理结果：加工装配顺序表 1.1 数据抽象与二元关系数据元素之间的前后关系图:p6p1p2p3p4p5p8p7 1.2 数据结构的基本概念一、什么是数据结构数据结构是对问题中的数据元素及相互间的联系的抽象。例 1， 列出我国主要地区一年的气象条件及万物变化的规律 —— 节气表立春，雨水，惊蛰，春分，清明，谷雨；春：夏：立夏，小满，芒种，夏至，小暑，大暑；秋：立秋，处暑，白露，秋分，寒露，霜降；冬：立冬，小雪，大雪，冬至，小寒，大寒。 1.2 数据结构的基本概念例2， 为了更好的支援和帮助边远地区和有困难的人民群众脱贫致富，暑期实践中，大家都积极报名参加扶贫志愿者队伍。现要对报名情况进行统计统计。 —— 扶贫志愿者报名表姓名 专 业年龄性别 学历 所在院系 服务支持张三通信与信息系统 25 男 硕士 电子系相关系统维修、更新、开发李四 法学 24 女 硕士 法学院法律咨询、援助 ? ? ? ? ? ? ?扶贫志愿者报名表（以报名次序排列） 1.2 数据结构的基本概念例3，简单描述一本书的章节