数据结构课件第1章.ppt

课时安排 专业必修，4.5学分 总学时：70小时 上课：54小时 试验：16小时 考试 成绩计算 平时成绩：30% 考勤+课堂表现+作业+上机实验报告+上机考察 考试成绩：70% 要求：上机不能做与该课程无关的内容。 注意：无故缺勤或上机时间玩游戏等第1次平时成绩扣5分，第2次扣10分，第3次扣15分，第4次扣20分，第5次扣30分，第6次平时成绩为0。 教材与参考书 教材：苏德富，《数据结构（C语言）》，重庆大学出版社 参考书：严蔚敏，《数据结构》，清华大学出版社 李勤，《数据结构》，中国电力出版社 Clifford A. Shaffer，《数据结构与算法分析》，电子工业出版社 课程重要性简介 课程主要内容简介 常见的几种时间复杂度数量级 算法的阶 设非负函数f(n)和g(n)，n∈N，如果存在正常数c和正整数n0 ，使得当n≥n0 时，有f(n)≤cg(n)，则称f(n)的阶小于或等于g(n)的阶；记为 f(n)∈O(g(n))，读作f(n)是 g(n)的大O。 算法的阶 算法的阶 例如：2n-5 ∈ O(n2)，因为当n?∞时，lim (2n -5)/n2 = 2/n - 5/n2 ?0-0=0；----低阶 例如：5n2 -3n=θ(n2)，因为当n?∞时，lim (5n2 -3n)/n2 = 5 - 3/n?5-0=5；----同阶 例如： n2 +5n=Ω(n)，因为当n?∞时，lim (n2 +5n)/n= n +5 ?∞；----高阶 本章重点 1.数据结构的有关基本概念 作业1 * 数据结构 （C语言版） 是计算机相关专业考研的重点内容 大公司笔试的主要内容 是计算机专业核心必修课，是其它后续计算机课程的重要基础 是非计算机专业的主要选修课 数据结构在学科中的地位 《数据结构》是计算机科学中一门综合性的专业基础课。数据结构的研究不仅涉及计算机的硬件的研究范围，而且和计算机软件的研究有着更为密切的关系，无论是编译程序还是操作系统，都涉及数据元素在存储器中的分配问题。可以认为数据结构是介于数学、计算机硬件、计算机软件三者之间的一门核心课程。 《数据结构》 所处的地位 数据的逻辑结构 数据的存储结构(顺序与链式) 及其操作(算法)（插入、删除与遍历等） 线性表、树和图 查找与排序（属常用算法总结） 算法的时空效率分析法 本课程章节主要内容 第一章：绪论 第二章：线性表和数组 第三章：栈和队列 第四章：串 第五章：树和二叉树 第六章：图 第七章：排序 第八章：查找 第九章：文件 第一章 绪 论 数据结构的引论 例1 图书馆的书目检索系统自动化问题 －－线形数据结构，1：1的关系 在书目自动检索系统中可以建立一张按登录顺序号排列的书目文件和三张分别按书名、作者名和分类号顺序排列的索引表，如下所示： 什么是数据结构 001 002 003 004 高等数学 理论力学 高等数学 线形代数 樊映川 罗远祥 华罗庚 栾汝书 S01 L01 S01 S02 书目卡片 高等数学 理论力学 线形代数 001,003, … 002, … 004, … L S 002, 001, 003 特点：计算机按某个特定的要求进行查询.处理对象之间存在一种简单的线形关系,这类模型可以称为简单的线形数据结构. 按书名排列 樊映川 华罗庚 栾汝书 001, 003, 004, 按作者排列 按索引号排列 例2 计算机和人的对弈问题－－“树”形数据结构，1：N的关系 对奕的过程是在一定的规则下随机进行的,因此,计算机必须对对弈过程之中可能发生的情况以及相应的对策都考虑周全.这个关系不是线形的,从一个棋盘可以派生出几个格局,如下图: “树根”是对奕开始之前的棋盘格局,而所有的“叶子”是可能出现 的结局,对奕的过程就是从树根沿树叉到达某个叶子的过程. * * * * * * * * * * * * * * * * * * (a) 棋盘格式示例 (b)井字棋对弈树的局部 * 例3 多叉路口交通灯的管理问题－－“图”形数据结构，M：N的关系 可以把这类交通,道路的问题当作一种“图”的结构：一个顶点表示一条通道,而通道之间的矛盾的关系以两个顶点之间的连线表示.如下图所示: 结论：综合上面三个例子,描述这类非数值计算性问题的数学模型不再是数学方程,而是诸如表、树和图之类的数据结构. 数据结构: 数据结构是一门非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科. A E D C B (a) 五叉路