数据结构实验四字符串的应用

更新时间：2023-11-26 02:41:01 阅读量：教育文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

第四章字符串的应用

【实验目的】

1. 熟练掌握字符串的数据类型定义以及字符串的五种基本操作的定义，并能利用这些基本操作实现字符串的其他基本操作的方法。

2. 熟练掌握字符串串的定长顺序存储结构上实现字符串的各种操作的方法。 3. 理解字符串的堆分配存储表示以及在其上实现字符串操作的基本方法。

4. 熟练掌握串的基本操作类型的实现方法，其中文本模式匹配方法是一个难点，在掌握了BF算法的基础上理解改进的KMP算法。

5. 了解一般文字处理软件的设计方法。

第一节知识准备

一、有关串几个重要概念

1. 串（字符串）：零个或多个字符组成的有限序列。一般记作s=\?an\ 2. 长度：串中字符的数目

3. 空串：零个字符的串，其长度为零

4. 子串和主串：串中任意个连续的字符组成的子序列称为该串的子串；包含子串的串相应地称为主串，字符在序列中的序号为该字符在串中的位置。

5. 当两个串的长度相等，并且各个对应位置的字符都相等时称为两串相等。 6. 空格串：由一个或多个空格组成的串‘ ’，同空串是完全不同的。

二、串的抽象数据类型定义 ADT String{

数据对象：D={ | ∈CharacterSet, i=1,2,...,n, n>=0} 数据关系：R1={< , >| , ∈D, i=2,...,n} 基本操作：

Assign(&s,t) 将串t的值赋给串 s Create(&s,ss) 将串s的值设定为字符序列ss Equal(s,t) 判定串s和串t是否相等 Length(s) 求串s的长度

Concat(&s,t) 将串s和串t连接成一个串，结果存于s中

Substr(&sub,s,start,len) 从s的第start个字符起，取长为len的子串存于sub Index(s,t) 求子串t在主串s中第一次出现的位置 Replace(&s,t,v) 以串v替换串s中的所有的非空子串t Insert(&s,pos,t) 在串s的第pos个字符之前插入串t；

Delete(&s,pos,len) 从串s中删去从第pos个字符起长度为len的子串； } ADT String 三、串的存储结构 1. 定长顺序存储表示

用一组地址连续的存储单元来存放字符序列，并约定该结构能存放字符的个数。 #define MAXLEN 字符最大个数 typedef struct {int len;

char ch[MAXLEN]; } SString; 2. 堆分配存储表示

系统先分配一个容量很大的地址连续的存储空间作为字符串的存放空间，每建立一个新串，系统从该空间中分配一个大小和串长相同的空间来存放新串。 typedef Struct { char *ch ; //存储空间基址 int length; //串的长度 }Hstring;

3. 串的块链存储表示

用链表形式来存储串，如果以串中每一个字符作为一个结点，使得相应的存储占用量增大，因此可采用将多个字符作为一个结点的形式来形成链表(即块链形式) #define MAX 80 //用户定义块的大小 typedef struct str {char ch[MAX]; struct str *next; }Chunk;

typedef struct string { Chunk *head,*tail; int length; }LString

在串的处理操作中，我们可视不同的情况进行选择使用不同的定义形式，当对字符串进行连接，删除等操作时，采用链结构更为方便上些，但采用链结构在进行串的截取(求子串)等操作时则比采用静态结构效率更低。

第二节串的基本操作示例

【问题描述】用C语言实现串的一些基本操作算法。【数据描述】

采用静态存储结构来表示串，用一维字符数组来存放字符序列，用整数len来表示当前串实际长度。 #define STRINGMAX 81 //串最多存放字符的个数 struct string {int len;

char ch[STRINGMAX]; };

typedef struct string STRING; 【C源程序】

本程序只设计了串的创建，联接，求子串和删除操作，其余各基本操作可在本程序基础上进行改进，补充。

#include \ #include \ #define STRINGMAX 81

#define LEN sizeof(struct string)/* 串的定义*/ struct string {int len;

char ch[STRINGMAX]; };

typedef struct string STRING;