首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
数据结构实验书


Concat(&s,t) Substr(&sub,s,start,len) Index(s,t)

将串 s 和串 t 连接成一个串,结果存于 s 中 从 s 的第 start 个字符起,取长为 len 的子串存于 sub 求子串 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 } 2. 堆分配存储表示 系统先分配一个容量很大的地址连续的存储空间作为字符串的存放空间,每建立一个新串,系统从该空间 中分配一个大小和串长相同的空间来存放新串。 typedef { char *ch ; Struct ch[MAXLEN]; 字符最大个数

SString;

//存储空间基址 //串的长度 }Hstring;

int length;

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

typedef struct

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

第二节 串的基本操作示例
【问题描述】用 C 语言实现串的一些基本操作算法。 【数据描述】 采用静态存储结构来表示串,用一维字符数组来存放字符序列,用整数 len 来表示当前串实际长度。 #define STRINGMAX 81 //串最多存放字符的个数

struct string {int char }; typedef 【C 源程序】 本程序只设计了串的创建,联接,求子串和删除操作,其余各基本操作可在本程序基础上进行改进, 补充。 #include #include "stdlib.h" "stdio.h" 81 string)/* 串的定义*/ struct string STRING; len; ch[STRINGMAX];

#define STRINGMAX #define LEN struct {int char }; string len;

sizeof(struct

ch[STRINGMAX];

typedef struct string STRING; void void void STRING void main() {STRING *s,*t,*v; int start,len; int position; t=(STRING *)malloc(LEN); s=(STRING *)malloc(LEN); v=(STRING *)malloc(LEN); printf("please creat(s); printf("please creat(t); concat(s,t); printf("the new print(s); printf("plese input the start position:");/*输入截取子串的起始位置*/ string s /* :"); 连接并输出相应的串*/ input the string t:"); /*创建 T 串*/ input the string s:"); /*创建 S 串*/ /*为三个串分配相应的存储空间*/ /*定义三个采用静态存储形式的串*/ creat(STRING print(STRING concat(STRING *s); *s); *s,STRING *t); *s,int start,int len);

*substr(STRING delete(STRING

*s,int

start,int len);

scanf("%d",&start); printf("please input the length:"); /*输入截取子串的长度*/

scanf("%d",&len); v=substr(s,start,len); printf(“the print(v); printf("plese input the start position:"); /* 输入删除串的起始位置*/ substring :”); /*截取子串*/

scanf("%d",&start); printf("please input the length:"); /* 输入删除串的长度*/

scanf("%d",&len); delete(s,start,len); printf("the deleted print(s); } void { int i; if (start<=s->len&&len>=0&&start+len<=s->len)/*删除操作合法性验证*/ {for(i=start+len;i<=s->len;i++) s->ch[i-len]=s->ch[i]; s->len=s->len-len; } else printf("cannot } STRING {int i; *t; *substr(STRING *s,int start,int len) delete!n"); /*置新的长度*/ /*从 start 位置开始移动元素*/ delete(STRING *s,int start,int len) /*删除串*/ string s :");

STRING

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++) t->ch[i]=s->ch[start+i]; t->len=len; t->ch[i]='\0'; return(t); } /*置子串长度*/ /*取字符序列入到子串的字符数组中*/ /*取子串的合法性验证*/

else return(NULL); } void { int i,j; if (s->len+t->len>(STRINGMAX-1)) printf("too else {j=s->len; for (i=0;i<t->len;i++) s->ch[i+j]=t->ch[i]; s->ch[i+j]= '\0 '; /*置新串 s 的长度*/ /*将串 t 中字符序列放入串 s 的尾部*/ /*连接操作合法性验证*/ concat(STRING *s,STRING *t)

long!cannot concat!!");

s->len=s->len+t->len; } } void creat(STRING *s)

{char c; int i; for (i=0;((c=getchar())!='n s->ch[i]=c; s->len=i; s->ch[i]= '\0 } void {int print(STRING i; '\0 ';i++) s) /*输出串的字符序列*/ '; '&&i<80);i++) /*将输入的字符序列放入串的字符数组中*/ /*置串的长度*/

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

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

【测试数据】 please input the please input the the new string string s:abcd↙ t:efg↙

string s:abcdefg↙ start position:3↙ length:3↙

plese input the please input the

the substring:def↙ plese input the please input the start position:3↙ length:3↙ :abcg↙

the deleted string s 【分析说明】

1. 上述程序采用的是串的静态存储形式,在定义串时对串可能容纳的字符个数要正确估计,否则会造成存 储空间的大量浪费; 2. 在进行串的连接操作时,还必须考虑连接后形成的新串长度是否会大于串定义的最大长度;采用链式存 储形式可以解决上述问题。 3. 如果采用链式存储形式,在某些操作实现中时间效率将会降低,如在删除操作中需首先找到删除的第一 个字符,这样就需先移动指针找到删除点才能进行,而静态形式可直接从下标为起始点的字符起即可进行 操作,因此,在设计不同的串处理应用程序时应根据可能进行的操作而选择相应比较合适的数据存储形式。 【实验题】 1. 根据以上程序采用的静态存储形式,完成串的置换、串的定位、串的插入操作的实现。 2. 选择一种链式存储形式,完成串的基本操作。

123456789101112131415161718192021222324252627282930

 


 

  【Top

最新搜索

 


 

热点推荐