Explain sequential and chain structures with stories

study hard and make progress every day

This article has included to my lot DayDayUP:github.com/RobodLee/DayDayUP warehouse, welcome Star

⭐⭐⭐⭐⭐

preface

This semester we have a course on information technology teaching, where each student is assigned a chapter on data structure and then comes on stage to talk about it. I was given a sequence structure and a chain structure. To make it interesting, I made up a short story and made some animations. I feel good, the animation has been done for a long time, in order not to waste my hard story and animation, so I want to share with you.

Computer memory

Both sequential and chained structures describe how data is stored in memory. So in order to understand these two data structures, it is necessary to first introduce the computer’s memory.

In the figure above, each row in the figure is a storage unit. Several storage units form a storage body. Each storage unit is connected to a selection line corresponding to the memory address.

For example, to read the data of the memory unit with the memory address 0, the CPU first sends the address information to MAR through the address bus, and MAR then sends the address to the decoder, which can select the corresponding word line through the address, and then sends a signal to the corresponding memory unit. Finally, the binary data from the storage cell can be sent to the MDR through the data wire (green wire). In this way, the data read operation is completed. If it is a write operation, the data in the MDR is sent to the corresponding storage unit through the data cable to control the read/write control line.

These are some knowledge of computer constitute principle, have not learned friend may see don’t quite understand, it doesn’t matter, just know a concept here, that is the computer’s memory is made up of several storage locations, each storage unit has a unique number (memory address), computer storage unit of the specified memory address to read/write operations.

For example, computer memory can be thought of as a hotel. Each room is a storage unit. The room number corresponds to the memory address, and the occupant of the room is the data stored in the memory.

Sequential structure

Before we introduce sequential structures, here’s a quick story:

One day, grandpa took seven gourd babies to the city for a trip.

Since it is to travel, so can not sleep on the street, so grandpa and gourd children are going to find a hotel to stay. They found a hotel with more empty rooms. Grandpa opened seven rooms connected together at a time, and then let seven gourd children live in them one by one.

As can be seen from the picture, the seven rooms are next to each other, so the seven calabash children also live in their own rooms one by one. Something like this is a sequential structure.

Sequential structure, which means that each data element is sequentially stored in a set of storage cells with consecutive addresses in the computer. In this way, logically adjacent elements are also adjacent in computer memory.

The sequence structure corresponds to an array, so how to express the above example in code:

In this code, the new keyword opens an array of size 7, which is equivalent to grandpa opening seven rooms and storing seven data into the array, which is equivalent to seven gourd children living in their respective rooms.

The chain structure

Let’s do the sequential structure and then let’s do the chain structure. Or continue with the story above.

Gourd children in this hotel after a period of time, feel a little boring to live, want to change another. But grandpa thought: why do you want to change? But t ao however these several small, can only depend on them, after all, double fist is difficult to rival fourteen hands, although grandpa is long and strong,

Then they packed up and went to a new hotel.

Because the hotel business is good, there are a lot of people, there are no seven rooms connected together, grandpa simply let them live, choose their own room to live.

After the end of the grandpa thought: these small dolls how to live so scattered, if lost how to do, not love me dead.

As a result, grandpa found the front desk little sister, looking for her to seven pieces of paper.

Then grandpa gave seven small pieces of paper to the calabash children, and each of them wrote down the next calabash child’s room number on the small paper. In this way, although several calabash children do not live together, they can find the room of the next calabash child through the room number on the paper. So from the big baby, you can find all the gourd baby.

The chain structure is characterized by the fact that the addresses of the computer storage units storing individual data elements are not necessarily contiguous, but are logically contiguous. Each node contains two parts: data field and pointer field.

That’s what the story is about. Let’s think about another problem. Now we can find the next calabash baby’s room by slip of paper, but how do we find the last one? It seems not possible, but make some modifications. For example, now each calabash baby has two pieces of paper on hand, and the other piece of paper records the room number of the previous calabash baby.

So this is essentially a double-linked list, where each node has two Pointers to the last node and the next node.

So, data structures are the study of how data is stored in memory. Although there are many data structures, the data is stored in memory, but the constraints are different, the concept is different. Whether it is stack, queue and other simple data structure, or tree, graph and other complex data structure, their implementation is no more than three ways: sequential storage, chain storage, sequential storage + chain storage.

expand

Finally, we will expand the knowledge of how to use sequential structure and chain structure to implement stack.

A stack is a data structure that can only hold and retrieve data from the top of the stack. Elements cannot be operated on from the bottom of the stack.

If you use a sequential structure, you can prepare an array that starts at the bottom of the stack and ends near the top. Then adding and removing elements can only be done from the trailing side.

typedef struct {
    ElemType data[MaxSize];     // It is used to store data
    int top;                    // point to the top of the stack
} SqStack;
Copy the code

If I had a chain structure instead. The head of the table is the bottom of the stack and the tail is the top of the stack. Then you can only add or remove elements from the end of the table. If the table head is the top of the stack and the table tail is the bottom of the stack, it is also possible, but only from one end of the stack definition.

typedef struct StackNode {
    ElemType data;
    struct StackNode *next;
} *LinkStack;
Copy the code

conclusion

To study data structure is to study how data is stored in memory. When you learn a new data structure, you can understand it easily by first understanding its definition and then thinking about its implementation and how to store it in memory.

Writing is not easy, after reading remember to like oh ~~~~

⭐⭐⭐⭐⭐

This article has included to my lot DayDayUP:github.com/RobodLee/DayDayUP warehouse, welcome Star

If you think the article is good, please give me a like, favorites, follow

Learn more programming knowledge, pay attention to the public number “R o B o D” :