算法与数据结构课件串和数组

第4章串和数组4.1串4.2数组4.3典型例题14.1串4.1.1串的根本概念串〔String〕:由零个或多个任意字符组成的字符序列。一般记做：s=“a1a2…an〞〔n≥0〕概念：s为串名“a1a2…an〞为串值例如：s=“YantaiUniversity〞n为串的长度，表示串中包含的字符个数n=0，空串〔NullString〕，记为：Ф假设ai=““，那么称为空格串(blankstring)，n=32子串、主串：串中任意连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。【例】a=“WelcometoBeijing〞b=“Welcome〞c=“Bei〞d=“Welcometo〞长度分别为18、7、3、10；b、c、d都是a的子串；子串的位置：子串的第一个字符在主串中的序号。b在a中的位置是1，c在a中的位置是12，d在a中的位置是1串相等：两个串的长度相等，并且每一个对应字符都相等。3(1)StrLength(s):求串长，返回串s中的字符个数。(2)StrAssign(s1,s2):串赋值，将s2的串值赋值给s1，s1原来的值被覆盖掉。(3)StrConcat(s1,s2):串联接，在s1的后面联接s2的串值，s1改变，s2不改变。(4)SubStr(s,i,len):求子串，返回从串s的第i个字符开始的、长度为len的子串。4.1.2串的根本运算1≤i≤StrLength(s)0≤len≤StrLength(s)-i+1

4(5)StrComp(s1,s2):串比较，假设s1=s2，返回值为0；假设s1＜s2，返回值＜0；假设s1＞s2，返回值＞0。(6)StrIndex(s,t):串定位，返回t在s中首次出现的位置，否那么返回值为-1。(7)StrInsert(s,i,t):串插入，将串t插入到串s的第i个字符位置上，即将t的第一个字符作为s的第i个字符，并返回产生的新串。1≤i≤StrLength(s)+15

