What is data structure

preface

It’s a pain in the neck. It says nothing.

An understanding of data structures

First of all, there doesn’t seem to be a uniform, standard answer to data structures in terms of definition. I searched several books and picked out a definition that I thought was easy to understand:

A data structure is a way of storing and organizing data in a computer. In general, carefully chosen data structures can lead to optimal efficiency algorithms.

If you’re not familiar with data structures, can you read a definition and understand it? If you can understand, I admire you, I am not, but now because of contact with more things, listen to more, read can also understand. I think for novices, we should first let them understand, and then look at the official definition after we have our own understanding, the effect will be better, anyway I think so. Let me explain data structures with an example from my life: How do I place books on a shelf? In other words, there are some shelves and a bunch of books. How do you put them on the shelves? In other words, you have a bunch of data, you’re given some storage space, how are you going to store that data? This is an unscientific question because you don’t know what a bookshelf looks like. It could be any one of the pictures below.

So you know, when someone asks you how a piece of data is organized, it really has something to do with the size of the data. Different scale of the problem, it is not the same difficulty to deal with. What’s the difficulty? The difficulty lies not in how you put it, but in the fact that the book is for doing things, so the placement of the book is directly related to two operations:

Operation 1: new book how to insert operation 2: how to find a specified book

Method one: I don’t know how do you think, my first feeling is put casually, literally put a benefit is that new book how to insert, the operation is very simple, put any free, the easiest way is to put all the books one by one put it next to each other, So, where are all the new books put where is free, So easy! It’s easy to put, but what about the second operation, how do I find it? That would be a terrible thing… Dead tired you! When dead tired, if only a small bookcase, also tired not die, but if it is above the third such books, and then you can imagine, all the books are put casually, then someone ask you, this book has a book in the city, but without the book, but you forgot to have, then how can you be sure it is there? You have to read every book from cover to cover before you can sigh and say… Alas, sorry, there is no such book.

Method 2: Do we have a slightly smarter solution? Is how to let me find books to find convenient? The second method, is in accordance with the alphabetic order of the title of the pinyin emissions, with the alphabetic order after the search is much more convenient. One of the smartest ways to do binary lookup is to find what binary lookup is: Now for example, a long line of books in front of you, then we can find a book called “data structure” of an S at the beginning of the book, let me from the first row in the middle of the find a book out to see the first letter of the title of it, if say “discrete mathematics”, begin with L, that we know, S in the back of the L, so “discrete mathematics” in front of the book I wouldn’t have it, I find range narrowed the half, since L find back, and then find the half of the middle, such as finding a book is a “web crawler”, starting with W, it S in the middle of the L and W, “web crawler” at the back of the book I need not tube, so I find and narrowed down by half, and so on, every time I can find, and then compared to the middle, I’ll soon narrow it down to one book, and I’ll know if it’s there or not. This method is much smarter than the previous method, and it solves the lookup problem very well. But again, the question is, how do you insert the new book? It becomes a new headache. For example, I just bought A book called The True Story of AH Q, which starts with an A, uh… Oh, no, we’d have to move almost all the books from one to the next until there was a gap in front of us to insert the new ones, which seems to be a pain too.

Method 3: So how to find a way to have the best of both worlds? Let’s think about how to place books in the library. If we go to the library and look for “Data Structure”, how to look for it? You can’t start from the first book, nor can you just touch a book in the middle. The book in the library usually divides according to the category of the book, for example we have social science, literature, art, science, engineering, and so on, and then engineering may be divided into a bit more detail, for example our computer may be divided into the following engineering, what advantage does this kind of cent have? Divide bookcase into a few areas, each area quickly specify put some categories of books, in each category, emissions in alphabetical order according to the title of the pinyin, so no matter what I do in every class operation, the end, the size of the book much smaller, compared with the size of the library, is one kind of I, whether lookup or inserts, is very convenient. Search, that is, before binary search, we first set a category, and then do binary search in a small range of a class, you can find the book we want to find faster. If it’s an insert, it’s going to be a category first, a binary search to figure out where it should be inserted, and then it’s going to move the space, but it’s still going to be a lot less than the number of books we started with.

Now the question arises:

Problem 1: How to allocate space? Question 2: How many categories should there be?

We are divided into various categories of books, its collection is not the same, you are unified to give it points… Or how many bookshelves are there in each category? This is also a headache, I am too difficult, if you give more bookshelves, there will always be some empty space waste, if you give a small bookshelf, when the new book has to constantly add new cabinets, very annoying. Don’t want to points of the problem of fine and classification, if you score is coarser, so there will be a lot of the same class book, that your workload will be very big, if want to reduce the workload, it is better to category of smaller, but the category a fine, there will be side effects, there are too many categories, more than the amount of a books, is also a trouble.

These questions are meant to illustrate:

The effectiveness of the problem solving approach is directly related to how the data is organized

So when I introduce the organization of data structures, there are actually two concepts: First, about the logical structure of data objects , for example, we started to think of bookshelf as simple a strip, so a layer of shelf, and then all of the books are one by one to put, in addition to a book first tail, each front and back of this book is only a book, if every book has a number of words, so this is a number corresponding to a book, So this is a one-to-one structure, and we call it a linear structure.

Another way to organize books is the third way mentioned above, which is to classify books first. If I give each class a number, then there are many books in the number of a category, so this is a one-to-many logical structure, and this structure is called a tree.

For libraries, suppose we also count things like: Have the people who bought this book, bought this book also bought other what book, then, is really a book corresponds to a lot of people, and one corresponding to a lot of books, this is a many-to-many, is a complex network, so the network corresponding logical structure is called figure Second, about the object of physical storage structure In addition to the logical structure, We also have the data objects and the physical storage structures in the computer, the logical structures that we’re talking about in the memory of the machine how do we put them, do we put them in a row or do we put them in separate places? In other words, do YOU store it in an array, or do you store it in a linked list? This is the physical storage structure.

This article

The above is my understanding of data structure, I think it should be said comprehensive, if not comprehensive also does not matter, after learning to continue to add. Did you get anything? Then pay attention to my original wechat public account [Like a leading sage] and read my article for the first time

The original is not easy to

I like to spend a lot of time writing some basic thinking because I know that beginners in the beginning of programming, when the confusion, the pain of the puzzle, indescribable. I want to help the pain of the fans when “I” out of the predicament, because I walked too long, if you have read the article at this time, please detour, do not spray, this article is not suitable for you. If you are the “me” who is enduring the pain of the fans, if you have a hint of enlightenment, it is also the value of this article, welcome to the road.

The public,

Can appreciate my article, can incidentally pay attention to the public number, appreciate each other, why lonely: