数据结构—chapter 1- 绪论

《数据结构—chapter 1- 绪论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、教材及参考书目教材：《数据结构——使用C语言（第3版）》，朱战立编著，西安交通大学出版社《数据结构实习指导书》中国地质大学（武汉）计算机科学与技术系《C语言程序设计（第二版）》，谭浩强，清华大学出版社主要参考书目：《数据结构》（C语言版），严蔚敏等编著，清华大学出版社；《计算机程序设计技巧》，D.E.克努特[美]著，管纪立等译，第一卷基本算法，第三卷排序与查找；《数据结构题集》（C语言版），严蔚敏、吴伟民编著，清华大学出版社；《数据结构习题与解析》（C语言篇），李春葆编著，清华大学出版社学习数据结构的意义数据结构是为研究和解决如何有效地组织和处理非数值数据而产生的理论、技术和

2、方法。数据结构是软件设计技术的理论基础，是计算机学科的核心专业基础课程，也是所有应用计算机的其他学科所必须掌握的课程。学习这门课程的目的训练复杂程序设计技能，提高编程能力：掌握常用的基本数据结构；培养分析问题的能力：培养数据抽象能力，学会分析研究具体问题中的数据特性；培养解决问题的能力：能够根据实际问题的需要选择合适的数据结构和算法初步掌握算法效率的度量——时间复杂度分析技巧教学内容研究八大基本数据结构——线性表、栈、队列、（串）、数组、树、二叉树、图逻辑特性在计算机中的存储方式操作集和在不同存储方式下操作的算法实现(重点、难点)各种算法的性能分析各种数据结构的应用(重点、难

3、点)研究两大基本操作——查找和排序各种实现算法及其效率分析学习的主线数据结构课程的特点及学习方法特点1：内容广，概念多学习方法1：注重各章节间的联系与衔接，抓住主线，融会贯通特点2：实践性强、动手编程难学习方法2：数据结构是一门实践性很强的课程，上机实习是其中很重要的一个环节。因此，学习一个阶段后要及时上机实习。要求：(1)认真地完成课后习题以及上机实习(2)编写的程序正确、结构清楚、易读，符合软件工程的规范(P25)。第一次课阅读：朱战立，第1-13、14-18、18-25页谭浩强练习：作业1Chapter1绪论1.1-2基本术语-数据结构-抽象数据类型1.3算法与算法分

4、析-算法-时间复杂度1.1基本术语●数据（Data）凡是能输入到计算机，由计算机进行加工处理的数字、字母、文字和其它符号均叫做数据。含义极为广泛，如图形、声音等都属数据的范畴。●数据元素（DataElement）数据的基本单位，即数据集合中的一个个体。有时，一个数据元素可由若干数据项组成，数据项是具有独立含义的最小单位。例、图书自动检索系统的数据登录号书名作者名出版单位分类号出版时间001002003高等数学理论力学数据结构樊映川严蔚敏罗远详S01L01J01高等教育出版社┇┇┇┇┇┇┅┅┅┅┅●数据结构（DataStructure）◆元素之间的关系称为结构。数据结构，简单地

5、说，就是数据元素的集合加上数据元素之间的相互关系的集合，可形式化地描述成一个二元组：DataStructure=(D,S)其中，D：数据元素的集合，S：D上关系的集合。◆1968年唐•欧•克努特[美]：数据结构=数据的逻辑结构+数据的存储结构+数据的运算◆数据的逻辑结构数据元素之间抽象化的相互关系。二元组形式化定义中的S即指的逻辑结构。三类基本结构：线性结构树形结构图形结构也可简单分为：线性结构：线性表、栈、队列、串、数组非线性结构：树、二叉树、图例1、图书自动检索系统（建立、查找、插入/删除）登录号书名作者名出版单位分类号出版时间001002003高等数学理论力学数据结

6、构樊映川严蔚敏罗远详S01L01J01高等教育出版社┇┇┇┇┇┇┅┅┅┅┅例2、一个大学的人事档案处理系统学校一院(系)二院(系)…n院(系)一专业二专业…m专业教师学生档案档案…档案例3、交通管理信息系统◆数据的物理结构（存储结构）逻辑结构到计算机存储器的映象。映象方法：顺序分配链式分配n–1i120┇┇元素序号┇┇an–1a2a1a0内存ai∧a1a2an…ai…h◆数据的运算（操作）逻辑操作和具体操作：逻辑结构逻辑操作存储结构具体操作常用的逻辑操作有：（1）建立一个数据结构（2）销毁一个数据结构（3）插入一个新元素到一个指定的数据结构（4）删除一个元素（5）修改一个元素

7、（或其中的数据项）的内容（6）排序（7）查找抽象只知道"做什么"，而无须考虑"如何做"具体概念小结数据结构研究数据元素间在客观世界的相互联系、在计算机内的存储方法以及如何能在各种结构上实施有效的操作算法。一个具体问题的软件设计通常包含三个步骤：（1）分析和确定问题的逻辑结构和逻辑操作；（2）设计该问题的具体存储结构；（3）设计该问题在具体存储结构下的操作实现算法。●数据类型（DataType）数据类型是一组值的集合以及定义在这个值集上的一组操作的总称。通常可看作是高级程序设计语言中已实现的数据结构。