数据结构与算法丨串 1-阿里云开发者社区

数据结构与算法丨串 1

2023-10-11 163

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构与算法丨串

一、概述

1.1 串的概念

串（即字符串）是一种特殊的线性结构，它的数据元素仅由一个字符组成。随着非数值处理的广泛应用，某些应用系统（如字符编辑、文字处理、信息检索、自然语言翻译和事务处理等系统）处理的对象经常是字符串数据。例如，在汇编和高级语言的编译程序中，源程序和目标程序都是字符串数据；在事务处理程序中，顾客的姓名、地址、货物的产地、名称等也是作为字符串处理的。

在不同类型的应用中，所处理的字符串具有不同的特点，要有效地实现字符串的处理，就必须根据不同情况选择合适的存储结构。

1.2 几个术语

（1）子串：串中任意连续字符组成的子序列称为该串的子串

（2）主串：包含子串的串称为主串。字符在串中的序号表示该字符在串中的位置，子串的第一个字符在主串中的序号称号子串的位置

（3）串相等：当且仅当两个串的长度相等且对应位置上字符都相同，称两个串是相等的

二、串的表示和实现

与线性表类似，串也可以利用顺序存储结构或链式存储结构进行表示

2.1 串的顺序存储表示

类似于顺序表，串的顺序存储表示用一组地址连续的存储单元存储串值中的字符序列。实现串的顺序结构有静态字符数组和动态字符数组两种方式

由于采用静态数组实现的顺序串的存储空间大小不能随意改变，因此进行串的连接时可能产生截断问题，另外在插入和删除时也不方便，所以一般采用动态数组实现

#define INITSIZE 128
#define INCRE 20
#define OK
#define ERROR 0
typedef struct{
    char * data;     //存放串中字符
    int length;       //串的长度
    int stringsize;   //当前串的存储空间
}SqString;

以下讨论串的基本操作实现

2.1.1 串初始化

int InitString(SqString *S){
  S->data=(char *)malloc(INITSIZE*sizeof(char));  //申请串的初始存储空间
  if(!S->data) return ERROR;
  S->length=0;
  S->stringsize=INITSIZE;
  return OK;
}

2.1.2 求串长

int StrLength(SqString *S){
  return S->length;
}

2.1.3 判断串是否为空

int StrEmpty(SqString *S){
  if(S->length==0) return OK;
  else return ERROR;
}

2.1.4 串赋值

int StrAssign(SqString *S,char *str){
  int i=0;
  while(*str){    //依次将str复制到串S
    S->data[i++]=*str++;
  }
  S->data[i]='\0';   //设置串结束符
  S->length=i;     //置当前串长
  return OK;
}

2.1.5 串复制

int StrCopy(SqString *S,SqString *T){
  int i=0;
  S->length=T->length;
  while(i<T->length){     //循环复制T中的字符到串S
    S->data[i]=T->data[i++];
  }
  S->data[i]='\0';
}

2.1.6 串比较

两个串S和T比较，若S==T，返回值为0；若S<T，返回值小于0；若S>T，返回值大于0

int StrCompare(SqString *S,SqString *T){
  int i;       
  for(i=0;i<S->length&&i<T->length;i++)   //依次比较两个串对应字符
    if(S->data[i]!=T->data)        //出现不等，则返回两个字符的差
      return S->data[i]-T->data[i];  
  return S->length-T->length;     //对应字符相等，则比较两个串长度是否相等
}

2.1.7 取子串

串S的第pos个字符开始长度为len的连续字符序列赋给子串Sub

int SubString(SqString *Sub,SqString *S,int pos,int len){
  int i;
  if(pos<1||pos>S->length||len<0||len>S->length-pos+1)
      return ERROR;
  Sub->length=0;       //初始化子串，置为空串
  for(i=0;i<len;i++){      //从起始位置开始依次给子串赋len个字符
    Sub->data[i]=S->data[i+pos-1];
    Sub->length++;
  }
  Sub->data[i]='\0';
  return OK;
}

2.1.8 串连接

把两个串s1和s2首尾连接成一个新串

int StrConcat(SqString *S,SqString *s1,SqString *s2){
  int i=0,j=0;
  if(s1->length+s2->length>=S->stringsize){
    S->data=(char *)realloc(S->data,(S->stringsize+INCRE)*sizeof(char));
    if(!S->data) return ERROR;   //若两个串长度和超过新串S的存储容量，申请增加串S空间
    S->stringsize+=INCRE;
  }
  while(i<s1->length){          //将串s1字符依次复制到串S中
    S->data[i]=s1->data[i++];     
  }
  while(j<s2->length){           //继续将串s2字符依次复制到串S中
    S->data[i++]=s2->data[j++]; 
  }
  S->data[i]='\0';
  S->length=s1->length+s2->length;  //修改串S长度为s1和s2串长和
  return OK;
}

2.2 串的链式存储表示

和线性表的链式存储结构相类似，也可采用链表方式存储串值。由于串结构中的每一个数据元素是一个字符，则用链表存储串值时，存在一个“结点大小”的问题，即每个结点可以存放一个字符，也可以存放多个字符。

为了便于进行串的操作，当以链表存储串值时，除头指针外可增设一个尾指针指示链表中的最后一个结点，并给出当前串的长度。称如此定义的串存储结构为块链结构。

#define NODESIZE 20       //由用户定义块大小 
typedef struct Node{
  char ch[NODESIZE];    
  struct Node * next;
}Node;
typedef struct Link{
  Node * head,*tail;    //串的头指针和尾指针 
  int curlen;          //串的当前长度 
}Link;