数据结构(第1章)讲义

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

1、授课教师：张小莉联系电话：5079389办公室：主楼1208Email:xlzhang@hbu.edu.cn数据结构数据是计算机可以直接处理的基本和最重要的对象。计算机科学是一门研究数据表示和数据处理的科学。计算机进行科学计算、过程控制、对文件的存储和检索及数据库技术等计算机应用，都是对数据进行加工处理的过程。------这个过程是按照程序进行的。要设计出一个结构好而且效率高的程序，必须研究数据的特性、数据间的相互关系及其对应的存储表示方法，并利用这些特性和关系设计出相应的算法和程序。《数据结构》课程就是围绕这些问题带你走进数据表示和数据处理的大门。---------研究数据表示和数据处

2、理2数据结构作为一门独立的课程在国外是从1968年才开始的，但在此之前其有关内容已散见于编译原理及操作系统之中。从20世纪60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们越来越重视数据结构。从70年代中期到80年代，各种版本的数据结构著作相继出现。目前，数据结构的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型和面向对象的观点来讨论数据结构已成为一种新的趋势，越来越被人们所重视。3本课程的任务是：在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技

3、能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。学业基础：本课程的先修课程为高级语言程序设计。学习本课程必须具备高级语言程序设计(如C或C++，等等)的基础知识与基本技能。它的后续课程有操作系统和数据库原理、算法分析与设计等。学时安排：总学时100。其中课堂讲授68学时,实验教学32学时。45理论学习（4学分）：平时成绩（30%）：出勤、课上提问、课后作业、小测、论坛参与等等；考试成绩（70%）：期末考试卷面分数。实验（1学分）：实验课：每个实验按照要求进行，并提交实验报告。6⒈教学内容：1.1数据结构的概念；1.2抽象数据类型；1.3算法和算法

4、分析。⒉教学目的：⑴领会数据、数据元素和数据项的概念及其相互间的关系；⑵清楚数据结构的逻辑结构、存储结构的联系与区别；⑶理解抽象数据类型的概念；⑷掌握进行简单算法分析的方法。第1章绪论7⒊教学重点：⑴数据、数据项、数据元素、数据结构的概念；⑵逻辑结构和数据结构在概念上的联系与区别；⑶抽象数据类型和数据抽象；⑷评价算法优劣的标准及方法。⒋教学难点：⑴区别算法与程序；⑵逻辑结构、存储结构的联系与区别；⑶抽象数据类型与数据抽象；⑷算法的时间复杂度分析。⒌学时安排：2学时81.1数据结构的概念为什么要学习数据结构有关概念和术语数据结构课程的内容91.1.1为什么要学习数据结构现实中有计算机处理的

5、两大类问题：数值问题和非数值问题计算机使用初期：主要是处理数值计算问题（归结为解方程、求值）。涉及的运算对象是简单，不重视数据结构。发展之后：非数值计算问题越来越显得重要。据统计，当今处理非数值计算性问题占用了90%以上的机器时间。数据结构更为复杂；数据元素之间的相互关系无法用数学方程式加以描述；要分析所处理的数据必要分析数据间的关系。10例1学生信息检索系统该系统的主要操作之一便是按照某个特定要求（如给定姓名）对学生信息文件进行查询。当我们需要查找某个学生或查询某个专业或年级的学生的有关情况的时候，只要我们建立了相关的数据库，按照某种算法编写了相关程序，就可以实现计算机自动检索。根据需

6、求分析，可以建立以下四张表：1112例1学生信息检索系统学号顺序排列的学生信息表姓名顺序排列的索引表专业顺序排列的索引表年级顺序排列的索引表学生信息检索系统的数学模型相对每一张表，表中的每一行的信息，我们可以成为一个数据元素，每张表中的数据元素之间是一个序列的关系，我们称之为线性关系。13例2八皇后问题该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。为了描述方便，将八皇后问题简化为四皇后问题:14在八皇后问题中，处理过程不是根据某种确定的计算法则，而是利用试探和回溯的

7、探索技术求解。为了求得合理布局，在计算机中要存储布局的当前状态。从最初的布局状态开始，一步步地进行试探，每试探一步形成一个新的状态，整个试探过程形成了一棵隐含的状态树。每一个状态，也是一个数据，而所有的数据之间是一种树型关系。15例3教学计划编排问题一个教学计划包含许多课程。课程之间，有些必须按规定的先后次序进行，有些则没有次序要求。即课程之间有先修和后修的关系，有些课程可以任意安排次序。某个专业的教学计划的各个课程之间的次序关系可