算法与数据结构（C++语言版）（第2版） 课件 第1章-绪论

DataStructureandAlgorithmdesign|analyze|experiment|implement数据结构与算法第一章概述《算法与数据结构（C++语言版第2版）》1.1课程介绍1.2什么是数据结构？1.3基本概念和术语1.4算法和算法分析1.5抽象数据类型*1.6算法拓展*1.7你怎么看？目录CONTENTS课程介绍核心专业基础课线上线下混合式第2学期开设84学时扩展24

1课程地位第1章概论 2~4

学时第2章线性表 6~8 学时第3章栈和队列 6~8 学时第4章串 2~4 学时第5章数组 0~4 学时第6章树 6~8 学时第7章树的应用

4~6 学时第8章图 6~8 学时第9章图的应用 4~6 学时第10章集合与查找 2~4 学时第11章散列 2~2 学时第12章排序 6~8 学时复习 2~2 学时共计 48~72学时课程介绍后续课程（数据库、操作系统、人工智能、网络等）的基础硕士研究生入学考试课程2002年前：专业课两张卷，各100分

(多数高校数据结构占100分)2003--2008：专业课一张卷，150分

(部分高校只考数据结构，如华中科大、北京交大、江苏大学等)2009----专业基础综合一张卷全国统考

(4科，数据结构占45分)2013----专业基础综合一张卷全国统考/自主命题(暨南大学、深圳大学等只考数据结构)课程介绍图源：淘宝网猜一猜课程介绍约5000pcs积木图源：淘宝网课程介绍程序设计就像搭积木数据结构是零件算法则是设计图纸课程介绍

2学什么？

2学什么？Pascal之父——NicklausWirth1984年图灵奖获得者Algorithms+DataStructures=Programs算法+数据结构=程序课程介绍记忆理解应用分析评价创新Learntoknow知识与技能Learntodo方法与能力Learntobe思维与创新Learntolearn未来与发展品格态度价值观

3为什么学？低阶高阶课程介绍

4课程目标编写高质量的程序课程介绍教材：冯广慧等，算法与数据结构(c++语言版)，电子工业出版社，2018-12参考书：严蔚敏，数据结构（C语言版），清华大学出版社，2012-5陈守孔、胡潇琨、李玲、冯广慧，算法与数据结构考研试题精析（第4版），机械工业出版社，2020-6

5教材和参考书课程介绍学生作品展演20集课堂教学录像62节，2480分钟习题解析23讲260分钟算法模拟动画40余算法学堂在线MOOC30讲，600分钟

6线上资源在线课程（参考）：（SPOC：习题微课、算法模拟动画、课堂实录、展演视频等）（MOOC：知识点微课、算法模拟动画、章节测验）课程介绍Manim是一款数学动画制作引擎，3Blue1Brown深入浅出、直观明了地分享数学之美，以独特的视觉角度解说高等数学，内容包括线性代数、微积分、神经网络、黎曼猜想、傅里叶变换以及四元数等等。

6在线资源课程介绍课前准备知识与技巧课堂教学模拟动画重难精讲、算法案例、真题方法与能力课后提升思维与创新项目小组导学微课习题微课情感与价值观线上线下混合模式

7怎么学？要求：“诚信代码保证”每人提交实验报告要求：理解基本概念和术语要求：参与式学习学堂在线MOOC、优慕课SPOC、百科园考试系统课程介绍不闻不若闻之，闻之不若见之，见之不若知之，知之不若行之。——摘自《荀子·儒效》WhatIhear,Iforget.WhatIhearandsee,Irememberalittle.WhatIhear,see,andaskquestionsaboutordiscusswithsomeoneelse，Ibegintounderstand.WhatIhear,see,discussanddo,Iacquireknowledgeandskill.WhatIteachtoanother,Imaster.——Silberman

7怎么学？课程介绍1.1课程介绍1.2什么是数据结构？1.3基本概念和术语1.4算法和算法分析1.5抽象数据类型*1.6算法拓展*1.7你怎么看？目录CONTENTS什么是数据结构？中国软件和信息技术服务业发展现状表

1例1线性结构

