数据结构与算法1.pptVIP

数据结构与算法;Chapter 1;Section1 数据结构讨论的范畴;计算机程序设计的两大要素;计算机如何解题;计算机解题的步骤;计算机的两大应用领域;数值计算;例1-1： 鸡兔同笼问题;非数值计算;例1-2 图书数目检索;;例1-3 人机对弈;;例1-4： 多叉路口的交通灯管理问题;A;AB;数据结构研究现实问题的数学模型（非数值计算）及其上的算法在计算机中的表示和实现。 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。 数据结构是一门不断发展的核心学科，随着计算机处理的非数值计算问题越来越广泛、深入和复杂，数据结构需要研究越来越复杂的结构和算法。　　;Section 2 基本概念;基本术语;example;数据结构的定义;数据结构的类型;逻辑结构;集合;线性结构;树形结构;※树和图统称“非线性结构”;数据的存储结构;顺序存储结构;链接顺序结构;数据的逻辑结构和物理结构是密切相关的两个方面。一般地，一种数据的逻辑结构根据需要可用多种物理结构来存储，而采用不同的物理结构，其数据处理的算法及其效率往往是不同的。 算法的设计取决于选定的逻辑结构 算法的实现依赖于采用的物理结构 ;数据结构的运算;Section 3 数据抽象和抽象数据类型;数据抽象和抽象数据类型;Example;Abstract Data Type;　ADT 抽象数据类型名 is DataObject: 数据对象描述 Relation?: 关系描述 Operation?: 操作声明 End 抽象数据类型名 在面向对象语言中，ADT可用“类”来实现，其中的操作用“方法”（C++中称为“成员函数”）实现。;复数运算的构造方法;#include stdio.h #include stdlib.h typedef struct complex { float x,y; }complex; Complex CreateComp(float x, float y) { Complex c; c.x=x; c.y=y; return c; } Complex Add(Complex a, Complex b) { Complex c; c.x=a.x+b.x; c.y=a.y+b.y; return c; } ;Void PrintComplex(Complex a) { printf(“%3.2f+%3.2fi\n”,a.x,a.y); } Void main() { Complex a,b,c; a=CreateComp(1.0f,2.0f); b=CreateComp(3.0f,4.0f); c=Add(a,b); PrintComplex(a); PrintComplex(b); PrintComplex(c); };Section 4 算法和算法分析;算法和算法分析;算法的特征;算法的描述;算法和程序的主要区别;软件开发过程;本课程的要求;算法评价的标准;时间复杂度;例1-5　 算法: 两数交换 　 s=a; 　//1次 　a=b;　 //1次 　b=s;　　//1次 　 ∴T(n)=３;例1-7 算法: 矩阵相加 　 for(i=0;in;i++) 　 //n+1次 　 for(j=0;jn;j++)　 //n(n+1)次 　 c[i][j]=a[i][j]+b[i][j]; 　//n*n次 　 ∴T(n)=2n2+2n+1;渐进时间复杂度;例1-8 算法: 矩阵相乘 void mult(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) ;例1-9 算法：选择排序 void select_sort(Type a[],int n) //将数组a中的数值序列排列成小→大的有序序列 { 　for(i=0;in-1;i++){ //n