数据结构与算法

数据结构与算法第1页，课件共58页，创作于2023年2月Chapter1第2页，课件共58页，创作于2023年2月Section1数据结构讨论的范畴第3页，课件共58页，创作于2023年2月计算机程序设计的两大要素程序=数据结构+算法程序→为计算机解题而编写的一组指令集数据结构→问题的数学模型算法→处理问题的策略（计算的方法）第4页，课件共58页，创作于2023年2月计算机如何解题要处理的现实问题怎么表示？即怎样用数学形式（函数、公式、符号）抽象地表示现实问题？也就是问题的数学模型是什么？这就是数据结构要讨论的问题。怎样对问题进行信息处理？也就是处理问题的策略是什么？这就是算法要讨论的问题。第5页，课件共58页，创作于2023年2月计算机解题的步骤从现实问题中抽象出一个具体的数学模型设计一个解此数学模型的合适算法使用某种编程语言将算法“翻译”成程序并调试正确通过多方位的测试，使程序投入实际运行，即使问题获得目标结果第6页，课件共58页，创作于2023年2月计算机的两大应用领域数值计算（科学与工程计算）数据：数值数据计算：解方程（组）、函数求值、概略统计、运筹等非数值计算（逻辑计算/数值处理）数据：文字、符号、表格、图象、声音、视频等计算：比较、归类、统计、查找、排序、转换以及传输等第7页，课件共58页，创作于2023年2月数值计算对于数值计算问题的解决方法，主要是用各种数学方程建立数学模型，例如：天气预报的数学模型为二阶椭圆偏微分方程，预测人口增长的数学模型为常微分方程。求解这些数学方程的方法是计算数学（数值分析）研究的领域，例如差分算法、有限元算法、无限元算法等。第8页，课件共58页，创作于2023年2月例1-1：鸡兔同笼问题数学模型算法二元一次方程如：x+y=m2x+4y=n(m≥2,n≥6且n%2=0)枚举法for(x=1;x<=m-1;x++)for(y=1;y<=m-1;y++)if((x+y==m)and(2*x+4*y==n)){print(“鸡＝”x”,兔子＝”y)；

break;}第9页，课件共58页，创作于2023年2月非数值计算当今计算机能够处理的应用问题90%以上是非数值计算问题——包括数据的比较、归类、统计、查找、排序、转换以及传输等。而绝大多数非数值计算问题是无法用数学方程式来描述的，它们需要使用特定的离散数学模型，如线性表树图这些模型及其算法就是数据结构学科所要研究的内容。第10页，课件共58页，创作于2023年2月例1-2图书数目检索数学模型：各种书目表（线性结构）书目信息如：书名、作者、出版社、出版日期、书号、分类号、内容提要等。问题：如何表示和组织书目信息？算法：按照某个特定要求（如给定书名）对相关书目表进行查询的方法。第11页，课件共58页，创作于2023年2月001数据结构张山清华出版社T01……002高等数学李司高教出版社S01……003数据结构王武清华出版社T02……004经济学原理马鲁三联出版社J01……………………………

……

数据结构001,003,…高等数学002,……经济学原理004,………………张山001,023李司002,…王武003,……………图1-1书目表示例T001,003…S002…J004…………第12页，课件共58页，创作于2023年2月例1-3人机对弈数学模型：对弈树（树结构）问题：如何表示、组织棋盘和棋子信息，如何表示、组织并保存动态变化的棋局状态（格局）算法：对弈／走棋操作的算法——使格局发生变化，由一种格局派生出另一种格局，并从多种可选路径中选择一种最优／合理路径，最后达到输／赢状态第13页，课件共58页，创作于2023年2月图1-2井字棋对弈树的局部

井字棋游戏的规则：从一个空的棋盘开始，白子先行，轮流走棋。判定胜负的标准是：三枚同色棋子占据了一横行或一竖行或一对角线，则获胜；如果直到棋盘被占满时还没有一方获胜，则为和局。第14页，课件共58页，创作于2023年2月例1-4：多叉路口的交通灯管理问题目标：如何保证多叉路口的交通畅通有序，并使交通流量达到最大，且不会发生交通事故，数学模型：通路状态图（图／网结构）需解决的问题：①当某一条通路通行时，有哪些通路不能同时通行？②当某一条通路通行时，有哪些通路可同时通行？③如何表示和组织通路状态信息？算法：结点的动态分组着色（绿色）策略，相邻结点不能同时为绿色。第15页，课件共58页，创作于2023年2月ABCDE可通路非通路

