Oracle

This study note was written in November 2021. At that time, the textbook I was using for class claimed to be implemented in C language but used some C++ syntax. This was not beginner-friendly, so I wrote a series of study notes on data structures, all implemented in pure C language. Many parts were referenced from the source code of Redis, such as doubly linked lists and hash tables. If experts find any errors, please point them out, and I will correct them. I hope these notes can serve as an introductory reference for computer beginners.

About Pointers#

Pointers are an essential part of the C language and are also crucial for representing linked storage structures. Understanding the basic concepts of pointers makes it easier to understand linked data structures such as linked lists.

Understanding Pointers and Pointer Variables#

Variables are used to store data, pointers are memory addresses, and pointer variables are used to store memory addresses.

    // Declare an integer variable age with a value of 17
    int age = 17;
    // Declare an integer pointer that points to the address of the variable age. The "&" symbol can be understood as the "address-of" symbol.
    int *p = &age;
    printf("Value of age: %d\n", age);
    printf("Value of *p: %d\n", *p);
    printf("Address of variable age: %p\n", &age);
    printf("Address pointed to by pointer p: %p\n", p);
    printf("Address of pointer p itself: %p\n", &p);

Output:

    Value of age: 17
    Value of *p: 17
    Address of variable age: 000000000062FE1C
    Address pointed to by pointer p: 000000000062FE1C
    Address of pointer p itself: 000000000062FE10

Pointer Diagram#

About Memory#

You may have doubts about memory addresses, which can be roughly understood as follows:

The integer pointer variable p stores the memory address of the integer variable age. The symbol & is the address-of symbol, so &age = 000000000062FE1C. Since the pointer variable itself is also a variable, p also has its own address, which can be obtained by taking the address of p: &p = 000000000062FE10. The *p notation retrieves the value stored in the memory address corresponding to the value stored in the pointer variable p.

Declaration of Struct#

Structures (struct) are frequently used in C programming. For those who have learned object-oriented programming languages, structures can be loosely understood as objects with only attributes and no methods. The declaration of a structure describes the composition layout of an object.

Declare a struct for describing a student:

struct student {
    char name[64];
    int age;
    int class;
}

Here, student is called a struct tag. You can think of struct student as a variable type similar to int. Now you can start using this structure:

Initialization of Struct#

Initializing all attributes at once#

struct student stu = {"austin", 19, 3};

Note:
The order of values in the braces must match the order of attributes declared in the structure.

Declaring first and then initializing separately#

struct student stu;
strcpy(stu.name, "austin");
stu.age = 19;
stu.class = 3;

About the strcpy function
The strcpy function is from the C standard library <string.h>. Don't forget to include it when using it. Since C does not have a variable type like String, we usually use character arrays to represent strings. However, character arrays cannot be directly assigned to strings. The strcpy function can solve this problem.

Combining attribute declaration and variable declaration#

struct student {
    char name[64];
    int age;
    int class;
} stu;
/* Then you can initialize this structure
strcpy(stu.name, "austin");
stu.age = 19;
stu.class = 3; */

Initialization can also be written together#

struct student {
    char name[64];
    int age;
    int class;
} stu = {"austin", 19, 3};

Multiple variables can be initialized together:

struct student {
    char name[64];
    int age;
    int class;
} stu = {"austin", 19, 3},
stu2 = {"tim", 78, 100};

The struct tag can be omitted#

If you only need a variable stu of type struct student, you can omit the struct tag student:

struct {
    char name[64];
    int age;
    int class;
} stu;

The disadvantage of this approach is that you cannot declare other variables like struct student stu.

Using Struct#

When defining a structure variable, use . to access members.
When defining a structure pointer, use -> to access members.

struct student {
    char name[64];
    int age;
    int class;
} stu;

// Initialize the structure variable
strcpy(stu.name, "austin");
stu.age = 19;
stu.class = 3;

struct student *stu_ptr = &stu;

// Access structure variable members using .
printf("age: %d\n", stu.age);
// Access using ->
printf("age: %d\n", stu_ptr->age);

Using typedef#

For example, there is a structure like this:

struct student {
    char name[64];
    int age;
    int class;
}

When using this structure, we declare variables like struct student stu. We can use the typedef keyword to assign an alias to struct student:

typedef struct student s;

In the above code, we assign the alias s to struct student. So the statement s stu; is equivalent to struct student stu, which is more concise and convenient. We can also use the typedef keyword when defining the structure itself, which can be combined into the following code:

typedef struct student {
    char name[64];
    int age;
    int class;
} s;

Summary#

Although there are various ways to use struct, it is not difficult to understand. It is recommended to master the use of struct, as it is the basic syntax for learning data structures.