Hello everyone
Data Structures and Algorithms
In this lecture, we continue to learn chapter two
contents of linear list
Today we are learning sequential list
sequential list
Also commonly referred to as a vector
which is always use an array to implement
The linear list which is always discussed
its elements are of the same type
It also means the length of them
In implement of our sequential list
We reserve this nature
So we can use a one-dimensional array
to store these data elements
Its storage structure
retains the logical structure fully
Thus when we need to find
the position of any element
we can locate it very quickly
This subscript position
which this element points to
So it is a random storage
Data Structure
OK. Let's see
in the sequential list
A memory address of an element's
A formula
When knowing such an array of variables
We should be able to know
Its a start address
That means the elements address
whose index is 0
We also know
the storage length of each element
I-th data
that is our starting address subscript 0
We then add the length of the array elements c
Then multiplied by i
Then we get the corresponding
such a position of the element
Now let's look at the class definition of sequential list
It is basically inherited
Our linear list's class definition template
There are some difference between them
First, we want to implement an array
Then this array
is predetermined a maximum length
It may be greater than the length of
Our current number of elements in the data
The current number of elements
Of course, is also very important as an indicator
Only the subscript 0 to the current number of elements
such length of interval
we are logically valid
This interval
in the current length
The length of the current element
to the max length
is our largest storage array length
That section
is such storage space that is reserved
In addition
There is a current element position
It is also very important
In linear list
We often do the position fix first, then the operation
In our sequential list
the current position is often expressed as
our current subscript value
Other interfaces
is just like our linear list
In fact,in the data structure
ADT's definition
has such an advantage
After we defined a linear list's united
classic template interface
Then realizing for the sequential
or the linked list's
interfaces are the same
Therefore,building the upper layer structure's
applications
the reserved can be totally the same
This approach
just need to modify the
header file's references
Now we look at the implementation of sequential list
Here we discuss its insert and delete operations
For other operations
On our course website
There is source code package
Please think first
Then look at the code
For insertion of sequential list
We want that after
insertion, such a logical structure
can still has a complete expression
in its storage structure
So we need to
move down the corresponding data elements
after this current one of insertion position
to leave out a space
so we will be able to bring this current element
into our vacancies
Now we look at the sequential list insertion algorithm
The first thing is that we have a current position
and a value that will be inserted
to be passed in as a parameter
And then we need to determine
the current number of elements inside the list
Whether it is already reached
the maximum storage limit
If it is
then the list is already full
We can not insert any element
Also we need to judge
the position of the current location of insert
Whether it is in our list's
valid number of logic unit
If it is beyond our current
valid sequence number of elements inside the list
such a range
We also are not allowed the insertion
In both cases
Returns are false
If the current position is a valid one
and this table is also not full
then we can insert
Then from the tail
to the current location
we do a cycle
Sequentially starting from the end of the table
we move the elements of this end of the table
to the back
Then this element above
will just fill into the position
it removed
Operating until the current location
The current position is also empty
Then we can fill
the inserted element values
Overall,
for our linear list
its size is increased by 1
And the insert is successful, returns true
Now we look at delete of sequential list
Delete is similar
It is the reverse operation of the insertion
In order to maintain this logic sequence
after the current element is deleted
we choose a element next from the current one
until the end of the list
These elements
will be moved up one by one
Then move
until the end of our list
This current linear list
reduces the number of elements by 1
Now look at the deletion algorithm of sequential list
First, the incoming subscript position p to be removed
We need first to check
the current list's length
Whether it is greater than 0
If it is less than or equal to 0
that is an empty list
and can not be deleted
Then check the subscript p
whether it is in the sequential list
within a reasonable range of elements
If the index exceeds the scope of this
it also returns false
For legal subscript range p
Then we start from this current p
Fill the elements behind it
one by one
until the end of the list
The actual length of the list then
Reduces 1
And after deleted
The sequential list also maintained
Stored-closed characteristic
That means its storage
retains its logical sequential relationship
OK. Now let's see
complexity of sequential list insertion and deletion algorithms
In sequential list inside
for insert delete operation
the main thing is to move one of the elements
For insertion algorithm
from the last position
to the current position to be inserted into
We move down following the order
This move was done
N-i times
For delete
started from the current index position i
we move the elements behind
forward sequentially
until the end of the sequential list
The number of elements to be moved is n-i-1
Assuming at position i
Probability of insertion and deletion
Are pi and pi '
then the average move number of insert
is the sum from 0 to n
The summation of the items
is (n-i) pi
This is because for the position we inserted
apart from the current 0 to n-1 several elements
the positions before can all be inserted
In fact, this position after n-1
can also be inserted
So the sum total is n +1 times of summation
For deletion algorithm
its average number of moves
is N-i-1 multiplied by pi '
From 0 to n-1 the sum is total of n times
Because for deleting it
the current array inside
Exactly has n elements
We can only do delete operation to
the current n elements
If probability of insertion and deletion
for each position on the sequential table
are equal
That means, pi = 1 / (n +1)
And substituting pi '= 1 / n
into the equation
you can calculate under the average case
if there is a uniform probability distribution
for the insertion algorithm
the number of elements it needs to move it
is n / 2
For the deletion algorithm
the number of elements it needs to move
is (n-1)/2
they are the same order of magnitude,namely that large O(n)
That means the time costs are large O(n)
Finally, I left two Questions
In sequential list
for insert and delete operations
What issues need to be considered for each
Also what are the advantages and disadvantages of the sequential list
Thank you