Xem mẫu
- Môn: CẤU TRÚC DỮ LIỆU
Chương 4: DANH SÁCH (LIST)
1
- 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
Ứng dụng của danh sách hạn chế
BÀI TẬP
2
- 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.}.
3
- 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. 4
- 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 5
- 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]
6
- 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;
}
7
- 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()
{ …} 8
- 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
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 (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);
}
10
- 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
11
- 3. Danh sách đặc (tt)
3.3. Các thao tác trên danh sách đặc (tt)
3.3.5. Hủy 1 phần tử trong danh sách
Loại bỏ phần tử có vị trí DelPosition trong danh sách M có
chiều dài Length (có thể có thao tác tìm kiếm xác định vị trí
xóa phần tử)
Thuật toán:
B1: IF(Length =0 OR DelPos > Len) Thực hiện BKT
B2: Pos = DelPos
B3: IF(Pos = Length)
Thực hiện B7
B4: M[Pos] = M[Pos+1]
B5: Pos++
B6: Lặp lại B3
B7: Length--
BKT: Kết thúc
12
- 3. Danh sách đặc (tt)
3.3. Các thao tác trên danh sách đặc (tt)
3.3.5. Hủy 1 phần tử trong danh sách (tt)
int CD_Delete_Element(T M[], int &Len, int DelPos)
{
int (Len ==0 || DelPos >=Len)
return (-1);
for (int I =DelPos; i
- 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;
14
- 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)
Giải thuật sắp xếp chọn trực tiếp (Straight Selection Sort)
Giải thuật sắp xếp chèn trực tiếp (Straight Insertion Sort)
Giải thuật sắp xếp trộn trực tiếp (Straight Merge Sort)
Giải thuật sắp xếp trộn tự nhiên (Natural Merge Sort)
15
- 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
Có nhiều thao tác tách 1 danh sách thành nhiều danh sách:
Phân phối luân phiên theo đường chạy (distribute)
Phân phối từng phần của danh sách thành các danh sách
con
Tách các phần tử thỏa mãn điều kiện cho trước thành các
danh sách con.
Giả sử cần tách danh sách M có chiều dài Length thành các danh
sách con SM1, SM2 có chiều dài tương ứng là Slen1 và
SLen2
16
- 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)
B1: IF(SLen1 >= Len)
SLen1 = Len
SLen2 = 0
B2:IF(SLen2 >= Len)
SLen2 = Len
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
17
- 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;
if (SLen2 < 0) SLen2 = 0;
if (SLen1 + SLen2 != Len) SLen2 = Len - SLen1;
for (int i=0; i
- 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
Các cách nhập danh sách:
Ghép nối đuôi các danh sách thành danh sách mới có chiều
dài là tổng chiều dài các danh sách.
Trộn xen kẽ các phần tử trong danh sách con theo 1 quy luật
nào đó thành 1 danh sách mới (dùng thuật toán merge trong
merge sort)
Giả sử cần ghép danh sách SM1, SM2 có chiều dài SLen1,
SLen2 thành danh sách M có chiều dài Len = SLen1+SLen2
theo thứ tự từ SM1 đến hết SM2
19
- 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)
Thuật toán:
B1: IF (Slen1+SLen2 > MaxLen) // M không đủ khả năng chứa
Thực hiện BKT
B2: I = 1 // Chép từ SM1[] vào M[]
B3: IF (I > SLen1)
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
20
nguon tai.lieu . vn
