Bài giảng môn Cấu trúc dữ liệu - Chương 4: Danh sách (List)

Thực hiện BKT B3: IF (Inode == DLLList.DLLLast) Thực hiện BKT B4: Jnode = DLLList.DLLLast B5: IF (Jnode = Inode) Thực hiện B7 B6: ELSE B6.1: If (Jnode->Key PreNode ->Key) Swap (Jnode ->Key, Jnode ->PreNode ->Key) B6.2: Jnode = Jnode ->NextNode B6.3: Lặp lại B5 B7: Inode = Inode ->NextNode B8: Lặp lại B3 BKT: Kết thúc 150 4.3. Danh sách liên kết đôi 4.3.2.k. Sắp xếp thứ tự thành phần dữ liệu trong danh sách (tt) Cài đặt thuật toán void DLLBubbleSort (DLLPType &DList) { DLLType Inode = DList.DLLFirst; if (Inode == NULL) return; while (Inode != DList.DLLLast) { DLLType Jnode = DList.DLLLast; while (Jnode != Inode) { if (Jnode->Key PreNode ->Key) Swap(Jnode->Key,Jnode->PreNode->Key) Jnode = Jnode ->PreNode ; } Inode = Inode ->NextNode ; } return; } 151 4.3. Danh sách liên kết đôi 4.3.2.l. Sao chép 1 danh sách thành 1 danh sách mới Thuật toán B1: DLLInitialize(NewList) B2: CurrNode = DLLList.DLLFirst B3: IF (CurrNode == NULL) Thực hiện BKT B4: DLLAddLast(NewList, CurrNode->Key) B5: CurrNode = CurrNode ->NextNode B6: Lặp lại B3 BKT: Kết thúc 152 4.3. Danh sách liên kết đôi 4.3.2.l. Sao chép 1 danh sách thành 1 danh sách mới Cài đặt thuật toán DLLPType DLLCopy(DLLPType &DList, DLLPType &NewList) { DLLInitialize(NewList); DLLType CurrNode = DList.DLLFirst; while (CurrNode != NULL) { if (DLLAddLast(NewList, CurrNode->Key) == NULL) { DLLDelete(NewList); break; } CurrNode = CurrNode ->NextNode ; } return (NewList); } 153 4. Danh sách liên kết 4.4. Ưu nhược điểm của danh sách liên kết • Nhược điểm • Mật độ sử dụng bộ nhớ của danh sách liên kết không tối ưu tuyệt đối (<100%) • Việc truy xuất và tìm kiếm các phần tử trong danh sách liên kết mất nhiều thời gian vì phải duyệt tuần tự qua các phần tử trong danh sách. • Bộ nhớ cần nhiều vì phải lưu thêm phần tử liên kết, nếu vùng dữ liệu là lớn thì tỷ lệ mức sử dụng bộ nhớ là cao. • Ưu điểm • Tận dụng được không gian bộ nhớ nhỏ để lưu trữ từng nút. • Việc thêm, xóa phần tử trong danh sách liên kết là dễ dàng, chỉ cần thay đổi mối liên kết của các phần tử với nhau. 154 5. Danh sách hạn chế 5.1. Hàng đợi (Queue) 5.2. Ngăn xếp (Stack) 5.3. Ứng dụng của danh sách hạn chế 155 5. Danh sách hạn chế 5.1. Hàng đợi (Queue) • Hàng đợi là một danh sách mà trong đó thao tác thêm 1 phần tử vào trong danh sách được thực hiện 1 đầu này và lấy 1 phần tử trong danh sách lại thực hiện bởi đầu kia. • Các phần tử đưa vào trong hàng đợi trước sẽ được lấy ra trước, phần tử đưa vào trong hàng đợi sau sẽ được lấy ra sau. • Hàng đợi còn được gọi là danh sách FIFO List và cấu trúc dữ liệu này còn được gọi cấu trúc FIFO (First In First Out) • Có nhiều cách biểu diễn hàng đợi: dùng danh sách đặc hoặc dùng danh sách liên kết • Quản lý vị trí 2 đầu của hàng đợi thông qua 2 biến: • Biến trước (Font) • Biến sau (Rear) 156 5.1. Hàng đợi 5.1.1. Cấu trúc dữ liệu biểu diễn cho hàng đợi • Biểu diễn và tổ chức hàng đợi bằng danh sách đặc và danh sách liên kết đơn được quản lý bởi 2 phần tử đầu và cuối • Cấu trúc dữ liệu biểu diễn hàng đợi bằng danh sách đặc typedef struct QC { int Len; int Front, Rear; T * List; } CQUEUE; CQUEUE CQList; 157 5.1. Hàng đợi 5.1.1. Cấu trúc dữ liệu biểu diễn cho hàng đợi (tt) Cấu trúc dữ liệu biểu diễn hàng đợi bằng danh sách liên kết typedef struct QElement { T Key; QElement *Next; } QOneElement; typedef QElement *QType; typedef struct QPElement { QType Font; QType Rear; } SQUEUE; SQUEUE SQList; 158 5.1. Hàng đợi 5.1.2. Các thao tác trên hàng đợi tổ chức bằng danh sách đặc a. Khởi tạo hàng đợi (Initialize) b. Thêm 1 phần tử vào hàng đợi (Add) c. Lấy nội dung 1 phần tử trong hàng đợi ra xử lý (Get) d. Hủy hàng đợi 159 5.1. Hàng đợi 5.1.2.a. Khởi tạo hàng đợi (tổ chức bằng danh sách đặc) B1: CQList.Len = Length B2: CQList.List = new T[Length] B3: IF(CQList.List == NULL) Thực hiện BKT B4: CQList.Front = CQList.Rear = 0 BKT: Kết thúc 160 5.1. Hàng đợi 5.1.2.a. Khởi tạo hàng đợi (tổ chức bằng danh sách đặc) Cài đặt thuật toán T * CQInitialize (CQUEUE & QList, int Length) { QList.Len = Length; QList.List = new T[Length]; if (QList.List == NULL) return (NULL); QList.Front = QList.Rear =-1; return (QList.List); } 161 5.1. Hàng đợi 5.1.2.b. Thêm 1 phần tử vào hàng đợi (tổ chức bằng danh sách đặc) Thuật toán // nếu hàng đợi đã bị đầy B1: IF(CQList.Front ==1 AND CQList.Rear == CQList.Len) Thực hiện BKT B2: IF(CQList.Rear+1 == CQList.Front) Thực hiện BKT B3: IF(CQList.Front = 0) // nếu hàng đợi rỗng CQList.Front = 1 B4: IF(CQList.Rear = CQList.Len) CQList.Rear = 1 B5: ELSE CQList.Rear ++ B6: CQList.List[CQList.Rear] = NewData BKT: Kết thúc 162 5.1. Hàng đợi 5.1.2.b. Thêm 1 phần tử vào hàng đợi (tổ chức bằng danh sách đặc) Cài đặt thuật toán int CQAdd(CQUEUE & QList, T NewData) { if (QList.Front == 0 && QList.Rear == QList.Len -1) return (-1); if (QList.Rear +1 == QList.Front) return (-1); if (QList.Front == -1) QList.Front =0 if (QList.Rear == QList.Len) QList.Rear = 0; else QList.Rear += 1; QList.List[QList.Rear] = NewData return (QList.Rear ); } 163 5.1. Hàng đợi 5.1.2.c. Lấy nội dung 1 phần tử trong hàng đợi ra xử lý (tổ chức bằng danh sách đặc) B1: IF (CQList.Front = 0) Thực hiện BKT B2: Data = CQList.List[CQList.Front] B3: IF(CQList.Rear == CQList.Front) B3.1: CQList.Rear = CQList.Front = 0 B3.2: Thực hiện BKT B4: IF (CQList.Front = CQList.Len) CQList.Front = 1 B5: ELSE CQList.Front++ BKT: Kết thúc 164 5.1. Hàng đợi 5.1.2.c. Lấy nội dung 1 phần tử trong hàng đợi ra xử lý (tổ chức bằng danh sách đặc) Cài đặt thuật toán int CQGet(CQUEUE & QList, T &Data) { if (QList.Front == -1) return (-1); Data = QList.List[QList.Front]; if (QList.Front == QList.Rear) { QList.Front = QList.Rear = -1; return (1); } if (QList.Front == QList.Len -1) QList.Front = 0; else QList.Front += 1; return (1); } 165 5.1. Hàng đợi 5.1.2.d. Hủy hàng đợi (tổ chức bằng danh sách đặc) Hủy bộ nhớ cấp phát cho hàng đợi void CQDelete(CQUEUE & QList) { delete QList.List; return; } 166 5.1. Hàng đợi 5.1.3. Các thao tác trên hàng đợi tổ chức bằng danh sách liên kết đơn a. Khởi tạo hàng đợi (Initialize) b. Thêm 1 phần tử vào hàng đợi (Add) c. Lấy nội dung 1 phần tử trong hàng đợi ra xử lý (Get) d. Hủy hàng đợi 167 5.1. Hàng đợi 5.1.3.a. Khởi tạo hàng đợi (dùng danh sách liên kết đơn) Tương tự với danh sách liên kết đơn, hàm khởi tạo thực hiện gán con trỏ Front và Rear về NULL SQUEUE SQInitialize (SQUEUE &QList) { QList.Front = QList.Rear = NULL; return (QList); } 168 5.1. Hàng đợi 5.1.3.b. Thêm 1 phần tử vào hàng đợi (dùng danh sách liên kết đơn) Thêm phần tử vào sau phần tử Rear (Thêm vào cuối danh sách liên kết) Giả sử dữ liệu đưa vào hàng đợi là NewData B1: NewElement = SLLCreateNode(NewData) B2: IF (NewElement == NULL) Thực hiện BKT B3: IF (SQList.Front == NULL) // hàng đợi dang rỗng B3.1: SQList.Front = SQList.Rear = NewElement B3.2: Thực hiện BKT B4: SQList.Rear->Next = NewElement B5: SQList.Rear = NewElement BKT: Kết thúc 169 5.1. Hàng đợi 5.1.3.b. Thêm 1 phần tử vào hàng đợi (dùng danh sách liên kết đơn) Cài đặt thuật toán: QType SQAdd(SQUEUE &Qlist, T NewData) { QType NewElement = SLLCreateNode(NewData) if (NewElement == NULL) return (NULL); if (QList.Front == NULL) QList.Front = QList.Rear = NewElement; else { QList.Rear->Next = NewElement; QList.Rear = NewElement; } return(NewElement); } 170 5.1. Hàng đợi 5.1.3.c. Lấy nội dung 1 phần tử trong hàng đợi ra xử lý (dùng danh sách liên kết đơn) Lấy nội dung thành phần dữ liệu của phần tử ở địa chỉ Front ra biến Data và tiến hành hủy phần tử này B1: IF (SQList.Front == NULL) // nếu hàng đợi bị rỗng Thực hiện BKT B2: TempElement = SQList.Front; B3: SQList.Front = SQList.Front ->Next B4: TempElement ->Next = NULL B5: Data = TempElement ->Key B6: IF (SQList.Front == NULL) SQList.Rear == NULL B7: delete TempElement BKT: Kết thúc 171 5.1. Hàng đợi 5.1.3.c. Lấy nội dung 1 phần tử trong hàng đợi ra xử lý (dùng danh sách liên kết đơn) Cài đặt thuật toán int SQGet (SQUEUE &QList, T &Data) { if (QList.Front = NULL) return (-1); QType TempElement = QList.Front; QList.Front = QList.Front ->Next; TempElement ->Next = NULL; Data = TempElement ->Next ; if (QList.Front = NULL) QList.Rear = NULL; delete TempElement; return(1); } 172 5.1. Hàng đợi 5.1.3.d. Hủy hàng đợi (dùng danh sách liên kết đơn) void SQQueue (SQUEUE &QList) { QList.Rear = NULL; while (QList.Front != NULL) { QType TempElement = QList.Front; TempElement ->Next = NULL; delete TempElement; } return; } 173 5.2. Ngăn xếp (Stack) Ngăn xếp là một danh sách mà trong đó thao tác trên 1 phần tử vào trong ngăn xếp và thao tác lấy ra một phần tử được thực hiện 1 đầu. Các phần tử được đưa vào ngăn xếp sau cùng sẽ được lấy ra trước tiên, phần tử được đưa vào trước tiên sẽ được lấy ra sau cùng. Ngăn xếp được gọi là danh sách vào sau ra trước LIFO, cấu trúc dữ liệu này được gọi là cấu trúc LIFO. 5.2.1. Cấu trúc dữ liệu 5.2.2. Các thao tác trên ngăn xếp tổ chức bằng danh sách đặc 5.2.2. Các thao tác trên ngăn xếp tổ chức bằng danh sách liên kết 174 5.2. Ngăn xếp 5.2.1. Cấu trúc dữ liệu Biểu diễn và tổ chức bằng danh sách đặc typedef struct SC { int Size; int SP; T * List; } CSTACK; CSTACK CSList; Biểu diễn và tổ chức bằng danh sách liên kết typedef struct SElement { T Key; SElement *Next; } SOneElement; typedef struct SOneElement *SSTACK; SSTACK SSP; 175 5.2. Ngăn xếp 5.2.2. Các thao tác trên ngăn xếp tổ chức bằng danh sách đặc 5.2.2.a. Khởi tạo ngăn xếp (Initialize) 5.2.2.b. Thêm 1 phần tử vào ngăn xếp (Push) 5.2.2.c. Lấy nội dung 1 phần tử trong ngăn xếp ra xử lý (Pop) 5.2.2.d. Hủy ngăn xếp 176 5.2. Ngăn xếp 5.2.2.a. Khởi tạo ngăn xếp (dùng danh sách đặc) B1: CSList.Size = MaxSize B2: CSList.List = new T[MaxSize] B3: IF (CSList.List == NULL) Thực hiện BKT B4: CSList.SP = CSList.Size +1 BKT: Kết thúc T * CSInitialize(CSTACK &SList, int MaxSize) { SList.Size = MaxSize; SList.List = new T[MaxSize]; if (SList.List == NULL) return (NULL); SList.SP = SList.Size ; return (SList.List); } 177 5.2. Ngăn xếp 5.2.2.b. Thêm 1 phần tử vào ngăn xếp (dùng danh sách đặc) B1: IF (CSList.SP == 1) Thực hiện BKT B2: CSList.SP -- B3: CSList.List[CSList.SP] = NewData BKT: Kết thúc int CSPush(CSTACK &SList, T NewData) { if (SList.SP == 0) return (-1); SList.SP -= 1; SList.List[SList.SP] = NewData; return (SList.SP); } 178 5.2. Ngăn xếp 5.2.2.c. Lấy nội dung 1 phần tử trong ngăn xếp ra xử lý (dùng danh sách đặc) B1: IF (CSList.SP == CSList.Size +!) Thực hiện BKT B2: Data = CSList.List[CSList.SP] B3: CSList.SP++ BKT: Kết thúc int CSPop(CSTACK &SList, T &Data) { if (SList.SP == SList.Size) return (-1); Data = SList.List[SList.SP]; SList.SP += 1; return (1); } 179 5.2. Ngăn xếp 5.2.2.d. Hủy ngăn xếp (dùng danh sách đặc) int CSDelete(CSTACK &SList) { delete SList.SList; return; } 180 5.2. Ngăn xếp 5.2.2. Các thao tác trên ngăn xếp tổ chức bằng danh sách liên kết 5.2.3.a. Khởi tạo ngăn xếp (Initialize) 5.2.3.b. Thêm 1 phần tử vào ngăn xếp (Push) 5.2.3.c. Lấy nội dung 1 phần tử trong ngăn xếp ra xử lý (Pop) 5.2.3.d. Hủy ngăn xếp 181 5.2. Ngăn xếp 5.2.3.a. Khởi tạo ngăn xếp (dùng danh sách liên kết) SSTACK SSInitialize (SSTACK &SList) { SList = NULL; return (SList); } 182 5.2. Ngăn xếp 5.2.3.b. Thêm 1 phần tử vào ngăn xếp (dùng danh sách liên kết) B1: NewElement = SLLCreateNode(NewData) B2: if (NewElement == NULL) Thực hiện BKT B3: if (SSP == NULL) B3.1: SSP = NewElement B3.2: Thực hiện BKT B4: NewElement ->Next = SSP B5: SSP = NewElement BKT: Kết thúc 183 5.2. Ngăn xếp 5.2.3.b. Thêm 1 phần tử vào ngăn xếp (dùng danh sách liên kết) SSTACK SSPush (SSTACK &SList, T NewData) { SSTACK NewElement = SLLCreateNode(NewData); if (NewElement == NULL) return (NULL); NewElement ->Next = SList; SList = NewElement; return (NewElement); } 184 5.2. Ngăn xếp 5.2.3.c. Lấy nội dung 1 phần tử trong ngăn xếp ra xử lý (dùng danh sách liên kết) B1: if (SSP == NULL) Thực hiện BKT B2: TempElement = SSP B3: SSP = SSP ->Next B4: TempElement ->Next = NULL B5: Data = TempElement->Key B6: delete TempElement- BKT: Kết thúc 185 5.2. Ngăn xếp 5.2.3.c. Lấy nội dung 1 phần tử trong ngăn xếp ra xử lý (dùng danh sách liên kết) int SSPop (SSTACK &SList, T &Data) { if (SList == NULL) return (-1); SSTACK TempElement = SList; SList = SList ->Next; TempElement ->Next = NULL; Data = TempElement->Key; delete TempElement; return (1); } 186 5.2. Ngăn xếp 5.2.3.d. Hủy ngăn xếp (dùng danh sách liên kết) void SSDelete (SSTACK &SList) { while (SList != NULL) { SSTACK TempElement = SList; SList = SList ->Next; TempElement ->Next = NULL; delete TempElement; } } 187 5.2. Ngăn xếp 5.3. Ứng dụng của danh sách hạn chế • Hàng đợi dùng trong nhiều trường hợp lưu trữ dữ liệu cần xử lý tuần tự. • Ngăn xếp dùng trong việc xử lý dữ liệu truy hồi, đặc biệt trong việc xử lý đệ quy của các thuật giải. 188 BÀI TẬP CHƯƠNG 4 • Bài tập chương 4, giáo trình Cấu trúc dữ liệu và giải thuật (Trang 156 -157)