数据结构 教学课件 作者 宗大华 陈吉人 04串 数组 矩阵.ppt

《数据结构 教学课件 作者 宗大华 陈吉人 04串 数组 矩阵.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第4章串、数组、矩阵4.1串4.2数组4.3特殊矩阵及稀疏矩阵串是一种特殊的线性表，特殊性在于它的每个数据元素只能是字符，在于串可以作为整体参与所需要的处理。数组本身是较为复杂的一种数据结构，但由于它的特性，能把它视为是线性表的推广。在众多矩阵中，有一类矩阵的阶数很高，但或其元素的分布有一定的规律可循，或里面含有大量的零元素。为了节省存储空间，常需要对这样的矩阵进行存储压缩处理。本章主要介绍以下几个方面的内容：串的基本知识；串的存储实现及各种处理算法；数组的基础知识及顺序存储；各种特殊矩阵（对称矩阵、三角矩阵），及其压缩存储；稀疏矩阵及其压

2、缩存储。4.1串串，就是通常所说的字符串，是一种特殊的线性表，它的数据元素仅限于是字符（英文字母、数字、空格以及其他字符）。可把串定义如下。4.1.1串的基本知识“串”是由0个或多个字符构成的一个有限序列，用双引号作为其定界符。若有一个串s：s="a1a2…an−1an"（n≥0）那么，s被称为是该串的“串名”，a1a2…an−1an就是串s的“值”。括在双引号内的字符个数n，称为字符串的“长度”。当n=0时，称其是一个“空串”。串中每个字符的序号，称为它在字符串的“位置”。字符串中任意多个连续字符所组成的子序列，称作是该串的“子串”，字符串本身称为

3、“主串”。子串第1个字符在主串中的位置，称作是该子串在“主串中的位置”。1．串的顺序存储实现4.1.2串的顺序存储实现当采用顺序式存储结构存储一个字符串时，就称它为“顺序串”。由于字符串是线性表的一个特例，因此，顺序串是顺序表的一个特例。类似于顺序表，人们是采用高级语言中的数组这种数据类型，来依次存放顺序串值中的字符序列的，这时每一个数组元素都只是一个字符。类似于顺序表，人们是采用高级语言中的数组这种数据类型，来依次存放顺序串值中的字符序列的，这时每一个数组元素都只是一个字符。为了建立一个顺序串St，需要做如下的工作：charSt[MAX];/*说明

4、一个字符型数组，申请一个连续的存储区*/St_max=MAX;/*设置顺序串的最大容量为MAX*/St_len=0;/*顺序串的长度*/书写时，字符串以双引号为界定符，它不被存放到数组里。为了明确字符串的结束位置，在串的末尾添加一个串结束符：“”。“”不算在串的长度之列。图4-1一个存放在数组里的字符串算法4-1连接两个顺序串的算法。2．连接两个顺序串图4-2连接两个串的示意图已知顺序串St1和St2，把St2连接到St1的末尾，得到一个新的顺序串St3。算法名为Concat_St()，参数为St1、St2。Concat_St(St1,St2

5、){charSt3[maxsize];/*创建一个新的顺序串为空*/St3_len=0;if(St1_len+St2_len>maxsize+1)/*新串放不下两个串*/{printf("两串长度之和超长！");return(NULL);}else{for(i=1;i<=St1_len;i++)/*把串St1传送给串St3*/St3[i]=St1[i];for(j=1;j<=St2_len;j++)/*接着把St2传送给串St3*/St3[j+St1_len]=St2[j];St3_Len=St1_len+St2_len;/*修改串St3的长度*/S

6、t3[St3_len+1]="";/*为St3安放串结束符*/return(St3);/*返回St3*/}}算法4-2判断两个顺序串相等的算法。已知顺序串St1和St2，如果相等则返回1，否则返回0。算法名为Equal_St()，参数为St1、St2。3．判断串相等Equal_St(St1,St2){if(St1_len!=St2_len)/*两个串长度不相等*/return(0);else/*两个串长度相等*/{for(i=1;i<=St1_len;i++)if(St1[i]!=St2[i])/*有字符不同*/return(0);return(

7、1);}}算法4-3从主串指定位置处取出定长子串的算法。4．取子串图4-3从主串中取子串示意图已知主串St1，从第i个位置开始，把连续n个字符组成的子串赋给串St2。算法名为Sub_St()，参数为St1、I、n。Sub_St(St1,i,n){charSt2[n+1];St2_len=0;if((i>=1)&&(i<=St1_len)&&(n>=1)&&(n<=St1_len-i+1))/*i和n正确*/{for(j=1;j<=n;j++)St2[j]=St1[i+j-1];St2_len=n;St2[n+1]="";}else/*参数不正确*

8、/{printf("开始位置或子串长度错！");return(NULL);}return(St2);}5．插