数据结构串和数组

数据结构串和数组第1页，共63页，2023年，2月20日，星期六串(String)是由零个或多个字符组成的有限序列。一般记为: S='a1a2...an' (n≥0)其中，S是串的名，用单引号括起来的字符序列是串的值；ai(1≤i≤n)可以是字母、数字或其它字符，串中字符的数目n称为串的长度。n=0的串称为空串(nullstring)。3.6.1串的定义和串的存储方式—概念第2页，共63页，2023年，2月20日，星期六串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。当两个串的长度相等，并且各个对应位置上的字符都相等时，称两个串相等。3.6.1串的定义和串的存储方式—概念第3页，共63页，2023年，2月20日，星期六例：串名为A、B、C、D的四个串如下：A='verygood'； 长度为9，是D的主串；B=''； 长度为3；C=''； 长度为0（空串）；D='good'； 长度为4，是A的子串。D在A中的位置是6。3.6.1串的定义和串的存储方式—概念第4页，共63页，2023年，2月20日，星期六

(1)赋值操作：StrAssign(S，chars)

初始条件：chars是字符串常量；

操作结果：生成一个值等于chars的字符串S；(2)插入操作：StrInsert(S，pos，T)

初始条件：字符串S、T存在， 1≤pos≤StrLength(S)+1；

操作结果：在字符串S的第pos个字符之前插入串T。3.6.1串的定义和串的存储方式—基本操作第5页，共63页，2023年，2月20日，星期六(3)删除操作：StrDelete(S，pos，len) 初始条件：字符串S存在， 1≤pos≤StrLength(S)-len+1； 操作结果：从字符串S中删除第pos个字符起长度为len的子串。(4)复制操作：StrCopy(S，T) 初始条件：字符串S存在； 操作结果：将字符串S的内容复制到串T。3.6.1串的定义和串的存储方式—基本操作第6页，共63页，2023年，2月20日，星期六(5)判空操作：StrEmpty(S)

初始条件：字符串S存在；

操作结果：若S为空串，则返回TRUE，否则返回FALSE。(6)比较操作：StrCompare(S，T)

初始条件：字符串S、T存在；

操作结果：若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0。3.6.1串的定义和串的存储方式—基本操作第7页，共63页，2023年，2月20日，星期六(7)求串长操作：StrLength(S) 初始条件：字符串S存在； 操作结果：返回字符串S的长度，即串S中字符的个数。(8)置空操作：StrClear(S) 初始条件：字符串S存在； 操作结果：将字符串S清为空串。3.6.1串的定义和串的存储方式—基本操作第8页，共63页，2023年，2月20日，星期六(9)联接操作：StrCat(S，T) 初始条件：字符串S、T存在； 操作结果：将字符串T的值连接在S的后面。(10)求子串操作：SubString(Sub，S，pos，len) 初始条件：字符串S存在， 1≤pos≤StrLength(S) 且1≤len≤StrLength(S)-pos+1； 操作结果：用Sub返回字符串S的第pos个字符开始长度为len的子串。3.6.1串的定义和串的存储方式—基本操作第9页，共63页，2023年，2月20日，星期六(11)定位操作：StrIndex(S，pos，T) 初始条件：字符串S、T存在，T非空， 1≤pos≤StrLength(S)； 操作结果：若字符串S中存在与T相等的子串，则返回它在字符串S中第pos个字符之后第一次出现的位置；否则返回0。(7)置换操作：StrReplace(S，T，V) 初始条件：字符串S、T、V存在，T非空； 操作结果：用V替换字符串S中出现的所有与T相等的不重叠的子串。3.6.1串的定义和串的存储方式—基本操作第10页，共63页，2023年，2月20日，星期六(13)释放操作：StrDestroy(S) 初始条件：字符串S存在； 操作结果：销毁字符串S。3.6.1串的定义和串的存储方式—基本操作第11页，共63页，2023年，2月20日，星期六串的两种基本存储结构：顺序存储结构和链式存储结构。定长顺序串：当串的长度基本固定时，主要考虑采用顺序存储结构实现。其C语言描述如下： #define

Maxlen

20 //串的最大长度 typedef

struct

