1. Định nghĩa mảng
Tính chất của mảng có thể thêm, bớt phần tử trong mảng và có độ phức tạp về thời gian là $O(n)$, đây là một nhược điểm tuy nhiên ưu điểm là ta có thể truy cập bất kỳ phần tử nào trong mảng với độ phức tạp về thời gian là hằng số.
Chú ý: Mảng rất giống với list trong python. nhưng có một số điểm khác nhau như sau
List trong Python là một tập hợp các mục có thể chứa các phần tử của nhiều kiểu dữ liệu, có thể là số, ký tự, v.v.
Dưới đây là sự khác biệt giữa list và mảng trong Python:
| List | Mảng |
|---|---|
| Có thể bao gồm các phần tử thuộc các kiểu dữ liệu khác nhau | Chỉ bao gồm các phần tử thuộc cùng một kiểu dữ liệu |
| Không cần nhập thư viện | Cần nhập thư viện |
| Không thể xử lý trực tiếp các phép toán số học | Có thể xử lý trực tiếp các phép toán số học |
| Ưu tiên cho chuỗi các mục dữ liệu ngắn hơn | Ưu tiên cho chuỗi các mục dữ liệu dài hơn |
| Tính linh hoạt cao hơn cho phép dễ dàng sửa đổi (thêm, xóa) dữ liệu | Tính linh hoạt kém hơn kể từ khi sửa đổi (thêm, xóa) dữ liệu |
| Sử dụng bộ nhớ lớn hơn | Tương đối nhỏ gọn hơn về kích thước bộ nhớ |
2. Mảng động (nguồn funix)
Ưu điểm: Tránh lãng phí bộ nhớ khi phải khai báo mảng có kích thước lớn ngay từ đầu.
Nhược điểm: Phải thực hiện thêm thao tác copy phần tử mỗi khi thay đổi kích thước. Một số thời gian thực hiện thao tác không còn là hằng số nữa.
Mảng động: kiểu dữ liệu trừu tượng với các thao tác sau (tối thiểu):
- Get(i): Trả về phần tử tại chỉ mục i
- Set(i, val): Thiết lập phần tử i với giá trị val
- PushBack(val): Thêm giá trị vào cuối mảng
- Remove(i): Xóa phần tử tại vị trí i
- Size(): Số lượng của các phần tử
class DArray():
def __init__(self):
self.size = 0 #so phan tu dang su dung trong array
self.capacity = 1 #kich thuoc cua array
self.array = [None]*self.capacity #array la mang duoc cap phat dong
def __len__(self):
return self.size
def get(self, i): #do phuc tap là O(1)
if i < 0 or i >= self.size:
return IndexError('i is out of bounds !')
return self.array[i]
def set(self, i, val): #do phuc tap là O(1)
if i < 0 or i >= self.size:
return IndexError('i is out of bounds !')
self.array[i] = val
def pushback(self, val): #do phuc tap là O(n)
if self.size == self.capacity:
new_arr = [None]*(2*self.capacity)
for i in range(self.size):
new_arr[i] = self.array[i]
self.array = new_arr
self.capacity = 2*self.capacity
self.array[self.size] = val
self.size += 1
def remove(self, i): #do phuc tap là O(n)
if i < 0 or i >= self.size:
return IndexError('i is out of bounds !')
if i == self.size - 1:
self.array = None
self.size -= 1
return
for j in range(i,self.size - 1):
self.array[j] = self.array[j+1]
self.array[self.size-1] = None
self.size -= 1
def Size(self): #do phuc tap là O(1)
return self.size
3. Danh sách liên kết đơn
Danh sách liên kết đơn là một tập hợp các Node được phân bố động, được sắp xếp theo cách sao cho mỗi Node chứa một giá trị (Data) và một con trỏ (Next). Con trỏ sẽ trỏ đến phần tử kế tiếp của danh sách liên kết đó. Nếu con trỏ mà trỏ tới NULL, nghĩa là đó là phần tử cuối cùng của linked list.
Ta có thể thực hiện một số thao tác sau trên danh sách liên kết đơn
- PushFront(Key): Thêm vào phía trước
- TopFront(Key): Trả về phần tử phía trước
- PopFront(): Xóa phần tử phía trước
- PushBack(Key): Thêm phần tử phía sau
- TopBack(Key): Trả về phần tử phía sau
- PopBack(): Xóa phần tử phía sau
- Find(Key): Kiểm tra key có trong danh sách hay không?
- Erase(Key): Xóa key trong danh sách
- Empty(): Kiểm tra danh sách có trống hay không?
- AddBefore(Node, Key): Thêm key trước node
- AddAfter(Node, Key): Thêm key sau node
Độ phức tạp về thời gian cho một số thao tác phổ biến
Đầu tiên chúng ta tạo một nút với khóa là 26, sau đó cho con trỏ liên kết (next) của node mới trỏ vào node đầu tiên trong danh sách hiện tại và cập nhật head point trỏ đến nút mới tạo. Độ phức tạp là $O(1).$
b. PopFront(Key)
Đầu tiên ta cập nhật con trỏ head, sau đó loại bỏ node đầu, thao tác này là $O(1)$
c. PushBack(Key)
Đầu tiên chúng ta tạo một nút với khóa là 26, sau đó dò từ đầu đến đến cuối danh sách và thêm node vừa tạo ở đó. Vì vậy thao tác này mất $O(n).$
PushBack(Key) (with tail): Chúng ta tạo một node mới, sau đó cho con trỏ liên kết (next) của tail hiện tại trỏ tới node mới và cập nhật lại node tail. Vậy độ phức tạp giảm xuống còn $O(1)$
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
def print_llist(self):
val = self.head
while val is not None:
print(val.data, end = ',')
val = val.next
def pushfront(self, data_new):
node_new = Node(data_new)
node_new.next = self.head
self.head = node_new
if self.tail is None:
self.tail = self.head
def topfront(self):
return self.head.data
def popfront(self):
if self.head is None:
raise IndexError('empty list')
self.head = self.head.next
if self.head is None:
self.tail = None
def pushback_no_tail(self, data_new):
node_new = Node(data_new)
if self.head is None:
self.head = self.tail = node_new
return
last = self.head
while last.next is not None:
last = last.next
last.next = self.tail = node_new
def pushback_with_tail(self, data_new):
node_new = Node(data_new)
if self.head is None:
self.head = self.tail = node_new
else:
self.tail.next = self.tail = node_new
def topback_no_tail(self):
if self.tail is None:
raise IndexError('empty list')
last = self.head
while last.next is not None:
last = last.next
return last.data
def topback_with_tail(self):
return self.tail.data
def popback(self):
if self.head is None:
raise IndexError('empty list')
if self.head == self.tail:
self.head = self.tail = None
else:
last = self.head
while last.next.next is not None:
last = last.next
last.next = None
self.tail = last
def find(self, key):
p = self.head
while p is not None:
if key == p.data:
return 'YES'
p = p.next
return 'NO'
def erase(self, key):
while self.head is not None and self.head.data == key:
if self.head == self.tail:
self.head.data = self.tail.data = None
else:
self.head = self.head.next
temp = self.head
if temp is not None:
while temp.next is not None:
if temp.next.data == self.tail.data == key:
self.tail = temp
temp.next = None
elif temp.next.data == key:
temp.next = temp.next.next
else:
temp = temp.next
def empty(self):
if self.head is None:
return 'YES'
else:
return 'NO'
def add_after(self, node, key):
node_new = Node(key)
node_new.next = node.next
node.next = node_new
if self.tail is node:
self.tail = node_new
def add_before(self, node, key):
node_new = Node(key)
if self.head is node:
node_new.next = self.head
self.head = node_new
return
temp = self.head
while temp.next is not None:
if temp.next is node:
node_new.next = temp.next
temp.next = node_new
return
temp = temp.next
llist = LinkedList()để giảm độ phức tạp của pop back và add before xuống chúng ta sử dụng danh sách liên kết đôi.
