Tài liệu Bồi dưỡng học sinh giỏi tin học thpt chuyên đề cấu trúc dữ liệu nâng cao

I. ĐẶT VẤN ĐỀ Khi giải một bài toán, ta cần định nghĩa tập hợp dữ liệu để biểu diễn dữ liệu vào và kết quả ra. Việc lựa chọn này tùy thuộc vào vấn đề cần giải quyết và những thao tác sẽ tiến hành trên dữ liệu. Có những thuật toán chỉ thích ứng với một cách tổ chức dữ liệu nhất định, nếu sử dụng những cách tổ chức dữ liệu khác sẽ kém hiệu quả hoặc không thể thực hiện được. Chính vì vậy khi tìm kiếm thuật toán giải quyết vấn đề không tách rời bước xây dựng cấu trúc dữ liệu. Chuyên đề “Cấu trúc dữ liệu nâng cao ” sẽ trình bày một số kiểu dữ liệu nâng cao thường được sử dụng. II. NỘI DUNG 1. Danh sách (List) Danh sách là tập sắp thứ tự các phần tử cùng kiểu. 1.1. Tổ chức danh sách 1.1.1. Tổ chức danh sách bằng mảng một chiều Khi cài đặt bằng mảng một chiều ta sử dụng một biến nguyên N để lưu số phần tử hiện có trong danh sách. * Các thao tác với danh sách: - Chèn phần tử vào danh sách: Nếu muốn chèn một phần tử V vào danh sách tại vị trí P, ta dồn tất cả các vị trí từ P đến vị trí N về sau một vị trí, sau đó đặt V vào vị trí P, tăng số lượng phần tử lên một đơn vị. - Xóa phần tử khỏi danh sách: Nếu muốn xóa phần tử P vẫn giữ nguyên thứ tự, ta dồn tất cả các phần tử từ vị trí P+1 tới vị trí N lên trước một vị trí, giảm số lượng phần tử đi một đơn vị. 1.1.2. Tổ chức danh sách bằng liên kết nối đơn Danh sách liên kết nối đơn gồm các nút được nối với nhau theo một chiều. Mỗi nút là một bản ghi gồm hai trường: một trường chứa giá trị và một trường chứa liên kết tới nút kế tiếp. Nút đầu tiên được gọi là chốt của danh sách, để duyệt danh sách ta bắt đầu từ chốt, dựa vào trường liên kết để đi tiếp cho tới khi gặp giá trị đặc biệt thì dừng lại. * Các thao tác với danh sách: - Chèn phần tử vào danh sách: Nếu muốn chèn một nút chứa giá trị V vào danh sách tại vị trí nút P, ta tạo ra một nút mới chứa giá trị V, sau đó tìm nút q đứng trước nút p, nếu thấy thì chỉnh lại liên kết: q liên kết đến nút mới, nút mới liên kết tới p, nếu không tìm thấy thì P là chốt, ta chỉnh lại liên kết nút mới liên kết tới chốt (cũ) và chốt được đặt lại bằng nút mới. - Xóa phần tử khỏi danh sách: Nếu muốn xóa nút P khỏi danh sách liên kết, ta tìm nút q đứng trước nút p trong danh sách, nếu thấy thì chỉnh lại liên kết: q liên kết đến nút liền sau p; nếu không thấy thì có nghĩa p là nút chốt, ta chỉ cần đặt lại chốt bằng nút đứng kế tiếp chốt (cũ) trong danh sách; Sau đó giải phóng bọ nhớ cấp phát cho nút p. 1 1.1.3. Tổ chức danh sách bằng liên kết nối kép Danh sách liên kết nối kép gồm các nút được nối với nhau theo hai chiều. Mỗi nút là một bản ghi gồm ba trường: trường thứ nhất chứa giá trị, trường thứ hai chứa liên kết tới nút kế tiếp (Next), trường thứ ba chứa liên kết tới nút liền trước (Prev). Danh sách nối kép có hai chốt: Nút đầu tiên được gọi là First, nút cuối cùng được gọi là Last. Để duyệt danh sách ta có hai cách: Hoặc là bắt đầu từ First, cách duyệt như danh sách liên kết nối đơn; Hoặc bắt đầu từ Last, dựa vào liên kết Prev để đi sang nút liền trước, đến khi duyệt đến giá trị đặc biệt (duyệt qua nút đầu) thì dừng lại Các thao tác với danh sách tương tự như danh sách liên kết nối đơn. 2. Hàng đợi và ngăn xếp 2.1. Ngăn xếp (Stack) Là danh sách được tổ chức theo kiểu LIFO (“vào sau, ra trước”). Trong ngăn xếp, các phần tử thêm vào sau được lấy ra khỏi ngăn xếp trước. Số lượng các phần tử trong ngăn xếp gọi là chiều cao của ngăn xếp phản ánh vị trí phần tử cuối vừa nạp vào, do biến top quản lý. 2.1.1. Tổ chức ngăn xếp 2.1.1.1. Tổ chức ngăn xếp bằng mảng - Ngăn xếp bị tràn khi bổ sung vào mà số phần tử vượt quá số lượng tối đa của mảng (mảng đầy) - Ngăn xếp rỗng khi số lượng phần tử thực sự trong mảng bằng không - Việc bổ sung phần tử vào ngăn xếp tương đương với thêm phần tử vào cuối mảng - Việc loại bỏ một phàn tử khỏi ngăn xếp tương đương với việc loại bỏ phần tử ở cuối mảng 2.1.1.2. Tổ chức ngăn xếp bằng danh sách liên kết nối đơn kiểu LIFO Khi cài đặt ngăn xếp bằng danh sách liên kết nối đơn kiểu LIFO, thì ngăn xếp bị tràn vùng không gian nhớ dùng cho các biến động không còn đủ để thêm một phần tử mới. Tuy nhiên, việc kiểm tra này sẽ rất khó vì nó phụ thuộc vào máy tính và ngôn ngữ lập trình, vì vậy khi tổ chức ngăn xếp bằng liên kết nối đơn kiểu LIFO. 2.2. Hàng đợi (Queue) Là danh sách được tổ chức theo kiểu FIFO (“vào trước, ra trước”). Phần tử được nạp vào (đẩy vào) ở vị trí cuối hàng đợi (biến rear hoặc last quản lý vị trí này), phần tử được lấy ra tại vị trí đầu hàng đợi (biến front hoặc first quản lý vị trí này). 2.2.1. Tổ chức hàng đợi 2.2.1.1. Tổ chức hàng đợi bằng mảng Khi mô tả hàng đợi bằng mảng, ta dùng front lưu chỉ số phần tử đầu của hàng đợi, còn rear lưu chỉ số cuối của hàng đợi, khởi tạo hàng đợi rỗng: front:=1 và rear:=0; - Để thêm một phần tử vào hàng đợi, ta tăng rear lên 1 và đưa gía trị đó vào phần tử thứ rear 2 - Để loại phần tử khỏi hàng đợi, ta tăng rear lên 1 và đưa giá trị đó vào phần tử thứ rear - Để loại một phần tử khỏi hàng đợi, ta lấy giá trị ở vị trí front và tăng front lên 1 - Hàng đợi đầy khi rear tăng lên hết khoảng chỉ số của mảng - Hàng đợi rỗng khi front > rear 2.2.1.2. Tổ chức hàng đợi bằng danh sách liên kết nối đơn kiểu FIFO Tương tự như tổ chức ngăn xếp bằng danh sách liên kết nối đơn kiểu LIFO, ta cũng không kiểm tra hàng đợi tràn khi tổ chức bằng danh sách liên kết nối đơn kiểu FIFO. [1] 3. Cây (Tree) Cây là tập hợp các nút, giữa các nút có quan hệ phân cấp (thường gọi là quan hệ “cha, con”). Có thể cài đặt cây bằng mảng hoặc bằng cấu trúc liên kết. Một dạng quan trọng của cây là cây nhị phân. Biểu diễn danh sách bằng cây nhị phân là cách tổ chức dữ liệu thường xuyên cập nhật có hiệu quả của bài toán thống kê động. Cây nhị phân (Binary Tree). Mỗi nút trên cây có tối đa 2 nhánh con gọi là cây con trái và cây con phải của nút đó. Cây nhị phân đầy đủ là cây nhị phân mà mọi nút nhánh đều có đúng 2 nhánh con. Cây nhị phân hoàn chỉnh là cây nhị phân đầy đủ mà các lá ở cùng độ sâu. Từ cây nhị phân hoàn chỉnh bỏ đi một số lá thì gọi là gần hoàn chỉnh. Cây nhị phân tìm kiếm (BST). Cây nhị phân tìm kiếm là cây nhị phân mà mỗi nút chứa một khóa. Khóa của mỗi nút không nhỏ hơn mọi khóa trong nhánh con trái và không lớn hơn mọi khóa trong nhánh con phải. [2] 4. Hàng đợi ưu tiên (Priority queue) Hàng đợi ưu tiên là một kiểu danh sách mà mỗi phần tử được gán với một mức độ ưu tiên giúp quá trình xử lý chúng theo quan hệ nào đó giữa chúng. Hàng đợi ưu tiên thuận tiện cho việc lấy ra phần tử được ưu tiên nhất khi dữ liệu luôn luôn cập nhật. Heap (hay là Binary Heap) là một hàng đợi ưu tiên thông dụng nhất. Heap thường có dạng một cây nhị phân gần hoàn chỉnh. Có hai loại: MaxHeap và MinHeap. Trong MaxHeap, mỗi nút lưu một phần tử của danh sách có độ ưu tiên không nhỏ hơn độ ưu tiên của các phần tử nằm ở hai nhánh con của nó. Ngược lại, trong MinHeap, mỗi nút lưu một phần tử của danh sách có độ ưu tiên không lớn hơn độ ưu tiên của các phần tử nằm ở hai nhánh con của nó. 3 5. Cây khoảng (Interval Tree) Cây khoảng là cây có quan hệ thứ tự bộ phận dùng lưu trữ các khoảng cơ sở. Cây khoảng cho phép cập nhật, tìm kiếm các khoảng rất hiệu quả. Có thể cài đặt cây khoảng như một Heap. Ví dụ trong bài toán quản lí một dãy số nguyên A={a0 , a2 , …, an-1 } mà dãy số này thường xuyên được cập nhật, chúng ta có thể tổ chức cây khoảng (interval tree) như sau: Trên cây nhị phân mỗi nút gán cho một đoạn chứa một số phần tử của dãy. Nút gốc là đoạn [a0 ; an-1 ] chứa mọi phần tử của dãy, tiếp theo là hai nút con của gốc tương ứng với hai đoạn liên tiếp: nút con trái của gốc được gán cho đoạn [a0 ; (a0 +an-1 ) div 2], nút con phải được gán cho đoạn [1+(a0 +an-1 ) div 2; an-1 ]….Cuối cùng tại các nút lá, mỗi lá quản lý một đoạn có điểm đầu và điểm cuối trùng nhau, nghĩa là chứa đúng một số nguyên của dãy. Cây khoảng thường dùng để xử lý dữ liệu trên các khoảng mà các khoảng luôn luôn cập nhật thay đổi. Một số bài toán như: tìm các khoảng chứa một số k cho trước hoặc tìm số lớn nhất, nhỏ nhất chứa trong một khoảng nào đó trong quá trình cập nhật các khoảng. 6. Cây chỉ mục (BIT - Binary indexed tree) Binary Indexed Trees hiện nay thường dùng lưu trữ các tần số và tích luỹ tần số (cộng dồn tần số) của dữ liệu thường xuyên cập nhật trong các bảng. Nó đáp ứng được các yêu cầu sau của n đối tượng: (1). Yêu cầu 1: cập nhật (lấy ra, nạp vào, sửa đổi giá trị…) đối tượng i? (2). Yêu cầu 2: Tính tổng giá trị (hoặc tần số) các đối tượng từ i tới k. [2] 7. Bài tập minh họa Bài 1. Sắp tô pô Cho N công việc, mỗi công việc i phải làm trước một số công việc nào đó trong N công việc này. Hãy xếp lịch thực hiện đủ N công việc. Dữ liệu vào từ file XL.IN: Dòng đầu là số nguyên dương N. Các dòng sau thể hiện quan hệ thứ tự bộ phận: đầu dòng là số i, các số tiếp theo là ji1 , ji2 ,.., jis thể hiện công việc i phải làm trước các công việc ji1 , ji2 ,.., jis 4 Kết quả ghi ra file XL.OUT một dòng N số hiệu công việc được lần lượt làm. Ví dụ XL.IN XL.OUT 10 1 2 2 4 3 5 4 6 5 8 6 3 7 5 9 4 3 10 8 9 10 Gợi ý. Thuật toán sắp tô pô (sắp sao cho bảo đảm thứ tự bộ phận) dùng ngăn xếp như sau: Xây dựng một đồ thị mỗi đỉnh là một công việc. Công việc i làm trước công việc j thì có cung nối từ đỉnh i tới đỉnh j. Các đỉnh không có cung đi tới gọi là đỉnh 0 (tương ứng là công việc không bị phụ thuộc công việc nào). Sau đó tiến hành các bước sau: + Tìm một đỉnh bậc 0 nạp vào Stack. + Thực hiện vòng lặp: Trong khi Stack chưa rỗng thì: - Lấy một phần tử i ở đỉnh Stack, đánh dấu đã xét i, xác nhận mảng một chiều T có thêm phần tử mới là i. - Xoá các cung đi ra từ i - Nạp đỉnh 0 mới vào Stack. + Nếu số lượng phần tử trong mảng T bằng N thì dãy T[1], T[2],..., T[N] là một cách sắp N phần tử đã cho bảo đảm thứ tự bộ phận. Chương trình. uses crt; const max = 100; fi = 'xl.in'; fo = 'xl.out'; type m1 = array[1..max] of integer; m2 = array[1..max,1..max] of integer; var t, d, s : m1; a : m2; n, sl, top : byte; g : text; procedure nhap; begin {Lấy giá trị cho biến N và mảng A(N,N)} end; function bac_0(i: byte): boolean; begin {Xác định đỉnh i có là đỉnh bậc 0 hay không} end; function dinhbac0: byte; begin {Dựa vào hàm bac_0, tìm một đỉnh bậc 0 chưa đánh dấu. end; procedure nap(i: byte); begin {Nạp phần tử i vào stack} end; function lay: byte; begin {Lấy một phần tử ở đỉnh stack ra khỏi stack} end; procedure hien; var i: byte; 5 begin if sl0 do begin i := lay; inc(sl); t[sl]:= i; d[i] := 1; xoa(i); pt := dinhbac0; if pt>0 then nap(pt); end; hien; end; procedure khoitri; begin {Khởi trị các mảng t, s, d và các biến top, sl} end; BEGIN khoitri; nhap; assign(g,fo);rewrite(g); sap_topo; close(g); END. Bài 2. Biểu thức hậu tố Các biểu thức toán học chứa các phép tính cộng (+), trừ (-), nhân (*), chia (/), dấu ngoặc trái: '(' và dấu ngoặc phải: ')' cùng các toán hạng được viết dưới dạng biểu thức trung tố. Ví dụ : T="7.2*8.5(2+3.4)". Biểu thức trung tố khi tính toán phải tuân theo các quy tắc ưu tiên phép tính và ưu tiên thứ tự thực hiện phép tính : + thực hiện trong ngoặc trước, ngoài ngoặc sau. + cùng trong ngoặc thì thực hiện nhân chia trước, cộng trừ sau. Những quy tắc này khó xử lý khi biểu thức có nhiều ngoặc, vì vậy người ta xây dựng một cách biểu diễn khác để máy tính dễ thực hiện tính biểu thức hơn: đó là cách viết biểu thức dưới dạng hậu tố (trong nó không có dấu ngoặc) H="7.2 8.5 * 2 3.4 + - " Việc tính biểu thức này rất dễ dàng bằng sử dụng ngăn xếp (Stack). 6 Hãy viết chương trình chuyển biểu thức trung tố thành biểu thức hậu tố, sau đó tính giá trị của biểu thức. Dữ liệu vào từ tệp “BL4.INP” gồm một số dòng, mỗi dòng là một biểu thức trung tố. Kết quả ra ghi vào tệp “BL4.OUT”, mỗi dòng là một kết quả tương ứng với một dòng của tệp dữ liệu vào và có dạng sau: Biểu thức trung tố  Biểu thức hậu tố = Giá trị biểu thức. Ví dụ: 7.2*8.5-(2+3.4)  7.2 8.5 * 2 3.4 + - = 54.4 Gợi ý. Quy tắc chuyển từ biểu thức trung tố thành biểu thức hậu tố: • Gán biểu thức hậu tố bằng xâu rỗng H :=””(xâu rỗng) • Đọc biểu thức trung tố T từ trái qua phải: + Nếu gặp dấu mở ngoặc '(' thì nạp nó vào ngăn xếp. + Nếu gặp dấu đóng ngoặc ')' thì lần lượt lấy các phần tử ở đỉnh ngăn xếp nối vào đuôi biểu thức hậu tố cho đến khi gặp dấu mở ngoặc nằm trong ngăn xếp thì lấy dấu mở ngoặc này khỏi ngăn xếp bỏ đi ( không nối vào H ). +Nếu gặp dấu phép toán thì so phép toán này với phép toán ở đỉnh ngăn xếp (nếu có); nếu phép toán này ưu tiên ít hơn phép toán ở đỉnh ngăn xếp thì lấy phép toán ở đỉnh ngăn xếp nối vào đuôi H, đồng thời nạp phép toán này vào đỉnh ngăn xếp. Trong trường hợp ngược lại hoặc trong trường hợp đỉnh ngăn xếp không có phép toán thì nạp phép toán này vào ngăn xếp. + Nếu gặp toán hạng thì nối toán hạng vào đuôi H. • Sau khi đọc xong biểu thức trung tố T, lần lượt lấy nốt các phần tử ở đỉnh ngăn xếp nối vào đuôi H cho đến khi ngăn xếp rỗng hoặc chỉ còn 1 dấu đóng ngoặc '('. Tính biểu thức hậu tố. Máy tính có thể dễ dàng tính biểu thức hậu tố theo quy tắc sau : Đọc biểu thức hậu tố từ đầu về cuối (từ trái sang phải): • Nếu gặp toán hạng thì cho toán hạng vào ngăn xếp. • Nếu gặp dấu phép toán thì lấy khỏi ngăn xếp toán hạng thứ nhất và toán hạng thứ hai, sau đó đem toán hạng thứ hai thực hiện phép toán với toán hạng thứ nhất, kết quả thu được lại cho vào ngăn xếp. • Số cuối cùng còn lại trong ngăn xếp chính là giá trị biểu thức cần tính. Chương trình uses crt; const max = 255; fi ='Bl4.inp'; fo ='Bl4.out'; type stack = array[1..max] of char; var s : stack; t,h : string; 7 i,top : byte; f1,f2 : text; procedure nap(ch : char); begin if top0 then begin h := h+ s[top]+' '; dec(top); end; end; function tl( ch : char) : byte; begin case ch of '(' : tl := 0; '+','-' : tl := 1; '*','/' : tl := 2; end; end; procedure chuyen; var i : byte; function chuyenso : string; var so : string; begin so := ''; while t[i] in ['0'..'9','.'] do begin so := so+t[i]; inc(i); end; chuyenso := so; dec(i); end; begin h := ''; i := 1; top := 0; while i<= length(t) do begin 8 case t[i] of '(' : nap(t[i]); ')' : begin while (s[top]<>'(') do lay; dec(top); end; '+','-','*','/' : begin while (tl(s[top])>=tl(t[i]))do lay; nap(t[i]); end else if t[i] in ['0'..'9'] then h := h + chuyenso + ' '; end; inc(i); end; while (top>0) and (s[top]<>'(') do lay; end; procedure tinh; var i : byte; a : real; s : array[1..max] of real; function so : real; var so1 : real; xau : string; j,cod : integer; begin j := i; while (h[i]<>' ') and (i ',h); tinh; end; close(f2); close(f1); END. Bài 3. Bài toán ”Trung vị của dãy” (ACM[POJ] 2623). Cho dãy N số nguyên không âm. Hãy xác định số trung vị của dãy. Nếu N lẻ thì số trung vị là số chính giữa dãy đã sắp, đó là vị trí (N+1)/2. Nếu N chẵn thì số trung vị là trung bình cộng hai số “chính giữa” dãy đã sắp, đó là các số ở vị trí N/2 và (N/2)+1. Dãy cho ban đầu là chưa sắp. Input Dòng đầu tiên chứa đúng một số N là độ dài của dãy. Dãy cho trong các dòng tiếp theo, mỗi dòng một số. Độ dài của dãy trong giới hạn từ 1 đến 250000. Mỗi phần tử của dãy là số nguyên dương không vượt quá 232 -1. Output In ra giá trị của số trung vị với đúng 1 chữ số thập phân sau dấu chấm (dấu phảy trong cách biểu diễn số thập phân). 10 Ví dụ Median.in 4 3 6 4 5 Median.out 4.5 Gợi ý. Tạo 2 Heap: A là MaxHeap (Heap có gốc mang khoá ưu tiên lớn nhất), B là MinHeap (Heap có gốc mang khoá ưu tiên nhỏ nhất). Đọc tệp input, mỗi lần được một số thì so sánh với gốc của A, nếu không výợt quá gốc của A thì nạp vào A, ngược lại thì nạp vào B. Sau khi có 2 Heap sẽ điều chỉnh (tháo Heap này chuyển sang Heap kia) sao cho số nút của A đúng bằng (N+1) div 2 Nếu N chẵn thì số trung vị là trung bình cộng của hai số ở hai gốc A và B. Nếu N lẻ thì số trung vị ở gốc của heap có số nút lớn hơn. Chương trình. const maxn = 1000; fi = 'median.in'; fo = 'median.out'; type rec = record w : integer; end; heap = array[0..maxn] of rec; var hmin,hmax : heap; n,sizehmin,sizehmax : integer; i,j : integer; f,g : text; node : rec; procedure init; begin fillchar(hmin, sizeof(hmin), 0); sizehmin := 0; fillchar(hmax, sizeof(hmax), 0); sizehmax := 0; end; procedure upheapmax(vt: integer); var key: rec; begin key := hmax[vt]; while (vt div 2>0) and (key.w > hmax[vt div 2].w) do begin hmax[vt]:= hmax[vt div 2]; vt:= vt div 2; end; hmax[vt]:= key; end; procedure inserthmax(node : rec); begin inc(sizehmax); hmax[sizehmax] := node; if sizehmax>1 then upheapmax(sizehmax); end; 11 procedure downheapmax(vt: integer); var key : rec; j : integer; begin Key := hmax[vt] ; j:=2*vt; while j <=sizehmax do begin if(hmax[j].w < hmax[j+1].w) then j:= j+1; if key.w > hmax[j].w then begin hmax[j div 2]:= key; exit; end else begin hmax[j div 2]:= hmax[j]; j:=2*j; end; hmax[j div 2]:= key; end; end; procedure removehmax(var node: rec); begin node := hmax[1]; hmax[1]:= hmax[sizehmax]; dec(sizehmax); downheapmax(1); end; procedure upheapmin(vt: integer); var key: rec; begin key := hmin[vt]; while (vt div 2>0) and (key.w < hmin[vt div 2].w) do begin hmin[vt]:= hmin[vt div 2]; vt:= vt div 2; end; hmin[vt]:= key; end; procedure inserthmin( node : rec); begin inc(sizehmin); hmin[sizehmin] := node; if sizehmin>1 then upheapmin(sizehmin); end; procedure downheapmin(vt: integer); var key : rec; j : integer; begin Key := hmin[vt] ; j:=2*vt; while j <=sizehmin do begin if(hmin[j].w > hmin[j+1].w) then j:= j+1; if key.w < hmin[j].w then begin hmin[j div 2]:= key; exit; end else begin hmin[j div 2]:= hmin[j]; j:=2*j; end; hmin[j div 2]:= key; 12 end; end; procedure removehmin(var node: rec); begin node := hmin[1]; hmin[1]:= hmin[sizehmin]; dec(sizehmin); downheapmin(1); end; procedure input_makeHeap; var i : integer; w : integer; node : rec; begin init; assign(f,fi); reset(f); readln(f,n); for i:=1 to n do begin readln(f,w); node.w := w; if w<=hmax[1].w then inserthmax(node) else inserthmin(node); end; close(f); end; procedure solve; var size, i : integer; node, node2 : rec; re : real; begin assign(g, fo); rewrite(g); while sizehmax>sizehmin do begin removehmax(node); inserthmin(node); end; while sizehmin>sizehmax do begin removehmin(node); inserthmax(node); end; if sizehmin>sizehmax then begin removehmin(node); re := node.w end else if sizehminl[i]^[j] then begin ii := i; jj := j; min := l[i]^[j]; end; end; end; procedure repair(ii,jj : integer); var node : thph; i,j : integer; begin new(node); node := ke[ii]; while node<>nil do begin i := node^.t; i for j:=1 to k do begin if d[i,j] then continue; if l[i]^[j] >= l[ii]^[jj] + node^.w then begin move(l[i]^[j],l[i]^[j+1],4*(k-j+1)); l[i]^[j] := l[ii]^[jj] + node^.w; move(tr1[i]^[j],tr1[i]^[j+1],4*(k-j+1)); move(tr2[i]^[j],tr2[i]^[j+1],4*(k-j+1)); tr1[i]^[j] := ii; tr2[i]^[j] := jj; break; end; end; node := node^.next; end; end; procedure solve; var i, ii, jj : integer; ok : boolean; begin for i:=1 to n do begin new(tr1[i]); fillchar(tr1[i]^,sizeof(tr1[i]^),0); new(tr2[i]); fillchar(tr2[i]^,sizeof(tr2[i]^),0); end; repeat findmin(ii,jj); ok := (ii=0) or (d[n,k]); if d[n,k] then break; 16 if not ok then begin d[ii,jj] := true; repair(ii,jj); end; until ok; end; function minpath:longint; var sum : longint; j : integer; begin sum := 0; for j:=1 to k do inc(sum, l[n]^[j]); minpath := sum; end; procedure write_output; var f : text; dem,t,i1,i2, j : integer; kq : array[1..40] of integer; begin assign(f,fo); rewrite(f); writeln(f,minpath); for j:=k downto 1 do begin dem := 1; kq[dem] := n; i1 := tr1[n]^[j]; i2 := tr2[n]^[j]; repeat inc(dem); kq[dem] := i1; i1 := tr1[i1]^[i2]; i2 := tr2[kq[dem]]^[i2]; until (i1=0); for t:=dem downto 1 do write(f,kq[t],' '); writeln(f); end; close(f); end; BEGIN read_input; prepare; solve; write_output; END. Bài 5. Cây BST Sau khi dựng cây nhị phân tìm kiếm, nếu duyệt cây theo kiểu tiền tự (trái, giữa, phải) sẽ được dãy tăng, duyệt theo kiểu hậu tự (phải, giữa, trái) sẽ được dãy giảm. Hãy viết chương trình đọc n số nguyên để xây dựng cây nhị phân tìm kiếm và duyệt cây để có mảng đã sắp (tăng/ giảm). Chương trình. uses crt; const fi = 'tree.inp'; type tree = ^node; node = record v : byte; r,l : tree; 17 end; var t : tree; x,n,k : integer; ch : char; function creat_node(x: integer; l,r : tree): tree; var t1 : tree; begin new(t1); t1^.v := x; t1^.l := nil; t1^.r := nil; creat_node := t1; end; Procedure insert(var t: tree; x : integer); begin if t=nil then t := creat_node(x,nil,nil) else begin if xnil then begin traversal_preoder_inc(t^.l); write(t^.v,' '); traversal_preoder_inc(t^.r); end; end; Procedure traversal_preoder_dec(t : tree); begin if t<>nil then begin traversal_preoder_dec(t^.r); write(t^.v,' '); traversal_preoder_dec(t^.l); end; end; Procedure search(t : tree; x : byte); var p1 : tree; begin p1 := t; while p1<>nil do begin if xp1^.v then p1 := p1^.r else begin writeln('co phan tu voi khoa la : ',x);exit;end; 18 end; if p1=nil then writeln('khong co phan tu voi khoa la : ',x); end; BEGIN clrscr; t := nil; creat_tree; repeat writeln('S:search - I:traversal_inc - D:traversal_dec - Q:Thoat '); ch := upcase(readkey); case ch of 'S' : begin write('hay cho khoa can tim: ');readln(k); search(t,k); end; 'I' :begin traversal_preoder_inc(t);writeln;end; 'D' :begin traversal_preoder_dec(t);writeln;end; end; until ch ='Q'; END. Bài 6. Cây khoảng (Interval Tree) Cho một dãy số A(0..N-1) gồm N số nguyên đánh số từ 0 đến N-1 là A[0], A[1], …, A[N-1]. Xét M yêu cầu gồm hai loại: • C i j: Thay phần tử thứ i bằng giá trị j. • Q i j: Xuất ra tổng các phần tử trong dãy số từ vị trí i đến vị trí j Nhiệm vụ: Cho trước dãy số A(0..N-1) và M yêu cầu trong file văn bản DAYSO.IN. Hãy thực hiện các phép biến đổi trên dãy và viết các kết quả ra file DAYSO.OUT Giới hạn: 1≤N≤10000; |Ai|≤1000, M≤100000 File input: Dòng đầu tiên chứa 2 số nguyên N và M. Dòng thứ hai chứa các phần tử của dãy A(0..N-1). M dòng cuối chứa các yêu cầu. Kết quả Ghi ra file output gồm một số dòng tương ứng là kết quả của các yêu cầu Q trong file input. Ví dụ DAYSO.IN 5 3 1 2 3 4 5 Q 2 3 C 3 7 Q 1 4 DAYSO.OUT 7 17 Hướng dẫn Tổ chức cây nhị phân đầy đủ, mỗi nút quản lý một đoạn thuộc dãy gồm các dữ liệu: số hiệu nút, vị trí phần tử đầu và cuối của đoạn, tổng các phần tử của dãy trong đoạn. Mỗi đoạn [left, right] lại 19 được chia thành hai đoạn con là [left, mid] và [mid+1, right] (mid=(left+right) div 2), tạo thành hai nút con trái và phải. Trong ví dụ nêu trong bài toán có cây như hình sau: Để cài đặt cây, có thể dùng mảng một chiều T và mảng một chiều Pos: T[d] là tổng các phần tử của đoạn do nút có số hiệu d quản lý, Pos[i] là số hiệu của nút lá chứa phần tử A[i]. Hàm đệ qui preprocess(left, right, d) xây dựng giá trị cho mảng Pos. Lời gọi ban đầu preprocess(1, n, 1) thực hiện đệ qui, ban đầu giả định số hiệu nút đầu tiên là d=1, nút này quản lí đoạn từ phần tử đầu đến phần tử cuối của dãy. Điều kiện dừng của đệ qui là gặp lá và gán số hiệu của nút trên cây cho nút lá. Chỉ có lá mới cần gán số hiệu nút, số hiệu các nút trong của cây thực ra không cần lưu vì khi biết số hiệu nút con suy ngay ra số hiệu nút cha của nó (khi qui định số hiệu nút gốc là 1 thì nút cha của nút có số hiệu i là nút có số hiệu i div 2), vì vậy khi biết số hiệu các nút lá, đi ngược về gốc sẽ tính được số hiệu các nút trong. Sau quá trình đệ qui này, rõ ràng nút lá đã biết được đủ cả 3 tính chất của đoạn do nút này quản lí là: vị trí phần tử đầu và cuối của một đoạn (hai vị trí này trùng nhau), tổng các phần tử của đoạn (chính là giá trị phần tử duy nhất), số hiệu của nút. Chú ý T[pos[i]]=A[i]. Bằng tiếp cận bottom-up, đi ngược từ các nút lá lên phía gốc, sẽ tính được tổng các phần tử thuộc đoạn do từng nút trên quản lý (nghĩa là xây dựng xong mảng T). Sau khi xây dựng xong cây (nghĩa là cài đặt xong mảng T và Pos) cần xây dựng hai phép toán: phép cập nhật lại giá trị một phần tử của mảng và phép tính tổng các phần tử của một đoạn tuỳ ý. Về phép cập nhật lại một phần tử của mảng: Giả sử cần cập nhật giá trị phần tử i, thì từ nút lá có số hiệu pos[i], đi ngược về gốc, dễ dàng cập nhật lại các giá trị tương ứng của T[j] với j là số hiệu của các nút cha trên đường đi về gốc. Về phép tính tổng của các phần tử của một đoạn tuỳ ý [i; j] ta xây dựng hàm đệ qui sum() đặt đoạn [i; j] vào gốc. Tìm đường đi về lá đến nút [left=i; right=j] thì dừng và xuất ra giá trị tổng các phần tử của nút này. Tìm kiếm nút [i..j] trên cây Interval bằng tìm kiếm nhị phân. Giả sử tìm đến nút [left; right] có số hiệu nút là d, đặt mid=(left+right) div 2, xét 3 trường hợp: • Mid=j : thì đoạn [i,j] thuộc đoạn [left;mid] có số hiệu 2*d • Mid - Xem thêm -