数据结构之串

基本概念

串(string)是由零个或多个字符组成的有限序列,又名叫字符串。形如s="a,b,c.."。ai(1 ≤ i ≤ n)可以是字母、数字或其他字符,i就是该字符在串中位置。串中的字符数目n称为串的长度,定义中谈到“有限”是指长度n是一个有限的数值。两个字符的串称为空串(null string),它的长度为零,可以直接用双引号“”表示。所谓序列,说明串的相邻字符之间具有前驱后继的关系。

空格串,是只包含空格的串。注意它和空串的区别,空格串是有内容有长度的,而且可以不止一个空格。

子串与主串,串中任意个数的连续字符组成的子序列称为该串的字串,相应地,包含子串的串称为主串。

子串在主串中的位置,就是子串第一个字符在主串中的序号。

串的存储结构

从串的存储方式来区分,主要分为堆式存储结构、链式存储结构和顺序存储结构。

顺序存储

串的静态存储结构即串的顺序存储结构,在大多数的计算机系统中,一个字占用多个字节,而一个字符只占用一个字节,所以为了节省空间,就采用紧缩格式存储。

类型定义:

typedef struct
    {
        char data[maxsize];
        int len;
    }stype;

下面是串的顺序结构的常用操作:

package bind;

class SqString {
	final int MaxSize = 100;
	char data[];
	int length;

	public SqString() {
		data = new char[MaxSize];
		length = 0;
	} // 字符串赋值 char[]

public void StrAssign(char cstr[])	{	
	int i;	
	for (i = 0; cstr[i] != '/0'; i++)	
		data[i] = cstr[i];	
	length = i;	} 
// 将串s复制给当前串SqSting
	public void StrCopy(SqString s) {
		int i;
		for (i = 0; i < s.length; i++)
			data[i] = s.data[i];
		length = i;
	} 
	// 判断串是否相等
	public boolean StrEqual(SqString s) {
		boolean b = true;
		if (s.length != length)
			b = false;
		else
			for (int i = 0; i < length; i++)
				if (s.data[i] != data[i]) {
					b = false;
					break;
				}
		return b;
	} 
	// 求串长
	public int StrLength() {
		return length;
	} 
	// 当前串与串s连接
	public void Concat(SqString s) {
		SqString str = new SqString();
		int i;
		str.length = length + s.length;
		for (i = 0; i < length; i++)
			str.data[i] = data[i];
		for (i = 0; i < s.length; i++)
			str.data[length + i] = s.data[i];
		this.StrCopy(str);
	} 
	// 返回串从第i开始之后j个字符组成的子串
	public SqString SubStr(int i, int j) {
		SqString s = new SqString();
		if (i <= 0 || i > length || j < 0 || i + j - 1 > length)
			return s;
		for (int k = i - 1; k < i + j - 1; k++) {
			s.data[s.length++] = data[k];
		}
		return s;
	} 
	// 在当前串在第i位插入S2
	public void InsStr(int i, SqString s2) {
		int j;
		SqString str = new SqString();
		if (i <= 0 || i > s2.length + 1) {
			System.out.println("Error:out of index! ");
			return;
		}
		for (j = 0; j < i - 1; j++)
			str.data[str.length++] = data[j];
		for (j = 0; j < s2.length; j++)
			str.data[str.length++] = s2.data[j];
		for (j = i - 1; j < length; j++)
			str.data[str.length++] = data[j];
		this.StrCopy(str);
	}

	// 删除第i位开始长度为j的子串
	public void DelStr(int i, int j) {
		int k;
		SqString s = new SqString();
		if (i <= 0 || i > length || i + j > length + 1) {
			System.out.println("Error: out of index!");
			return;
		}
		for (k = 0; k < i - 1; k++)
			s.data[s.length++] = data[k];
		for (k = i + j - 1; k < length; k++)
			s.data[s.length++] = data[k];
		this.StrCopy(s);
	}

	// 用串t代替当前串中第i位开始的j个字符构成的子串
	public void RepStr(int i, int j, SqString t) {
		this.DelStr(i, j);
		this.InsStr(i, t);
	}

	public void DispStr() {
		int i;
		if (length > 0) {
			for (i = 0; i < length; i++)
				System.out.print(data[i] + " ");
			System.out.println();
		}
	}
}

