【数据结构】【串】【课堂笔记】(含代码)

简介: 【数据结构】【串】【课堂笔记】(含代码)


串的基本概念

串是由0个或者多个字符组成的有限序列

记为:s="a11a2……an"

串与线性表的对比

串的逻辑结构:和线性表极为相似

区别:串的数据对象约定是字符集

串的基本操作:和线性表有很大区别

  • 线性表的基本操作:以单个元素为操作对象
  • 串的基本操作:以串的整体为操作对象

子串与主串

子串

由串中任意个连续的字符组成的子序列

主串

包含子串的串

字符位置

字符在序列中的序号(从1开始)

子串位置

子串的首字符在主串中的位置

串的基本操作

加工型

串复制:将某个串复制给当前串

串连接:将串S1和S2联接而成一个新串

串替换:用子串x替换当前串中的子串y

插入子串:将子串插到当前串中的某个位置

删除子串:从当前串中删除指定子串

大写转小写:将串中的大写字母转化为对应小写字符

小写转大写:将串中的小写字母转化为对应大写字符

串压缩:将当前串中首部和尾部的所有空格删除

引用型

判空:判断当前串是否为空

串比较:判断当前串与指定串是否相等

求串长:返回当前串的字符个数

求子串:返回串的第i个字符开始的长达k个字符的子串

子串定位:输出子串在当前串中首次出现的位置

串的顺序储存与实现

在串的顺序储存中,一般有三种方法表示串的长度

(1)用一个变量来表示串的长度

(2)在串尾储存一个特殊字符作为串的终结符

(3)用数组的0号存在串的长度

串的实现

顺序储存结构的串可以用字符数组来存储字符数据

串的初始化

public calss string{
    private int maxSize =10;//串中字符数组的初始长度
    private char[] chars;//存储元素的数组对象
    private int length;//保存串的当前长度
    public string(){}
    public string(int n){}
    public void copy(string t){}
    public boolean isEmpty(){}
    public int compare(string t){}
    public int getLength(){}
    ...//此处省略部分成员方法
}

getter and setter

public class string {
    private int maxSize =10;//串中字符数组的初始长度
    private char[] chars;//存储元素的数组对象
    private int length;//保存串的当前长度
    public string(){}
    public string(int n){
    }
    public void copy(string t){
    }
    public boolean isEmpty(){
        return length <= 0;
    }
    public int compare(string t){
        return -1;
    }
    public int getLength(){
        return length;
    }
    public int getMaxSize() {
        return maxSize;
    }
    public void setMaxSize(int maxSize) {
        this.maxSize = maxSize;
    }
    public char[] getChars() {
        return chars;
    }
    public void setChars(char[] chars) {
        this.chars = chars;
    }
    public void setLength(int length) {
        this.length = length;
    }
}

功能完善

