资源描述：
《第1章_数据结构ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、计算机软件技术基础集美大学诚毅学院郭静课程介绍开课时间：第1周—第18周总学时：36学时成绩分配：平时成绩30%、期末成绩70%课程目的：学生学习计算机软件规范的组织方法、软件设计的常用方法，学习数据结构、计算机操作系统和数据库原理，提高学生计算机应用能力。重点章节：第一章——数据结构：包括表、栈、队列等基本的线性数据结构，树、图等非线性数据结构，以及递归、排序、查找等基本的程序操作。第三章——操作系统：包括操作系统的形成与发展，操作系统的作用与类型，处理器管理，存储管理，设备管理和文件管理等。第四章——软件工程：包括软件的生命周期，
2、软件开发的工程化方法，软件的测试策略与测试方法，以及软件质量的度量等。第五章——数据库技术：包括数据库管理技术的发展历程，常用数据库系统概述，关系数据库理论基础及关系数据库管理系统的设计等。第1章数据结构1.1绪论1.2线性数据结构及其应用1.3递归与非线性数据结构1.4内部排序1.5查找为什么要学习数据结构？程序=数据结构+算法数据结构并不是来教你怎样编程的，数据结构是教你如何在现有程序的基础上把它变得更优（运算更快，占用资源更少）数据结构并不是一门语言，它是一种思想，一种方法，一种思维方式，它并不受语言的限制。1.1绪论1.1.1
3、数据结构产生的背景1.1.2什么是数据结构1.1.3数据结构的重要性1.1.4基本概念和术语1.1.5算法和算法分析1.1.1数据结构产生的背景●计算机科学和软件工程的惊人发展使计算机的应用已渗透到各个领域，计算机的应用已不再局限于数值计算（科学计算）。●解决数值计算问题的许多理论、方法和技术一般不适应于解决诸如数据的分类与查找、情报检索、数据库、企业管理、系统工程、图形图像处理、人工智能以及日常生活等各领域的非数值处理问题。●计算机加工处理的对象由纯粹的数字发展到字符、表格和图像等各种具有一定结构的数据。●“数据结构”就是为研究和解
4、决这些非数值问题而提出的理论和方法，是解决这些问题的重要基础知识。1.1.2什么是数据结构●从提出一个实际问题到计算机解出答案需有经过下列步骤：首先从实际问题中抽取出数学模型然后设计相应的算法再编程序、调试、求解。建立数学模型是分析具体问题的过程，包括：分析具体问题中操作对象找出这些对象间的关系，并用数学语言描述数学模型分两类：1）数值计算类：例：根据三条边，求三角形面积。假定：三条边依次为a,b,c三个实型数，满足：a>0,b>0,c>0,a+b>c,b+c>a,c+a>b,则s=area=2）非数值计算类：例1:5个整数组成的集合
5、：D={20,-5，66,15,44}其中:20,-5,66等称为数据元素(元素)，元素与元素之间关系是它们同属于集合D。D={20,-5,66,15,44}是一个数据对象例2:一列整数：(线性结构)L=(20,-5，66,15,44）其中:元素与元素之间在L中是前后关系或线性关系。L=(20,-5,66,15,44)是一个线性表。例3：学生信息检索问题表1.1学生入学情况简表这是一张二维表，其中每行均是一名学生的有关情况。要查找某人的情况只能用顺序检索的方法，若按照几个关键字查找，就要建立相应的索引表。准考证号姓名性别年龄总分来自何
6、地200101李林男19530福建200123张丽女20510江西200140王晓女18550福建………………………………此例中若我们按照准考证号、姓名、性别、生源检索，就需建立4个索引表，这4张表就是学生信息检索的数学模型，计算机的主要操作便是按照某个特定要求来对学生进行查询。这类型的数学模型中，计算机处理的对象之间存在的是一种最简单的线性关系，这类数学模型结构可称为线性的数据结构。准考证号姓名性别来自何地……200101李林男福建……200123张丽女江西……200140王晓女福建………………………………姓名准考证号……李林200
7、101……张丽200123……王晓200140……………………性别准考证号……男200101……女200123、200140……………………来自何地准考证号……福建200101、200140……江西200123……………………例4：学校组织体系问题在这种情况下，各数据元素之间的逻辑关系就不是线性的，所以应采用树型结构分级管理，如图1.1所示。要查找某位教师，可顺着“系—教研室—个人”的路线往下查找，这类数学模型结构可称为树的数据结构。某学校一系101教研室…教师p教师1…教师q教师1106教研室…九系…901教研室…教师m教师1…教师
8、n教师909教研室…图1.1学校组织体系示意图例5：部分城市公路交通网问题因为任意两个城市之间都可能有公路相通，所以，这是一种比树形结构更为复杂的数据结构，称其为图结构。图1.2部分城市公路交通网例6：田径赛的时间安排问
