人民邮电出版社：高职高专现代信息技术系列教材《数据结构》课程电子教案（PPT课件讲稿）第四章 串和数组

第4牛和数组 本章主要介绍下列内容: 串的定义、存储结构和基本运算 数组的定义、基本运算和存储结构 特殊矩阵的压缩存储 请单鼠标左键换页! 退出

第4章 串和数组 本章主要介绍下列内容： ⚫ 串的定义、存储结构和基本运算 ⚫ 数组的定义、基本运算和存储结构 ⚫ 特殊矩阵的压缩存储 退出

1 2数组 请单赤鼠标左键换页!

4.1 串 4.2 数组

4.1 4.1.1串的定义和基本运算 串是字符串的简称。它是一种在数据元素的组成 上具有一定约束条件的线性表,即要求组成线性表的 所有数据元素都是字符,所以,人们经常又这样定义 串:串是一个有穷字符序列。 请单鼠标左键换页!

4.1 串 4.1.1 串的定义和基本运算 串是字符串的简称。它是一种在数据元素的组成 上具有一定约束条件的线性表，即要求组成线性表的 所有数据元素都是字符，所以，人们经常又这样定义 串：串是一个有穷字符序列

串一般记作: 1a2 (n20 其中,s是串的名称,用双引号(“”)括起来的 字符序列是串的值;a,可以是字母、数字或其他字符; 串中字符的数目n被称作串的长度。当n=0时,串中没 有任何字符,其串的长度为0,通常被称为空串。 sl中没有字符,是一个空串;而s2中有两个空格 字符,它的长度等于2,它是由空格字符组成的串, 般称此为空格串。 概念: 子串、主串:串中任意连续的字符组成的子序列 被称为该串的子串。包含子串的串又被称为该子串的 主串。 请单鼠标左键换页!

串一般记作： s= “a1a2 ...an” (n0) 其中，s是串的名称，用双引号（“”）括起来的 字符序列是串的值；ai可以是字母、数字或其他字符； 串中字符的数目n被称作串的长度。当n=0时，串中没 有任何字符，其串的长度为0，通常被称为空串。 s1= “” s2= “ ” s1中没有字符，是一个空串；而s2中有两个空格 字符，它的长度等于2，它是由空格字符组成的串，一 般称此为空格串。 概念： 子串、主串：串中任意连续的字符组成的子序列 被称为该串的子串。包含子串的串又被称为该子串的 主串

例如,有下列四个串a,b,c,d: a=“ Welcome to Beijing” b=“ Welcome” Bej d=“ welcometo” 子串的位置:子串在主串中第一次出现的第一个 字符的位置。 两个串相等:两个串的长度相等,并且各个对应 的字符也都相同 例如,有下列四个串a,b,c,d: a- program b=“ Program pro d=“ progran” 请单鼠标左键换页!

例如，有下列四个串a，b，c，d： a= “Welcome to Beijing” b= “Welcome” c= “Bei” d= “welcometo” 子串的位置：子串在主串中第一次出现的第一个 字符的位置。 两个串相等：两个串的长度相等，并且各个对应 的字符也都相同。 例如，有下列四个串a，b，c，d： a= “program” b= “Program” c= “pro” d= “program

串的基本操作: (1)创建串 Stringassign(s, string constant) (2)判断串是否为空 StringEmpty(s) (3)计算串长度 Length(s) (4)串连接 Concat(s1,s2) (5)求子串 Substr(s1s2 start,len) (6)串的定位 Index(s1s2) 请单鼠标左键换页!

串的基本操作： （1） 创建串 StringAssign (s,string_constant) （2）判断串是否为空 StringEmpty(s) （3）计算串长度Length(s) （4）串连接 Concat(s1,s2) （5）求子串SubStr(s1,s2start,len) （6）串的定位Index(s1,s2)

例如1:将s2串插入到串s的第个字符后面。 Substr(s3, sl, 1,i); SubStr(s4, sl, i+l, Length(s1)-i); Concat(s3, s2) Concat(s3, s4) String Assign(s1, s3); 例如2:删除串s中第个字符开始的连续j个字符 Substr(sl, s, 1, i-1) Substr(s2, s, i+j, Length(s)-i-j+1) Concat(sl, s2) String Assign(s, s1) 请单鼠标左键换页!

例如1：将s2串插入到串s1的第i个字符后面。 SubStr(s3,s1,1,i); SubStr(s4,s1,i+1,Length(s1)-i); Concat(s3,s2); Concat(s3,s4); StringAssign (s1,s3); 例如2：删除串s中第i个字符开始的连续j个字符。 SubStr(s1,s,1,i-1); SubStr(s2,s,i+j,Length(s)-i-j+1); Concat(s1,s2); StringAssign(s,s1);

4.1.2串的存储结构 1.顺序存储结构 串的顺序存储结构与线性表的顺序存储类似,用 组连续的存储单元依次存储串中的字符序列。在C 语言中,有两种实现方式: 第一种是事先定义字符串的最大长度,字符串存 储在一个定长的存储区中。类型定义如下所示: #define max string 255 /0号单元存放串的长度,字符从1号单元开始存放 type unsigned char String MAX STRINGI 请单赤鼠标左键换页!

4.1.2 串的存储结构 1. 顺序存储结构 串的顺序存储结构与线性表的顺序存储类似，用 一组连续的存储单元依次存储串中的字符序列。在C 语言中，有两种实现方式： 第一种是事先定义字符串的最大长度，字符串存 储在一个定长的存储区中。类型定义如下所示： #define MAX_STRING 255 //0号单元存放串的长度，字符从1号单元开始存放 type unsigned char String[MAX_STRING];

第二种是在程序执行过程中,利用标准函数 malloc和free动态地分配或释放存储字符串的存储单元, 并以一个特殊的字符作为字符串的结束标志,它的好 处在于:可以根据具体情况,灵活地申请适当数目的 存储空间,从而提高存储资源的利用率。类型定义如 下所示: typedef structi char *str nt length g ISTRING: 不同的定义形式,算法中的处理也略有不同。下 面我们将给出在第二种顺序存储方式下串的几个基本 操作的算法。 请单鼠标左键换页!

第二种是在程序执行过程中，利用标准函数 malloc和free动态地分配或释放存储字符串的存储单元， 并以一个特殊的字符作为字符串的结束标志，它的好 处在于：可以根据具体情况，灵活地申请适当数目的 存储空间，从而提高存储资源的利用率。类型定义如 下所示： typedef struct{ char *str; int length; }STRING; 不同的定义形式，算法中的处理也略有不同。下 面我们将给出在第二种顺序存储方式下串的几个基本 操作的算法

(1)串的赋值 int String Assign(STRINGS, char *string constant) if(s-str) free(s->str); 若s已经存在,将它占据的空间释放掉 for (len=0, ch=string constant; ch; len++, ch++) 求 string constant串的长度 if en S->str=(char )malloc(sizeof(char); s >str0J=”10’;s> length=0;}/空串 请单赤鼠标左键换页!

（1） 串的赋值 int StringAssign(STRING*s,char *string_constant) { if (s->str) free(s->str); //若s已经存在，将它占据的空间释放掉 for (len=0,ch=string_constant;ch;len++,ch++); //求string_constant串的长度 if (!len) { s->str=(char*)malloc(sizeof(char));s- >str[0]=’\0’; s->length=0; } //空串