吉林大学数据结构课件 第一章 序论

数据结构主讲教师：贾海洋[e-mail]任课教师：贾海洋电子邮件：[e-mail]讲授课程：数据结构、算法分析、数据挖掘研究方向：知识工程、机器学习、数据挖掘、生物信息学教学计划第一章绪论第二章线性表、堆栈和队列第三章数组和字符串第六章递归第四章树第五章图第七章排序第八章查找答疑和上机时间答疑课后+邮件上机实验（平时成绩+上机考试）第7--14周（共八次，使用VC++环境）周二5-8节计算机楼实验室A209第一章绪论1.1为什么要学习数据结构1.2数据结构概念1.3算法1.4算法的正确性证明1.5算法分析基础为什么要学习数据结构在计算机科学中是一门综合性的专业基础课。不仅是一般程序设计的基础，而且是编译原理、操作系统、数据库系统及其他专业课的重要基础学习操作系统的基础（栈、队列、存储管理、文件等）学习编译原理的基础（表达式计算、散列表、语法树）为什么要学习数据结构在计算机科学中是一门综合性的专业基础课。不仅是一般程序设计的基础，而且是编译原理、操作系统、数据库系统及其他专业课的重要基础学习计算机网络的基础（Dijkstra算法）学习数据库系统的基础（线性表、多链表和索引树）为什么要学习数据结构在计算机科学中是一门综合性的专业基础课。不仅是一般程序设计的基础，而且是编译原理、操作系统、数据库系统及其他专业课的重要基础从事科学研究的基础（基础数据结构、经典算法、算法分析方法、算法正确性证明方法）为什么要学习数据结构在计算机科学中是一门综合性的专业基础课。不仅是一般程序设计的基础，而且是编译原理、操作系统、数据库系统及其他专业课的重要基础数据结构课程的目的：从对问题抽象和求解的角度来介绍常用的数据结构，阐明其内在逻辑关系，在计算机中的存储表示，以及刻画施加于其上之各种操作的算法第一章绪论1.1为什么要学习数据结构1.2数据结构概念1.3算法1.4算法的正确性证明1.5算法分析基础数据结构的发展历史20世纪40年代，电子计算机刚刚诞生处理纯数值性的信息，称为数值计算30吨！！170m2！!数据结构的发展历史20世纪40年代：处理纯数值性的信息20世纪50年代末计算机大量应用于解决非数值计算问题从简单的数值发展到复杂数据各种高级程序设计语言的出现（1951FORTRAN）产生了数组、记录、串和层次表结构等新的数据结构数据结构的发展历史20世纪40年代：处理纯数值性的信息20世纪50年代末：解决非数值计算问题20世纪60年代美国计算机界出现了“信息结构”的概念（据结构概念的前身）;1968年，“数据结构”列为一门独立的课程著名计算机科学家克努斯（D.E.Knuth）陆续出版了包括《基本算法》、《半数值算法》和《排序和查找》等三卷的旷世之作《计算机程序设计技巧》(TheArtofComputerProgramming)~uno/~uno/1974年，因其在算法分析和编程语言设计方面的突出贡献，荣获美国计算机协会图灵奖，是历史上最年轻的获奖者（36岁）。图灵奖被称为计算机界的诺贝尔奖。《计算机程序设计艺术》一书与牛顿的《自然哲学的数学原理》等书一起，被评为“世界历史上最伟大的十种科学著作”之一。他的所有著作都有个奇特“附加效应”，那就是任何人发现书中的错误，不论是技术上的或是排版上的还是历史上的错误，都可以向他指出，并可领取2.56美元！数据结构的发展历史•20世纪40年代：处理纯数值性的信息•20世纪50年代末：解决非数值计算问题•20世纪60年代：数据结构列为一门独立的课程•20世纪70年代后期：随着数据库技术的成功应用，数据结构相应地增加了文件组织、存储和管理等方面的内容。数据结构的发展历史1972年，著名计算机科学家霍尔（C.A.R.Hoare）在其论文“数据结构札记”中，澄清了关于数据结构术语和概念等方面的杂乱局面，并深刻论述了算法与数据结构密不可分的关系；1976年，著名计算机科学家沃思（N.Wirth）出版了名为《算法＋数据结构＝程序》的专著，不仅形象地描述了数据结构、算法与程序之间的关系，还旗帜鲜明的提出数据结构和算法对程序设计的重要性。数据结构的发展历史20世纪40年代：处理纯数值性的信息20世纪50年代末：解决非数值计算问题20世纪60年代：数据结构列为一门独立的课程20世纪70年代后期：随着数据库技术的成功应用，数据结构相应地增加了文件组织、存储和管理等方面的内容。20世纪80年代，随着面向对象概念和面向对象技术的兴起，数据结构增加了抽象数据类型等概念数据结构？？是什么？？数据结构01韩冬05杨帆03刘禹伯04孙晓东02冯明06迟克逊09张原沫07陆静雅08薛杨10张雷什么是数据？数据数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。在计算机科学中，数据的含义非常广泛，我们把一切能够输入到计算机中并被计算机程序处理的信息，包括文字、表格、图象等，都称为数据。数据例如一个简单的数值计算程序所使用的数据是一些实数或整数，一个编译程序使用和加工的数据是源程序，而一个能修改自身的计算机程序所使用和加工的数据（对象）就是其自身。数据是指对象的表示，即按照适合于通信、解释或处理（借助人或自动装置）的方式所形成的关于事实、概念或指令的表示；数据只是表示，而无含义[3]。【3】张效祥等.计算机科学技术百科全书.北京:清华大学出版社,2005.数据是计算机科学与技术中最基本的概念，它是计算机程序要处理的“原料”，是所有被计算机识别、存储和加工处理的符号的总称[4,5]。【4】管纪文,刘大有.数据结构.北京:高等教育出版社,1988.【5】刘大有,唐海鹰等.数据结构.北京:高等教育出版社,2001.数据元素(元素、结点、顶点、DataElement)数据元素是组成数据的基本单位。在程序中通常把结点作为一个整体进行考虑和处理。学号姓名53080101韩冬53080102冯明53080103刘禹伯53080104孙晓东53080105杨帆53080106迟克逊53080107陆静雅53080105杨帆每一行（代表一个同学）作为一个基本单位来考虑。数据项一般情况下，一个数据元素含有若干个数据项,数据项是构成数据的最小单位。每个数据元素都有学号、姓名这两个数据项构成。学号姓名数据结构什么是结构？HHNNNNNHHNNNNN分子结构什么是结构AGCTGACTGCATAGCTACGTTAGCDNA的结构：DNA双螺旋模型数据+结构01韩冬05杨帆03刘禹伯04孙晓东02冯明06迟克逊09张原沫07陆静雅08薛杨10张雷学号姓名53080101韩冬53080102冯明53080103刘禹伯53080104孙晓东53080105杨帆53080106迟克逊53080107陆静雅53080108薛杨53080109张原沫53080110张雷线性结构非线性结构数据的逻辑结构01韩冬02冯明03刘禹伯04孙晓东05杨帆长春市四平市吉林省辽宁省沈阳市大连市中国线性结构数据的存储结构/物理结构数组链表01韩冬02冯明03刘禹伯04孙晓东05杨帆01韩冬02冯明03刘禹伯04孙晓东05杨帆数据上的运算集合查找寻找1班学号为20的同学姓名查找所有1班姓王的同学排序将8班同学按照姓名拼音排序按照专业课总成绩排名定义1.2数据结构是指由若干数据成分按照一定方式构成的复合数据以及作用于其上的函数或运算。数据成分(元素)及其间的数据约束关系合称为数据结构的逻辑结构。数据结构从数学上可用适当的数学结构以及其上的函数变换统一地定义[3]。但迄今为止，关于数据结构之定义在计算机科学技术界还未取得完全认同。有些学者认为数据结构应由数据的逻辑结构、数据的存储结构及其运算（操作）三部分组成。数据结构的组成：数据的逻辑结构数据的存储结构数据上施加的操作逻辑结构数据元素之间的逻辑关系称为数据的逻辑结构。逻辑结构的形式化表示逻辑结构表示为二元组L=(N,R)，其中N(L)是结点的有限集合，R(L)是N上的关系集合。一般地，R={r}。逻辑结构例1L=(N,R)，N={a,b,c,d,e},R={r}，r={}aecdb逻辑结构例2L=(N,R)，N={a,b,c,d,e},R={r}，r={a,b,b,c,c,d,d,e}abcde例3L=(N,R)，N={k1，k2，…，k9}R={r}，r={k1,k2，k1,k3，k1,k4，k1,k7，k1,k8，k4,k5，k4,k6，k8,k9}k1k2k3k4k7k8k5k6k9例3L=(N,R)，N={k1，k2，…，k4}R={r}，r={(k1,k2),(k1,k3),(k3,k4),(k2,k3)}r={(k1,k2),(k2,k1),(k1,k3),(k3,k1),(k3,k4),(k4,k3),(k2,k3),(k3,k2)}k1k2k3k4逻辑结构集合线性树图逻辑结构的分类线性结构结构中有且仅有一个始结点和一个终结点，始结点只有一个后继结点，终结点只有一个前趋结点，每个内结点有且仅有一个前趋结点和一个后继结点。非线性结构（树、图）结构中的结点可能有多个前趋结点和多个后继结点。数据结构的组成：数据的逻辑结构数据的存储结构数据上施加的操作存储结构是指数据的逻辑结构在计算机中所需的存储空间、空间的构成结构及对该存储结构的访问方式等的总称数据的存储结构是建立一种由逻辑结构到存储结构的映射：建立结点集合N到存储区域M的映射：N-M，中每个结点j∈N都对应唯一的连续存储单元c∈M对于每一个关系元组a,b∈r，映射为存储单元的地址顺序关系（或指针的地址指向关系）存储结构是指数据的逻辑结构在计算机中所需的存储空间、空间的构成结构及对该存储结构的访问方式等的总称数据的存储结构是建立一种由逻辑结构到存储结构的映射：01韩冬02冯明03刘禹伯04孙晓东05杨帆01韩冬02冯明03刘禹伯04孙晓东05杨帆学号姓名53080101韩冬53080102冯明53080103刘禹伯53080104孙晓东53080105杨帆存储结构是指数据的逻辑结构在计算机中所需的存储空间、空间的构成结构及对该存储结构的访问方式等的总称数据的存储结构是建立一种由逻辑结构到存储结构的映射：顺序、链接、索引和散列四种方法1）顺序存储顺序存储将一组结点存放在地址相邻的存储单元内，结点间的逻辑关系由存储单元的自然顺序关系来表达，即用一块无空隙的存储区域存储结点数据。例如，用数组存储线性数据结构，数组的元素是数据结点，按照顺序存储方法存储，结点之间的线性关系用地址单元的顺序关系来自然表达。2)链接存储链接存储通过在结点的存储结构中附加指针字段来存储结点间的逻辑关系，任意的逻辑关系r都可以用指针地址来表达。其中，数据结点一般由两部分组成：数据字段和指针字段。数据字段存放结点本身的数据，指针字段存放指向后继结点的指针。链接存储灵活性很大，适用于那些需要经常动态变化（插入、删除等操作）的数据结构；通常借助高级语言中的指针类型来实现。3）索引存储索引存储可以看作顺序存储方法的一种推广，通过建造一个由整数域Z映射到存储地址域的函数，把整数索引值映射到结点的存储地址，从而形成一个存储一串指针的索引表，每个指针指向存储区域的一个数据结点。4）散列存储散列存储利用散列函数(hashfunctions)进行索引值的计算，然后通过索引表求出结点的指针地址，是索引方法的一种延伸和扩展。散列存储适用于高速检索的结构。散列存储的关键问题是如何恰当地选择散列函数，建造散列表，并解决在构建散列表时的“冲突”问题。我们将在第8章详细介绍散列存