C语言数据结构-第四章串-电大同步进度

阳光穿透心脏的1/2处 2022-11-14 13:12 220阅读 0赞

# 第四章 串 #

字符串是计算机处理的最基本的非数值数据。字符串是一种特定的线性表,其特殊性就在于组成线性表的每个元素就是一个单字符。

本章给出：

l         串的基本概念

l         串的顺序存储结构和基本操作实现

l         串的链式存储结构和基本操作实现

l         讨论串的模式匹配算法及改进的模式匹配算法。

# 第一讲 串的基本概念——内容简介 #

本节主要介绍：

l         串的基本概念

l         串的抽象数据类型定义

了解串与线性表的异同。

# **1****、串的基本概念** #

**字符串（**String）是由零个或多个字符组成的有限序列。记为:S = ′a1 a2 … an′( n ≥ 0 )

其中 S 是串的名字,用单引号括起来的字符序列是串的值,每个 ai( 1 ≤ i≤ n)可以是字母、数字或其他字符。 n 是串中字符的个数,称为串的长度,n=0 时的串称为空串( Null String)。

需要特别指出的是,串值必须用一对单引号括起来( C 语言中是双引号),但单引号是界限符,它不属于串,其作用是避免与变量名或常量混淆。

**子串**:串中任意个连续的字符组成的子序列称为该串的子串。

**主串**:包含子串的串相应地称为主串。可见,子串是主串的一部分。

**子串在主串中的位置**:通常将字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。

**串相等**:当且仅当两个串的值相等时,称这两个串是相等的,即只有当两个串的长度相等,并且每个对应位置的字符都相等时才相等。

串也是一种特定的线性表,串的逻辑结构和线性表极为相似,其特定性仅在于串的数据对象限定为字符集。

### **2****、串的抽象数据类型定义如下****:** ###

ADT String \{

**数据对象**: D=\{  ![a\_\{i\}][a_i] | ![a\_\{i\}][a_i]∈ CharacterSet，记为 V，i=1 ,2 ,…, n,n≥ 0 \}

**结构关系**: R=\{< ![a\_\{i\}][a_i],![a\_\{i+1\}][a_i_1] >| ![a\_\{i\}][a_i]，![a\_\{i+1\}][a_i_1]∈ V，i=1 ,…, n-1 ; n-1 ≥ 0 \}

**基本操作**:

( 1 ) StrAsign( S,chars)

操作前提: chars 是字符串常量。

操作结果:生成一个值等于 chars 的串 S。

( 2 ) StrInsert( S,pos,T)

操作前提:串 S 存在,1 ≤ pos≤ StrLength( S)+ 1 。

操作结果:在串 S 的第 pos 个字符之前插入串 T。

( 3 ) StrDelete( S,pos,len)

操作前提:串 S 存在,1 ≤ pos≤ StrLength( S)+ 1 。

操作结果:从串 S 中删除第 pos 个字符起长度为 len 的子串。

( 4 ) StrCopy( S,T)

操作前提:串 S 存在。

操作结果:由串 T 复制得串 S。

( 5 ) StrEmpty( S)

操作前提:串 S 存在。

操作结果:若串 S 为空串,则返回 TRUE,否则返回 FALSE。

( 6 ) StrCompare( S,T)

操作前提:串 S 和 T 存在。

操作结果:若 S>T,则返回值>0 ;如 S=T,则返回值=0 ;若 S<T,则返回值<0 。

( 7 ) StrLength( S)

操作前提:串 S 存在。

操作结果:返回串 S 的长度,即串 S 中的字符个数。

( 8 ) StrClear( S)

操作前提:串 S 存在。

操作结果:将 S 清为空串。

( 9 ) StrCat( S,T)

操作前提:串 S 和 T 存在。

操作结果:将串 T 的值连接在串 S 的后面。

( 10 ) SubString( Sub,S,pos,len)

操作前提:串 S 存在,1 ≤ pos≤ StrLength( S)且 1 ≤ len≤ StrLength( S)-pos+1 。

操作结果:用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。

( 11 ) StrIndex( S,pos,T)

操作前提:串 S 和 T 存在,T 是非空串,1 ≤ pos≤ StrLength( S)。

操作结果:若串 S 中存在和串 T 相同的子串,则返回它在串 S 中第 pos 个字符之后第一次出现的位置;否则返回 0 。

( 12 ) StrReplace( S,T,V)

操作前提:串 S、 T 和 V 存在且 T 是非空串。

操作结果:用 V 替换串 S 中出现的所有与 T 相等的不重叠的子串。

( 13 ) StrDestroy( S)

操作前提:串 S 存在。

操作结果:销毁串 S。

\}ADT string

