數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用

數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用第四章

字符串的應(yīng)用【實驗?zāi)康摹?/p>

1.熟練掌握字符串的數(shù)據(jù)類型定義以及字符串的五種基本操作的定義，并能利用這些基本操作實現(xiàn)字符串的其他基本操作的方法。

2.熟練掌握字符串串的定長順序存儲結(jié)構(gòu)上實現(xiàn)字符串的各種操作的方法。

3.理解字符串的堆分配存儲表示以及在其上實現(xiàn)字符串操作的基本方法。

4.熟練掌握串的基本操作類型的實現(xiàn)方法，其中文本模式匹配方法是一個難點，在掌握了BF算法的基礎(chǔ)上理解改進的KMP算法。

5.了解一般文字處理軟件的設(shè)計方法。第一節(jié)

知識準(zhǔn)備

一、有關(guān)串幾個重要概念

1.串（字符串）：零個或多個字符組成的有限序列。一般記作s="a1a2

…an"(n≥0)

2.長度：串中字符的數(shù)目

3.空串：零個字符的串，其長度為零

4.子串和主串：串中任意個連續(xù)的字符組成的子序列稱為該串的子串；包含子串的串相應(yīng)地稱為主串，字符在序列中的序號為該字符在串中的位置。

5.當(dāng)兩個串的長度相等，并且各個對應(yīng)位置的字符都相等時稱為兩串相等。

6.空格串：由一個或多個空格組成的串‘’，同空串是完全不同的。數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用全文共20頁，當(dāng)前為第1頁。二、串的抽象數(shù)據(jù)類型定義

ADT

String{

數(shù)據(jù)對象：D={

|

∈CharacterSet,

i=1,2,...,n,

n>=0}

數(shù)據(jù)關(guān)系：R1={<

,

>|

,

∈D,

i=2,...,n}

基本操作：

Assign(&s,t)將串t的值賦給串

s

Create(&s,ss)將串s的值設(shè)定為字符序列ss

Equal(s,t)判定串s和串t是否相等

Length(s)

求串s的長度

Concat(&s,t)

將串s和串t連接成一個串，結(jié)果存于s中

Substr(&sub,s,start,len)

從s的第start個字符起，取長為len的子串存于sub

Index(s,t)

求子串t在主串s中第一次出現(xiàn)的位置

Replace(&s,t,v)以串v替換串s中的所有的非空子串t

Insert(&s,pos,t)在串s的第pos個字符之前插入串t；

Delete(&s,pos,len)從串s中刪去從第pos個字符起長度為len的子串；

}

ADT

String

三、串的存儲結(jié)構(gòu)

1.定長順序存儲表示

用一組地址連續(xù)的存儲單元來存放字符序列，并約定該結(jié)構(gòu)能存放字符的個數(shù)。

#define

MAXLEN

字符最大個數(shù)

typedef

struct

{int

len;

char

ch[MAXLEN];

}

SString;

2.堆分配存儲表示

系統(tǒng)先分配一個容量很大的地址連續(xù)的存儲空間作為字符串的存放空間，每建立一個新串，系統(tǒng)從該空間中分配一個大小和串長相同的空間來存放新串。

typedef

Struct

{

char

*ch

;

//存儲空間基址

int

length;

//串的長度

}Hstring;

3.串的塊鏈存儲表示

用鏈表形式來存儲串，如果以串中每一個字符作為一個結(jié)點，使得相應(yīng)的存儲占用量增大，因此可采用將多個字符作為一個結(jié)點的形式來形成鏈表(即塊鏈形式)

#define

MAX

80

//用戶定義塊的大小

typedef

struct

str

{char

ch[MAX];

struct

str

*next;

數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用全文共20頁，當(dāng)前為第2頁。

}Chunk;

typedef

struct

string

{

Chunk

*head,*tail;

int

length;

}LString

在串的處理操作中，我們可視不同的情況進行選擇使用不同的定義形式，當(dāng)對字符串進行連接，刪除等操作時，采用鏈結(jié)構(gòu)更為方便上些，但采用鏈結(jié)構(gòu)在進行串的截取(求子串)等操作時則比采用數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用全文共20頁，當(dāng)前為第1頁。數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用全文共20頁，當(dāng)前為第2頁。數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用全文共20頁，當(dāng)前為第3頁。第二節(jié)

串的基本操作示例