public class MySqString {
	public static void main(String args[])	{	
		char cstr1[] =		{ 'a', 'b', 'c', 'd', 'e', 'f', 'g', '/0' };	
		char cstr2[] =		{ '1', '2', '3', '4', '5', '6', '7', '/0' };	
		SqString s1 = new SqString();	
		s1.StrAssign(cstr1);	
		System.out.print("s1:");		
		s1.DispStr();		
		SqString s2 = new SqString();	
		s2.StrAssign(cstr2);		
		System.out.print("s2:");		
		s2.DispStr();		
		SqString s3 = new SqString();	
		s3.StrCopy(s1);		
		System.out.print("s3=s1/ns3:");		
		s3.DispStr();		
		System.out.println("s3.length=" + s3.length);	
		s3.Concat(s2);	
		System.out.print("s3=s3+s2:");	
		s3.DispStr();		
		System.out.println("s3.length=" + s3.length);	
		SqString s4 = new SqString();		
		System.out.println("返回串3从第1开始之后2个字符组成的子串");		
		s4 = s3.SubStr(1, 2);		
		s4.DispStr();		
		System.out.println("在当前串在第i位插入S2");		
		s4.InsStr(2, s2);		
		s4.DispStr();		
		System.out.println("删除第2位开始长度为1的子串");		
		s4.DelStr(2, 1);		
		s4.DispStr();		
		System.out.println("用串s2代替当前串中第2位开始的3个字符构成的子串");		
		s4.RepStr(2, 3, s2);	
		s4.DispStr();	}
}}

堆式存储

串的堆式存储结构类似于线性表的顺序存储结构,以一组地址连续的存储单元存放串值字符序列,其存储空间是在程序执行过程中动态分配的,而不是静态分配的。在C和C++语言中 ,提供一个称之为“堆”的共享空间,可以在程序运行过程中,系统利用函数malloc( )和free( )动态地申请或释放一块连续空间。由于在C和C++语言中可以用指针对数组进行访问和操作,在串的存储和操作上也可以充分利用上述特性。(这种在c和c++用的比较多,不做讲解)

堆式存储结构定义:

Typedef struct 
{  char *ch;   //指针域,指向存放串值的存储空间基址
   int length;  // 整型域:存放串长 
}HString;

链式存储

这种比较简单,如我们常见的链表。

表示:

//串的链式存储表示
typedef struct{
    char ch
    LStrNode *next;
}LStrNode,*LString;

链式存储简单操作

#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
  
/*字符结点*/  
struct Node{  
    char c;  
    struct Node * next;  
};  
  
typedef struct Node * PNode;  
  
/*函数声明*/  
PNode createNullLinkedString(void);  
int isNullLinkedString(PNode pstr);  
int initLinkedString(PNode pstr);  
int insertBeforeElement(PNode pstr);  
int dtempteElement(PNode pstr);  
void printString(PNode pstr);  
  
/*----------创建一个空的字符串---------------*/  
PNode createNullLinkedString(){  
    PNode pstr=(PNode)malloc(sizeof(struct Node));  
    if(pstr != NULL){  
        pstr->next=NULL;  
        pstr->c='-';  
        printf("创建成功!\n");  
    }  
    else{  
        pstr=NULL;  
        printf("创建失败!\n");  
    }  
    return pstr;  
}  
  
/*-----------判断串是否为空----------------*/   
int isNullLinkedString(PNode pstr){  
    if(pstr->next == NULL){  
        printf("空串!\n");  
        return 1;  
    }  
    else{  
        printf("非空串!\n");  
        return 0;  
    }  
}  
  
/*----------初始化一个空字符串-------------*/  
int initLinkedString(PNode pstr){  
    PNode cur = pstr;  
      
    if(isNullLinkedString(pstr)){  
          
        while(1){  
            char c;  
            printf("输入字符(@结束)>>>");  
            scanf("%c",&c);  
            getchar();  
            if(c =='@'){  
                break;  
            }  
            // 申请要插入的结点   
            PNode temp = (PNode)malloc(sizeof(Node));  
            temp->next = NULL;  
            temp->c = c;  
            if(pstr->next == NULL){  
                pstr->next = temp;  
                cur = pstr;  
            }else{  
                cur->next->next = temp;  
                cur = cur->next;  
            }     
        }   
        printf("初始化完毕!\n");  
        printString(pstr);  
        return 1;  
    }else{  
        printf("初始化失败!\n");  
        return 0;  
    }  
}  
  
/*-----------在指定字符之前插入字符---------------*/  
int insertBeforeElement(PNode pstr,char c,char s){  
    PNode cur = pstr;  
    while(cur->next != NULL){  
        // 找到指定字符   
        if(cur->next->c == c) {   
            PNode temp = (PNode)malloc(sizeof(PNode));  
            temp->c = s;  
            temp->next = cur->next;  
            cur->next = temp;   
            printf("插入成功!\n");  
            printString(pstr);  
            return 1;  
        }  
        cur = cur->next;  
    }  
    printf("未找到指定字符,插入失败\n");  
    return 0;  
}  
  
