《内蒙古大学《算法与数据结构》课件第1章概述》由会员分享，可在线阅读，更多相关《内蒙古大学《算法与数据结构》课件第1章概述（76页珍藏版）》请在金锄头文库上搜索。
1、计算机专业本科主干基础课计算机专业本科主干基础课 第第1章章 概述概述1.1 数据结构的发展数据结构的发展1.2 数据结构数据结构1.3 数据的逻辑结构数据的逻辑结构1.4 抽象数据类型（抽象数据类型（ADT）1.5 数据的存储结构数据的存储结构1.6 算法与算法分析算法与算法分析1.7 ADT的表示与实现间的关系的表示与实现间的关系 早期：早期：1946年，年， 数值计算数值计算 如：弹道计算如：弹道计算 矩阵运算矩阵运算 M1 * M2 * M3*Mn 函数计算函数计算 y=f(x) 方程组求解方程组求解 定积分定积分 dxxx1522)53(早期数据的特点早期数据的特点: : 数据量少，
2、计算比较复杂，当时人们只注重求解数据量少，计算比较复杂，当时人们只注重求解方法，并不注重数据的组织方法，并不注重数据的组织 。 在这一阶段，在这一阶段，数据结构数据结构还未形成一门系统的还未形成一门系统的学科，而是零星地分布在程序设计、图论、集合、代学科，而是零星地分布在程序设计、图论、集合、代数、操作系统和编译原理等课程中。数、操作系统和编译原理等课程中。中期：中期：7070s-80s-80s s 非数值计算猛增非数值计算猛增 70s80s90s1.1非数值数据的特点：非数值数据的特点：w 数据量大，计算比较简单。数据量大，计算比较简单。w 人们不得不把注意力集中于分析数据间的关系、人们不得
3、不把注意力集中于分析数据间的关系、数据的组织形式和数据的表示方法。数据的组织形式和数据的表示方法。 7070年代中期数据结构形成了一门课程。年代中期数据结构形成了一门课程。目前：目前：计算机应用领域不断扩大，信息量越来计算机应用领域不断扩大，信息量越来越大，问题越来越复杂。越大，问题越来越复杂。w 它们的特点是数据量异常庞大它们的特点是数据量异常庞大; ;w 关系十分复杂关系十分复杂; ;w 因此不仅要注重因此不仅要注重求解方法求解方法, ,而且要注重而且要注重数据数据 间的关系。间的关系。w 两者不可偏废一者。两者不可偏废一者。课程介绍课程介绍地位地位: : 数学、软件、硬件之间数学、软件、
4、硬件之间相关的课程相关的课程离散数学离散数学程序设计程序设计操作系统操作系统编译原理编译原理数据库数据库是核心专业基础课！是核心专业基础课！数学数学 代数系统代数系统硬件硬件存储装置存储装置系统设计系统设计 软件软件文件系统文件系统数据组织数据组织信息检索信息检索程序设计程序设计编码理论编码理论 算子关系算子关系数据类型数据类型数据表示数据表示 数据运算数据运算数据结构数据结构数据存储数据存储机器组织机器组织党政机关 党委总机 4811122 宣传部 4811234 组织部 4812345大专院校 内蒙古大学 校务办公室 4991234 计算机学院 4992930 党政机关 党委总机 4811
5、122 宣传部 4811234 组织部 4812345大专院校 内蒙古大学 校务办公室 4991234 计算机学院 4992930 党政机关 党委总机 4811122 宣传部 4811234 组织部 4812345大专院校 内蒙古大学 校务办公室 4991234 计算机学院 4992930 党政机关党政机关 党委总机党委总机 4811122 宣传部宣传部 4811234 组织部组织部 4812345大专院校大专院校 内蒙古大学内蒙古大学 校务办公室校务办公室 4991234 计算机学院计算机学院 4992930 电话号码本电话号码本1v 例例1.16845678是谁的电是谁的电话？话？ 太难找
6、了！太难找了！10党政机关 党委总机 4811122 宣传部 4811234 组织部 4812345大专院校 内蒙古大学 校务办公室 4991234 计算机学院 4992930 党政机关 党委总机 4811122 宣传部 4811234 组织部 4812345大专院校 内蒙古大学 校务办公室 4991234 计算机学院 4992930 党政机关 党委总机 4811122 宣传部 4811234 组织部 4812345大专院校 内蒙古大学 校务办公室 4991234 计算机学院 4992930 110 .匪警 119火警120急救1234567.6845678.Tom电话号码本电话号码本2684
7、5678是老朋友是老朋友Tom的电话？的电话？ 太太容易找了！容易找了！电话号码结构：电话号码结构：按电话号码的大小排列按电话号码的大小排列数据的安排直接影响到工作效率。数据的安排直接影响到工作效率。电话号码结构：按照单位排列电话号码电话号码结构：按照单位排列电话号码内蒙古党委内蒙古党委内蒙古政府内蒙古政府党政机关党政机关理工学院理工学院计算机系计算机系网络中心网络中心计算中心计算中心计算机学院计算机学院内蒙古大学内蒙古大学内蒙古工业大学内蒙古工业大学大专院校大专院校医疗卫生医疗卫生交通运输交通运输呼和浩特市呼和浩特市电话号码簿电话号码簿v 例例1.2假设要在假设要在n个城市之间建立通信联络网
8、，连通个城市之间建立通信联络网，连通n 个城市个城市最少需要最少需要n-1条线路，如何在最节省经费的前提下建立条线路，如何在最节省经费的前提下建立这个通信网。这个通信网。281234567 1016 141812 25 2422关系图见图，从图可以看出，实线连关系图见图，从图可以看出，实线连接的顶点表示不可以同一天举行比赛，接的顶点表示不可以同一天举行比赛，由虚线连接的顶点表示比赛可以在同一由虚线连接的顶点表示比赛可以在同一天举行，所以四个球队进行的循环赛至天举行，所以四个球队进行的循环赛至少需要三天少需要三天: AB，ACBD，ADBC。A,B,C,D 4个球队进行循环比赛，规定一个队在一天
9、个球队进行循环比赛，规定一个队在一天中最多进行一场比赛，中最多进行一场比赛，C和和D已进行过比赛，问至少还已进行过比赛，问至少还需比赛几天？需比赛几天？v 例例1.3ABBCBDADAC 球队比赛图球队比赛图解：解：因为还有因为还有5场比赛：场比赛：AB, AC, AD, BC, BD。每一场比赛表示图中的一个顶点。每一场比赛表示图中的一个顶点。如边如边(AB,AC)表示表示AB和和AC不能在同一天进行。不能在同一天进行。 能被计算机表示、存储和加工处理的一切信息。能被计算机表示、存储和加工处理的一切信息。基本概念基本概念数据数据(Data)：v 例例1.3 1.3 学生信息登记表学生信息登记
10、表每一行是一个每一行是一个数据元素，学生数据元素的集合数据元素，学生数据元素的集合是一个数据对象是一个数据对象.基本概念基本概念数据元素数据元素(Data Element)： 数据的基本单位，数据的基本单位，相对独立，通常作为一个整体看待。相对独立，通常作为一个整体看待。姓姓 名名学学 号号性性 别别年龄年龄民族民族系系专业专业入学时间入学时间.数据项数据项(Data Item)： 组成数据元素的不可分割的最小单位。组成数据元素的不可分割的最小单位。 如：学号，姓名，年龄如：学号，姓名，年龄姓姓 名名学学 号号性性 别别年龄年龄民族民族系系专业专业入学时间入学时间王小林王小林060631男男1
11、8汉族汉族计算机计算机计算机科学计算机科学2006,9陈陈 红红060632女女20计算机计算机计算机应用计算机应用2006,9刘建平刘建平060633男男19回族回族计算机计算机电子商务电子商务2006,9. .基本概念基本概念17 性质相同的数据元素的集合。性质相同的数据元素的集合。 如如 A,B,Z,a,b,z是一个数据对象是一个数据对象.基本概念基本概念数据对象数据对象(Data Object)：是一个数据对象。,.,.,3, 2, 1, 0n数据类型数据类型(Data Type)： 指定一种数据对象的类型指定一种数据对象的类型. 如如 字母数据对象字母数据对象.包括包括A,B,Z,a
12、,b,z 定义为一个定义为一个值的集合值的集合以及定义在该值集合上的以及定义在该值集合上的一组一组操作操作的总称的总称. 如如 整数数据对象整数数据对象.包括包括0, 1, 2, 3, n基本概念基本概念C+语言的数据类型语言的数据类型基本类型基本类型结构类型结构类型整型整型实型实型字符型字符型枚举型枚举型指针型指针型数组型数组型结构型结构型共用体共用体类类基本概念基本概念数据结构研究的对象包括三个方面数据结构研究的对象包括三个方面:数据的逻辑结构数据的逻辑结构 指数据之间的逻辑关系指数据之间的逻辑关系, 即指数据元素之间的关联方即指数据元素之间的关联方式或邻接关系。式或邻接关系。数据的存储结
13、构数据的存储结构 指数据在计算机中存储的位置，如某个电话号码在指数据在计算机中存储的位置，如某个电话号码在号码本上的位置。号码本上的位置。运算的集合（算法）运算的集合（算法） 定义在逻辑结构上的一组操作。定义在逻辑结构上的一组操作。 如输入如输入/读取、检索读取、检索/查找、插入、删除、更新等。查找、插入、删除、更新等。数据结构的概念：数据结构的概念：数据结构数据结构: : 按照某种按照某种逻辑关系逻辑关系组织起来的一批数据组织起来的一批数据, 按按一定的一定的存储方法存储方法把它存储在计算机中把它存储在计算机中, 并在这些数据上并在这些数据上定义了一个定义了一个运算的集合运算的集合.根据数据
14、元素间的不同特性根据数据元素间的不同特性, 通常有以下通常有以下4种基本逻辑结构：种基本逻辑结构：逻辑结构逻辑结构2. 集合集合1. 线性结构线性结构3. 树型结构树型结构4. 图型或网状结构图型或网状结构非线性结构非线性结构数据元素间的逻辑数据元素间的逻辑结构可形式描述为：结构可形式描述为：DS=(D,R)其中：其中：D 是数据元素的有限集合；是数据元素的有限集合；R是是 D上的关系有限集合；上的关系有限集合；q 线性结构线性结构(Linear Structure)：DS=(D, R)D=d1,d2, dnR=| i=1,2,3, n-1v例例1.4：DS=(D,R1) D=d1, d2,
15、d3, d4,d5,d6 R1 =, , , , d1 d2 d3 d4 d5 d6 线性结构线性结构线性结构的线性结构的特点：特点：结构中的数据元素具有结构中的数据元素具有“一对一一对一”的关系的关系v例例1.5 DS=(D，R2) D=d1, d2, d3, d4,d5,d6 d1 D , d2 D , d3 D , d4 D , d5 D , d6 Dq集合集合集合特点：集合特点：结构中的数据元素只具有结构中的数据元素只具有“同属于一个集合同属于一个集合”的关的关系系d1 d2 d3d4 d5 d6集合集合v例例1.6：DS=(D,R3) D=d1, d2, d3, d4 ,d5,d6,
16、d7 R3 =, , , , q 树型结构树型结构d4d1d2d3d5d6 d7 树型结构树型结构根结点根结点:无前驱的结点，无前驱的结点， 如如d1叶结点叶结点: 无后继的结点，无后继的结点， 如如d4,d5,d6,d7树型结构的特点：树型结构的特点：有且仅有一个根结点，有且仅有一个根结点，其它结点有且仅有一个其它结点有且仅有一个前驱结点，对于非根结前驱结点，对于非根结点都存在从根到该结点点都存在从根到该结点的一条路径。的一条路径。结构中的数据元素结构中的数据元素存在存在一对多一对多的关系的关系v例例1.7：DS=(D,R4) D=d1, d2, d3, d4,d5 R4 =, , , , , , q图型或网状结构图型或网状结构图型结构的特点：图型结构的特点：结构中的数据元素结构中的数据元素存在存在多对多多对多的关系的关系d1d2d3d4d5抽象数据类型与数据类型的不同点抽象数据类型与数据类型的不同点：数据类型仅局限于计算机中定义并实现了的数据类型数据类型仅局限于计算机中定义并实现了的数据类型;而抽象数据类型还包括用户在设计软件系统时自己定义的而抽象数据类型还包括用户在设计软
