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
4. 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
5. Danh sách hạn chế

Hàng đợi

Ngăn xếp


X
>
Trong đó :

V
X
= { tập hợp các thứ tự gồm một số biến động các phần tử
kiểu T }.

O
X
= { 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ổ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

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)

{
int (Len ==0 || DelPos >=Len)
return (-1);
for (int I =DelPos; i<Len; i++)
M[i] = M[i+1];
Len --;
return (Len);
}
14
3. Danh sách đặc (tt)
3.3. Các thao tác trên danh sách đặc (tt)
3.3.6. Sửa đổi giá trị cho 1 phần tử trong danh sách

Giả sử phần tử trong danh sách được thay đổi ở tại vị trí
Position trong danh sách M có chiều dài Length.

Thao tác sửa đổi là thao tác tìm kiếm phần tử cần có vị trí (hay
giá trị) và gán giá trị mới

M[Pos] = NewValue;
15
3. Danh sách đặc (tt)
3.3. Các thao tác trên danh sách đặc (tt)
3.3.7. Sắp xếp thứ tự phần tử trong danh sách
Dùng các thuật toán sắp xếp nội

Giải thuật sắp xếp nổi bọt (Bubble Sort)

Giải thuật sắp xếp dựa trên phân hoạch (Quick Sort)


SLen1 = 0
B3: IF(SLen1 + SLen2 <> Len) SLen2 = Len – SLen1
B4: IF (SLen1 < 0) SLen1 = 0
B5: IF (SLen2 < 0) SLen2 = 0
B6: I =1, SI = 1
B7: IF (I > SLen1) Thực hiện B11
B8: SM[SI] = M[I]
B9: I++, SI++
B10: Lặp lại B7
B11: SI = 1
B12: IF(I > Len) Thực hiện BKT
B13: SM2[SI] = M[I]
B14: I++, SI++
B15: Lặp lại B12
BKT: Kết thúc
18
3. Danh sách đặc (tt)
3.3. Các thao tác trên danh sách đặc (tt)
3.3.8. Tách 1 danh sách thành nhiều danh sách (tt)
void CS_Split(T M[], int Len, T SM1[], int &SLen1, T SM2[], int
&SLen2)
{ int (Slen1 >=Len)
{ SLen1 = Len;
Slen2 = 0;
}
int (Slen2 >=Len)
{ SLen2 = Len;
SLen1 = 0;
}
if (SLen1 < 0) SLen1 = 0;

Thực hiện B7
B4: M[I] = SM[I]
B5: I++
B6: Lặp lại B3
B7: SI = 1 // Chép từ SM2[] vào M[]
B8: IF (SI > SLen2)
Thực hiện BKT
B9: M[I] = SM[SI]
B10: I++; SI++
B11: Lặp lại B8
BKT: Kết thúc
21
3. Danh sách đặc (tt)
3.3. Các thao tác trên danh sách đặc (tt)
3.3.9. Nhập nhiều danh sách thành 1 danh sách(tt)
int CD_Concat(T SM1[], int SLen1, T SM2[], int SLen2, T M [], int
&Len)
{
if (SLen1+SLen2 > MaxLen)
return (-1);
for (int I = 0; I < SLen1; I++)
M[I] = SM1[I];
for (int J = 0; J < SLen2; I++, J++)
M[I] = SM1[J];
Len = SLen1+ SLen2;
return (Len);
}
22
3. Danh sách đặc (tt)
3.3. Các thao tác trên danh sách đặc (tt)

sách đặc có các ưu điểm:

Mật độ sử dụng danh sách là tối ưu tuyệt đối.

Truy cập, tìm kiếm các phần tử là dễ dàng vì vị trí các phần
tử liền kề với nhau trong bộ nhớ.

Nhược điểm của danh sách là khi thêm hay hủy 1 phần tử
trong danh sách cần dịch chuyển các phần tử còn lại qua vị trí
khác.

Được ứng dụng nhiều trong cấu trúc dữ liệu mảng (mảng 1
chiều, mảng nhiều chiều, mảng cấp phát tĩnh, mảng cấp phát
động).
25
4. Danh sách liên kết (Linked List)
4.1. Định nghĩa
4.2. Danh sách liên kết đơn (Simply Linked List)
4.3. Danh sách liên kết kép (Doubly Linked List)
4.4. Ưu nhược điểm của danh sách liên kết