(8)StrDelete(s,i,len):串删除，从串s中删去从第i个字符开始的长度为len的子串，并返回产生的新串。(9)StrRep(s,t,r):串替换，用串r替换串s中出现的所有与串t相等的不重叠的子串，s的串值改变。1≤i≤StrLength(s)0≤len≤StrLength(s)-i+16子串定位：StrIndex(s,t)【算法思想】在主串s中取从第i个字符起，长度和串t相等的子串与串t比较，假设相等，那么求得函数值为i，否那么i值增1，直至串s中不存在和串t相等的子串为止。【算法设计】intStrIndex(Strings,Stringt){

return0;

//s中不存在与t相等的子串}//算法结束n=StrLength(s);m=StrLength(t);i=1;while(i<=n-m+1){}//whileStrAssign(sub,SubStr(s,i,m));if(StrComp(sub,t)!=0)++i;elsereturni;7串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。串的根本操作和线性表有很大差异：在线性表的根本操作中，大多以“单个元素〞作为操作对象；而在串的根本操作中，通常以“串的整体〞作为操作对象。总结8串的顺序存储结构:用一组地址连续的存储单元依次存放串中的字符序列。

定长顺序存储结构堆分配存储结构串的链式存储结构(略)块链存储表示4.1.3串的存储结构及其根本运算的实现9定长：按预定义的大小，为每一个串变量分配一个固定长度的存储区。需要事先定义字符串的最大长度。类型定义如下所示：#defineMAXSIZE256chardata[MAXSIZE];【问题】串的实际长度如何表示？1.定长顺序存储结构10(1)类似顺序表，用指针指向最后一个字符。typedefstruct{chardata[MAXSIZE];intcurlen;}SeqString;这种方法可直接得到串的长度：curlen+1(2)在串尾存储一个不会在串中出现的特殊字符作为终结符。这种方法不能直接得到串的长度(3)用数组的0号单元存放串的实际长度。真正的串值从1号单元开始存放11仍以一组地址连续的存储单元存放串的字符序列，但其存储空间是在算法执行过程中动态分配得到的。在C语言中，利用标准函数malloc和free来管理。好处：可以根据具体情况，灵活地申请适当数目的存储空间，从而提高存储资源的利用率。类型定义如下所示：typedefstruct{char*ch；intlen;}HSTRING;2.堆分配存储结构12串结束用‘\0’来标识(1)串联接：把两个串s1和s2首尾联接成一个新串s。intStrConcat1(char*s1,char*s2,char*s){ inti=0,j,len1,len2; len1=StrLength(s1);len2=StrLength(s2);

if(len1+len2>MAXSIZE-1)return0;/*s长度不够*/ j=0;

while(s1[j]!=’\0’){s[i]=s1[j];i++;j++;} j=0;

while(s2[j]!=’\0’){s[i]=s2[j];i++;j++;} s[i]=’\0’; return1;}在第一种顺序存储方式下串的根本运算的实现13intStrSub(char*t,char*s,inti,intlen)/*用t返回串s中第个i字符开始的长度为len的子串1≤i≤串长*/{ intslen; slen=StrLength(s); if(i<1||i>slen||len<0||len>slen-i+1) {printf(＂参数不对＂);return0;}

for(j=0;j<len;j++) t[j]=s[i+j-1]; t[j]=’\0’; return1;}(2)求子串14intStrComp(char*s1,char*s2){ inti=0;

while(s1[i]!=’\0’&&s2[i]!=’\0’&&s1[i]==s2[i]) i++; return(s1[i]-s2[i]);}(3)串比较15第2次上机文电122-1〔53人〕6-16周双204机房文通124-1〔31人靠窗〕、124-2〔33人〕6-16周双205机房实验1线性表的根本操作实验2链表的根本操作16(4)子串定位intStrIndex(char*s,char*t){ inti=0,j=0;

while(s[i]!=‘\0’&&t[j]!=‘\0’) if(s[i]==t[j]){++i;++j;} else{i=i-j+1;j=0;} if(t[j]==‘\0’)returni-j; elsereturn-1;}17184.2数组高级语言中的数组intA[10];charB[4][5];数组是由类型相同的数据元素构成的有序集合，每个元素称为一个数组元素；每个元素受n(n>=1)个线性关系的约束，每个元素在n个线性关系中的序号i1,i2,…,in称为该元素的下标，可以通过下标访问该数据元素；19二维数组的定义inta[2][3];//声明A为整型数组类型typedefintA[3];//定义类型为A的一维数组变量aAa[2];两个变量组成的一个数组，其中每一个变量都是数组a[0][1]a[0][0]a[1][2]a[1][1]a[1][0]a[0][2]a[0]a[1]20结论二维数组是一个特殊的一维数组，其每个数据元素又是一个一维数组。二维数组是一个特殊的线性表，其每个数据元素又是一个线性表。任何多维数组都可以看作一个线性表，线性表中的每个数据元素又是一个线性表。数组是线性表的推广。21数组的逻辑结构和根本操作22数组的操作数组中的数据元素数目固定。一旦定义了一个数组，其数据元素数目不再有增减变化。数组上一般不做插入和删除操作。数组操作的特点:1)只有引用型操作，没有加工型操作;2)取值操作：给定一组下标，读取对应的数据元素。赋值操作：给定一组下标，存储或修改与其对应的数据元素。适合顺序存储23一维数组中，一旦a1的存储地址LOC(a1)确定，并假设每个数据元素占用L个存储单元，那么任一数据元素ai的存储地址LOC(ai)就可由以下公式求出：LOC(ai)=LOC(a1)+(i-1)*L(0≤i≤n)可见，一维数组中任一数据元素的存储地址可直接计算得到。一维数组中任一数据元素可直接存取，是一种随机存储的结构。一维数组的存储24矛盾：计算机的存储结构是线性的、一维的。问题：如何用线性的存储结构存放二维数组的元素？解决方法：1〕以行序为主序存储：先存储第1行，然后紧接着存储第2行，最后存储第m行；2〕以列序为主序存储：先存储第1列，然后紧接着存储第2列，最后存储第n列；二维数组的存储25数组a[2][3]的顺序存储a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2行序为主序a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2列序为主序26设二维数组A是：A[c1..d1,c2..d2](c1≤i≤d1,c2≤j≤d2)其中c1、c2和d1、d2分别为二维数组A的边界的下界和上界，每个数组元素占用L个存储单元LOC(i,j)=LOC(c1,c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*L