/*---------删除指定元素----------*/  
int deleteElement(PNode pstr,char c){  
    PNode cur = pstr;  
    while(cur->next != NULL){  
        // 找到指定字符   
        if(cur->next->c == c){  
            cur->next = cur->next->next;  
            printf("删除成功!\n");  
            printString(pstr);  
            return 1;   
        }  
        cur = cur->next;  
    }  
    printf("删除失败!\n");  
    return 0;  
}  
  
/*----------打印当前字符串----------*/  
void printString(PNode pstr){  
    PNode cur = pstr;  
      
    printf("[");  
    while(cur->next != NULL){  
        printf(" %c ",cur->next->c);  
        cur = cur->next;  
    }  
    printf("]");  
}  
/*-------主控-------*/  
int main(void){  
    PNode pstr= NULL;  
    printf("\n--------字符串的基本操作---------\n");  
    char c,s,ch;  
    int input;  
    while(1){  
        printf("\n 1_创建空串\n 2_判断当前是否为空\n 3_初始化空串\n");  
        printf(" 4_在指定字符之前插入字符\n 5_删除指定字符\n 6_打印串\n");  
        printf("\n请选择>>>");   
        scanf("%d",&input);  
        scanf("%c",&ch);   
        switch(input){  
            case 1 :   
                pstr = createNullLinkedString();  
                break;  
            case 2 :   
                isNullLinkedString(pstr);  
                break;  
            case 3 :   
                initLinkedString(pstr);  
                break;  
            case 4 :   
                printf("请指定字符>>>");  
                scanf("%c",&c);  
                getchar();  
                printf("请输入要插入的字符>>>");  
                scanf("%c",&s);  
                insertBeforeElement(pstr,c,s);  
                break;  
            case 5 :  
                printf("请指定字符>>>");  
                scanf("%c",&s);   
                deleteElement(pstr,s);  
                break;  
            case 6 :   
                printString(pstr);  
                break;  
            default:   
                printf("输入错误,请重新输入");  
                break;  
        }  
    }  
    return 0;  
}  

串的比较

对于两个串不相等时,如何判定它们的大小呢。我们这样定义:  给定两个串:s = “a1a2…….an”,t = “b1,b2……bm”,当满足以下条件之一时,s < t。 存在某个k < min(m,n),使得ai = bi(i = 1, 2 , ….., k -1),ak < bk  假如当s = “happen” ,t = “happy”,因为两串的前4个字符均相同,而两串的第5个字母(k值),字母e的ASCII码时101,而字母y的ASCII码时121,显然e < y,所以s < t。 n < m,且ai = bi (i = 1, 2, …… , n)  例如当 s = “hap”,t = “happy”,就有s < t,因为t比s多处了两个字母。

串的抽象数据类型

串的逻辑结构和线性表很相似,不同之处在于串针对的是字符集,也就是串中的元素都是字符。因此,对于串的基本操作与线性表所有很大差别的。线性表更关注的是单个元素的操作但串中更多的是查找子串的位置、得到指定位置的子串、替换子串等操作

例如串的add

Data
    串中元素仅由一个字符组成,相邻元素具有前驱和后继关系。
Operation
    StrAssign(T,*chars):生成一个其值等于字符串常量chars的串T。
    strCopy(T,S):串S存在,由串S复制得串T
    ClearString(S):串S存在,将串清空
    StringEmpty(S):若串S为空,返回true,否则false
    StrLength(S):返回串S的元素个数,即串的长度
    StrCompare(S,T):若S>T,返回值大于0;若S=T,返回0,若S<T,返回值0
    Concat(T,S1,S2):用串T返回S1和S2连接而成的新串
    SubString(Sub,S,pos,len):串S存在,1≤pos≤StrLength(S)
                且0≤len≤StrLength(S)-pos+1,用Sub
                返回值S的第pos个字符起长度为len的子串
    Index(S,T,pos):串S和串T存在,T是非空串1≤ pos ≤StrLength(S)
                若主串S中存在和串T相同的子串,则返回它在主串S中
                第pos个字符后第一个出现的位置,否则返回0
    Replace(S,T,V):串S、T和V存在,T是非空串。用V替换主串中出现的
                所有与T相等的不重叠的子串
    StrInset(S,pos,T):串S和T存在,1 ≤ pos ≤StrLength(S) + 1
                在串S的第pos个字符之前插入串T
    StrDelete(S,pos,len):串S存在,1≤pos≤StrLengthS-len+1
                从串S中删除第pos个字符起长度为len的子串。

串的查找

