数据结构与STL绪论

1、数数 据据 结结 构构信息与通信工程学院信息与通信工程学院蔺志青蔺志青联系方式联系方式：蔺志青蔺志青Email: Tel :料网址资料网址:http:/数据结构课程的地位数据结构课程的地位数据结构课程的学习方法数据结构课程的学习方法1. 计算机及相关专业的专业基础课。计算机及相关专业的专业基础课。2.2.程序设计和大型软件开发的核心。程序设计和大型软件开发的核心。3. 在本专业中的地位。在本专业中的地位。1. 课程特点课程特点: 注重数据组织和算法思路、强调解决问题的能力、注重数据组织和算法思路、强调解决问题的能力、实践性强。实践性强。2. 学习方法和要求学习方法和要

2、求: 预习预习、记结构、读算法、写算法、上机调试。、记结构、读算法、写算法、上机调试。( (一般课程的学习方法一般课程的学习方法: :) )数据结构数据结构基本概念基本概念2学时学时 算法算法基本概念基本概念1学时学时线性表线性表6学时学时查找技术查找技术4学时学时栈、队列、栈、队列、串串5学时学时 数组数组2学时学时树树6学时学时图图6学时学时主要内容和学时安排主要内容和学时安排: : 共共3838学时学时排序技术排序技术6学时学时 考核考核平时平时10%实验实验30%期末闭卷考试期末闭卷考试60%没有期中考试没有期中考试期末考试时间，初步定在期末考试时间，初步定在12月下旬月下旬数据结构与

3、STL6第一章第一章 绪论绪论学习内容：学习内容：1.1 数据结构的起源数据结构的起源 1.2 数据结构的基本概念数据结构的基本概念 1.3 算法和算法分析简介算法和算法分析简介 1.4 STL与数据结构与数据结构1.5 实例分析实例分析数据结构与STL71.1 数据结构的起源数据结构的起源程序设计的两个重要问题：程序设计的两个重要问题： 待处理的数据存储到计算机中设计相应的算法操作这些数据数据表示数据表示数据处理数据处理 对数据的处理对数据的处理 数据的逻辑表示数据的逻辑表示数据的存储方法数据的存储方法数据结构数据结构课程内容课程内容数据结构与STL8起源起源计算机处理的对象计算机处理的对象

4、 数值问题数值问题非数值问题非数值问题大量数据大量数据计算机发展初期：处理数值计算问题计算机发展初期：处理数值计算问题 不重视数据结构不重视数据结构 20世纪世纪6080年代：非数值处理年代：非数值处理(结构化程序设计结构化程序设计) 沃思：沃思：算法算法 + 数据结构数据结构 = 程序程序 20世纪世纪80年代至今：面向对象年代至今：面向对象(OO)技术出现技术出现 数据结构与面向对象具有天然的对应数据结构与面向对象具有天然的对应 算法和数据结构的关系算法和数据结构的关系: 电话号码查询问题电话号码查询问题 电话号码簿，已知电话号码簿，已知n n个人名和对应的电话号码。个人名和对应的电话号码

5、。要求：设计一个算法，当给定任何一个人名时，该算法能查出对应的电话号码，若没有此人，则报告标志。数据：人名和电话号码。操作：查找。数据组织： （1）无规则的任意排列。 （2）将人名按拼音的字母顺序排列，或按姓氏笔划排列。算法设计：如何设计，与数据组织有关？如果要求按电话号码查询人名呢？如何设计数据结构。如果要求按电话号码查询人名呢？如何设计数据结构。数据结构与STL10电话号码查询问题如果要求按电话号码查询人名呢？如何设计数据结构。顺序查找折半查找索引查找 田径运动会时间安排田径运动会时间安排姓名姓名 项目项目1 项目项目2 项目项目3丁一跳高 A跳远 B100米E马二标枪 C铅球 D张三标枪

