-
Thông tin
-
Hỏi đáp
Ngân hàng câu hỏi có đáp án ôn tập môn Toán rời rạc | trường Đại học Huế
1 giải thuật đệ quy:BT01. Tháp Hà Nội:BT02. Ước số chung lớn nhất.BT03. Tính giai thừa của 1 số.BT04. Bài toán mã đi tuần.Hướng dẫn giải bài toán mã đi tuần.Xây dựng bước đi cho quân mã.Kiểm tra tính hợp lệ của bước đi.2 Danh sách liên kết.BT06. Cài đặt danh sách liên kết đơn.BT07. Cài đặt danh sách liên kết kép.BT08. Cài đặt ngăn xếp – stack.Các khái niệm cơ bản về cây nhị phân.BT10. Cài đặt cây - duyệt cây theo thứ tự trước. Tài liệu giúp bạn tham khảo, ôn tập và đạt kết quả cao. Mời bạn đọc đón xem!
Toán rời rạc (ĐHH) 7 tài liệu
Đại học Huế 272 tài liệu
Ngân hàng câu hỏi có đáp án ôn tập môn Toán rời rạc | trường Đại học Huế
1 giải thuật đệ quy:BT01. Tháp Hà Nội:BT02. Ước số chung lớn nhất.BT03. Tính giai thừa của 1 số.BT04. Bài toán mã đi tuần.Hướng dẫn giải bài toán mã đi tuần.Xây dựng bước đi cho quân mã.Kiểm tra tính hợp lệ của bước đi.2 Danh sách liên kết.BT06. Cài đặt danh sách liên kết đơn.BT07. Cài đặt danh sách liên kết kép.BT08. Cài đặt ngăn xếp – stack.Các khái niệm cơ bản về cây nhị phân.BT10. Cài đặt cây - duyệt cây theo thứ tự trước. Tài liệu giúp bạn tham khảo, ôn tập và đạt kết quả cao. Mời bạn đọc đón xem!
Môn: Toán rời rạc (ĐHH) 7 tài liệu
Trường: Đại học Huế 272 tài liệu
Thông tin:
Tác giả:
Preview text:
lO M oARcPSD| 47110589 ĐẠI HỌC HUẾ
KHOA KỸ THUẬT VÀ CÔNG NGHỆ BÁO CÁO
ĐỒ ÁN CTDL & GT NĂM HỌC 2020-2021
Giảng viên hướng dẫn: Hồ Quốc Dũng Lớp: KHDL & TTNT Số phách
( Do hội đồng chấm thi gh ) i
Thừa Thiên Huế, ngày …tháng…năm..... lO M oARcPSD| 47110589 ĐẠI HỌC HUẾ
KHOA KỸ THUẬT VÀ CÔNG NGHỆ ( MẪU BÌA PHỤ ) BÁO CÁO
ĐỒ ÁN CTDL & GT NĂM HỌC 2020-2021
Giảng viên hướng dẫn: Hồ Quốc Dũng Lớp: KHDL & TTNT
Sinh viên thực hiện: Nguyễn Phước
( ký tên và ghi rõ họ tên ) Số phách
( Do hội đồng chấm thi gh ) i
Thừa Thiên Huế, ngày …tháng…năm..... lO M oARcPSD| 47110589 Mục Lục
KHOA KỸ THUẬT VÀ CÔNG NGHỆ..........................................................................................1
KHOA KỸ THUẬT VÀ CÔNG NGHỆ..........................................................................................2
1 giải thuật đệ quy:..........................................................................................................................5
BT01. Tháp Hà Nội:....................................................................................................................5
BT02. Ước số chung lớn nhất......................................................................................................6
BT03. Tính giai thừa của 1 số......................................................................................................7
BT04. Bài toán mã đi tuần...........................................................................................................8
Hướng dẫn giải bài toán mã đi tuần.........................................................................................8
Xây dựng bước đi cho quân mã.........................................................................................8
Kiểm tra tính hợp lệ của bước đi........................................................................................8
BT05. Bài toán 8 quân hậu........................................................................................................15
Giải bài toán xếp hậu bằng đệ quy..................................................................................15
2 Danh sách liên kết.......................................................................................................................20
BT06. Cài đặt danh sách liên kết đơn........................................................................................21
BT07. Cài đặt danh sách liên kết kép........................................................................................21
BT08. Cài đặt ngăn xếp – stack.................................................................................................22
BT09. Cài đặt hàng đợi – queue................................................................................................23
3 Cây..............................................................................................................................................25
Các khái niệm cơ bản về cây nhị phân...............................................................................25
BT10. Cài đặt cây - duyệt cây theo thứ tự
trước........................................................................26
BT11. Cài đặt cây - duyệt cây theo thứ tự sau...........................................................................27
4. Đồ Thị........................................................................................................................................29
Cấu trúc dữ liệu đồ thị (Graph).............................................................................................29
BT12. Cài đặt đồ thị vô hướng..................................................................................................30
.......................................................................................................................................................30
BT13. Cài đặt đồ thị có hướng...................................................................................................33
5. Sắp xếp và tìm kiếm..................................................................................................................35
BT14. Cài đặt thuật toán sắp xếp chọn.....................................................................................35
BT15. Cài đặt thuật toán sắp xếp chèn.....................................................................................36
BT16. Cài đặt thuật toán sắp xếp nổi bọt..................................................................................38
BT17. Cài đặt thuật toán sắp xếp nhanh - quick sort................................................................38
BT18. Cài đặt thuật toán heap sort...........................................................................................40
BT19. Cài đặt thuật toán sắp xếp trộn - merge sort..................................................................45
Đường dẫn link mã nguồn:
https://github.com/NguyenPhuoc1207/Do_An_CTDL
1 giải thuật đệ quy:
Một đối tượng được mô tả thông qua chính nó được gọi là mô tả đệ quy.
Một bài toán mang tính chất đệ quy khi nó có thể được phân rã thành các bài toán nhỏ hơn
nhưng mang cùng tính chất với bài toán ban đầu, các bài toán nhỏ lại được phân rã thành các
bài toán nhỏ hơn nữa theo cùng tính chất đó.
Trong đời sống, cũng thường xuyên thấy một số hiện tượng đệ quy, ví dụ như hai chiếc gương
đặt đối diện nhau, vòng xoắn ốc (trong vòng xoắn ốc có vòng xoắn ốc nhỏ hơn). lO M oARcPSD| 47110589
Đệ quy có ưu điểm là thuận lợi cho việc biểu diễn bài toán, đồng thời làm gọn chương trình. Tuy
nhiên cũng có nhược điểm, đó là không tối ưu về mặt thời gian (so với sử dụng vòng lặp), gây
tốn bộ nhớ và có thể tràn stack nếu không kiểm soát tốt độ sâu của đệ quy.
BT01. Tháp Hà Nội:
Cách giải bài toán tháp Hà Nội bằng đệ quy
Qui ước: Đặt tên 3 cột là A B C để tiện theo dõi. Yêu cầu bài toán là chuyển n
chiếc đĩa từ cột A sang cột C Cách giải •
Đầu tiên ta lấy cột C làm cọc trung gian. Chuyển n-1 chiếc đĩa sang cột B. •
Ta chuyển chiếc đĩa lớn nhất sang cột C •
Lấy cột A làm cột trung gian chuyển n-1 chiếc đĩa từ cột B sang cột C Code python: lO M oARcPSD| 47110589 Code R:
BT02. Ước số chung lớn nhất
Một phương pháp đơn giản đề tìm USCLN của a và b là duyệt từ số nhỏ hơn trong 2 số
a và b cho đến 1, khi gặp số nào đó mà cả a và b đều chia hết cho nó thì đó chính là
USCLN của a và b. Tuy vậy phương pháp này chưa phải là hiệu quả nhất.
Vào thế kỷ 3 TCN, nhà toán học Euclid (phiên âm tiếng Việt là Ơ-clit) đã phát minh ra
một giải thuật tìm USCLN của hai số nguyên dương rất hiệu quả được gọi là giải thuật
Euclid. Cụ thể về ý tưởng của bài toán, giả sử a lớn hơn b, khi đó việc tính UCSLN của lO M oARcPSD| 47110589
a và b sẽ được đưa về bài toán tính USCLN của a mod b và b vì USCLN(a, b) = USCLN(a mod b, b).
Khi đã tìm được USCLN thì việc tìm BSCNN của hai số nguyên dương a và b khá đơn
giản. Khi đó BSCNN(a, b) = (a * b) / UCSLN(a, b). Code python: Code R:
BT03. Tính giai thừa của 1 số Code python: Code R: lO M oARcPSD| 47110589
BT04. Bài toán mã đi tuần
Hướng dẫn giải bài toán mã đi tuần
Xây dựng bước đi cho quân mã
Giọi x,y là độ dài bước đi trên các trục Oxy. Một bước đi hợp lệ của quân mã sẽ
như sau: |x| + |y| = 3 ( Với x,y > 0).
Khi đó ở một vị trí bất kì quân mã có có 8 đường có thể di chuyển. Chưa xét đến
bước đi đó có hợp lệ hay không.
Các bước đi đó là: ( -2, -1), ( -2, 1), ( -1, -2), ( -1, 2), ( 1, -2), ( 1, 2), ( 2, -1), ( 2, 1)
Để đơn giản ta sẽ tạo hay mảng X[], Y[] để chứa các giá trị trên. Với mỗi X[i],
Y[i] sẽ là một cách di chuyển của quân mã(0 ≤i≤ 7 ).
Kiểm tra tính hợp lệ của bước đi
Ta sẽ dùng một mảng hai chiều A[n*n] để lưu vị trí của từng ô trong bàn cờ. Tất
cả mảng đều khởi tạo giá trị là 0( quân mã chưa đi qua).
Giọi x,y là vị trí hiện tại của quân mã, thì vị trí tiếp theo mà quân mã đi sẽ có
dạng x+X[i], y+Y[i]. Một vị trí được gọi là hợp lệ thì sẽ thỏa mãn tính chất sau: • 0 ≤ x+X[i]≤ n-1. • 0 ≤ x+X[i]≤ n-1.
Nếu bước đi đó là bước đi đúng thì ta sẽ lưu thứ tự của bước đi đó vào mảng A[ x+X[i], y+Y[i] ]. Code python: lO M oARcPSD| 47110589 Code R: library(purrr) library(dplyr) library(tidyverse)
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Knight offsets i.e. the possible movements of a knight from the current location lO M oARcPSD| 47110589
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knight_offsets <- matrix(c( 1, 2, 2, 1, -2, 1, -1, 2, 2, -1, 1, -2, -1, -2, -2, -1 ), ncol = 2, byrow = TRUE)
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#' Recurisvely calculate moves for a knight to complete a tour #'
#' @param this_move proposed next move. 2 element numeric vector of (row, col)
#' position at which to place the knight next
#' @param moves list of vectors. Each vector is length=2 and indicates the
#' row/column locations of the knight's tour so far lO M oARcPSD| 47110589
#' @param visited 8x8 logical matrix which indicates whether or not a square has been
#' visited by the knight already. When called by the user, this matrix #' must only contain FALSE
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
move_knight <- function(this_move, moves, visited) {
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~ # Mark the move as visited
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~
moves <- append(moves, list(this_move))
visited[this_move[1] + (this_move[2] - 1)*8] <- TRUE
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~ # termination if all visited
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~ if (all(visited)) { return(moves) } lO M oARcPSD| 47110589
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Find all possible moves from this position
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~
next_move <- cbind(knight_offsets[,1] + this_move[1], knight_offsets[,2] + this_move[2])
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~
# keep only moves that remain on the board
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~
on_board <- next_move[,1] %in% 1:8 & next_move[,2] %in% 1:8
next_move <- next_move[on_board,,drop=FALSE]
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Keep only moves that target a location that has not yet been visited
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~
not_yet_visited <- !visited[next_move] next_move <-
next_move[not_yet_visited,, drop = FALSE] lO M oARcPSD| 47110589
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Recurse over every possible next move
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~
for (i in seq_len(nrow(next_move))) { res <-
move_knight(next_move[i,, drop = FALSE], moves, visited) if (!is.nul (res)) { return(res) } } NULL }
system.time({ moves <- move_knight(c(4, 8), moves = list(), visited = matrix(FALSE, 8, 8)) })
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#' Convert results to a data.frame for ggplot
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ lO M oARcPSD| 47110589
moves_df <- as.data.frame(do.call(rbind, moves))
moves_df <- set_names(moves_df, c('x', 'y'))
moves_df$idx <- 1:nrow(moves_df)
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ # Plot the knight's tour
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ggplot(moves_df, aes(x, y)) +
geom_tile(aes(fill=as.logical((x+y)%%2)), colour = 'black') +
geom_path(alpha = 0.7, linetype = 1, size = 0.25) +
geom_text(aes(label = idx)) + scale_fil _manual(values = c('grey70',
'white')) + theme_void() + theme(legend.position = 'none') +
coord_equal() + labs( title = "A knight's tour in #RStats" ) lO M oARcPSD| 47110589
BT05. Bài toán 8 quân hậu
Giải bài toán xếp hậu bằng đệ quy •
Để tiện trình bày ta dùng biến i để đánh dấu các hàng từ trên xuống (
1 đến n). Dùng biến j để đánh dấu các cột từ trái sang phải ( 1 đến n ); •
Các phần tử nằm trên cùng hàng có chỉ số hàng bằng nhau; •
Các phần tử nằm trên cùng cột có chỉ số cột bằng nhau; •
Để tiện cho việc in kết quả ra thì ta chỉ in ra chỉ số các cột tuần tự theo
các hàng từ trên xuống. •
Điều kiện để đặt một quân hậu đúng chỗ là không có 2 trên cùng một
cột ( chỉ số cột khác nhau). Không có 2 quân hậu nào cùng ở trên một đường chéo. Ý tưởng: •
Đầu tiên ta đặt quân hậu thứ nhất vào các cột trên hàng 1 ( có n cách đặt ). •
Thử đặt quân hậu 2 vào từng cột ở hàng 2 sao cho không bị quân hậu
1 khống chế. Với mỗi vị trí của quân hậu này ta lại thử đặt quân hậu
thứ ba vào các cột sao cho không bị các quân hậu trước khống chế. •
Sau khi đặt xong quân hậu thứ tám thì in ra một cách đặt. Code python: """The n queens puzzle.""" class NQueens:
"""Generate all valid solutions for the n queens puzzle""" def __init__(self, size): lO M oARcPSD| 47110589
# Store the puzzle (problem) size and the number of valid solutions
self.size = size self.solutions = 0 self.solve() def solve(self):
"""Solve the n queens puzzle and print the number of solutions"""
positions = [-1] * self.size self.put_queen(positions, 0)
print("Found", self.solutions, "solutions.")
def put_queen(self, positions, target_row): """
Try to place a queen on target_row by checking all N possible cases.
If a valid place is found the function calls itself trying to place a queen
on the next row until all N queens are placed on the NxN board. """
# Base (stop) case - all N rows are occupied if target_row == self.size:
self.show_full_board(positions) #
self.show_short_board(positions) self.solutions += 1 else:
# For all N columns positions try to place a queen
for column in range(self.size): # Reject all invalid
positions if self.check_place(positions,
target_row, column): positions[target_row] =
column self.put_queen(positions, target_row + 1)
def check_place(self, positions, ocuppied_rows, column): """
Check if a given position is under attack from any of
the previously placed queens (check column and diagonal positions) """
for i in range(ocuppied_rows): if
positions[i] == column or \ positions[i] - i ==
column - ocuppied_rows or \ positions[i] + i == column + ocuppied_rows: return False return True
def show_full_board(self, positions): """Show the full NxN board""" for row in range(self.size): line = "" for column in range(self.size): if positions[row] == column: line += "Q " else: line += ". " lO M oARcPSD| 47110589 print(line) print("\n")
def show_short_board(self, positions): """
Show the queens positions on the board in compressed form, each
number represent the occupied column position in the corresponding row. """ line = "" for i in range(self.size): line += str(positions[i]) + " " print(line) def main():
"""Initialize and solve the n queens puzzle""" NQueens(8) if __name__ == "__main__":
# execute only if run as a script main() Code R: library(tidyverse)
#-----------------------------------------------------------------------------
#' Try and place a Queen given a vector of positions of the current Queens #'
#' This function calls itself recursively for every valid placement of the #' next queen. #'
#' @param queens A vector of integers representing the column
placement #' of queens so far. The index within this list #'
is the row, and the value is the column.
#' To generate all solutions, pass in an empty vector (the default) #'
#' e.g. queens = c(1, 4, 7) corresponds to queens placed at c(1, 1), c(2, 4) and #' c(3, 7) #' #'
#' --------------------------------- #' | | | | | | | | |
#' --------------------------------- #' | | | | | | | | |
#' --------------------------------- #' | | | | | | | | |
#' --------------------------------- #' | | | | | | | | |
#' ---------------------------------
#' | | | | | | | Q | | 3rd row, 7th column
#' ---------------------------------
#' | | | | Q | | | | | 2nd row, 4th column
#' --------------------------------- lO M oARcPSD| 47110589
#' | Q | | | | | | | | 1st row, 1st column
#' --------------------------------#' #' #' #'
#' @return a list where each element is a vector of 8 integers
#' i.e. a solution to the 8 queens problem #------------------------------------------------------------
----------------place_queen <- function(queens=c(1)) {
#--------------------------------------------------------------------------
# If there are 8 queens placed, then this must be a solution.
#--------------------------------------------------------------------------
if (length(queens) == 8) { return(list(queens)) }
#--------------------------------------------------------------------------
# Figure out where a queen can be placed in the next row.
# Drop all columns that have already been taken - since we
# can't place a queen below an existing queen
#--------------------------------------------------------------------------
possible_placements <- setdiff(1:8, queens)
#--------------------------------------------------------------------------
# For each queen already on the board, find the diagonal #
positions that it can see in this row.
#--------------------------------------------------------------------------
diag_offsets <- seq.int(length(queens), 1) diags <- c(queens +
diag_offsets, queens - diag_offsets) diags <- diags[diags > 0 & diags < 9]
#---------------------------------------------------------------------------
# Drop these diagonal columns from possible placements
#--------------------------------------------------------------------------
possible_placements <- setdiff(possible_placements, diags)
#---------------------------------------------------------------------------
# For each possible placement, try and place a queen
#--------------------------------------------------------------------------
possible_placements %>% map(~place_queen(c(queens, .x)))
%>% keep(~length(.x) > 0) %>% flatten() }
#----------------------------------------------------------------------------#' Plot a single solution
#' @param queens a vector of 8 integers giving the column positions of 8 queens
#------------------------------------------------------------------------ ----
plot_single_8queens <- function(queens, title = NULL) {
queens_df <- tibble(cols = queens, rows=1:8) board_df <- lO M oARcPSD| 47110589
expand.grid(cols = 1:8, rows = 1:8) %>% mutate(check = (cols + rows) %%2 == 1)
p <- ggplot(queens_df, aes(rows, cols)) +
geom_tile(data=board_df, aes(fill=check), colour='black') +
geom_text(label='\u2655', family="Arial Unicode MS", size = 8) +
theme_void() + coord_equal() +
scale_fill_manual(values = c('TRUE'='white', 'FALSE'='grey70')) + theme( legend.position = 'none' ) if (is.null(title)) {
p <- p + labs(title = paste("Queens:", deparse(as.numeric(queens)))) } else {
p <- p + labs(title = title) } }
#----------------------------------------------------------------------------#
Start with no queens placed and generate all solutions.
#----------------------------------------------------------------------------solutions <- place_queen() v=1:8 f=function(q){L=length(q)
if(L==8){q}else{flatten(map(setdiff(v,c(q,q+L:1,q- L:1)),~f(c(q,.))))}}
s=data.frame(c=unlist(f(c())),r=v,x=rep(1:92,e=8),z=3)
b=mutate(crossing(c=v,r=v),z=(c+r)%%2) g=geom_tile
ggplot(s,aes(r,c,fill=z))+g(d=b)+g()+facet_wrap(~x) lO M oARcPSD| 47110589
2 Danh sách liên kết
Danh sách liên kết đơn(Single linked list) là ví dụ tốt nhất và đơn giản nhất về cấu trúc dữ
liệu động sử dụng con trỏ để cài đặt. Do đó, kiến thức con trỏ là rất quan trọng để hiểu cách
danh sách liên kết hoạt động, vì vậy nếu bạn chưa có kiến thức về con trỏ thì bạn nên học
về con trỏ trước. Bạn cũng cần hiểu một chút về cấp phát bộ nhớ động. Để đơn giản và dễ
hiểu, phần nội dung cài đặt danh sách liên kết của bài này sẽ chỉ trình bày về 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.
Cách loại danh sách liên kết: •
Danh sách liên kết đơn- Linked List. •
Danh sách liên kết đôi - Doubly Linked List. •
Danh sách liên kết vòng - Circular Linked List.
BT06. Cài đặt danh sách liên kết đơn
Danh sách liên kết đơn(Single linked list) là ví dụ tốt nhất và đơn giản nhất
về cấu trúc dữ liệu động sử dụng con trỏ để cài đặt. Do đó, kiến thức con trỏ là
rất quan trọng để hiểu cách danh sách liên kết hoạt động, vì vậy nếu bạn chưa
có kiến thức về con trỏ thì bạn nên học về con trỏ trước. Bạn cũng cần hiểu một
chút về cấp phát bộ nhớ động. Để đơn giản và dễ hiểu, phần nội dung cài đặt
danh sách liên kết của bài viết này sẽ chỉ trình bày về danh sách liên kết đơn. Code python: class Node:
# Function to initialise the node object
def __init__(self, data): self.data = data # Assign data
self.next = None # Initialize next as null
# Linked List class contains a Node object class LinkedList:
# Function to initialize head def __init__(self): self.head = None
# Code execution starts here if __name__=='__main__': # Start with the empty list llist = LinkedList() lO M oARcPSD| 47110589
llist.head = Node(1) second = Node(2) third =
Node(3) llist.head.next = second; # Link first node with
second second.next = third; # Link second node with the third node Code R:
lst <- list() # creates an empty (length zero) list
lst[[1]] <- 3 # automagically extends the lst lst[[2]] <- 4 # ditto lst
elist <- list(vec=1:4,df=data.frame(a=1:3, b=4:6),mat=matrix(1:4, nrow=2), name="pks") elist[["vec"]]
BT07. Cài đặt danh sách liên kết kép Code python: Code R:
lst <- list(1, 2, 3, 4, 5) # a list of 5 items
lst <- vector("list", 10000) # 10000 NULLs lst[[1]] <- 1
lst[[10000]] <- 10000 # lst now contains 1, NULL, ..., NULL, 10000 lst
BT08. Cài đặt ngăn xếp – stack Code python: