数据结构与算法 教学课件 作者 张晓蕾 第三章.ppt

《数据结构与算法 教学课件 作者 张晓蕾 第三章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第3章向量向量的基本知识3.1向量运算3.2简易向量类3.3标准模板向量类3.4模板向量容器的测试类3.5矩阵类3.63.1向量的基本知识3.1.1线性表的定义线性表是n（n≥0）个数据元素的有限序列（sequence）。在表中，元素之间存在线性逻辑关系：表中有且仅有一个开始结点；有且仅有一个终端结点；除开始结点外，表中每个结点只有一个前驱结点；除终端结点外，表中每个结点只有一个后继结点。因此，线性表也称为序列类型，即它们可以排成一个序列：{a0，a1，……，an-2，an-1}这里ai（0≤i≤n-1）具有相同的数据类型。n代表线性表的

2、长度，当n=0时，线性表为空。向量采用顺序存储结构。在计算机内，向量是内存中一批连续的存储单元。假设向量的第1个元素的地址是LOC(a0)，每个元素占用的内存空间大小为L，则下标为i的元素ai的存储地址是:3.1.2向量的存储结构LOC(ai)＝LOC(a0)＋Li其具体表示如下：structVector{ELEMTYPEelem[MAXSIZE];//数组域intlen;//表长域};3.2向量运算3.2.1向量运算简介（1）容量或长度size()返回向量的大小max_size()返回最大可能的向量大小resize(n)改变自身的大小为

3、nempty()向量是否为空（2）数据存取operator[](i)返回下标为i的元素at(i)返回下标为i的元素并核对i是否越界front()返回向量第1个元素back()返回向量最后一个元素（3）修改数据push_back(x)插入x到向量的尾部pop_back()删除向量中最后一个元素insert(i,x)在向量的位置i插入元素xinsert(i,n,x)在向量的位置i插入n个相同元素xerase(i)删除向量中指定位置i的元素erase(first,last)删除向量中指定范围[first,last)的元素clear()删除向量中

4、所有的元素（4）按某种要求重排向量中的元素sort(first,last)对向量中所有元素排序partial_sort(first,middle,last)对向量中部分元素[first,middle)排序（5）按某个特定值查找向量中的元素find(first,last,value)在向量[first1,last1)中查找指定的值valuesearch(first1,last1,first2,last2)在向量[first1,last1)中查找另一向量[first2,last2)下面说明在向量的插入与删除这两个基本运算的C++实现：1．插入

5、3.2.2插入算法与删除算法移动前空a0a1…ai-1ai…an-1elem移动后an-1a0a1…ai-1ai…elem先后插入xan-1a0a1…ai-1xai…elem图3-1向量插入算法的图示（1）使用指针的方法从略，可参看教材p.49。（2）使用引用的方法voidinsert(structVector&p,inti,ELEMTYPEx){intj;if(i<0i>p.len)cout<<"插入位置错误!"<=i;j--)p.elem[j+1]=p.elem[j];p.elem

6、[i]=x;p.len++;}}例3-1测试插入算法。见教材p.50。2．删除（1）使用指针的方法从略，可参看教材p.50。（2）使用引用的方法voiderase(structVector&p,inti){intj;if(i<0i>p.len-1)cout<<"元素不存在!"<

7、lem图3-3向量删除算法的实现3.3简易向量类3.3.1简易向量类及其实现简易向量类miniVector编写在名为“minivector.h”的头文件中。3.3.2简易向量类的测试例3-3测试简易向量类。3.4标准模板向量类在标准C++模板库内，线性表顺序存储结构的实现就是vector容器。要使用向量容器必须先声明下面的包含：#include向量容器类构造器使用的一般语法如下：vector对象名[(初始化参数)];其中，对象名及其初始化就是对象的构造器。3.4.1模板向量类的构造器及下标运算符向量构造器：

8、（1）vectorA;//空整型数组（2）vectorA(10);//数组大小为10，初始化为0（3）vectorA(10,1);//数组大小为10，初始化为1（