6、 C100米E200米F李四铅球 D200米F跳高 A王五跳远 B200米F 参赛选手比赛项目表参赛选手比赛项目表 数据结构模型数据结构模型 比赛时间表比赛时间表AFDCEB时间1时间2时间3时间4A, CB, DEFKnuth(唐纳德克努特): 1938年出生，25岁毕业于加州理工学院数学系，博士，留校任教，28岁时任副教授。30岁时，加盟斯坦福大学计算机系，任正教授。从31岁起，开始出版他的历史性经典巨著：The Art of Computer Programming。他计划共写7卷，然而出版三卷之后，已震惊世界，使他获得计算机科学界的最高荣誉Turing Award，此时，他年仅36岁。

7、他有一个奇妙的承诺：在他定期进行的讲座中，会不断提出一些新的难题。如果有人能在给定的期限内解出任何一道难题，他将为那个人的博士论文签名(大约相当于名誉导师吧)！不知道世界之大，有没有哪位后起之秀能获得这样的殊誉？数据结构与STL13第一章第一章 绪论绪论学习内容：学习内容：1.1 数据结构的起源数据结构的起源 1.2 数据结构的基本概念数据结构的基本概念 1.3 算法和算法分析算法和算法分析 1.4 STL与数据结构与数据结构1.5 实例分析实例分析数据结构与STL141.2 数据结构的基本概念数据结构的基本概念数据（数据（data） 信息的载体信息的载体 分为两类：数值型数据、非数值型数据分

8、为两类：数值型数据、非数值型数据数据元素（数据元素（data element） 也称为元素、结点、顶点或记录也称为元素、结点、顶点或记录 是数据的基本单位，在计算机程序中通常是数据的基本单位，在计算机程序中通常作为一个整体进行处理。作为一个整体进行处理。数据项（数据项（data item） 也称为字段或域也称为字段或域 构成数据元素的不可分割的最小单位。每构成数据元素的不可分割的最小单位。每个数据元素可以包含多个不同的数据项。个数据元素可以包含多个不同的数据项。数据类型（数据类型（data type） 具有相同性质的计算机数据的集合以及在具有相同性质的计算机数据的集合以及在这个数据集合上的一组

9、操作。这个数据集合上的一组操作。 可分为简单类型和构造类型。可分为简单类型和构造类型。struct Studentint No;char name10;float score;int age;char sex;stu10=1,张三张三,90,19,M,2,张莉张莉,95,18,F;分析上述代码，哪些是：分析上述代码，哪些是：数据、数据元素、数据、数据元素、数据项、数据类型？数据项、数据类型？数据结构与STL15数据结构的概念数据结构的概念数据结构（数据结构（data structure）按照某种按照某种逻辑关系逻辑关系组织起来的一组数据，按一定组织起来的一组数据，按一定的的存储方式存储方式存储

10、在计算机的存储器中，并在这些存储在计算机的存储器中，并在这些数据上定义了一组数据上定义了一组运算运算(操作操作)的集合。的集合。数据结构包含三个方面的内容数据结构包含三个方面的内容: (三要素三要素)对数据的操作或运算对数据的操作或运算 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据结构与STL16数据的逻辑结构数据的逻辑结构描述数据元素相互间的关联形式或邻接形式描述数据元素相互间的关联形式或邻接形式反映了数据内部的构成方式反映了数据内部的构成方式定义了数据的本质特点定义了数据的本质特点常常将数据的逻辑结构直接称为数据结构常常将数据的逻辑结构直接称为数据结构数据的逻辑结构独立

11、于计算机，与存储方式无关，可数据的逻辑结构独立于计算机，与存储方式无关，可认为是从具体问题抽象出来的数学模型。认为是从具体问题抽象出来的数学模型。数据元素之间不同的逻辑特点代表不同的逻辑结构数据元素之间不同的逻辑特点代表不同的逻辑结构四四 种种 常常 见见 的的 逻逻 辑辑 结结 构构(a)集合集合 (b)线性结构线性结构 (c)树结构树结构 (d)图结构图结构例例1 学生学籍登记表学生学籍登记表线性结构线性结构学号学号姓名姓名性别性别出生日期出生日期政治面貌政治面貌0001王军男1993/09/02团员0002李明男1993/12/25党员0003汤晓影女1994/03/25团员例例2 人人

