串的存储结构有两种：顺序存储结构和链式存储结构
串的存储方式有两种：紧缩格式和非紧缩格式
由于串的函数方法较多，我直接学习教材上写的函数，自己不写了
串的存储方式
顺序存储结构
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
//顺序串基本运算的算法 #include <stdio.h> #define MaxSize 100 typedef struct { char data[MaxSize]; int length; //串长 } SqString; void StrAssign(SqString &s,char cstr[]) //字符串常量赋给串s { int i; for (i=0;cstr[i]!='\0';i++) s.data[i]=cstr[i]; s.length=i; } void DestroyStr(SqString &s) { } void StrCopy(SqString &s,SqString t) //串复制 { int i; for (i=0;i<t.length;i++) s.data[i]=t.data[i]; s.length=t.length; } bool StrEqual(SqString s,SqString t) //判串相等 { bool same=true; int i; if (s.length!=t.length) //长度不相等时返回0 same=false; else for (i=0;i<s.length;i++) if (s.data[i]!=t.data[i]) //有一个对应字符不相同时返回0 { same=false; break; } return same; } int StrLength(SqString s) //求串长 { return s.length; } SqString Concat(SqString s,SqString t) //串连接 { SqString str; int i; str.length=s.length+t.length; for (i=0;i<s.length;i++) //将s.data[0..s.length-1]复制到str str.data[i]=s.data[i]; for (i=0;i<t.length;i++) //将t.data[0..t.length-1]复制到str str.data[s.length+i]=t.data[i]; return str; } SqString SubStr(SqString s,int i,int j) //求子串 { SqString str; int k; str.length=0; if (i<=0 || i>s.length || j<0 || i+j-1>s.length) return str; //参数不正确时返回空串 for (k=i-1;k<i+j-1;k++) //将s.data[i..i+j]复制到str str.data[k-i+1]=s.data[k]; str.length=j; return str; } SqString InsStr(SqString s1,int i,SqString s2) //插入串 { int j; SqString str; str.length=0; if (i<=0 || i>s1.length+1) //参数不正确时返回空串 return str; for (j=0;j<i-1;j++) //将s1.data[0..i-2]复制到str str.data[j]=s1.data[j]; for (j=0;j<s2.length;j++) //将s2.data[0..s2.length-1]复制到str str.data[i+j-1]=s2.data[j]; for (j=i-1;j<s1.length;j++) //将s1.data[i-1..s1.length-1]复制到str str.data[s2.length+j]=s1.data[j]; str.length=s1.length+s2.length; return str; } SqString DelStr(SqString s,int i,int j) //串删去 { int k; SqString str; str.length=0; if (i<=0 || i>s.length || i+j>s.length+1) //参数不正确时返回空串 return str; for (k=0;k<i-1;k++) //将s.data[0..i-2]复制到str str.data[k]=s.data[k]; for (k=i+j-1;k<s.length;k++) //将s.data[i+j-1..s.length-1]复制到str str.data[k-j]=s.data[k]; str.length=s.length-j; return str; } SqString RepStr(SqString s,int i,int j,SqString t) //子串替换 { int k; SqString str; str.length=0; if (i<=0 || i>s.length || i+j-1>s.length) //参数不正确时返回空串 return str; for (k=0;k<i-1;k++) //将s.data[0..i-2]复制到str str.data[k]=s.data[k]; for (k=0;k<t.length;k++) //将t.data[0..t.length-1]复制到str str.data[i+k-1]=t.data[k]; for (k=i+j-1;k<s.length;k++) //将s.data[i+j-1..s.length-1]复制到str str.data[t.length+k-j]=s.data[k]; str.length=s.length-j+t.length; return str; } void DispStr(SqString s) //输出串s { int i; if (s.length>0) { for (i=0;i<s.length;i++) printf("%c",s.data[i]); printf("\n"); } } |
串链式存储结构
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 |
//链串基本运算的算法 #include <stdio.h> #include <malloc.h> typedef struct snode { char data; struct snode *next; } LinkStrNode; void StrAssign(LinkStrNode *&s,char cstr[]) //字符串常量cstr赋给串s { int i; LinkStrNode *r,*p; s=(LinkStrNode *)malloc(sizeof(LinkStrNode)); r=s; //r始终指向尾结点 for (i=0;cstr[i]!='\0';i++) { p=(LinkStrNode *)malloc(sizeof(LinkStrNode)); p->data=cstr[i]; r->next=p;r=p; } r->next=NULL; } void DestroyStr(LinkStrNode *&s) { LinkStrNode *pre=s,*p=s->next; //pre指向结点p的前驱结点 while (p!=NULL) //扫描链串s { free(pre); //释放pre结点 pre=p; //pre、p同步后移一个结点 p=pre->next; } free(pre); //循环结束时,p为NULL,pre指向尾结点,释放它 } void StrCopy(LinkStrNode *&s,LinkStrNode *t) //串t复制给串s { LinkStrNode *p=t->next,*q,*r; s=(LinkStrNode *)malloc(sizeof(LinkStrNode)); r=s; //r始终指向尾结点 while (p!=NULL) //将t的所有结点复制到s { q=(LinkStrNode *)malloc(sizeof(LinkStrNode)); q->data=p->data; r->next=q;r=q; p=p->next; } r->next=NULL; } bool StrEqual(LinkStrNode *s,LinkStrNode *t) //判串相等 { LinkStrNode *p=s->next,*q=t->next; while (p!=NULL && q!=NULL && p->data==q->data) { p=p->next; q=q->next; } if (p==NULL && q==NULL) return true; else return false; } int StrLength(LinkStrNode *s) //求串长 { int i=0; LinkStrNode *p=s->next; while (p!=NULL) { i++; p=p->next; } return i; } LinkStrNode *Concat(LinkStrNode *s,LinkStrNode *t) //串连接 { LinkStrNode *str,*p=s->next,*q,*r; str=(LinkStrNode *)malloc(sizeof(LinkStrNode)); r=str; while (p!=NULL) //将s的所有结点复制到str { q=(LinkStrNode *)malloc(sizeof(LinkStrNode)); q->data=p->data; r->next=q;r=q; p=p->next; } p=t->next; while (p!=NULL) //将t的所有结点复制到str { q=(LinkStrNode *)malloc(sizeof(LinkStrNode)); q->data=p->data; r->next=q;r=q; p=p->next; } r->next=NULL; return str; } LinkStrNode *SubStr(LinkStrNode *s,int i,int j) //求子串 { int k; LinkStrNode *str,*p=s->next,*q,*r; str=(LinkStrNode *)malloc(sizeof(LinkStrNode)); str->next=NULL; r=str; //r指向新建链表的尾结点 if (i<=0 || i>StrLength(s) || j<0 || i+j-1>StrLength(s)) return str; //参数不正确时返回空串 for (k=0;k<i-1;k++) p=p->next; for (k=1;k<=j;k++) //将s的第i个结点开始的j个结点复制到str { q=(LinkStrNode *)malloc(sizeof(LinkStrNode)); q->data=p->data; r->next=q;r=q; p=p->next; } r->next=NULL; return str; } LinkStrNode *InsStr(LinkStrNode *s,int i,LinkStrNode *t) //串插入 { int k; LinkStrNode *str,*p=s->next,*p1=t->next,*q,*r; str=(LinkStrNode *)malloc(sizeof(LinkStrNode)); str->next=NULL; r=str; //r指向新建链表的尾结点 if (i<=0 || i>StrLength(s)+1) //参数不正确时返回空串 return str; for (k=1;k<i;k++) //将s的前i个结点复制到str { q=(LinkStrNode *)malloc(sizeof(LinkStrNode)); q->data=p->data; r->next=q;r=q; p=p->next; } while (p1!=NULL) //将t的所有结点复制到str { q=(LinkStrNode *)malloc(sizeof(LinkStrNode)); q->data=p1->data; r->next=q;r=q; p1=p1->next; } while (p!=NULL) //将结点p及其后的结点复制到str { q=(LinkStrNode *)malloc(sizeof(LinkStrNode)); q->data=p->data; r->next=q;r=q; p=p->next; } r->next=NULL; return str; } LinkStrNode *DelStr(LinkStrNode *s,int i,int j) //串删去 { int k; LinkStrNode *str,*p=s->next,*q,*r; str=(LinkStrNode *)malloc(sizeof(LinkStrNode)); str->next=NULL; r=str; //r指向新建链表的尾结点 if (i<=0 || i>StrLength(s) || j<0 || i+j-1>StrLength(s)) return str; //参数不正确时返回空串 for (k=0;k<i-1;k++) //将s的前i-1个结点复制到str { q=(LinkStrNode *)malloc(sizeof(LinkStrNode)); q->data=p->data; r->next=q;r=q; p=p->next; } for (k=0;k<j;k++) //让p沿next跳j个结点 p=p->next; while (p!=NULL) //将结点p及其后的结点复制到str { q=(LinkStrNode *)malloc(sizeof(LinkStrNode)); q->data=p->data; r->next=q;r=q; p=p->next; } r->next=NULL; return str; } LinkStrNode *RepStr(LinkStrNode *s,int i,int j,LinkStrNode *t) //串替换 { int k; LinkStrNode *str,*p=s->next,*p1=t->next,*q,*r; str=(LinkStrNode *)malloc(sizeof(LinkStrNode)); str->next=NULL; r=str; //r指向新建链表的尾结点 if (i<=0 || i>StrLength(s) || j<0 || i+j-1>StrLength(s)) return str; //参数不正确时返回空串 for (k=0;k<i-1;k++) //将s的前i-1个结点复制到str { q=(LinkStrNode *)malloc(sizeof(LinkStrNode)); q->data=p->data;q->next=NULL; r->next=q;r=q; p=p->next; } for (k=0;k<j;k++) //让p沿next跳j个结点 p=p->next; while (p1!=NULL) //将t的所有结点复制到str { q=(LinkStrNode *)malloc(sizeof(LinkStrNode)); q->data=p1->data;q->next=NULL; r->next=q;r=q; p1=p1->next; } while (p!=NULL) //将结点p及其后的结点复制到str { q=(LinkStrNode *)malloc(sizeof(LinkStrNode)); q->data=p->data;q->next=NULL; r->next=q;r=q; p=p->next; } r->next=NULL; return str; } void DispStr(LinkStrNode *s) //输出串 { LinkStrNode *p=s->next; while (p!=NULL) { printf("%c",p->data); p=p->next; } printf("\n"); } |