int Index(String S,String T,int pos)
{
    int n,m,i;
    String sub;
    if(pos > 0)
    {
        n = StrLength(S);//得到主串S的长度
        m = StrLength(T);
        i = pos;
        while(i <= n-m+1)
        {
            SubString(sub,S,i,m);//取主串第i个位置,m长度的子串
            if(StrCompare(sub,T) != 0)//如果两串不相等
                i++;
            else                      //如果相等 
                return i;             //返回i值
        }
    }
    return 0;//若无子串与T相等,返回0
}

串的模式匹配

子串的定位操作通常称为串的模式匹配。应该算是串中最重要的操作之一。假设我们要从下面的主串S = “goodgoogle”中,找到T=”google”这个子串的位置。最简单的朴素想法就是,对主串的每一个字符作为子串开头,与要匹配的字符串进行匹配。对主串作大循环,每个字符开头做T长度的小循环,知道匹配完成为止。

前面我们已经用串的其他操作实现了模式匹配的算法Index。现在考虑不用其他操作,而是只用基本的数组来实现同样的算法。

int Index(String S,String T,int pos)
{
    int i = 0;
    int j = 0;
    int SLen = 0;
    int TLen = 0;
    while(s[i] != '\0')//计算S长度
    {
        SLen++;
    }
    while(T[i] != '\0')//子串T的长度
    {
        TLen++;
    }
    int i = pos;
    while(i <= SLen - TLen && j <= TLen)
    {
        if(S[i] == T[i])
        {
            i++;
            j++;
        }
        else
        {
            i = i - j + 1;//匹配失败回到开始的地方的下一个位置
            j = 0;//子串回到原来位置
        }
    }
    if(j > TLen)
    {
        return i - TLen;
    }
    else
        return 0;
}

注:分析一下,最好的情况时什么?那就是一开始就成功,此时时间复杂度为O(1)。 稍差一点,如果像”abcdedgood”中查找”good”。那么时间复杂度就是O(n + m),n为主串长度,m为要匹配的子串长度。根据等概原则,平均是(n + m) / 2次查找,时间复杂度为O(n+m)。那么最坏的情况是什么呢?就是每次不成功的匹配都发生在串T的最后一个字符,比如主串S = 0000000000000000000000000000000000001,而要匹配的子串为T = 0000001。前者是有49个“0”和1个“1”,后者是9个“0”和1个“1”。这样等于前40个位置要循环40 * 10次。知道第41个位置,这里也要匹配10次。 

哦,mygod,最坏时间复杂度为O[(n-m+1)*m]。

全是KMP模式匹配算法也是串的操作之一,有兴趣的可以看看之前这个算法的讲解kmp算法

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

谈谈Go语言的反射三定律

简介 Reflection(反射)在计算机中表示 程序能够检查自身结构的能力,尤其是类型。它是元编程的一种形式,也是最容易让人迷惑的一部分。 虽然Go语言没...

48811
来自专栏进击的君君的前端之路

函数与作用域

1424
来自专栏风口上的猪的文章

.NET面试题系列[11] - IEnumerable<T>的派生类

ICollection<T>继承IEnumerable<T>。在其基础上,增加了Add,Remove等方法,可以修改集合的内容。IEnumerable<T>的直...

1142
来自专栏HTML5学堂

获取对象具体类型的功能函数

HTML5学堂:JavaScript当中,时常会使用到typeof来进行数据类型的检测,但是我们觉得typeof不能够满足我们的需求,对于数组、函数、时间对象等...

3287
来自专栏文武兼修ing——机器学习与IC设计

表的应用——排序与描述多项式排序多项式ADTGO语言笔记

排序 朴素排序 在链表建立的过程中可以直接完成排序功能,即建立一个新链表并将源数据一个一个存进新链表中,每个元素存储的位置在小于这个元素的节点和大于这个元素的节...

3496
来自专栏Script Boy (CN-SIMO)

Qt Quick编程(1)——QML的核心部分ECMAScript

说道QML,不得不先说一下ECMAScript: ECMAScript语言的标准是由Netscape、Sun、微软、Borland等公司基于JavaScript...

4630
来自专栏Golang语言社区

Go语言interface详解

interface Go语言里面设计最精妙的应该算interface,它让面向对象,内容组织实现非常的方便,当你看完这一章,你就会被interface的巧妙设计...

3709
来自专栏C++

python笔记:#005#算数运算符

1622
来自专栏尾尾部落

[LeetCode] Longest Common Prefix 最长公共前缀 [LeetCode] Longest Common Prefix 最长公共前缀

链接:https://leetcode.com/problems/longest-common-prefix/#/description 难度:Easy ...

1582
来自专栏Golang语言社区

Go语言interface详解

interface Go语言里面设计最精妙的应该算interface,它让面向对象,内容组织实现非常的方便,当你看完这一章,你就会被interface的巧妙设计...

3717

扫码关注云+社区

领取腾讯云代金券