This is the 8th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

preface

On an article, the blogger wrote the order list of simple operation, string and we’ve learned before stack, queue, are chain storage structure, because the order of storage is always limited, and the chain store is don’t need us to define the size and generate as much as they want to use, you will not release, indeed in terms of storage, the chain store has a lot of advantages, This article needs to be combined with the last article to see, because there are a lot of logic, the blogger is said to like an article, ha ha ha steal lazy, next let us learn!! 😁 😁 😁

Once a day, try!!

1. Understand the logic of chain string and the core code of chain string

The list storage structure of a string is similar to that of a sequential storage structure with the difference between compact and non-compact storage structures. Insert and delete operation efficiency is high; The storage space usage is low.

A logical diagram for the establishment of a chain string

Core code:

There’s no hard code, just some basic code, as long as you’re good at linking lists, there’s no problem with that, right

Typedef struct Node// char data; Struct Node *next; }*LinkString; // Pointer structure type name LinkString s1; // define string pointer s=(LinkString)malloc(sizeof(Node)); S ->next=NULL; Q ->data=p->data; // Free (q); // Release the nodeCopy the code

2. Chain initialization and some basic operations

Chain string of the most basic initialization, judge empty string, find the length.

LinkString CreateNullString() // LinkString initialization {LinkString s; // define the first Node s=(LinkString)malloc(sizeof(Node)); // Allocate memory if(s! S ->next=NULL; return s; If (s->next==NULL) return 1; if(s->next==NULL) return 1; else return 0; } int length(LinkString s) {LinkString p; int n=0; p=s->next; while(p! =NULL)// traversal string {n++; P =p->next; } return n; Void print(LinkString s) {LinkString p=s->next; while(p! =NULL) { printf("%c",p->data); p=p->next; } printf("\n"); }Copy the code

3. Chain string assignment operation

This assignment is the equivalent of a single linked list, not too difficult, and the blogger has written detailed notes

