1. Khái niệm danh sách:
Danh sách là một dãy hữu hạn các phần tử thuộc cùng một lớp đối tượng nào đó. Chẳng hạn: Danh sách sinh viên một lớp, danh sách các số nguyên nào đó,… Thông thường mỗi đối tượng là một bản ghi có nhiều trường.
- Một danh sách có n phần tử được ký hiệu là
L(a¬1, a2,…, an)
- Nếu n>0 thì a1 được gọi là phần tử đầu danh sách, an là phần tử cuối- Nếu n=0 thì ta nói danh sách là rỗng(không có phần tử nào)
- Một tính chất quan trọng của danh sách là các phần tử được sắp tuyến tính: nếu n>1 thì ai là phần tử đứng trước ai+1
2. Một số phép toán cơ bản trên danh sách:
+ Phép toán khởi tạo danh sách rỗng
+ Thêm một phần tử vào đầu/cuối/sau phần tử có khoá=k cho trước
+ Loại bỏ phẩn tử đầu/cuối/sau hoặc trước ptử có khoá=k cho trước của danh sách
+ Duyệt danh sách, tìm kiếm trên danh sách
+ Sắp xếp danh sách
+….
3. Cài đặt danh sách:
Danh sách có thể được cài đặt bằng mảng hoặc bằng cấp phát động(danh sách liên kết)
- Trong cài đặt bằng mảng, Danh sách được khai báo như một mảng, mỗi phần tử của danh sách là một phần tử của mảng.
+ Ưu điểm: Dễ dàng truy xuất đến các phần tử của danh sách(vì thông qua phần tử của mảng)
+ Nhược điểm: Khó thực hiện các phép toán chèn thêm/loại bỏ. Vì chèn thêm một phần tử vào vị trí i ta phải dịch tất cả các phần tử từ i đến n sang phải một vị trí, hoặc khi loại bỏ phần tử thứ i ta phải dịch các phẩn tử từ i+1 đến n sáng trái 1 vị trí. Nếu danh sách luôn biến động thì sẽ rất tốn chi phí thời gian. Hơn nữa, độ dài của danh sách bị giới hạn bởi kích thước của mảng, khi số phần tử của danh sách ít thì lãng phí bộ nhớ, khi nhiều thì không được vượt quá kích thước mảng
- Cài đặt bằng danh sách liên kết: Mỗi phần tử sẽ được cấp phát bộ nhớ khi cần và các phần tử liên kết với nhau thông qua thành phần liên kết. Trong cách cài đặt này, mỗi phần tử là một Node gồm 2 phần:
+ Phần dữ liệu(data) dùng để lưu thông tin của chính phần tử
+ Phần liên kết: dùng để chứa địa chỉ của phần tử kế tiếp nó trong danh sách.
Sau đây ta xét cách cài đặt danh sách bằng Danh sách liên kết(để đơn giản ta dùng danh sách liên kết đơn) và để đơn giản ta giả thiết thành phần dữ liệu chỉ có một trường và kiểu là kiểu số nguyên
+ Ưu điểm: Tiết kiệm bộ nhớ, dễ dàng thực hiện các phép toán thêm/loại bỏ
+ Nhược điểm: Truy xuất chậm, để truy xuất được các phần tử trong danh sách, ta phải biết được địa chỉ của phần tử đầu tiên trong danh sách, sau đó dựa vào trường liên kết để đi đến các phần tử khác
4. Danh sách liên kết đơn
-Định nghĩa: Danh sách liên kết đơn là danh sách liên kết mà thành phần liên kết của mỗi phần tử chỉ có một trường dùng để chứa địa chỉ của phần tử kế tiếp sau nó trong danh sách, trường này thường gọi là con trỏ Next
- Cách tổ chức:
+ Cấu trúc một Node trên danh sách:
Mã:
typedef struct tagNode{
Data info;//Data là một kiểu dữ liệu đã được định nghĩa trước
struct tagNode *Next;
}Node;Để truy cập được đến các phần tử ta phải biết được địa chỉ của phần tử đầu sau đó dựa vào trường Next để đến các phần tử tiếp theo. Do đó ta luôn dùng một con trỏ Head(đầu) trỏ vào phẩn tử đầu.
Trong nhiều trường hợp ta cần làm việc ngay với phần tử cuối, vì vậy ta dùng thêm con trỏ luôn trỏ vào phần tử cuối của danh sách là Tail(cuối)
Như vậy, cấu trúc danh sách có dạng :
Mã:
typedef struct tagList{
Node *Head ;
Node *Tail ;
}List;Phép toán chèn đầu gọi là : AddHead
Chèn cuối gọi là : AddTail
5. Hàng đợi(Queue) :
- Định nghĩa : Hàng đợi là một dạng danh sách đặc biệt có hạn chế phép toán. Cụ thể chỉ có 2 phép toán là thêm một phần tử vào một đầu và lấy ra phần tử ở đầu kia của danh sách. Phép toán thêm vào được gọi là EnQueue và lấy ra được gọi là DeQueue
- Nguyên lý hoạt động : Phần tử nào được đưa vào trước thì được lấy ra trước. Hay còn gọi là First In – First Out(FIFO)
- Ứng dụng : Được ứng dụng rất nhiều, chẳng hạn dùng cho xử lý bộ đệm bàn phím (Phím nào gõ trước thì hiện lên màn hình trước).
- Cài đặt : Vì hàng đợi cũng là danh sách nên có thể được cài đặt bằng mảng hoặc bằng danh sách liên kết. Sau đây ta xét cách cài đặt bằng danh sách liên kết đơn
+ Cấu trúc một Node
Mã:
typedef struct tagNode{
Data info;//Data là một kiểu dữ liệu đã được định nghĩa trước
struct tagNode *Next;
}Node;Mã:
typedef struct tagList{
Node *Head ;
Node *Tail ;
}Queue;+ Khởi tạo Queue rỗng :
Mã:
void InitQueue(Queue &Q){
Q.Head=Q.Tail=NULL ;
}Mã:
int IsEmptyQueue(Queue Q){
if(Q.Head==NULL) return 1 ;
else return 0;
}void EnQueue(Queue &Q, Data v){
Node *P;
P=new Node;//Cấp phát bộ nhớ cho node P
If(P==NULL)return; //Hết bộ nhớ
P->info=v; //Cấp dữ liệu cho node P P->Next=NULL;//Node P không trỏ đi đâu cả
if(IsEmptyQueue(Q))Q.Head=P; //Nếu hàng đợi rỗng thì P vừa là Head vừa là Tail
else Q.Tail->Next=P; //Ngược lại link liên kết Tail tới node P
Q.Tail=P; // Bây giờ P là Tail
}Lấy một phần tử khỏi Queue(DeQueue) :
Data DeQueue(Queue &Q){
Node *P;
Data v;
if(IsEmptyQueue(Q))return NULLDATA;//NULLDATA là một hằng xác định rỗng
P=Q.Head;//P là Head Q.Head=P->Next; if(Q.Head==NULL)Q.Tail=Q.Head;
v=P->info; delete P; //Xóa node
return v;
}Mã:
Mã:
void printQ(Queue Q){
Node *P;
P=Q.Head ; //P là Head
while(P !=NULL){
print("%3d", P->info) ;
P=P->Next; //Link tới phần tử tiếp theo
}
}-Để đơn giản ta định nghĩa Data là kiểu nguyên:
Mã:
typedef int Data
Mã:
typedef struct tagSV{
int MaSV;
char TenSV[30];
char *QueQuan;
}SinhVien;Source: http://www.kmasecurity.net/xforce/ma-nguon/1245-quan-ly-queue-bang-danh-sach-lien-ket.html
//cac_thao_tac_voi_Queue_su_dung_danh_sach_lien_ket.h
#include<iostream>
/*:
void Init_Queue(Queue &Q); //Khoi tao Queue;
bool IsEmpty(Queue Q); //Kiem tra tinh rong cua queue
void EnQueue(Queue &Q, int v); //Chen them mot node vao queue
int DeQueue(Queue &Q); //Xoa mot node khoi Queue
void Print_Queue(const Queue &Q);// Duyet va in toan bo cac node cua queue
int Get_Queue(const Queue &Q); //Xem mot node cua queue ma khong lam thay doi no
*/
//Khai_bao_Queue thong qua Node
typedef struct TagNode
{
int Infor;
TagNode *Next;
}Node;
typedef struct TagList
{
Node *Head; //Tro vao dau cua hang doi
Node *Tail;//Tro vao cuoi hang doi
}Queue;
//Cac thao tac voi Queue
//Khoi tao
void Init_Queue(Queue &Q)
{
Q.Head = Q.Tail = NULL; //Khoi tao gia tri ban dau bang rong
}
//Kiem tra rong
bool IsEmpty_Queue(Queue Q)
{
if(Q.Head == NULL)
return 1; //Neu Queue rong tra ve 1
return 0; //Nguoc lai tra ve 0
}
void EnQueue(Queue &Q, int v)
{
//Khoi tao mot node de chen vao Queue
Node *P;
P = new Node; //Cap phat bo nho cho node
//Kiem tra xem HDH da cap phat bo nho cho node chua
if(P == NULL)
{
std::cout<<std::endl<<"Empty Memory. "<<std::endl;
return;
}
//Gan gia tri cho Node moi
P->Infor = v;
P->Next = NULL; //P khong tro di dau ca
if(IsEmpty_Queue(Q))
{
Q.Head = P; //Neu Q rong, P vua la Head vua la Tail
}
else
{
Q.Tail->Next = P; //Tao lien ket giua Q voi P
}
Q.Tail = P; //P la Tail;
}
int DeQueue(Queue &Q)
{
int v; //Luu gia tri cua node bi xoa
Node *P; //Tro den Node bi xoa
P = Q.Head; //P tro vao Head
if(IsEmpty_Queue(Q))return 0;
Q.Head = Q.Head->Next; // Head tro vao node sau cua no
v = P->Infor; // v luu lai gia tri node bi xoa
if(Q.Head ==NULL)Q.Tail = Q.Head;
delete(P); //Giai phong bo nho cho Head cu
return v; //Tra ve gia tri node bi xoa
}
int Get_Node( const Queue &Q)
{
int v;
v = Q.Head->Infor; //V luu gia tri cua node Head;
return v; //Tra ve gia tri node do
}
void Print_Queue(const Queue &Q)
{
Node *P; //P tro vao node duoc in ra
P = Q.Head; //Q.Head tro vao node Head
while(P !=NULL) //Trong khi Queue khong rong
{
std::cout<<" "<<P->Infor;
P = P->Next; //P tro vao node sau no
}
}
//Chuong trinh vi du su dung cac thao tac cua Queue#include"cac_thao_tac_voi_queue.h"#include<iostream>#include<conio.h>void Init_Queue(Queue &Q); //Khoi tao Queue;bool IsEmpty(Queue Q); //Kiem tra tinh rong cua queuevoid EnQueue(Queue &Q, int v); //Chen them mot node vao queueint DeQueue(Queue &Q); //Xoa mot node khoi Queuevoid Print_Queue(const Queue &Q);// Duyet va in toan bo cac node cua queueint Get_Queue(const Queue &Q); //Xem mot node cua queue ma khong lam thay doi noint main(){Queue Q;char c;int n;Init_Queue(Q);do{std::cout<<"Nhap 0 de thoat chuong trinh."<<std::endl<<"Nhap 1 de kiem tra tinh rong cua queue."<<std::endl<<"Nhap 2 de them mot node vao queue."<<std::endl<<"Nhap 3 de xoa mot node khoi queue."<<std::endl<<"Nhap 4 de duyet queue."<<std::endl;c = getch(); //Nhap mot ky tuswitch (c){case '0':{return 0;}case '1':{if(IsEmpty_Queue(Q))std::cout<<std::endl<<"Queue rong.";else std::cout<<std::endl<<"Queue khong rong.";system("pause");}break;case '2':{std::cout<<"Enter the value of new Node ";std::cin>>n;EnQueue(Q,n);}break;case '3':{std::cout<<"Xoa node "<<DeQueue(Q);system("pause");}break;case '4':{std::cout<<std::endl<<"Danh sach cua queue: ";Print_Queue(Q);std::cout<<std::endl;system("pause");}break;}system("cls");}while(1);}
.png)
.png)
.png)
0 comments:
Post a Comment