Chương 2: Cấu trúc dữ liệu danh sách

CẤU TRÚC DỮ LIỆU (BẬC CAO ĐẲNG) Nguyễn Thanh Cẩm BÀI GIẢNG KHOA KHOA HỌC MÁY TÍNH – BỘ MÔN LẬP TRÌNH Chương2: CẤU TRÚC DỮ LIỆU DANH SÁCH Danh sách Danh sách đặc Danh sách liên kết Ngăn xếp Hàng đợi NỘI DUNG TRÌNH BÀY 1 1. Danh sách Định nghĩa Các phép toán trên danh sách 1. Danh sách Danh sách là tập hợp hữu hạn các phần tửcùng kiểu (Elementtype) : a1, a2, …, an (n>=1) với tính chất: nếu biết được ai sẽ biết ai+1 (0 nào đó để thực hiện công việc Ví dụ: Phép tìm kiếm: là thao tác tìm phần tử trong danh sách thỏa mãn điều kiện nào đó Ví dụ: b. Các phép toán trên danh sách 1. Danh sách Thêm phần tử vào danh sách: là thao tác thêm phần tử mới Vào danh sách. Phần tử có thể được thêm vào cuối, đầu hoặc giữa danh sách.Chú ý danh sách đầy Ví dụ: b. Các phép toán trên danh sách 1. Danh sách Loại bỏ phần tử khỏi danh sách: là thao tác loại bỏ phần tử khỏi danh sách. Trước khi loại bỏ phải xác định phần tử cần loại bỏ (tìm kiếm).Chú ý: sau khi loại bỏ, số phần tử của danh sách giảm đi 1 đơn vị Ví dụ: b. Các phép toán trên danh sách 1. Danh sách Sửa đổi phần tử trong danh sách: là thao tác hiệu chỉnh phần tử trong danh sách. Trước khi hiệu chỉnh cần phải xác định phần tử cần hiệu chỉnh (tìm kiếm) Ví dụ: Sắp xếp thứ tự danh sách: là thao tác sắp lại thứ tự các phần tử trong danh sách theo một quy tắc nào đó Ví dụ: b. Các phép toán trên danh sách 1. Danh sách Tách một danh sách thành nhiều danh sách: là thao tác tách một phần hoặc tất cả các phần tử trong DS đưa sang các danh sách khác Vd: Ghép nhiều danh sách thành danh sách mới: là thao tác ngược lại của quá trình tách. Trộn nhiều danh sách thành danh sách mới b. Các phép toán trên danh sách 2. Danh sách đặc Định nghĩa Khai báo Các phép toán Đặc điểm của danh sách đặc 2. Danh sách đặc Danh sách đặc là danh sách mà các phần tử được sắp xếp kế tiếp nhau trong bộ nhớ, phần tử ai+1 đứng sau phần tử ai. Định nghĩa add[1] add[i] add[n]  d  add[i] = add[1] + (i-1)*d 2. Danh sách đặc #define MaxLength ... //Số nguyên thích hợp để chỉ độ dài của danh sách typedef ... ElementType; //kiểu của phần tử trong danh sách typedef int Position; //kiểu vị trí cuả các phần tử typedef struct { ElementType Elements[MaxLength]; //mảng chứa các phần tử của DS Position Last; //giữ độ dài danh sách } List; b. Khai báo Vd: 2. Danh sách đặc Khởi tạo danh sách rỗng Kiểm tra danh sách rỗng Tìm kiếm phần tử trong danh sách Chèn phần tử vào danh sách Loại bỏ phần tử khỏi danh sách c. Các phép toán 2. Danh sách đặc Khởi tạo danh sách rỗng c. Các phép toán void Make_List(List *L) { L->Last = 0; }  Trong đó Last chỉ vị trí của phần tử cuối cùng trong danh sách và đó cũng là độ dài hiện tại của danh sách 2. Danh sách đặc ii. Kiểm tra danh sách rỗng Danh sách rỗng là một danh sách mà độ dài của nó bằng 0.  int Empty_List(List L) { return L.Last == 0; } c. Các phép toán 2. Danh sách đặc iii. Chèn phần tử vào danh sách Giả sử ta chèn phần tử có nội dung x vào danh sách ở vị trí p. Khi đó các phần tử từ vị trí thứ p đến vị trí thứ last được di chuyển ra sau 1 đơn vị và độ dài danh sách tăng lên 1 đơn vị. c. Các phép toán 2. Danh sách đặc Giải thuật Chèn phần tử vào danh sách void Insert_List(ElementType X, Position P, List *L){ if (L->Last==MaxLength) printf("Danh sach day"); else if ((PL->Last)) printf("Vi tri khong hop le"); else{ Position i; for(i=L.Last; i>=p; i--) L->element[i+1]= L->element[i]; L->Elements[p]=X; L->Last++; } } c. Các phép toán 2. Danh sách đặc iv. Loại bỏ phần tử khỏi danh sách Để loại bỏ phần tử vị trí p ra khỏi danh sách L ta dời các phần tử từ vị trí p+1 đến cuối danh sách sang trái 1 vị trí. Lưu ý: độ dài của danh sách giảm đi 1 đơn vị c. Các phép toán 2. Danh sách đặc iv. Loại bỏ phần tử khỏi danh sách Giải thuật loại bỏ void Delete_List(Position P,List *L){ if ((PL->Last)) printf("Vi tri khong hop le"); else if (Empty_List(*L)) printf("Danh sach rong!"); else{ Position i; for(i=P;iLast;i++) L->Elements[i] = L->Elements[i+1]; L->Last--; } } c. Các phép toán 2. Danh sách đặc v. Tìm kiếm phần tử trong danh sách Trường hợp danh sách không thứ tự Position Search_List(ElementType X,List L){ Position found=0, i=0; if (Empty_List(L)) printf("Danh sach rong!"); else{ while (ilink;}} if(count==n) return q; else return NULL; } b. Các phép toán 2. Danh sách liên kết iv. Chèn phần tử vào danh sách Chèn ở đầu DS: void in_sert(ElementType x,List **T) {List *p; p=(List*)malloc(sizeof(List)); p->element=x; p->link=(*T);(*T)=p; } b. Các phép toán 2. Danh sách liên kết iv. Chèn phần tử vào danh sách Chèn ở cuối DS: void in_sert_C(ElementType x,List **T,List **S) {List *p; p=(List*)malloc(sizeof(List)); p->element=x; p->link=NULL; if(Empty((*T))) (*T)=(*S)=p; else{ (*S)->link=p;(*S)=(*S)->link;} } b. Các phép toán 2. Danh sách liên kết iv. Chèn phần tử vào danh sách Chèn ở giữa DS: void in_sert_G(ElementType x,int n,List **T) {List *p,*k; p=(List*)malloc(sizeof(List)); p->element=x; k=search(n,*T); p->link=k->link; k->link=p; } b. Các phép toán 2. Danh sách liên kết v. Xóa phần tử khỏi danh sách Xóa ở đầu danh sách: void Delete_T(List **T) {List *p; if((*T)!=NULL) { p=(*T);(*T)=p->link;delete(p); } } b. Các phép toán 2. Danh sách liên kết v. Xóa phần tử khỏi danh sách Xóa ở giữa danh sách: void Delete_G(int n,List **T) {List *p,*q; if(Empty(*T)) coutlink!=NULL) {q=p->link; p->link=q->link; free(q);} } } b. Các phép toán 2. Danh sách liên kết Ưu điểm - Thích hợp phép chèn, loại bỏ, trộn, ghép danh sách - Rất phù hợp với các loại danh sách có nhiều biến động c. Đặc điểm của danh sách liên kết 2. Danh sách liên kết ii. Nhược điểm - Tốn vùng nhớ cho chỉ điểm liên kết - Không thích hợp cho tìm kiếm c. Đặc điểm của danh sách liên kết Chúc các bạn thành công ! KHOA KHOA HỌC MÁY TÍNH – BỘ MÔN LẬP TRÌNH 2. Danh sách liên kết Viết thuật toán tạo danh sách liên kết chứa các số nguyên nhập từ bàn phím, sau đó hiển thị danh sách vừa tạo Viết thuật toán chèn phần tử vào danh sách liên kết sau vị trí n được nhập từ bàn phím Viết thuật toán xóa phần tử sau vị trí m trong danh sách liên kết Viết thuật toán đếm số nút trong danh sách liên kết Viết thuật toán tính giá trị trung bình của các phần tử trong danh sách Viết thuật toán đảo ngược một danh sách liên kết Viết thuật toán trộn 2 danh sách liên kết cho trước Bài tập 4. Ngăn xếp Định nghĩa Các phép toán trên ngăn xếp Tổ chức theo danh sách đặc Tổ chức theo danh sách liên kết Ứng dụng 4. Ngăn xếp Ngăn xếp (Stack) là danh sách mà việc thêm vào hoặc loại bỏ một phần tử chỉ thực hiện tại một đầu được gọi là đỉnh (TOP) của ngăn xếp. Theo nguyên tắc vào sau ra trước LIFO (last in - first out ) Định nghĩa 4. Ngăn xếp MAKE_STACK(S): Khởi tạo ngăn xếp. POP(S,x) lấy phần tử đỉnh của ngăn xếp gán cho x. PUSH(x,S) thêm một phần tử x vào đầu ngăn xếp. EMPTY_STACK(S) kiểm tra ngăn xếp rỗng. FULL_STACK(S): Kiểm tra ngăn xếp đầy b. Các phép toán trên ngăn xếp 4. Ngăn xếp Khai báo ngăn xếp #define MaxLength ... //độ dài của mảng typedef ... ElementType; //kiểu các phần tử trong ngăn xếp typedef struct { ElementType Elements[MaxLength]; int Top_idx; //giữ vị trí đỉnh ngăn xếp } Stack; c. Tổ chức theo danh sách đặc 4. Ngăn xếp Tạo ngăn xếp void Make_Stack(Stack *S){ S->Top_idx=MaxLength; } c. Tổ chức theo danh sách đặc 4. Ngăn xếp Kiểm tra ngăn xếp rỗng int Empty_Stack(Stack S){ return S.Top_idx==MaxLength; } c. Tổ chức theo danh sách đặc 4. Ngăn xếp Kiểm tra ngăn xếp đầy int Full_Stack(Stack S){ return S.Top_idx==0; } c. Tổ chức theo danh sách đặc 4. Ngăn xếp Chương trình con xóa phần tử ra khỏi ngăn xếp void Pop(Stack *S,int *y){ if (!Empty_Stack(*S)) { *y=S->Elements[S->Top_idx]; S->Top_idx=S->Top_idx+1;} else printf("Loi! Ngan xep rong!"); } c. Tổ chức theo danh sách đặc 4. Ngăn xếp Chương trình con thêm phần tử vào ngăn xếp : void Push(ElementType X, Stack *S){ if (Full_Stack(*S)) printf("Loi! Ngan xep day!"); else{ S->Top_idx=S->Top_idx-1; S->Elements[S->Top_idx]=X; } } c. Tổ chức theo danh sách đặc 4. Ngăn xếp Khai báo ngăn xếp typedef ... ElementType; typedef struct Node{ ElementType Element; struct Node *link;} Stack; d. Tổ chức theo danh sách liên kết 4. Ngăn xếp Tạo ngăn xếp: void Make_Stack(Stack **S) { (*S)=NULL; } d. Tổ chức theo danh sách liên kết 4. Ngăn xếp Kiểm tra ngăn xếp rỗng: int Empty_Stack(Stack *S) { return S==NULL; } d. Tổ chức theo danh sách liên kết 4. Ngăn xếp Thêm phần tử vào ngăn xếp void Push(int X, Stack **S) {Stack *p; p=(Stack*)malloc(sizeof(Stack)); p->Element=X; p->link=(*S);(*S)=p; } d. Tổ chức theo danh sách liên kết 4. Ngăn xếp Xóa phần tử ra khỏi ngăn xếp void Pop (Stack **S,int *y) {Stack *p; if((S)!=NULL) { *y=(*S)->Element; p=(*S);(*S)=p->link; delete(p); } } d. Tổ chức theo danh sách liên kết 4. Ngăn xếp Ứng dụng ngăn xếp để loại bỏ đệ qui của chương trình Thuật toán chuyển đổi cơ số Ký pháp nghịch đảo Ba lan e. Ứng dụng 4. Ngăn xếp Thuật toán chuyển đổi cơ số e. Ứng dụng Thuật toán này chuyển đổi biểu diễn cơ số 10 của một số nguyên dương Number sang cơ số 2 và hiển thị biểu diễn cơ số 2. Lặp lại các bước sau cho đến khi Number = 0: Tính số dư Remaider của phép chi Number cho 2 Đặt số dư remaider vào đỉnh ngăn xếp Thay Number bằng phần nguyên của kết quả phép Number chia cho 2 4. Ngăn xếp Thuật toán chuyển đổi cơ số e. Ứng dụng Thuật toán này chuyển đổi biểu diễn cơ số 10 của một số nguyên dương Number sang cơ số 2 và hiển thị biểu diễn cơ số 2. (2) Lặp lại các bước sau cho đến khi ngăn xếp số dư rỗng: Lấy ra remaider từ đỉnh ngăn xếp Hiển thị Remaider 4. Ngăn xếp Ký pháp nghich đảo Ba lan e. Ứng dụng Ví dụ: Biểu thức:A*(B+C) Được viết thành: A B C + * Biểu thức: (1+5)*(8-(4-1)) Được viết thành: 1 5 + 8 4 1 - - * 4. Ngăn xếp Ký pháp nghich đảo Ba lan e. Ứng dụng Khởi động ngăn xếp rỗng của các toán hạng: Lặp lại các bước sau cho đến khi gặp dấu kết thúc biểu thức được đọc: Đọc phần tử (hằng, biến, phần tử) 4. Ngăn xếp Ký pháp nghich đảo Ba lan e. Ứng dụng Nếu là toán hạng, đẩy vào ngăn xếp. Nếu là toán tử, thực hiện các bước sau: (i) lấy ra ngăn xếp 2 giá trị(nếu không lấy được hai toán hạng thì có lỗi biểu thức, kết thúc thuật toán) (ii) áp dụng toán tử trên vào hai giá trị vừa lấy (iii) đẩy kết quả vào ngăn xếp (c) Khi gặp dấu kết thức biểu thức, giá trị biểu thức là giá trị duy nhất ở đỉnh ngăn xếp. 4. Hàng đợi Định nghĩa Các phép toán cơ bản trên hàng Tổ chức theo danh sách đặc Tổ chức theo danh sách liên kết Ứng dụng 4. Hàng đợi Hàng đợi, hay ngắn gọn là hàng (queue) là danh sách mà phép thêm vào thực hiện tại một đầu gọi là cuối hàng (REAR), còn phép loại bỏ thì thực hiện ở đầu kia của danh sách, gọi là đầu hàng (FRONT). Hàng tuân thủ nguyên tắc vào trước - ra trước FIFO (first in - first out) Định nghĩa Hàng đợi 4. Hàng đợi MAKE_QUEUE(Q) khởi tạo một hàng. I_QUEUE(x,Q) thêm phần tử x vào cuối hàng Q. O_QUEUE(Q,y) lấy ra phần tử y tại đầu của hàng Q. EMPTY_QUEUE(Q) hàm kiểm tra hàng rỗng. FULL_QUEUE(Q) kiểm tra hàng đầy. b. Các phép toán cơ bản trên hàng 4. Hàng đợi Các khai báo cần thiết #define MaxLength ... //chiều dài tối đa của mảng typedef ... ElementType; //Kiểu dữ liệu của các phần tử trong hàng typedef struct { ElementType Elements[MaxLength]; //Lưu trữ nội dung các phần tử int Front, Rear; //chỉ số đầu và đuôi hàng } Queue; c. Tổ chức theo danh sách đặc 4. Hàng đợi Tạo hàng void Make_Queue(Queue *Q) { Q->Front=-1; Q->Rear=-1; } c. Tổ chức theo danh sách đặc 4. Hàng đợi Kiểm tra hàng rỗng int Empty_Queue(Queue Q) { return Q.Front==-1; } c. Tổ chức theo danh sách đặc 4. Hàng đợi Kiểm tra đầy Hàng đầy nếu số phần tử hiện có trong hàng bằng số phần tử trong mảng. int Full_Queue(Queue Q) { return (Q.Rear-Q.Front+1)==MaxLength; } c. Tổ chức theo danh sách đặc 4. Hàng đợi Xóa phần tử ra khỏi hàng Khi xóa một phần tử đầu hàng ta chỉ cần cho front tăng lên 1. Nếu front > rear thì hàng thực chất là hàng đã rỗng, nên ta sẽ khởi tạo lại hàng rỗng (tức là đặt lại giá trị front = rear =-1). c. Tổ chức theo danh sách đặc 4. Hàng đợi Xóa phần tử ra khỏi hàng void O_Queue(Queue *Q,int *x){ if (!Empty_Queue(*Q)) { *x=Q->Elements[Q->Front]; Q->Front=Q->Front+1; if (Q->Front>Q->Rear) Make_Queue(Q); } else coutFront=0; if (Q->Rear==MaxLength-1) { for(int i=Q->Front;iRear;i++) Q->Elements[i-Q->Front]=Q->Elements[i]; Q->Rear=MaxLength - Q->Front-1; Q->Front=0; } Q->Rear=Q->Rear+1; Q->Elements[Q->Rear]=X; } else coutFront= Q->Rear=NULL; } d. Tổ chức theo danh sách liên kết 4. Hàng đợi Kiểm tra hàng rỗng Hàng rỗng nếu Front trỏ đến NULL int Empty_Queue(Queue Q) { return (Q.Front==NULL); } d. Tổ chức theo danh sách liên kết 4. Hàng đợi Thêm một phần tử vào hàng void I_Queue(int X, Queue *Q) {Node *p; if(Q->Rear==NULL) { p=(Node*)malloc(sizeof(Node)); p->Element=X;p->Next=NULL; Q->Front=Q->Rear=p; }else {p=(Node*)malloc(sizeof(Node)); p->Element=X;p->Next=NULL; Q->Rear->Next=p; Q->Rear=p; } } d. Tổ chức theo danh sách liên kết 4. Hàng đợi Xóa một phần tử ra khỏi hàng void O_Queue(Queue *Q,int *x) { if (!Empty_Queue(*Q)) { *x=Q->Front->Element; Position T; T=Q->Front; Q->Front=Q->Front->Next; free(T); } else cout<<"Loi : Hang rong"; } d. Tổ chức theo danh sách liên kết 4. Hàng đợi Hàng đợi là một cấu trúc dữ liệu được dùng khá phổ biến trong thiết kế giải thuật. Bất kỳ nơi nào ta cần quản lí dữ liệu, quá trình... theo kiểu vào trước-ra trước đều có thể ứng dụng hàng đợi. Ví dụ rất dễ thấy là quản lí in trên mạng, nhiều máy tính yêu cầu in đồng thời và ngay cả một máy tính cũng yêu cầu in nhiều lần. Nói chung có nhiều yêu cầu in dữ liệu, nhưng máy in không thể đáp ứng tức thời tất cả các yêu cầu đó nên chương trình quản lí in sẽ thiết lập một hàng đợi để quản lí các yêu cầu. Yêu cầu nào mà chương trình quản lí in nhận trước nó sẽ giải quyết trước. e. Ứng dụng 4. Hàng đợi Một ví dụ khác là duyệt cây theo mức được trình bày chi tiết trong chương sau. Các giải thuật duyệt theo chiều rộng một đồ thị có hướng hoặc vô hướng cũng dùng hàng đợi để quản lí các nút đồ thị. Các giải thuật đổi biểu thức trung tố thành hậu tố, tiền tố. e. Ứng dụng Chúc các bạn thành công ! KHOA KHOA HỌC MÁY TÍNH – BỘ MÔN LẬP TRÌNH Bài tập Ngăn xếp & Hàng đợi Viết chương trình dùng ngăn xếp để chuyển một số thập phân sang số nhị phân Dùng các hàm cơ bản trên ngăn xếp như: MAKE_STACK(S), POP(S,x), PUSH(x,S), EMPTY_STACK(S), FULL_STACK(S Lấy ra phần tử đáy của ngăn xếp, nhưng để lại nguyên nội dung của ngăn xếp Lấy ra phần tử thư n của ngăn xếp, nhưng để lại nguyên nội dung của ngăn xếp. Dùng các hàm cơ bản trên hàng đợi như: MAKE_QUEUE(Q), I_QUEUE(x,Q), O_QUEUE(Q,y), EMPTY_QUEUE(Q), Lấy ra phần tử ởcuối hàng đợi, nhưng để lại nguyên nội dung của hàng đợi. Lấy ra phần tử thứ n của hàng đợi, nhưng để lại nguyên nội dung của hàng đợi. Dùng các phép toán cơ bản trên hàng đợi và ngăn xếp. Viết chương trình đảo ngược các phần tử của hàng đợi.