{ //串的定义 charch[Maxlen]; intlen; //串的长度 }

Sstring；3.6.1串的定义和串的存储方式—串的存储结构第12页，共63页，2023年，2月20日，星期六在进行串的插入时：插入位置pos将原字符串划分为两部分(分别假设为A和B，长度分别为LA和LB)；待插入字符串假设为C，其长度为LC；插入过程可能出现下列三种情况：

1)插入后串的总长度为LA+LB+LC≤Maxlen；

2)插入后串的总长度>Maxlen，且pos+LC<Maxlen；3)插入后串的总长度>Maxlen，且pos+LC>Maxlen；3.6.2定长顺序串运算—插入算法分析第13页，共63页，2023年，2月20日，星期六/*在串s中序号为pos的字符之前插入串t*/int

StrInsert(SString*s,intpos,SStringt){

int

i;if(pos<0||pos>s->len)

return(0); /*插入位置不合法*/

if(s->len+t.len<=Maxlen){

/*插入后串长≤Maxlen*/

for(i=s->len+t.len-1;i>=t.len+pos;i--) s->ch[i]=s->ch[i-t.len];for(i=0;i<t.len;i++)s->ch[i+pos]=t.ch[i];s->len=s->len+t.len;}3.6.2定长顺序串运算—插入算法实现第14页，共63页，2023年，2月20日，星期六elseif(pos+t.len<=Maxlen){/*插入后串长>Maxlen，

但串t的字符序列可以全部插入*/

for(i=Maxlen-1;i>=t.len+pos;i--) s->ch[i]=s->ch[i-t.len];for(i=0;i<t.len;i++)s->ch[i+pos]=t.ch[i];s->len=Maxlen;}else{ /*串t的部分字符序列要舍弃*/

for(i=0;i<Maxlen-pos;i++)s->ch[i+pos]=t.ch[i];s->len=Maxlen;}return(1);}3.6.2定长顺序串运算—插入算法实现第15页，共63页，2023年，2月20日，星期六intStrDelete(SString*s,intpos,intlen){if(pos<0||pos>(s->len-len))return(0);for(i=pos+len;i<s->len;i++) s->ch[i-len]=s->ch[i];s->len=s->len-len;return(1);}3.6.2定长顺序串运算—删除算法实现第16页，共63页，2023年，2月20日，星期六在进行串的连接时：假设原字符串为A，长度为LA；待连接串假设为B，其长度为LB；连接过程可能出现下列三种情况：

1)连接后串的总长度为LA+LB≤Maxlen；

2)连接后串的总长度>Maxlen，且LA<Maxlen；3)连接后串的总长度>Maxlen，LA=Maxlen；3.6.2定长顺序串运算—连接算法分析第17页，共63页，2023年，2月20日，星期六/*将串t连接在串s的后面*/int

StrCat(SString*s,SStringt){

int

i,flag;if(s->len+t.len<=Maxlen){

/*连接后串长≤Maxlen*/

for(i=s->len;i<s->len+t.len;i++) s->ch[i]=t.ch[i-s->len];s->len=s->len+t.len;flag=1;}3.6.2定长顺序串运算—连接算法实现第18页，共63页，2023年，2月20日，星期六elseif(s->len<Maxlen){/*连接后串长>Maxlen，

但串s的长度<Maxlen*/

for(i=s->len;i<Maxlen;i++) s->ch[i]=t.ch[i-s->len];s->len=Maxlen;flag=0;}elseflag=0;/*串s的长度=Maxlen，串t不被连接*/return(flag);}3.6.2定长顺序串运算—连接算法实现第19页，共63页，2023年，2月20日，星期六数组(array)可看成是线性表的推广，是最常用的数据结构之一。数组是有限个数组元素的集合，元素数目固定；数组的每个元素与一组下标相对应，数组元素的下标关系具有上下界的约束且下标有序；数组中所有数组元素的数据类型必须一致；数组的两种基本运算：给定下标，存取相应的数据元素；给定下标，修改相应的数据元素。3.6.3二维数组的结构特点和存储方式—定义第20页，共63页，2023年，2月20日，星期六一个m行n列的二维数组(也称为矩阵)，记作A[m,n]。3.6.3二维数组的结构特点和存储方式—定义A=a11a12...a1na21a22...a2n……am1am2...amn

