Is a string a linear list with special data objects and operations?

Yes, string is a linear list structure with special data objects and operations. The string mentioned in the data structure is a string; the characters in the string have a "one-to-one" logical relationship, so strictly speaking, the string storage structure is a linear storage structure.

The operating environment of this tutorial: Windows 7 system, Dell G3 computer.

The string mentioned in the data structure, that is, a string, is a whole composed of n characters (n >= 0). These n characters can be composed of letters, numbers, or other characters.

In the data structure, strings must be stored in a separate storage structure, which is called a string storage structure.

Strictly speaking, the string storage structure is also a linear storage structure, because the characters in the string also have a "one-to-one" logical relationship. However, unlike the linear storage structure we learned before, the string structure is only used to store character type data.

Special strings

• Empty string: A string containing zero characters. For example: S = "" (nothing in double quotes), usually expressed directly as Ø.

• Space string: A string containing only spaces. Note that it is different from the empty string. There is content in the space string, but it contains spaces, and the space string can contain multiple spaces. For example, a = " " (contains 3 spaces).

• Substring and main string: A string composed of any consecutive characters in the string is called a substring of the string, and the string containing the substring is called the main string.

For example: a = "BEI", b = "BEIJING", c = "BJINGEI". For strings a and b, since b contains the continuous string a,

, it can be said that a is a substring of b, and b is the main string of a; and for c and a, although c also contains all the characters of a, but not consecutive "BEI", so the string c has no relationship with a.

The position of substring in the main string: for string a = "BEI", the position of the first character 'B' in string b is 1, so the position of substring a in main string b = The position in "BEIJING" is 1.

The position of the substring in the main string is different from the storage position of the characters in the array. The position of the substring in the main string starts from 1.

Standard for equality of two strings: If the string values ​​of two strings are exactly the same, then the two strings are equal.

There are three storage structures for string storage

There are three structures for storing strings:

1 Fixed-length sequential storage;

2 Heap allocation storage;

3 Block chain storage.

Fixed-length sequential storage

Use a fixed-length array (i.e., static array) to store strings.

For example: char a[7] = "abcdfg";

When storing a string in this way, you need to estimate the length of the string and apply for enough storage space in advance. If the target string exceeds the length requested by the array, the excess part will be automatically discarded (called "truncation").

For example: char a[3] = "abcdfg";//In fact, only "abc" is stored in the array, and the following ones are truncated. Heap allocated storage

Uses dynamic array to store string

In C language, there is a free storage area called "heap", using the malloc function and Free function management, malloc function is responsible for applying for space, and free function is responsible for releasing space.

For example:

char * a = (char*)malloc(5*sizeof(char));//创建 a 数组，动态申请5个 char 类型数据的存储空间

The advantage of using heap allocation storage is that when it is found that the applied space is not enough, you can re-apply for larger storage space through the realloc() function.

例如：a = (char*)realloc(a, 10*sizeof(char));//前一个参数指申请空间的对象；第二个参数，重新申请空间的大小

The storage space applied for using the malloc function will not be released automatically, and the programmer needs to call the free() function to release it manually. If it is not released manually, it will be recycled by the operating system when the program execution is completely completed.

例如：free(a);//释放动态数组a申请的空间

To give a complete example, the connection strings "abc" and "defg" become "abcdefg";

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
    char * a1=NULL;
    char * a2=NULL;
    
    a1=(char*)malloc(3*sizeof(char));
    strcpy(a1, "abc");//将字符串“abc”复制给a1
    
    a2=(char*)malloc(3*sizeof(char));
    strcpy(a2, "defg");
    
    int lengthA1=strlen(a1);
    int lengthA2=strlen(a2);
    if (lengthA1<lengthA1+lengthA2) {
        a1=(char*)realloc(a1, (lengthA1+lengthA2)*sizeof(char));
    }
    int i;
    for (i=lengthA1; i<lengthA1+lengthA2; i++) {
        a1[i]=a2[i-lengthA1];
    }
    printf("%s",a1);
    
    free(a1);
    free(a2);
    return 0;
}

Note: In the program, When we assigned values ​​to a1 and a2, we used the strcpy copy function. You cannot use it directly here: a1 = "abc".

If you do this, the program will compile with an error, telling you that space without malloc cannot be freed.

The reason is: The strcpy function copies the string to the applied storage space, while direct assignment means the string is stored in another memory space (itself a constant, placed in the constant area),

The pointing of pointers a1 and a2 has been changed. In other words, although the storage space dynamically applied for before was applied for, it was lost before it was used.

Block chain storage

Block chain storage actually borrows the storage structure of a linked list to store strings. Under normal circumstances, it is enough to use a single linked list, and there is no need to add a head node.

When building a linked list, each node can store one character or multiple characters.

链表中最后一个结点的数据域不一定全被串值占满，通常会补上 “#” 或者其他特殊的字符和字符串中的字符区分开。

每个结点设置字符数量的多少和存储的串的长度、可以占用的存储空间以及程序实现的功能相关。

如果串包含数据量很大，但是可用的存储空间有限，那么就需要提高空间利用率，相应地减少结点数量（因为多一个节点，就多申请一个指针域的空间）。

而如果程序中需要大量地插入或者删除数据，如果每个节点包含的字符过多，操作字符就会变得很麻烦，为实现功能增加了障碍。

总结

在平时编写程序，经常会用到例如：char *a = ”abcd”;这种方式表示字符串，和上面三种存储方式最主要的区别是：这种方式用于表示常量字符串，只能使用，不能对字符串内容做修改（否则程序运行出错）；而以上三种方式都可以对字符串进行删改的操作。

例如：

#include <stdio.h>
int main() {
    char* a="abcd";
    a[1]=&#39;b&#39;;
    return 0;
}

程序编译可以通过，运行失败，改成下面堆分配存储的方式就对了：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
    char * a=(char*)malloc(4*sizeof(char));
    strcpy(a, "abcd");
    a[1]=&#39;e&#39;;
    printf("%s",a);
    return 0;
}

三种存储表示方式中，最常用的是堆分配存储，因为它在定长存储的基础上通过使用动态数组，避免了在操作串时可能因为申请存储空间的不足而丢失字符数据；和块链存储方式相比，结构相对简单，更容易操作。

更多计算机编程相关知识，请访问：编程视频！！

The above is the detailed content of Is a string a linear list with special data objects and operations?. For more information, please follow other related articles on the PHP Chinese website!