12、机对弈问题机对弈问题树形结构树形结构图图1-1 对弈树的局部对弈树的局部.例例3 教学计划编排问题教学计划编排问题图形结构图形结构编号编号课程名称课程名称先修课先修课C1高等数学高等数学无无C2计算机导论计算机导论无无C3离散数学离散数学C1C4程序设计程序设计C1, C2C5数据结构数据结构C3，C4C6计算机原理计算机原理C2，C4C7数据库原理数据库原理C4，C5，C6如何反映课程之如何反映课程之间次序关系？间次序关系？数据结构与STL20C6C1C3C5C7C2C4教学计划编排问题的拓扑结构图教学计划编排问题的拓扑结构图图形结构图形结构数据结构与STL21数据的存储结构数据的存储结构

13、考虑如何在计算机的存储器中存储各个数据元考虑如何在计算机的存储器中存储各个数据元素，并且同时反映数据元素间的逻辑关系。素，并且同时反映数据元素间的逻辑关系。对于每种逻辑结构，都可以设计多种存储方法对于每种逻辑结构，都可以设计多种存储方法基本的两种存储结构基本的两种存储结构顺序存储结构顺序存储结构链式存储结构链式存储结构存储结构存储结构：数据及其逻辑结构在计算机中的表示数据及其逻辑结构在计算机中的表示（又称映象）。（又称映象）。 通常有两种存储结构：通常有两种存储结构： （1 1）顺序存储结构：）顺序存储结构：用一组连续的地址空间用一组连续的地址空间依次存放所有数据依次存放所有数据元素。元素。

14、（2 2）链接存储结构：）链接存储结构：用一组任意的存储单元用一组任意的存储单元来存储数据元素，来存储数据元素，用指针来表示数据元素之间的用指针来表示数据元素之间的逻辑关系。逻辑关系。 元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容顺顺序序存存储储m1345h1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 4存储地址存储地址 存储内容存储内容 指针指针 1345 1345 元素元素1 1 14001400 1346 1346 元素元素4 4 14001400 元素元

15、素2 2 1536 1536 1536 1536 元素元素3 3 1346 1346链链式式存存储储 h数据的运算数据的运算( (操作操作):):是指对数据的读取、修改、加工、处理等操作是指对数据的读取、修改、加工、处理等操作。例如例如: 插入、删除、修改、查找、排序等。插入、删除、修改、查找、排序等。 数据结构的基本操作：数据结构的基本操作： 定义于逻辑结构，实现于存储结构。定义于逻辑结构，实现于存储结构。数据结构与STL26每学习一种数据结构每学习一种数据结构各种数据结构的学习主线各种数据结构的学习主线其逻辑结构是什么？可有哪些运算？其逻辑结构是什么？可有哪些运算？有哪些存储结构？有哪些存

16、储结构？C+如何描述各种存储结构如何描述各种存储结构基于每种存储结构，各种运算如何实现？基于每种存储结构，各种运算如何实现？各种存储结构的优缺点对比各种存储结构的优缺点对比数据结构与STL27第一章第一章 绪论绪论学习内容：学习内容：1.1 数据结构的起源数据结构的起源 1.2 数据结构的基本概念数据结构的基本概念 1.3 算法和算法分析简介算法和算法分析简介 1.4 STL与数据结构与数据结构1.5 实例分析实例分析数据结构与STL281.3 算法和算法分析简介算法和算法分析简介算法算法解题的方法解题的方法数据的运算是通过算法（数据的运算是通过算法（algorithm）描述的）描述的讨论算法

17、的效率和性能是数据结构课程的重要内容讨论算法的效率和性能是数据结构课程的重要内容算法通常满足算法通常满足5个准则：个准则：输入：输入：具有具有0个或多个输入的参数。个或多个输入的参数。输出：输出：算法执行要有输出结果。算法执行要有输出结果。有穷性：有穷性：算法中每条指令的执行次数必须是有限的。算法中每条指令的执行次数必须是有限的。确定性：确定性：每条指令必须有确切的含义，无二义性。每条指令必须有确切的含义，无二义性。可行性：可行性：每条指令的执行时间都是有限的。每条指令的执行时间都是有限的。 算法设计的原则算法设计的原则l 正确性：正确性：l程序中不含语法错误；程序中不含语法错误；l对于几组输

