om du on g th an co ng .c Phần 3: Cấu trúc dữ liệu và giải thuật cu u Chương 9: Các cấu trúc tuyến tính Phần B: Cấu trúc Danh Sách om Các nội dung chính  ng co th an  du on g  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) (QueueHàng đợi) Một số ứng dụng của ngăn xếp và hàng đợi cu u  .c Cấu trúc danh sách    .c ng Kí hiệu: L = <x1,x2,...,xn> co 1 và x1,x2,...,xn là các phần tử của danh sách, n  x1 được gọi là phần tử đầu tiên (đầu) của danh sách  xn được gọi là phần tử cuối cùng (đuôi) của danh sách th an  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. du on g  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ử. cu u  om Giới thiệu - Mô tả cấu trúc Quy ước: trường hợp đặc biệt khi danh sách không có phần tử nào, gọi là danh sách rỗng, kí hiệu (L = ). Giới thiệu – Đặc trưng: .c 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. th an co  ng  om 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ột phí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. cu u d