数据结构课件吴伟民编著

《数据结构课件吴伟民编著》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构主讲教师邢振祥1总学时：60讲课学时：50实验学时：10教材：《数据结构C语言版》严蔚敏、吴伟民-----清华大学出版社《数据结构C语言篇》习题与解析李春葆-----清华大学出版社课程安排课程要求课前请做好预习保持课堂安静，头脑清醒，思维活跃认真、独立、按时完成并提交作业重视上机实践，有效利用宝贵的上机时间上机安排上机地点：机房上机时间：上机内容：要求:所有作业必须独立完成算法作业必须经上机调试通过上机考勤3次缺席，按不及格处理发现上机时间上网，按缺席一次处理课程重要性核心基础课程编程基础考研课程计算机等级考试课

2、程程序员考试课程请同学们把本课程的学习重视起来！！！1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示和实现1.4算法和算法分析第一章绪论教学目的：（1）了解数据结构及算法的概念；（2）掌握计算语句频度和估算算法时间复杂度的方法。教学的重点和难点：估算算法时间复杂度。第一章绪论1.1什么是数据结构什么是程序、软件？N.沃思（NiklausWirth)教授提出：程序=算法+数据结构程序设计:为计算机处理问题编制一组指令集算法:处理问题的策略数据结构:问题的数学模型软件=程序+文档（软件工程的观点）电子计算机的

3、主要用途：早期：主要用于数值计算。后来：处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。数值计算解决问题的一般步骤：数学模型→选择计算机语言→编出程序→测试→最终解答。数值计算的关键是：如何得出数学模型（方程）？程序设计人员比较关注程序设计的技巧。非数值计算问题：数据元素之间的相互关系一般无法用数学方程加以描述例1学籍管理问题——表结构学号姓名性别出生日期政治面貌0001王军男1983/09/02团员0002李明男1982/12/25党员0003汤晓影女1984/03/26团员……………完成什

4、么功能?各表项之间是什么关系？例2人机对弈问题——树结构如何实现对弈?各格局之间是什么关系？…………..……..………...……例3教学计划编排问题——图结构C4,C5,C6数据库原理C7C2,C4计算机原理C6C3,C4数据结构C5C1,C2程序设计C4C1离散数学C3无计算机导论C2无高等数学C1先修课课程名称编号C1C2C3C4C6C5C7如何表示课程之间的先修关系？求解非数值计算的问题：主要考虑的是设计出合适的数据结构及相应的算法。即：首先要考虑对相关的各种信息如何表示、组织和存储？因此，可以认为：数据结构是一门

5、讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。数据结构课程的形成和发展：形成阶段：60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。发展阶段：数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。70年代后期，我国高校陆续开设该课程。《数据结构课程》所处的地位：1.2基本概念和术语数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机

6、中并被计算机程序处理的符号的总称。数据元素(DataElement):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。三者之间的关系：数据>数据元素>数据项例：班级通讯录>个人记录>姓名、年龄……数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。序偶：由两个具有给定次序的元素x和y所组成的序列,记为。关系：是指集合中元素之间的相互联系。是集合中某些元素所构成的序偶的集合。例如D={A，B，C，D，E

7、}R={,,}和R={,,}都是D上的一种关系。数据结构：带结构的数据元素的集合假设用三个4位的十进制数表示一个含12位数的十进制数。3214,6587,9345─a1(3214),a2(6587),a3(9345)则在数据元素a1、a2和a3之间存在着“次序”关系a1,a2、a2,a33214，6587，9345a1a2a36587，3214，9345a2a1a3≠例如:又例，在2行3列的二维数组{a1,a2,a3,a4,a5,a6}中六个元素之间存在

8、两个关系:行的次序关系:列的次序关系:row={,,,}col={,,}a1a3a5a2a4a6a1a2a3a4a5a6数据结构：带结构的数据元素的集合再例，在一维数组{a1,a2,a3,a4,a5,a6}的数据元素之间