2串的链接存储及其部分运算的实现 串的链接存储采用单链表的形式实现,其中每个结 点的定义如下 typedef struct node char data. struct node *next 3 linkstrnode, typedef linkstrnode *linkstring 例如,串S=“ abcde”,其链接存储结构如下图所示 b C d e∧
2 串的链接存储及其部分运算的实现 串的链接存储采用单链表的形式实现，其中每个结 点的定义如下： typedef struct node { char data; struct node *next; } linkstrnode; typedef linkstrnode *linkstring; 例如，串S=“abcde”，其链接存储结构如下图所示： a b c d e ∧ S
(1)创建字符串运算 istrcreate(S) void strcreate(inkstring *S char ch; linkstrnode *p,*r: *SENULL, =NULL. while((ch=getchar)='\n) [p=(inkstrnode *)malloc(sizeof(inkstrnode) p->data=ch if (S==NULL)*S=p else r->next=p: r=p;/r移向当前链接串的最后一个字符的位置/ if(r!=NULL)r->next=NULL/处理表尾结点指针域*/
（1）创建字符串运算strcreate (S) void strcreate (linkstring *S) { char ch; linkstrnode *p,*r; *S=NULL; r=NULL; while ((ch=getchar())!=‘\n’) { p=(linkstrnode *)malloc(sizeof(linkstrnode)); p->data=ch; if (*S==NULL) *S=p; else r->next=p; r=p; /*r移向当前链接串的最后一个字符的位置*/ } if (r!=NULL) r->next=NULL; /*处理表尾结点指针域*/ }
(2)插入运算 trinsert(s,i,T) void strinsert(linkstring *S, int i, lin kstring T i int k linkstring p, q3 p 2S.k=1 while(p & ki-1) ip=p->next k++;) if(p) printf(error\n); else &a=t while(q->next)q=q->next; g->next=p->next; p->next=T;
（2）插入运算strinsert(S,i,T) void strinsert(linkstring *S,int i,linkstring T) { int k ; linkstring p,q; p=*S, k=1; while (p && k<i-1) { p=p->next ; k++; } if (!p) printf("error\n"); else { q=T; while(q->next) q=q->next; q->next=p->next; p->next=T; } }
(3)删除运算 strdelete( s|en) void strdelete(linkstring*S, int i, int len) i int k: linkstring p, q r: =*S, q=null; k=1; 八用p查找S的第个元素,q始终跟踪p的前驱* while (p &&k<i) (q=p; p=p->next: k++i] if (p) printf("errol\n" ); else k=1; /p从第个元素开始查找长度为en子串的最后元素* while(k<len &&p) p=p->next水k++;} if(p) printf("error 2\n");
（3）删除运算strdelete(S,i,len) void strdelete(linkstring*S,int i,int len) { int k ; linkstring p,q,r; p=*S, q=null; k=1; /*用p查找S的第i个元素，q始终跟踪p的前驱*/ while (p && k<i) {q=p; p=p->next ; k++;} if (!p) printf("error1\n"); else { k=1; /*p从第i个元素开始查找长度为len子串的最后元素*/ while(k<len && p ) { p=p->next ;k++;} if(!p) printf("error2\n");
else i if (la[ r=*S; *S=p->next; 1 /被删除的子串位于s的最前面* else /*被删除的子串位于S的中间或最后* r=g->next, g->next= p->next, p->next=null. while(r!=null) (p=r; r=r->next; free(p),]
else { if (!q) { r=*S; *S=p->next; } /*被删除的子串位于S的最前面*/ else { /*被删除的子串位于Ｓ的中间或最后*/ r=q->next; q->next= p->next; } p->next=null; while (r !=null) {p=r; r=r->next; free(p);} } } }