文档介绍：?网络游戏算法设计?第2章算法分析与数据结构主要内容:学习目标: ?第2章算法分析与数据结构?算法描述?数据抽象?算法复杂度的计算?了解算法描述?了解数据抽象?掌握算法复杂度的计算重点:难点: ?第2章算法分析与数据结构?算法复杂度的计算?算法复杂度的计算第2章算法分析与数据结构使用计算机解决实际问题的过程,就是分析问题涉及的数据、合理组织数据以及规划解决问题的算法的过程。在计算机科学的发展过程中,分析、组织数据和规划算法被单独成一个学科,这就是数据结构。数据结构在计算机科学技术中,尤其是在网络游戏程序设计中起到了举足轻重的作用。数据结构是网络游戏开发的核心知识之一,是许多后续内容的重要基础。第2章算法分析与数据结构 算法描述算法是一组有穷的规则,它们规定了解决某一特定类型问题的一系列运算,是对解题方案的准确与完整的描述。算法的描述方法可以归纳为以下 4种: 1)自然语言; 2)图形,如 NS 图、流程图,图的描述与算法语言的描述对应; 3)算法语言,即计算机语言、程序设计语言、伪代码; 4)形式语言,用数学的方法,可以避免自然语言的二义性。第2章算法分析与数据结构 数据抽象数据抽象类型给出了一种用户定义的数据类型,其运算符指明了用户如何操作数据,数据抽象类型与具体应用无关,这可使程序员把注意力集中在数据及其操作的理想模型上。 class Cirle { public: Cirle(float r) { m_Radii = r; } float Area(); // 计算圆面积 float Cirumference(); // 计算圆周长 private: float m_Radii; }; 第2章算法分析与数据结构 算法复杂度的计算 空间复杂度程序所需要的空间主要由指令空间、数据空间、环境栈空间构成。?指令空间指令空间是指用来存储经过编译之后的程序指令所需的空间。程序所需要的指令空间的数量取决于如下因素: 1)把程序编译成机器代码的编译器; 2)编译时实际采用的编译器选项; 3)目标计算机。第2章算法分析与数据结构 算法复杂度的计算?数据空间数据空间是指用来存储所有常量和所有变量值所需的空间。数据空间包括: 1)存储常量和简单变量所需要的空间 2)存储复合变量所需要的空间。这一类空间包括数据结构所需的空间及动态分配的空间。 int i = 4, j = 5; int iArray[256]; 第2章算法分析与数据结构 算法复杂度的计算对于简单变量和常量来说,所需要的空间取决于所使用的计算机和编译器,以及变量与常量的数目。对于一个结构变量,可以把它的每个成员所占用的空间累加起来即可得到该变量所需要的内存。 double a[100]; int maze[rows][cols]; 数组 a 需要的空间为 100 个 double 类型元素所占用的空间,若每个元素占用8个字节,则分配给该数组的空间总量为 800 字节。数组 maze 有 rows * cols 个 int 类型的元素,它所占用的总空间为 4* rows * cols 字节。第2章算法分析与数据结构 算法复杂度的计算?环境栈空间环境栈用来保存函数调用返回时恢复运行所需要的信息。每当一个函数被调用时,下面的数据将被保存在环境栈中: 1)返回地址; 2)函数被调用时所有局部变量的值以及传值形式参数的值(仅对于递归函数而言); 3)所有引用参数及常量引用参数的定义。