数据结构串和数组幻灯片.ppt

《数据结构串和数组幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构串和数组幻灯片.ppt（63页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构串和数组第1页，共63页，编辑于2022年，星期六l串串(String)是是由由零零个个或或多多个个字字符符组组成成的的有有限限序序列列。一一般记为般记为:S=a1 a2.an(n0)l其其中中，S是是串串的的名名，用用单单引引号号括括起起来来的的字字符符序序列列是是串串的的值值；ai(1in)可可以以是是字字母母、数数字字或或其其它它字字符符，串串中字符的数目中字符的数目n称为串的长度。称为串的长度。ln=0的串称为的串称为空串空串(null string)。3.6.1 串的定串的定义义和串的存和串的存储储方式方式概念概念第2页，共63页，编辑于2022年，星期六串串中中任任意意个个

2、连连续续的的字字符符组组成成的的子子序序列列称称为为该该串串的的子串子串。包含子串的串相包含子串的串相应应地称地称为为主串主串。通常称字符在序列中的序号通常称字符在序列中的序号为该为该字符在串中的位置。字符在串中的位置。子子串串在在主主串串中中的的位位置置则则以以子子串串的的第第一一个个字字符符在在主主串串中中的位置来表示。的位置来表示。当当两两个个串串的的长长度度相相等等，并并且且各各个个对对应应位位置置上上的的字字符符都都相等时，称相等时，称两个串相等两个串相等。3.6.1 串的定串的定义义和串的存和串的存储储方式方式概念概念第3页，共63页，编辑于2022年，星期六l例：串名例：串名为为

3、A、B、C、D的四个串如下：的四个串如下：l A=very good；长长度度为为9，是，是D的主串；的主串；l B=；长长度度为为3；l C=；长长度度为为0（空串）；（空串）；l D=good；长长度度为为4，是，是A的子串。的子串。lD在在A中的位置是中的位置是6。3.6.1 串的定串的定义义和串的存和串的存储储方式方式概念概念第4页，共63页，编辑于2022年，星期六l(1)赋值操作：赋值操作：StrAssign(S，chars)初始条件：初始条件：chars是字符串常量；是字符串常量；操作结果：生成一个值等于操作结果：生成一个值等于chars的字符串的字符串S；l(2)插入操作：插入

4、操作：StrInsert(S，pos，T)初始条件：字符串初始条件：字符串S、T存在，存在，1pos StrLength(S)+1；操操作作结结果果：在在字字符符串串S的的第第pos个个字字符符之之前前插插入入串串T。3.6.1 串的定串的定义义和串的存和串的存储储方式方式基本操作基本操作第5页，共63页，编辑于2022年，星期六(3)删删除操作：除操作：StrDelete(S，pos，len)初始条件：字符串初始条件：字符串S存在，存在，1pos StrLength(S)-len+1；操操作作结结果果：从从字字符符串串S中中删删除除第第pos个个字字符符起起长长度度为为len的子串。的子串。

5、(4)复制操作：复制操作：StrCopy(S，T)初始条件：字符串初始条件：字符串S存在；存在；操作操作结结果：将字符串果：将字符串S的内容复制到串的内容复制到串T。3.6.1 串的定串的定义义和串的存和串的存储储方式方式基本操作基本操作第6页，共63页，编辑于2022年，星期六l(5)判空操作：判空操作：StrEmpty(S)初始条件：字符串初始条件：字符串S存在；存在；操操作作结结果果：若若S为为空空串串，则则返返回回TRUE，否否则则返返回回FALSE。l(6)比比较较操作：操作：StrCompare(S，T)初始条件：字符串初始条件：字符串S、T存在；存在；操操作作结结果果：若若ST，

6、则则返返回回值值0；若若S=T，则则返返回回值值=0；若；若ST，则则返回返回值值Maxlen，且，且pos+LCMaxlen，且，且pos+LCMaxlen；3.6.2 定定长顺长顺序串运算序串运算插入算法分析插入算法分析第13页，共63页，编辑于2022年，星期六/*在串在串s中序号为中序号为pos的字符之前插入串的字符之前插入串t*/int StrInsert(SString*s,int pos,SString t)int i;if(poss-len)return(0);/*插入位置不合法插入位置不合法*/if(s-len+t.lenlen+t.len-1;i=t.len+pos;i-)

