山东第一医科大学(泰山医学院):《数据结构》课程教学资源(PPT课件)第4章 串

第四章串 §4.1串类型的定义 §4.2 串的表示和实现 4.2.1定长顺序存储表示 4.2.2堆分配存储表示 4.2.3串的块链存储表示
第四章 串 §4.1 串类型的定义 §4.2 串的表示和实现 4.2.1 定长顺序存储表示 4.2.2 堆分配存储表示 4.2.3 串的块链存储表示

4.1串类型的定义 串和基本概念 串(String)是零个或多个字符组成的有限序列。 一般记作S=a1a2a3.an',其中S是串名,引号括 起来的字符序列是串值: a(1sisn)可以是字母、数字或其它字符; 串中所包含的字符个数称为该串的长度。长度为零 的串称为空串(Empty String),它不包含任何字符。 通常将仅由一个或多个空格组成的串称为空白串 (Blank String) 注意:空串和空白串的不同,例如··和”分别 表示长度为1的空白串和长度为0的空串
4.1 串类型的定义 一、串和基本概念 串(String)是零个或多个字符组成的有限序列。 一般记作S=‘a1a2a3…an ’,其中S 是串名,引号括 起来的字符序列是串值; ai(1≦i≦n)可以是字母、数字或其它字符; 串中所包含的字符个数称为该串的长度。长度为零 的串称为空串(Empty String),它不包含任何字符。 通常将仅由一个或多个空格组成的串称为空白串 (Blank String) 注意:空串和空白串的不同,例如‘ ’和‘’分别 表示长度为1的空白串和长度为0的空串

串中任意个连续字符组成的子序列称为该串的子串, 包含子串的串相应地称为主串。 通常将子串在主串中首次出现时的该子串的首字 符对应的主串中的序号,定义为子串在主串中的序 号(或位置)。 例如,设A和B分别为 A='This is a string'B='is' 则B是A的子串,A为主串。B在A中出现了两次 其中首次出现所对应的主串位置是3。因此,称B在 A中的序号(或位置)为3。 特别地,空串是任意串的子串,任意串是其自身 的子串
串中任意个连续字符组成的子序列称为该串的子串, 包含子串的串相应地称为主串。 通常将子串在主串中首次出现时的该子串的首字 符对应的主串中的序号,定义为子串在主串中的序 号(或位置)。 例如,设A和B分别为 A=‘This is a string’ B=‘is’ 则B是A的子串,A为主串。B在A中出现了两次, 其中首次出现所对应的主串位置是3。因此,称B在 A中的序号(或位置)为3。 特别地,空串是任意串的子串,任意串是其自身 的子串

通常在程序中使用的串可分为两种:串变量和串 常量。串常量和整常数、实常数一样,在程序中只 能被引用但不能改变其值,即只能读不能写。 通常串常量是由直接量来表示的,例如语句 Error(“overflow)中"overflow'是直接量。但 有的语言允许对串常量命名,以使程序易读、易写。 如,可定义 const char path[]="dir/bin/appl"; 这里path是一个串常量,对它只能读不能写。 串变量和其它类型的变量一样,其取值是可以改 变的。 两个串相等:长度相等,对应位置字符都相等。 二、串的抽象数据定义
通常在程序中使用的串可分为两种:串变量和串 常量。串常量和整常数、实常数一样,在程序中只 能被引用但不能改变其值,即只能读不能写。 通常串常量是由直接量来表示的,例如语句 Error(“overflow”)中“overflow”是直接量。但 有的语言允许对串常量命名,以使程序易读、易写。 如,可定义 const char path[]=“dir/bin/appl”; 这里path是一个串常量,对它只能读不能写。 串变量和其它类型的变量一样,其取值是可以改 变的。 两个串相等:长度相等,对应位置字符都相等。 二、串的抽象数据定义

串的基本操作 对于串的基本操作,许多高级语言均提供了相 应的运算或标准库函数来实现。下面仅介绍几种 在C语言中常用的串运算。 定义下列几个变量: char s1[20]='dirtreeformat',s2[20]='file.mem'; char s3[30],*p; int result; (1)求串长(length) int strlen(char*s);l求串的长度 例如:printf(“%d”,strlen(s1);输出13
三、串的基本操作 对于串的基本操作,许多高级语言均提供了相 应的运算或标准库函数来实现。下面仅介绍几种 在C语言中常用的串运算。 定义下列几个变量: char s1[20]=‘dirtreeformat’,s2[20]=‘file.mem’; char s3[30],*p; int result; (1) 求串长(length) int strlen(char *s); //求串的长度 例如:printf(“%d”,strlen(s1)); 输出13

2)串复制(copy) char *strcpy(char *to,char *from); 该函数将串from复制到串to中,并且返回一个指 向串to的开始处的指针。 例如:strcpy(s3,s1);ls3=“dirtreeformat" (3)联接(concatenation) char *strcat(char *to,char *from) 该函数将串from复制到串to的末尾,并且返回 一个指向串to的开始处的指针。 例如:strcat(s3,”) strcat(s3,s2); ls3=“dirtreeformat/file.mem
(2)串复制(copy) char *strcpy(char *to,char *from); 该函数将串from复制到串to中,并且返回一个指 向串to的开始处的指针。 例如:strcpy(s3,s1); //s3=“dirtreeformat” (3)联接(concatenation) char *strcat(char *to,char *from) 该函数将串from复制到串to的末尾,并且返回 一个指向串to的开始处的指针。 例如:strcat(s3,”/”) strcat(s3,s2); //s3=“dirtreeformat/file.mem