import javax.xml.crypto.dsig.keyinfo.RetrievalMethod;
public class string {
    private int maxSize =10;//串中字符数组的初始长度
    private char[] chars;//存储元素的数组对象
    private int length;//保存串的当前长度
    //串的初始化
    //构造一个空串
    public string(){
    }
    //构造一个能保存n个字符串的串
    public string(int n){
    }
    public void copy(string t){
        //将串t复制给当前串
        if(this.maxSize<t.maxSize){
            this.maxSize=t.maxSize;
            this.chars = new char[this.maxSize];
        }
        this.length=0;//初始化当前串的长度
        for(int i=0;i<t.getLength();i++){
            this.chars[i]=t.chars[i];
            this.length++;
        }
    }
    public boolean isEmpty(){
        return length <= 0;
    }
    /**
     * compare 串比较
     * @param t 字符型
     * @return int型 | 若当前串等于串t,则返回值0;若当前串大于串t,则返回1;若当前串小于于串t,则返回-1
     * @author xrilang
     */
    public int compare(string t){
        int i = 0;
        while(this.chars[i]==t.chars[i] && i < this.length && i<t.getLength()){i++;}
        //若当前串等于串t,则返回值0
        if(i==this.length && i==t.length) return 0;
        //若当前串大于串t,则返回1
        else if(i==t.getLength() && i < this.length) return 1;
        //若当前串小于于串t,则返回-1
        else return -1;
    }
    /**
     * concat 串联结
     * @param t 字符型
     * @author 萌狼蓝天
     */
    public void concat(string t){
        if(this.maxSize<this.length+t.getLength()){
            //当前串容量不够,暂存到数组tempArr
            char[] tempArr = new char[this.length];
            for(int i=0;i<this.length;i++){
                tempArr[i]=this.chars[i];
            }
            //重设maxSize,使串容量满足需求
            this.maxSize = this.length+t.getLength();
            this.chars=new char[this.maxSize];
            //恢复当前串的原始状态
            for(int i=0;i<tempArr.length;i++){
                this.chars[i]=tempArr[i];
            }
        }
        for(int i=0;i<t.length;i++){
            this.chars[this.length]=t.chars[i];
            this.length++;
        }
    }
    /**
     * subString 求子串
     * @param pos int型 索引 所求子串起始位置,不能为负数
     * @param len int型 长度 所求子串的长度
     * @return string型 返回所求子串,如果不存在则返回null
     * @author 萌狼蓝天
     */
    public string subString(int pos,int len){
        if(pos<0) return null;
        if(pos+len>=this.length) {
            //从位置pos开始不存在长度为len的子串
            return null;
        }
        string temp = new string(len);
        for(int i=0;i<len;i++){
            temp.chars[i]=this.chars[pos+i];
            temp.length ++;
        }
        return temp;
    }
    public int getLength(){
        return length;
    }
    public int getMaxSize() {
        return maxSize;
    }
    public void setMaxSize(int maxSize) {
        this.maxSize = maxSize;
    }
    public char[] getChars() {
        return chars;
    }
    public void setChars(char[] chars) {
        this.chars = chars;
    }
    public void setLength(int length) {
        this.length = length;
    }
}


相关文章
|
8天前
|
Go 索引
掌握Go语言:Go语言范围,优雅遍历数据结构,简化代码操作实战解析(24)
掌握Go语言:Go语言范围,优雅遍历数据结构,简化代码操作实战解析(24)
|
8天前
|
存储 编译器 C语言
【数据结构】C语言实现链队列(附完整运行代码)
【数据结构】C语言实现链队列(附完整运行代码)
45 0
|
8天前
|
存储 编译器 C语言
【数据结构】C语言实现带头双向循环链表万字详解(附完整运行代码)
【数据结构】C语言实现带头双向循环链表万字详解(附完整运行代码)
11 0
|
8天前
|
存储 编译器 C语言
【数据结构】C语言实现单链表万字详解(附完整运行代码)
【数据结构】C语言实现单链表万字详解(附完整运行代码)
50 0
|
8天前
|
存储 算法 程序员
【数据结构】C语言实现顺序表万字详解(附完整运行代码)
【数据结构】C语言实现顺序表万字详解(附完整运行代码)
49 0
|
2天前
|
存储 算法 搜索推荐
数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)(下)
数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)
21 1
|
2天前
|
算法 编译器
数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)(中)
数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)
20 4
|
3天前
|
存储 算法 搜索推荐
数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)(上)
数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)
22 6
|
3天前
|
机器学习/深度学习 算法 分布式数据库
数据结构与算法⑭(第四章_下)二叉树的模拟实现和遍历代码(下)
数据结构与算法⑭(第四章_下)二叉树的模拟实现和遍历代码
10 1
|
3天前
|
算法
数据结构与算法⑭(第四章_下)二叉树的模拟实现和遍历代码(上)
数据结构与算法⑭(第四章_下)二叉树的模拟实现和遍历代码
11 1