二维数组的存储27对二维数组floata[5][4]计算：(1)数组a中的数组元素数目；(2)假设数组a的起始地址为2000，且每个数组元素长度为32位(即4个字节)，数组元素a[3][2]的内存地址。解：该数组的元素数目共有5*4=20个。由于C语言采用行序为主序的存储方式，那么有：LOC(a3,2)=LOC(a0,0)+(i*n+j)*k=2000+(3*4+2)*4=2056举例28矩阵的压缩存储矩阵是在很多科学与工程计算中遇到的数学模型。数学上矩阵的定义：一个由s×n个元素排成的s行〔横向〕n列〔纵向〕的表。当矩阵的阶数较高，而且矩阵中的一些元素有特殊的性质时，可以采用节省空间的存储方法压缩存储对多个值相同的元素只分配一个存储空间，零元素不分配空间矩阵需要有特殊性：特殊矩阵：值相同的元素或零元素按规律分布；稀疏矩阵：非零元素少且分布无规律；294.2.3稀疏矩阵非零元素较少，分布无规律稀疏因子：δ=t/(m*n)<=0.05由于分布无规律，存放非零元素必须同时存放其在矩阵中的位置，即下标和值一起存放一个三元组唯一确定了稀疏矩阵中的一个非零元素那么对应的三元组线性表为：((1,3,1),(2,2,2),(3,1,3),(4,4,5),(5,5,6),(6,6,7),(6,7,4))30稀疏矩阵的存储结构三元组线性表：((1,3,1),(2,2,2),(3,1,3),(4,4,5),(5,5,6),(6,6,7),(6,7,4))顺序存储结构－－三元组顺序表链式存储结构－－十字链表〔略〕311.稀疏矩阵的三元组表存储32defineSMAX1024/*一个足够大的数*/typedefstruct{inti,j;/*非零元素的行、列*/datatypev;/*非零元素值*/}SPNode;/*三元组类型*/typedefstruct{intmu,nu,tu;/*矩阵的行、列及非零元素的个数*/SPNodedata[SMAX];/*三元组表*/}SPMatrix;/*三元组表的存储类型*/三元组顺序表下面的讨论假设按行有序存储。33设A为一个m×n的稀疏矩阵，那么其转置矩阵B就是一个n×m的稀疏矩阵。且满足ai,j=bj,i,其中1≤i≤m,1≤j≤n。rcd01605-223-831335740-12429rcd04-1210613324932-850-25372.稀疏矩阵的转置运算34稀疏矩阵的转置求一个矩阵的转置矩阵可以经过以下步骤来完成：将矩阵的行列值互换；对每个三元组所表示的非零元，将该元素的行、列值互换；按行序重排三元组。35稀疏矩阵的转置

如何实现按行序重排三元组？在A的三元组表A.data中从前至后依次找出第0列的所有元素，也就是B的第0行的元素，将其按找到的顺序放入B的三元组表B.data中。在A中：在B中：以上是第0列的处理，依次处理第1列…..第n-1列36voidTransM1(SPMatrix*A){ SPMatrix*B; intp,q,col; B=malloc(sizeof(SPMatrix)); B->mu=A->nu;B->nu=A->mu;B->tu=A->tu; if(B->tu>0) { q=0; for(col=1;col<=(A->nu);col++) for(p=1;p<=(A->tu);p++) if(A->data[p].j==col)

{ B->data[q].i=A->data[p].j;//B的行为A的列 B->data[q].j=A->data[p].i;//B的列为A的行 B->data[q].v=A->data[p].v; q++; } } returnB;}3738用num数组记录矩阵A中每列的非0元素个数3.稀疏矩阵转置的改进算法思想：在扫描三元组表A.data的过程中，每遇到一个三元组，就将它的行列值交换并放在三元组表B.data的正确位置上。因此，需要求出矩阵A中每列第一个非零元在B.data中的位置。cpot[1]=1cpot[col]=cpot[col-1]+num[col-1]2≤col≤n

j123456num[j]121102cpot[j]124566矩阵A的num和cpot向量的值:39SPMatrix*TransM2(SPMatrix*A){∥三元组表上实现矩阵的快速转置的算法

SPMatrix*B;inti,j,k,num[n+1],cpot[n+1];B=malloc(sizeof(SPMatrix));B->mu=A->nu;B->nu=A->mu;B->tu=A->tu;if(B->tu>0){for(i=1;i<=A->nu;i++)∥矩阵A每一列非零元个数初始化为零 num[i]=0;for(i=1;i<=A->tu;i++)∥求矩阵A每一列的非零元个数{j=A->data[i].j;num[j]++;} cpot[1]=1; for(i=2;i<=A->nu;i++)

∥求A.data第j列第一个非零元在B.data中的序号cpot[i]=cpot[i-1]+num[i-1];稀疏矩阵的快速转置算法40

for(i=1;i<=A->tu;i++)∥求转置矩阵B的三元组表{j=A->data[i].j;k=cpot[j];B->data[k].i=A->data[i].j; B->data[k].j=A->data[i].i; B->data[k].v=A->data[i].v;cpot[j]++;}}returnB;}

时间复杂度为：O(A.n+A.len);稀疏矩阵的快速转置算法414.2.4矩阵的其他运算举例例４.2假设矩阵Am×n中存在某个元素aij满足：aij是第i行中最小值且是第j列中的最大值，那么称该元素为矩阵A的一个鞍点。试编写一个算法，找出A中的所有鞍点。根本思想：在矩阵A中求出每一行的最小值元素，然后判断该元素是否是它所在列中的最大值，是那么打印出，接着处理下一行。42voidsaddle(intA[][],intm,intn)/*