4)串比较(compare) int strcmp(char *s1,char *s2); 该函数比较串s1和串s2的大小,当返回值小于0, 等于0或大于0时分别表示s1s2 例如:result=:strcmp(“baker'”,”Baker')result>0 result=strcmp(“12”,”12");result=0 result=strcmp(“Joe",”Joseph");result<0 (5)字符定位(index) char strchr(char *s,char *c); 该函数是找c在字符串s中第一次出现的位置,若 找到则返回该位置,否则返回NULL。 例如:p=strchr(s2,”.”);p指向“file”之后的位置 if(p)strcpy(p,”.cpp");s2=“file.cpp
(4)串比较(compare) int strcmp(char *s1,char *s2); 该函数比较串s1和串s2的大小,当返回值小于0, 等于0或大于0时分别表示s1s2 例如:result=strcmp(“baker”,”Baker”) result>0 result=strcmp(“12”,”12”); result=0 result=strcmp(“Joe”,”Joseph”); result<0 (5)字符定位(index) char strchr(char *s,char *c); 该函数是找c在字符串s中第一次出现的位置,若 找到则返回该位置,否则返回NULL。 例如:p=strchr(s2,”.”); p 指向“file”之后的位置 if(p) strcpy(p,”.cpp”); s2=“file.cpp

例:串的定位index(s,t,pos) 算法思想 算法思想: 1、在主串中取从第个字符起长度和串T相等的子串和 T比较 2、若相等,则求得函数值为引, 3、否则值增1直至S中不存在和串T相等的子串为止
例: 串的定位index(s,t,pos) 算法思想 算法思想: 1、在主串中取从第i个字符起长度和串T相等的子串和 T比较 2、若相等,则求得函数值为i, 3、否则i值增1直至S中不存在和串T相等的子串为止

