A linear table is a table in which data elements are arranged like a line . The strict definition of linear table is A finite sequence of data elements with the same characteristics . Its characteristics are 3 individual ：
Unlike collections , Elements with the same value can appear in the linear table .
The logical structure of a linear table is generally expressed as ( a 0 , a 1 , ⋯ , a n − 1 ) (a_0,a_1,\cdots,a_{n-1}) (a0,a1,⋯,an−1), use n ( n ≥ 0 ) n(n\geq0) n(n≥0) Represents the length of the linear table （ That is, the number of elements in the linear table ）. When n = 0 n=0 n=0 when , Indicates that the linear table is an empty table , Does not contain any data elements .
Logical characteristics of linear tables ： There is at most one precursor element per element , At most, there is only one subsequent element .
Count According to the Yes like ： D = { a i ∣ 0 ≤ i ≤ n − 1 , n ≥ 0 , a i by E class type } Count According to the Turn off system ： r = { < a i , a i + 1 > ∣ a i , a i + 1 ∈ D , i = 0 , ⋯ , n − 2 } The base Ben shipment count ： fromlist(a) ： root According to the Count Group a Of whole Ministry element plain build state Line sex surface add(e) ： take element plain e add Add To Line sex surface Of At the end of the tail insert(i,e) ： insert Enter into element plain e do by order Number i Of element plain delete(i) ： Delete except order Number by i Of element plain getelem(i) ： a take order Number by i Of element plain setelem(i,e) ： set up Set up order Number i Of element plain value by e getno(e) ： seek Line sex surface in The first One individual value by e Of element plain Of order Number getsize() ： a take Line sex surface Of Long degree display() ： transport Out Line sex surface Of the Yes element plain \begin{aligned} & Data objects ：D=\{a_i|0\leq i\leq n-1,n\geq0,a_i by E type \} \\ & Data relation ：r=\{<a_i,a_{i+1}>|a_i,a_{i+1}\in D,i=0,\cdots,n-2\} \\ & Basic operation ：\\ &\quad \text{fromlist(a)}： According to the array a Establish a linear table for all elements of \\ &\quad \text{add(e)}： Put the element e Add to the end of the linear table \\ &\quad \text{insert(i,e)}： Insert elements e As serial number i The elements of \\ &\quad \text{delete(i)}： The deletion number is i The elements of \\ &\quad \text{getelem(i)}： Get sequence number as i The elements of \\ &\quad \text{setelem(i,e)}： Set sequence number i The element value of is e \\ &\quad \text{getno(e)}： Find the first value in the linear table as e The sequence number of the element \\ &\quad \text{getsize()}： Get the length of the linear table \\ &\quad \text{display()}： Output all elements of the linear table \\ \end{aligned} Count According to the Yes like ：D={ ai∣0≤i≤n−1,n≥0,ai by E class type } Count According to the Turn off system ：r={ <ai,ai+1>∣ai,ai+1∈D,i=0,⋯,n−2} The base Ben shipment count ：fromlist(a)： root According to the Count Group a Of whole Ministry element plain build state Line sex surface add(e)： take element plain e add Add To Line sex surface Of At the end of the tail insert(i,e)： insert Enter into element plain e do by order Number i Of element plain delete(i)： Delete except order Number by i Of element plain getelem(i)： a take order Number by i Of element plain setelem(i,e)： set up Set up order Number i Of element plain value by egetno(e)： seek Line sex surface in The first One individual value by e Of element plain Of order Number getsize()： a take Line sex surface Of Long degree display()： transport Out Line sex surface Of the Yes element plain
Linear tables have two storage structures ： Sequential storage and Chain store , This article will mainly explain sequential storage .
The sequential storage of linear table is to store all the elements in the linear table into a continuous storage space in the memory according to their logical order . The sequential storage structure of a linear table is called The order sheet .
Next we will adopt Python To implement the sequence table . The sequence table usually has a maximum capacity capacity, When the number of elements to be stored is greater than capacity when , We can expand the sequence table （ For example capacity Tripled ）.
class SqList:
def __init__(self, capacity):
self.capacity = capacity # The maximum capacity
self.data = [None] * self.capacity # For storing data
self.size = 0 # The number of elements in the sequence table
We can create one resize Function is used to modify the maximum capacity of a linear table ：
def resize(self, newcapacity):
assert newcapacity >= 0
if newcapacity >= self.capacity:
self.data = self.data + [None] * (newcapacity - self.capacity)
else:
self.data = self.data[:newcapacity]
self.capacity = newcapacity
Given list a, We need to establish the corresponding sequence table through this list .
def fromlist(self, a):
for i in range(len(a)):
# Expand the capacity when overflow occurs 2 times
if self.size == self.capacity:
self.resize(self.size * 2)
# because self.size It's from 0 Start incremental
self.data[self.size] = a[i]
self.size += 1
The time complexity is O ( n ) \mathcal{O}(n) O(n), among n n n Indicates the number of elements in the sequence table .
def add(self, e):
# Prevent overflow
if self.size == self.capacity:
self.resize(self.size * 2)
self.data[self.size] = e
self.size += 1
To be in position i i i Insert element at e e e, We need to self.data[i, i+1, ..., n-1] Each element of is moved back one bit .
def insert(self, i, e):
assert 0 <= i <= self.size
if self.size == self.capacity:
self.resize(self.size * 2)
for j in range(self.size, i, -1):
self.data[j] = self.data[j - 1]
self.data[i] = e
self.size += 1
Average time complexity ： O ( n ) \mathcal{O}(n) O(n).
To delete a location i i i The element of , We need to self.data[i+1, ..., n-1] Each element of moves forward one bit .
def delete(self, i):
assert 0 <= i < self.size
for j in range(i, self.size - 1):
self.data[j] = self.data[j + 1]
self.size -= 1
# Adaptive capacity reduction to save space
if self.size < self.capacity / 2:
self.resize(self.capacity / 2)
Average time complexity ： O ( n ) \mathcal{O}(n) O(n).
def __getitem__(self, i):
assert 0 <= i < self.size
return self.data[i]
def __setitem__(self, i, x):
assert 0 <= i < self.size
self.data[i] = x
def getno(self, e):
for i in range(self.size):
if self.data[i] == e:
return i
# No return found -1
return -1
def getsize(self):
return self.size
def display(self):
print(*self.data[:self.size])
sqlist = SqList(10)
sqlist.fromlist(list(range(10)))
sqlist.display()
# 0 1 2 3 4 5 6 7 8 9
sqlist.add(33)
sqlist.insert(3, 19)
sqlist.delete(0)
sqlist.display()
# 1 2 19 3 4 5 6 7 8 9 33
sqlist[10] = 3
print(sqlist[1])
# 2
print(sqlist.getno(3))
# 3
print(sqlist.getsize())
# 11
sqlist.display()
# 1 2 19 3 4 5 6 7 8 9 3
That is, if the original sequence table is ( 4 , 3 , 2 , 1 ) (4,3,2,1) (4,3,2,1), The sequence table after turning should be ( 1 , 2 , 3 , 4 ) (1,2,3,4) (1,2,3,4).
def reverse(sqlist):
i, j = 0, sqlist.getsize() - 1
while i < j:
sqlist[i], sqlist[j] = sqlist[j], sqlist[i]
i += 1
j -= 1
sqlist = SqList(5)
sqlist.fromlist(list(range(5)))
sqlist.display()
# 0 1 2 3 4
reverse(sqlist)
sqlist.display()
# 4 3 2 1 0
Time complexity O ( n ) \mathcal{O}(n) O(n), Spatial complexity O ( 1 ) \mathcal{O}(1) O(1).
Design an algorithm from position i i i Start deleting the following k k k Elements （ Include i i i）. For example, set L = ( 1 , 2 , 3 , 4 , 5 ) , i = 1 , k = 2 L=(1,2,3,4,5),i=1,k=2 L=(1,2,3,4,5),i=1,k=2, Then, after the operation L = ( 1 , 4 , 5 ) L=(1,4,5) L=(1,4,5).
Obviously, there needs to be i ≥ 0 , k ≥ 1 i\geq0,k\geq1 i≥0,k≥1, The index of the last element deleted is i + k − 1 i+k-1 i+k−1, Need to meet 0 ≤ i + k − 1 ≤ n − 1 0\leq i+k-1\leq n-1 0≤i+k−1≤n−1, namely 1 ≤ i + k ≤ n 1\leq i+k\leq n 1≤i+k≤n.
def delete_k(sqlist, i, k):
assert i >= 0 and k >= 1 and 1 <= i + k <= sqlist.getsize()
for j in range(i + k, sqlist.getsize()):
sqlist[j - k] = sqlist[j]
sqlist.size -= k
sqlist = SqList(5)
sqlist.fromlist(list(range(5)))
sqlist.display()
# 0 1 2 3 4
delete_k(sqlist, 1, 2)
sqlist.display()
# 0 3 4
Time complexity O ( n ) \mathcal{O}(n) O(n).
An ordered table is a linear table arranged by increasing or decreasing element values or attribute values . An ordered table is a subset of a linear table . An ordered table is a sequential storage structure of an ordered table . For ordered tables , The order of its elements can be used to improve the efficiency of related algorithms , Two way merge is a classical algorithm of ordered table .
Consider two progressive ordered tables A A A and B B B, Designing an algorithm will A A A and B B B Merge together and form a new incremental order table C C C.
We can set two pointers i , j i,j i,j, use i i i Traverse A A A, use j j j Traverse B B B. At the beginning , i = j = 0 i=j=0 i=j=0. Every comparison i i i and j j j The size of the element referred to , Add smaller to C C C in , And move the pointer pointing to the smaller one to the right , Keep repeating this operation .
def merge(A, B):
C = SqList(A.capacity + B.capacity)
i = j = 0
while i < A.getsize() and j < B.getsize():
if A[i] < B[j]:
C.add(A[i])
i += 1
else:
C.add(B[j])
j += 1
# if i,j Not reaching the end at the same time , Then there must be a sequence table with residual elements , At this point, just add all these elements C Then you can
while i < A.getsize():
C.add(A[i])
i += 1
while j < B.getsize():
C.add(B[j])
j += 1
return C
A = SqList(5)
A.fromlist(list(range(1, 11, 2)))
B = SqList(5)
B.fromlist(list(range(2, 11, 2)))
A.display()
# 1 3 5 7 9
B.display()
# 2 4 6 8 10
C = merge(A, B)
C.display()
# 1 2 3 4 5 6 7 8 9 10
class SqList:
def __init__(self, capacity):
self.capacity = capacity
self.data = [None] * self.capacity
self.size = 0
def resize(self, newcapacity):
assert newcapacity >= 0
if newcapacity >= self.capacity:
self.data = self.data + [None] * (newcapacity - self.capacity)
else:
self.data = self.data[:newcapacity]
self.capacity = newcapacity
def fromlist(self, a):
for i in range(len(a)):
if self.size == self.capacity:
self.resize(self.size * 2)
self.data[self.size] = a[i]
self.size += 1
def add(self, e):
if self.size == self.capacity:
self.resize(self.size * 2)
self.data[self.size] = e
self.size += 1
def insert(self, i, e):
assert 0 <= i <= self.size
if self.size == self.capacity:
self.resize(self.size * 2)
for j in range(self.size, i, -1):
self.data[j] = self.data[j - 1]
self.data[i] = e
self.size += 1
def delete(self, i):
assert 0 <= i < self.size
for j in range(i, self.size - 1):
self.data[j] = self.data[j + 1]
self.size -= 1
if self.size < self.capacity / 2:
self.resize(self.capacity / 2)
def __getitem__(self, i):
assert 0 <= i < self.size
return self.data[i]
def __setitem__(self, i, x):
assert 0 <= i < self.size
self.data[i] = x
def getno(self, e):
for i in range(self.size):
if self.data[i] == e:
return i
return -1
def getsize(self):
return self.size
def display(self):
print(*self.data[:self.size])
Pythonpyecharts real-time drawing custom visual longitude and latitude thermal map
Catalog background be based
2022 Summer Practice (Django Tutorial Learning Record) (5th week 4) P58 content review and knowledge sorting
P58 Content Review and Knowled