A→B:BCBDDAEA

A→C:BDDADBEAEBA→D:EAEBECB→A:B→C:ABDBEBB→D:ACDAECD→A:ABACBDEBD→B:ACBCECD→C:E→A:ABACADE→B:ACADBCBDDAE→C:ADBDDBE→D:图1-3五叉路口示意图第16页，课件共58页，创作于2023年2月ABACADDCBABCBDEBEDEADADBEC每个结点代表一条通路；不能同时通行的结点用一条连线连接(相邻）；相邻结点用不同颜色标记，表示不能同时通行；相同颜色的结点表示这些通路可同时通行。孤立结点表示任何时候都可以通行，恒为绿色。图1-4通路状态图第17页，课件共58页，创作于2023年2月数据结构研究现实问题的数学模型（非数值计算）及其上的算法在计算机中的表示和实现。数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。数据结构是一门不断发展的核心学科，随着计算机处理的非数值计算问题越来越广泛、深入和复杂，数据结构需要研究越来越复杂的结构和算法。第18页，课件共58页，创作于2023年2月Section2基本概念第19页，课件共58页，创作于2023年2月基本术语数据（Data）客观事物的符号表示，是计算机可操作的对象。所有能被输入到计算机中并被计算机程序处理的符号的总称。信息在计算机中的表示。数据元素（DataElement）数据中的一个“个体”，数据结构中讨论的基本单位。一个数据元素也可以由一个或若干个数据项（DataItem）组成。数据项是有意义的数据的最小原子单位。数据对象（DataObject）性质相同的数据元素的集合。第20页，课件共58页，创作于2023年2月example数据对象数据元素数据项整数集单个整数单个整数（不可再分）复数集单个复数实部，虚部学生档案单个学生记录多个数据项（学号、姓名、性别等）第21页，课件共58页，创作于2023年2月数据结构的定义带结构的数据元素的集合/带结构的数据对象。这里的结构是指数据元素之间的某种约束关系，即数据结构中讨论的数据元素都不是孤立的，而是相互之间必定存在着一定的关系。相互之间存在一种或多种特定关系的数据元素的集合。关系决定了结构。对于同样的数据元素，不同的关系将构成不同的结构。第22页，课件共58页，创作于2023年2月数据结构的类型逻辑结构（LogicalStructure）存储结构（StorageStructure）第23页，课件共58页，创作于2023年2月逻辑结构“数据结构”通常指的只是数据的逻辑结构，它描述的是数据元素之间的逻辑关系，即数据元素之间固有的（内在的）、本质的联系，它们反映在人们的概念上，是抽象的，与物理的计算机无关。集合结构线性结构树形结构图状结构第24页，课件共58页，创作于2023年2月集合结点之间不存在关系，或说仅仅存在“同属一个数据对象”的关系。第25页，课件共58页，创作于2023年2月线性结构元素（结点node）之间存在线性关系／1:1关系；除首结点外，每个结点有且只有一个前驱；除尾结点外，每个结点有且只有一个后继。首结点尾结点第26页，课件共58页，创作于2023年2月树形结构结点之间存在层次关系／1:n关系；除根结点无前驱外，每个结点有且只有一个前驱，但任一结点可以有0~n个后继。

根结点第27页，课件共58页，创作于2023年2月※树和图统称“非线性结构”结点之间存在任意关系／n:m关系：可以存在没有前驱的结点或和没有后继的结点，其他的每个结点则可以有多个前驱，也可以有多个后继。（在图中，元素也称作“顶点”）

网状结构（图）第28页，课件共58页，创作于2023年2月数据的存储结构是逻辑结构在计算机存储器中的映象(image)。即逻辑结构在计算机中的表示顺序存储结构链接存储结构第29页，课件共58页，创作于2023年2月顺序存储结构通过数据元素在存储器中的一个固定的相对位置来表示元素之间的前驱或后继关系。采用顺序映象的物理结构称作顺序结构。a0a1a2a3102104106108第30页，课件共58页，创作于2023年2月链接顺序结构通过在元素的存储单元中附加“指针”的方式来表示前驱或后继关系。采用链式映象的物理结构称作链式结构。a0a1a2a3first第31页，课件共58页，创作于2023年2月数据的逻辑结构和物理结构是密切相关的两个方面。一般地，一种数据的逻辑结构根据需要可用多种物理结构来存储，而采用不同的物理结构，其数据处理的算法及其效率往往是不同的。算法的设计取决于选定的逻辑结构算法的实现依赖于采用的物理结构第32页，课件共58页，创作于2023年2月数据结构的运算数据结构常见的运算创建运算清除运算插入运算删除运算搜索运算更新运算访问运算遍历运算第33页，课件共58页，创作于2023年2月Section3数据抽象和抽象数据类型第34页，课件共58页，创作于2023年2月数据抽象和抽象数据类型数据类型是一个值的集合和定义在这个集合上的一组操作的总称数据类型是高级程序设计语言所定义的某类数据的集合和定义在该集合上的一组原操作的总称。原操作是指可对集合中的数据元素进行的运算，其算法已由语言系统或计算机硬件实现，并用特定的符号（运算符）表示。

数据类型＝集合＋原操作集第35页，课件共58页，创作于2023年2月Example整形数据类型（int）值的范围：-232~232-1（-32768~32767）元素映像：4字节存储单元算数运算：+,-,×,/关系运算：<,>,<=,>=,!=,==赋值运算：=第36页，课件共58页，创作于2023年2月AbstractDataType抽象数据类型（ADT）是数据类型的扩展或是广义的数据类型，它可定义各种类型的逻辑数据结构，包括线性表、树、图等。抽象数据类型是一个数据结构和定义在这个数据结构上的一组操作的总称。ADT=数据结构＋操作集这里的“操作”非原操作，需要自定义。ADT可用一个三元组表示：ADT=(D,R,P)D—数据对象，R—D上的关系集，P—对D的基本操作集第37页，课件共58页，创作于2023年2月

ADT<抽象数据类型名>isDataObject:

<数据对象描述>Relation

:

<关系描述>Operation

:

<操作声明>End<抽象数据类型名>在面向对象语言中，ADT可用“类”来实现，其中的操作用“方法”（C++中称为“成员函数”）实现。ADT的定义格式第38页，课件共58页，创作于2023年2月复数运算的构造方法ADT1-1Complexe{

数据：由一对实数（x,y）构成

运算：两个复数分别为a（a1,a2）和b（b1,b2） ComplexCreateComp(floatx,floaty)%构造复数 ComplexAdd(Complexa,Complexb)%求和 ComplexSub(Complexa,Complexb)%求差 ComplexMul(Complexa,Complexb)%求积 ComplexDiv(Complexa,Complexb)%求除数 }第39页，课件共58页，创作于2023年2月#include<stdio.h>#include<stdlib.h>typedefstructcomplex{ float

x,y;}complex;ComplexCreateComp(floatx,floaty){ Complexc; c.x=x;c.y=y; returnc;}ComplexAdd(Complexa,Complexb){ Complexc; c.x=a.x+b.x;c.y=a.y+b.y; returnc;}程序1-1Complex的实现第40页，课件共58页，创作于2023年2月VoidPrintComplex(Complexa){ printf(“%3.2f+%3.2fi\n”,a.x,a.y);}Voidmain(){ Complexa,b,c; a=CreateComp(1.0f,2.0f); b=CreateComp(3.0f,4.0f); c=Add(a,b); PrintComplex(a); PrintComplex(b); PrintComplex(c);}程序1-2测试复数加法运算第41页，课件共58页，创作于2023年2月Section4算法和算法分析第42页，课件共58页，创作于2023年2月算法和算法分析算法（Algorithm）是求解特定问题的方法，它是指令的有限序列。算法是对特定问题求解步骤进行描述的一组指令集。这里的“指令”不是指计算机的机器指令，它可以是高级语言的一条或多条语句，也可以是伪码语句，或用自然语言编写的操作命令。第43页，课件共58页，创作于2023年2月算法的特征输入输出确定性能行性有穷性第44页，课件共58页，创作于2023年2月算法的描述算法不是程序，而是实现程序的方法（模型），设计算法也称程序建模。自然语言：容易，但不简洁和严谨、有二义性。流程图：算法逻辑直观清晰，但转换成高级语言程序需要一定的开销。如程序流程图、N-S图、UML活动图。伪码语言（算法语言）：介于自然语言和高级程序设计语言之间，保留了高级语言的语法骨架，但对具体语法和语法细节不做非常详尽的要求，如忽略变量定义和输入/出格式等。特点是简洁、易读、严谨、易被转换成高级语言。流行的如PDL等。高级语言：开销大，不灵活，不符合软件工程思想，不是现代软件设计风格。第45页，课件共58页，创作于2023年2月算法和程序的主要区别程序不一定满足有穷性，可以出现有意义的无穷循环；算法则必须满足有穷性。程序中的指令必须是机器可执行的；而算法中的指令则无此限制，算法只是程序的模型。设计算法是软件开发过程中详细设计阶段的工作，由高级程序员完成；编程的实质是算法的编程语言翻译，是编码阶段的工作，由普通程序员完成。第46页，课件共58页，创作于2023年2月软件开发过程

