数据结构ppt(第1章)

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

1、授课教师：石强Email:shiqiang@hbu.cn数据结构数据结构是计算机及相关专业中一门重要的专业基础课程。当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下了厚实的知识基础，同时也提供了必要的技能训练。因此，数据结构课程在计算机应用专业中具有举足轻重的作用。本课程的任务是：在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。9/16/20212

2、数据结构讲义学业基础：本课程的先修课程为离散数学和高级语言程序设计。学习本课程必须具备高级语言程序设计(比如Pascal语言或C语言)的基础知识与基本技能。它的后续课程有操作系统和数据库原理等。进度安排：总学时68，其中课堂讲授72学时，实验教学34学时。9/16/20213数据结构讲义⒈教学内容：1.1数据结构的概念；1.2抽象数据类型；1.3算法和算法分析。⒉教学目的：⑴领会数据、数据元素和数据项的概念及其相互间的关系；⑵清楚数据结构的逻辑结构、存储结构的联系与区别，以及在数据结构上施加的运算及其实现；⑶理解抽象数据类型的概念；⑷掌握进行简单算法分析的方法。第一章绪论9/16/

3、20214数据结构讲义⒊教学重点：⑴数据、数据元素、数据项；⑵逻辑结构和数据结构在概念上的联系与区别；⑶存储结构及其三个组成部分；⑷抽象数据类型和数据抽象；⑸评价算法优劣的标准及方法。⒋教学难点：⑴区别算法与程序；⑵逻辑结构、存储结构的联系与区别；⑶抽象数据类型与数据抽象；⑷算法的时间复杂度分析。⒌学时安排：3学时9/16/20215数据结构讲义1.1数据结构的概念为什么要学习数据结构有关概念和术语数据结构课程的内容9/16/20216数据结构讲义1.1.1为什么要学习数据结构由于早期程序设计所涉及的运算对象是简单的整型、实型或布尔类型数据，所以程序设计者的主要精力是集中于程序设计

4、的技巧上，而无须重视数据结构。随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题越来越显得重要。据统计，当今处理非数值计算性问题占用了90%以上的机器时间。这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。因此，解决这类问题的关键不再是数学分析和计算方法，而是要设计出合适的数据结构，才能有效地解决问题。9/16/20217数据结构讲义例1学生信息检索系统当我们需要查找某个学生的有关情况的时候；或者想查询某个专业或年级的学生的有关情况的时候，只要我们建立了相关的数据结构，按照某种算法编写了相关程序，就可以实现计算机自动检索。由此，可以在学生信

5、息检索系统中建立一张按学号顺序排列的学生信息表和分别按姓名、专业、年级顺序排列的索引表，由这四张表构成的文件便是学生信息检索的数学模型，计算机的主要操作便是按照某个特定要求（如给定姓名）对学生信息文件进行查询。（b）姓名索引表崔文靖8何文颖6李淑芳2刘丽3，9石宝国5魏永鸣10吴承志1赵胜利7张会有42000级6，7，82001级9，1098级1，2，399级4，5计算机科学与技术1，5，6，9信息与计算科学2，4，8数学与应用数学3，7，10记录号学号姓名性别专业年级1980001吴承志男计算机科学与技术98级2980002李淑芳女信息与计算科学98级3990301刘丽女数学与应

6、用数学99级4990302张会友男信息与计算科学99级5990303石宝国男计算机科学与技术99级6000801何文颖女计算机科学与技术2000级7000802赵胜利男数学与应用数学2000级8000803崔文靖男信息与计算科学2000级9010601刘丽女计算机科学与技术2001级10010602魏永鸣男数学与应用数学2001级（a）学生信息表（c）专业索引表（d）年级索引表图1.1学生信息查询系统中的数据结构9/16/20218数据结构讲义在八皇后问题中，处理过程不是根据某种确定的计算法则，而是利用试探和回溯的探索技术求解。为了求得合理布局，在计算机中要存储布局的当前状态。从最

7、初的布局状态开始，一步步地进行试探，每试探一步形成一个新的状态，整个试探过程形成了一棵隐含的状态树。如图1.2所示（为了描述方便，将八皇后问题简化为四皇后问题）。回溯法求解过程实质上就是一个遍历状态树的过程。在这个问题中所出现的树也是一种数据结构，它可以应用在许多非数值计算的问题中。例2八皇后问题9/16/20219数据结构讲义例3教学计划编排问题一个教学计划包含许多课程，在教学计划包含的许多课程之间，有些必须按规定的先后次序进行，有些则没有次序要求。即有些课程之间有