**【****本节要点****】**

串是特定的线性表

串的 ADT

### 作业 ###

设s=‘abcd’,s1=‘123’，则执行语句StrInsert( s,2,s1)后，s=           .

*  A.‘123abcd’
 *  **B.‘a123bcd’**
 *  C.‘ab123cd’
 *  D.‘abc123d’

设s=‘abcd’，则执行语句StrDelete( s,2,2)后，s=           .

*  A.‘abcd’
 *  B.‘abc’
 *  **C.‘ad’**
 *  D.‘a’

# 第二讲 串的顺序存储结构——内容简介 #

本节主要介绍：

串的顺序存储结构包括：

*  定长顺序串
 *  堆串

及在两种存储下的基本操作。

# 第 2 讲串的顺序存储结构 #

串的顺序存储结构有定长顺序串、堆串。

### **1****、定长顺序串** ###

定长顺序串是将串设计成一种静态结构类型,串的存储分配是在编译时完成的。与前面所讲的线性表的顺序存储结构类似,可用一组地址连续的存储单元存储串的字符序列。

### **1****）定长顺序串存储结构** ###

定长顺序串类型定义如下:

#define MAXLEN 40
    typedef struct {                /*串结构定义*/
    	char ch[MAXLEN];
    	int len;
    }SString;

其中 MAXLEN 表示串的最大长度,ch 是存储字符串的一维数组,每个分量存储一个字符,len 是字符串的长度。

### **2****）****.****定长顺序串基本操作的实现** ###

( 1 )串插入函数

**【问题分析】**在进行顺序串的插入时,插入位置 pos 将串分为两部分(假设为 A、 B,长度为LA、 LB)

及待插入部分(假设为 C,长度为 LC),则串由插入前的 AB 变为 ACB,由于是顺序串,插入会引起元素的移动。可能出现以下三种情况:

①插入后串长( LA+LC \+LB)≤ MAXLEN,则将 B 后移 LC 个元素位置,再将 C 插入。

②插入后串长>MAXLEN 且 pos+LC≤ MAXLEN,则 B 后移时会有部分字符被舍弃。

③插入后串长> MAXLEN 且 pos \+LC >MAXLEN,则 B 的全部字符被舍弃(不需后移),并且 C 在插入时也有部分字符被舍弃。

【算法描述】

int StrInsert(SString *s, int pos, SString t)
    /*在串s中下标为pos的字符之前插入串t */
    {
    	int i;
    	if (pos<0 || pos>s->len) /*插入位置不合法*/
    		return(0); 
    	if (s->len + t.len<=MAXLEN) /*插入后串长≤MAXLEN*/
    	{
    		for (i=s->len + t.len-1;i>=t.len + pos;i--)
    			s->ch[i]=s->ch[i-t.len];
    		for (i=0;i<t.len;i++) 
    			s->ch[i+pos]=t.ch[i];
    		s->len=s->len+t.len;
    	}
    	else
    	{
    		if (pos+t.len<=MAXLEN) /*插入后串长>MAXLEN,但串t的字符序列可以全部插入*/
    		{
    			for (i=MAXLEN-1;i>t.len+pos-1;i--) 
    				s->ch[i]=s->ch[i-t.len];
    			for (i=0;i<t.len;i++)
    				s->ch[i+pos]=t.ch[i];
    			s->len=MAXLEN;
    		}
    		else /*插入后串长>MAXLEN,并且串t的部分字符也要舍弃*/
    		{ 
    			for (i=0;i<MAXLEN-pos;i++)
    				s->ch[i+pos]=t.ch[i];
    			s->len=MAXLEN;
    		}
    		return(1);
    	}
    }

完整程序

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAXLEN 40
    typedef struct {          /*串结构定义*/
    	char ch[MAXLEN];
    	int len;
    }SString;
    
    void createstring(SString* s)
    {
    	int i, j;
    	char c;
    	printf("请输入要建立的串的长度:");
    	scanf("%d", &j);
    	for (i = 0; i < j; i++)
    	{
    		printf("请输入串的第%d个字符:", i + 1);
    		fflush(stdin);
    		scanf("%c", &c);
    		s->ch[i] = c;
    	}
    	s->len = j;
    }
    
    void output(SString* s)
    {
    	int i;
    	for (i = 0; i < s->len; i++)
    		printf("%c   ", s->ch[i]);
    	printf("\n");
    }
    
    int StrInsert(SString* s, int pos, SString t)
    /*在串s中下标为pos的字符之前插入串t */
    {
    	int i;
    	if (pos<0 || pos>s->len) /*插入位置不合法*/
    		return(0);
    	if (s->len + t.len <= MAXLEN) /*插入后串长≤MAXLEN*/
    	{
    		for (i = s->len + t.len - 1; i >= t.len + pos; i--)
    			s->ch[i] = s->ch[i - t.len];
    		for (i = 0; i < t.len; i++)
    			s->ch[i + pos] = t.ch[i];
    		s->len = s->len + t.len;
    	}
    	else
    	{
    		if (pos + t.len <= MAXLEN) /*插入后串长>MAXLEN,但串t的字符序列可以全部插入*/
    		{
    			for (i = MAXLEN - 1; i > t.len + pos - 1; i--)
    				s->ch[i] = s->ch[i - t.len];
    			for (i = 0; i < t.len; i++)
    				s->ch[i + pos] = t.ch[i];
    			s->len = MAXLEN;
    		}
    		else /*插入后串长>MAXLEN,并且串t的部分字符也要舍弃*/
    		{
    			for (i = 0; i < MAXLEN - pos; i++)
    				s->ch[i + pos] = t.ch[i];
    			s->len = MAXLEN;
    		}
    		return(1);
    	}
    }
    
    
    void main()
    {
    	SString* str1;
    	SString  str2;
    	int i, j, k, pos;
    	int flag = 0;
    	str1 = (SString*)malloc(sizeof(SString));
    	str1->len = 0;
    	printf("建立字符串1:\n");
    	createstring(str1);
    	printf("建立字符串2:\n");
    	createstring(&str2);
    	printf("请输入要插入的位置:");
    	scanf("%d", &pos);
    	flag = StrInsert(str1, pos, str2);
    	if (flag == 0)
    		printf("插入操作失败!");
    	else
    	{
    		printf("插入后串为:\n");
    		output(str1);
    	}
    
    }

显然,实现顺序串插入的算法其实现复杂度为: O( s->len+t.len)。

( 2 )串删除函数

int StrDelete(SString *s, int pos, int len)
    /*在串s中删除从下标pos起len个字符*/
    { 
    	int i;
    	if (pos<0 || pos>(s->len-len))/*删除参数不合法*/
    		return(0); 
    	for (i=pos+len;i<s->len;i++)
    		s->ch[i-len]=s->ch[i]; /*从pos+len开始至串尾依次向前移动，实现删除len个字符*/
    	s->len=s->len - len; /*s串长减len*/
    	return(1);
    }

完整程序