1例2树型结构什么是数据结构？

1例3铁路“十三五”发展规划图状结构什么是数据结构？数据结构是一门研究（）的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。数值计算非数值计算AB提交单选题10分1.1课程介绍1.2什么是数据结构？1.3基本概念和术语1.4算法和算法分析1.5抽象数据类型*1.6算法拓展*1.7你怎么看？目录CONTENTS数据结构三要素

1基本概念和术语(1)数据（Data）、(2)数据元素（DataElement）、(3)数据项（DataItem）、(4)数据对象（DataObject）学号姓名性别专业住址04200101侯亮平男计算机科学与技术北京04200102陆亦可女计算机科学与技术上海04200103李达康男计算机科学与技术广州04200104冯小强男计算机科学与技术深圳04200105张小雅女计算机科学与技术重庆04200106沙瑞金男计算机科学与技术珠海……………数据元素数据项计算机科学与技术专业2020级学生信息表数据对象

2数据的逻辑结构数据结构三要素036036（1）顺序存储（2）链式存储（3）索引存储

3数据的存储结构思考：顺序结构如何实现？

链式结构如何实现？数据结构三要素

3数据的存储结构（4）数据结构三要素

4数据结构三要素数据结构三要素在数据结构中，从逻辑上可以将之分为()。动态结构和静态结构紧凑结构和非紧凑结构内部结构和外部结构线性结构和非线性结构ABCD提交单选题10分己知表头元素为c的单链表在内存中的存储状态如下表所示。现将f放于1014H处并插入到单链表中，若f在逻辑上位a和e之间，则a，e，f的链接地址”依次是()1010H,1014H,1004H1010H,1004H,1014H1014H,1010H,1004H1014H,1004H,1010HABCD提交地址元素链接地址1000Ha1010H1004Hb100CH1008Hc1000H100CHdNULL1010He1004H1014H

【2012全国硕士统考408】单选题10分1.1课程介绍1.2什么是数据结构？1.3基本概念和术语1.4算法和算法分析1.5抽象数据类型*1.6算法拓展*1.7你怎么看？目录CONTENTS算法（Algorithm）：是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。简单的说，算法就是解决特定问题的方法。我们的课程用C/C++语言描述算法。评价一个算法优劣的重要依据：花费的时间代价占有的空间代价算法的定义及特性

1算法的概念算法具有下列重要特性：1．有穷性2．确定性3．可行性4．输入（零个或多个输入）5．输出（一个或多个输出）

2算法的特性算法的定义及特性百钱买百鸡问题是一个数学问题，出自中国古代约5—6世纪成书的《张邱健算经》，是全书的最后一题。今有鸡翁一，值钱伍；鸡母一，值钱三；鸡雏三，值钱一。凡百钱买鸡百只，问鸡翁、母、鸡雏各几何？【要求公鸡，母鸡，小鸡数量不为零】请2位同学展示代码，并分析原操作的执行次数。

3算法的重要性

小组讨论算法的定义及特性 x+y+z=100 ① 5x+3y+z/3=100 ②令3x②-①可得 7x+4y=100即 y=25-(7/4)x

③又因为y是自然数，则可令

x=4k

④ 将④代入③可得

y=25-7k

⑤ 由0<y<100可知1<=k<=3将④⑤代入①可得

z=75+3k

⑥

要保证0<x，y，z<100，k的取值范围只能是[1,3]

这个方法好吗？

算法思想算法的定义及特性intmain(){intx,y,z;cout<<"百元买百鸡的问题所有可能的解如下：\n";for(intk=1;k<=3;k++){ x=4*k; //公鸡 y=25-7*k; //母鸡 z=75+3*k; //小鸡 cout<<"公鸡:"<<x<<"只" <<"母鸡:"<<y<<"只"<<"小鸡:"<<z<<"只\n";}return0;}

代码实现

循环体只执行3次算法的定义及特性设计一个好的算法通常要考虑达到以下目标：1．正确性（Correctness)2．可读性（Readability）3．健壮性（Robustness）4．高效性（Highefficiency)算法和算法分析

