Hello,everyone.
We will continue with the first section of the Data Structure and Algorithm.
In this lecture, we mainly introduce definitions of data structure especially the concept of abstract data type.
Firstly, what is a structure?
A structure mainly contains entities and relations between them.
Combine them as a whole and an organic structure is built.
There are three basic aspects in data structure.
The first one is the logical relationship, which means the mathematical logical relationship between entities.
On the logical relationship, there may be some good properties.
The properties help us to store and computer efficiently.
In conputer, we must store data in the main memory to express it reasonably. Data can be exchanged with cpu only in that way.
So we must organize the storage of data.
Besides, to solve problems, we mainly focus on using some arithmetic operations to get output for corresponding data.
In this way, operation or algorithm is a very important part of data structure.
They supplement each other and are indispensable to the others.
In different scenarios, we focus on different ones, but none of them is indispensable.
The logical structure of data structure can be mainly divided into linear and non-linear structures.
Linear structure is represented by linear table such as array and linked list.
There are some special data structures in linear table such as stack¡¢queue and string.
They will be introduced in the sections later on.
Non-linear structure can be divided into two categories mainly.
The first one is the tree structure.
The tree structure is a hierarchical organizational form.
And the graph structure is the structure with the least attributes.
The structure is made up of by the edges between nodes only.
In several structures, the structure with the most attributes is linear table. However, in fact, it is the simplest data structure.
There are some inclusion relation between these structures.
The whole book of data structure can be seen as organized by the logical structure of data structure.
We discuss about the logical properties of each structure first.
Then we discuss about some operations related with it. In other words, what kind of operations does it support?
To implement them, we must store the data We may have to store reasonably in the computer.
The storage structure of the data is a mapping from logic to its physical storage unit.
Physical storage unit must be stored in the memory, only in that way can we operate on the data structure.
Data must stay in the memory to communicate directly with the CPU.
The memory can seen as a linear structure which is encoded from low address to high address.
We can access units of memory directly without the process of search or traversal in the whole memory.
It mainly happens because we access any address in the memory with the same time.
Let's look at an example of storage structure.
For a linear table like this, it is an array with three elements.
After we get the starting address of the first element, we can calculate the starting address of the other elements directly.
The starting address of A[0] is 4
An integer elements take up 4 bytes.
So we know the starting address of the second and the third element is 8 and 12.
That is the process of mapping.
For every node we define in the data structure, the memory space we apply for must be continuous area.
If a pointer has been pointed into another extended content, it can be used to develop new space.
Storage structure of data structures can be divided into four categories such as sequence, links, index and hash.
Sequence structure corresponds to the form of array.
The continuous storage of the stucture can express the logically related order of it.
If the logically structure of your structure is not sequential, you can storage it in order after a sequential operation.
Link structure correspond to the form of linked list.
Link structure is very important in data structure especially for non-linear structure such as binary tree, tree and graph.
In most cases, it is very natural and convenient to compute by using link structure to express.
Index and hash are contents which are emphasised in data structure.
Index is to build a index table for the data, can we can find the corresponding storage address of the data efficiently by using the index table.
Hash is a special kind of index structure, it is also a kind of storage structure.
Hash is able to find the storage space of the key you are searching in the hash table quickly and then fetch the value of the key by map the key to the hash table.
There is a very important concept in data structure, that is abstract data type.
We look back at the three aspect of the data structure, that is logical structure¡¢ storage structure and computing.
The storage structure is proposed to implement and express in the computer.
For the user of the data structure, we mainly focus on the logical structure of it. In other ways, we focus on the logical property of it and what kind of operations it supports.
It doesn't matter how you store in the memory.
So we can define a series of abstract data type.
We only need to describe the logical structure and the operations it supports clearly.
Abstract data type develops with development of modularity and object-oriented methods.
With the support of abstract data type, our software can be built on the basis of data structure we have implemented before.
We can build more complex application system without concern of the implementation of the bottom layer.
When it is referenced by upper layer, we don't need to rewrite call form of the function, we only need to modify the reference of the header file.
Abstract data type mainly concerns about logic and operation these two aspects.
Logic is expressed in the data object, object contains the data and the relationship between data which can be understood as the relationship between entities.
Its manipulation embodies in data operations.
This function embodies as function in object-oriented language such as C++.
So we can describe logical structure first and then describe the definition of function, in that way we can describe the abstract data type well.
Let's have a look at a example.
For an abstract data type like stack, it is a linear structure firstly, it means its data is organized in order, from the first element to the last element.
One other property of the stack is that the operation of the data structure is constrained.
When we construct the data structure and operate on it , we are only allowed to operate on only one side of the structure.
It means data that comes to the stack in the end must be get out of the stack first.
Data that in the middle of the stack and data that comes to the stack first could't be access directly.
We must get or read element at the top of the stack.
The main operation of stack is read(pop out of the stack) and write(push in the stack).
After definiting the logical structure, we define the operation interface of it correspondingly.
We use the abstract class of C++ to describe it.
Firstly, the type of the element of the stack is class T.
We can assign the type of the element in the stack when we call it later on.
It can be integer, float or other complex types.
The operation of stack mainly contains push and pop and some auxiliary operations.
We can describe the main operation of the abstract data type of stack by using the definition of the C++ class.
It can be seen that our logical structure is implemented by using the description of an auxiliary language, we can't give it a formal representation in the definition of the class.
Let's think about how is the logical structure which is an important concept expressed in the abstract data type of data structure.
The example we show before has introduced it.
Whether is the abstract type the definition of class?
Can we express the abstract data type without using template to describe the ADT?
Thank you!