#define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<stdlib.h>
    
    #define MAXLEN 40
    typedef struct {          /*串结构定义*/
    	char ch[MAXLEN];
    	int len;
    }SString;
    
    void createstring(SString* s)
    {
    	int i, j;
    	char c;
    	printf("请输入要建立的串的长度:");
    	scanf("%d", &j);
    	for (i = 0; i < j; i++)
    	{
    		printf("请输入串的第%d个字符:", i + 1);
    		fflush(stdin);
    		scanf("%c", &c);
    		s->ch[i] = c;
    	}
    	s->len = j;
    }
    
    void output(SString* s)
    {
    	int i;
    	for (i = 0; i < s->len; i++)
    		printf("%c   ", s->ch[i]);
    	printf("\n");
    }
    
    int StrDelete(SString* s, int pos, int len)
    /*在串s中删除从下标pos起len个字符*/
    {
    	int i;
    	if (pos<0 || pos>(s->len - len))/*删除参数不合法*/
    		return(0);
    	for (i = pos + len; i < s->len; i++)
    		s->ch[i - len] = s->ch[i]; /*从pos+len开始至串尾依次向前移动，实现删除len个字符*/
    	s->len = s->len - len; /*s串长减len*/
    	return(1);
    }
    
    void main()
    {
    	SString* str1;
    	int j, pos;
    	int flag = 0;
    	str1 = (SString*)malloc(sizeof(SString));
    	str1->len = 0;
    	printf("建立字符串1:\n");
    	createstring(str1);
    	printf("请输入删除位置和长度:\n");
    	fflush(stdin);
    	scanf("%d,%d", &pos, &j);
    	flag = StrDelete(str1, pos, j);
    	if (flag == 0)
    		printf("删除操作失败!");
    	else
    	{
    		printf("删除后串为:\n");
    		output(str1);
    	}
    
    }

（3）串的简单模式匹配 Brute-Force(布鲁特\-福斯)算法

【算法思想】

简单的模式匹配算法是一种带回溯的匹配算法，

算法的基本思想是:从主串S 的第 pos 个字符开始,和模式串 T 的第一个字符开始比较,

如果相等,就继续比较后续字符,

如果不等,则从(回溯到)主串 S 的第 pos+1 个字符开始重新和模式串 T 比较,

直到模式串 T 中的每一个字符和主串 S 中的一个连续字符子序列全部相等,则称匹配成功,

返回和 T 中第一个字符相等的字符在主串 S 中的位置;或者主串中没有和模式串相等的字符序列,则称匹配不成功。

【算法描述】

实现时设 i、 j、 start 三个指示器:

i——指向主串 S 中当前比较的字符,起始指向 S 的首字符,此后,每比较一步,后移一步,一趟匹配失败时,回溯到该趟比较起点的下一位置。

j———指向子串 T 中当前比较的字符,起始指向 T 的首字符,此后,每比较一步,后移一步,一趟匹配失败时,回溯到 T 的首字符处。

start———记录每趟比较时在主串 S 中的起点,每趟比较后,后移一步,以便确定下一趟的起始位置。

**例**** ****4**** ****-1**      图 4 .1 给出了一个匹配过程的例子,其中方框对应的字符为失配字符。

![20210329145932900.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 4][]

顺序串的简单模式匹配(定位)函数

Link *StrIndex(LKString *s, LKString *t)
    /*求子串t在主串s中第一次出现的位置指针*/
    {
    	Link *sp,*tp,*pre;	
    	if (t->len == 0) 
    		return NULL;/*子串是空串，则返回*/
    	
    	sp = s->head->next;/*主串第一个结点指针*/
    	tp = t->head->next;/*子串第一个结点指针*/
    	
    	pre = sp;/*记录当前串比较的起始位置指针*/
    	while(sp != NULL && tp != NULL)
    	{
    		if (sp->ch == tp->ch) {
    			/*若当前sp和tp的字符都相同，则继续比较*/
    			sp = sp->next;
    			tp = tp->next;
    		}
    		else
    		{
    			/*返回到串比较起始位置的下一个结点继续比较*/
    			sp = pre->next;
    			pre = sp;/*更新比较的起始位置*/
    			tp = t->head->next;/*子串第一个结点*/
    		}
    	}
    	if ( tp == NULL) {
    		/*匹配成功，返回位置指针*/
    		return pre;
    	}
    	else
    		return NULL;/*匹配不成功，返回空指针*/
    }

