数据结构第1章试卷.ppt

JYP * 与实际测量的数据完全吻合。 JYP * 规划性能测量实验时应注意以下问题： 时钟精度、期望的测量结果精度以及与此相关的重复次数。 根据是测量最坏性能还是平均性能，生成合适的实验数据。 实验目的：是为了比较还是为了预测实际运行时间？ 当实验目的是预测实际运行时间时，人们需要通过测量数据建立t与n之间的函数关系。 JYP * 一般需用计算机生成导致一个算法最坏性能的数据集。 但在有的情况下计算机生成也非常困难。这时可根据实例特性的值随机生成足够量的实验数据，取这些数据导致的最长运行时间作为最坏性能。 生成平均性能数据更为困难，一般也采用随机生成的方法。 JYP * 1.7 C++中的模板 C++的模板（template）有效地提高了函数和类的可重用性。 模板（又称为参数化类型）是一种能被实例化为任何数据类型的变量，这些类型既包括C++基本类型又包括用户定义的类型。 模板函数: template class KeyType int seqsearch (KeyType *a, const int n, KeyType x ) { int i=n; a[0]=x; while (a[i] != x) i--; return i; } JYP * 通过调用seqsearch，可以很容易地在字符数组或浮点数数组中查找元素: char carray[200]; float farray[300]; char x = ’r’; float y = 306.523; … // 设此时以上数组已完成初始化 seqsearch(carray, 200, x); seqsearch(farray, 300, y); 函数seqsearch的KeyType在调用时被实例化为相应的实参类型，例如，调用seqsearch(farray, 300, y)表示在浮点数数组farray中查找浮点数y。 JYP * seqsearch使用操作符“!=”比较两个KeyType对象，使用操作符“=”将一个KeyType对象赋值给另一个KeyType对象。 对于用户定义的数据类型，这些操作不可能由系统预定义。用户必须重载这些操作以实现新的语义。 JYP * 模板类： template class Type class Bag { public: Bag ( int MaxSize = DefaultSize ); // 假设DefaultSize已定义 int Add (const Type x ); // 将对象x加入容器中 int Delete (const int k ); // 从容器中删除并打印k 个对象 private: int top; // 指示已用空间 Type *b; // 用数组b存放Type对象 int n; // 容量 }; JYP * template class Type BagType::Bag ( int MaxSize = DefaultSize ):n(MaxSize) { b = new Type[n]; top = -1; } template class Type int BagType::Add (const Type x) { if (top = = n) return 0; // 返回0表示加入失败 else {b[++top] = x; return 1;} } JYP * template class Type int BagType::Delete (const int k) { if (top + 1 k ) return 0; // 返回0表示容器内元素不足k // 个，删除失败 else { for (int i = 0; i k; i++) cout b[top – i] “ ” ; top = top - k; return 1; } } Bagfloat f; BagCircle c; 于是，Bag对象f存放浮点数，c存放圆。 JYP * 1.8 效率与权衡 时间和空间的权衡； 通用性和效率的权衡； 开发效率与运行效率的权衡； 等等。 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金