4算法的设计要求解决同一个问题总是存在着多种算法，最重要的计算资源是时间和空间衡量算法效率的方法主要有两大类：1．事后统计的方法2．事前分析估算的方法去除掉一些与计算机硬件、软件有关的因素，可以认为算法的“运行工作量”只依赖于问题的规模n

5算法效率的衡量方法算法和算法分析算法的时间复杂度（TimeComplexity）T(n)是该算法的时间耗费，是其所求解问题规模n的函数。当问题规模n趋向无穷大时，不考虑具体的运行时间函数，只考虑运行时间函数的数量级（阶）这称为算法的渐进时间复杂度(AsymptoticTimeComplexity)。

6算法的时间复杂度算法和算法分析渐进表示法的常用记法——大O表示法

T(n)=O(f(n))说明：如果存在常量c>0和正整数n0>=1，当n>=n0

时有T(n)<=cf(n)。即给出了时间复杂度的上界，不可能比cf(n)更大。

6算法的时间复杂度算法和算法分析例：某算法时间函数T(n)=n2+2n+1，求它的时间复杂度。分析：当n0=1，c=4时，若n>=n0

，则：n2+2n+1<4n2因此：时间复杂度用大O表示法记为T(n)=O(n2)算法和算法分析常见的时间复杂度及其关系如下：计算时间复杂度的小技巧：(1)找最复杂、运行时间最长的(2)保留最高次项，忽略系数和低次项

6算法的时间复杂度算法和算法分析语句的频度(frequencycount)指该语句重复执行的次数。【例1】分析下述程序段的时间复杂度。for(j=1;j<=10000;++j)++x;分析：选取“++x;”为基本操作，语句频度为10000，则时间复杂度为O(1)，即常量阶。

6算法的时间复杂度算法和算法分析【例2】分析下述程序段的时间复杂度。for(j=1;j<=n;j*=2)++x;分析：选取“++x;”为基本操作，语句频度为log2n，则时间复杂度为O(log2n)，即对数阶。

6算法的时间复杂度算法和算法分析【例3】分析下述程序段的时间复杂度。for(i=1;i<=100*n;++i)++x;分析：选取“++x;”为基本操作，语句频度为100×n，则时间复杂度为O(n)，即线性阶。

6算法的时间复杂度算法和算法分析

【例4】分析下述程序段的时间复杂度。for(j=1;j<=n;j++)for(k=1;k<=j;++k)++x;分析：选取“++x;”为基本操作，语句频度为(1+n)×n/2，则时间复杂度为O(n2)，即平方阶。思考：所有的双重循环时间复杂度都是O(n2)吗？

6算法的时间复杂度算法和算法分析【例5】分析下述程序段的时间复杂度。for(j=1;j<n;j*=2){for(k=1;k<=n;++k){++x;}}时间复杂度为O(nlog2n)，即线性对数阶

6算法的时间复杂度算法和算法分析求整数n(n>=0)阶乘的算法如下，其时间复杂度是()。O(log2n)O(n)O(nlog2n)O(n2)ABCD提交intfact(intn){if(n<=1)return1；

returnn*fact(n-1)；}【2012全国硕士统考408】单选题10分下列程序段的时间复杂度()。O(log2n) O(n)O(nlog2n) O(n2)ABCD提交【2014全国硕士统考408】for(k=1;k<=n;k*=2)for(j=1;j<=n;j+=1)count++;单选题10分下列函数的时间复杂度()。O(log2n)O(n1/2)O(n)O(nlog2n)ABCD提交【2017全国硕士统考408】intfunc(intn){inti=0,sum=0;while(sum<n)sum+=++i;returni;}单选题10分设n是描述问题规模的非负整数，下列程序段的时间复杂度是（

）。O(log2

n) O(n1/2)O(n) O(n2)ABCD提交【2019年全国统考408】x=0；while(n>=(x+l)*(x+l))x=x+l；单选题10分空间复杂度（SpaceComplexity）或称为空间复杂性是指解决问题的算法在执行时所占用的存储空间，也是衡量算法有效性的一个指标，记作：

