串的抽象数据类型.docx
- 文档编号:16233105
- 上传时间:2023-07-12
- 格式:DOCX
- 页数:14
- 大小:158.69KB
串的抽象数据类型.docx
《串的抽象数据类型.docx》由会员分享,可在线阅读,更多相关《串的抽象数据类型.docx(14页珍藏版)》请在冰点文库上搜索。
串的抽象数据类型
实习报告——“串的抽象数据类型”演示程序
(1)、程序的功能和特点
主要实现的功能:
1.打印字符串;
2.求当前串的实际长度;
3.返回当前串的字符数组;
4.在当前串中查找子字符串;
5.取出当前从m开始n个字符组成的子串;
6.判断当前串与对象串的大小关系;
7.判断当前串是否为空串;
8.取当前串的第i个字符;
(2)、程序的算法设计
“串的抽象数据类型”算法:
1.【逻辑结构与存储结构设计】
逻辑结构:
线性结构
存储结构:
内存中连续的存储单元
2.【基本操作设计】
串的顺序存储结构是内存中用一段连续的存储单元存储字符序列
所以可以通过数组实现
3.【算法设计】
在当前串中查找子字符串:
(i、j为每个串元素在串中的索引位置)
判断当前串与对象串的大小关系:
While(串的索与对象引<当前串与对象串长度的最小的长度
或遍历当前串元素!
=对象串元素)
返回当前串元素与对象串元素的差
4.【高级语言代码】
//在当前串中查找子字符串
publicintFind(CStringpat){
//穷举法
for(inti=0;i intj=0; //从ch[i]与pat.ch比较 while(j if(ch[i+j]==pat.ch[j]) j++; elsebreak; if(j==pat.curLen) returni+1;//pat扫描完,匹配成功,返回子串开始位置 } return-1;//匹配失败 } //取出当前串从m开始n个字符组成的子串 publicCStringsubString(intm,intn){ //从串第m个位置起连续提取n个字符,形成子串返回 if(m+n>curLen)//子串长度不合理 n=curLen-m; chart[]=newchar[n];//字符数组 for(inti=0,j=m;i t[i]=ch[j]; //传送串数组 CStringtemp=newCString(t);//构造方法2 returntemp; } //判断当前串与对象串other的大小关系 publicintCStringCmp(CStringother){ intl=curLen>other.curLen? curLen: other.curLen; inti=0,j=0; while(i =other.ch[j++]); returnch[i]-other.ch[j]; } //判断当前串是否为空串 booleanIsStrEmpty(){ returncurLen==0; } //将串other连接到当前串之后 publicvoidCStringApp(CStringother){ intj=0,i=curLen; while(i ch[i++]=other.ch[j++]; curLen+=other.curLen; } //取当前串的第i个字符 publicchargetchar(inti){ if(i returnch[i]; else return0; } (三)、程序中类的设计 “CString”类: 1.【逻辑结构与存储结构】 逻辑结构: 线性结构 2.【主要成员变量说明】 intcurLen;//串的实际长度 charch[]=newchar[maxlen];//串的存储数组 3.【主要成员方法说明】 //打印字符串 publicvoidstrPrint(){ } //求当前串的实际长度 publicintLength(){ } //返回当前串的字符数组 publicchar[]getValue(){ } //在当前串中查找子字符串 publicintFind(CStringpat){ } //取出当前串从m开始n个字符组成的子串 publicCStringsubString(intm,intn){ } //判断当前串与对象串other的大小关系 publicintCStringCmp(CStringother){ } //判断当前串是否为空串 booleanIsStrEmpty(){ } //将串other连接到当前串之后 publicvoidCStringApp(CStringother){ } //取当前串的第i个字符 publicchargetchar(inti){ } 4.【高级语言代码】 packagestudy_2; //串的抽象数据类型 importjava.io.*; publicclassCString{ finalstaticintmaxlen=128; intcurLen;//串的实际长度 charch[]=newchar[maxlen];//串的存储数组 //构造方法1: 从已有串复制 publicCString(CStringother){ curLen=other.curLen; for(inti=0;i ch[i]=other.ch[i]; } //构造方法2: 从已有字符数组复制 publicCString(chararrchar[]){ curLen=arrchar.length;//数组长度 for(inti=0;i ch[i]=arrchar[i]; } //构造方法3: 从键盘输入 publicCString(){ System.out.println("输入若干字符后回车"); try{ BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in)); br.read(ch); }catch(IOExceptione){} intl=0; while(ch[l]! =13)//回车结束 l++; curLen=l; } //打印字符串 publicvoidstrPrint(){ for(inti=0;i System.out.print(ch[i]); System.out.println(); } //求当前串的实际长度 publicintLength(){ returncurLen; } //返回当前串的字符数组 publicchar[]getValue(){ chartmp[]=newchar[curLen]; for(inti=0;i tmp[i]=ch[i]; } returntmp; } //在当前串中查找子字符串 publicintFind(CStringpat){ //穷举法 for(inti=0;i intj=0; //从ch[i]与pat.ch比较 while(j if(ch[i+j]==pat.ch[j]) j++; elsebreak; if(j==pat.curLen) returni+1;//返回子串开始位置 } return-1;//匹配失败 } //取出当前串从m开始n个字符组成的子串 publicCStringsubString(intm,intn){ //从串第m个位置起连续提取n个字符,形成子串返回 if(m+n>curLen)//子串长度不合理 n=curLen-m; chart[]=newchar[n];//字符数组 for(inti=0,j=m;i t[i]=ch[j]; //传送串数组 CStringtemp=newCString(t);//构造方法2 returntemp; } //判断当前串与对象串other的大小关系 publicintCStringCmp(CStringother){ intl=curLen>other.curLen? curLen: other.curLen; inti=0,j=0; while(i =other.ch[j++]); returnch[i]-other.ch[j]; } //判断当前串是否为空串 booleanIsStrEmpty(){ returncurLen==0; } //将串other连接到当前串之后 publicvoidCStringApp(CStringother){ intj=0,i=curLen; while(i ch[i++]=other.ch[j++]; curLen+=other.curLen; } //取当前串的第i个字符 publicchargetchar(inti){ if(i returnch[i]; else return0; } publicstaticvoidmain(String[]args){ CStrings1=newCString();//构造方法3 s1.strPrint(); chartmp[]=s1.getValue();//字符数组 CStrings2=newCString(tmp);//构造方法2 s2.strPrint(); CStrings3=newCString(tmp);//构造方法1 s3.strPrint(); CStringsub1=newCString(); System.out.println(s1.Find(sub1)); s1.CStringApp(sub1); s1.strPrint(); } } (4)、程序的输入输出和运行结果截屏
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 抽象 数据类型