Danh sách list trong cấu trúc dữ liệu

1

Môn: CẤU TRÚC DỮ LIỆU

Chương 4: DANH SÁCH (LIST)

2

NỘI DUNG CHƯƠNG 4

1. Khái niệm danh sách

2. Các phép toán trên danh sách

3. Danh sách đặc  Định nghĩa  Biểu diễn danh sách đặc  Các thao tác trên danh sách đặc  Ưu nhược điểm và ứng dụng

1. Danh sách liên kết  Định nghĩa  Danh sách liên kết đơn  Danh sách liên kết kép  Ưu nhược điểm của danh sách liên kết

1. Danh sách hạn chế  Hàng đợi  Ngăn xếp  Ứng dụng của danh sách hạn chế

BÀI TẬP

3

1. Khái niệm danh sách

 Danh sách a1

, a2

, ….aN

là tập hợp các phần tử có kiểu dữ liệu

xác định và giữa chúng có 1 mối quan hệ nào đó. Nếu biết

phần tử ai  vị trí của phần tử ai+1

 Số phần tử trong một danh sách là chiều dài của 1 danh sách.

Danh sách rỗng là danh sách có chiều dài = 0

 Cho T là một kiểu được định nghĩa trước, kiểu danh sách TX

gồm các phần tử thuộc kiểu T được định nghĩa là:

TX

= < VX

, OX

>

Trong đó :

 VX

= { tập hợp các thứ tự gồm một số biến động các phần tử

kiểu T }.

 OX

= { tạo danh sách; tìm 1 phần tử trong danh sách; chèn 1

phần tử vào danh sách; huỷ 1 phần tử khỏi danh sách; liệt

kê danh sách, sắp xếp danh sách.}.

4

2. Các phép toán trên danh sách

Tùy theo loại của từng danh sách sẽ có các phép toán khác nhau,

các phép toán thông thường như sau:

2.1. Tạo mới 1 danh sách

 Đưa vào danh sách nội dung các phần tử.

 Chiều dài của danh sách là xác định.

2.2. Thêm 1 phần tử vào danh sách

 Khi thêm 1 phần tử chiều dài danh sách tăng lên.

 Có thao tác thêm vào đầu, cuối hay tại 1 vị trí xác định của

danh sách.

2.3. Tìm kiếm 1 phần tử trong danh sách

 Tìm 1 phần tử trong danh sách thỏa mãn điều kiện nào đó

 Dùng các thuật toán tìm kiếm trong chương “Tìm kiếm”

2.4. Loại bớt 1 phần tử trong danh sách

 Chiều dài danh sách giảm xuống 1 phần tử

 Công việc loại bớt cũng bao gồm thao tác tìm kiếm ra phần tử

cần hủy trong danh sách.

5

2. Các phép toán trên danh sách (tt)

2.5. Sửa đổi giá trị 1 phần tử trong danh sách

 Thay đổi thông tin của 1 phần tử trong danh sách

 Công việc cập nhật phần tử cũng bao gồm thao tác tìm kiếm ra phần tử cần hủy trong danh sách.

2.6. Sắp xếp danh sách

 Dùng các thuật toán trong chương sắp xếp.

2.7. Tách danh sách thành nhiều danh sách con

 Tách danh sách thành các DS con theo 1 quy luật chia nào đó

 Tổng chiều dài các danh sách được chia bằng chiều dài danh sách ban đầu

2.8. Nhập nhiều danh sách thành 1 danh sách

 Nhập các danh sách thành 1 danh sách

 Tổng chiều dài danh sách bằng tổng chiều dài các danh sách ban đầu

 Có thể ghép đuôi các danh sách hay trộn lẫn theo 1 phương pháp nhất định

2.9. Sao chép 1 danh sách: Sao chép toàn bộ nội dung của danh

sách thành 1 danh sách khác.

2.10. Hủy danh sách: Huỷ nội dung hay cả vùng nhớ chứa DS

6

3. Danh sách đặc (Condensed List)

3.1. Định nghĩa

 Danh sách đặc là danh sách mà không gian bộ nhớ lưu trữ các

phần tử nằm kề cận nhau trong bộ nhớ.

3.2. Biểu diễn danh sách đặc

 Biểu diễn danh sách đặc dùng 1mảng các phần tử có kiểu dử

liệu là kiểu dữ liệu của các phần tử trong danh sách

 Cần biết chiều dài tối đa của một danh sách đặc thông qua 1

biến.

 Cần biết chiều dài thực của một danh sách đặc thông qua 1

biến.

VD:#define MaxLength 1000

int RealLength;

T CD_List[MaxLength]

Hay: T * CD_List = new T[MaxLength]

7

3. Danh sách đặc (tt)

3.3. Các thao tác trên danh sách đặc

Một số thao tác trên danh sách đặc được thống kê tóm tắt:

3.3.1. Khởi tạo danh sách

Khởi tạo danh sách cho chiều dài danh sách trở về 0.

void CD_Initialize(int &Len)

{

Len = 0;

return;

}

8

3. Danh sách đặc (tt)

3.3. Các thao tác trên danh sách đặc (tt)

3.3.2. Tạo danh sách mới & nhập danh sách

Tạo danh sách mới có chiều dài tối đa MaxLen, hàm trả về giá trị

thực của danh sách mới được tạo.

int CD_Create_List(T M[], int &Len)

{

if (Len > MaxLen)

Len = MaxLen;

for (int I = 0; i< Len;I++)

M[I] = InputOneElement();

return (Len);

}

T InputOneElement()

{ …}

9

3. Danh sách đặc (tt)

3.3. Các thao tác trên danh sách đặc (tt)

3.3.3. Thêm 1 phần tử vào danh sách

Thêm 1 phần tử có giá trị NewValue vào trong danh sách có chiều

dài Length tại vị trí InsPos

B1: IF (Length = MaxLen)

Thực hiện BKT

B2: Pos = Length+1

B3: IF(Pos = InsPos)

Thực hiện B7

B4: M[Pos] = M[Pos -1]

B5: Pos--

B6: Lặp lại B3

B7:M[InsPos] = NewValue

B8: Length++

BKT: Kết thúc

10

3. Danh sách đặc (tt)

3.3. Các thao tác trên danh sách đặc (tt)

3.3.3. Thêm 1 phần tử vào danh sách (tt)

int CD_InsertElement(T M[], int &Len, T NewValue, int InsPos)

{

if (Len == MaxLen)

return (-1);

for (int I = Len; I >InsPos; I++)

M[I] = M[I-1];

M[InsPos] = NewValue;

Len++;

return (Len);

}

11

3. Danh sách đặc (tt)

3.3. Các thao tác trên danh sách đặc (tt)

3.3.4. Tìm kiếm 1 phần tử trong danh sách

Dùng các thuật toán tìm kiếm tìm phần tử thỏa mãn điều kiện trong

danh sách

 Tìm kiếm tuyến tính

 Tìm nhị phân