系统分析员系统设计员高级程序员程序员系统测试员需求分析概要设计详细设计编码测试设计ADT是概要设计阶段的工作，由系统设计员完成；算法设计是详细设计阶段的工作，由高级程序员完成；用编程语言编程则是编码阶段的工作，由程序员完成。第47页，课件共58页，创作于2023年2月本课程的要求

系统设计员——设计ADT

高级程序员——设计算法

程序员——编写C++程序并上机调试测试员——找程序的毛病

第48页，课件共58页，创作于2023年2月算法评价的标准正确性：算法的运行结果应当满足系统需求。一个算法的正确性必须通过测试才能验证健壮性：是指一个算法对不合理数据输入的反映和处理能力。当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名其妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误性质的值，以便在更高的抽象层次上进行处理。可读性：算法是写给其他人（程序员、测试人员及维护人员）看的！！效率：包括时间性和空间性，即运行该算法程序所需花费的时间和占用存储空间的大小。对于同一个问题如果有多个算法可以解决，运行时间短的算法效率高，这是评价算法效率最主要的度量。第49页，课件共58页，创作于2023年2月时间复杂度时间复杂度是指程序运行从开始到结束所需的时间一个算法的时间复杂度是该算法中各条原指令的重复执行次数之和，记为T(n)，它是问题规模n的函数，与问题规模成正比。算法的执行时间=Σ[语句(i)的执行次数*语句(i)的执行时间]问题规模是指算法对求解问题所要处理的数据量。例如，求100以内还是10000以内的素数，就说后者规模比前者大。第50页，课件共58页，创作于2023年2月例1-5