【算法分析】该算法思路比较简单,但最坏时间复杂度较高,为 O( s.len\* t.len)

如主串为51 个 0 ,模式串为 7 个 0 后有个 1

每趟都在最后一个不匹配后而倒到 start+1

整个匹配过程共需 s.len- t.len=45 趟

每趟比较 t.len=8 个字符,故此例整个比较了 360 次

这个算法的主要时间耗费在失配后的比较位置有回溯,造成了比较次数太多的情况。降低时间复杂度可采用无回溯的算法

### **2****、堆****串** ###

字符串包括串名与串值两部分,而串值采用堆串存储方法存储,串名用符号表存储。

**堆串存储方法****:**仍以一组地址连续的存储单元顺序存放串中的字符,但它们的存储空间是在程序执行过程中是动态分配的。

系统将一个地址连续、容量很大的存储空间作为字符串的可用空间,每当建立一个新串时,系统就从这个空间中分配一个大小和字符串长度相同的空间存储新串的串值。

**串名符号表**:所有串名的存储映像构成一个符号表。借助此结构可以在串名和串值之间建立一个对应关系,称为串名的存储映像。

下图是一个堆串存储及符号表的示例，其中 a='a program'，b='string '，c='process'，free=23。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 5][]

**1****）堆串存储表示****:** C 语言已经有一个称为“堆”的自由存储空间,并可用函数malloc()和函数 free()完成动态存储管理。因此,可以直接利用 C 语言中的“堆”来实现堆串。此时堆串可定义如下:

typedef struct
    {
    	char* ch;
    	int len;
    }HString;

其中 len 域指示串的长度,ch 域指示串的起始地址。

**2****）堆串基本操作的实现**

( 1 )堆串插入函数

StrInsert(HString* s,int pos,HString* t)
    /*在串 s 中下标为 pos 的字符之前插入串 t */
    {
    	int i;
    	char* temp;
    	if (pos<0 || pos>s->len || s->len == 0) return(0); /*插入位置不合法*/
    	temp = (char*)malloc(s->len + t->len); /*动态产生足够的空间存放插入后的串*/
    	if (temp == NULL) return(0);
    	for (i = 0; i < pos; i++) temp[i] = s->ch[i];
    	for (i = 0; i < t->len; i++) temp[i + pos] = t->ch[i];
    	for (i = pos; i < s->len; i++) temp[i + t->len] = s->ch[i];
    	s->len += t->len;
    	free(s->ch);
    	s->ch = temp;
    	return(1);
    }

( 2 )堆串删除函数

StrDelete(HString* s,int pos,int len)
    /*在串 s 中删除从下标 pos 起 len 个字符 */
    {
    	int i;
    	char* temp;
    	if (pos<0 || pos>(s->len - len)) return(0); /*删除参数不合法*/
    	temp = (char*)malloc(s->len - len);
    	if (temp == NULL) return(0);
    	for (i = 0; i < pos; i++) temp[i] = s->ch[i];
    	for (i = pos; i < s->len - len; i++) temp[i] = s->ch[i + len];
    	s->len = s->len - len;
    	free(s->ch);
    	s->ch = temp;
    	return(1);
    }

**【本节要点】**

串的顺序存储结构：定长顺序串与堆串

定长顺序串的模式匹配算法。

### 作业 ###

假设主串S=‘aaabbbababaabb’,模式串T=‘abaa’,用串匹配算法从主串的第6个字符开始模式匹配，需要做  **4**   趟匹配，方能找到匹配串。

![20210329151607893.png][]

假设主串S=‘aaabbbababaabb’,模式串T=‘abaa’,用串匹配算法从主串的第6个字符开始模式匹配，在第2趟匹配中，要做 **4**  次比较。

![20210329151656648.png][]

# 第3讲 串的链式存储及串的应用——内容简介 #

本节主要介绍：

串的链式存储结构及基本操作。

包括：

l         单链表实现链串

l         块链串

# 第 3 讲串的链式存储与串的应用举例 #