18、入数据能够得出满足要求的结果；对于几组输入数据能够得出满足要求的结果；l对精选的、典型的、刁难性的几组数据能得出满足要对精选的、典型的、刁难性的几组数据能得出满足要求的结果；求的结果；l对于一切合法的输入数据都能得出满足要求的结果。对于一切合法的输入数据都能得出满足要求的结果。l 可读性：可读性：l 健壮性：健壮性：l 高效率与低存储量需求高效率与低存储量需求l效率：算法执行时间；效率：算法执行时间；l存储量：最大存储空间。存储量：最大存储空间。自然语言流程图伪代码程序设计语言30数据结构与STL常见的算法描述方法常见的算法描述方法 数据结构与STL31欧几里得算法描述举例欧几里得算法描述举例

19、辗转相除法求两个自然数辗转相除法求两个自然数m和和n的最大公约数，的最大公约数，假定假定mn 自然语言描述：自然语言描述： 流程图描述：流程图描述：(1) 输入m和n；(2) 取得m除以n的余数r；(3) 若r=0，则n为最大公约数，算法结束；否则执行第(4)步；(4) 将n放到m中，r放到n中；(5) 转第(2)步执行。数据结构与STL32欧几里得算法描述举例欧几里得算法描述举例伪代码描述：伪代码描述： 程序设计语言描述：程序设计语言描述： 1. input m,n2. r=m%n;3. while (r!=0) 3.1 m=n; 3.2 n=r; 3.3 r=m%n;4. output n

20、;int EUCLID (int m, int n)int r = m % n;while (r != 0)m = n; n = r;r = m % n;return n;数据结构与STL33欧几里得算法描述举例欧几里得算法描述举例采用面向对象的方法描述：采用面向对象的方法描述： class NaturalNumberpublic: unsigned long int EUCLID(NaturalNumber & n); /欧几里德算法求解最大公约数 /其它外部接口private: unsigned long int num; /存储真正的自然数;/返回欧几里德算法求解最大公约数uns

21、igned long int NaturalNumber : EUCLID(NaturalNumber & n) unsigned long int m = (num n.num) ? num : n.num; /较大的自然数赋值给m unsigned long int n = (num n.num) ? num : n.num; /较小的自然数赋值给n unsigned long int r = m % n; while (r != 0) m = n; n = r; r = m % n; return n;算法效率的衡量方法和准则算法效率的衡量方法和准则算法执行时间的相关因素算法执行

22、时间的相关因素算法选用的策略算法选用的策略问题的规模问题的规模编写程序的语言编写程序的语言编译程序产生的机器代码的质量编译程序产生的机器代码的质量计算机执行指令的速度计算机执行指令的速度事后统计法事后统计法必须执行程序必须执行程序其他因素掩盖算法本质其他因素掩盖算法本质事前分析估算法事前分析估算法数据结构与STL35算法好坏的评价算法好坏的评价:算法的时间复杂度算法的时间复杂度算法的空间复杂度算法的空间复杂度算法的可读性算法的可读性.算法的执行时间算法的执行时间:与哪些因素相关？与哪些因素相关？问题规模通常是指算法处理的数据量的大小，记作问题规模通常是指算法处理的数据量的大小，记作 n。运行算

23、法所需要的时间运行算法所需要的时间 T 可看作问题规模可看作问题规模n的函数，的函数， 记作记作T(n)。 算法分析算法分析 计算工具计算工具 对算法执行时间的度量对算法执行时间的度量算法本身算法本身 问题的规模问题的规模数据结构与STL36语句的频度（语句的频度（frequency count） 即：语句执行的次数即：语句执行的次数 假定每条语句执行一次所需的时间是假定每条语句执行一次所需的时间是单位时间单位时间，则每条语句执行的时间正比于该语句执行的次数则每条语句执行的时间正比于该语句执行的次数 算法运行时间算法运行时间算法中所有语句的频度之和。算法中所有语句的频度之和。 for (i=0

24、; in; i+) n+1 for (j=0; jn; j+) n(n+1) k+; n2语句的频度语句的频度算法的总用时：T(n)=2n2+2n+1 算法时间复杂度的估算算法时间复杂度的估算算法的工作量：所有语句的频度之和；算法的工作量：所有语句的频度之和；( (但过于具体将非常繁琐，而且不能反映时间耗费的但过于具体将非常繁琐，而且不能反映时间耗费的本质本质) )；算法算法 = = 控制结构控制结构+ +原操作原操作原操作法：基本操作原操作法：基本操作-原操作原操作设设f(n)f(n)为原操作对为原操作对n n的函数，的函数，执行时间执行时间= = 原操作原操作( (i)i)的执行次数的执行