算法:两数交换

s=a;

//1次

a=b;

//1次

b=s;

//1次

∴T(n)=３例1-6算法:求累加和

s=0;//1次

for(i=0;i<n;i++)//n+1次

s+=a[i];

//n次

∴T(n)=2n+2第51页，课件共58页，创作于2023年2月例1-7

算法:矩阵相加

for(i=0;i<n;i++)

//n+1次

for(j=0;j<n;j++)

//n(n+1)次

c[i][j]=a[i][j]+b[i][j];

//n*n次

∴T(n)=2n2+2n+1第52页，课件共58页，创作于2023年2月渐进时间复杂度一个算法的时间复杂度的计算是比较繁琐的，特别对于较复杂的算法更是如此。实际上，一般也没有必要精确地计算出算法的时间复杂度，只要大致计算出相应的数量级／阶（order）即可。假如，随着问题规模n的增长，时间复杂度的增长率和某个函数f(n)的增长率相同；换言之，当n→∞时，T(n)与f(n)同阶无穷大且f(n)是T(n)的上界，则可记作：T(n)=O(f(n))并称T(n)为为算法的渐进时间复杂度（通常也简称为时间复杂度），其值用大O表示。第53页，课件共58页，创作于2023年2月例1-8

算法:矩阵相乘voidmult(inta[],intb[],int&c[]){//以二维数组存储矩阵元素，c为a和b的乘积 for(i=1;i<=n;++i) \\n+1 for(j=1;j<=n;++j) \\n(n+1) { c[i,j]=0; \\n2 for(k=1;k<=n;++k) \\n2(n+1) c[i,j]+=a[i,k]*b[k,j]; \\n3 }}∴T(n)=2n3+3n2+2n+1∴渐进时间复杂度：O(n3)第54页，课件共58页，创作于2023年2月例1-9算法：选择排序voidselect_sort(Typea[],intn)//将数组a中的数值序列排列成小→大的有序序列{

for(i=0;i<n-1;i++){//n-1

min=i;

/