Trang 1
goupee.vn goupee.com Phần 3: Cấu trúc dữ liệu và giải thuật Chương 9: Các cấu trúc tuyến tính Phần B: Cấu trúc Danh Sách cuu duong than cong . com fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
Nội dung tài liệu
Trang 2
goupee.vnCác nội dung chính goupee.com Cấu trúc danh sách Mô tả Cấu trúc vào sau ra trước (LIFO) (Stack-Ngăn xếp) Cấu trúc vào trước ra trước (FIFO) (Queue- Hàng đợi) Một số ứng dụng của ngăn xếp và hàng đợi cuu duong than cong . com fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 3
goupee.vnGiới thiệu - Mô tả cấu trúc goupee.com Danh sách tuyến tính: CTDL gồm một hay nhiều phần tử cùng kiểu dữ liệu và tồn tại một trật tự tuyến tính giữa các phần tử. Kí hiệu: L = <x ,x ,...,xn> 1 2 n 1 và x ,x ,...,xn là các phần tử của danh sách, 1 2 x được gọi là phần tử đầu tiên (đầu) của danh sách 1 xn được gọi là phần tử cuối cùng (đuôi) của danh sách Trật tự tuyến tính: trật tự trước-sau giữa các phần tử, tức là với mọi cặp phần tử <xi,xj> (1 i,j n và i j) trong tập các phần tử này luôn có duy nhất một trật tự trước sau. Quy ước: trường hợp đặc biệtcuu duong than cong . comkhi danh sách không có phần tử nào, gọi là danh sách rỗng, kí hiệu (L = ). fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 4
goupee.vnGiới thiệu – Đặc trưng: goupee.com Kích thước hay độ dài danh sách: số phần tử của danh sách. Kích thước của danh sách rỗng bằng 0. Chú ý kích thước danh sách không cố định mà biến đổi trong quá trình xử lý, thao tác và nó là đại lượng mà ta thường không biết trước được. Kiểu dữ liệu của các phần tử: có một kiểu dữ liệu duy nhất cho các phần tử của danh sách. Kiểu dữ liệu cho các phần tử luôn luôn cố định. Trật tự tuyến tính trong danh sách: một danh sách luôn có hai phía, mộtcuu duong than cong . comphía chúng ta quy ước là đầu, còn phía kia là đuôi của danh sách. Trật tự trước-sau là trật tự từ đầu đến cuối. fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 5
goupee.vnGiới thiệu – Các thao tác cơ bản trên danh goupee.com sách Khởi tạo danh sách Định ra cấu trúc danh sách, xác định các đặc trưng của danh sách. Sau thao tác khởi tạo, ta thường thu được một danh sách rỗng (danh sách chưa có nội dung, mà mới chỉ có phần khung). Trong các ngôn ngữ lập trình, thao tác khởi tạo thường là việc khai báo cấu trúc lưu trữ thích hợp để biểu diễn cho cấu trúc danh sách yêu cầu. cuu duong than cong . com fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 6
goupee.vnGiới thiệu – Các thao tác cơ bản trên danh goupee.com sách Bổ sung một phần tử mới vào danh sách Trước tiên cần phải xác định vị trí trong danh sách mà phần tử mới sẽ được đưa vào. Thông thường, vị trí bổ sung thường là đầu hay cuối của danh sách. Tuy nhiên, ta cũng có thể chèn phần tử mới vào giữa danh sách. Mỗi thao tác bổ sung này làm tăng kích thước danh sách lên 1. Chú ý, điều kiện trướccuu duong than cong . comtiên (hay tiền điều kiện) để thực hiện được thao tác bổ sung là danh sách chưa “đầy” hay chưa bão hoà. fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 7
goupee.vnGiới thiệu – Các thao tác cơ bản trên danh goupee.com sách Loại bỏ một phần tử khỏi danh sách Đây là thao tác ngược lại của thao tác bổ sung. Việc loại bỏ này làm giảm kích thước của danh sách đi 1. Chú ý là điều kiện trước tiên để loại bỏ một phần tử là danh sách phải không rỗng, tức là nó phải còn ít nhất một phần tử. Nói chung,cuu duong than cong . comviệc xác định trạng thái rỗng của danh sách là một công việc đơn giản, vì đây cũng chính là trạng thái của danh sách sau thao tác khởi tạo. fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 8
goupee.vnGiới thiệu – Các thao tác cơ bản trên danh goupee.com sách Tìm kiếm một phần tử trong danh sách: tìm kiếm sự xuất hiện hay không của một hay một số phần tử trong danh sách theo một điều kiện tìm kiếm, và nếu xuất hiện thì ở vị trí nào trong danh sách. Thao tác tìm kiếm thường đi đôi với các thao tác bổ sung và loại bỏ. Chúng ta sẽ dành một chương “các giải thuật tìm kiếm” để nói về thao tác này. Sắp xếp danh sách: là thao tác sắp xếp các phần tử của danh sách theo một trật tự nhất định Các giải thuật sắp xếp sẽ được trìnhcuu duong than cong . combầy chi tiết trong chương “Các giải thuật sắp xếp” Nối hai hay nhiều danh sách con để thành một danh sách Tách danh sách thành hai hayfb.com/goupee.vn nhiều danh sách con CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 9
goupee.vnGiới thiệu – Các cấu trúc danh sách thông goupee.com dụng Cấu trúc vào sau ra trước (Last In, First Out - LIFO) hay cấu trúc ngăn xếp – Stack Cấu trúc vào trước ra trước (First In, First Out - FIFO) hay cấu trúc hàng đợi – Queue cuu duong than cong . com fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 10
goupee.vnGiới thiệu – Các cấu trúc danh sách thông goupee.com dụng Cấu trúc hàng đợi có ưu tiên - Priority queue Ở đây mỗi phần tử có thêm một thuộc tính gọi là độ ưu tiên. Với các phần tử có độ ưu tiên như nhau thì danh sách hoạt động giống như nguyên tắc hàng đợi. Khi có hai phần tử bất kỳ có độ ưu tiên khác nhau thì danh sách luôn ưu tiên phần tử có độ ưu tiên cao hơn, nên dù phần tử có độ ưu tiên cao hơn có được bổ sung vào sau phần tử có độ ưu tiên thấp hơn thì nó vẫn được loại bỏ ra trước. Có thể ncuu duong than cong . comói cấu trúc này kết hợp cả hai nguyên tắc hoạt động của ngăn xếp và hàng đợi không ưu tiên. fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 11
goupee.vnGiới thiệu – Các phương pháp cài đặt goupee.com Cài đặt bằng cấu trúc lưu trữ tuần tự (hay mảng một chiều): đây là cách cài đặt đơn giản và nhanh nhất. Tuy nhiên, cách cài đặt này cũng có một số hạn chế do sự khác nhau cơ bản giữa cấu trúc danh sách và cấu trúc mảng, giữa một bên là cấu trúc động, một bên là cấu trúc tĩnh. Cài đặt bằng cấu trúc lưu trữ móc nối: đây là một cấu trúc lưu trữ động với kích thước và tổ chức lưu trữ có thể biến đổi linh hoạt theo yêu cầu của cấu trúc dữ liệu,cuu duong than cong . comnên rất thích hợp để tổ chức và lưu trữ các cấu trúc dữ liệu động. fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 12
goupee.vnNguyên tắc chung goupee.com Khi sử dụng một CTLT để cài đặt cho một cấu trúc dữ liệu, chúng ta phải lưu ý một số nguyên tắc sau: Tính đầy đủ: CTLT phải có các đặc trưng thích hợp để biểu diễn đầy đủ các đặc tính và khả năng của CTDL. Nó thể hiện ở hai khía cạnh Khả năng lưu trữ: là kích thước của CTLT được cài đặt. Đại lượng này được quyết định bởi miền giá trị của cấu trúc dữ liệu mà nó cài đặt. Việc cài đặt cấu trúc dữ liệu kiểu số nguyên là một ví dụ sinh động về nguyên tắc cài đặt này. Khả năng xử lý: được cụ thể hoá bằng tập các thao tác được cài đặt trên CTLT đã chọn.cuu duong than cong . com Tính mở Tính che dấu fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 13
goupee.vnCài đặt danh sách bằng cấu trúc lưu trữgoupee.com tuần tự Nguyên tắc chung: Chọn cấu trúc lưu trữ phù hợp Bố trí hợp lý các phần tử của danh sách trong CTLT đã chọn cuu duong than cong . com fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 14
goupee.vnCài đặt danh sách bằng cấu trúc lưu trữgoupee.com tuần tự Nguyên tắc chung: Chọn cấu trúc lưu trữ phù hợp Xác định kích thước tối đa MAX của danh sách Xác định kiểu dữ liệu cho mỗi phần tử của danh sách Chọn CTLT là mảng một chiều kích thước và kiểu dữ liệu như đã chọn cuu duong than cong . com fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 15
goupee.vnCài đặt danh sách bằng cấu trúc lưu trữgoupee.com tuần tự Nguyên tắc chung: Bố trí hợp lý các phần tử của danh sách trong CTLT đã chọn theo một số nguyên tắc: Bố trí mỗi phần tử trong một ngăn nhớ Bố trí các phần tử lần lượt theo trật tự tuyến tính của chúng Bố trí các phần tử ở các vị trí kề nhau để đảm bảo số thông tin cần quản lý danh sách là ít nhất. Chọn cách bố trí thích hợp để các thao tác cơ bản thựccuu duong than cong . com hiện trên danh sách là hiệu quả nhất. fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 16
goupee.vnCài đặt danh sách bằng cấu trúc lưu trữgoupee.com tuần tự Một số cách bố trí các phần tử của danh sách trong mảng a) Bố trí liền từ đầu mảng H=1, R=n, chỉ cần một thông tin là n b) Bố trí dãy liên tục, cần hai trong ba thông tin H, R, n. a1 a2 a3 … an-1 an H=1 R=n MAX a) cuu duong than cong . coma a … a a 1 2 n-1 n H R MAX b) fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 17
goupee.vnCấu trúc LIFO (Stack) goupee.com Mô tả: cấu trúc vào sau ra trước (Last In, First Out - LIFO) hay cấu trúc ngăn xếp – Stack Đỉnh (top) 5 4 Thứ tự bổ sung 3 Thứ tự loại bỏ 2 1 2 3cuu duong than cong . com4 5 1 5 4 3 2 1 Đáy (bottom) Cấu tạo và hoạt động của Stack fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 18
goupee.vnCài đặt Stack bằng cấu trúc lưu trữ tuần tgoupee.comự Nguyên tắc cài đặt 1 2 MAX a1 a2 … … … aT-1 aT loại bỏ bổ sung B = 1 T (Đáy) (Đỉnh) cuu duong than cong . com Biểu diễn ngăn xếp bằng CTLT tuần tự fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 19
goupee.vn goupee.com typedef struct { Type info [MAX]; unsigned int n; //Số phần tử của Stack } Stack; CTLT tuần tự được thể hiện qua mảng info, Type là kiểu dữ liệu của danh sách n là số phần tử của ngăn xếp. Đỉnh của ngăn xếp sẽ ở vị trí n-1 cuu duong than cong . com fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 20
goupee.vn goupee.com typedef struct { Type info [MAX]; unsigned int n; //Số phần tử của Stack } Stack; Trạng thái hiện thời của ngăn xếp: Rỗng (empty): n=0 Đầy (full): thông thường, giá trị MAX là kích thước tối đa của ngăn xếp (nếu có thể xác định chính xác) hoặc kích thước tối đa mà CTLT tuần tự này được cho phép, nên ta sẽ quy ước ngăn xếp đầy khi n=MAX. Bình thường (cuu duong than cong . comnormal): trạng thái không rỗng mà cũng không đầy. Khi ngăn xếp ở trạng thái này, nó có thể thực hiện các thao tác bổ sung và loại bỏ. fb.com/goupee.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!