串的定义及基本运算

1上机实训3：串的基本操作一、实训目的通过实训，掌握串的运算（赋值，比较，联结，插入子串，模式匹配……等）二、实验理论知识1)串的基本概念及其含义串( string)是由零个或多个字符组成的有限序列，一般记作:s='a1a2…an'(n≥0)，其中s为串的名字，用单引号括起来的字符序列为串的值；ai(1≤i≤n)可以是字母、数字或其它字符（取决于程序设计语言所使用的字符集）；n为串中字符的个数，称为串的长度。

2)串的存储表示及其实现●顺序存储可以用一组地址连续的存储单元依次存放串的各个字符，这是串的顺序存储结构，也称为顺序串●链式存储和线性表的链式存储结构相类似，也可采用链表方式存储串值。

串的这种链式存储结构简称为链串。

用链表存储字符串，每个结点需要有两个域：一个数据域（data）和一个指针域(Next)，其中数据域存放串中的字符，指针域存放后继结点的地址。

3)模式匹配问题三、实训案例与分析【实例1】串的存储与基本运算【实例分析】在本实例中练习计算字符串的长度、字符串的复制、字符串的比较、字符串的连接、字符串的插入等基本操作。

在设计时1)编写一个菜单函数，根据不同情况做（1-5）不同选择。

2)如果选择1，即要求计算输入字符串的长度。

3)如果选择2，完成字符串的复制。

4)如果选择3，完成字符串的比较。

5)如果选择4，完成两个字符串的连接。

6)如果选择5，字符串的插入。

【参考程序】#include <stdio.h>#define MAX 128typedef enum {fail,success} status;typedef enum {false,true} boolean;main(){ int strlen();void strass();boolean strcmp();status strcat( );status strins();int t,n,i;boolean b;status st;char s[MAX],s1[MAX],s2[MAX];printf("\n1. The length of string\n");printf(" 2. The assignment of string\n");printf(" 3. A string compare with another string:\n"); printf(" 4. A string connect with another string:\n"); printf(" 5. A string to be inserted into another string\n"); printf(" Please input a operation:");/*输入操作选项*/ scanf("%d",&t);switch(t){case 1:printf("please input a string:\n");getchar();gets(s);n=strlen(s);printf("the length is: %d",n);break;case 2:printf("please input the first string:\n");getchar();gets(s1);printf("please input the second string:\n");getchar();gets(s2);strass(s1,s2);break;case 3:printf("please input the first string:\n"); getchar();gets(s1);printf("please input the second string: \n"); gets(s2);b=strcmp(s1,s2);if (b==true)printf("equal\n");elseprintf("not equal\n");break;case 4:printf("please input the first string:\n"); getchar();gets(s1);printf("please input the second string:\n"); gets(s2);st=strcat(s1,s2);if(st==success)printf("answer is %s\n",s1);elseprintf("error!\n");break;case 5:printf("please input the first string:\n"); getchar();gets(s1);printf("please input the second string:\n"); gets(s2);printf("please input i:");scanf("%d",&i);st=strins(s1,i,s2);if(st==success)printf("answer is: %s\n",s1);else printf("error!\n");break;case 0:break;default: printf("There isn't this operation!");}}int strlen(s) /*求字符串的长度子函数*/char s[];{ int i;for(i=0;s[i]!='\0';i++);return (i);}void strass(s1,s2)char s1[],s2[];{ int i=0;while(s1[i]!='\0'){ s2[i]=s1[i];i++;}s2[i]='\0';printf("s2 is %s",s2);}boolean strcmp(s1,s2) /*字符串比较子函数*/ char s1[],s2[];{ int i=0;while (s1[i]==s2[i] && s1[i]!='\0' && s2[i]!='\0') i++;if (s1[i]=='\0' && s2[i]=='\0')return (true);elsereturn (false);}status strcat (s1,s2) /*字符串连接子函数*/char s1[],s2[];{ int i,j,k;i=strlen(s1);j=strlen(s2);if((i+j)>=MAXN)return(fail);for(k=0;k<=j;k++)s1[i+k]=s2[k];return (success);}status strins (s1,i,s2)char s1[],s2[];int i;{ int m,n,k;m=strlen(s1);n=strlen(s2);if (i<0||i>m||(m+n)>MAXN )return (fail) ;for(k=m;k>=i;k--)s1[k+n]=s1[k];for(k=0;k<n;k++)s1[i+k]=s2[k];return (success);}【测试数据与结果：】计算字符串的长度1. The length of string2. The assignment of string3. A string compare with another string:4. A string connect with another string:5. A string to be inserted into another string Please input a opertation:1please input a string:you are a boy!the length is: 14字符串的复制1. The length of string2. The assignment of string3. A string compare with another string:4. A string connect with another string:5. A string to be inserted into another string Please input a opertation:2please input the first string:you are a boy!please input the second string:i am a girl!s2 is you are a boy!字符串的比较1. The length of string2. The assignment of string3. A string compare with another string:4. A string connect with another string:5. A string to be inserted into another string Please input a opertation:3please input the first string:you are a boy!please input the second string:i am a girl!not equal字符串的连接1. The length of string2. The assignment of string3. A string compare with another string:4. A string connect with another string:5. A string to be inserted into another stringPlease input a opertation:4please input the first string:you are a boy!please input the second string:i am a girl!answer is：you are a boy!i am a girl!字符串的插入1. The length of string2. The assignment of string3. A string compare with another string:4. A string connect with another string:5. A string to be inserted into another stringPlease input a opertation:5please input the first string:you are a boy!please input the second string:i am a girl!please input i:2answer is i am a girl! you are a boy!【实例2】统计主串指定单词在主串中出现的次数和位置【实例描述】统计主串指定单词在主串中出现的次数和位置，要求：1)输入以回车作为结束符的一串字符作为主串；2)求主串中指定单词出现的次数和位置，注意单词与子串的区别；【实例分析】假设num存放出现次数，初始化为0，position[i]存放每一次匹配时的位置。