S(n)=O(g(n))其中n为问题的规模（或大小）。表示随着问题规模n的增大，算法运行所需存储量的增长率与函数g(n)的增长率相同。

7算法的空间复杂度算法和算法分析如果输入数据所占空间只取决于问题本身，和算法无关，则在讨论算法的空间复杂度时只需分析除输入和程序之外的辅助变量所占的额外空间即可。如果所需额外空间相对于输入数据量来说只是一个常数，则称此算法为“原地工作”，此时的空间复杂度为O(1)；如果算法所需的存储量与特定的输入有关，同时间复杂度一样，也是按照最坏的情况进行考虑。

7算法的空间复杂度算法和算法分析算法是供人阅读的程序是让机器执行的算法用计算机语言实现时就是程序程序不具有算法的有穷性算法<>程序1.1课程介绍1.2什么是数据结构？1.3基本概念和术语1.4算法和算法分析1.5抽象数据类型*1.6算法拓展*1.7你怎么看？目录CONTENTS和数据结构的形式定义相对应，抽象数据类型可用以下三元组表示：（D，R，P）其中D是数据对象，即具有相同特性的数据元素的集合。R是D上的关系集合，P是对D的基本操作集合。抽象数据类型的伪代码定义格式：ADT抽象数据类型名{

数据对象D：<数据对象的定义>

数据关系R：<数据关系的定义>

基本操作P：<基本操作的定义>}ADT抽象数据类型名抽象数据类型随着程序设计的发展，数据结构的发展经历了三个阶段：——无结构阶段——结构化阶段——面向对象阶段计算机科学家N.Wirth教授曾经提出一个著名的公式“算法+数据结构=程序”这个公式在软件开发的进程中产生了深远的影响，但是，它并没有强调数据结构与解决问题的算法是一个整体，因此在面向对象程序设计阶段，有人主张将它修改为：程序=对象+对象+…抽象数据类型抽象数据类型ADTList{数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R={<ai-1,ai>|ai,ai-1∈D,i=2,…,n}基本操作：ListInit(L)；ListLength(L)；ListGet(L,i);ListLocate(L,x);ListClear(L);ListEmpty(L)；ListPrior(L,e)；ListNext(L,e)；ListInsert(L,i,e);ListDelete(L,i);}ADTList1.了解数据结构求解非数值计算问题2.理解数据结构的基本概念和术语：数据、数据元素、数据项、数据对象、数据结构的三要素，掌握逻辑结构和存储结构的分类3.理解算法的概念和特点，掌握基本的算法分析方法，会计算算法的时间复杂度总结1.1课程介绍1.2什么是数据结构？1.3基本概念和术语1.4算法和算法分析1.5抽象数据类型*1.6算法拓展*1.7你怎么看？目录CONTENTS【蓝桥杯】最大连续子序列和问题对于一个给定的长度为N的整数序列A，它的“子序列”的定义是：A中非空的一段连续的元素（整数）。你要完成的任务是，在所有可能的子序列中，找到一个子序列，该子序列中所有元素的和是最大的（跟其他所有子序列相比），如所有子序列之和都是负数则返回0。程序要求你输出这个最大值。输入输入文件的第一行包含一个整数N，第二行包含N个整数，表示A。其中1<=N<=100000-10000<=A[i]<=

10000输出输出仅包含一个整数，表示你算出的答案。样例输入53-23-54样例输出4算法拓展求数组中最大连续子序列之和，如所有子序列之和都是负数则返回0。例如:数组A：{-2,11,-4,13,-5,-2}，

最大连续子序列之和为20，即11+(-4+13)=20。数组B：{1,3,-2,4,-5}，

最大连续子序列之和为6，即1+3+(-2)+4=6。算法拓展方法一：求出所有连续子序列之和，然后从中选取最大值。下面列举了所有子序列的下标范围：[0，0]，[0，1]，…，[0，n-1][1，1]，[1，2]，…，[1，n-1]……[n-1，n-1]算法拓展intmaxSubSum1(intarray[],intlength){inti,maxSum=0,start,end;//start为待求和的子序列的起始下标，end为结束下标

for(start=0;start<length;start++)for(end=start;end<length;end++){intthisSum=0;//统计子序列array[start]~array[end]之和

for(i=start;i<=end;i++)thisSum+=array[i];if(thisSum>maxSum)maxSum=thisSum;}returnmaxSum;}时间复杂度为O(n3)方法一算法拓展方法二：算法设计的一个重要原则就是“不做重复的事”可以由array[start]～array[end-1]求和结果，加上array[end]得到array[start]～array[end]之和

