您的位置: 网站首页 > 程序开发 > 数据结构 > 第4章 串、数组和广义表 > 【4.4 串操作应用举例】

4.4 串操作应用举例

 

4.4  串操作应用举例

4.4.1  文本编辑

文本编辑程序是一个面向用户的系统服务程序,广泛用于源程序的输入和修改,甚至用于报刊和书籍的编辑排版以及办公室的公文书稿的起草和润色。文本编辑的实质是修改字符数据的形式或格式。虽然各种文本编辑程序的功能强弱不同,但是其基本操作是一致的,一般都包括串的查找、插入和删除等基本操作。

为了编辑的方便,用户可以利用换页符和换行符把文本划分为若干页,每页有若干行(当然,也可不分页而把文件直接划成若干行)。我们可以把文本看成是一个字符串,称为文本串。页则是文本串的子串,行又是页的子串。

比如有下列一段源程序:

main()

{

   float a,b,max;

   scanf("%f,%f",&a,&b);

   if (a>b)

      max=a;

   else

      max=b;

};

可以把此程序看成是一个文本串。输入到内存后如图4-4所示。

201

M

a

i

n

(

)

{

 

 

f

l

o

a

t

 

a

,

b

,

M

a

x

;

 

 

s

c

a

n

f

{

%

f

,

%

f

,

&

a

,

&

b

)

;

 

 

i

f

 

a

b

 

 

m

a

x

=

a

;

 

 

e

l

s

e

 

 

m

a

x

=

b

;

}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4-4  文本格式示例

为了管理文本串的页和行,在进入文本编辑的时候,编辑程序先为文本串建立相应的页表和行表,即建立各子串的存储映象。页表的每一项给出了页号和该页的起始行号。而行表的每一项则指示每一行的行号、起始地址和该行子串的长度。假设图4-3所示文本串只占一页,且起始行号为100,则该文本串的行表如图4-5所示。

 

起始地址

 

100

201

8

101

209

17

102

226

24

103

250

17

104

267

15

105

282

2

4-5  4-4所示文本串的行表

文本编辑程序中设立页指针、行指针和字符指针,分别指示当前操作的页、行和字符。

如果在某行内插入或删除若干字符,则要修改行表中该行的长度。若该行的长度超出了分配给它的存储空间,则要为该行重新分配存储空间,同时还要修改该行的起始位置。如果要插入或删除一行,就要涉及行表的插入或删除。若被删除的行是所在页的起始行,则还要修改页表中相应页的起始行号(修改为下一行的行号)。为了查找方便,行表是按行号递增顺序存储的,因此,对行表进行的插入或删除运算需移动操作位置以后的全部表项。页表的维护与行表类似,在此不再赘述。由于访问是以页表和行表作为索引的,所以在作行和页的删除操作时,可以只对行表和页表作相应的修改,不必删除所涉及的字符。这可以节省不少时间。

以上概述了文本编辑程序中的基本操作。其具体的算法,读者可在学习本章之后自行编写。

4.4.2  建立词索引表

信息检索是计算机应用的重要领域之一,由于信息检索的主要操作是在大量的存放在磁盘上的信息中查询一个特定的信息,为了提高查询效率,我们就必须建立一个索引表。索引表也可以看成是文本串的形式,也是串的操作应用之一。