1.定義
假設(shè)以一維數(shù)組heap [MAXSIZE] 表示可供字符串進(jìn)行動(dòng)態(tài)分配的存儲(chǔ)空間,并設(shè) int start 指向heap 中未分配區(qū)域的開始地址(初始化時(shí)start =0) 。在程序執(zhí)行過程中,當(dāng)生成一個(gè)新串時(shí),就從start指示的位置起,為新串分配一個(gè)所需大小的存儲(chǔ)空間,同時(shí)建立該串的描述。這種存儲(chǔ)結(jié)構(gòu)稱為堆結(jié)構(gòu)。 此時(shí),堆串可定義如下:
typedef struct
{int len;
int start;
} HeapString;
其中l(wèi)en域指示串的長度, start域指示串的起始位置。借助此結(jié)構(gòu)可以在串名和串值之間建立一個(gè)對(duì)應(yīng)關(guān)系,稱為串名的存儲(chǔ)映象。系統(tǒng)中所有串名的存儲(chǔ)映象構(gòu)成一個(gè)符號(hào)表。?
文章來源:http://www.zghlxwxcb.cn/news/detail-744342.html
?在C語言中,已經(jīng)有一個(gè)稱為“堆”的自由存儲(chǔ)空間,并可用malloc()和free()函數(shù)完成動(dòng)態(tài)存儲(chǔ)管理。因此,我們可以直接利用C語言中的“堆”實(shí)現(xiàn)堆串。此時(shí),堆串可定義如下:文章來源地址http://www.zghlxwxcb.cn/news/detail-744342.html
typedef struct
{
char * ch;
int len;
} HString;
2.基本操作
1.初始化
//初始化
HString * Init_HString( )
{ HString *s;
s = (HString *) malloc ( sizeof( HString ) );
s->len=0;
s->ch=NULL;
printf("初始化成功。\n");
return s;
}
2.錄入
//錄入
int Enter_SStrin(HString *s)
{char x;
int len;
printf("請(qǐng)輸入字符串長度和元素:");
scanf("%d %c",&len,&x);
s->ch=(char *) malloc ( len );
while(x!='#')
{
s->ch[s->len] = x;
s->len=s->len+1;
scanf(" %c",&x);
}
printf("錄入完成。\n");
return 1; /*入隊(duì)成功,函數(shù)返回1*/
}
3.插入
//插入
int StrInsert(HString *s,HString t) /* 在串s中序號(hào)為pos的字符之前插入串t */
{
int i,pos;
char *temp;
printf("請(qǐng)輸入插入位置:");
scanf("%d",&pos);
if (pos<0 || pos>s->len || s->len==0) return(0);
temp=(char *)malloc(s->len + t.len);
if (temp==NULL) return(0);
for (i=0;i<pos;i++) temp[i]=s->ch[i];
for (i=0;i<t.len;i++) temp[i+pos]=t.ch[i];
for (i=pos;i<s->len;i++) temp[i + t.len]=s->ch[i];
s->len+=t.len;
free(s->ch);s->ch=temp;
printf("插入成功\n");
return(1);
}
4.刪除
//串刪除函數(shù)
int StrDelete(HString *s) /* 在串s中刪除從序號(hào)pos起的len個(gè)字符 */
{
int i,pos,len;
char *temp;
printf("請(qǐng)輸入刪除位置和個(gè)數(shù):");
scanf("%d %d",&pos,&len);
if (pos<0 || pos>(s->len - len)) return(0);
temp=(char *)malloc(s->len - len);
if (temp==NULL) return(0);
for (i=0;i<pos;i++) temp[i]=s->ch[i];
for (i=pos;i<s->len - len;i++) temp[i]=s->ch[i+len];
s->len=s->len-len;
free(s->ch);s->ch=temp;
printf("刪除成功\n");
return(1);
}
5.遍歷
//遍歷
void Printf(HString *s)
{int i;
for(i=0;i<s->len;i++)
{printf("%c",s->ch[i]);
}
printf("\n");
}
6.復(fù)制
//串復(fù)制函數(shù)
int StrCopy(HString *s,HString t) /* 將串t的值復(fù)制到串s中 */
{
int i;
s->ch=(char *)malloc(t.len);
if (s->ch==NULL) return(0);
for (i=0;i<t.len;i++) s->ch[i]=t.ch[i];
s->len=t.len;
printf("復(fù)制完成。\n");
return(1);
}
7.判空
//判空函數(shù)
int StrEmpty(HString s) /* 若串s為空(即串長為0),則返回1,否則返回0 */
{
if (s.len==0) {
printf("堆串為空。\n");
return(1);
}
else
printf("堆串不為空。\n");
return(0);
}
8.比較
//串比較函數(shù)
int StrCompare(HString s,HString t) /* 若串s和t相等, 則返回0; 若s>t, 則返回1; 若s<t, 則返回-1 */
{
int i;
for (i=0;i<s.len&&i<t.len;i++)
if (s.ch[i]!=t.ch[i])
{
if(s.ch[i]- t.ch[i]==0)
printf("串s和t相等。\n");
if(s.ch[i]- t.ch[i]>0)
printf("串s大于t。\n");
if(s.ch[i]- t.ch[i]<0)
printf("串s小于t。\n");
return(s.ch[i] - t.ch[i]);
}
if(s.len - t.len==0)
printf("串s和t相等。\n");
if(s.len - t.len>0)
printf("串s大于t。\n");
if(s.len - t.len<0)
printf("串s小于t。\n");
return(s.len - t.len);
}
9.求串長
//求串長函數(shù)
int StrLength(HString s) /* 返回串s的長度 */
{printf("串長為:%d\n",s.len);
return(s.len);
}
10.清空
//清空函數(shù)
int StrClear(HString *s) /* 將串s置為空串 */
{
if (s->ch!=NULL) free(s->ch);
s->ch=NULL;
s->len=0;
printf("清空完成。\n");
return(1);
}
11.連接
//連接函數(shù)
int StrCat(HString *s,HString t) /* 將串t連接在串s的后面 */
{
int i;
char *temp;
temp=(char *)malloc(s->len + t.len);
if (temp==NULL) return(0);
for (i=0;i<s->len;i++)
temp[i]=s->ch[i];
for (i=s->len;i<s->len + t.len;i++)
temp[i]=t.ch[i-s->len];
s->len+=t.len;
free(s->ch);s->ch=temp;
printf("連接完成。\n");
return(1);
}
12.求子串
//求子串函數(shù)
HString *SubString(HString s) /* 將串s中序號(hào)pos起的len個(gè)字符復(fù)制到sub中 */
{
int i,pos,len;
HString *sub;
sub = (HString *) malloc ( sizeof( HString ) );
sub->len=0;
sub->ch=NULL;
printf("請(qǐng)輸入子串起始位置,和子串長度:");
scanf("%d %d",&pos,&len);
if (sub->ch!=NULL) free(sub->ch);
if (pos<0 || pos>s.len || len<1 || len>s.len-pos)
{ sub->ch=NULL;
sub->len=0;
printf("子串位置不合法。\n");
return(0);}
else {
sub->ch=(char *)malloc(len);
if (sub->ch==NULL) return(0);
for (i=0;i<len;i++)
sub->ch[i]=s.ch[i+pos];
sub->len=len;
printf("截取子串成功。\n");
return(sub);
}
}
13.定位
//定位函數(shù)
int StrIndex(HString s,HString t) /* 求串t在串s中的位置 */
{
int i, j,pos;
printf("請(qǐng)輸入在第幾個(gè)元素之后進(jìn)行查找:");
scanf("%d",&pos);
if (s.len==0 || t.len==0)
{printf("s或t不存在。\n");
return(0);
}
i=pos;j=0;
while (i<s.len && j<t.len)
{ if (s.ch[i]==t.ch[j])
{
i++;j++;
}
else {
i=i-j+1;j=0;
}
}
if (j>=t.len)
{printf("串t首在s中的位置為:%d\n",i-j);
return(i-j);
}
else
printf("未在s中找到t。\n");
return(0);
}
3.代碼
#include<stdio.h>
#include<malloc.h>
typedef struct
{
char * ch;
int len;
} HString;
//初始化
HString * Init_HString( )
{ HString *s;
s = (HString *) malloc ( sizeof( HString ) );
s->len=0;
s->ch=NULL;
printf("初始化成功。\n");
return s;
}
//錄入
int Enter_SStrin(HString *s)
{char x;
int len;
printf("請(qǐng)輸入字符串長度和元素:");
scanf("%d %c",&len,&x);
s->ch=(char *) malloc ( len );
while(x!='#')
{
s->ch[s->len] = x;
s->len=s->len+1;
scanf(" %c",&x);
}
printf("錄入完成。\n");
return 1; /*入隊(duì)成功,函數(shù)返回1*/
}
//遍歷
void Printf(HString *s)
{int i;
for(i=0;i<s->len;i++)
{printf("%c",s->ch[i]);
}
printf("\n");
}
//插入
int StrInsert(HString *s,HString t) /* 在串s中序號(hào)為pos的字符之前插入串t */
{
int i,pos;
char *temp;
printf("請(qǐng)輸入插入位置:");
scanf("%d",&pos);
if (pos<0 || pos>s->len || s->len==0) return(0);
temp=(char *)malloc(s->len + t.len);
if (temp==NULL) return(0);
for (i=0;i<pos;i++) temp[i]=s->ch[i];
for (i=0;i<t.len;i++) temp[i+pos]=t.ch[i];
for (i=pos;i<s->len;i++) temp[i + t.len]=s->ch[i];
s->len+=t.len;
free(s->ch);s->ch=temp;
printf("插入成功\n");
return(1);
}
//串刪除函數(shù)
int StrDelete(HString *s) /* 在串s中刪除從序號(hào)pos起的len個(gè)字符 */
{
int i,pos,len;
char *temp;
printf("請(qǐng)輸入刪除位置和個(gè)數(shù):");
scanf("%d %d",&pos,&len);
if (pos<0 || pos>(s->len - len)) return(0);
temp=(char *)malloc(s->len - len);
if (temp==NULL) return(0);
for (i=0;i<pos;i++) temp[i]=s->ch[i];
for (i=pos;i<s->len - len;i++) temp[i]=s->ch[i+len];
s->len=s->len-len;
free(s->ch);s->ch=temp;
printf("刪除成功\n");
return(1);
}
//串復(fù)制函數(shù)
int StrCopy(HString *s,HString t) /* 將串t的值復(fù)制到串s中 */
{
int i;
s->ch=(char *)malloc(t.len);
if (s->ch==NULL) return(0);
for (i=0;i<t.len;i++) s->ch[i]=t.ch[i];
s->len=t.len;
printf("復(fù)制完成。\n");
return(1);
}
//判空函數(shù)
int StrEmpty(HString s) /* 若串s為空(即串長為0),則返回1,否則返回0 */
{
if (s.len==0) {
printf("堆串為空。\n");
return(1);
}
else
printf("堆串不為空。\n");
return(0);
}
//串比較函數(shù)
int StrCompare(HString s,HString t) /* 若串s和t相等, 則返回0; 若s>t, 則返回1; 若s<t, 則返回-1 */
{
int i;
for (i=0;i<s.len&&i<t.len;i++)
if (s.ch[i]!=t.ch[i])
{
if(s.ch[i]- t.ch[i]==0)
printf("串s和t相等。\n");
if(s.ch[i]- t.ch[i]>0)
printf("串s大于t。\n");
if(s.ch[i]- t.ch[i]<0)
printf("串s小于t。\n");
return(s.ch[i] - t.ch[i]);
}
if(s.len - t.len==0)
printf("串s和t相等。\n");
if(s.len - t.len>0)
printf("串s大于t。\n");
if(s.len - t.len<0)
printf("串s小于t。\n");
return(s.len - t.len);
}
//求串長函數(shù)
int StrLength(HString s) /* 返回串s的長度 */
{printf("串長為:%d\n",s.len);
return(s.len);
}
//清空函數(shù)
int StrClear(HString *s) /* 將串s置為空串 */
{
if (s->ch!=NULL) free(s->ch);
s->ch=NULL;
s->len=0;
printf("清空完成。\n");
return(1);
}
//連接函數(shù)
int StrCat(HString *s,HString t) /* 將串t連接在串s的后面 */
{
int i;
char *temp;
temp=(char *)malloc(s->len + t.len);
if (temp==NULL) return(0);
for (i=0;i<s->len;i++)
temp[i]=s->ch[i];
for (i=s->len;i<s->len + t.len;i++)
temp[i]=t.ch[i-s->len];
s->len+=t.len;
free(s->ch);s->ch=temp;
printf("連接完成。\n");
return(1);
}
//求子串函數(shù)
HString *SubString(HString s) /* 將串s中序號(hào)pos起的len個(gè)字符復(fù)制到sub中 */
{
int i,pos,len;
HString *sub;
sub = (HString *) malloc ( sizeof( HString ) );
sub->len=0;
sub->ch=NULL;
printf("請(qǐng)輸入子串起始位置,和子串長度:");
scanf("%d %d",&pos,&len);
if (sub->ch!=NULL) free(sub->ch);
if (pos<0 || pos>s.len || len<1 || len>s.len-pos)
{ sub->ch=NULL;
sub->len=0;
printf("子串位置不合法。\n");
return(0);}
else {
sub->ch=(char *)malloc(len);
if (sub->ch==NULL) return(0);
for (i=0;i<len;i++)
sub->ch[i]=s.ch[i+pos];
sub->len=len;
printf("截取子串成功。\n");
return(sub);
}
}
//定位函數(shù)
int StrIndex(HString s,HString t) /* 求串t在串s中的位置 */
{
int i, j,pos;
printf("請(qǐng)輸入在第幾個(gè)元素之后進(jìn)行查找:");
scanf("%d",&pos);
if (s.len==0 || t.len==0)
{printf("s或t不存在。\n");
return(0);
}
i=pos;j=0;
while (i<s.len && j<t.len)
{ if (s.ch[i]==t.ch[j])
{
i++;j++;
}
else {
i=i-j+1;j=0;
}
}
if (j>=t.len)
{printf("串t首在s中的位置為:%d\n",i-j);
return(i-j);
}
else
printf("未在s中找到t。\n");
return(0);
}
void menu()
{
printf("--------1.初始化s------\n");
printf("--------2.初始化t------\n");
printf("--------3.錄入s--------\n");
printf("--------4.錄入t--------\n");
printf("--------5.插入---------\n");
printf("--------6.刪除---------\n");
printf("--------7.判空---------\n");
printf("--------8.復(fù)制---------\n");
printf("--------9.比較---------\n");
printf("--------10.求長度------\n");
printf("--------11.清空--------\n");
printf("--------12.連接--------\n");
printf("--------13.求子串sub---\n");
printf("--------14.定位-------\n");
printf("--------15.遍歷s-------\n");
printf("--------16.遍歷t-------\n");
printf("--------17.遍歷sub-----\n");
printf("--------18.退出程序----\n");
}
int main()
{HString *s,*t,*sub;
int n1,n2,n3,n4,n5,n6,n7,n8,n9,n10,n11,a,quit=0;
menu();
while(1)
{
scanf("%d",&a);
switch(a)
{
case 1:s=Init_HString( );break;
case 2:t=Init_HString( );break;
case 3:n1=Enter_SStrin(s);break;
case 4:n2=Enter_SStrin(t);break;
case 5:n3=StrInsert(s,*t);break;
case 6:n4=StrDelete(s);break;
case 7:n5=StrEmpty(*s);break;
case 8:n6=StrCopy(s,*t);break;
case 9:n7=StrCompare(*s,*t) ;break;
case 10:n8=StrLength(*s);break;
case 11:n9=StrClear(s);break;
case 12:n10=StrCat(s,*t);break;
case 13:sub=SubString(*s);break;
case 14:n11=StrIndex(*s,*t);break;
case 15:Printf(s);break;
case 16:Printf(t);break;
case 17:Printf(sub);break;
case 18:quit=1;break;
default:printf("輸入1~18之間的數(shù)字\n");break;
}
if(quit==1)
{break;
}
}
return 0;
}
到了這里,關(guān)于數(shù)據(jù)結(jié)構(gòu)(超詳細(xì)講解!!)第十八節(jié) 串(堆串)的文章就介紹完了。如果您還想了解更多內(nèi)容,請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持TOY模板網(wǎng)!