int index(string s,string t,int pos){ if(pos>0){ n=strlen(s);m=strlen(t);i=pos; while(i<n-m+1){ substr(sub,s,i,m); if(strcmp(sub,t)!=0) ++i; else return(i); return(0);
int index(string s,string t,int pos){ if(pos>0){ n=strlen(s); m=strlen(t); i=pos; while(i<n-m+1){ substr(sub,s,i,m); if(strcmp(sub,t)!=0) ++i; else return(i); } } return(0); }

4.2串的表示和实现 因为串是特殊的线性表,故其存储结构与线性表的 存储结构类似。只不过由于组成串的结点是单个字符。 串的数据对象约束为字符集。 4.2.1定长顺序存储表示 定长顺序存储表示,也称为静态存储分配的顺序表。 它是用一组连续的存储单元来存放串中的字符序列。 所谓定长顺序存储结构,是直接使用定长的字符数组 来定义,数组的上界预先给出: #define maxstrlen 256 typedef char sstring[maxstrlen]; sstring s:/s是一个可容纳255个字符的顺序 串
4.2 串的表示和实现 因为串是特殊的线性表,故其存储结构与线性表的 存储结构类似。只不过由于组成串的结点是单个字符。 串的数据对象约束为字符集。 4.2.1定长顺序存储表示 定长顺序存储表示,也称为静态存储分配的顺序表。 它是用一组连续的存储单元来存放串中的字符序列。 所谓定长顺序存储结构,是直接使用定长的字符数组 来定义,数组的上界预先给出: #define maxstrlen 256 typedef char sstring[maxstrlen]; sstring s; //s是一个可容纳255个字符的顺序 串
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 山东第一医科大学(泰山医学院):《数据结构》课程教学资源(PPT课件)第3章 栈和队列.ppt
- 山东第一医科大学(泰山医学院):《数据结构》课程教学资源(PPT课件)第2章 线性表.ppt
- 山东第一医科大学(泰山医学院):《数据结构》课程教学资源(PPT课件)第1章 绪论(主讲教师:王玫).ppt
- 大连大学:信息工程学院计算机科学与技术专业课程教学大纲汇编.pdf
- 山东第一医科大学(山东省医学科学院):《数字图像处理》课程授课电子教案 Computer Image Processing.doc
- 山东第一医科大学(山东省医学科学院):《数字图像处理》课程PPT教学课件讲稿(负责人:张兆臣).ppt
- 山东第一医科大学(山东省医学科学院):《数字图像处理》课程各章作业习题.doc
- 大连大学:软件工程学院软件工程专业课程教学大纲汇编.pdf
- 湖南人文科技学院:《Web前端开发》课程思政教学资源(PPT课件)网站开发基础.pptx
- 湖南人文科技学院:《Web前端开发》课程思政教学资源(授课教案)网站开发基础(主讲教师:刘鹃梅).pdf
- 新乡学院:数学与统计学院信息与计算科学专业《毕业论文》课程教学大纲(2015).pdf
- 新乡学院:数学与统计学院信息与计算科学专业《认知见习》课程教学大纲(2015).pdf
- 新乡学院:数学与统计学院信息与计算科学专业《专业见习2》课程教学大纲(2015).pdf
- 新乡学院:数学与统计学院信息与计算科学专业《专业见习1》课程教学大纲(2015).pdf
- 新乡学院:数学与统计学院信息与计算科学专业《校内见习》课程教学大纲(2015).pdf
- 新乡学院:数学与统计学院信息与计算科学专业《C语言程序设计》课程教学大纲(2015).pdf
- 新乡学院:数学与统计学院信息与计算科学专业《综合设计(数学建模)》课程教学大纲(2015).pdf
- 新乡学院:数学与统计学院信息与计算科学专业《数值分析课程设计》课程教学大纲(2015).pdf
- 新乡学院:数学与统计学院信息与计算科学专业《多媒体技术应用》课程教学大纲(2015).pdf
- 新乡学院:数学与统计学院信息与计算科学专业《微机原理与接口技术》课程教学大纲(2015).pdf
- 山东第一医科大学(泰山医学院):《数据结构》课程教学资源(PPT课件)第5章 数组和广义表.ppt
- 山东第一医科大学(泰山医学院):《数据结构》课程教学资源(PPT课件)第6章 树.ppt
- 山东第一医科大学(泰山医学院):《数据结构》课程教学资源(PPT课件)第7章 图.ppt
- 山东第一医科大学(泰山医学院):《数据结构》课程教学资源(PPT课件)第9章 查找.ppt
- 山东第一医科大学(泰山医学院):《数据结构》课程教学资源(PPT课件)第10章 排序.ppt
- 西安电子科技大学:《Java程序设计》课程教学课件(讲稿)第一章 Java语言基础(主讲:高洋).pdf
- 西安电子科技大学:《Java程序设计》课程教学课件(讲稿)第二章 使用Java解决简单的问题.pdf
- 西安电子科技大学:《Java程序设计》课程教学课件(讲稿)第三章 类、类的继承和接口.pdf
- 西安电子科技大学:《Java程序设计》课程教学课件(讲稿)第四章 Java类库简介和数据结构类使用.pdf
- 西安电子科技大学:《Java程序设计》课程教学课件(讲稿)第五章 异常和多线程.pdf
- 西安电子科技大学:《Java程序设计》课程教学课件(讲稿)第七章 Java的图形与用户界面.pdf
- 电子工业出版社:《数字图像处理》书籍教材PDF电子版(中译第三版)第2章 数字图像处理基础.pdf
- 电子工业出版社:《数字图像处理》书籍教材PDF电子版(中译第三版)第1章 绪论(冈萨雷斯 Rafael C.Gonzalez、Richard E. Woods).pdf
- 《数字图像处理》课程教学课件(Digital Image Processing)数字图像处理基础 2.1 人眼视觉感知基础(打印版).pdf
- 《数字图像处理》课程教学课件(Digital Image Processing)数字图像处理基础 2.2 图像数字化(打印版).pdf
- 《数字图像处理》课程教学课件(Digital Image Processing)数字图像处理基础 2.3 图像插值(打印版).pdf
- 《数字图像处理》课程教学课件(Digital Image Processing)数字图像处理基础 2.4 像素间关系.pdf
- 电子工业出版社:《数字图像处理》书籍教材PDF电子版(中译第三版)第3章 灰度变换与空间滤波.pdf
- 《数字图像处理》课程教学课件(Digital Image Processing)灰度变换与空间滤波 3.1 邻域 邻接、连接 区域、边界 距离.pdf
- 《数字图像处理》课程教学课件(Digital Image Processing)灰度变换与空间滤波 3.2 直方图 Histogram processing.pdf