Data Structure (Explained in Super Detail!!) Section 18 String (Pile of Strings)

1.Definition

Assume that the one-dimensional array heap [MAXSIZE] represents the storage space for dynamic allocation of strings, and let int start point to the start address of the unallocated area in the heap (start =0 during initialization). During the execution of the program, when a new string is generated, a storage space of the required size is allocated for the new string starting from the position indicated by start, and a description of the string is established at the same time. This storage structure is called a heap structure. At this time, the heap string can be defined as follows:

typedef struct
{int len;
 int start;
} HeapString;

The len field indicates the length of the string, and the start field indicates the starting position of the string. With the help of this structure, a correspondence relationship can be established between the string name and the string value, which is called the storage image of the string name. The storage images of all string names in the system form a symbol table.

In the C language, there is already a free storage space called “heap”, and the malloc() and free() functions can be used to complete dynamic storage management. Therefore, we can directly use the “heap” in C language to implement a heap string. At this time, the heap string can be defined as follows:

typedef struct
{
    char*ch;
    int len;
} HString;

2.Basic operations

1.Initialization

//Initialization
HString * Init_HString( )
{ HString *s;
s = (HString *) malloc ( sizeof( HString ) );
 s->len=0;
 s->ch=NULL;
 printf("Initialization successful.\\
");
return s;
}

2.Input

//Input
int Enter_SStrin(HString *s)
{char x;
int len;
printf("Please enter the string length and elements:");
scanf("%d %c", & amp;len, & amp;x);
s->ch=(char *) malloc (len);
while(x!='#')
{
s->ch[s->len] = x;
s->len=s->len + 1;
scanf(" %c", & amp;x);
}
printf("Entry completed.\\
");
return 1; /*Enter the queue successfully, the function returns 1*/
}

3.Insert

//Insert
int StrInsert(HString *s,HString t) /* Insert string t before the character with serial number pos in string s */
{
int i,pos;
char *temp;
printf("Please enter the insertion position:");
scanf("%d", & amp;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("Insertion successful\\
");
return(1);
} 

4.Delete

//String deletion function
int StrDelete(HString *s) /* Delete len characters starting from serial number pos in string s */
{
int i,pos,len;
char *temp;
printf("Please enter the deletion position and number:");
scanf("%d %d", & amp;pos, & amp;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("Deletion successful\\
");
return(1);
} 

5. Traversal

//Traverse
void Printf(HString *s)
{int i;
for(i=0;i<s->len;i + + )
{printf("%c",s->ch[i]);
}
printf("\\
");
}

6.Copy

//String copy function
int StrCopy(HString *s,HString t) /* Copy the value of string t to string 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("Copying completed.\\
");
return(1);
} 

7. Short judgment

//empty function
int StrEmpty(HString s) /* If string s is empty (that is, the string length is 0), return 1, otherwise return 0 */
{
if (s.len==0) {
printf("Heap string is empty.\\
");
return(1);
}
else
printf("Heap string is not empty.\\
");
return(0);
}

8. Comparison

//String comparison function
int StrCompare(HString s,HString t) /* If string s and t are equal, return 0; if s>t, return 1; if s<t, return -1 */
{
int i;
for (i=0;i<s.len & amp; & amp;i<t.len;i + + )
    if (s.ch[i]!=t.ch[i])
{
    if(s.ch[i]-t.ch[i]==0)
printf("Strings s and t are equal.\\
");
if(s.ch[i]-t.ch[i]>0)
printf("String s is greater than t.\\
");
if(s.ch[i]-t.ch[i]<0)
printf("String s is less than t.\\
");
return(s.ch[i] - t.ch[i]);
}
if(s.len - t.len==0)
printf("Strings s and t are equal.\\
");
if(s.len - t.len>0)
printf("String s is greater than t.\\
");
if(s.len - t.len<0)
printf("String s is less than t.\\
");
return(s.len - t.len);
} 

9. Find the string length

//Function to find string length
int StrLength(HString s) /* Return the length of string s */
{printf("The string length is: %d\\
",s.len);
return(s.len);
} 

10. Clear

//Clear function
int StrClear(HString *s) /* Set string s to an empty string */
{
if (s->ch!=NULL) free(s->ch);
s->ch=NULL;
s->len=0;
printf("Clearing completed.\\
");
return(1);
} 

11.Connection

//Connection function
int StrCat(HString *s,HString t) /* Connect string t to string 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("Connection completed.\\
");
return(1);
}

12. Find substrings

//Find substring function
HString *SubString(HString s) /* Copy len characters starting from the serial number pos in string s to sub */
{
int i,pos,len;
HString *sub;
sub = (HString *) malloc ( sizeof( HString ) );
 sub->len=0;
 sub->ch=NULL;
printf("Please enter the starting position of the substring and the length of the substring:");
scanf("%d %d", & amp;pos, & amp;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("The substring position is illegal.\\
");
   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("Intercepting substring successfully.\\
");
   return(sub);
   }
} 

13. Positioning

//Positioning function
int StrIndex(HString s,HString t) /* Find the position of string t in string s */
{
int i, j,pos;
printf("Please enter the number of elements to search after:");
scanf("%d", & amp;pos);
if (s.len==0 || t.len==0)
{printf("s or t does not exist.\\
");
return(0);
}
i=pos;j=0;
while (i<s.len & amp; & amp; j<t.len)
   { if (s.ch[i]==t.ch[j])
     {
       i + + ;j + + ;
       }
    else {
       i=i-j + 1;j=0;
       }
    }
if (j>=t.len)
{printf("The position of the beginning of string t in s is: %d\\
",i-j);
return(i-j);
}
else
printf("t was not found in s.\\
");
return(0);
}

3. Code

 #include
#include

typedef struct
{
    char*ch;
    int len;
} HString;


//Initialization
HString * Init_HString( )
{ HString *s;
s = (HString *) malloc ( sizeof( HString ) );
 s->len=0;
 s->ch=NULL;
 printf("Initialization successful.\\
");
return s;
}


//Enter
int Enter_SStrin(HString *s)
{char x;
int len;
printf("Please enter the string length and elements:");
scanf("%d %c", & amp;len, & amp;x);
s->ch=(char *) malloc (len);
while(x!='#')
{
s->ch[s->len] = x;
s->len=s->len + 1;
scanf(" %c", & amp;x);
}
printf("Entry completed.\\
");
return 1; /*Enter the queue successfully, the function returns 1*/
}

//Traverse
void Printf(HString *s)
{int i;
for(i=0;i<s->len;i + + )
{printf("%c",s->ch[i]);
}
printf("\\
");
}


//Insert
int StrInsert(HString *s,HString t) /* Insert string t before the character with serial number pos in string s */
{
int i,pos;
char *temp;
printf("Please enter the insertion position:");
scanf("%d", & amp;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;ich[i];
for (i=0;ilen;i + + ) temp[i + t.len]=s->ch[i];
s->len + =t.len;
free(s->ch);s->ch=temp;
printf("Insertion successful\\
");
return(1);
}


//string deletion function
int StrDelete(HString *s) /* Delete len characters starting from serial number pos in string s */
{
int i,pos,len;
char *temp;
printf("Please enter the deletion position and number:");
scanf("%d %d", & amp;pos, & amp;len);
if (pos<0 || pos>(s->len - len)) return(0);
temp=(char *)malloc(s->len - len);
if (temp==NULL) return(0);
for (i=0;ich[i];
for (i=pos;ilen - len;i + + ) temp[i]=s->ch[i + len];
s->len=s->len-len;
free(s->ch);s->ch=temp;
printf("Deletion successful\\
");
return(1);
}

//String copy function
int StrCopy(HString *s,HString t) /* Copy the value of string t to string s */
{
int i;
s->ch=(char *)malloc(t.len);
if (s->ch==NULL) return(0);
for (i=0;ich[i]=t.ch[i];
s->len=t.len;
printf("Copying completed.\\
");
return(1);
}


//empty function
int StrEmpty(HString s) /* If string s is empty (that is, the string length is 0), return 1, otherwise return 0 */
{
if (s.len==0) {
printf("Heap string is empty.\\
");
return(1);
}
else
printf("Heap string is not empty.\\
");
return(0);
}

//string comparison function
int StrCompare(HString s,HString t) /* If string s and t are equal, return 0; if s>t, return 1; if s0)
printf("String s is greater than t.\\
");
if(s.ch[i]-t.ch[i]<0)
printf("String s is less than t.\\
");
return(s.ch[i] - t.ch[i]);
}
if(s.len - t.len==0)
printf("Strings s and t are equal.\\
");
if(s.len - t.len>0)
printf("String s is greater than t.\\
");
if(s.len - t.len<0)
printf("String s is less than t.\\
");
return(s.len - t.len);
}


//Find string length function
int StrLength(HString s) /* Return the length of string s */
{printf("The string length is: %d\\
",s.len);
return(s.len);
}

//Clear function
int StrClear(HString *s) /* Set string s to an empty string */
{
if (s->ch!=NULL) free(s->ch);
s->ch=NULL;
s->len=0;
printf("Clearing completed.\\
");
return(1);
}


//Connection function
int StrCat(HString *s,HString t) /* Connect string t to string 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("Connection completed.\\
");
return(1);
}

//Find substring function
HString *SubString(HString s) /* Copy len characters starting from the serial number pos in string s to sub */
{
int i,pos,len;
HString *sub;
sub = (HString *) malloc ( sizeof( HString ) );
 sub->len=0;
 sub->ch=NULL;
printf("Please enter the starting position of the substring and the length of the substring:");
scanf("%d %d", & amp;pos, & amp;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("The substring position is illegal.\\
");
   return(0);}
else {
   sub->ch=(char *)malloc(len);
   if (sub->ch==NULL) return(0);
   for (i=0;ich[i]=s.ch[i + pos];
   sub->len=len;
   printf("Intercepting substring successfully.\\
");
   return(sub);
   }
}

//Positioning function
int StrIndex(HString s,HString t) /* Find the position of string t in string s */
{
int i, j,pos;
printf("Please enter the number of elements to search after:");
scanf("%d", & amp;pos);
if (s.len==0 || t.len==0)
{printf("s or t does not exist.\\
");
return(0);
}
i=pos;j=0;
while (i<s.len & amp; & amp; j<t.len)
   { if (s.ch[i]==t.ch[j])
     {
       i + + ;j + + ;
       }
    else {
       i=i-j + 1;j=0;
       }
    }
if (j>=t.len)
{printf("The position of the beginning of string t in s is: %d\\
",i-j);
return(i-j);
}
else
printf("t was not found in s.\\
");
return(0);
}

  void menu()
{
printf("--------1.Initialization s------\\
");
printf("--------2.Initialization t------\\
");
printf("--------3.Enter s--------\\
");
printf("--------4.Enter t--------\\
");
printf("--------5.Insert---------\\
");
printf("--------6.Delete---------\\
");
printf("--------7. Empty---------\\
");
printf("--------8.Copy---------\\
");
printf("--------9.Compare---------\\
");
printf("--------10. Find the length------\\
");
printf("--------11. Clear--------\\
");
printf("--------12.Connect--------\\
");
printf("--------13. Find substring sub---\\
");
printf("--------14. Positioning-------\\
");
printf("--------15. Traverse s-------\\
");
printf("--------16. Traverse t-------\\
");
printf("--------17. Traverse sub-----\\
");
printf("--------18.Exit the program----\\
");
}

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", & amp;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("Enter a number between 1 and 18\\
");break;
}
if(quit==1)
{break;
}
}
return 0;
 }

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57208 people are learning the system