### **1****、****块链串** ###

由于串也是一种线性表,因而也可以采用链式存储。

因为串是一个特殊的线性表(表中每个元素就是一个字符)。

在具体实现时,一个链表存放一个串值,每个结点既可以存放一个字符,也可以存放多个字符。

每个结点称为块,整个链表称为块链结构,为便于操作,再增加一个尾指针。

块链结构可定义如下：

#define	BLOCK_SIZE	4 /*每结点存放字符个数 4*/
    typedef struct Block {
    	char ch[BLOCK_SIZE];
    	struct Block* next;
    } Block;
    
    typedef struct {
    	Block* head;
    	Block* tail;
    	int len;
    } BLString;

**结点大小**:链表中的结点分成两个域 data 和 link,其中**结点大小是指**** data**** ****域中存放字符的****个数**

**链域大小是指** link 域中占用字符的个数

如果一个结点大小为 4 ,链域大小为 2 ,根据存储密度=串值占用的存储位/实际为串分配存储位,故该字符串的存储密度为 2 /3 。

显然,串的存储密度越小,运算处理就越方便,但存储占用的量较大。应根据具体情况来确定使用串的何种存储结构。

**结点大小等于**** ****1** :当 BLOCK\_SIZE 等于 1 时,每个结点存放 1 个字符,结构同线性链表,存储结构可定义如下,插入、删除的处理方法和线性链表一样,

参见本章典型题解部分串的链式模式匹配,算法处理简单,但存储密度较低。

**结点大于**** ****1** :当 BLOCK\_SIZE 大于 1 时,每个结点存放多个字符,当最后一个结点未存满时,不足处可用特定字符(如\#)补齐。

虽然存储密度相对结点大小等于 1 的存储方法来说,存储密度较高,但此时插入、删除的处理方法比较复杂,需要考虑结点的分拆和合并。

### **2****、串的应用举例****:****简单的行编辑器** ###

可将文本看成为一个大的字符串,文本编辑就相当对字符串的处理。

文本编辑程序用于源程序的输入和修改 ,公文书信、报刊和书籍的编辑排版等。

常用的文本编辑程序有Edit,WPS,Word 等。

文本编辑的实质是修改字符数据的形式和格式,虽然各个文本编辑程序的功能不同,但基本操作是一样的,都包括串的查找、插入和删除等。

为了编辑方便,可以用分页符和换行符将文本分为若干页,每页有若干行。

可以把文本当作一个字符串,称为文本串,页是文本串的子串,行是页的子串。

这里采用堆存储结构来存储文本,同时设立页指针、行指针和字符指针,分别指向当前操作的页、行和字符,同时建立页表和行表存储每一页、每一行的起始位置和长度。

假设有如下 Pascal 源程序：

FUNC max(x，y：integer)：integer;
    VAR z：integer;
    BEGIN
    IF x > y THEN z : = x;
    ELSE z : = y;
    RETURN(z);
    END;

该程序输入内存后放到一个堆中，如图 4.3 所示。其中↙为换行符。表 4－1 和表 4－2 分别为下图所示文本串的页表和行表。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 6][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 7][]

由表 4 \-1 、表 4 \-2 可以看出,当在某行内插入字符时,就要修改行表中该行的长度,

若该行的长度超出了分配给它的存储空间,则要重新给它分配存储空间,同时修改它的起始位置和长度。

如果要插入或删除一行,就要进行行表的插入和删除,当行的插入和删除涉及页的变化是时要对页表进行修改

### **3****、****总结与提高** ###

**1****、****主要知识点**

( 1 )字符串是一种特定的线性表,其特殊性就在于组成线性表的每个元素就是一个单字符。

( 2 )字符串常用的存储方式有三种:定长顺序串、堆串和块链串。

( 3 )定长顺序串以一维数组作为静态存储结构,运算实现类同顺序表。

堆串以动态分配的方式产生一组地址连续的存储单元顺序存放串中的字符，运算实现类同顺序串。块链串以链表作为存储结构,运算实现类同链表。

