数据结构课程设计-字符串操作

输入是否结束输入标志；｝

(5) 关闭文件。

2）给定单词计数的实现思路是：

(1) 输入要检索的文本文件名，打开相应的文件； (2) 输入要检索统计的单词；

(3) 循环读文本文件，读入一行，将其送入定义好的串中，并求该串的实

际长度，调用串匹配函数进行计数。具体描述如下：

while(不是文件结束){

读入一行并到串中； 求出串长度； 模式匹配函数计数；｝

(4) 关闭文件，输出统计结果。

3）检索单词出现在文本文件中的行号、次数及其位置的实现思路是：

(1) 输入要检索的文本文件名，打开相应的文件； (2) 输入要检索统计的单词； (3) 行计数器置初值0； (4) while(不是文件结束){

读入一行到指定串中； 求出串长度； 行单词计数器0；

调用模式匹配函数匹配单词定位、该行匹配单词计数； 行号计数器加1；

if(行单词计数器!=0)输出行号、该行有匹配单词的个数以及相应的位置；}

五、模块划分

1.串的模式匹配：

穷举法:Index(S, T, pos)

S为主串，T为模式串，从pos位置开始进行 BF算法:IndexBF(SString S,SString T,int pos)

朴素的模式匹配算法，S为主串，T为模式串，从pos位置开始进行。 KMP算法:get_next(SString T, int next[]) 获取字符串T对应的 next[]数组。

IndexKMP(SString S,SString T,int pos,int next[])

利用模式串T的next函数求T在主串S中第pos个字符之后的位置。

2.字符串的加密与解密:

加密：Encrypt(SString S,SString *T) 将字符串S加密后存储在T中

解密：Decrypt(SString S,SString *T) 将字符串S解密后存储到T中

3.文本文件单词的计数和检索：

CreatTextFile() 创建文本文件 SubStrCount()

利用模式匹配，给定单词计数 SubStrInd()

利用模式匹配，检索单词出现在文本文件中的行号、次数及其位置 int match(char a[],int n,char c)

判断字符是否为标点或空格，换行符等，若相符返回1，否则返回0。

六、数据结构

ADT String{

数据对象：D={ai|ai∈CharacterSet,i=1,2,3,??n,n≥0} 数据关系：R1={|a(i-1),ai∈D,i=2,??n} 基本操作：

InitString(&S, a[])

初始条件：a[]是字符型数组。 操作结果：生成一个其值为a[]的串S。 StrLength(S) 初始条件：串S存在 操作结果：返回的元素个数。 StrCompare(S, T) 初始条件： 串S、T存在。

操作结果：若S>T,则返回值大于0；若S

SubString(&sub, S, pos, len)

初始条件：串S存在,0≤pos

初始条件：串S,T存在，0≤pos≤S.length。 操作结果：在串S的第个下标开始插入串T。

StrDelete(&S, pos, len)

初始条件：串S存在, 0≤pos≤S.length-len。

操作结果：从串的第pos个下标开始删除长度为len的子串。 StrContact(&S, T) 初始条件：串S,T存在。

操作结果：用S返回S与T连接而成的新串。 Index(S, T, pos)

初始条件：串S、T存在，0≤pos≤S.length-1。

操作结果：若主串S中存在与串T相同的串则返回从下标pos开始的第一个出现的位置，否则返回-1。 show(S)

初始条件：串S存在。 操作结果：显示串S。 } ADT String

七、源程序（格式调整，添加注释）

#include #include

#define MaxStrSize 256 typedef struct {

char ch[MaxStrSize]; int length;

} SString;//定义顺序串类型 //pos为下标

//实现串的赋值、比较、连接、插入和删除等操作，并在此基础上完成串的模式匹配

void InitString(SString *s,char a[]) {int i,j;

for(j=0;a[j]!='\\0'; j++); for(i=0;ich[i]=a[i];

s->length=strlen(a); }

//串赋值

int StrLength(SString s) {return s.length;} //求串长

int StrCompare(SString s,SString t) { int i;

for (i=0; i

if (s.ch[i]!=t.ch[i]) return s.ch[i]-t.ch[i]; return s.length-t.length; } //串比较

void SubString(SString *sub,SString S,int pos,int len) { int i;

for(i=0;i

sub->ch[i]=S.ch[pos+i]; sub->length=len;} //截取串

void StrInsert(SString *s,SString t,int pos) {int i,m,n; m=s->length; n=t.length;

for(i=m-1;i>=pos-1;i--) s->ch[i+n]=s->ch[i]; for(i=0;i

s->ch[i+pos]=t.ch[i]; s->length=s->length+n; }//插入算法

void StrDelete(SString *s,int pos,int len) {int i;

for(i=pos+len;ilength;i++) s->ch[i-len]=s->ch[i]; s->length=s->length-len; }

//删除算法

void StrContact(SString *s,SString t) {StrInsert(s,t,s->length);} //连接算法

void show(SString S) {int i;

for(i=0;i

//显示串

//-----------------加密与解密--------------------------- void Encrypt(SString S,SString *T) {char c;

int i,h,l,j=0;

for (i=0;i

h=(c>>4)&0xf; //取前四位 l=c&0xf; // 取后四位