第21页，共63页，2023年，2月20日，星期六按行优先顺序存储 对于上述二维数组A而言，可以将其看成是由m个行向量组成的向量，即： Am×n=((a11，...，a1n)，(a21，...，a2n)，...，(am1，...，amn)) 这种行向量表相当于一个线性表。 行优先顺序存储就是数组元素按行向量表次序进行存储，即第i+1个行表紧跟在第i个行表后面进行存储。3.6.3二维数组的结构特点和存储方式—存储结构第22页，共63页，2023年，2月20日，星期六 当把n维数组的元素按行优先顺序地存放在存储器里，则每个元素的存储地址可以用公式计算出来。这个计算公式称为“地址公式”。 假设每个数据元素占c个存储单元，则上述二维数组Am×n的地址公式为： Loc(aij)=Loc(a11)+[(i-1)*n+(j-1)]*c (1≤i≤m，1≤j≤n)3.6.3二维数组的结构特点和存储方式—存储结构第23页，共63页，2023年，2月20日，星期六按列优先顺序存储 对于上述二维数组A而言，也可以将其看成是由n个列向量组成的向量，即： Am×n=((a11，...，am1)，(a12，...，am2)，...，(a1n，...，amn)) 这种列向量表也相当于一个线性表。 列优先顺序存储就是数组元素按列向量表次序进行存储，即第i+1个列表紧跟在第i个列表后面进行存储。3.6.3二维数组的结构特点和存储方式—存储结构第24页，共63页，2023年，2月20日，星期六 当把n维数组的元素按列优先顺序地存放在存储器里，并假设每个数据元素占c个存储单元，则上述二维数组Am×n的地址公式为： Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*c (1≤i≤m，1≤j≤n)3.6.3二维数组的结构特点和存储方式—存储结构第25页，共63页，2023年，2月20日，星期六 根据二维数组的特性可以推出：一个三维数组可以用其数据元素为二维数组的线性表来定义；依次类推，n维数组是由数据元素为n-1维数组的线性表构成。 因此，对n维数组也有上述两种不同顺序分配的存储结构。当把n维数组的元素这样顺序地存放在存储器里，则每个元素的存储地址都可以用“地址公式”计算出来。3.6.3二维数组的结构特点和存储方式—存储结构第26页，共63页，2023年，2月20日，星期六在C语言中，可以把一个二维数组看作是一种特殊的一维数组，该一维数组的元素又是一个一维数组。例如定义：inta[3][4]；其中，可以把a看作是一个一维数组，它有3个元素：a[0]、a[1]、a[2]，每个元素又是一个包含4个元素的一维数组。3.6.3二维数组的结构特点和存储方式—示例第27页，共63页，2023年，2月20日，星期六通常在实际计算中经常出现一些阶数很高的矩阵，且矩阵中有许多值相同的元素或者零元素。为了节省存储空间，可以对这类矩阵进行压缩存储。所谓压缩存储是指：为多个值相同的元素只分配一个存储空间；对零元素不分配空间。3.6.3二维数组的结构特点—特殊矩阵的存储方式第28页，共63页，2023年，2月20日，星期六下三角矩阵的存储方式： 设下三角矩阵为An×n，满足：3.6.3二维数组的结构特点—特殊矩阵的存储方式A=a110 …0a21a22…0

……an1an2…ann

第29页，共63页，2023年，2月20日，星期六 若将其中的非零元素按行优先顺序存放为： 则一维数组Sa[k]和矩阵元素aij之间存在着一一对应关系： (1≤j≤i≤n)3.6.3二维数组的结构特点—特殊矩阵的存储方式k=+j第30页，共63页，2023年，2月20日，星期六假设每个数据元素占用一个字节的存储单元，则下三角矩阵的地址公式为：3.6.3二维数组的结构特点—特殊矩阵的存储方式Loc(aij)=Loc(a11)+i(i−1)/2+(j−1)第31页，共63页，2023年，2月20日，星期六三对角矩阵的存储方式： 设三对角矩阵为An×n，满足：3.6.3二维数组的结构特点—特殊矩阵的存储方式A=a11a12

0 ………………0a21a22a230……………00

a32a33

a34

0…………0…………00……………an-1,n-2an-1,n-1an-1,n

00……………0an,n-1ann