( 4 )串的模式匹配算法是本章的重点,简单的模式匹配算法处理思路简单,由于进行了带回溯的处理,时间复杂度较高。改进的** KMP ****模式匹配算法**计算滑动位置,因而失配后无回溯,匹配速度较高。

**2****、**** ****典型题例**

要求编写一个用带头结点的单链表实现串的模式匹配算法,每个结点存放一个字符(结点大小为 1 )。

借助于前面的结点大小为 1 定义链串类型 LKString。

【问题分析】该算法类同顺序串的简单模式匹配,实现匹配过程需考虑链表的特征(从头比较的技术,指针保留的技术)。

【算法思想】从主串 s 的第一个字符和模式串 t 的第一个字符开始比较,如果相等,就继续比较后续字符,如果不等,则从主串 s 的下一个字符开始重新和模式串 t 比较。一直到模式串 t 中的每一个字符依次和主串 s 中的对应字符相等,则匹配成功,返回主串的当前起始位置指针。如果主串中没有和模式串相同的子串,则称匹配不成功,返回空指针 NULL。

【算法描述】

typedef struct
    {
    	char* ch;
    	int len;
    }HString;
    
    StrInsert(HString* s,int pos,HString* t)
    /*在串 s 中下标为 pos 的字符之前插入串 t */
    {
    	int i;
    	char* temp;
    	if (pos<0 || pos>s->len || s->len == 0) return(0); /*插入位置不合法*/
    	temp = (char*)malloc(s->len + t->len); /*动态产生足够的空间存放插入后的串*/
    	if (temp == NULL) return(0);
    	for (i = 0; i < pos; i++) temp[i] = s->ch[i];
    	for (i = 0; i < t->len; i++) temp[i + pos] = t->ch[i];
    	for (i = pos; i < s->len; i++) temp[i + t->len] = s->ch[i];
    	s->len += t->len;
    	free(s->ch);
    	s->ch = temp;
    	return(1);
    }
    Link* StrIndex(LKString* s, LKString* t)
    /* 求模式串 t 在主串 s 中第一次出现的位置指针 */
    {
    	Link* sp, * tp, * start;
    	if (t->len == 0) return s->head->next;	/* 空串是任意串的子串 */
    	start = s->head->next;
    	/* 记录主串的起始比较位置 */
    	sp = start;	/* 主串从 start 开始 */
    	tp = t->head->next;
    	/* 模式串从第一个结点开始 */
    	while (sp != NULL && tp != NULL)
    	{
    		if (sp->ch == tp->ch)	/* 若当前对应字符相同，则继续比较 */
    		{
    			sp = sp->next;
    			tp = tp->next;
    		}
    		else	/* 发现失配字符，则返回到主串当前起始位置的下一个结点继续比较*/
    		{
    			start = start->next;	/* 更新主串的起始位置 */
    			sp = start;
    			tp = t->head->next;	/* 模式串从第一个结点重新开始 */
    		}
    	}
    	if (tp == NULL)	return	start;	/* 匹配成功，返回主串当前起始位置指针 */
    	else	return	NULL;	/* 匹配不成功，返回空指针 */
    }

### **4****、****本章小结** ###

串的基本概念

串的顺序存储：定长顺序串、堆串

串的链式存储：块链串

定长顺序串的模式匹配算法

串的应用举例

### 作业 ###

用带头结点的单链表来表示串s,则串s 为空串的条件是（  ）

*  **A.s->next==NULL**
 *  B.s==NULL
 *  C.s->next==s
 *  D.s->next->next==NULL

## 第四章 单元测验 ##

1单选(5分)

下面关于串的叙述中，不正确的是（    ）。

*  A.串既可以采用顺序存储，也可以采用链式存储。
 *  **B.空串是由空格构成的串。**
 *  C.串是字符的有限序列。
 *  D.模式匹配是串的一种重要运算 。

2单选(5分)

串的长度是指（    ）。

*  **A.串中所含字符的个数。**
 *  B.串中所含不同字母的个数。
 *  C.串中所含不同字符的个数。
 *  D.串中所含非空格字符的个数。

