数据结构 教学课件 ppt 作者 叶乃文 郑晓红 第四章
49页1、第4章 串和数组,本章主要介绍下列内容: 串的定义、存储结构和基本运算 数组的定义、基本运算和存储结构 特殊矩阵的压缩存储,退出,4.1 串 4.2 数组,4.1 串,4.1.1 串的定义和基本运算 串是字符串的简称。它是一种在数据元素的组成上具有一定约束条件的线性表,即要求组成线性表的所有数据元素都是字符,所以,人们经常又这样定义串:串是一个有穷字符序列。,串一般记作: s= “a1a2.an” (n0) 其中,s是串的名称,用双引号(“”)括起来的字符序列是串的值;ai可以是字母、数字或其他字符;串中字符的数目n被称作串的长度。当n=0时,串中没有任何字符,其串的长度为0,通常被称为空串。 s1= “” s2= “ ” s1中没有字符,是一个空串;而s2中有两个空格字符,它的长度等于2,它是由空格字符组成的串,一般称此为空格串。 概念: 子串、主串:串中任意连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。,例如,有下列四个串a,b,c,d: a= “Welcome to Beijing” b= “Welcome” c= “Bei” d= “welcomet
2、o” 子串的位置:子串在主串中第一次出现的第一个字符的位置。 两个串相等:两个串的长度相等,并且各个对应的字符也都相同。 例如,有下列四个串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(s1,s2start,len) (6)串的定位 Index(s1,s2),例如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);
3、Concat(s1,s2); StringAssign(s,s1);,4.1.2 串的存储结构 1. 顺序存储结构 串的顺序存储结构与线性表的顺序存储类似,用一组连续的存储单元依次存储串中的字符序列。在C语言中,有两种实现方式: 第一种是事先定义字符串的最大长度,字符串存储在一个定长的存储区中。类型定义如下所示: #define MAX_STRING 255 /0号单元存放串的长度,字符从1号单元开始存放 type unsigned char StringMAX_STRING;,第二种是在程序执行过程中,利用标准函数malloc和free动态地分配或释放存储字符串的存储单元,并以一个特殊的字符作为字符串的结束标志,它的好处在于:可以根据具体情况,灵活地申请适当数目的存储空间,从而提高存储资源的利用率。类型定义如下所示: typedef struct char *str; int length; STRING; 不同的定义形式,算法中的处理也略有不同。下面我们将给出在第二种顺序存储方式下串的几个基本操作的算法。,(1) 串的赋值 int StringAssign(STRING*s,cha
4、r *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-str0=0; s-length=0; /空串,else s-str=(char*)malloc(len+1)*sizeof(char); /分配空间 if (!s-str) return ERROR; s-str0len=string_constant0len; /对应的字符赋值 s-length=len; /赋予字符串长度 return OK; ,(2)判断串是否为空 int StringEmpty(STRING s) if (!s.length) return TRUE; else return FALSE; (3)求串的长度 int Length(STRING s) return s.length; ,(4)串连接 int Concat
《数据结构 教学课件 ppt 作者 叶乃文 郑晓红 第四章》由会员E****分享,可在线阅读,更多相关《数据结构 教学课件 ppt 作者 叶乃文 郑晓红 第四章》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-04-11 25页
2024-04-11 37页
2024-04-11 28页
2024-04-11 31页
2024-04-11 36页
2024-04-11 29页
2024-04-11 22页
2024-04-11 27页
2024-04-11 34页
2024-04-11 32页