Void Stringassign(LinkString s,char t[]) {LinkString p,q,r; r=s; //r always represents the end node (the last non-empty node, not the last NULL node). q=s->next; int i; for(i=0; t[i]! = '\ 0'; I++)// iterate over the array we want to assign if(q! =NULL) {q->data=t[I]; // assign to r=q; Q =q->next; Else {p=(LinkString)malloc(sizeof(Node)); P ->data=t[I]; / / assignment r - > next = p; // connect to new node r=p; } r->next=NULL; // The last node points to an empty while(q! {p=p->next; // Point to the next free(q); / / release q = p; // Assign the unreleased value to q}}Copy the code

4. Chain string copy operation

Chain string copy operation logic and sequence string consistent, do not understand can see the blogger on an article. Is there really nothing so logically consistent that a blogger doesn’t even want to draw a logical graph, so a blogger would put an article under it

Void assign(LinkString s,LinkString t) {LinkString p,q,r, STR; p=t->next; q=s->next; r=s; while(p! =NULL) // traversal t string {if(q! {q->data=p->data; / / copy r = q; Q =q->next; {STR =(LinkString)malloc(sizeof(Node)); STR ->data=p->data; / / copy r - > next = STR; // the last connection to the new node r= STR; } p=p->next; } while(q! {p=p->next; free(q); // free the node q=p; } r->next=NULL; }Copy the code

A connection between two strings

The logic for joining is the same as for sequential strings, creating a new string and then joining

Void contact(LinkString s,LinkString s1,LinkString s2) {LinkString p,q,r,t; r=s; p=s1->next; q=s->next; while(p! =NULL)// traverse S1 and assign to s {if(q! {q->data=p->data; q=q->next; r=q; } else { t=(LinkString)malloc(sizeof(Node)); T ->data=p->data; r->next=t; r=t; } p=p->next; } p=s2->next; // reassign p to traverse s2 while(p! =NULL)// s2 assignment {if(q! {q->data=p->data; q=q->next; r=q; } else {t=(LinkString)malloc(sizeof(Node)); t->data=p->data; r->next=t; r=t; } p=p->next; } while(q! {p=q->next; free(q); q=p; } r->next=NULL; // The last pointer to NULL}Copy the code

6. Chain string get substring operation

I’m going to use a sequential graph to represent the logic, the logic is the same except that the assignments are different

Int substr(LinkString s,int I,int len,LinkString t) {LinkString p,q,r,u; If (I < = 0 | | I > length (s) | | I + len - 1 > length (s)) / / judge the validity of len and I return 0; Int j,k; // int j,k; for(j=0,p=s; j<i; P =p->next; for(k=0,r=t,q=t->next; k<len; k++) { if(q! {q->data=p->data; R = q / / assignment; Q =q->next; } else { u=(LinkString)malloc(sizeof(Node)); U ->data=p->data; / / assignment r - > next = u; // join new node r=u; } p=p->next; //s string shifts to the next} while(q! {p=q->next; free(q); q=p; } r->next=NULL; return 1; }Copy the code

7. Chain string insertion operation

So let’s do it again, insert in a single linked list, it’s really the same logic, it’s no different, delete is the same logic.

Int insert(LinkString s,int I,LinkString t) int insert(LinkString s,int I,LinkString t) If (I < = 0 | | I > length (s) + 1) / / judge the validity of the I return 0; Int j; // int j; for(j=0,p=s; j<i-1; P =p->next; q=t->next; while(q! =NULL)// traversal t insert string {r=(LinkString)malloc(sizeof(Node)); R ->data=q->data; R ->next=p->next; P ->next=r; Q =q->next; q=q->next; //t string shifted to the next node p=r; } return 1;} return 1; }Copy the code

8. Delete chain string operation

Int deleteString(LinkString s,int I,int len){//s represents the string, I represents the starting position, len represents the number of LinkString p,q,r after I; If (I < = 0 | | I > length (s) | | I + len - 1 > length (s)) / / and sequence logic consistent, we can see a bo master article return 0; int j; for(j=0,p=s; j<i-1; P =p->next; for(j=0; j<len; J++) {q=p->next; P ->next=q->next; // set the pointer field from the previous position to the next free(q); } return 1; }Copy the code

9. Effect demonstration and overall code

Overall code :(can run directly)

#include <iostream> #include<stdio.h> #include<stdlib.h> typedef struct Node { char data; Struct Node *next; }*LinkString; LinkString CreateNullString() // LinkString initialization {LinkString s; // define the first Node s=(LinkString)malloc(sizeof(Node)); // Allocate memory if(s! S ->next=NULL; return s; If (s->next==NULL) return 1; if(s->next==NULL) else return 0; } void Stringassign(LinkString s,char t[]) {LinkString p,q,r; r=s; //r always represents the end node (the last non-empty node, not the last NULL node). q=s->next; int i; for(i=0; t[i]! = '\ 0'; I++)// iterate over the array we want to assign if(q! =NULL) {q->data=t[I]; // assign to r=q; Q =q->next; Else {p=(LinkString)malloc(sizeof(Node)); P ->data=t[I]; / / assignment r - > next = p; // connect to new node r=p; } r->next=NULL; // The last node points to an empty while(q! {p=p->next; // Point to the next free(q); / / release q = p; Void assign(LinkString s,LinkString t) {LinkString p,q,r, STR; LinkString p,q,r, STR; p=t->next; q=s->next; r=s; while(p! =NULL) // traversal t string {if(q! {q->data=p->data; / / copy r = q; Q =q->next; {STR =(LinkString)malloc(sizeof(Node)); STR ->data=p->data; / / copy r - > next = STR; // the last connection to the new node r= STR; } p=p->next; } while(q! {p=p->next; free(q); // free the node q=p; } r->next=NULL; } int length(LinkString s) {LinkString p; int n=0; p=s->next; while(p! =NULL)// traversal string {n++; P =p->next; } return n; Void contact(LinkString s,LinkString s1,LinkString s2) {LinkString p,q,r,t; r=s; p=s1->next; q=s->next; while(p! =NULL)// traverse S1 and assign to s {if(q! {q->data=p->data; q=q->next; r=q; } else { t=(LinkString)malloc(sizeof(Node)); T ->data=p->data; r->next=t; r=t; } p=p->next; } p=s2->next; // reassign p to traverse s2 while(p! =NULL)// s2 assignment {if(q! {q->data=p->data; q=q->next; r=q; } else {t=(LinkString)malloc(sizeof(Node)); t->data=p->data; r->next=t; r=t; } p=p->next; } while(q! {p=q->next; free(q); q=p; } r->next=NULL; Int substr(LinkString s,int I,int len,LinkString t) {LinkString p,q,r,u; if(i<=0 || i>length(s) || i+len-1>length(s) ) return 0; Int j,k; // 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->data=p->data; r=q; q=q->next; } else { u=(LinkString)malloc(sizeof(Node)); u->data=p->data; 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(LinkString s,int I,LinkString t) {LinkString p,q,r; if(i<=0 || i>length(s)+1) return 0; Int j; // int j; for(j=0,p=s; j<i-1; j++) p=p->next; q=t->next; while(q! =NULL) { r=(LinkString)malloc(sizeof(Node)); r->data=q->data; r->next=p->next; p->next=r; q=q->next; p=r; } return 1; } int deleteString(LinkString s,int I,int len){LinkString 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(LinkString s) {LinkString p=s->next; while(p! =NULL) { printf("%c",p->data); p=p->next; } printf("\n"); } int main(int argc, char** argv) { LinkString s1; LinkString s2; LinkString s3; s1=CreateNullString(); s2=CreateNullString(); s3=CreateNullString(); char str[100]; Printf (" Please enter string: \n"); gets(str); Stringassign(s1,str); Printf (" s1: "); print(s1); Printf (" s1: length: %d\n",length(s1)); assign(s2,s1); Printf (" s2: "); print(s2); Printf (" chain s2 delete operation (three characters removed in position 2: "); DeleteString (s2, 2, 3); print(s2); Printf (" chain join operation joins s1 and s2 to produce s3: "); contact(s3,s1,s2); print(s3); Printf (" chain insert operation (insert s3 from position 6 of s1) : "); Insert (s1, 6, s3); print(s1); Printf (" string intercepts substring s2 (intercepts fourth position of s3 string of length 4: "); Substr (s3, 4, 4, s2); print(s2); return 0; }Copy the code

Conclusion:

Chain string really is not difficult, is what we learned before, in its form, logic, bloggers feel now, why linear table storage structure list to learn first, because the back of the stack, queue, string, basically is done on the basis of the linked list, not how difficult, no technique problems above, next, I’m going to learn an array, Pay attention to the following article oh, creation is not easy to praise, comment, collection oh!! ❤ ❤ ❤

The last:Advanced data structure learning, sequence (sequence and algorithm)

The last:# Data Structure upgrade study notes, linear list linked List section

Next up:Data structure advanced learning, array and array matrix three kinds of compression