ctdlvagt
Sắp xếp tìm kiếm
Sắp xếp lựa chọn (selecttion-sort)
Đặt phần tử nhỏ nhất là a[0] so sánh a[0] lần lượt với các phần tử khác để tìm vị trí nhỏ nhất, sau đó hoán vị phần tử đó với a[0] ta có phần tử nhỏ nhất là phần tử đầu tiên bên trái
Void SelectionSort(int a[], int n){
for(int i=0;i<n-1;i++) {
int k=i;
for(int j=i+1;j<n;j++)
if(a[k]>a[j]) k=j;
if(k!=i) {
int temp = a[i];
a[i]=a[k];
a[k]=temp;
}
}
}
Độ phức tạp O(n2)
Sắp xếp chèn (insertion-sort)
Xem phần tử đầu tiên bên trái nằm trong ds mới đã dc sx, sau đó chèn lần lượt từng pt của ds chưa dc sx vào ds đã dc sx sao cho vẫn giữ nguyên thứ tự sx.
Void InsertionSort(int a[], int n){
int j,x,i;
for(i=1;i<n;i++){
x =a[i];
j=i-1;
while((j>=0)&&(a[j]>x)){
a[j+1] = a[j];
j-- ;
}
a[j+1] = x;
}
}
Sắp xếp nổi bọt (Bubble-sort)
Cho pt nhỏ nhất nổi lên vị trí thứ 0, pt nhỏ kế tiếp nổi lên vị trí thứ 1,…n
Void BubbleSort(int a[], int n){
for(int i=0;i<n-1;i++){
for(int j=n-1;j>i;j--){
if(a[j]<a[j-1]){
int temp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
}
}
}
Sắp xếp nhanh
void quickSort(int a[], int l, int r){
int x,i,j,temp;
i=l; j=r; x=a[(l+r)/2];
while(i<=j
while(a[i]<x) {i++;}
while(a[j]>x) {j--;}
if(i<=j){
temp=a[i]; a[i]=a[j]; a[j]=temp;
i++; j--;
}
}
if(l<j){ quickSort(a,l,j)}
if(i<r){ quickSort(a,i,r); }
}
Tìm kiếm tuần tự
int search(int a[], int x) {
for(int i=0;i<n;i++) {
if(a[i]==x) return i;
}
return 0;
}
Tìm kiếm nhị phân
int search(int *a, int x){
int k, i=0,j=n-1;
while(i<=j){
k = (i+j)/2;
if(a[k]==x) return k;
if(a[k]>x) j=k-1;
else i=k+1;
}
return 0;
Ngăn xếp (Stack)
Là trường hợp đặt biệt của danh sách trong đó người ta chỉ thực hiện 2 thao tác chính là thêm vào và lấy ra 1 pt tại 1 đầu của danh sách (LIFO)
Cài đặt ngăn xếp bằng mảng
#define MAX 100
Typedef struct {
int top;
int a[MAX];
} stack;
Hàm khởi tạo:
Void init(stack &s){
s.top = -1;
}
Hàm kiểm tra đầy
int isfull(stack &s){
Return(s.top == max -1);
}
Hàm kiểm tra rỗng
int isEmpty(stack &s){
Return(s.top == -1);
}
Hàm thêm dữ liệu
Void Push(stack &s, int x){
If( isfull(s) ) return;
s.a[++s.top] = x;
}
Hàm lấy dữ liệu
int Pop(stack &s){
If( isEmpty(s) ) return;
Return(s.a[s.top--] ) ;
}
Cài đặt ngăn xếp bằng danh sách liên kết
Typedef struct node {
int item;
struct node *next;
} *stacknode;
Typedef struct{
stacknode top;
} stack;
Trong cài đặt ngăn xếp bằng ds liên kết không có hàm kiểm tra đầy vì danh sách liên kết tận dụng được bộ nhớ
Hàm khởi tạo
Void init(stack *s){
s->top = null;
}
Hàm kiểm tra rỗng
Int isEmpty(stack *s){
Return(s->top == null);
}
Hàm thêm dữ liệu
Void Push(stack *s, int x){
Stacknode q;
q= ( stacknode )malloc( sizeof (structnode) );
q->item =x;
q->next = s->top;
s->top =q;
}
Hàm lấy dữ liệu
int Pop(stack *s){
if(isEmpty(s) ) return -1;
stacknode q = s->top;
x = (s->top)->item;
s->top = (s->top)->next;
Free(q);
Return x;
}
Ứng dụng ngăn xếp
3.1: Chuyển trung tố thành hậu tố
Void chuyenHauTo(char a[] ){
Stack s;
Init(s);
For(int i = 0; i<=strlen(a); i++){
If( ‘0’ <=a[i] && a[i]<=’9’ )
Cout<<a[i];
If( a[i] ==’+’ || a[i] ==’-’ || a[i] ==’*’ || a[i] ==’/’ )
Push(s,a[i]);
If( a[i] = ‘)’ )
Cout<<pop(s);
}
}
3.2:Tính hậu tố
int tinhHauTo(char a[]){
stack s;
init(s);
For(int i = 0; i<=strlen(a); i++){
If( ‘0’ <=a[i] && a[i]<=’9’ )
Push(s, a[i]);
Else{
Int y = pop(s);
Int x = pop(s);
If(a[i]==’+’) push(s,x+y);
If(a[i]==’-’) push(s,x-y);
If(a[i]==’*’) push(s,x*y);
If(a[i]==’/’) push(s,x/y);
}
}
Return pop(s);
}
3.3: Chuyển cơ số
Void Convert(int a, int b){
Stack(s);
Init(s);
Do{
Push(s, a%b);
a=a/b
}
While(a!= 0)
While( !IsEmpty(s)) printf(“%X”, Pop(s) );
}
Hàng đợi (Queue)
Là trường hợp đặt biệt của danh sách trong đó người ta chỉ thực hiện 2 thao tác cơ bản là thêm 1 phần tử vào đầu và lấy ra phân tử tại đầu kia
Cài đặt hàng đợi bằng mảng
#define MAX 100
Typedef struct {
Int head, count, tail;
Int a[MAX];
} Queue;
Hàm khởi tạo:
Void init(Queue &q){
q.tail = -1;
q.head = 0;
q.count = 0;
}
Hàm kiểm tra đầy
int isfull(Queue &q){
Return(q.count ==MAX);
}
Hàm kiểm tra rỗng
int isEmpty(Queue &q){
Return(q.count ==0);
}
Hàm thêm dữ liệu
Void Push(Queue &q, int x){
If( Isfull(q) ) return -1;
q.count ++;
q.tail ++;
if(q.tail == MAX) q.tail = 0;
q.a[q.tail] = x;
}
Hàm lấy dữ liệu
int Pop(Queue &q){
If( IsEmpty(q) ) return -1;
q.count --;
q.head ++;
if(q.head == MAX) q.head = 0;
x = q.a[q.head];
Return x;
}
Cài đặt hàng đợi bằng danh sách liên kết
Typedef struct node {
int item;
struct node *next;
} *Queuenode;
Typedef struct{
Queuenode head, tail ;
} Queue;
Hàm khởi tạo
init (Queue *q){
q->head = null;
q->head = null;
}
Hàm kiểm tra rỗng
int isEmpty(Queue *q){
Return(q->head == null);
}
Hàm thêm dữ liệu
Void Push(Queue *q, int x){
Queuenode r;
r= ( Queuenode )malloc( sizeof (structnode) );
r->item =x;
r->next = null;
if( isEmpty(*q) )
q->tail = r
q->head = r;
return;
(q->tail)->next = r;
q->tail = r;
}
Hàm lấy dữ liệu
int Pop(Queue *q){
if(isEmpty(*q)) return -1;
Queuenode r;
r = q->head;
q->head =( q->head)->next;
x = (q->head) ->item;
Free(r);
Return x;
}
Ứng dụng của hàng đợi
3.1: Thuật toán tìm kiếm theo chiều rộng:
Void BFS(int u){
Queue q;
init(q);
chuaxet[u] = 0;
cout<<u<<”” “”;
Push(q,u);
While(!isEmpty(q)){
int v = pop(s);
for(int i = 1; i<=n;i++){
if( a[u][i]&&chuaxet[i] )
push(q,i);
chuaxet[i]=0;
cout<<i<<”” “”;
}
}
}
Cây nhị phân – danh sách liên kết
Danh sách liên kết đơn
Danh sách liên kết là cấu trúc dữ liệu dùng để lưu trữ một tập các dữ liệu có cùng kiểu và các dữ liệu này được lưu trữ không liên tiếp trong bộ nhớ. Mỗi nút (phần tử) trên danh sách sẽ giữ địa chỉ của nút kế tiếp, khi đó chỉ cần biết địa chỉ nút đầu tiên là có thể truy xuất đến tất cả các nút.
+ Ưu điểm:
Thao tác hủy hoặc chèn nút nhanh vì không phải thực hiện thao tác dời.
Số nút không cố định, có thể cấp phát thêm nút hoặc thu hồi bộ nhớ đã cấp phát cho nút nên chương trình dễ mở rộng và sử dụng bộ nhớ được tối ưu.
Kích thước danh sách liên kết không bị hạn chế bởi 64KB, chỉ bị giới hạn bởi bộ nhớ dành cho chương trình.
+ Khuyết điểm:
Tìm kiếm dữ liệu chậm vì phải dò tìm từ đầu danh sách (tìm tuyến tính).
Tốn thêm bộ nhớ để lưu trữ địa chỉ nút kế.
Typedef struct node {
int item;
struct node *next;
} *listnode;
Chèn trước
Void insertBegin( listnode *p, int x ){
Listnode q;
q = ( listnode )malloc( sizeof (structnode) );
q->item = x;
q->next = *p;
*p= q;
}
Chèn sau:
Void insertEnd(listnode *p, int x){
Listnode q, r;
q = ( listnode )malloc( sizeof (structnode) );
q->item =x;
q->next = null;
if(*p == null ) *p=q;
else
r = *p;
while(r->next != null){
r=r->next;
r->next = q;
}
}
Chèn tại vị trí nào đó
Void insertMiddle(listnode *p, int position, int x){
Listnode q, r;
Int count = 1, found = 0;
r = *p;
while(r!=null){
if(count == position){
q = ( listnode )malloc( sizeof (structnode) );
q->item =x;
q->next = r->next;
r->next = q;
found = 1;
}
r=r->next;
count ++;
}
}
Xóa trước
Void removeBegin(listnode *p){
Listnode q;
If(*p == null) return;
q=*p;
*p = *p->next;
q->next = null;
Free(q);
}
Xóa sau:
Void removEnd(listnode *p){
If(*p->next ==null){
Free(*p);
*p=null;
Return;
}
If(*p == null) return;
Listnode q, r;
r=*p;
while(r->next!=null){
q=r;
r=r->next;
}
q->next = null;
Free(r);
}
Xóa tại vị trí nào đó:
Void removeMiddle(listnode *p, int position){
Listnode q, r;
int count = 1, found =0;
r=*p;
while(r!=null && found = 0){
if(count == position ){
q=r->next;
r->next = q->next;
q->next = null;
Free(q);
Found = 1;
}
Count ++;
r=r->next;
}
}
Cây nhị phân thông thường
Cây là cấu trúc dữ liệu dùng để lưu trữ một tập các dữ liệu có cùng kiểu và các dữ liệu này được lưu trữ không liên tiếp trong bộ nhớ. Mỗi nút (phần tử) trên cây sẽ giữ địa chỉ của nút con bên trái và địa chỉ của nút con bên phải, khi đó chỉ cần biết địa chỉ nút gốc (nút không là con của bất kỳ nút nào) là có thể truy xuất đến tất cả các nút.
Struct node {
int info;
node *left, * right;
};
Hàm tạo 1 nút
Node * make_node(int x){
node *p= new node;
p-> info =x;
p->left=p->right=NULL;
return p;
}
Tạo gốc
Void taogoc(node *&proot,int x){
Proot = make_node(x);
}
Thêm 1 nút trái vào bên trái node (Tương tự cho bên phải)
Void themtrai(node *&p, int x){
If(p->left != null) return;
Node *q = make_node(x);
p->left = q;
}
Xóa 1 node lá bên trái
Hàm kiểm tra có phải nút lá:
int nutla(node *p){
if(p->left == null && p->right ==null) return 1;
return 0;
}
Void xoatrai(node *p){
If(p->left==null) return;
If(!nutla(p->left)) return;
Node *q = p->left;
p->left = null;
delete q;
}
Cây nhị phân tìm kiếm
Hàm tìm nút
node* search(node* proot,int x) {
node* p;
if(proot==NULL) return NULL;
if(proot->info==x) return proot;
if(x<proot->info) p=search(proot->left,x);
else p=search(proot->right,x);
return p;
};
Hàm chèn nút
void insert(node* &proot,int x){
if(proot==NULL) {
proot=makenode(x); return;
}
if(search(proot,x)){
cout<<endl<<"Nut da co, khong them duoc!";return;
}
if(x<proot->info) insert(proot->left,x);
else insert(proot->right,x);
}
void insert2(node * &proot, int x)
{if(proot==NULL) {proot=makenode(x);return;}
if(search(proot,x)) {cout<<endl<<"Nut da co, khong them duoc!";return;}
node *fp, *p, *q; // fp la nut cha cua p, q la nut them vao
// Khoi dong cac gia tri
fp = NULL;
p = proot;
//tim nut fp, ya va fya, nut moi them vao la nut la con cua nut fp
while(p!=NULL)
{if(x<p->info)
{fp=p;p=p->left;} else {fp=p;p=p->right;}
} //end of while(p!=NULL)
/*Sau vong lap tren day thi nut p bi rong, con nut fp la nut can them
nut co noi dung x.*/
//Them nut q co noi dung x la con cua fp.
q = makenode(x);
if(x < fp->info) fp->left = q; else fp->right = q;
//Tao nut la moi co noi dung x
}
Hàm hủy cây
void del_tree(node *&proot){
if(proot!=NULL){
del_tree(proot->left);
del_tree(proot->right);
delete proot;
proot=NULL;
}
}
Hàm hủy nút
void remove(node *&proot, int x)
{node *fp,*p,*f,*rp,*q; /*rp la nut thay the cho nut p co noi dung x,
f la nut cha cua nut thay the rp*/
p=search2(proot,fp,x); //fp la nut cha cua nut p
if(p==NULL) {cout<<"Khong tim thay nut x";return;}
//Nut la
if(p->right==NULL && p->left==NULL)
{if(p==proot) {delete proot;proot=NULL;return;}
if(fp->left==p) {fp->left=NULL;delete p;return;}
if(fp->right==p) {fp->right=NULL;delete p;return;}
};
//Nut chi co mot cay con trai
if(p->left!=NULL && p->right==NULL)
{if(fp->left==p) {fp->left=p->left;delete p;return;}
if(fp->right==p) {fp->right=p->left;delete p;return;}
}
//Nut chi co mot cay con phai
if(p->left==NULL && p->right!=NULL)
{if(fp->left==p) {fp->left=p->right;delete p;return;}
if(fp->right==p) {fp->right=p->right;delete p;return;}
};
//Nut p co 2 nut con
//Tim nut thay the, la nut phai nhat cua cay con trai
f=p;
rp=p->left;
while(rp->right!=NULL) {f=rp;rp=rp->right;}
f->right=rp->left;/*rp la phai nhat, do do khong co con phai
vi khong con rp nen nut cha phai chi den nut sau do*/
p->info=rp->info;
//doi noi dung cua p va rp, roi xoa rp
delete rp;
}
Hàm duyệt cây
void NLR(node *proot){ // duyệt trước
if (proot!=NULL){
printf("%d ",proot->data);
NLR(proot->left);
NLR(proot->right);
}
}
void LNR(node *proot){ // duyệt giữa
if (proot!=NULL){
LNR(proot->left);
printf("%d ",proot->data);
LNR(proot->right);
}
}
void LRN(node *proot){ // duyệt sau
if (proot!=NULL){
LRN(proot->left);
LRN(proot->right);
printf("%d ",proot->data);
}
}
Đồ thị
Duyệt theo chiều sâu (Tìm kiếm theo chiều sâu DFS)
Dùng đệ quy:
Void DFS(int u){
Cout << u;
Chuaxet[u]=0;
For(int i =0; i<=n; i++){
DFS(i);
}
}
Dùng stack
Void DFS(int u){
Stack s;
Init(s);
Push(s,u);
Chuaxet[u]=0;
Cout <<u;
While(! isEmpty(s) ){
Int x = pop(s)
For(int i = 0; i<=n; i++){
If(chuaxet[i]&&a[u][i])
Cout<<i;
Chuaxet[i]=0;
Push(s,i);
Push(s,u)
}
}
Break;
}
Kiểm nghiệm thuật toán theo chiều sâu dưới dạng ma trận kề:
1 2 3 4 5 6 7 8 9 10
1 0 1 0 0 1 0 1 0 0 0
2 1 0 1 1 0 0 0 0 0 0
3 0 1 0 0 0 1 0 1 1 0
4 1 0 0 0 0 0 0 0 0 0
5 0 1 0 0 1 0 0 0 0 0
6 0 0 1 0 0 0 0 0 0 1
7 1 1 0 0 0 0 0 0 0 0
8 0 0 1 1 0 0 0 0 0 0
9 0 0 0 0 0 1 1 0 0 0
10 0 0 0 0 0 0 0 0 1 0
Các bước duyệt và trạng thái stack (duyệt theo chiều sâu DFS) cho u=5
Stack
5
52
521
5217
521
52
523
5236
5 2 3 6 10
5 2 3 6 10 9
5 2 3 6 10
5 2 3 6
5 2 3
5 2 3 8
5 2 3 8 4
Đỉnh đã duyệt
5 // dò dòng 5 trên ma trận nếu gặp 1 thì lấy giá trị của cột: là 2
52 // sau khi lấy dc 2 thì ghi vào rồi dò dòng 2
521
5217 // nếu dò dòng 7 ko có giá trị nào bỏ 7 rồi dò 1, nếu 1 ko có bỏ 1 dò 2…
5217
5217
52173
521736
5 2 1 7 3 6 10
5 2 1 7 3 6 10 9
5 2 1 7 3 6 10 9
5 2 1 7 3 6 10 9
5 2 1 7 3 6 10 9
5 2 1 7 3 6 10 9 8
5 2 1 7 3 6 10 9 8 4
Duyệt với u =5 được kq: 5 2 1 7 3 6 10 9 8 4
Các bước duyệt và trạng thái queue (duyệt theo chiều rộng BFS) cho u=5
queue
5
2
1 3 4
3 4 7
4 7 6 8 9
7 6 8 9
6 8 9
8 9 10
9 10
10
Đỉnh đã duyệt
5
52 // dò 5 được 2 và 5 lấy cả 2 và 5
5 2 1 3 4 // dò 2 lấy 1 3 4
5 2 1 3 4 7 // dò 1 lấy 7, 5 đã có ko lấy
5 2 1 3 4 7 6 8 9
5 2 1 3 4 7 6 8 9
5 2 1 3 4 7 6 8 9
5 2 1 3 4 7 6 8 9 10
5 2 1 3 4 7 6 8 9 10
5 2 1 3 4 7 6 8 9 10
Duyệt với u =5 được kq: 5 2 1 3 4 7 6 8 9 10
Bạn đang đọc truyện trên: Truyen2U.Net