第32页，共63页，2023年，2月20日，星期六 若将其中的非零元素按行优先顺序存放，假设每个数据元素占用一个字节的存储单元，则三对角矩阵的地址公式为：3.6.3二维数组的结构特点—特殊矩阵的存储方式Loc(aij)=Loc(a11)+2(i−1)+(j−1)

其中：i=1,j=1,2

或：i=n,j=n-1,n

或：1<i<n,j=i-1,i,i+1第33页，共63页，2023年，2月20日，星期六对称矩阵的存储方式： 解决方案类似于下三角矩阵的存储。3.6.3二维数组的结构特点—特殊矩阵的存储方式第34页，共63页，2023年，2月20日，星期六稀疏矩阵：

如果一个矩阵中大多数元素为零，非零元素较少且分布无一定规律，则称之为稀疏矩阵。顺序存储：三元组表：线性表中的每个结点由三个字段组成，分别是该非零元素的行下标、列下标和值。3.6.3二维数组的结构特点—特殊矩阵的存储方式第35页，共63页，2023年，2月20日，星期六 稀疏矩阵的C语言表示： #definesmax16 /*最大非零元素个数*/ typedefintdatatype; typedefstruct{ inti,j; /*行号，列号*/ datatypev; /*元素值*/ }node;3.6.3二维数组的结构特点—特殊矩阵的存储方式第36页，共63页，2023年，2月20日，星期六 稀疏矩阵的C语言表示： typedefstruct{ intm,n,t; /*行数，列数，非零元素个数*/ nodedata[smax]; /*三元组表*/ }spmatrix; /*稀疏矩阵类型*/3.6.3二维数组的结构特点—特殊矩阵的存储方式第37页，共63页，2023年，2月20日，星期六 稀疏矩阵举例：非零元素按行优先顺序存储。3.6.3二维数组的结构特点—特殊矩阵的存储方式第38页，共63页，2023年，2月20日，星期六 该稀疏矩阵共有20个元素，仅有6个非零元素。其三元组表如下图所示。3.6.3二维数组的结构特点—特殊矩阵的存储方式m=4n=5t=6行号域列号域值域1015204831014123521-26306第39页，共63页，2023年，2月20日，星期六伪地址表示法： 伪地址是指本元素在矩阵中按行优先顺序的相对位置，上述稀疏矩阵A中非零元素为： {5，8，1，3，-2，6} 非零元素的伪地址=n*i+j，n为矩阵的列数。 因此，5的伪地址为1；1的伪地址为5；…。3.6.3二维数组的结构特点—特殊矩阵的存储方式第40页，共63页，2023年，2月20日，星期六稀疏矩阵的转置运算： 一般矩阵的转置算法为： for(col=0;col<n;col++) for(row=0;row<m;row++) B[col][row]=A[row][col]; 由于稀疏矩阵含有大量的零元素，因此，其转置算法修改为如下所示：3.6.3二维数组的结构特点—特殊矩阵的存储方式第41页，共63页，2023年，2月20日，星期六spmatrixTRANSMAT(spmatrixa) /*返回稀疏矩阵A的转置*/ {intano,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二维数组的结构特点—特殊矩阵的存储方式第42页，共63页，2023年，2月20日，星期六 if(b->t>0) /*有非零元素，则转置*/ {bno=0; for(col=0;col<a->n;col++)/*按*a的列序转置*/ for(ano=0;ano<a－>t;ano++) /*扫描整个三元组表*/ if(a->data[ano].j==col) /*列号为col则进行置换*/ {b->data[bno].i=a->data[ano].j; b->data[bno].j=a->data[ano].i; b->data[bno].v=a->data[ano].v;3.6.3二维数组的结构特点—特殊矩阵的存储方式第43页，共63页，2023年，2月20日，星期六 bno++; /*b->data结点序号加1*/ } } returnb; /*返回转置结果指针*/} /*TRANSMAT*/3.6.3二维数组的结构特点—特殊矩阵的存储方式第44页，共63页，2023年，2月20日，星期六该算法的时间主要耗费在col和ano的二重循环上，若A的列数为n，非零元素个数为t，则执行时间为Ｏ(nt)，即与Ａ的列数和非零元素个数的乘积成正比。而通常用二维数组表示矩阵时，其转置算法的执行时间是Ｏ(mn)。由于非零元素个数一般远远大于行数，因此，上述稀疏矩阵转置算法虽然节省了空间，但增加了转置的时间。3.6.3二维数组的结构特点—特殊矩阵的存储方式第45页，共63页，2023年，2月20日，星期六链式存储结构：带行指针向量的单链表表示。 行指针向量 列值 ——>——> ——>——> ——> ——>3.6.3二维数组的结构特点—特殊矩阵的存储方式1506^011-2^48^23^第46页，共63页，2023年，2月20日，星期六十字链表结构：3.6.3二维数组的结构特点—特殊矩阵的存储方式第47页，共63页，2023年，2月20日，星期六设已知一个n×n的上三角矩阵X，其上三角元素已按行序为主序连续存放在数组Y中。请设计一个tran函数，将数组Y中元素按列为主序连续存放在数组Z中。3.6.4应用实例—问题描述A=12 3