3单选(5分)

StrCompare(‘Computer’, ‘Compare’)的返回值是（    ）。

*  A.0
 *  **B.1**
 *  C.-1
 *  D.100

4单选(5分)

设有两个串S和T，其中T是S的子串，求T在S中首次出现的位置的算法称为（    ）。

得分/总分

*  A.联接
 *  B.串比较
 *  C.求子串
 *  **D.匹配**

5单选(5分)

串是一种特殊的线性表，其特殊性体现在（   ）。

*  A.数据元素可以是多个字符
 *  B.可以顺序存储
 *  **C.数据元素是一个字符**
 *  D.可以链式存储

6单选(5分)

假设空串是任何串的子串，则串S='Computer'的子串个数是（ ）。

*  A.9
 *  **B.37**
 *  C.36
 *  D.8

7单选(5分)

SubStr('DataStructure',5,3)的返回值是（   ）。

*  A.'aStrc' 
 *  B. 'taStr' 
 *  **C.'Str'**
 *  D. 'aSt'

8单选(5分)

两个串相等的充分必要条件是（    ）。

*  A.两个字符串存储形式相同
 *  B.两个字符串中对应位置上的字符相等
 *  **C.两个字符串的长度相等且对应位置上的字符也相等**
 *  D.两个字符串的长度相等

9单选(5分)

StrIndex(‘Index of String’,1,‘Str’）的值是（    ）。

*  A.11
 *  B.9
 *  C.12
 *  **D.10**

10单选(5分)

下列说法正确的是（   ）。

*  A.串中任意个字符组成的序列称为该串的子串。
 *  B.子串就是子序列。
 *  C.串中任意个连续字符组成的序列称为该串的子序列。
 *  **D.串中任意个连续字符组成的序列称为该串的子串。**

11判断(5分)

串是一种数据对象特殊的线性表。

*  **A.✓**
 *  B.×

判断(5分)

空格串是指由空格字符所组成的字符串，其长度等于空格个数。

*  **A.✓**
 *  B.×

判断(5分)

组成串的数据元素只能是字符。

*  **A.✓**
 *  B.×

判断(5分)

一个字符串中任意个连续的字符组成的子序列称为该串的子串 。

*  **A.✓**
 *  B.×

判断(5分)

空格串就是空串。

*  A.✓
 *  **B.×**

判断(5分)

串S=‘I Like DS.’的长度是8.

*  A.✓
 *  **B.×**

判断(5分)

串‘Computer’和串‘computer’相等。

*  A.✓
 *  **B.×**

判断(5分)

串中的元素可以是任意类型，只要这些元素属于同一数据对象即可。

*  A.✓
 *  **B.×**

判断(5分)

串只能采用顺序存储，不能用链式存储。

*  A.✓
 *  **B.×**

[a_i]: https://latex.codecogs.com/gif.latex?a_%7Bi%7D
[a_i_1]: https://latex.codecogs.com/gif.latex?a_%7Bi&plus;1%7D
[20210329145932900.png]: /images/20221022/c31e3b95475c4a6896b1a36316630cf2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70]: /images/20221022/9f3b2f12c68a465ea0931fbf125e036c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 1]: /images/20221022/9a8f4124ec884e36b7718fe546406249.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 2]: /images/20221022/acec6c521caf48b89511f0287ff8fc23.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 3]: /images/20221022/ed94a92088914a0e84eadb6d53140c20.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 4]: /images/20221022/87d4a29efe68420aba75c4d9b4a57b95.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 5]: /images/20221022/8067f6b2c34144f892db33b7712ecb2b.png
[20210329151607893.png]: /images/20221022/5a6f61b33eef4d4daa73f025b21a956f.png
[20210329151656648.png]: /images/20221022/a7ccfd669e644ccaaf2d043ed44c6caa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 6]: /images/20221022/99c3bc08593b4f6793fe02db668d5eee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20210329152447775.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY=,size_16,color_FFFFFF,t_70