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