4

50

6

7

8

90

0

10

11

120

0

013140

0

0

0

15第48页，共63页，2023年，2月20日，星期六根据已知条件： 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；将y[k]=x[i,j]元素存放在z[j*(j-1)/2+i]中，且当一行没有结束时j++，否则i++并修改下一行元素的个数及i和j的值，直到k=n(n+1)/2为止。3.6.4应用实例—算法分析第49页，共63页，2023年，2月20日，星期六#include<stdio.h>#defineN5voidtran(inty[],intn,intz[]){ intk,step=n,count=0,i=0,j=0; for(k=0;k<n*(n+1)/2;k++){ count++; z[j*(j-1)/2+i]=y[k]; if(count==step){ step--; count=0; i++; j=i; } else j++; }}3.6.4应用实例—算法实现第50页，共63页，2023年，2月20日，星期六main(){ intx[N][N],y[N*(N+1)/2],z[N*(N+1)/2]; inti,j,k=0,n=N; for(i=0;i<n;i++) for(j=0;j<n;j++) x[i][j]=0; printf(“pleaseinputnonzerodataofMatrix:\n); for(i=0;i<n;i++) for(j=i;j<n;j++) scanf(“%d”,&x[i][j]);3.6.4应用实例—算法实现第51页，共63页，2023年，2月20日，星期六 for(i=0;i<n;i++) for(j=0;j<n;j++) printf(“%4d”,x[i][j]); printf(“\n”); for(i=0;i<n;i++) for(j=i;j<n;j++){ y[k]=x[i][j]; k++; } for(i=0;i<n*(n+1)/2;i++) printf(“%4d”,y[i]); printf(“\n”); tran(y,n,z); for(i=0;i<n*(n+1)/2;i++) printf(“%4d”,z[i]); printf(“\n”);}3.6.4应用实例—算法实现第52页，共63页，2023年，2月20日，星期六[问题描述]输入一个稀疏矩阵，要求：将其转化为三元组的表示形式；在三元组存储矩阵中查找值为x的结点，若x存在，则输出其位置，否则输出“不存在”提示信息。3.6.5稀疏矩阵压缩存储方式和简单运算实例第53页，共63页，2023年，2月20日，星期六[算法描述]稀疏矩阵用二维数组A进行存储；三元组用结构体B表示；将数组A中的非零元素及它所在的行、列下标按行优先顺序存在到B中；在B中查找值为x的结点，若存在，则输出其位置；否则输出“不存在”提示信息。3.6.5稀疏矩阵压缩存储方式和简单运算实例第54页，共63页，2023年，2月20日，星期六[C语言源程序]#include<stdio.h> #defineMax100 typedefintElemtype; typedefstruct{ inti,j; Elemtypev; }Pnode;3.6.5稀疏矩阵压缩存储方式和简单运算实例第55页，共63页，2023年，2月20日，星期六 typedefstruct{ introws,cols,terms; Pnodedata[Max+1]; }PMatrix; PMatrixB;3.6.5稀疏矩阵压缩存储方式和简单运算实例第56页，共63页，2023年，2月20日，星期六 voidcrt_matrix(intA[][Max],intm,intn){ inti,j,k=1; for(i=1;i<=m;i++) for(j=1;j<=n;j++) if(A[i][j]!=0){ B.data