数据结构-串和数组.ppt

3.6 其他线性结构,串(String)是由零个或多个字符组成的有限序列。一般记为:S=a1 a2.an(n0)其中，S是串的名，用单引号括起来的字符序列是串的值；ai(1in)可以是字母、数字或其它字符，串中字符的数目n称为串的长度。n=0的串称为空串(null string)。,3.6.1 串的定义和串的存储方式概念,串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。当两个串的长度相等，并且各个对应位置上的字符都相等时，称两个串相等。,3.6.1 串的定义和串的存储方式概念,例：串名为A、B、C、D的四个串如下：A=very good；长度为9，是D的主串；B=；长度为3；C=；长度为0（空串）；D=good；长度为4，是A的子串。D在A中的位置是6。,3.6.1 串的定义和串的存储方式概念,(1)赋值操作：StrAssign(S，chars)初始条件：chars是字符串常量；操作结果：生成一个值等于chars的字符串S；(2)插入操作：StrInsert(S，pos，T)初始条件：字符串S、T存在，1pos StrLength(S)+1；操作结果：在字符串S的第pos个字符之前插入串T。,3.6.1 串的定义和串的存储方式基本操作,(3)删除操作：StrDelete(S，pos，len)初始条件：字符串S存在，1pos StrLength(S)-len+1；操作结果：从字符串S中删除第pos个字符起长度为len的子串。(4)复制操作：StrCopy(S，T)初始条件：字符串S存在；操作结果：将字符串S的内容复制到串T。,3.6.1 串的定义和串的存储方式基本操作,(5)判空操作：StrEmpty(S)初始条件：字符串S存在；操作结果：若S为空串，则返回TRUE，否则返回FALSE。(6)比较操作：StrCompare(S，T)初始条件：字符串S、T存在；操作结果：若ST，则返回值0；若S=T，则返回值=0；若ST，则返回值0。,3.6.1 串的定义和串的存储方式基本操作,(7)求串长操作：StrLength(S)初始条件：字符串S存在；操作结果：返回字符串S的长度，即串S中字符的个数。(8)置空操作：StrClear(S)初始条件：字符串S存在；操作结果：将字符串S清为空串。,3.6.1 串的定义和串的存储方式基本操作,(9)联接操作：StrCat(S，T)初始条件：字符串S、T存在；操作结果：将字符串T的值连接在S的后面。(10)求子串操作：SubString(Sub，S，pos，len)初始条件：字符串S存在，1posStrLength(S)且1lenStrLength(S)-pos+1；操作结果：用Sub返回字符串S的第pos个字符开始长度为len的子串。,3.6.1 串的定义和串的存储方式基本操作,(11)定位操作：StrIndex(S，pos，T)初始条件：字符串S、T存在，T非空，1posStrLength(S)；操作结果：若字符串S中存在与T相等的子串，则返回它在字符串S中第pos个字符之后第一次出现的位置；否则返回0。(7)置换操作：StrReplace(S，T，V)初始条件：字符串S、T、V存在，T非空；操作结果：用V替换字符串S中出现的所有与T相等的不重叠的子串。,3.6.1 串的定义和串的存储方式基本操作,(13)释放操作：StrDestroy(S)初始条件：字符串S存在；操作结果：销毁字符串S。,3.6.1 串的定义和串的存储方式基本操作,串的两种基本存储结构：顺序存储结构和链式存储结构。定长顺序串：当串的长度基本固定时，主要考虑采用顺序存储结构实现。其C语言描述如下：#define Maxlen 20/串的最大长度typedef struct/串的定义char chMaxlen;int len;/串的长度 Sstring；,3.6.1 串的定义和串的存储方式串的存储结构,在进行串的插入时：插入位置pos将原字符串划分为两部分(分别假设为A和B，长度分别为LA和LB)；待插入字符串假设为C，其长度为LC；插入过程可能出现下列三种情况：1)插入后串的总长度为LA+LB+LC Maxlen；2)插入后串的总长度Maxlen，且pos+LCMaxlen，且pos+LCMaxlen；,3.6.2 定长顺序串运算插入算法分析,/*在串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-)s-chi=s-chi-t.len;for(i=0;ichi+pos=t.chi;s-len=s-len+t.len;,3.6.2 定长顺序串运算插入算法实现,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.chi;s-len=Maxlen;return(1);,3.6.2 定长顺序串运算插入算法实现,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 定长顺序串运算删除算法实现,在进行串的连接时：假设原字符串为A，长度为LA；待连接串假设为B，其长度为LB；连接过程可能出现下列三种情况：1)连接后串的总长度为LA+LB Maxlen；2)连接后串的总长度Maxlen，且LAMaxlen，LA=Maxlen；,3.6.2 定长顺序串运算连接算法分析,/*将串t连接在串s的后面*/int StrCat(SString*s,SString t)int i,flag;if(s-len+t.lenlen;ilen+t.len;i+)s-chi=t.chi-s-len;s-len=s-len+t.len;flag=1;,3.6.2 定长顺序串运算连接算法实现,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 定长顺序串运算连接算法实现,数组(array)可看成是线性表的推广，是最常用的数据结构之一。数组是有限个数组元素的集合，元素数目固定；数组的每个元素与一组下标相对应，数组元素的下标关系具有上下界的约束且下标有序；数组中所有数组元素的数据类型必须一致；数组的两种基本运算：给定下标，存取相应的数据元素；给定下标，修改相应的数据元素。,3.6.3 二维数组的结构特点和存储方式定义,一个m行n列的二维数组(也称为矩阵)，记作Am,n。,3.6.3 二维数组的结构特点和存储方式定义,A=,a11 a12.a1n a21 a22.a2n am1 am2.amn,按行优先顺序存储对于上述二维数组A而言，可以将其看成是由m个行向量组成的向量，即：Amn=(a11，.，a1n)，(a21，.，a2n)，.，(am1，.，amn)这种行向量表相当于一个线性表。行优先顺序存储就是数组元素按行向量表次序进行存储，即第i+1个行表紧跟在第i个行表后面进行存储。,3.6.3 二维数组的结构特点和存储方式存储结构,当把n维数组的元素按行优先顺序地存放在存储器里，则每个元素的存储地址可以用公式计算出来。这个计算公式称为“地址公式”。假设每个数据元素占c个存储单元，则上述二维数组Amn的地址公式为：Loc(aij)=Loc(a11)+(i-1)*n+(j-1)*c(1im，1jn),3.6.3 二维数组的结构特点和存储方式存储结构,按列优先顺序存储对于上述二维数组A而言，也可以将其看成是由n个列向量组成的向量，即：Amn=(a11，.，am1)，(a12，.，am2)，.，(a1n，.，amn)这种列向量表也相当于一个线性表。列优先顺序存储就是数组元素按列向量表次序进行存储，即第i+1个列表紧跟在第i个列表后面进行存储。,3.6.3 二维数组的结构特点和存储方式存储结构,当把n维数组的元素按列优先顺序地存放在存储器里，并假设每个数据元素占c个存储单元，则上述二维数组Amn的地址公式为：Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*c(1im，1jn),3.6.3 二维数组的结构特点和存储方式存储结构,根据二维数组的特性可以推出：一个三维数组可以用其数据元素为二维数组的线性表来定义；依次类推，n维数组是由数据元素为n-1维数组的线性表构成。因此，对n维数组也有上述两种不同顺序分配的存储结构。当把n维数组的元素这样顺序地存放在存储器里，则每个元素的存储地址都可以用“地址公式”计算出来。,3.6.3 二维数组的结构特点和存储方式存储结构,在C语言中，可以把一个二维数组看作是一种特殊的一维数组，该一维数组的元素又是一个一维数组。例如定义：int a34；其中，可以把a看作是一个一维数组，它有3个元素：a0、a1、a2，每个元素又是一个包含4个元素的一维数组。,3.6.3 二维数组的结构特点和存储方式示例,通常在实际计算中经常出现一些阶数很高的矩阵，且矩阵中有许多值相同的元素或者零元素。为了节省存储空间，可以对这类矩阵进行压缩存储。所谓压缩存储是指：为多个值相同的元素只分配一个存储空间；对零元素不分配空间。,3.6.3 二维数组的结构特点特殊矩阵的存储方式,下三角矩阵的存储方式：设下三角矩阵为Ann，满足：,3.6.3 二维数组的结构特点特殊矩阵的存储方式,A=,a11 0 0 a21 a22 0 an1 an2 ann,若将其中的非零元素按行优先顺序存放为：则一维数组Sak和矩阵元素aij之间存在着一一对应关系：(1ji n),3.6.3 二维数组的结构特点特殊矩阵的存储方式,k=,+j,假设每个数据元素占用一个字节的存储单元，则下三角矩阵的地址公式为：,3.6.3 二维数组的结构特点特殊矩阵的存储方式,Loc(aij)=Loc(a11)+i(i1)/2+(j1),三对角矩阵的存储方式：设三对角矩阵为Ann，满足：,3.6.3 二维数组的结构特点特殊矩阵的存储方式,A=,a11 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,若将其中的非零元素按行优先顺序存放，假设每个数据元素占用一个字节的存储单元，则三对角矩阵的地址公式为：,3.6.3 二维数组的结构特点特殊矩阵的存储方式,Loc(aij)=Loc(a11)+2(i1)+(j1)其中：i=1,j=1,2 或：i=n,j=n-1,n 或：1in,j=i-1,i,i+1,对称矩阵的存储方式：解决方案类似于下三角矩阵的存储。,3.6.3 二维数组的结构特点特殊矩阵的存储方式,稀疏矩阵：如果一个矩阵中大多数元素为零，非零元素较少且分布无一定规律，则称之为稀疏矩阵。顺序存储：三元组表：线性表中的每个结点由三个字段组成，分别是该非零元素的行下标、列下标和值。,3.6.3 二维数组的结构特点特殊矩阵的存储方式,稀疏矩阵的C语言表示：#define smax 16/*最大非零元素个数*/typedef int datatype;typedef struct int i,j;/*行号，列号*/datatype v;/*元素值*/node;,3.6.3 二维数组的结构特点特殊矩阵的存储方式,稀疏矩阵的C语言表示：typedef struct int m,n,t;/*行数，列数，非零元素个数*/node datasmax;/*三元组表*/spmatrix;/*稀疏矩阵类型*/,3.6.3 二维数组的结构特点特殊矩阵的存储方式,稀疏矩阵举例：非零元素按行优先顺序存储。,3.6.3 二维数组的结构特点特殊矩阵的存储方式,该稀疏矩阵共有20个元素，仅有6个非零元素。其三元组表如下图所示。,3.6.3 二维数组的结构特点特殊矩阵的存储方式,伪地址表示法：伪地址是指本元素在矩阵中按行优先顺序的相对位置，上述稀疏矩阵A中非零元素为：5，8，1，3，-2，6非零元素的伪地址=n*i+j，n为矩阵的列数。因此，5的伪地址为1；1的伪地址为5；。,3.6.3 二维数组的结构特点特殊矩阵的存储方式,稀疏矩阵的转置运算：一般矩阵的转置算法为：for(col=0;coln;col+)for(row=0;rowm;row+)Bcolrow=Arowcol;由于稀疏矩阵含有大量的零元素，因此，其转置算法修改为如下所示：,3.6.3 二维数组的结构特点特殊矩阵的存储方式,spmatrix TRANSMAT(spmatrix a)/*返回稀疏矩阵A的转置*/int ano,bno,col;/*ano和bno分别指示a-data和b-data中结点序号；col指示*a的列号，即*b的行号*/pmatrix*b;/*存放转置后的矩阵*/b=malloc(sizeof(spmatrix);b-m=a-n;b-n=a-m;/*行列数交换*/b-t=a-t;,3.6.3 二维数组的结构特点特殊矩阵的存储方式,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.i;b-databno.v=a-dataano.v;,3.6.3 二维数组的结构特点特殊矩阵的存储方式,bno+;/*b-data结点序号加1*/return b;/*返回转置结果指针*/*TRANSMAT*/,3.6.3 二维数组的结构特点特殊矩阵的存储方式,该算法的时间主要耗费在col和ano的二重循环上，若A的列数为n，非零元素个数为t，则执行时间为(nt)，即与的列数和非零元素个数的乘积成正比。而通常用二维数组表示矩阵时，其转置算法的执行时间是(mn)。由于非零元素个数一般远远大于行数，因此，上述稀疏矩阵转置算法虽然节省了空间，但增加了转置的时间。,3.6.3 二维数组的结构特点特殊矩阵的存储方式,链式存储结构：带行指针向量的单链表表示。行指针向量 列值,3.6.3 二维数组的结构特点特殊矩阵的存储方式,十字链表结构：,3.6.3 二维数组的结构特点特殊矩阵的存储方式,设已知一个nn的上三角矩阵X，其上三角元素已按行序为主序连续存放在数组Y中。请设计一个tran函数，将数组Y中元素按列为主序连续存放在数组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,根据已知条件：Y=(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)期望得到的结果：Z=(1,2,6,3,7,10,4,8,11,13,5,9,12,14,15)解题思路：用i和j表示矩阵X中元素的行和列下标。用k表示数组Y中元素的下标。初始值设为：i=1,j=1,k=1；将yk=xi,j元素存放在zj*(j-1)/2+i中，且当一行没有结束时j+，否则i+并修改下一行元素的个数及i和j的值，直到k=n(n+1)/2为止。,3.6.4 应用实例算法分析,#include#define N 5void 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)/2+i=yk;if(count=step)step-;count=0;i+;j=i;elsej+;,3.6.4 应用实例算法实现,main()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”,3.6.4 应用实例算法实现,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”);,3.6.4 应用实例算法实现,问题描述 输入一个稀疏矩阵，要求：将其转化为三元组的表示形式；在三元组存储矩阵中查找值为x的结点，若x存在，则输出其位置，否则输出“不存在”提示信息。,3.6.5 稀疏矩阵压缩存储方式和简单运算实例,算法描述稀疏矩阵用二维数组A进行存储；三元组用结构体B表示；将数组A中的非零元素及它所在的行、列下标按行优先顺序存在到B中；在B中查找值为x的结点，若存在，则输出其位置；否则输出“不存在”提示信息。,3.6.5 稀疏矩阵压缩存储方式和简单运算实例,C语言源程序#include#define Max 100typedef int Elemtype;typedef struct int i,j;Elemtype v;Pnode;,3.6.5 稀疏矩阵压缩存储方式和简单运算实例,typedef struct int rows,cols,terms;Pnode dataMax+1;PMatrix;PMatrix B;,3.6.5 稀疏矩阵压缩存储方式和简单运算实例,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 稀疏矩阵压缩存储方式和简单运算实例,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 稀疏矩阵压缩存储方式和简单运算实例,int searchval(int x)int flag=0,t=1;while(t=B.terms)if(B.datat.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 稀疏矩阵压缩存储方式和简单运算实例,if(flag)return(1);else printf(“The%d is not in the Matrix-An”,x);return(0);,3.6.5 稀疏矩阵压缩存储方式和简单运算实例,main()int m,n,i,j,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”,3.6.5 稀疏矩阵压缩存储方式和简单运算实例,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”,3.6.5 稀疏矩阵压缩存储方式和简单运算实例,需要补充！,习题,