。如：array[0]array[1]array[2]array[3]array[4]array[5]array[5]算法拓展intmaxSubSum2(intarray[],intlength){intmaxSum=0,start,end;for(start=0;start<length;start++){intthisSum=0;for(end=start;end<length;end++){ thisSum+=array[end];if(thisSum>maxSum)maxSum=thisSum;}}returnmaxSum;}时间复杂度为O(n2)方法二算法拓展

算法拓展intmaxSubSum3(intarray[],intlength){intmaxSum=0,thisSum=0,i;for(i=0;i<length;i++){thisSum+=array[i];if(thisSum<0)//如果thisSum<0表明前几个连续数之和是小于0的

thisSum=0;//需要计算新的thisSum，因此thisSum=0elseif(thisSum>maxSum)maxSum=thisSum;}returnmaxSum;}时间复杂度为O(n)方法三算法拓展1.1课程介绍1.2什么是数据结构？1.3基本概念和术语1.4算法和算法分析1.5抽象数据类型*1.6算法拓展*1.7你怎么看？目录CONTENTS“我看到老师在知识扩展环节里，有介绍STL的内容，既然STL已经实现了一些常见数据结构和算法，我们为什么还要学这门课呢？”思考：既然有了计算器，为什么还要学习数学呢？

我国由制造大国

创造强国、创新强国

一个反馈问题迈向创新精神纪录片《创新中国》/special/cxzg/sy/创新精神纪录片《创新中国》/special/cxzg/sy/创新精神工匠精神在平凡的岗位上精益求精、勇于创新，干出不平凡的业绩，就是工匠精神的体现。《庄子》中庖丁解牛、匠石运斧、老汉粘蝉等生动事例告诉人们，自古以来工匠们喜欢不断雕琢自己的产品，不断改善自己的技艺，享受着产品在双手中升华的过程。2015年，中央电视台播出《大国工匠》纪录片，讲述了24位大国工匠的动人故事。这些大国工匠令人感动的地方之一，就是他们对精度的要求。如彭祥华，能够把装填爆破药量的呈送控制在远远小于规定的最小误差之内；高凤林，我国火箭发动机焊接第一人，能把焊接误差控制在0.16毫米之内，并且将焊接停留时间从0.1秒缩短到0.01秒；胡双钱，中国大飞机项目的技师，仅凭他的双手和传统铁钻床就可产生出高精度的零部件，等等。辩证思想从算法的时间复杂度和空间复杂度分析，引出安全和效率、科技强国与乡村振兴、疫情防控与复工复产等问题，学习思考矛盾的对立统一、在一定条件下，矛盾双方可以发生相互的转换，用对立统一的辩证思想看待处理问题。进而使学生科学看待疫情防控，正确理解国家有序复工复产的决策，服从校园防疫管理等相关安排。科技强国与乡村振兴全球第一的光伏，全球第一风电，全球第二核电，全球唯二的互联网超级大国，全球最强制造大国——没有这些东西，也就没有农村光伏和“核能下乡”。“光伏+养殖+扶贫+环境改善”四位一的体良性循环。知乎软件岗位业务素养和职业道德规范

一附录：C/C++编程规范

二附录：学术诚信书

三附录：软件工程师业务素质1.3.1算法的定义及特性

四附录：软件工程师道德规范遵守编程规范，形成良好的编程风格。具有良好的职业道德和职业操守；具备较强的组织观念和集体意识。→_→word文档可双击查看

一附录：C/C++编程规范软件岗位业务素养和职业道德规范为促进优良学风建设，规范学术行为，维护学术诚信。希望同学们能保证本人所提交的作业、报告、代码、测验等均为本人创作完成，除特别注明和引用外，均