preface
This article is equivalent to a note arrangement of my previous study of data structure. You are welcome to comment and point out the shortcomings, which will be updated in the future.
catalogue
2, Logical characteristics of linear table
3, One of the storage structures of linear table -- sequential storage structure
3.1 related concepts of sequence table
3.2 code implementation of sequence table (java)
1, Definition of linear table
To learn linear tables, first you know what linear tables are
definition:
A linear table is a finite sequence of data elements with the same characteristics
Graphic related concepts
be careful:
-
The number n of data elements is defined as the length of the table
-
When n=0, it is called an empty table
-
Record the non empty linear table (n > 0) as: (a1,a2....a(n))
-
The data element a (I) (1 < = I < = n) here is just an abstract symbol, and its specific meaning can be different in different cases
II. Logical characteristics of linear table
-
In a non empty linear table, there is only one start node a1, which has no direct forward trend, but only one direct successor a2
-
There is only one terminal node an, which has no direct successor, but only one direct forward trend a(n-1).
-
The other internal nodes AI (2 < = I < = n-1) have only one direct forward trend a(i-1) and one direct successor a(i+1).
-
Linear table is a typical linear structure.
3, One of the storage structures of linear table -- sequential storage structure
3.1 related concepts of sequence table
Definition of sequential storage:
A storage structure in which logically adjacent data elements are stored in physically adjacent storage units. In short, logically adjacent and physically adjacent
Features:
The storage location where the first element a1 of the linear table is located is called the * * start location * * or * * base address of the linear table**
If the storage address is discontinuous, it cannot be a sequential storage structure.
As long as you know the storage location of one element, you can calculate the storage location of other elements
Logical association is represented by physical location adjacency
Any element can be accessed randomly
3.2 code implementation of sequence table (java)
package com.studySelf.Linearlist02.Sqlist;
import java.util.Iterator;
/**
* @author wang
* @packageName com.studySelf.Linearlist02.Sqlist
* @className List
* @date 2021/11/29 19:45
*/
public class Seqlist<T> extends Object implements Iterable<T>{
/**An array of storage elements*/
private Object[] element;
/**Record the number of elements in the current sequence table*/
private int n;
//Construction method
public Seqlist(int capacity) {
//Initialize array
this.element = new Object[capacity];
//Initialization length
this.n = 0;
}
/**Set a linear table as an empty table*/
public void clear() {
this.n = 0;
}
/**Judge whether the current linear table is empty*/
public boolean isEmpty() {
return n==0;
}
/**Gets the length of the linear table*/
public int length() {
return n;
}
/**Gets the element at the specified location*/
public T get(int i) {
return (T) element[i];
}
/**Get all elements*/
public void getAll() {
for(int i = 0;i<n;i++) {
System.out.println(element[i]);
}
}
/**Add element to linear table*/
public void insert(T t) {
//If the array has reached the upper limit, it is expanded
if(n==element.length) {
//The expansion capacity is twice that of the original array
resize(2*element.length);
}
element[n++] = t;
}
/**Inserts an element at the specified i index*/
public void insert(int i,T t) {
//If the array has reached the upper limit, it is expanded
if(n==element.length) {
//The expansion capacity is twice that of the original array
resize(2*element.length);
}
//Move the element at index i and its subsequent elements backward one bit in turn
for(int index = n;index>i;index--) {
element[index] = element[index-1];
}
element[i] = t;
//Element plus one
n++;
}
/**Deletes the element at the specified location i and returns the element*/
public T remove(int i) {
//Record the value at index i
T current = (T) element[i];
//The elements behind index i can be moved back one bit in turn
for(int index = i;index < n-1 ;index++) {
element[index] = element[index+1];
}
//Number of elements - 1
n--;
if(n>0 && n<element.length/4) {
resize(element.length/2);
}
return current;
}
/**Method of changing capacity*/
public void resize(int newSize) {
//Record original array
T[] temp = (T[]) element;
//Create a new array
element = new Object[newSize];
//Pass the contents of the old array to the new array
for(int i = 0;i<n;i++) {
element[i] = temp[i];
}
}
/**Find where the t element first appears*/
public int indexOf(T t) {
for(int i =0;i<n;i++) {
if(element[i].equals(t)) {
return i;
}
}
return -1;
}
@Override
public Iterator<T> iterator() {
return new LIterator<T>();
}
private class LIterator<T> implements Iterator<T> {
private int cur ;
public LIterator() {
//Traverse from 0
this.cur = 0;
}
@Override
//This method indicates whether the next element is included
public boolean hasNext() {
//When the current element index is less than the number of elements, that is, the index is equal to or greater than n, it proves that there are no elements in the sequence table and returns false
return cur<n;
}
@Override
//The next element is the next element in the array
public T next() {
return (T)element[cur++];
}
}
}
Test:
public class SeqListTest {
public static void main(String[] args) {
Seqlist<String> sl = new Seqlist<>(2);
sl.insert("Liu Xiang");
sl.insert("Su Bingtian");
sl.insert("Zhang Sanfeng");
sl.insert(1,"Ferrari");
sl.insert(1,"Lamborghini");
// sl.getAll();
System.out.println("Third:" +sl.get(2));
for(String s : sl) {
System.out.println(s);
}
}
}
/*
Output results
Third: Ferrari
Liu Xiang
Lamborghini
Ferrari
Su Bingtian
Zhang Sanfeng
*/Time complexity analysis of the sequence table
get(i): no matter how large the number of data elements N is, the corresponding elements can be obtained only once eles[i], so the time complexity is O(1);
Insert (int i, t, t): every time you insert, you need to move the elements behind I. with the increase of the number of elements N, the more elements are moved, and the time complexity is O(n);
remove(int i): every time you delete, you need to move the elements behind the I position once. With the increase of the amount of data N, more elements are moved, and the time complexity is O(n);
Because the bottom layer of the sequence table is implemented by an array, and the length of the array is fixed, the container expansion operation is involved in the process of operation. In this way, the time complexity of the sequence table in the use process is not linear. At some nodes that need to be expanded, the time will increase sharply, especially the more elements, the more obvious the problem is
3.3 summary of sequence table
Features:
1. Use the storage location of data elements to represent the front and back relationship between adjacent data elements in the linear table, that is, the logical structure of the linear table is consistent with the storage structure
2. When accessing the linear table, you can quickly calculate the storage address of any element. Therefore, it can be roughly considered that the time spent accessing each element is equal
Advantages and disadvantages of sequence table:
advantage:
1. High storage density (storage capacity of node itself / storage capacity of node structure)
2. Any element in the table can be accessed at random
Disadvantages:
When inserting or deleting an element, a large number of elements need to be moved
Waste of storage space
It belongs to static storage form, and the number of data elements cannot be expanded freely