哈工大数据结构课件第一章

第1章绪论数据结构与算法数据结构与算法数据结构与算法数据结构与算法DataStructruesandAlgorithmsg张岩张岩海量数据计算研究中心哈工大计算机科学与技术学院张岩Slide1-12013/9/152013/9/15哈工大计算机科学与技术学院第1章绪论课程说明课程说明课程说明课程说明课程编号：13SC03100100授课学时：48（3至15周，4学时/周）授课学时：48（3至15周，4学时/周）实验学时：12（第8\10\12\14周，3学时/周）课程分类：专业（技术）基础课程分类专技术答疑地点：综合楼804，每周1次课程资源：考核形式：考核形式期末笔试70%+平时成绩10%+实验成绩20%主讲教师：张岩主讲教师：张岩联系方式：电话[phone]email:zhangy@hiteducn哈工大计算机科学与技术学院张岩Slide1-22013/9/15email:[e-mail]第1章绪论课程目标课程目标课程目标课程目标象精通小学乘法口诀一样，彻底精通数据结构彻底精通数据结构不能只停留在逻辑层面上让数据结构不再是你程序设计的障碍！不再是你程序设计的障碍不再是你学习其他课程的障碍!考不再是你考研的障碍!不再是你找工作的障碍!不再是你找工作的障碍!在编程中升华你的计算思维，爱上计算机专业！哈工大计算机科学与技术学院张岩Slide1-32013/9/15第第11章章绪论绪论第第11章章绪论绪论2013/9/15Slide1-4第1章绪论学习目标学习目标了解数据结构的基本概念、研究对象以及数据结构课程的发展历史对数据结构与算法课程有一个宏观的认识展历史，对数据结构与算法课程有个宏观的认识掌握贯穿全书的重要概念-----抽象数据型，包括其概念的定义和实现方法初步掌握抽象技术方法义和实现方法，初步掌握抽象技术方法了解算法、算法复杂性，掌握算法性能的评价方法了解解决问题的一般过程和算法的逐步求精方法，掌握问题求解的基本过程和方法哈工大计算机科学与技术学院张岩Slide1-52013/9/15第1章绪论本章主要内容本章主要内容本章主要内容本章主要内容数据结构的兴起和发展基本概念与研究对象抽象数据类型算法及算法分析逐步求精的程序设计方法逐步求精的程序设计方法本章小结哈工大计算机科学与技术学院张岩Slide1-62013/9/15第1章绪论数据结构的创始人—Donald.E.Knuth数据结构的创始人Donald.E.Knuth1938年出生，25岁毕业于加州理工学院数学系博士毕业后留校任教28岁任数学系，博士毕业后留校任教，28岁任副教授。30岁时，加盟斯坦福大学计算机系，任教授。从31岁起，开始出版他的历史性经典巨著的历史性经典巨著：TheArtofComputerProgrammingpgg他计划共写7卷，然而出版三卷之后，已震惊世界，使他获得计算机科学界的昀高荣誉图灵奖，此时，他年仅36岁。哈工大计算机科学与技术学院张岩Slide1-72013/9/15昀高荣誉图灵奖，此时，他年仅36岁。第1章绪论1111数据结构的兴起和发展1.11.1数据结构的兴起和发展客观世界与计算机世界的关系计算机科学是研究信息表示和信息处理的科学。信息在计算机内是用数据表示的。信息在计算机内是用数据表示的。用计算机解决实际问题的实质可以用下图表示：客观世界（客观问题）概念世界机器世界（存储表示）映象映象抽象抽象映象抽象（客观问题）(逻辑模型)（存储表示）实现映象抽象抽象抽象映象模拟客观世界与计算机的关系哈工大计算机科学与技术学院张岩Slide1-82013/9/15客观世界与计算机的关系第1章绪论1111数据结构的兴起和发展((Cont)Cont)1.11.1数据结构的兴起和发展((Cont.)Cont.)程序设计的实质是什么?数据表示：将数据存储在计算机中数据处理：处理数据，求解问题数据结构问题起源于程序设计数据结构随着程序设计的发展而发展1.无结构阶段：在简单数据上作复杂运算1.无结构阶段：在简单数据上作复杂运算2.结构化阶段：数据结构＋算法＝程序3面向对象阶段：（对象＋行为）＝程序3.面向对象阶段：（对象＋行为）＝程序数据结构的发展并未终结哈工大计算机科学与技术学院张岩Slide1-92013/9/15数据结构的发展并未终结…….第1章绪论1212研究对象与基本概念研究对象与基本概念1.21.2研究对象与基本概念研究对象与基本概念例1学籍管理问题——表结构完成什么功能?各表项之间是什么关系？学号姓名性别出生日期政治面貌0001王晓东男1990/09/02团员李明远男党员0002李明远男1989/12/25党员0003张蔷薇女1991/03/26团员0003张蔷薇女1991/03/26团员……………哈工大计算机科学与技术学院张岩Slide1-102013/9/15第1章绪论1212研究对象与基本概念研究对象与基本概念((Cont)Cont)1.21.2研究对象与基本概念研究对象与基本概念((Cont.)Cont.)例2人机对弈问题——树结构如何实现对弈?各格局之间是什么关系？……..……..哈工大计算机科学与技术学院张岩Slide1-112013/9/15……………...……第1章绪论1212研究对象与基本概念研究对象与基本概念((Cont)Cont)1.21.2研究对象与基本概念研究对象与基本概念((Cont.)Cont.)例3教学计划编排问题——图结构如何表示课程之间的先修关系？无高等数学C1先修课课程名称编号C3C5C1离散数学C3无计算机导论C2C1C3C4数据结构CC1,C2程序设计C4C2C4C7数据库原理C2,C4计算机原理C6C3,C4数据结构C5C6哈工大计算机科学与技术学院张岩Slide1-122013/9/15C4,C5,C6数据库原理C76第1章绪论1212研究对象与基本概念研究对象与基本概念((Cont)Cont)1.21.2研究对象与基本概念研究对象与基本概念((Cont.)Cont.)计算机求解问题问题→抽象出问题的模型→求模型的解问题——数值问题、非数值问题问题数值问题非数值问题数值问题→数学方程非数值问题→数据结构非数值问题→数据结构数据结构与算法课程的研究对象是研究非数值计算问题中计算机的操作对象以及它们之间的关系和操作的学科。哈工大计算机科学与技术学院张岩Slide1-132013/9/15第1章绪论1212研究对象与基本概念研究对象与基本概念((Cont)Cont)1.21.2研究对象与基本概念研究对象与基本概念((Cont.)Cont.)数据结构的基本概念数据：一切能输入到计算机中并能被计算机程序识别和数据：一切能输入到计算机中并能被计算机程序识别和处理的符号集合。数值数据：整数、实数等数值数据：整数、实数等非数值数据：图形、图象、声音、文字等数据元素：数据的基本单位在计算机程序中通常作为数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据项：构成数据元素的不可分割的昀小单位。数据项：构成数据元素的不可分割的昀小单位。数据对象：具有相同性质的数据元素的集合。结点：数据元素在计算机内的位串表示结点：数据元素在计算机内的位串表示。域（字段）：数据元素中数据项在计算机内的表示信息表是数据对象在计算机内的表示哈工大计算机科学与技术学院张岩Slide1-142013/9/15信息表：是数据对象在计算机内的表示。第1章绪论1212研究对象与基本概念研究对象与基本概念((Cont)Cont)1.21.2研究对象与基本概念研究对象与基本概念((Cont.)Cont.)数据结构数据元素之间的相互关系，这种关系是抽象的，即并不涉及数据元素的具体内容。是数据元素及其相互间的关系的数学描述数学描述。相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。数据的逻辑结构数据元素之间的抽象关系，数据元素之间逻辑关系的整体学籍管理问题中，表项之间的逻辑关系指的是什么？学籍管理问题中，表项之间的逻辑关系指的是什么人机对弈问题中，格局之间的逻辑关系指的是什么？教学计划编排问题中，课程之间的逻辑关系指的是什么?哈工大计算机科学与技术学院张岩Slide1-152013/9/15数据的逻辑结构是从具体问题抽象出来的数据模型。第1章绪论1212研究对象与基本概念研究对象与基本概念((Cont)Cont)1.21.2研究对象与基本概念研究对象与基本概念((Cont.)Cont.)数据的存储结构又称物理结构，是数据及其逻辑结构在计算机中的表示。实质上是内存分配，以确定元素及元素之间关系的表示。在具体实现时，依赖于计算机语言。哈工大计算机科学与技术学院张岩Slide1-162013/9/15第1章绪论1212研究对象与基本概念研究对象与基本概念((Cont)Cont)1.21.2研究对象与基本概念研究对象与基本概念((Cont.)Cont.)数据结构从逻辑上分为四类：即四种基本的逻辑结构集合：数据元素之间就是“属于同一个集合”；数据线性结构：数据元素之间存在着一对一的线性关系；哈工大计算机科学与技术学院张岩Slide1-172013/9/15第1章绪论1212研究对象与基本概念研究对象与基本概念((Cont)Cont)1.21.2研究对象与基本概念研究对象与基本概念((Cont.)Cont.)数据结构从逻辑上分为四类：即四种基本的逻辑结构集合：数据元素之间就是“属于同一个集合”；数据线性结构：数据元素之间存在着一对一的线性关系；树型结构：数据元素之间存在着一对多的层次关系；图结构：数据元素之间存在着多对多的任意关系。哈工大计算机科学与技术学院张岩Slide1-182013/9/15第1章绪论1212研究对象与基本概念研究对象与基本概念((Cont)Cont)1.21.2研究对象与基本概念研究对象与基本概念((Cont.)Cont.)两种基本的存储结构例：（bat,cat,eat）顺序存储结构用一组连续的存储单元依次…起始地址,,存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示bat位置来表示。cateateat…哈工大计算机科学与技术学院张岩Slide1-192013/9/15第1章绪论1212研究对象与基本概念研究对象与基本概念((Cont)Cont)1.21.2研究对象与基本概念研究对象与基本概念((Cont.)Cont.)两种基本的存储结构例：（bat,cat,eat）例：（bat,cat,eat）顺序存储结构用一组连续的存储单元依次0200…cat0200…存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示0208bat020003250208位置来表示。链接存储结构0300…02000300…用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示03000300逻辑关系用指针来表示。0325…eat∧0325…哈工大计算机科学与技术学院张岩Slide1-202013/9/15…∧…第1章绪论1212研究对象与基本概念研究对象与基本概念((Cont)Cont)1.21.2研究对象与基本概念研究对象与基本概念((Cont.)Cont.)逻辑结构与存储结构的关系数据的逻辑结构属于用户视图是面向问题的反映了数据数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是面向计算机的。面向计算机的。一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。同的存储结构，其数据处理的效率往往是不同的。数据结构与算法的学习内容数据对象的结构形式各种数据结构的性质(逻辑结构)数据对象的结构形式,各种数据结构的性质(逻辑结构);数据对象和“关系”在计算机中的表示(物理结构/存储结构);数据结构上定义的基本操作(算法)及其实现;算法的效率（时间和空间）;哈工大计算机科学与技术学院张岩Slide1-212013/