A. DANH SÁCH

_ Tính chất : Các phần tử trong danh sách có thứ tự tuyến tính theo vị trí.

_ EndList là vị trí sau phần tử cuối cùng trong danh sách.

_ Các phép toán : (Đặc//Liên kết)

MakeNull_List(L) – Empty_List(L) : –> L->Last==0; // –> L->Next==NULL;

Insert_List(X,P,&L) –> P không hợp lệ khi (P<1) hoặc (P>Last+1) //

FirstList(L)  –> 1

+ EndList(L)  –>  L.Last+1

Retrieve(P,L) –> L.Elements[P-1]

+ Next(P,L) –> P+1

+ Locate(X,L) ;  Delete_List(P,&L) [Q-1]=[Q]; Previous(P,L) ;

_ Phần tử thứ 1 mang chỉ số 0 trong mảng. –> Locate và Retrieve trả về L.Element[P-1]

_ So sánh : Mảng : phải ước lượng số phần tử, thời gian xen hoặc xóa lâu, truy cập Previous mau. Con trỏ : Thích hợp với ds động, tốn vùng nhớ cho Next, xen hoặc xóa mau, Previous lâu.

B. NGĂN XẾP :

_ Vào sau ra trước – LIFO (last in – first out)

_ Các phép toán : MakeNull_Stack(S) ; Top(S) ; Pop(S) ; Push(X,S) ; Empty_Stack(S) (Top=MaxLength); Full_Stack(S) (Top=0);

_ Điểm yếu cài đặc bằng mảng là phải ước lượng số phần tử, để linh hoạt dùng ngăn xếp = con trỏ.

_ Ứng dụng : Khử đệ quy

C. HÀNG ĐỢI

_ Đầu hàng (Front) – Cuối hàng (Rear)

_ Vào trước ra trước – FIFO (first in – first out)

_ Các phép toán : MakeNull_Queue(Q) ; Front(Q) ; EnQueue(x,Q) ; DeQueue(Q) ; Empty_Queue(Q) ; Full_Queue(Q);

1. Mảng

_ Giả sử hàng có n phần tử thì Front=0, Rear=n-1 (Xóa 1 ptử Front tăng 1, thêm 1 ptử Rear tăng 1)

_ Hàng có xu hướng đi xuống, không thêm được nữa khi Rear=MaxLength-1

2. Tịnh tiến

_ Chỉ cần quản lí đầu hàng và cuối hàng

_ Hàng rỗng khi và chỉ khi Front=-1

_ Số phần tử của hàng = Rear-Front+1

3. Xoay vòng

_ Front có thể lớn hơn Rear.

_ Kiểm tra hàng rỗng : (Rear-Front+1) mod MaxLength=0