数据结构与算法-C++实现PPT第一章 绪论

数据结构第一章绪论本章的内容与目标课程基本情况数据结构的研究对象与基本概念算法与算法分析课程基本情况学习目标——学会编程掌握基本的数据结构培养算法设计能力、程序设计能力

提问：利用计算机求解问题的实质是什么？数据表示：将数据存储在计算机中数据处理：处理数据，求解问题培养算法分析和评价的能力评价算法、改进算法学习难度——难课程基本情况能力培养理论课程工程知识：学习和运用计算机科学知识和建模方法推演、分析实际工程问题。问题分析：认识到计算机领域的工程问题有多种解决方案可以选择，并结合文献查阅及研究，比较、寻求可替代的解决方案。现代工具：了解计算机专业的主要算法和信息检索工具的原理和方法，并理解其局限性。社会责任：能分析和评价计算机工程实践和复杂工程问题解决方案对社会、健康、安全、法律以及文化的影响，以及这些制约因素对项目实施的影响，并理解计算机专业工程实践应承担的社会责任。课程基本情况能力培养课程设计问题分析：能够从工程科学的角度，结合文献查阅及研究，对计算机领域复杂工程问题的解决方案，分析影响因素，并获得有效结论。环境可持续：知晓和理解环境保护和可持续发展的理念和内涵，正确认识计算机科学技术的发展与环境和可持续发展的关系。个人与团队：理解个人在团队中的角色划分，能够组织、协调和指挥团队开展工作。课程基本情况考核方式：平时30%，包括考勤(6分)、作业及实验(20分)和课堂参与(6分)考试70%，闭卷考试，难度不低于考研试题考试题型：以能力训练型题目为主实验必做题目：顺序表、单链表、二叉树、图，随课堂进度完成考核标准：速度+完成质量课程设计：分组，每组1题，课程设计周完成课程基本情况课程性质数据结构是计算机课程体系中最核心的课程之一承前启后前导课：高等数学、程序设计语言、离散数学后续课：数据库、操作系统……属于武术中的“练功”科目学完C++以后，很多同学感觉“能考试，不能编程”“练武不练功，到头一场空”“编程秘籍”就业、考研、职场生涯课程基本情况确保取得好成果的方法：请认真上课，投入时间和注意力，认真看书和课件把握上机实验的机会，认真练习上机分组，自由组合，5-6人一组。通过同组讨论的方法解决问题认真对待作业，严禁雷同

作业分两类：个人完成的作业：每章交一次

1次启发式作业：鼓励组内讨论、自主完成实际动手编程能力远比逻辑层面的理解要重要得多！！！课程基本情况C++编译环境VC6.0，与新操作系统不兼容，在字符串等操作有缺陷visualstudio,容量大,对java支持不佳Codeblocks,推荐,小型编译系统,对java支持不佳Netneans(/downloads/),java环境，c++需配合cygwin(/)

eEclipse,

java环境，c++需配合mingw第一次课堂参与自学模板的内容要求：下周三请一位同学主讲，其他同学补充主讲的同学要准备PPT，其他同学可以不准备要能让同学们理解模板的用途、原理和使用方法请自荐或者推荐一位同学作为主讲数据结构的兴起与发展数据结构的创始人——DonaldKnuth

1938年出生，25岁获得加州理工学院数学系博士学位。30岁任斯坦福大学计算机系教授。31岁，经典巨著TheArtofComputerProgramming第一卷出版他计划共写7卷，到1973年第三卷出版时已经震惊世界，36岁获得图灵奖。之后致力于对排版技术进行改造，结果就是对整个西文印刷行业带来革命性变革的TEX排版和METAFONT字型设计系统2008年，第四卷《组合算法》出版“如果你认为你是一名优秀的程序员，就去读第一卷，如果你可以读懂整套书，请发一份简历给我”——比尔盖茨数据结构的兴起与发展数据结构的发展阶段无结构阶段结构化阶段：数据结构＋算法＝程序面向对象阶段：（数据结构＋算法）＝程序……数据结构的研究对象计算机求解问题的一般步骤？

问题→想法→算法→程序→求模型的解待求解问题的分类

数值问题→数学方程