Chapter 4 串4.1 串的定义及其运算4.2 串的表示和实现4.3 串的模式匹配算法4.4 串的应用——文本编辑本章重点:1. 串的定义及基本操作的确切含义。

2. 串的存储结构（顺序、链式）的描述方法。

3. 串的模式匹配算法，尤其是KMP 算法中next 函数的定义及如何计算给定模式串的next 函数值。

本章难点:1. 在串的顺序存储结构上实现串的各种操作的方法。

2. 串匹配的KMP 算法。

4.1 串的定义及其运算一、串的基本概念1.字符（Char ）：字母、数字、其它符号。

2.串（String ）：由n(n ≥0)个字符组成的有限序列。

记为：S=“a 0a 1…a n-1”。

其中，S 是串的名，称为串名，a 0a 1…a n-1是串的值，称为串值。

串中字符的数目称为串的长度。

名值名值A=“1234”S=“abcde”例：注意：双引号“和”不属于S 的值，其作用只是为了避免与其他符号混淆。

3.空串（Null String ）：不含任何字符的串。

用“”或Φ表示。

其长度为0。

4.空格串（Blank String ）：仅含空格字符的串（即由一个或多个空格字符组成的串）。

例：长度为2的空格串记作“”或“φφ”5.子串（Substring ）：串中的一个连续字符子序列叫做该串的一个子串。

对应地，该串就称为主串。

例：A=“123456”，B=“456”，C=“46”B 为A 的子串，A 为主串；C 不是A 的子串。

二、串的基本运算1.初始化Initiate(S)2.赋值Assign(S, T)例：T=“DATA”，则执行Assign(S,T)后，S 的值就等于“DATA”。

注：后一个参数可为串变量名，也可为字符序列。

3.求长度Length(S)4.比较Compare(S, T)比较结果有三种：S 大于T ，S 等于T ，S 小于T 。

5.插入Insert(S, pos, T)若0≤pos ≤Length(S)，则在串S 的第pos 个字符之前插入串T ，串S 的新长度为Length(S)+Length(T)。