首页 > 代码库 > 串的数据结构表——顺序串与链式串
串的数据结构表——顺序串与链式串
串的结构类似与线性表，只不过串的数据元素是一个字符，即是由零个或多个字符组成的有限序列。
一、串的顺序存储
串的顺序存储结构也就是顺序存储，即串中的字符被依次的存在一组连续的存储单元中，可以类比线性表的顺序存储，可以写出其数据结构如下：
typedef struct st{ char *ch; //串存放的起始地址，串中第i个字符存储在ch[i-1]中 int length; //串的长度 int strsize; //分配的存储空间的大小，如果不足，在通过realloc()分配增加空间}string;假设现在的字符串是“friend”，其结构可以用如图所示：
现在我们拿到这个数据结构第一步是要初始化一个串，即首先在内存中开辟一段连续的存储空间（大小可以假先预定MAXSIZE个存储空间），初始化其长度length为0，同时制定其串的最大容量是MAXSZIE，如下：
//串的初始化操作string CreateNullString(){ string s; s.length=0; s.ch=(char*)malloc(MAXSIZE *sizeof(char)); s.strsize=MAXSIZE; return s;}初始化完成之后，我们可以类比顺序表，对串完成一系列操作，如串拷贝、取子串、串赋值等，
程序示例如下：
#include<stdio.h>#include<stdlib.h>#define MAXSIZE 100typedef struct st{ char *ch; //串存放的起始地址，串中第i个字符存储在ch[i-1]中 int length; //串的长度 int strsize; //分配的存储空间的大小，如果不足，在通过realloc()分配增加空间}string;//串的初始化操作string CreateNullString(){ string s; s.length=0; s.ch=(char*)malloc(MAXSIZE *sizeof(char)); s.strsize=MAXSIZE; return s;}//判断空串int isEmpty(string s){ if(s.length==0) return 1; else return 0;}//赋值操作void StringAssign(string *s1,char s2[]){ int i=0; while(s2[i]!=‘\0‘) // ‘\0‘ 是字符串的结束符，任何字符串之后都会自动加上‘\0‘ i++; //计算s2的长度 if(i>s1->strsize) { //所赋值的字符数组超过字符串的默认容量，则增加存储空间 s1->ch=(char*)malloc(i*sizeof(char)); s1->strsize=i; } s1->length=i; for(i=0;i<s1->length;i++) s1->ch[i]=s2[i]; //从第一个字符开始逐个字符赋值}//串拷贝操作void StringCopy(string *s1,string s2){ if(s1->strsize<s2.length) { s1->ch=(char*)realloc(s1->ch,s2.length*sizeof(char)); s1->strsize=s2.length; } s1->length=s2.length; int i; for(i=0;i<s1->length;i++) s1->ch[i]=s2.ch[i];}//求串的长度int StringLength(string s){ return s.length;}//串的连接操作void concat(string *s,string s1,string s2){ if(s->strsize<s1.length+s2.length) { s->ch=(char*)realloc(s->ch,(s1.length+s2.length)*sizeof(char)); s->strsize=s1.length+s2.length; } s->length=s1.length+s2.length; //两串连接 int i; for(i=0;i<s1.length;i++) //将s1复制到s中 s->ch[i]=s1.ch[i]; for(;i<s->length;i++) s->ch[i]=s2.ch[i-s1.length]; //将s2复制到s中去}//取子串操作int substr(string s,int i,int len,string *t){ /* i表示从字符串s的第i个位置开始截取（索引从1开始） len表示截取字符串的长度 */ if(i<=0 || i>s.length || len<0 || len>s.length-i+1) //参数不合法 return 0; if(t->length<len) //存储空间不够，继续分配存储空间 { t->ch=(char*)realloc(t->ch,len*sizeof(char)); t->strsize=len; } t->length=len; int k; for(k=0;k<t->length;k++) t->ch[k]=s.ch[i-1+k]; return 1;}//插入操作int insertString(string *s,int i,string t){ //在字符串s的第i个位置插入字符串t if(i<=0 || i>s->length+1) return 0; if(s->strsize<s->length+t.length) //空间不足 { s->ch=(char*)realloc(s->ch,(s->length+t.length)*sizeof(char)); s->strsize=s->length+t.length; } int k; for(k=s->length-1;k>=i-1;k--) //将s中的后i个字符后移到后面 s->ch[k+t.length]=s->ch[k]; s->length=s->length+t.length; for(k=0;k<t.length;k++) //将t的值赋值给s s->ch[k+i-1]=t.ch[k]; return 1;}//删除操作int deleteString(string *s,int i,int len){ //从s的第i个字符开始删除len个字符 if(i<=0 || i>s->length || len<0 || len>s->length-i+1) //参数不合法 return 0; int k; for(k=i+len-1;k<s->length;k++) //从s的i+len-1个位置开始将其后的所有字符前移 s->ch[k-len]=s->ch[k]; s->length-=len; return 1;}//输出操作void print(string s){ int i; for(i=0;i<s.length;i++) printf("%c",s.ch[i]); printf("\n");}void main(){ string s1=CreateNullString(); string s2=CreateNullString(); string s3=CreateNullString(); char ch[MAXSIZE]; printf("请输入主串：\n"); gets(ch); StringAssign(&s1,ch); printf("主串 s1 为："); print(s1); StringCopy(&s2,s1); printf("拷贝串操作结果如下，结果如下 s2 ："); print(s2); printf("删除操作（1——s1.length-3 全删）："); deleteString(&s2,1,s1.length-3); print(s2); printf("插入操作,插入到s2的第2个位置上，请输入插入的字符串："); gets(ch); StringAssign(&s3,ch); insertString(&s2,2,s3); print(s2); printf("取子串操作（取s1的子串【2-4】)："); substr(s1,2,3,&s3); print(s3); printf("串连接操作【将s1与s3合并】："); concat(&s1,s1,s2); print(s1);} 结果如下：
二、串的链式存储
串的链式存储结构称为串的链式存储，即串中的每一个节点包括两个部分：数据域和指针域，其中数据域用来存放字符，指针域用来存放指向下一个节点的指针。
由此可得串的链式数据结构如下：
typedef struct node{ char ch; //字符域 struct node *next; //指针域，存放下一个结点的地址}node,*linkstr;如下所示：
其初始化操作主要是开辟头结点，同时让它的下一个指针指向为NULL：
//初始化操作linkstr CreateNullString(){ linkstr s; s=(linkstr)malloc(sizeof(node)); if(s!=NULL) s->next=NULL; return s;}由此，完整的案例如下：
#include<stdio.h>#include<stdlib.h>//链式串typedef struct node{ char ch; //字符域 struct node *next; //指针域，存放下一个结点的地址}node,*linkstr;//初始化操作linkstr CreateNullString(){ linkstr s; s=(linkstr)malloc(sizeof(node)); if(s!=NULL) s->next=NULL; return s;}//判断空串int iEmpty(linkstr s){ if(s->next==NULL) return 1; else return 0;}//赋值操作void Stringassign(linkstr s,char t[]){ linkstr p,q,r; r=s; //r始终表示的是尾结点（最后一个非空节点，而不是最后一个NULL节点）。 q=s->next; int i; for(i=0;t[i]!=‘\0‘;i++) if(q!=NULL) { q->ch=t[i]; r=q; q=q->next; } else { //(初始化时只给头结点分配了存储空间或者其他情况)，如果需要继续添加数据（其他节点没分配空间）需要继续分配 p=(linkstr)malloc(sizeof(node)); //添加节点 p->ch=t[i]; r->next=p; r=p; } r->next=NULL; //将s中原来多余的空间释放掉 while(q!=NULL) { p=p->next; free(q); q=p; }}//串拷贝操作void assign(linkstr s,linkstr t){ //将t串的值赋值给s串 linkstr p,q,r,u; p=t->next; q=s->next; r=s; while(p!=NULL) { //串s原先分配了空间 if(q!=NULL) { q->ch=p->ch; r=q; q=q->next; } //若串s原先的空间不够用 else { u=(linkstr)malloc(sizeof(node)); u->ch=p->ch; r->next=u; r=u; } //p节点后移 p=p->next; } //同理，若q的长度过长，可以释放多余的空间 while(q!=NULL) { p=p->next; free(q); q=p; } r->next=NULL;}//求串的长度int length(linkstr s){ linkstr p; int n=0; p=s->next; while(p!=NULL) { n++; p=p->next; } return n;}//串的连接操作void contact(linkstr s,linkstr s1,linkstr s2){ linkstr p,q,r,t; r=s; p=s1->next; q=s->next; while(p!=NULL) { if(q!=NULL) { q->ch=p->ch; q=q->next; r=q; } else { //串s原来没有分配存储空间，需要申请空间 t=(linkstr)malloc(sizeof(node)); t->ch=p->ch; r->next=t; r=t; } p=p->next; } p=s2->next; while(p!=NULL) { if(q!=NULL) { q->ch=p->ch; q=q->next; r=q; } else { //串s原来没有分配存储空间，需要申请空间 t=(linkstr)malloc(sizeof(node)); t->ch=p->ch; r->next=t; r=t; } p=p->next; } //将串s的多余的空间清除掉(这个情况只可能发生在while的if循环中) while(q!=NULL) { p=q->next; free(q); q=p; } r->next=NULL; }//截取子串int substr(linkstr s,int i,int len,linkstr t){ linkstr p,q,r,u; if(i<=0 || i>length(s) || i+len-1>length(s) ) return 0; //指针指向s的第i-1个位置 int j,k; for(j=0,p=s;j<i;j++) p=p->next; for(k=0,r=t,q=t->next;k<len;k++) { if(q!=NULL) { q->ch=p->ch; r=q; q=q->next; } else { u=(linkstr)malloc(sizeof(node)); u->ch=p->ch; r->next=u; r=u; } p=p->next; } while(q!=NULL) { p=q->next; free(q); q=p; } r->next=NULL; return 1;}//插入操作int insert(linkstr s,int i,linkstr t){ linkstr p,q,r; if(i<=0 || i>length(s)+1) return 0; //指向第i-1个位置 int j; for(j=0,p=s;j<i-1;j++) p=p->next; q=t->next; while(q!=NULL) { r=(linkstr)malloc(sizeof(node)); r->ch=q->ch; r->next=p->next; p->next=r; q=q->next; p=r; } return 1;}//删除操作int deleteString(linkstr s,int i,int len){ linkstr p,q,r; if(i<=0 || i>length(s) || i+len-1>length(s) ) return 0; int j; for(j=0,p=s;j<i-1;j++) p=p->next; for(j=0;j<len;j++) { q=p->next; p->next=q->next; free(q); } return 1;}//打印输出void print(linkstr s){ linkstr p=s->next; while(p!=NULL) { printf("%c",p->ch); p=p->next; } printf("\n");}void main(){ linkstr s1; linkstr s2; linkstr s3; s1=CreateNullString(); s2=CreateNullString(); s3=CreateNullString(); char str[100]; printf("请输入字符串：\n"); gets(str); Stringassign(s1,str); printf("串s1："); print(s1); printf("串s1的长度为：%d\n",length(s1)); assign(s2,s1); printf("串s2："); print(s2); printf("串s2删除操作(第三个位置的三个字符删除 ："); deleteString(s2,3,3); print(s2); printf("串连接操作（s3=s1+s2 ）："); contact(s3,s1,s2); print(s3); printf("插入操作(从s1的第6个位置插入s3)："); insert(s1,6,s3); print(s1); printf("测试截取子串的功能s2（截取s3的第四个位置长度为4的字符串："); substr(s3,4,4,s2); print(s2); printf("测试字Contact的清除过多存储空间的功能：(将两个较短的字符[两个s2]合并写到s1上去："); contact(s1,s2,s2); print(s1);} 结果如图：
串的数据结构表——顺序串与链式串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。