非数值问题→数据结构数据结构的研究对象例1-1：用计算机来实现学籍管理—表序号姓名球队状态能力1乔帮主公牛正常1002闪电侠热火伤病973魔术师湖人停赛99……………问题：学籍管理中，对这张表进行的运算或处理有哪些？以你现在所学，如何在计算机中存储一行元素？学号的作用是什么？数据结构的研究对象例1-2：人机对弈—树结构…………..……..………...……问题1：树结构的元素关系与表结构的元素关系有什么区别？问题2：如何在计算机中存储一个局面？数据结构的研究对象例1-3城市间交通网—图问题1：图结构的元素关系与树结构的元素关系有什么区别？

北京纽约巴黎伦敦东京墨西哥北京

10982124纽约109

55108巴黎82

397伦敦553

89东京10897

113墨西哥12489113

墨北纽伦东巴109108113821245597389问题2:以你目前所学，如何在计算机里存储一条边？数据结构的基本概念数据结构的定义

数据结构是研究非数值问题中计算机的操作对象以及它们之间的关系和操作的学科数据：所有能输入到计算机中并能被计算机程序识别和处理的符号集合数值数据：整数、实数等非数值数据：图形、图象、声音、文字等数据结构的基本概念数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理

例：学籍登记表中的一行，一个棋盘格局、一门课程数据项：构成数据元素的不可分割的最小单位例：学生的学号、姓名等属性数据对象：具有相同性质的数据元素的集合数据结构的基本概念例1-1：用计算机来实现学籍管理—表数据元素？数据项？数据对象？序号姓名球队状态能力1乔帮主公牛正常1002闪电侠热火伤病973魔术师湖人停赛99……………数据结构的基本概念例1-2：人机对弈—树结构…………..……..………...……数据元素？数据项？数据对象？数据结构的基本概念例1-3城市间交通网—图数据元素？数据项？数据对象？墨北纽伦东巴109108113821245597389数据结构的基本概念数据对象、数据元素、数据项之间的关系包含关系：数据对象是由数据元素组成，数据元素是由数据项组成数据元素是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。数据结构的基本概念数据结构：相互之间存在一定关系的数据元素的集合按照视点的不同，数据结构分为逻辑结构和存储结构逻辑结构：指数据元素之间逻辑关系的整体存储结构：又称为物理结构，是数据及其逻辑结构在计算机中的表示数据结构的基本概念数据的逻辑结构集合：数据元素之间的关系仅仅就是“属于同一个集合”，没有其他关系线性结构：数据元素之间存在着一对一的线性关系数据结构的基本概念数据的逻辑结构树结构：数据元素之间存在着一对多的层次关系图结构：数据元素之间存在着多对多的任意关系数据结构的基本概念数据的存储结构顺序存储：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。……起始地址例:（,,）数据结构的基本概念数据的存储结构顺序存储：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。链接存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。0200020803000325…………例:（,,）02000325∧数据结构的基本概念逻辑结构与存储结构的关系数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是面向计算机的。同种逻辑结构的数据可以用多种存储结构来存储；而采用不同的存储结构，其数据处理的效率往往是不同的。数据结构的访问接口对数据结构的访问是指对数据的读取、修改、加工、处理等操作。数据结构的基本操作：各种应用都能通过这些操作实现对数据结构的各种访问。

访问接口：操作的调用形式与规范（例如形参表、返回类型等）。数据结构的访问接口：数据结构基本操作接口的全体。数据结构的基本概念数据结构的基本概念抽象数据类型的概念数据类型（DataType）：一组值的集合以及定义于这个值集上的一组操作的总称。例如：C++中的整型，实型变量抽象（Abstract）:抽出问题本质的特征而忽略非本质的细节例如：地图、汽车模型抽象数据类型（AbstractDataType，ADT）:一个数据结构以及定义在该结构上的一组操作的总称数据结构的基本概念ADT是一种用户定义的数据类型，其运算指明了用户如何对数据进行操作C++语言使用类Class来表示抽象数据结构设计ADT的基本思想数据结构的基本概念ADT的一般形式数据结构的基本概念ADT的例子ADT名：球星Data:描述数据的结构姓名，年龄，球队，各项能力，…Operation：描述数据的行为

