《数据结构运算》PPT课件.ppt

第二章数据结构及其运算,主要内容,2.1 数据类型2.2 一维数组2.3 二维数组2.4 高维数组2.5 数组操作2.6 数组运算与矩阵运算2.7 多项式2.8 关系运算、逻辑运算和运算符2.9 字符串数组2.10 细胞数组2.11 结构体数组,2.1 引 言,数据结构是程序设计的重要基础，使用合理的数据结构去描述问题，能够缩短程序代码、简化程序结构、便于程序维护。在MATLAB里共有六种基本数据类型，每一种类型可以构成一维、二维和多维的数组。这六种是：双精度型（double）：双精度数值类型，是最常用的类型；字符型（char）：字符数组，每个字符占16位；稀疏型（sparse）：双精度稀疏矩阵，只存储矩阵中的非0元素；细胞型（cell）：细胞，可以存放任意类型数据结构体（struct）：不同类型的数据集合存储型（storage）：用于图像处理,2.1 引 言,数组（Array）可以是一维的行（或列），也可以是二维或多维的。用户可以操作整个数组，也可以操作数组中的某个或者某些元素。MATLAB会根据表达式的运算结果，自动确定变量的类型和大小。变量的数据类型可以用以下函数来查看：isa（var，type）%变量var的数据类型名称如果 是type，则返回1，否则返回0class(var)%返回变量a的数据类型名称whos var%查看变量var的详细情况,2.2 一维数组,一、一维数组的创建 1逐个元素输入法 2冒号运算符法【说明】冒号运算符的格式是：startv:step:endvstartv是初值，即数组的第一个元素值。endv是终值，即数组的最后一个元素值。step称为步长，即数组元素每次增加的值；步长setp可以省略不写，此时默认步长为1；setp可以为负值，此时要求startvendv。,2.2 一维数组,【说明】linspace函数的调用格式为：x=linspace(a,b,n)数组的第一个元素值为a，最后一个元素值为b，数组中共有n个元素，这n个元素线性均匀分布于a和b之间，即数组元素依次为,3、线性分隔法,4、对数分隔法,【说明】logspace函数的调用格式为：x=logspace(a,b,n)数组的第一个元素值为，最后一个元素值为，数组中共有n个元素，这n个元素的以10为底的对数值均匀分布与a和b之间，即数组元素依次为,2.2 一维数组,二、一维数组的访问一维数组的访问遵循以下约定：用下标方式访问数组元素，下标要用一对圆括号()引起来;下标代表的是元素在数组中的位置序号，从1开始，最大值为数组中元素的个数;下标可以是常量，也可以是变量;可以访问数组中的单个元素，也可以访问数组中的某些元素，即数组的子数组。,例,2.3 二维数组,一、二维数组的建立1逐个输入数组元素值如果数组内元素数量少，可以直接从键盘逐个输入元素的值，需要遵循的规则是：整个数组必须用中括号“”括起来数组的行与行之间用分号“;”分隔，或者用回车符分隔每行之间的元素必须用逗号“,”或者空格分隔分隔符必须是英文字符，即在英文状态下输入分号、括号、方括号、逗号等,例,2.3 二维数组,2利用M文件 如果数组元素很多，或者元素值要经常改变，我们可以采用M文件来输入和保存数组。用M文件实现对数组x的输入和保存，方法如下：（1）在当前目录下，用程序编辑器建立一个名为MyData.m的文件；（2）在编辑器中输入x内容；（3）保存MyData.m文件；（4）在命令窗口键入MyData，就可以在内存中建立 数组x并读入数组元素的值。,例,2.3 二维数组,二、二维数组的访问二维数组的访问遵循以下约定：用下标方式访问数组元素，下标要用一对圆形括号()引起来；用双下标方式访问数组元素，格式为(r,c)，其中r为二维数组的行下标，c为二维数组的列下标，下标之间用逗号分隔；用单下标方式访问二维数组，二维数组的单下标是按照列优先规则排序的，即二维数组被看作是从第一列开始从左到右依次将各列首位连接而成的一维数组，单下标表示元素在这个一维数组中的位置；单下标和双下标具有对应关系，其值可以通过 ind2sub和sub2ind函数进行转换；可以访问二维数组的某个元素及其子数组，可 以对元素和子数组赋值。,例,2.3 二维数组,【说明】有关空数组某一维长度为0的数组称为空数组;空数组用 表示，表示数组中没有元素，但可以表示计算结果为“空”;仅仅能用isempty函数正确判断数组是否为空;可以通过给数组元素赋值空数组来缩小数组的大小;尽量不要用空数组参与逻辑运算和关系运算;,例,2.4 高维数组,一、高维数组的创建可以采用下列方法创建高维数组：直接通过全下标方式进行元素赋值；用低维数组合成高维数组；用数组生成函数（ones/zeros/rand等）生成高维数组；用数组操作函数（repmat/reshape等）构造高维数组。,例,2.4 高维数组,二、多维数组的访问对于高维数组的访问，有下列约定：可以通过全下标方式访问。对于三维数组来说，第一维下标称为“行下标”，第二维下标称为“列下标”，第三维下标一般称为“页下标。”可以通过单下标方式访问。高维数组的单下标是按照后维优先的次序排列的，对于三维数组来说，先排列“页”，页内先排列“列”，列内再排列“行”，即第1行第1列第1页的元素单下标为1，然后先变化行下标，再变化列下标，最后变化页下标。数组的维数通过ndims函数获取。数组的尺寸通过size函数获取数组的所有维中的最大长度通过length函数获取。,例,2.5 数组操作,一、标准数组的生成 数学中定义了很多标准数组或者矩阵，如全1数组、全零数组、对角阵等，在Matlab中有相应的函数用来生成这些标准数组。1ones功能：生成全1数组，即数组中的元素都为1。格式：Y=ones(n)生成nn的全1矩阵 Y=ones(m1,m2,mk)生成m1m2mk的全1数组 Y=ones(size(A)生成和数组A同样尺寸的全1数组2zeros功能：生成全0数组，即数组中的元素都为0。格式：同ones函数,2.5 数组操作,3rand功能：生成均匀分布随机数组。格式：Y=sand(state,v)设置随机发生器的初始状态为v其他同ones函数4randn功能：产生正态分布随机数组。格式：同rand函数5magic功能：产生魔方矩阵,不适用于高维数组。格式：M=magic(n)产生nn的魔方矩阵,2.5 数组操作,6eye功能：产生单位矩阵，即主对角线元素都为1而其他元素都为0的二维 数组格式：Y=eye(n)Y=eye(n,m)Y=eys(size(A)Y=eye(m,n,classname)说明：classname是字符串，表示元素的数据类型名 称，可取double,single,int8,uint8,int16,uint16，int32,uint32,int64,uint64。,2.5 数组操作,7diag功能：产生对角阵，即矩阵的某个对角线元素不全为0，其他元素为0。格式：X=diag(v,k)生成length(v)+k阶方阵，并在第k条对角线放置元素vX=diag(v)生成length(v)阶方阵，并在主对角线放置元素vv=diag(X,k)返回方阵X的第k条对角线元素构成的列向量v=diag(X)返回方阵X的主对角线元素构成的列向量说明：v为行向量，表示对角线元素；k为对角线位置，k=0 表示主对角线，k0表示在主对角线上方的第k条对角 线，k0表示在主对角线下方的第(-k)条对角线。,例,2.5 数组操作,二、数组操作 对数组的操作包括数组的扩展、收缩、重排、元素交换和子数组访问等。数组操作可以通过两种方式实现，一种是通过Matlab提供的运算符（逗号，分号，括号等）来实现，另外一种是使用Matlab提供的数组操作函数。下面介绍常用的数组操作函数。1、cat功能：把大小相同的若干数组，沿着指定维的方向，串接成新数组。格式：C=cat(dim,A,B)C=cat(dim,A1,A2,A3,A4,.)说明：A，B，A1，A2等为被串接数组，要求这些数组 同维；dim表示串接方向，1表示行，2表示列，3表示页，以此类推。,2.5 数组操作,2、fliplr 功能：沿着垂直中线，左右（Left-Right）对称交换数组元素（不超过2维）格式：B=fliplr(A)3、flipud 功能：沿着水平中线，上下（Up-Down）对称交换数组元素（不超过2维）格式：B=flipud(A)4、rot90 功能：逆时针旋转二维数组。格式：B=rot90(A)逆时针旋转矩阵90度 B=rot90(A,k)逆时针旋转矩阵90*k度,2.5 数组操作,5、repmat 功能：按指定维上的数目，分块铺放指定数组。格式：B=repmat(A,m,n)沿着第1维铺放m个A，第2维铺放n个A B=repmat(A,m n)B=repmat(A,m n p.)6、reshape 功能：在总元素不变的前提下，重新安排数组各个维的长度，形成新数组。格式：B=reshape(A,m,n)B=reshape(A,m,n,p,.)B=reshape(A,m n p.)B=reshape(A,.,.)说明：A是待重新安排的数组；m，n，p等是新数组各个维 的长度；表示自动计算某个维的长度而无需用户指定。,2.5 数组操作,7、tril 功能：提取矩阵的下三角元素，生成下三角阵。格式：L=tril(X)L=tril(X,k)说明：X为待提取的矩阵；k为三角阵的分界线位置，含义同diag8、triu 功能：提取矩阵的上三角元素，生成上三角阵。格式：L=triu(X)L=triu(X,k)说明：X为待提取的矩阵；k为三角阵的分界线位置，含义同diag函数。,例,例,2.6 数组运算与矩阵运算,一、数组运算Matlab定义了数组运算，数组运算是指对数组中的每个元素进行相同的运算。数组运算可以通过Matlab提供的运算符和数组运算函数实现。1.用数组运算符进行数组运算A+B 数组加法运算 A-B 数组减法运算A.*B 数组相乘，A和B相同位置元素的乘积 作为结果数组的元素A./B 数组相除，A和B相同位置元素相除作 为结果数组的元素,2.6 数组运算与矩阵运算,A.B一定与A./B相同A.p数组各元素求p次幂A#BA、B数组对应元素间进行关系运算，#代表关系运算符ABA、B数组对应元素间进行逻辑运算，代表逻辑运算符A.数组转置，非共轭转置sA标量s与数组A运算，s与A的每个元素进行运算，代表某个运算符,2.6 数组运算与矩阵运算,2.数组运算函数三角函数:sin，cos，asin，asinh，asec，sect，tan，atan等指数对数函数：exp指数函数 log自然对数函数 log10以10为底的对数函数 log2以2为底的对数函数 pow22的幂函数 sqrt平方根函数,2.6 数组运算与矩阵运算,复数函数abs绝对值，模angle相角（弧度为单位）imag复数的虚部real复数的实部conj复数的共轭取整函数：ceil向+方向取整fix向0方向取整floor向-方向取整round向最近的整数取整sign符号函数，操作数为正则返回1，为负则返回-1，为零则返回0,2.6 数组运算与矩阵运算,二、矩阵运算矩阵和二维数组在数据结构上是完全相同的，但是矩阵是一种数学变换或者数学算子，矩阵的运算在数学上有严格的运算规则定义，和数组运算是不同的。矩阵运算可以通过Matlab运算符实现，Matlab也提供矩阵函数来支持矩阵运算。下面列出常用的矩阵运算。A+B矩阵加法A-B矩阵减法A*B矩阵乘法，要满足维数要求，一般不符合交换律A/B矩阵右除，求xB=A的最小二乘解AB矩阵左除，求Bx=A的最小二乘解Ap矩阵乘方,2.6 数组运算与矩阵运算,s*A标量s与矩阵A相乘，标量s分别与A的每个元素相乘expm(A)矩阵的指数函数logm(A)矩阵的对数函数sqrtm(A)矩阵的平方根函数inv(A)矩阵的逆矩阵【说明】点运算。Matlab运算符提供了点运算功能。在常用的算数运算符前面加上一个“.”则代表运算是按照数组运算规则进行运算，否则是按照矩阵运算规则进行运算的。Matlab中有些运算函数的名字是某个函数名字后加了 一个字母m，通常情况下，这两个函数的运算功能是 相同的，只是加了m的函数按照矩阵运算规则运算，另外一个函数按照数组运算规则运算。,例,2.6 数组运算与矩阵运算,三、特殊的运算结果1.正无穷大 Inf有些数值计算结果是趋向于无穷大（Infinity），Matlab中用Inf表示正无穷大。2.非数 NaN有些计算结果会产生非数（Not a Number），Matlab中用NaN来表示非数。【说明】Matlab给出了Inf和NaN的目的是为了避免因为运算 结果出现无穷大或者不可预知的非数情况而造成程 序执行的中断。,例,2.7 多项式,一、多项式的创建直接输入法poly(A)若A为方阵，则创建方阵A的特征多项式poly(a)如果向量a=bn bn-1b1 b0，则创建(x-b0)(x-b1)(x-bn-1)(x-bn)生成 的多项式的系数向量，即创建全部根为 bn,bn-1,b1,b0对应的多项式。,2.7 多项式,二、多项式的运算 数学上对多项式的运算有严格的定义，多项式运算包括多项式相乘、多项式相除、多项式相加减、多项式求导、多项式求值、多项式的部分分式展开和多项式求根等。多项式加减：+-说明：使用Matlab的运算符+-实现多项式的加减法多项式相乘:p=conv(p1,p2)说明：p为多项式p1和多项式p2的乘积多项式相除：q,r=deconv(p1,p2)说明：多项式p1除以多项式p2，商多项式为q，余多项式为r,2.7 多项式,多项式求导dp=polyder(p)为多项式p的导数多项式为dpdp=polyder(p1,p2)多项式p1和多项式p2乘积的导数多项式为dpnum,den=polyder(p1,p2)有理分式(p1/p2)的求导后的有理分式为(num/den)多项式求值pA=polyval(p,A)按数组运算规则求多项式p在自变量为A时的值MA=ployvalm(p,A)按矩阵运算规则求多项式p在自变量为A时的值说明：当自变量A为矩阵时，多项式中的常数项a0被 当作a0*eye(n)处理,2.7 多项式,多项式求根：r=roots(p)r为多项式p的根组成的列向量部分分式分解：r,p,k=residue(num,den)有理分式(num/den)部分分式分解后，r为留数，p为极点，k为直项多项式拟合：p=polyfit(x,y,n)由给定数据x和y拟合出n阶多项式p，用来逼近y=f(x)曲线矩阵的特征多项式：p=poly(A)多项式p为矩阵A的特征多项式,例,2.8 关系运算、逻辑运算和运算符,一、逻辑值在程序流程的控制和解决问题的分析判断中，需要对某些命题的真假给出答案，因此Matlab定义了逻辑值，包括“逻辑真”和“逻辑假”。对于逻辑值，Matlab有如下约定：在关系表达式和逻辑表达式中的输入中，任何非0数为“逻辑真”，只有0为“逻辑假”。关系表达式和逻辑表达式的计算结果是一个由0和1构成的“逻辑数组”（Logical Array），逻辑数组中“1”表示真，“0”表示假。逻辑数组属于“数值数组”的子类，它可以作为数值数组参与数值计算，也可以用于数组寻访等特殊场合。比如：用逻辑矩阵作为数组下标，可以提取数组中逻辑矩阵真值位置处的元素。关系运算符和逻辑运算符遵循数组运算规则。,2.8 关系运算、逻辑运算和运算符,二、关系运算符Matlab提供的关系运算符如下：大于=大于等于=等于!=不等于三、逻辑运算符Matlab提供了3种逻辑操作，他们分别是数组逻辑操作、位逻辑操作和先决逻辑操作。,2.8 关系运算、逻辑运算和运算符,数组逻辑操作&逻辑与|逻辑或 逻辑非xor逻辑异或位逻辑操作函数（操作数必须是非负整形标量或者数组）bitand 位与 bitor 位或bitcmp 位非bitnor 位异或先决逻辑运算符（要求操作数为标量）&先决与，如果第一个操作数为假，则不判断其他操作数，直接给出结论“假”|先决或，如果第一个操作数为真，则不判断其他操作数，直接给出结论“真”,例,2.8 关系运算、逻辑运算和运算符,四、逻辑函数逻辑函数的运行结果是逻辑矩阵，从函数名上就可以看出其的功能。any(v)；%向量v中有非0元素，结果为1，否则为0；对矩阵的运算结果 是行向量all(v)；%向量v中都是非0元素，结果为1。对矩阵的运算结果是行向量isequal(A,B)；%判断是否相等，数组运算ismember(A,B)；%A的元素是B中元素，则A相应位置为1，否则为0 判断特殊数据的逻辑函数isempty isfinite isinf isletter isnan isprime isreal isspace判断数据类型的逻辑函数iscell ischar iscellstr isfield isglobal ishandle islogical isnumeric isobject issparse isstruct,例,例,2.8 关系运算、逻辑运算和运算符,五、运算符及其优先级MATLAB的运算符可分为三类：算术运算符、关系运算符和逻辑运算符。除去个别运算符外，一般可认为算术运算符的优先级最高，其次是关系运算符，再其次是逻辑运算符。下表是Matlab运算符优先级的约定。【说明】如果书写表达式的时候，无法弄清某些运算符的优先级，建议使用括号来规定运算次序。,2.8 关系运算、逻辑运算和运算符,2.9 字符串数组,一、字符与字符串MATLAB有强大的字符处理能力，字符串处理主要用于数据的可视化显示、宏操作、符号计算和文件操作等。Matlab中，对于字符和字符串有如下描述：字符是字符串中的一个元素，一个英文字符或者一个汉字都占用一个字符位。字符在内存中是用其ASCII码存储的，通常一个字符的ASCII码为2个Byte。字符或者字符串必须放在“单引号”对中。如果字符串中出现“单引号”字符，则用2个“单引号”表示。字符串可以看作是一维字符数组。一维字符串数组可以看作是二维字符数组。,例,2.9 字符串数组,二、字符串数组的访问一维字符串数组相当于二维字符数组，因此其访问方式和二维数组的访问方式相同，可以采用单下标和双下标方式访问。今后如无特别说明，本书中的“字符串数组”就指的是一维字符串数组。三、字符串转换函数Matlab提供了大量的字符串转换函数，实现各种数据类型和字符串之间的相互转换。abs把字符串转换为ASCII码fprintf sprintf sscanf 字符串的格式化输入输出函数,例,2.9 字符串数组,base2dec bin2dec dec2base dec2hex hex2dec hex2num int2str mat2str num2str str2num str2mat char double 强制转换函数【说明】dec表示十进制整数；num表示浮点数；int表示整数；mat表示数值矩阵；base表示任意进制串；bin表示2进制串；hex表示16进制串；str表示字符串；2表示To（转换到），如bin2dec的意思是“把二进制串转换到十进制整数”。,2.9 字符串数组,四、字符串操作函数用户可以使用Matlab提供的字符串操作函数对字符串进行各种操作，这些操作包括：创建blanks char mat2str deblank连接strcat strvcat 搜索与替换findstr strmatch strrep strtok执行宏字符串eval feval,2.9 字符串数组,逻辑判断ischar isletter isspace 大小写转换lower upper字符串比较strcmp strncmp对齐方式strjust,2.10 细胞数组,一、细胞数组的数据结构程序设计中为了便于处理数据和简化程序代码，希望将不同类型的数据放置在某种数据结构中，并且通过每个数据在这种数据结构中的位置索引来访问该数据。数值数组(Numberic Array)中只能放置相同类型的数据，不能解决这样的问题。Matlab定义了细胞数组（Cell Array），其与数值数组的比较如下：相同点数值数组和细胞数组都是数组，都可以用下标（单下标、全下标）方式访问不同点数值数组的元素是相同类型的数据，细胞数组的元素可以是不同类型的数据,2.10 细胞数组,二、细胞数组的访问细胞数组也是数组，可以用访问数组的方法来访问细胞数组，即通过单下标或全下标的方式访问细胞数组中的某个元素或子数组。细胞是细胞数组中的元素，可以把细胞当作是一种新的数据类型。细胞的访问是通过圆括号（）和下标实现的，就和访问数组元素一样。细胞的内容是指细胞内放置的数据，这些数据可以是任何Matlab数据类型。访问细胞的内容是通过花括号 和下标实现的。细胞的内容可以当作是普通Matlab变量，使用方法和普通变量没有区别。细胞数组可以嵌套使用，即细胞的内容可以是细胞数组。,例,2.11 结构体数组,一、结构体数组的数据结构结构体是若干个数据的集合，这些数据可以是不同的Matlab数据类型，且结构体中的每个数据都被分派了一个名字，我们称之为“域名”或“成员名”。结构体数组是由多个结构体数据构成的数组，其基本元素为结构体数据。结构体类型是用户根据需要，用基本数据类型构造出来的新数据类型。结构体能够更准确直观地描述客观事物，能够把和某个事物相关的属性数据构造到一个数据结构中，并给这个事物的各个属性命名，可以用直观的名字去访问这个事物的属性。合理的构造和使用结构体，能够使程序编码获得简化，大大提高程序的可读性和可维护性,2.11 结构体数组,二、结构体数据的访问结构体的访问约定如下：访问结构体数据的某个成员，要使用成员（域）运算符“.”,其格式为：结构体数据.成员名访问结构体数组中的元素，即结构体数据，方法和访问数组元素相同。结构体数组可以是一维、二维和多维的。结构体的成员可以作为普通Matlab变量使用。结构体可以嵌套使用，即结构体的成员可以是其他的结构体。结构体的成员可以是细胞数组。,2.11 结构体数组,三、结构体数组的创建1.通过直接给结构体的成员赋值来创建2.利用构造函数创建结构体数组可以用函数struct建立结构体数组，其用法为：s=struct(field1,values1,field2,values2,.)【说明】field1，field2为成员名，必须为字符串values1,values2为成员的值。如果建立的不是单结 构体变量（11结构体数组），要求它们是具有相同维数的细胞数组。任何情况下，空数组“”作为成员值可以创建新的空成员。struct函数无法创建具有嵌套格式的结构体数据，被嵌套的结构体成员可以通过直接输入法创建。,例,例,例,习题,21 创建一个有7个元素的一维数组，并做如下处理：直接寻访一维数组的第6个元素；寻访一维数组的第1、3、5个元素；寻访一维数组中第4个至最后1个元素；寻访一维数组中大于70的元素。22 有数组T=1-2 3-4 2-3，通过编程生成范德蒙矩阵。23 找出数组 中所有绝对值大于3的元素。24 建立矩阵A，然后找出在10,20区间的元素的位置。25 求 的“商”及“余”多项式。26 求3阶方阵A的特征多项式。,