第2章 向量

  • 格式:pdf
  • 大小:514.71 KB
  • 文档页数:40

2010-3-15
福州大学数学与计算机科学学院
20
算法与数据结构
Algorithms and Data Structures
如何表示和存放大整数呢
• 在利于编程实现,同时便于提高运算效率的基础 上选择数据结构 – 在数据结构上的一个小改进对效率的提高有时 会有很大帮助的。而数据结构在一定程度上是 可以弥补算法的不足的。 • 基本的思想 – 用数组存放和表示大整数。一个数组元素,存 放大整数中的一位。
2010-3-15
福州大学数学与计算机科学学院
4
算法与数据结构
Algorithms and Data Structures
const修饰指针的情况
• • • • • const int* a = & [1] int const *a = & [2] int* const a = & [3] const int* const a = & [4] 具体参考CSDN文章:Const用法小结
福州大学数学与计算机科学学院 3
2010-3-15
算法与数据结构
Algorithms and Data Structures
2.3 向量的迭代器
• 向量的数据模型是由类型为T的元素组成的一个序列。 • 迭代器来表示向量中元素的位置。 • 向量的迭代器的类型定义为指向连续内存单元地址的指 针: • typedef T* iterator; • typedef const T* const_iterator; • 随机访问迭代器
算法与数据结构
Algorithms and Data Structures
第2章 向量
2.1 向量的基本概念 2.2 ADT向量 2.3 向量的迭代器 2.4 向量的实现方法 2.5 矩阵与多维向量 2.6 高精度整数 2.7 应用举例
2010-3-15 福州大学数学与计算机科学学院 1
算法与数据结构
Algorithms and Data Structures
大整数与1位数相乘是按位相乘
2010-3-15
福州大学数学与计算机科学学院
28
算法与数据结构
Algorithms and Data Structures
大整数按位相乘且结果相加 & 大整数与大整数相乘
2010-3-15
福州大学数学与计算机科学学院
vector testing
return 0;
2010-3-15
福州大学数学与计算机科学学院
14
算法与数据结构
Algorithms and Data Structures
2.5 矩阵与多维向量
2010-3-15
福州大学数学与计算机科学学院
15
算法与数据结构
Algorithms and Data Structures
3 4 0 4
4 3 0 3
5 3 0 3
6 3 0 3
7 2 0 2
8 2 0 2
9 2 0 2
10 1 0 1
1 12 1 1 0 9 1 0 1
• 一个数组元素只存储一个位的方式有点浪费 • 是否可以通过增加存储位数的方法 这个进位可以 • 来提高效率呢? 通过扩大数组 的方法来存放
2010-3-15 福州大学数学与计算机科学学院 25
福州大学数学与计算机科学学院 19
2010-3-15
算法与数据结构
Algorithms and Data Structures
为什么需要高精度计算
• C/C++中的int 和unsigned 类型变量,都不能保存超过10 位的整数 • 即便使用能表示的很大数值范围的double 变量,但有效 位也只有15位 • 在某些情况下(如数据加密和科学计算等方面),我们需要 参与运算的数,可能会远远不止10 位,例如,可能需要 保留小数点后面100位(比如求π的值) 一般称这种基本数据类型无法表示的整数为大整数。
matrix成员学数学与计算机科学学院
18
算法与数据结构
Algorithms and Data Structures
2.6 高精度整数
• • • • • • • • • • • • • typedef unsigned int digit; typedef vector<digit> intv; struct integer{ integer(const string& s,digit b=10);// 构造函数 integer(digit b=10,int size=0);// 构造函数 int operator[](int)const;// 位提领运算 bool operator<(const integer&)const;// 大整数比较 int sign();// 大整数符号 void setbase(digit b){base=b;}// 设置基数 digit base;// 大整数基数2 <= base <= 2^16 bool neg;// 符号 vector<digit> s;// 数字向量 };
matrix成员函数的实现
2010-3-15
福州大学数学与计算机科学学院
16
算法与数据结构
Algorithms and Data Structures
matrix成员函数的实现
2010-3-15
福州大学数学与计算机科学学院
17
算法与数据结构
Algorithms and Data Structures
– 用3个迭代器itx,ity和itz分别扫描3个向量x,y和z – 在遇到较小元素时相应的迭代器后移 – 当且仅当3个迭代器所指位置处元素相同时迭代 器无法移动 – 在最坏情况下对3个向量扫描一遍就可以判定是 否存在公共元素
2010-3-15 福州大学数学与计算机科学学院 31
算法与数据结构
Algorithms and Data Structures
8 3 0 3
9 4 0 4
10 4 0 4
11 4 0 4
12 5 0 5
进位没有存 放的位置
为什么会出现这种情况?
2010-3-15
福州大学数学与计算机科学学院
24
算法与数据结构
Algorithms and Data Structures
大整数的表示
• 数组下标: 0 1 2 • 大整数一: 5 4 4 • 大整数二: 0 0 0 5 4 4 • 结果:
vector成员函数的实现
2010-3-15
福州大学数学与计算机科学学院
10
算法与数据结构
Algorithms and Data Structures
vector成员函数的实现
2010-3-15
福州大学数学与计算机科学学院
11
算法与数据结构
Algorithms and Data Structures
2010-3-15
福州大学数学与计算机科学学院
21
算法与数据结构
Algorithms and Data Structures
精度和效率的保证
• 若要精确地表示大整数并在计算结果中要求精确 地得到所有位数上的数字,就必须用软件的方法 来实现大整数的算术运算 • 利用所选的数据结构,正确、高效地实现整数的 四则运算 • 算法的选择对程序的效率有绝对的影响,算法是 决定程序效率的根本
vector成员函数的实现
2010-3-15
福州大学数学与计算机科学学院
12
算法与数据结构
Algorithms and Data Structures
vector成员函数的实现
2010-3-15
福州大学数学与计算机科学学院
13
算法与数据结构
Algorithms and Data Structures
2010-3-15
福州大学数学与计算机科学学院
22
算法与数据结构
Algorithms and Data Structures
大整数的表示
对于大整数1112223334445 我们可以用一维数组来表示: 数组下标: 0 1 2 3 4 5 6 7 8 9 10 1 12 存储数据: 1 1 1 2 2 2 3 3 3 4 4 1 4 5
算法与数据结构
Algorithms and Data Structures
大整数加法是按位相加
2010-3-15
福州大学数学与计算机科学学院
26
算法与数据结构
Algorithms and Data Structures
大整数减法是按位相减
2010-3-15
福州大学数学与计算机科学学院
27
算法与数据结构
CSDN技术中心 Const用法小结.mht
2010-3-15 福州大学数学与计算机科学学院 5
算法与数据结构
Algorithms and Data Structures
2.4 向量的实现方法
• • • • • • • • • • • • • • • • template <class T> class vector{ public: typedef T* iterator;// 向量迭代器 vector(int size=0,const T& value=T());// 构造函数 ~vector(){if(start)delete []start;}// 析构函数 void push_back(const T& item);// 向量尾插入元素 void pop_back();// 删除向量尾元素 void resize(int new_size,const T& x=T());// 重置向量长度 iterator begin(){return start;}// 指向向量首的迭代器 iterator end(){return start+sz;}// 向量尾的下一位置的迭代器 private: iterator start;// 向量内存单元起始地址 int sz;// 向量中元素个数 int maxsz; // 分配给向量的可用空间大小 };