操作1：构造操作2：析构操作3：踢球操作4：转会操作5：受伤……EndADT算法与算法分析算法（Algorithm）:是对特定问题求解步骤的一种描述，是指令的有限序列。算法的五大特性输入：一个算法有零个或多个输入。输出：一个算法有一个或多个输出。有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。算法与算法分析算法评价——“好”算法的要求正确：对于合法的输入，得到正确的结果鲁棒性：算法的健壮程度。异常输入情况下算法的表现简单性：算法容易理解和实现抽象分级：可读性，便于理解。用模块化方法实现算法高效性：尽可能减少算法的时间效率和空间效率算法与算法分析算法描述方法自然语言流程图程序设计语言伪代码UML例：需要在给定序列中查找指定元素key——折半查找算法算法与算法分析自然语言描述：粗线条地描述算法思想优点：便于阅读和理解缺点：冗长、二义性注意事项：避免写成自然段例：折半查找的自然语言描述Step1.用待查值key和序列的中间值m进行比较，若想等，则查找成功Step2.如果待查值比中值大，则在中值的右半区继续进行折半查找Step3.否则在中值的左半区继续进行折半查找。算法与算法分析流程图优点：流程直观缺点：严密性、灵活性不足；不适用于复杂算法算法与算法分析程序设计语言优点：能由计算机执行缺点：抽象性差，对语言能力要求高注意：将算法写成子函数算法与算法分析伪代码Pseudocode

介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计表达能力强，抽象性强，容易理解，类似自然语言伪代码并没有严格的规则，常用“缩进”表示分支结构，常用连续的数字或字母来标示同一即模块中的连续语句算法与算法分析UML统一建模语言（UnifiedModelingLanguage）UML是描述、构造和文档化软件系统的可视化语言。作用:建立软件模型建模语言:提供交流的词汇和规则可视化:通过标准图符构成图形来描述模型通用标准:成为软件建模的标准语言,并且在其他领域也得到应用。UML不属于本课程范畴，本课程仅使用简单类图和活动图UML的学习对于将来掌握软件工程，向系统架构师发展很有好处

算法与算法分析UML结构UML构造块物件结构物件行为物件分组物件注解物件关系关联依赖泛化实现图类图顺序图对象图协作图构件图状态图部署图活动图用例图公共机制规格说明修饰公共分类扩展机制架构用例视图逻辑视图进程视图实现视图部署视图算法与算法分析活动图的要素折半查找的活动图算法与算法分析算法分析的方法事后统计：将算法实现，测算其时间和空间开销。

缺点：⑴编写程序实现算法花费较多的时间精力⑵测试结果依赖于计算机软硬件等环境因素事前分析：对算法所消耗资源的一种估算方法算法分析（AlgorithmAnalysis）：对算法所需要的计算机资源——时间和空间进行估算时间复杂度（TimeComplexity）空间复杂度（SpaceComplexity）算法与算法分析时间复杂度度量算法执行的时间长短，一般是问题规模n的函数算法的执行时间＝每条语句执行时间之和执行次数×执行一次的时间

指令系统、编译的代码质量因此，算法的时间复杂度是用基本语句的执行次数来描述的,记作T(n)哪个因素是由算法决定的？执行次数算法与算法分析例3：for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;例1：x++;例2：for(i=1;i<=n;i++)x++;如果程序由这三条语句组成，则总执行次数为：T(n)=n2+n+1算法与算法分析渐进复杂度估算：考虑影响算法效率的最主要的因素，忽略次要因素随着n的增加，最主要影响算法效率的因素是算法与算法分析算法分析的标记——大O符号当问题复杂度n增加时，运算所需时间、空间代价T(n)的上界注意:来源于Orderof……里的O，绝对不是0定义：若存在两个正常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n))问题的规模n：或大小。如：矩阵的阶数、图的结点个数、正整数个数……上述定义表明，如果对于足够大的(大于某自然数n0)的n

，存在正数c，使T(n)不大于c×f(n)

，则T

是f的大O符号。算法与算法分析定义：若存在两个正常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n))注意：1、对与同一对T(n)和f(n)，

c和n0通常有多个取值2、只说明存在c和n0，但并不关心如何得到c和n0，也不关心如何在多组取值中选择3、唯一关心的是：如何描述算法复杂程度的数量级别：最简形式的f(n)：单项且无常数算法与算法分析复杂度分析中的简化原则

—专注引起复杂度变化的最显著因素忽略常量

忽略所有复杂度属于低数量级的项

算法与算法分析例：某算法执行基本操作次，则略去常量忽略复杂度较低的项定理：若A(n)=amnm+am-1nm-1++a1n+a0是一个m次多项式，则A(n)=O(nm)算法与算法分析算法分析算例，求下列算法的复杂度例1-5：++x;例1-6：for(i=0;i<n;i++)++x;基本语句：，执行次数：基本语句：，执行次数：例1-7：for(i=0;i<n;i++)for(j=0;j<n;j++)++x;基本语句：，执行次数：算法与算法分析例1-8：for(i=0;i<n;i++)for(j=0;j<n;j++){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];