25、次数* *原操作原操作( (i)i)的执行时间的执行时间数据结构与STL38算法的渐进时间复杂度算法的渐进时间复杂度当表达式结果为常数当表达式结果为常数222( )221limlim2nnT nnnnnT(n)与n2是同阶的 T(n)与n2是同数量级的记作T(n)=O(n2) 称为算法的时间复杂度算法的时间复杂度时间复杂度也可以利用算法中的基本语句计算 基本语句：执行次数与算法的执行次数成正比的语句。 数据结构与STL39分析算法的时间复杂度分析算法的时间复杂度 j += i;i = j - i;j = j - i;for (i=0;i100;i+) for (j=0;ji;j+)sum +=

26、 j;for (i=0;in;i+) for (j=0;j=i;j+)sum += j;12011(1)22niinnO(1)O(1)O(n2)数据结构与STL40y=0;while (y+1)*(y+1)=n) y+; (T(n)+1)2 nT(n)=O(n1/2) i=0,j=0;while (i+jj) j+;else i+;O(n) 数据结构与STL41特殊情况下的算法时间复杂度特殊情况下的算法时间复杂度最好的执行次数最好的执行次数最坏的执行次数最坏的执行次数平均时间复杂度平均时间复杂度 在数组an中查找值为k的元素，若找到返回其位置i（0in），否则返回-1。int i=n-1;wh

27、ile(i=0 & ai!=k) i-;return i;1 n 110011(1)2nniiinp niin O(n) 数据结构与STL42时间复杂度时间复杂度O(？) 1, logn, n1/2, n, nlog2n, n2 , n3, 2n ?常见的时间复杂度常见的时间复杂度常数阶常数阶O(1)、对数阶、对数阶O(logn)、线性阶、线性阶O(n)、线性对数阶、线性对数阶O(nlogn)、平方阶、平方阶O(n2)、立方阶、立方阶O(n3)、k次方阶次方阶O(nk)、指数阶指数阶O(2n)等。等。当问题规模当问题规模n较大时，具有指数阶量级的算法是不可计算的较大时，具有指数阶量级的

28、算法是不可计算的数据结构与STL43算法的空间复杂度算法的空间复杂度空间复杂度空间复杂度算法在执行过程中所耗费的存储空间算法在执行过程中所耗费的存储空间 也是问题规模也是问题规模n的函数的函数 对空间复杂度的重视情况：对空间复杂度的重视情况：早期：计算机系统内存较小早期：计算机系统内存较小空间复杂度非常空间复杂度非常重视重视现代：计算机内存储器成本降低，存储容量的不现代：计算机内存储器成本降低，存储容量的不断增大断增大 空间效率换时间效率空间效率换时间效率问题规模问题规模n很大时，算法的空间效率也非常重要！很大时，算法的空间效率也非常重要！ 数据结构与STL44第一章第一章 绪论绪论学习内容：

29、学习内容：1.1 数据结构的起源数据结构的起源 1.2 数据结构的基本概念数据结构的基本概念 1.3 算法和算法分析简介算法和算法分析简介 1.4 STL与数据结构与数据结构1.5 实例分析实例分析数据结构与STL451.4 STL与数据结构与数据结构STL:Standard Template Library，标准模板类，标准模板类是C+语言提供的一个基础模板集合，包含了各种常用的存储数据的模板类及相应的操作函数，为开发者提供了一种快速有效的访问机制。起初由惠普实验室（Hewett-Packard Labs）开发，并于1998年被定为国际标准，正式成为C+语言的标准库。是一些容器、算法和其他一些组件的集合，这些容器有list，vector，set，map等。 数据结构与STL46STL构成构成 适配器适配器容器适配器，如容器适配器，如stack、queue、priority_queue迭代器适配器迭代器适配器泛函适配器泛函适配器 容器容器顺序容器：顺序容器：vector、list、 deque