7、s-chi=s-chi-t.len;for(i=0;ichi+pos=t.chi;s-len=s-len+t.len;3.6.2 定定长顺长顺序串运算序串运算插入算法插入算法实现实现第14页，共63页，编辑于2022年，星期六 else if(pos+t.lenMaxlen，但串但串t的字符序列可以全部插入的字符序列可以全部插入*/for(i=Maxlen-1;i=t.len+pos;i-)s-chi=s-chi-t.len;for(i=0;ichi+pos=t.chi;s-len=Maxlen;else/*串串t的部分字符序列要舍弃的部分字符序列要舍弃*/for(i=0;ichi+pos=t

8、.chi;s-len=Maxlen;return(1);3.6.2 定定长顺长顺序串运算序串运算插入算法插入算法实现实现第15页，共63页，编辑于2022年，星期六int StrDelete(SString*s,int pos,int len)if(pos(s-len-len)return(0);for(i=pos+len;ilen;i+)s-chi-len=s-chi;s-len=s-len-len;return(1);3.6.2 定定长顺长顺序串运算序串运算删删除算法除算法实现实现第16页，共63页，编辑于2022年，星期六在进行串的连接时：在进行串的连接时：假设原字符串为假设原字符串为A

9、，长度为，长度为LA；待连接串假设为待连接串假设为B，其长度为，其长度为LB；连接过程可能出现下列三种情况：连接过程可能出现下列三种情况：1)连接后串的总长度为连接后串的总长度为LA+LB Maxlen；2)连接后串的总长度连接后串的总长度Maxlen，且，且LAMaxlen，LA=Maxlen；3.6.2 定定长顺长顺序串运算序串运算连连接算法分析接算法分析第17页，共63页，编辑于2022年，星期六/*将串将串t连接在串连接在串s的后面的后面*/int StrCat(SString*s,SString t)int i,flag;if(s-len+t.lenlen;ilen+t.len;i+

10、)s-chi=t.chi-s-len;s-len=s-len+t.len;flag=1;3.6.2 定定长顺长顺序串运算序串运算连连接算法接算法实现实现第18页，共63页，编辑于2022年，星期六 else if(s-lenMaxlen，但串但串s的长度的长度len;ichi=t.chi-s-len;s-len=Maxlen;flag=0;else flag=0;/*串串s的长度的长度=Maxlen，串，串t不被连接不被连接*/return(flag);3.6.2 定定长顺长顺序串运算序串运算连连接算法接算法实现实现第19页，共63页，编辑于2022年，星期六数数组组(array)可可看看成成

11、是是线线性性表表的的推推广广，是是最最常常用用的的数数据据结结构之一。构之一。数数组组是有限个数是有限个数组组元素的集合，元素数目固定；元素的集合，元素数目固定；数数组组的的每每个个元元素素与与一一组组下下标标相相对对应应，数数组组元元素素的的下下标标关系具有上下界的关系具有上下界的约约束且下束且下标标有序；有序；数数组组中所有数中所有数组组元素的数据元素的数据类类型必型必须须一致；一致；数数组组的两种基本运算：的两种基本运算：1.给给定下定下标标，存取相，存取相应应的数据元素；的数据元素；2.给给定下定下标标，修改相，修改相应应的数据元素。的数据元素。3.6.3 二二维维数数组组的的结结构特

12、点和存构特点和存储储方式方式定定义义第20页，共63页，编辑于2022年，星期六一一个个m行行n列列的的二二维维数数组组(也也称称为为矩矩阵阵)，记记作作Am,n。3.6.3 二二维维数数组组的的结结构特点和存构特点和存储储方式方式定定义义A=a11 a12 .a1n a21 a22 .a2n am1 am2 .amn 第21页，共63页，编辑于2022年，星期六按行按行优优先先顺顺序存序存储储对对于于上上述述二二维维数数组组A而而言言，可可以以将将其其看看成成是是由由m个个行向量行向量组组成的向量，即：成的向量，即：Amn=(a11，.，a1n)，(a21，.，a2n)，.，(am1，.，a

13、mn)这这种行向量表相当于一个种行向量表相当于一个线线性表。性表。行行优优先先顺顺序序存存储储就就是是数数组组元元素素按按行行向向量量表表次次序序进进行行存存储储，即即第第i+1个个行行表表紧紧跟跟在在第第i个个行行表表后后面面进进行存行存储储。3.6.3 二二维维数数组组的的结结构特点和存构特点和存储储方式方式存存储结储结构构第22页，共63页，编辑于2022年，星期六当当把把n维维数数组组的的元元素素按按行行优优先先顺顺序序地地存存放放在在存存储储器器里里，则则每每个个元元素素的的存存储储地地址址可可以以用用公公式式计计算算出出来。来。这这个个计计算公式称算公式称为为“地址公式地址公式”。

14、假假设设每每个个数数据据元元素素占占c个个存存储储单单元元，则则上上述述二二维维数数组组Amn的地址公式的地址公式为为：Loc(aij)=Loc(a11)+(i-1)*n+(j-1)*c(1im，1jn)3.6.3 二二维维数数组组的的结结构特点和存构特点和存储储方式方式存存储结储结构构第23页，共63页，编辑于2022年，星期六按列按列优优先先顺顺序存序存储储对对于于上上述述二二维维数数组组A而而言言，也也可可以以将将其其看看成成是是由由n个个列向量列向量组组成的向量，即：成的向量，即：Amn=(a11，.，am1)，(a12，.，am2)，.，(a1n，.，amn)这这种列向量表也相当于一

15、个种列向量表也相当于一个线线性表。性表。列列优优先先顺顺序序存存储储就就是是数数组组元元素素按按列列向向量量表表次次序序进进行行存存储储，即即第第i+1个个列列表表紧紧跟跟在在第第i个个列列表表后后面面进进行行存存储储。3.6.3 二二维维数数组组的的结结构特点和存构特点和存储储方式方式存存储结储结构构第24页，共63页，编辑于2022年，星期六当当把把n维维数数组组的的元元素素按按列列优优先先顺顺序序地地存存放放在在存存储储器器里里，并并假假设设每每个个数数据据元元素素占占c个个存存储储单单元元，则则上述二上述二维维数数组组Amn的地址公式的地址公式为为：Loc(aij)=Loc(a11)+

16、(j-1)*m+(i-1)*c(1im，1jn)3.6.3 二二维维数数组组的的结结构特点和存构特点和存储储方式方式存存储结储结构构第25页，共63页，编辑于2022年，星期六根根据据二二维维数数组组的的特特性性可可以以推推出出：一一个个三三维维数数组组可可以以用用其其数数据据元元素素为为二二维维数数组组的的线线性性表表来来定定义义；依依次次类类推推，n维维数数组组是是由由数数据据元元素素为为n-1维维数数组组的的线线性性表表构构成。成。因因此此，对对n维维数数组组也也有有上上述述两两种种不不同同顺顺序序分分配配的的存存储储结结构构。当当把把n维维数数组组的的元元素素这这样样顺顺序序地地存存放

17、放在在存存储储器器里里，则则每每个个元元素素的的存存储储地地址址都都可可以以用用“地地址址公公式式”计计算算出来。出来。3.6.3 二二维维数数组组的的结结构特点和存构特点和存储储方式方式存存储结储结构构第26页，共63页，编辑于2022年，星期六在在C语语言言中中，可可以以把把一一个个二二维维数数组组看看作作是是一一种种特特殊殊的的一一维维数数组组，该该一一维维数数组组的的元元素素又又是是一一个个一一维维数数组组。例例如如定定义义：int a34；其其中中，可可以以把把a看看作作是是一一个个一一维维数数组组，它它有有3个个元元素素：a0、a1、a2，每每个个元元素素又又是是一一个个包包含含4

18、个个元元素素的的一一维维数数组组。3.6.3 二二维维数数组组的的结结构特点和存构特点和存储储方式方式示例示例第27页，共63页，编辑于2022年，星期六通通常常在在实实际际计计算算中中经经常常出出现现一一些些阶阶数数很很高高的的矩矩阵阵，且矩阵中有许多值相同的元素或者零元素。且矩阵中有许多值相同的元素或者零元素。为了节省存储空间，可以对这类矩阵进行压缩存储。为了节省存储空间，可以对这类矩阵进行压缩存储。所所谓谓压压缩缩存存储储是是指指：为为多多个个值值相相同同的的元元素素只只分分配配一个存储空间；对零元素不分配空间。一个存储空间；对零元素不分配空间。3.6.3 二二维维数数组组的的结结构特点

19、构特点特殊矩特殊矩阵阵的存的存储储方式方式第28页，共63页，编辑于2022年，星期六下三角矩下三角矩阵阵的存的存储储方式：方式：设设下三角矩下三角矩阵为阵为Ann，满满足：足：3.6.3 二二维维数数组组的的结结构特点构特点特殊矩特殊矩阵阵的存的存储储方式方式A=a11 0 0 a21 a22 0 an1 an2 ann 第29页，共63页，编辑于2022年，星期六若将其中的非零元素按行若将其中的非零元素按行优优先先顺顺序存放序存放为为：则则一一维维数数组组Sak和和矩矩阵阵元元素素aij之之间间存存在在着着一一一一对对应应关系：关系：(1ji n)3.6.3 二二维维数数组组的的结结构特点

20、构特点特殊矩特殊矩阵阵的存的存储储方式方式k=+j第30页，共63页，编辑于2022年，星期六l假假设设每每个个数数据据元元素素占占用用一一个个字字节节的的存存储储单单元元，则则下三角矩阵的地址公式为：下三角矩阵的地址公式为：3.6.3 二二维维数数组组的的结结构特点构特点特殊矩特殊矩阵阵的存的存储储方式方式Loc(aij)=Loc(a11)+i(i1)/2+(j1)第31页，共63页，编辑于2022年，星期六三三对对角矩角矩阵阵的存的存储储方式：方式：设设三三对对角矩角矩阵为阵为Ann，满满足：足：3.6.3 二二维维数数组组的的结结构特点构特点特殊矩特殊矩阵阵的存的存储储方式方式A=a11

21、 a12 0 0 a21 a22 a23 0 00 a32 a33 a34 0 0 0 0 an-1,n-2 an-1,n-1 an-1,n 0 0 0 an,n-1 ann 第32页，共63页，编辑于2022年，星期六若若将将其其中中的的非非零零元元素素按按行行优优先先顺顺序序存存放放，假假设设每每个个数数据据元元素素占占用用一一个个字字节节的的存存储储单单元元，则则三三对对角角矩矩阵阵的地址公式为：的地址公式为：3.6.3 二二维维数数组组的的结结构特点构特点特殊矩特殊矩阵阵的存的存储储方式方式Loc(aij)=Loc(a11)+2(i1)+(j1)其中：其中：i=1,j=1,2 或：或：

22、i=n,j=n-1,n 或：或：1in,j=i-1,i,i+1第33页，共63页，编辑于2022年，星期六对对称矩称矩阵阵的存的存储储方式：方式：解决方案解决方案类类似于下三角矩似于下三角矩阵阵的存的存储储。3.6.3 二二维维数数组组的的结结构特点构特点特殊矩特殊矩阵阵的存的存储储方式方式第34页，共63页，编辑于2022年，星期六稀疏矩稀疏矩阵阵：如如果果一一个个矩矩阵阵中中大大多多数数元元素素为为零零，非非零零元元素素较较少少且且分分布无一定规律，则称之为稀疏矩阵。布无一定规律，则称之为稀疏矩阵。(1)顺顺序存序存储储：a)三三元元组组表表：线线性性表表中中的的每每个个结结点点由由三三个

23、个字字段段组组成成，分分别别是是该该非零元素的行下非零元素的行下标标、列下、列下标标和和值值。3.6.3 二二维维数数组组的的结结构特点构特点特殊矩特殊矩阵阵的存的存储储方式方式第35页，共63页，编辑于2022年，星期六稀疏矩稀疏矩阵阵的的C语语言表示：言表示：#define smax 16/*最大非零元素个数最大非零元素个数*/typedef int datatype;typedef struct int i,j;/*行号，列号行号，列号*/datatype v;/*元素元素值值*/node;3.6.3 二二维维数数组组的的结结构特点构特点特殊矩特殊矩阵阵的存的存储储方式方式第36页，共6

24、3页，编辑于2022年，星期六稀疏矩稀疏矩阵阵的的C语语言表示：言表示：typedef struct int m,n,t;/*行数，列数，非零元素个数行数，列数，非零元素个数*/node datasmax;/*三元三元组组表表*/spmatrix;/*稀疏矩稀疏矩阵类阵类型型*/3.6.3 二二维维数数组组的的结结构特点构特点特殊矩特殊矩阵阵的存的存储储方式方式第37页，共63页，编辑于2022年，星期六稀疏矩稀疏矩阵举阵举例：非零元素按行例：非零元素按行优优先先顺顺序存序存储储。3.6.3 二二维维数数组组的的结结构特点构特点特殊矩特殊矩阵阵的存的存储储方式方式第38页，共63页，编辑于20

25、22年，星期六该该稀稀疏疏矩矩阵阵共共有有20个个元元素素，仅仅有有6个个非非零零元元素素。其三元其三元组组表如下表如下图图所示。所示。3.6.3 二二维维数数组组的的结结构特点构特点特殊矩特殊矩阵阵的存的存储储方式方式m=4n=5t=6行号域列号域值域1015204831014123521-26306第39页，共63页，编辑于2022年，星期六b)伪伪地址表示法：地址表示法：伪伪地地址址是是指指本本元元素素在在矩矩阵阵中中按按行行优优先先顺顺序序的的相相对对位位置置，上述稀疏矩上述稀疏矩阵阵A中非零元素中非零元素为为：5，8，1，3，-2，6非零元素的非零元素的伪伪地址地址=n*i+j，n为

26、为矩矩阵阵的列数。的列数。因此，因此，5的的伪伪地址地址为为1；1的的伪伪地址地址为为5；。3.6.3 二二维维数数组组的的结结构特点构特点特殊矩特殊矩阵阵的存的存储储方式方式第40页，共63页，编辑于2022年，星期六(2)稀疏矩稀疏矩阵阵的的转转置运算：置运算：一般矩一般矩阵阵的的转转置算法置算法为为：for(col=0;coln;col+)for(row=0;rowdata和和b-data中中结结点序号；点序号；col指示指示*a的列号，即的列号，即*b的行号的行号*/pmatrix*b;/*存放存放转转置后的矩置后的矩阵阵*/b=malloc(sizeof(spmatrix);b-m=

27、a-n;b-n=a-m;/*行列数交行列数交换换*/b-t=a-t;3.6.3 二二维维数数组组的的结结构特点构特点特殊矩特殊矩阵阵的存的存储储方式方式第42页，共63页，编辑于2022年，星期六 if(b-t0)/*有非零元素，有非零元素，则转则转置置*/bno=0;for(col=0;coln;col+)/*按按*a的列序的列序转转置置*/for(ano=0;anot;ano+)/*扫扫描整个三元描整个三元组组表表*/if(a-dataano.j=col)/*列号列号为为col则进则进行置行置换换*/b-databno.i=a-dataano.j;b-databno.j=a-dataano

28、.i;b-databno.v=a-dataano.v;3.6.3 二二维维数数组组的的结结构特点构特点特殊矩特殊矩阵阵的存的存储储方式方式第43页，共63页，编辑于2022年，星期六 bno+;/*b-data结结点序号加点序号加1*/return b;/*返回返回转转置置结结果指果指针针*/*TRANSMAT */3.6.3 二二维维数数组组的的结结构特点构特点特殊矩特殊矩阵阵的存的存储储方式方式第44页，共63页，编辑于2022年，星期六l该该算算法法的的时时间间主主要要耗耗费费在在col和和ano的的二二重重循循环环上上，若若A的的列列数数为为n，非非零零元元素素个个数数为为t，则则执执

29、行行时时间间为为(n t)，即与的列数和非零元素个数的乘，即与的列数和非零元素个数的乘积积成正比。成正比。l而而通通常常用用二二维维数数组组表表示示矩矩阵阵时时，其其转转置置算算法法的的执执行行时时间间是是(m n)。l由由于于非非零零元元素素个个数数一一般般远远远远大大于于行行数数，因因此此，上上述述稀稀疏疏矩矩阵阵转转置算法置算法虽虽然然节节省了空省了空间间，但增加了，但增加了转转置的置的时间时间。3.6.3 二二维维数数组组的的结结构特点构特点特殊矩特殊矩阵阵的存的存储储方式方式第45页，共63页，编辑于2022年，星期六(2)链链式存式存储结储结构：构：a)带带行指行指针针向量的向量的

30、单链单链表表示。表表示。行指行指针针向量向量 列列值值 3.6.3 二二维维数数组组的的结结构特点构特点特殊矩特殊矩阵阵的存的存储储方式方式1506011-24823第46页，共63页，编辑于2022年，星期六b)十字十字链链表表结结构：构：3.6.3 二二维维数数组组的的结结构特点构特点特殊矩特殊矩阵阵的存的存储储方式方式第47页，共63页，编辑于2022年，星期六l设设已已知知一一个个nn的的上上三三角角矩矩阵阵X，其其上上三三角角元元素素已已按按行行序序为为主序主序连续连续存放在数存放在数组组Y中。中。l请请设设计计一一个个tran函函数数，将将数数组组Y中中元元素素按按列列为为主主序序

31、连连续续存存放放在数在数组组Z中。中。3.6.4 应应用用实实例例问题问题描述描述A=1 2 3 4 5 0 6 7 8 90 0 10 11 120 0 0 13 140 0 0 0 15第48页，共63页，编辑于2022年，星期六l根据已知条件：根据已知条件：Y=(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)l期望得到的期望得到的结结果：果：Z=(1,2,6,3,7,10,4,8,11,13,5,9,12,14,15)l解解题题思路：思路：1.用用i和和j表表示示矩矩阵阵X中中元元素素的的行行和和列列下下标标。用用k表表示示数数组组Y中中元元素素的的下下标标。2

32、.初始初始值设为值设为：i=1,j=1,k=1；3.将将yk=xi,j元元素素存存放放在在zj*(j-1)/2+i中中，且且当当一一行行没没有有结结束束时时j+，否否则则i+并并修修改改下下一一行行元元素素的的个个数数及及i和和j的的值值，直直到到k=n(n+1)/2为为止。止。3.6.4 应应用用实实例例算法分析算法分析第49页，共63页，编辑于2022年，星期六l#include l#define N 5lvoid tran(int y,int n,int z)int k,step=n,count=0,i=0,j=0;for(k=0;kn*(n+1)/2;k+)count+;zj*(j-1

33、)/2+i=yk;if(count=step)step-;count=0;i+;j=i;elsej+;3.6.4 应应用用实实例例算法算法实现实现第50页，共63页，编辑于2022年，星期六lmain()int xNN,yN*(N+1)/2,zN*(N+1)/2;int i,j,k=0,n=N;for(i=0;in;i+)for(j=0;jn;j+)xij=0;printf(“please input non zero data of Matrix:n);for(i=0;in;i+)for(j=i;jn;j+)scanf(“%d”,&xij);3.6.4 应应用用实实例例算法算法实现实现第51

34、页，共63页，编辑于2022年，星期六for(i=0;in;i+)for(j=0;jn;j+)printf(“%4d”,xij);printf(“n”);for(i=0;in;i+)for(j=i;jn;j+)yk=xij;k+;for(i=0;in*(n+1)/2;i+)printf(“%4d”,yi);printf(“n”);tran(y,n,z);for(i=0;in*(n+1)/2;i+)printf(“%4d”,zi);printf(“n”);l3.6.4 应应用用实实例例算法算法实现实现第52页，共63页，编辑于2022年，星期六l问题问题描述描述 l输输入一个稀疏矩入一个稀疏矩阵

35、阵，要求：，要求：将其将其转转化化为为三元三元组组的表示形式；的表示形式；在在三三元元组组存存储储矩矩阵阵中中查查找找值值为为x的的结结点点，若若x存存在在，则则输输出出其其位置，否位置，否则输则输出出“不存在不存在”提示信息。提示信息。3.6.5 稀疏矩稀疏矩阵压缩阵压缩存存储储方式和方式和简单简单运算运算实实例例第53页，共63页，编辑于2022年，星期六l算法描述算法描述稀疏矩稀疏矩阵阵用二用二维维数数组组A进进行存行存储储；三元三元组组用用结结构体构体B表示；表示；将将数数组组A中中的的非非零零元元素素及及它它所所在在的的行行、列列下下标标按按行行优优先先顺顺序存在到序存在到B中；中；

36、在在B中中查查找找值值为为x的的结结点点，若若存存在在，则则输输出出其其位位置置；否否则则输输出出“不存在不存在”提示信息。提示信息。3.6.5 稀疏矩稀疏矩阵压缩阵压缩存存储储方式和方式和简单简单运算运算实实例例第54页，共63页，编辑于2022年，星期六lC语语言源程序言源程序l#include#define Max 100typedef int Elemtype;typedef struct int i,j;Elemtype v;Pnode;3.6.5 稀疏矩稀疏矩阵压缩阵压缩存存储储方式和方式和简单简单运算运算实实例例第55页，共63页，编辑于2022年，星期六typedef stru

37、ct int rows,cols,terms;Pnode dataMax+1;PMatrix;PMatrix B;3.6.5 稀疏矩稀疏矩阵压缩阵压缩存存储储方式和方式和简单简单运算运算实实例例第56页，共63页，编辑于2022年，星期六void crt_matrix(int AMax,int m,int n)int i,j,k=1;for(i=1;i=m;i+)for(j=1;j=n;j+)if(Aij!=0)B.datak.i=i;B.datak.j=j;B.datak.v=Aij;k+;3.6.5 稀疏矩稀疏矩阵压缩阵压缩存存储储方式和方式和简单简单运算运算实实例例第57页，共63页，编

38、辑于2022年，星期六B.rows=m;B.cols=n;B.terms=k-1;printf(“the Matrix=B:n);printf(“%4d%4d%4dn”,B.rows,B.cols,B.terms);for(i=1;i=B.terms;i+)printf(“%4d%4d%4dn”,B.datai.i,B.datai.j,B.datai.v);3.6.5 稀疏矩稀疏矩阵压缩阵压缩存存储储方式和方式和简单简单运算运算实实例例第58页，共63页，编辑于2022年，星期六int searchval(int x)int flag=0,t=1;while(t=B.terms)if(B.da

39、tat.v=x)printf(“The%d is in row:%2d and col:%2dn”,x,B.datat.i,B.datat.j);flag=1;t+;3.6.5 稀疏矩稀疏矩阵压缩阵压缩存存储储方式和方式和简单简单运算运算实实例例第59页，共63页，编辑于2022年，星期六if(flag)return(1);else printf(“The%d is not in the Matrix-An”,x);return(0);3.6.5 稀疏矩稀疏矩阵压缩阵压缩存存储储方式和方式和简单简单运算运算实实例例第60页，共63页，编辑于2022年，星期六main()int m,n,i,j,

40、x;int aMaxMax;printf(“Please input the Matrix-An”);for(i=1;i=m;i+)for(j=1;j=n;j+)printf(“Please input A%2d%2d:”,i,j);scanf(“%d”,&Aij);3.6.5 稀疏矩稀疏矩阵压缩阵压缩存存储储方式和方式和简单简单运算运算实实例例第61页，共63页，编辑于2022年，星期六printf(“the Matrix-A:n”);for(i=1;i=m;i+)for(j=1;j=n;j+)printf(“%4d”,Aij);printf(“n”);crt_matrix(m,n);printf(“Please input x=”);scanf(“%d”,&x);searchval(x);3.6.5 稀疏矩稀疏矩阵压缩阵压缩存存储储方式和方式和简单简单运算运算实实例例第62页，共63页，编辑于2022年，星期六需要需要补补充！充！习题习题第63页，共63页，编辑于2022年，星期六