严蔚敏版数据结构课件 绪论

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

1、井冈山大学电子与信息工程学院计算机科学系孙凌宇sunlingyu@jgsu.edu.cn•先修课程：C程序设计•《数据结构》是“信息管理与信息系统”专业及“计算机应用技术”等相关专业的专业基础课。本课程主要培养学生分析数据、组织数据的能力，介绍数据的逻辑结构、存储结构及有关算法。使学生能够根据数据处理问题的需要，为待处理的数据选择合适的逻辑结构和存储结构，编写出效率较高、质量较好的程序。•《数据结构》作为一门独立的课程最早开设于美国的一些大学，1968年美国Donald.E.Knuth教授（1974TuringAward）开创了数据结构的

2、最初体系，他所著的《TheArtofComputerProgramming》第一卷《FundamentalAlgorithms》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。68/69/73/08•从60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们就越来越重视数据结构，认为程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法。从70年代中期到80年代初，各种版本的数据结构著作就相继出现。•EdsgerDijkstra——结构化编程荷兰/1930/“goto有

3、害论”/最短路径算法/1972TuringAward•DavidParnas——模块化设计、信息隐藏•NiklausWirth——数据结构、逐步求精瑞士/1934/Pascal之父/1984TuringAwardAlgorithm+DataStructure=ProgramsProgramDevelopmentbyStepwiseRefinement•目前在我国，《数据结构》也已经不仅仅是计算机专业的教学计划中的核心课程之一，而且是其它非计算机专业的主要选修课程之一。课程教学要求•课时安排：17周（3+1），共68学时。–理论——48学时

4、–课程上机——16学时–期末复习及习题课——4学时•数据结构是计算机专业基础课，内容多且抽象，学习有难度。课外学习很关键。•具体教学进度及内容安排。课程教学要求•多做习题，以加深对概念的理解，提高程序设计能力。•机器是比任何教师都严厉的检查者。实验对课程学习很重要，要求上机前做好充分准备。除课程安排的机时外，根据自身情况多上机。用C语言描述时，其数据元素的类型定义和组织，主要通过结构体来完成。使数据元素的操作与数据元素的定义相对独立，可用C语言中的自定义函数来完成。采用VisualC++6即可。•预习→听课→复习→作业→实验第第11章章绪

5、绪论论本章要点：一、介绍数据结构二、数据结构的基本概念及相关术语三、数据类型和抽象数据类型之间的联系四、算法的特点及算法的时间与空间复杂性第第11章章绪绪论论逻辑结构数据结构存储结构相关操作的实现1.1什么是数据结构数据结构是计算机科学中广泛使用的一个术语，在计算机科学中具有非常重要的作用。计算机科学是一门研究用计算机进行信息表示和处理的科学。程序用于实现信息表示形式之间的变换：信息表示A计算机程序信息表示B信息的表示和处理又直接关系到处理信息的程序的效率。信息并不是没有组织，信息（数据）之间往往具有重要的结构关系。因此，为了编写出一个“

6、好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。•程序：为计算机处理问题编制的指令集合。•算法：处理问题的策略。（怎么处理）•数据结构：问题的数学模型。（对处理的信息怎么表示）例：设有一个电话号码薄，它记录了N个人的名字和其对应的电话号码。要求设计一个电话号码查询系统：当给定任何一个人的名字时，该算法能够能够输出此人的电话号码。如无此人，则报告无此人的信息。分析：算法的设计，依赖于计算机如何存储人名和对应的电话号码，或者说依赖于名字和其电话号码的结构。可将名字和对应的电话号码设计成：二维数

7、组、结构数组。1。数据元素的存储形式（数组、链表文件等）2。查找的方法：顺序、二分法、分块索引。3。效率：当N=100，1000，10000时4。若N=10万、N=100万……随着计算机软、硬件的发展，计算机的应用范围在不断扩大，计算机所处理的数据的数量也在不断扩大，计算机所处理的数据已不再是单纯的数值数据，而更多的是非数值数据。需要处理的数据并不是杂乱无章的，它们一定有内在的联系，只有弄清楚它们之间的本质的联系，才能使用计算机对大量的数据进行有效的处理。数值计算的程序设计问题结构应力分析计算——线性方程组全球天气预报——环流模式方程非数

8、值计算的程序设计问题例：计算机对弈算法：对弈的规则和策略模型：？（棋盘、棋子如何表示）–例1书目自动检索系统线性表数学模型书目文件001高等数学书目卡片樊映川S01002理论力学罗远祥L01登