【問題描述】用C語言實現(xiàn)串的一些基本操作算法。

【數(shù)據(jù)描述】

采用靜態(tài)存儲結(jié)構(gòu)來表示串，用一維字符數(shù)組來存放字符序列，用整數(shù)len來表示當(dāng)前串實際長度。

#define

STRINGMAX

81

//串最多存放字符的個數(shù)

struct

string

{int

len;

char

ch[STRINGMAX];

};

typedef

struct

string

STRING;

【C源程序】

本程序只設(shè)計了串的創(chuàng)建，聯(lián)接，求子串和刪除操作，其余各基本操作可在本程序基礎(chǔ)上進行改進，補充。

#include

"stdlib.h"

#include

"stdio.h"

#define

STRINGMAX

81

#define

LEN

sizeof(struct

string)/*

串的定義*/

struct

string

{int

len;

char

ch[STRINGMAX];

};

typedef

struct

string

STRING;

void

creat(STRING

*s);

void

print(STRING

*s);

void

concat(STRING

*s,STRING

*t);

STRING

*substr(STRING

*s,int

start,int

len);

void

delete(STRING

*s,int

start,int

len);

main()

{STRING

*s,*t,*v;

/*定義三個采用靜態(tài)存儲形式的串*/

int

start,len;

int

position;

t=(STRING

*)malloc(LEN);

/*為三個串分配相應(yīng)的存儲空間*/

s=(STRING

*)malloc(LEN);

v=(STRING

*)malloc(LEN);

printf("please

input

the

string

s:");

/*創(chuàng)建S串*/

creat(s);

printf("please

input

the

string

t:");

/*創(chuàng)建T串*/

creat(t);

concat(s,t);

/*

連接并輸出相應(yīng)的串*/

printf("the

new

string

s

:");

print(s);

printf("plese

input

the

start

position:");/*輸入截取子串的起始位置*/

scanf("%d",&start);

printf("please

input

the

length:");

/*輸入截取子串的長度*/

scanf("%d",&len);

v=substr(s,start,len);

/*截取子串*/

printf(“the

substring

:”);

print(v);

printf("plese

input

the

start

position:");

/*

輸入刪除串的起始位置*/

scanf("%d",&start);

printf("please

input

the

length:");

/*

輸入刪除串的長度*/

數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用全文共20頁，當(dāng)前為第4頁。

scanf("%d",&len);

delete(s,start,len);

/*刪除串*/

printf("the

deleted

string

s

:");

print(s);

}

void

delete(STRING

*s,int

start,int

len)

{

int

i;

if

(start<=s->len&&len>=0&&start+len<=s->len)/*刪除操作合法性驗證*/

{for(i=start+len;i<=s->len;i++)

/*從start位置開始移動元素*/

s->ch[i-len]=s->ch[i];

s->len=s->len-len;

/*置新的長度*/

}

else

printf("cannot

delete!\n");

}

STRING

*substr(STRING

*s,int

start,int

len)

{int

i;

STRING

*t;

t=(STRING

*)malloc(LEN);

if

(start<0&&start>=s->len)

/*取子串的合法性驗證*/

return(NULL);

else

if

(len>=1&&len<=s->len-start)

{

for(i=0;i<len;i++)

/*取字符序列入到子串的字符數(shù)組中*/

t->ch[i]=s->ch[start+i];

t->len=len;

/*置子串長度*/

t->ch[i]='\0';

return(t);

}

數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用全文共20頁，當(dāng)前為第5頁。

else

return(NULL);

}

void

concat(STRING

*s,STRING

*t)

{

int

i,j;

if

(s->len+t->len>(STRINGMAX-1))

/*連接操作合法性驗證*/

printf("too

long!cannot

concat!!");

else

{j=s->len;

for

(i=0;i<t->len;i++)

s->ch[i+j]=t->ch[i];

/*將串t中字符序列放入串s的尾部*/

s->ch[i+j]=

'\0

';

s->len=s->len+t->len;

/*置新串s的長度*/

}

}

void

creat(STRING

*s)

{char

c;

int

i;

for

(i=0;((c=getchar())!='\n

'&&i<80);i++)

s->ch[i]=c;

/*將輸入的字符序列放入串的字符數(shù)組中*/

s->len=i;

/*置串的長度*/

s->ch[i]=

'\0

';

}

void

print(STRING

s)

/*輸出串的字符序列*/

{int

i;

for

(i=0;s->ch[i]!=

'\0

';i++)

printf("%c",s->ch[i]);

printf("\n");

}

數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用全文共20頁，當(dāng)前為第6頁。數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用全文共20頁，當(dāng)前為第3頁。數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用全文共20頁，當(dāng)前為第4頁。數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用全文共20頁，當(dāng)前為第5頁。數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用全文共20頁，當(dāng)前為第6頁。數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用全文共20頁，當(dāng)前為第7頁。第三節(jié)字符串操作演示系統(tǒng)

【問題描述】

用戶自己實現(xiàn)串類型，并寫一個串的基本操作的演示系統(tǒng)。在該演示系統(tǒng)中能提供命令行的輸入，并能對輸入的命令行進行簡單的編譯并作相應(yīng)的出錯處理，最后根據(jù)命令動詞功能來執(zhí)行命令行。命令定義如下：

1.賦值：assign

串名1

串名2

例如輸入命令

assign

ss

tt

操作的結(jié)果是將串tt賦值給了ss串

2.新建：creat

串名

字符串常量

例如輸入命令

creat

ss

'abcdefg

'

操作的結(jié)果是將字符串常量賦值給串ss，注意：字符串常量兩邊用單引號括起來，不能省略。

3.判等：

equal

串名1

串名2

例如輸入命令

equal

ss

tt

操作的結(jié)果是根據(jù)兩串比較的結(jié)果輸出相應(yīng)的信息

4.求串長：length

串名

操作的結(jié)果是返回字符串長度

5.字符串連接：

concat

串名1

串名2

新串名

例如輸入命令

concat

ss

tt

v

操作的結(jié)果是將串ss和串tt連接起來(ss在前，tt在后)形成一個新串，并輸出新串

6.求子串：

substr

串名

起始位置

子串長度

新子串名

例如輸入命令

substr

ss

1

3

t

操作的結(jié)果是將串ss從起始位置1開始的3

個字符存入到串t中

7.子串定位：

index

串名1

串名2

起始位置

例如輸入命令

index

ss

t

1

操作的結(jié)果是返回串t在串ss從第1個字符后的字符序列中第一次出現(xiàn)的位置

8.退出：

quit

功能：結(jié)束演示系統(tǒng)運行

【數(shù)據(jù)描述】

1.定義串的數(shù)據(jù)類型為指向字符的指針

typedef

char

*STRING;/*定義新的字符串類型，即指向字符的指針*/

2.在本程序中支持串名操作，因此需將各字符串所對應(yīng)的串名和首地址都存放在一個串頭表中

struct

strheadlist

{STRING

strhead[100];

/*字符串首地址*/

STRING

strname[100];

/*字符串的串名*/

int

curnum;

/*當(dāng)前串頭表中串的數(shù)目*/

}

3.對于提示符下輸入的每一行命令，在進行分析以后，需要保留分析的結(jié)果(參數(shù)最多有6個)

數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用全文共20頁，當(dāng)前為第8頁。

struct

result

{int

num;

/*命令行中參數(shù)的個數(shù)(含命令動詞)*/

int

nametype[6];

/*命令行中各參數(shù)的類型*/

STRING

str[6];

/*命令行中各參數(shù)都以字符串的形式返回*/

}

注：參數(shù)類型以整型表示，如為1，則表示參數(shù)為命令動詞；

如為2，則表示參數(shù)為字符串

如為3，則表示參數(shù)為整數(shù)

如為4，則表示參數(shù)為串名

可以仿照DOS操作系統(tǒng)來進行設(shè)計，提供命令行提示符，并能輸入相應(yīng)命令，并將命令行拆分為不同的幾個部分（類似統(tǒng)計單詞個數(shù)），再根據(jù)編譯的結(jié)果進行相應(yīng)的處理。

【C源程序】

#include

"stdlib.h"

#include

"stdio.h"

typedef

char

*STRING;

/*定義新的字符串類型，即指向字符的指針*/

struct

strheadlist

{STRING

strhead[100];

STRING

strname[100];

int

curnum;

};

/*定義指向字符串的字針數(shù)組，并存放各字符串的串名（串名也用字符串來表示），及當(dāng)前堆中串的數(shù)目*/

struct

result

{int

num;

int

nametype[6];

STRING

str[6];

};

/*定義命令行編譯以后形成的命令及參數(shù)等數(shù)據(jù)*/

int

strtoint(STRING

s);

void

creat(STRING

s,STRING

ss);

void

assign(STRING

s,STRING

t);

數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用全文共20頁，當(dāng)前為第9頁。

int

equal(STRING

s,STRING

t);

int

length(STRING

s);

void

concat(STRING

s,STRING

t,STRING

v);

void

substr(STRING

s,int

start,int

len,STRING

v);

int

index(STRING

s,STRING

t,int

start);

struct

result

cmdsyna(int

row);

int

lookup(STRING

s);

struct

strheadlist

head;

char

cmd[40][80];

main()

{

struct

result

comm;

int

row=0,i;

char

c;

int

equ;

head.curnum=0;

while(1)

/*重復(fù)輸入并處理相應(yīng)命令*/

{

printf("CMD>");

for

(i=0;(c=getchar())!='\n

';i++)

cmd[row][i]=c;

cmd[row][i]=

'\0

';

comm=cmdsyna(row);/*對各命令動詞進行判數(shù)并作參數(shù)分析*/

if

(strcmp(comm.str[0],"creat")==0)/*字符串創(chuàng)建*/

{if

(comm.num!=2)

printf("Parameters

is

wrong!\n");

else

if

(lookup(comm.str[1])!=-1)

printf("String

%s

cannot

be

creat!\n");

else

{if

(type[1]==4

&&

type[2]==2)

creat(comm.str[1],comm.str[2]);

}

}

else

if

(strcmp(comm.str[0],"assign")==0)/*字符串賦值*/

數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用全文共20頁，當(dāng)前為第10頁。

{if

(comm.num!=2)

printf("Parameters

is

wrong!\n");

else

assign(comm.str[1],comm.str[2]);

}

else

if

(strcmp(comm.str[0],"equal")==0)/*字符串判等*/

{if

(comm.num!=2)

printf("Parameters

is

wrong!\n");

else

{if

(lookup(comm.str[1])==-1||lookup(comm.str[2])==-1)

printf("String

%s

or

%s

is

not

found!\n",comm.str[1],comm.

str[2]);

else

{if

(equal(head.strhead[lookup(comm.str[1])],

head.strhead[lookup(comm.str[2])])==1)

printf("Equal!!!\n");

else

printf("Not

equal!!!\n");

}

}

}

else

if

(strcmp(comm.str[0],"length")==0)/*字符串求長*/

{if

(comm.num!=1)

printf("Parameters

is

wrong!\n");

else

{if

(lookup(comm.str[1])==-1)

printf("The

string

%s

connot

be

found!\n");

else

printf("String

%s

:%s

length

is

%d\n",comm.str[1],

head.strhead

[lookup(comm.str[1])],length(head.strhead[lookup(comm.str[1])]));

}

}

else

if

(strcmp(comm.str[0],"concat")==0)/*字符串連接并形成新的字符串*/

{if

(comm.num!=3)

printf("Parameters

is

wrong!\n");

else

{

if

(lookup(comm.str[1])==-1||lookup(comm.str[2])==-1)

printf("The

string

%s

or

%s

is

not

found!\n",

comm.str[1],comm.str[2]);

數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用全文共20頁，當(dāng)前為第11頁。

else

if

(lookup(comm.str[3])!=-1)

printf("String

%s

connot

be

creat!\n",

comm.str[3]);

else

concat(head.strhead[lookup(comm.str[1])],

head.strhead[lookup(comm.str[2])],comm.str[3]);

}

}

else

if

(strcmp(comm.str[0],"substr")==0)/*取字符串子串，并形成新的字符串*/

{if

(comm.num!=4)

printf("Parameters

wrong!\n");

else

{if

(lookup(comm.str[1])==-1)

printf("String

%s

is

not

found!\n",comm.str[1]);

else

{if

(lookup(comm.str[4])!=-1)

printf("String

%s

connot

be

creat!\n",comm.str[4]);

else

{int

start,len;

start=strtoint(comm.str[2]);

len=strtoint(comm.str[3]);

substr(head.strhead[lookup(comm.str[1])],start,

len,comm.str[4]);

}

}

}

}

else

if

(strcmp(comm.str[0],"index")==0)/*字符串定位*/

{if

(comm.num!=3)

printf("Parameters

wrong!\n");

else

{if

(lookup(comm.str[1])==-1||lookup(comm.str[2])==-1)

數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用全文共20頁，當(dāng)前為第12頁。printf("String

%s

or

%s

is

not

found!\n",

comm.str[1],comm.str[2]);

else

{int

start,flag=-1;

start=strtoint(comm.str[3]);

flag=index(head.strhead[lookup(comm.str[1])],head.strhead[lookup(comm.str[2])],start);

if

(flag==-1)

printf("String

%s

start

%d

,

String

%s

is

not

index!!!\n",comm.str[1],start,comm.str[2]);

else

printf("String

%s

start

%d

,String

%s

is

index

%d!!!\n",

comm.str[1],start,comm.str[2],flag);

}

}

}

else

if

(strcmp(comm.str[0],"quit")==0)/*退出演示系統(tǒng)*/

{printf("Bye

Bye!\n");

break;

}

else

printf("Bad

filename

or

no

command!\n");/*錯誤命令動詞提示*/

row++;

}

}

int

strtoint(STRING

s)/*將字符串轉(zhuǎn)換成整數(shù)常量*/

{

int

i=0;

int

total=0;

while(s[i]!=

'\0

')

{total=total*10+s[i]-48;

i++;

數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用全文共20頁，當(dāng)前為第13頁。

}

return(total);

}

int

lookup(STRING

s)

/*查找串表中是否存在串名所對應(yīng)的字符串，如存在則返回所對應(yīng)的位置，否則返回-1*/

{int

i;

int

look=-1;

for

(i=0;i<head.curnum;i++)

if

(strcmp(head.strname[i],s)==0)

{look=i;

break;

}

if

(look==head.curnum)

look=-1;

return(look);

}

struct

result

cmdsyna(int

row)

/*對輸入的命令行進行編譯*/

{int

i;

struct

result

res;

char

c;

int

word=0,start;

res.num=-1;

for(i=0;(c=cmd[row][i])!=

'\0

';i++)

{

if(c==

'

')

{word=0;

cmd[row][i]=

'\0

';

}

else

if

(word==0)

/*出現(xiàn)了一個新的參數(shù)，將分離出的各參數(shù)以及命令動詞放置于參數(shù)表中*/

{res.num++;

數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用全文共20頁，當(dāng)前為第14頁。

start=i;word=1;

res.str[res.num]=&cmd[row][start];

if

(res.num==0)

type[res.num]=1;

else

if

(cmd[row][start]==39)

{cmd[row][start]=

'\0

';

res.str[res.num]=&cmd[row][start+1];

type[res.num]=2;

}

else

{if

(cmd[row][start]>=

'0

'&&cmd[row][start]<=

'9

')

type[res.num]=3;

else

type[res.num]=4;

}

}

else

{if

(type[res.num]==2

&&

c==39)

cmd[row][i]=

'\0

';

/*處理參數(shù)中字符串常量*/

if

(type[res.num]==3

&&(c<'0'||c>'9'))

cmd[row][i]=

'\0';

/*處理參數(shù)中整數(shù)常量*/

}

}

return(res);

}

int

index(STRING

s,STRING

t,int

start)

/*從串S起始置START開始查找串T，如找到，則返回第一次出現(xiàn)的位置，否則返回-1*/

{

int

i,j;

if

((start<0)||(start+length(t)>length(s))||(length(t)==0))

數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用全文共20頁，當(dāng)前為第15頁。

return(-1);

else

{i=start;

j=0;

while

(i<length(s)&&j<length(t))

{

if

(s[i]==t[j])

{i++;j++;}

else

{i=i-j+1;j=0;}

}

}

if

(j==length(t))

return(i-length(t));

else

return(-1);

}

void

substr(STRING

s,int

start,int

len,STRING

v)

/*為新串開辟新的空間，并將從串S中START起始位置起取LEN長度的子串存放起來，把新串的串名和首地址存放于串表中*/

{int

i;

char

ch[80];

if

(start<0&&start>=length(s))

printf("Cannot

be

substr!!!\n");

else

{if

(len>=1&&len<=length(s)-start)

{

head.strname[head.curnum]=v;

head.strhead[head.curnum]=ch;

for(i=0;i<len;i++)

ch[i]=s[start+i];

數(shù)據(jù)結(jié)構(gòu)實驗四字符串的應(yīng)用全文共20頁，當(dāng)前為第16頁。

ch[i]=

'\0';

head.curnum++;

printf(