Ôn cấu trúc dữ liệu & giải thuật

Dark Blog 15:57 Tin học No comments

Tìm kiếm tuyến tính:

int linearnsearch(int a[], int N, int x)

{

int i=o;

while((i<N)&&(a[i]==x))

i++;

if(i==N) return -1;//không tìm thấy x: không hiểu sao lại return -1

else return i;//tìm thấy x:không hiểu

}

int find(int a[],int n,int x)

{

Int I;

For(i=0;i<n;i++)

{

If(a[i]==x)

Return I;

}

Return 0;

}

Giải thuật tìm kiếm nhị phân

Phương pháp sử dụng vòng lặp:
int BinarySearch(int A[],int value, int N) {
/*1*/    low = 0;
/*2*/    high = N;
            int mid;
/*3*/    while (low < high) {
/*4*/       mid = (low + high)/2;
/*5*/        if (A[mid] < value)
/*6*/            low = mid + 1;
            else
/*7*/             high = mid;
            }
/*8*/    if ((low < N) && (A[low] == value))
/*9*/        return low; // tim thay
           else
/*10*/       return -1;  // Khong tim thay
}
Các lệnh /*1*/, /*2*/, /*3*/, /*9*/, /*10*/  tốn thời gian O(1) ;
Các lệnh  /*4*/,/*5*/, /*6*/, /*7*/  tốn thời gian O(1), lồngtrong vòng lặp /*3*/;
    Vòng lặp /*3*/trong trường hợp xấu nhất  sẽ chạy n=2klần( vị mỗi lần chạy mãng sẽ chia làm 2)  k=log(n) nên độ phức tạp là O(logn).
Vậy độ phức tạp của giải thuật là Max{ O(1), O(logn)}=O(logn).

Phương pháp sửdụng đệ quy:
int BinarySearch(int A,int value,int low,int high) {
       int mid;
       if (high < low)
           return -1 ;// khong tim thay
       mid = (low + high)/2;
       if (A[mid] > value)
           return BinarySearch(A, value, low, mid-1);
       else if (A[mid] < value)
          return BinarySearch(A, value, mid+1, high);
             else
                return mid; // tim thay   }
Khi mảng có chiều dài là 1, thì tathực hiện lệnh gán và return nên T(1)=1
Khi mảng có chiều dài lớn hơn 1,ta thực hiện lệnh T(n/2)+1: thực hiện lệnh search với n/2 chiều dài; và lệnhgán O(1), lệnh if O(1).
Do đó, ta có phương trình đề quy:
T(n) = 1                nếu n=1     (1)
T(n) = T(n/2) + 1  nếu n>1   (2)
Giải (2) : T(n)= T(n/2) + 1
               T(n) = T(n/4) + 2
               T(n) = T(n/8) + 3
               …………………
               T(n) = T(n/2i ) + i
Giải thuật kết thúc khi  n/2i =1 => n= 2i    => i=logn . Khi đó T(n)= T(1) + logn
Vậy T(n) = O(logn)

I - Giảt thuật Selection sort
Nội dung của phương pháp này là lần lượt chọn 1 phần tử nhỏ nhất trong dãy chỉ số k1, k2, …, kn với i=0,1…,n; ki¬<ki+1<….,kn và đổi chỗ cho phần tử thứ ki. Như vậy sau j=n-1 lần chọn chúng ta dãy khoá được sắp xếp tăng dần. Các bước thực hiện như sau:
• Lần chọn thứ 0: Tìm trong khoảng từ 0 đến n-1 bằng cách thực hiện n-1 lần so sánh để xác định phần tử min0 và đổi chỗ cho phần tử ở vị trí 0
• Lần chọn thứ 1: Tìm trong khoảng từ 1 đến n-1 bằng cách thực hiện n-2 lần so sánh để xác định phần tử min1 và đôỉ chỗ cho phần tử vị trí 1
• …………………….
• Lần chọn thứ i : tìm trong khoảng từ i đến n-1 bằng cách thực hiện n-i lần so sánh để xác định phần tử mini và đổi chỗ cho phần tử vị trí thứ i
• Lần chọn thứ n-2: Tìm trong khoảng n-2 đến n-1 bằng cách thực hiện 1 lần so sánh để xác định phần tử min(n-2) và đổi chỗ cho phần tử vị trí thứ n-2
Độ phức tạp của thuật toán này là:
Cmin=Cmax=Ctb=n(n-1)/2
Chính vì thế nên thuật toán có tên là sắp xếp lựa chọn
Cài đặt thuật toán trên tập số nguyên như sau:

Code:

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#include<alloc.h>

#include<dos.h>

void Select(int *, int);

void Init(int *, int);

void In(int *, int);

void Init(int *A, int n){

int i;

printf("\n Tao lap day so:");

for (i=0; i<n;i++){

A[i]=random(1000);

printf("%5d",A[i]);

}

delay(1000);

}

void Select(int *A, int n){

for(i=0;i<n-1;i++){

for (j=i+1;j<n;j++){

if(A[i]>A[j]){

temp=A[i];

A[i]=A[j];

A[j]=temp;

}

In(A,n);

}

void In(int *A, int n){

for(i=0;i<n;i++)

printf("%5d",A[i]);

delay(1000);

}

void main(void){

int *A,n;clrscr();

printf("\n Nhap n="); scanf("%d",&n);

A=(int *) malloc(n*sizeof(int));

Init(A,n);Select(A,n);

free(A);

}

thu gọn lại ý kiến của bạn cho dễ hiểu hơn :

Code:

void selectionSort( int list[], int last )

{

int smallest;

int temp,current,walk;

for ( current = 0 ; current < last ; current++ ) // Scan all items in array

{

smallest = current;

for ( walk = current + 1 ; walk <= last ; walk++ ) // sort

if ( list[walk] < list[smallest] ) smallest = walk; //exhange if it is suitable

temp = list[current];

list[current] = list[smallest];

list[smallest] = temp;

}

return;

}

II- Giải thuật Insertion sort

Giải thuật này dựa trên kinh nghiệm của những nguời chơi bài. Khi trên tay có i-1 lá bài đã được sắp xếp dang trên tay, nay ta thêm lá bài thứ i thì lá bài đó với là bài i-1, i-2,… để tìm được vị trí thích hợp để chèn vào cho đúng thứ tự.
Với nguyên tắc sắp xếp như trên thì giải thuật sắp xếp như sau:
• Lấy phần tử đầu tiên i0 làm khởi tạo
• Lấy tiếp phần tử i1 chọn vị trí thích hợp của phần tử i1 trong tập 2 phần tử và thực hiện đổi chỗ .
• ……………….
• Lấy tiếp phần tử thứ ik, chọn vị trí thích hợp của phần tử ik trong tập k+1 phần tử và thực hiện đổi chỗ.
• Dãy sẽ được sắp xếp hoàn toàn sau n-1 bước chèn.
Độ phức tạp bé nhất là : Cmin = n-1
Độ phức tạp lớn nhất là : n(n-1)/2 = O(n^2)
Độ phức tạp trung bình là: (n^2+n-2)/4=O(n^2)
Thuật toán được cài đặt như sau: (Trên tập mẫu là số nguyên)

Code:

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <alloc.h>

#include <dos.h>

void Insert(int *, int);

void Init(int *, int);

void In(int *, int);

void Init(int *A, int n){

int i;

printf("\n Tao lap day so:");

for (i=0; i<n;i++){

A[i]=random(1000);

printf("%5d",A[i]);

}

delay(1000);

}

void Insert(int *A, int n){

for (i=1;i<n;i++){

temp=A[i];

for(j=i-1;j>=0 && temp<A[j];j--)

A[j+1]=A[j];

A[j+1]=temp;

printf("\n");

In(A,i+1);

}

void In(int *A, int n){

for(i=0;i<n;i++)

printf("%5d",A[i]);

delay(1000);

}

void main(void){

int *A,n;clrscr();

printf("\n Nhap n="); scanf("%d",&n);

A=(int *) malloc(n*sizeof(int));

Init(A,n);Insert(A,n);

free(A);

}

thu gọn lại nhé :

Code:

void insertionSort ( int list[] , int last )

{

// Statements

// Local Declarations

int walk;

int temp;

bool located;

// Statements

// Outer Loop

for ( int current = 1 ; current <= last ; current++ )

{

// Inner loop ; Select and move 1 element

located = false;

temp = list[current];

for ( walk = current - 1 ; walk >= 0 && located ; )

if ( temp < list[walk] )

{

list[walk + 1] = list[walk] ;

walk--;

} // if

else

located = true ;

list[walk + 1] = temp ;

} // for

return;

}

III- Giải thuật Bubble Sort (sắp xếp theo phương pháp sủi bọt)
Giải thuật này thực hiện bằng cách đổi chỗ liên tiếp hai phần tử kế cận nhau khi chúng ngược thứ tự. Quá trình thực hiện được duyệt từ đáy lên đỉnh, như vậy sau lần duyệt thứ nhất phần tử lớn nhất sẽ xếp đúng ở vị trí n-1, ở lần duyệt thứ k thì k phần tử lớn nhất đã xếp đúng vị trí n-1, n-2, …, n-k+1. Sau lần duyệt thứ n-1 thì toàn bộ n phần tử sẽ được sắp xếp. Với phương pháp này các phần tử nhỏ sẽ được nổi dần lên như là nước sủi bọt nhờ đó nó có tên gọi là phương pháp sủi bọt.
Độ phức tạp của thuật toán là : Cmin = Cmax = Ctb = n(n-1)/2

Chương trình cài đặt được mô tả như sau:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <alloc.h>
#include <dos.h>
void Bubble(int *, int);
void Init(int *, int);
void In(int *, int);
void Init(int *A, int n){
int i;
printf("\n Tao lap day so:");
for (i=0; i<n;i++){
A[i]=random(1000);
printf("%5d",A[i]);
}
delay(1000);
}
void Bubble(int *A, int n){
register i,j,temp;
for (i=1; i<n; i++){
for (j=n-1; j>=i; j--){
if (A[j-1]>A[j]){
temp=A[j-1];
A[j-1]=A[j];
A[j]=temp;
}
}
printf("\n Ket qua lan:%d", i);
In(A,n);
}
}
void In(int *A, int n){
register int i;
for(i=0;i<n;i++)
printf("%5d",A[i]);
delay(1000);
}
void main(void){
int *A,n;clrscr();
printf("\n Nhap n="); scanf("%d",&n);
A=(int *) malloc(n*sizeof(int));
Init(A,n);Bubble(A,n);
free(A);
}

IV - Giải thuật Shaker Sort
Là cải tiến của thuật toán Bubble Sort, trong đó sau mỗi lần duyệt đi để xếp đúng vị trí phần tử lớn nhất chúng ta thực hiện duyệt lại để sắp xếp đúng vị trí phần tử nhỏ nhất. Dãy sẽ được sắp xếp sau [n/2] +1 lần duyệt. Chương trình mô tả thuật toán như sau :
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <alloc.h>
#include <dos.h>
void Shaker(int *, int);
void Init(int *, int);
void In(int *, int);
void Init(int *A, int n){
int i;
printf("\n Tao lap day so:");
for (i=0; i<n;i++){
A[i]=random(1000);
printf("%5d",A[i]);
}
delay(1000);
}
void Shaker(int *A, int n){
register i,j,temp, exchange;
do {
exchange=0;
for (i=n-1; i>0; i--){
if (A[i-1]>A[i]){
temp=A[i-1];
A[i-1]=A[i];
A[i]=temp;
exchange=1;
}
}
for(j=1; j<n;j++){
if (A[j-1]>A[j]){
temp=A[j-1];
A[j-1]=A[j];
A[j]=temp;
exchange=1;
}
}
printf("\n Ket qua lan:");
In(A,n);
}while(exchange);
}
void In(int *A, int n){
register int i;
for(i=0;i<n;i++)
printf("%5d",A[i]);
delay(1000);
}
void main(void){
int *A,n;clrscr();
printf("\n Nhap n="); scanf("%d",&n);
A=(int *) malloc(n*sizeof(int));
Init(A,n);Shaker(A,n);
free(A);
}

V - Giải thuật Quick sort

Phương pháp sắp xếp này là phương pháp sắp xếp kiểu phân đoạn, là một cải tiến của phương pháp Selection sort .
Nội dung chủ đạo của phương pháp này là chọn ngẫu nhiên một phần tử nào đó của dãy làm khoá chốt. Tính từ khoá chốt, các phần tử nhỏ hơn khoá được sắp xếp trước chốt (Đầu dãy) , các phần tử còn lại thì xếp sau chốt (cuối dãy).
Để làm được việc đó các phần tử trong dãy sẽ được so sánh với khoá chốt và trao đổi vị trí cho nhau hoặc cho khoá chốt nếu phần tử đó lớn hơn chốt mà lại nằm trước chốt hoặc nhở hơn chốt mà lại nằm sau chốt. Khi việc đổi chỗ lần đầu tiên thực hiện xong thì dãy hình thành hai đoạn : một đoạn bao gồm các phần tử nhỏ hơn chốt, và một đoạn gồm các phần tử lớn hơn chốt. Còn chốt thì chính là vị trí của phần tử trong dãy đc sắp xếp.

Áp dụng kĩ thuật trên cho mỗi đoạn trước chốt và sau chốt cho tới khi các đoạn chỉ còn 2 phần tử nữa thì việc ghi nhớ là kô cần thiết nữa.
Dãy sẽ được sắp xếp khi tất cả các đoạn được xử lí xong.
Độ phức tạp của thuật toán:
Trường hợp tốt nhất : Cmax = Ctb = O(nlogn)
Trường hợp xấu nhất Cmin = k*O(n^2)
Sau đây là cài đặt thuật toán trên C theo đệ qui:

Code:

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <alloc.h>

#include <dos.h>

void qs(int *, int ,int);

void Quick(int *,int );

void Init(int *, int);

void In(int *, int);

void Init(int *A, int n){

int i;

printf("\n Tao lap day so:");

for (i=0; i<n;i++){

A[i]=random(1000);

printf("%5d",A[i]);

}

delay(1000);

}

void Quick(int *A, int n){

qs(A,0,n-1);

}

void qs(int *A, int left,int right) {

i=left; j=right;

x= A[(left+right)/2];

do {

while(A[i]<x && i<right) i++;

while(A[j]>x && j>left) j--;

if(i<=j){

y=A[i];A[i]=A[j];A[j]=y;

i++;j--;

}

} while (i<=j);

if (left<j) qs(A,left,j);

if (i<right) qs(A,i,right);

}

void In(int *A, int n){

for(i=0;i<n;i++)

printf("%5d",A[i]);

delay(1000);

}

void main(void){

int *A,n;clrscr();

printf("\n Nhap n="); scanf("%d",&n);

A=(int *)malloc(n*sizeof(int));

Init(A,n);Quick(A,n);printf("\n");

In(A,n);getch();

free(A);

}

VII - Giải thuật Heap Sort
Heap là một cây nhị phân được biểu diễn bằng một mảng mà mảng đó biểu diễn một cây nhị phân hoàn chỉnh sao cho khoá ở node cha bao giờ cũng lớn hơn khoá của node con của nó.
Sắp xếp kiểu Heap Sort được tiến hành qua hai giai đoạn. Giai đoạn đầu tiên cây nhị phân biểu diễn bảng khoá được biến đổi đưa về một heap. Như vậy, đối với heap nếu j là chỉ số của node con thì [j/2] là chỉ số của node cha. Như vậy node gốc của heap là khoá có giá trị lớn nhất trong mọi node.
Để chuyển từ cây nhị phân bình thường thành một cây nhị phân heap. Chúng ta thực hiênh duyệt từ dưới lên (bottom up). Node lá đương nhiên là một heap. Nếu cây con bên trái và cây con bên phải đều là một heap thì toàn bộ cây cũng là một heap. Như vậy để tạo thành một heap chúng ta thực hiện so sánh nội dung node bên trái , nội dung node bên phải với node cha của nó, node nào có giá trị lớn hơn sẽ được thay đổi làm node cha. Quá trình lần lượt ngược lại cho tới khi gặp node gốc thì nội dung node gốc chính là khoá có giá trị lớn nhất.
Giai đoạn hai của thuật giải là đưa nội dung của node gốc về vị trí cuối cùng và nội dung của node cuối cùng được thay vào cị trí node gốc sau đó coi như node cuối cùng đã bị loại bỏ vì thực tế node cuối cùng là giá trị lớn nhất trong dãy số.
Cây mới được hình thành (không kể phần tử loại bỏ) không phải là một heap, chúng ta lại thực hiện vun thành đống và thực hiện tương tự như trên cho tới khi đống còn một phần tử là phần tử bé nhất của dãy.
Độ phức tạp của Heap Sort là :
Cmã = Cmin = O(n logn) cơ số hai.
Giải thuật được cài đặt như sau:

Code:

#include <conio.h>

#include <stdlib.h>

#include <alloc.h>

#include <dos.h>

void Heap(int *, int );

void Init(int *, int);

void In(int *, int);

void Init(int *A, int n){

int i;

printf("\n Tao lap day so:");

for (i=0; i<n;i++){

A[i]=random(1000);

printf("%5d",A[i]);

}

delay(1000);

}

void Heap(int *A, int n) {

int k,x,s,f,ivalue;

for(k=1;k<n;k++){

x=A[k];

s=k; f=(s-1)/2;

while(s>0 && A[f]<x){

A[s]=A[f];

s=f; f=(s-1)/2;

}

A[s]=x;

}

for(k=n-1;k>0;k--){

ivalue=A[k];

A[k]=A[0];

f=0;

if(k==1)

s=-1;

else

s=1;

if(k>2 && A[2]>A[1])

s=2;

while(s>=0 && ivalue<A[s]){

A[f]=A[s];

f=s;s=2*f +1;

if (s+1<=k-1 && A[s]<A[s+1])

s=s+1;

if (s>k-1)

s=-1;

}

A[f]=ivalue;

}

void In(int *A, int n){

for(i=0;i<n;i++)

printf("%5d",A[i]);

delay(1000);

}

void main(void){

int *A,n;clrscr();

printf("\n Nhap n="); scanf("%d",&n);

A=(int *) malloc(n*sizeof(int));

Init(A,n);Heap(A,n);printf("\n");

In(A,n);getch();

free(A);

}

VIII - Giải thuật Merge Sort
Sắp xếp theo Merge sort là sắp xếp bằng cách trộn hai danh sách đã được sắp xếp thành một danh sách đã được sắp xếp. Phương pháp này được tiến hành thông qua các bước sau:
1- Coi danh sách cần sắp xếp (có n phần tử) là n danh sách con mỗi danh sách con gồm 1 phần tử , như vậy các danh sách con đã được sắp xếp. Trộn từng cặp hai danh sách con kế cận thành một danh sách có hai phần tử ta nhận được n/2 danh sách con đã được sắp xếp.
2- Xem danh sách cần sắp xếp như n/2 danh sách con đã được sắp xếp. Trộn từng cặp hai danh sách kế cận thành từng danh sách có 4 phần tử đã được sắp xếp ta nhận được n/4 danh sách con.
3- …
……
i- Làm tương tự như bước i-1. Quá trình tiếp tục khi ta nhận được danh sách có n phần tử đã được sắp xếp.
Ví dụ :
42 23 74 11 68 58 94 36
Lần 1: [23 42] [11 74] [58 68] [36 94]
Lần 2: [11 23 42 74] [36 58 68 94]
Lần 3: [11 23 36 42 58 68 74 94]
Nhận được dãy đã sắp xếp.
Chương trình cài đặt thuật toán như sau:

Code:

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <alloc.h>

#include <dos.h>

#define MAX 10

void Merge(int *, int );

void Init(int *, int);

void In(int *, int);

void Init(int *A, int n){

int i;

printf("\n Tao lap day so:");

for (i=0; i<n;i++){

A[i]=random(1000);

printf("%5d",A[i]);

}

delay(1000);

}

void Merge(int *A, int n) {

int i,j,k,low1,up1,low2,up2,size;

int *dstam;size=1;dstam=(int *) malloc(n*sizeof(int));

while(size<n){

low1=0;k=0;

while(low1 +size <n){

low2=low1+size; up1=low2-1;

if (low2+size-1< n)

up2=low2+size-1;

else

up2=n-1;

for(i=low1, j=low2; i<=up1 && j<=up2; k++){

if(A[i]<=A[j])

dstam[k]=A[i++];

else

dstam[k] =A[j++];

}

for(;i<=up1;k++)

dstam[k]=A[i++];

for(;j<=up2;k++)

dstam[k]=A[j++];

low1=up2+1;

}

for (i=low1; k<n;i++)

dstam[k++]=A[i];

for(i=0;i<n;i++)

A[i]=dstam[i];

size*=2;

}

printf("\n Ket qua:");

In(A,n);free(dstam);

}

void In(int *A, int n){

for(i=0;i<n;i++)

printf("%5d",A[i]);

delay(1000);

}

void main(void){

int *A,n;clrscr();

printf("\n Nhap n="); scanf("%d",&n);

A=(int *) malloc(n*sizeof(int));

Init(A,n);Merge(A,n);printf("\n");

free(A);

}

B- Tìm kiếm
Tìm kiếm là công việc quan trọng đối với các hệ thống tin học và có liên quan mật thiết với quá trình sắp xếp dữ liệu. Bài toán tìm kiếm tổng quát có thể được phát biểu như sau:
“ Cho một bảng gồm n bản ghi R1,R2,…, Rn. Với mỗi bản ghi Ri được tương ứng với 1 khoá ki (trường thứ I trong record). Hãy tìm bản ghi có giá trị bằng khoá X cho trước.”
Nếu quá trình chúng ta tìm được bản ghi có giá trị khoá là X thì phép tìm kiếm được thoả (successful). Nếu không có giá trị nào thoả thì quá trình tím kiếm không thành công, sau quá trình này có thể xuất hiện thêm yêu cầu bổ sung thêm bản ghi mới có giá trị khoá là X vào thì giải thuật được gọi là tìm kiếm bổ sung.
Các thuật toán tìm kiếm cơ bản là:
I- Tìm kiếm tuần tự
Đây là kĩ thuật tìm kiếm cổ điển nhất trên 1 danh sách chưa được sắp xếp. Nội dung cơ bản của phương pháp này là duyệt từ bản ghi thứ nhất cho tới bản ghi cuối cùng, và so sánh lần lượt với khoá X cần tìm, trong quá trình duyệt nếu có bản ghi trùng với giá trị của X thì chúng ta đưa ra vị trí của bản ghi trong dãy, nếu duyệt tới cuối cùng mà không có bản ghi nào trùng giá trị thì quá trình tìm kiếm không thành công.
Chương trình cài đặt thuật toán hoàn toàn đơn giản.

Code:

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <alloc.h>

#include <dos.h>

int Sequential(int *, int, int);

void Init(int *, int);

void Init(int *A, int n){

int i;

printf("\n Tao lap day so:");

for (i=0; i<n;i++){

A[i]=random(1000);

printf("%5d",A[i]);

}

delay(1000);

}

int Sequential(int *A, int x, int n){

for (i=0; i<n ; i ++){

if (A[i] == X)

return(i);

}

return(-1);

}

void main(void){

int *A,n, x, k;clrscr();

printf("\n Nhap n="); scanf("%d",&n);

printf(“\n Sè x cÇn t×m:”); scanf(“%d”, &x);

A=(int *) malloc(n*sizeof(int));

k= Sequential(A,x,n);

if ( k>=0)

printf(“\n %d ë vÞ trÝ %d”, x,k);

else

printf(“\n %d kh«ng thuéc d•y”);

free(A); getch();

}

#include<iostream.h>

#include<conio.h>

#include<fstream.h>

#include<stdlib.h>

#include<ctype.h>

#include<time.h>

clock_t  start, end;

double t;

long  *abc;

long  n,i;

void xuat(long  a[])

        for(long  i=0;i<n;i++)

                cout<<a[i]<<"  ";

        cout<<endl;

//////////////////////////////////////////////////////////////////////////////////////////////////////

void bubbleSort(long a[],long n)

        long  temp;

        for(long  i=0;i<n;i++)

               for(long  j=n-1;j>i;j--)

               if(a[j]<a[j-1])

                       temp=a[j];

                               a[j]=a[j-1];

                               a[j-1]=temp;

//////////////////////////////////////////////////////////////////////////////////////////////////////

void chonTrucTiep( long a[], long n)

        long  possMin;

        long  temp;

        for(long  i=0;i<n-1;i++)

               possMin=i;

               for(long  j=i+1;j<n;j++)

                       if(a[j]<a[possMin])

                               possMin=j;

                       temp=a[i];

                       a[i]=a[possMin];

                       a[possMin]=temp;

////////////////////////////////////////////////////////////////////////////////////////////////////

void chenTrucTiep(long  a[],long  n)

        long j;

        long x;

        for(long i=1;i<n;i++)

               x=a[i];

               j=i-1;

               while(a[j]>x && j>=0)

                       a[j+1]=a[j];

                       j--;

               a[j+1]=x;

//////////////////////////////////////////////////////////////////////////////////////////////////

void chenNP(long a[],long n)

        long x;

        for(long i=1;i<n;i++)

               long l=0,r=i-1;long j=i-1;

               x=a[i];

               while(l<=r)

                       long m=(l+r)/2;

                       if(a[m]>x)

                                  r=m-1;

                       else   l=m+1;

               for( j=i-1;j>l;j--)

               a[j+1]=a[j];

               a[l]=x;

///////////////////////////////////////////////////////////////////////////////////////////////////

void tronHaiNua(long a[],long l1,long r1,long l2,long r2)

        for(long i=l2;i<r2;i++)

               long  x=a[i];

               long j=r1;

               while(a[j]>x && j>=l1)

                       a[j+1]=a[j];

                       j--;

               a[j+1]=x;

               r1++;

void tronTuNhien(long a[],long l, long r)

        if(l<r)

               tronTuNhien(a,l,(l+r)/2);

               tronTuNhien(a,(l+r)/2+1,r);

               tronHaiNua(a,l,(l+r)/2,(l+r)/2+1,r);

//////////////////////////////////////////////////////////////////////////////////////////////////

void quickSort(long a[],long l,long r)

        long  x,temp;

        long  i,j;

        x=a[(l+r)/2];

        i=l;j=r;

do

        {       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--;

        }while(i<=j);

        if(j>l)

               quickSort(a,l,j);

        if(i<r)

               quickSort(a,i,r);

//////////////////////////////////////////////////////////////////////////////////////////////////

void chenTrucTiepLC( long a[], long n)

        long j;

        long x;

        for(long i=1;i<n;i++)

               x=a[i];

               j=i-1;

               while(a[j]>x )

                       a[-1]=x;

                       a[j+1]=a[j];

                       j--;

               a[j+1]=x;

//////////////////////////////////////////////////////////////////////////////////////////////////

void hieuChinhHM(long a[],long l,long r)

        long i,j,x;

        i=l;j=2*i;x=a[i];

        while (j<=r)

               if(j<r)

                       if (a[j]<=a[j+1])

                               j++;

               if(a[j]<=x)

                       break;

               a[i]=a[j];

               i=j;

               j=2*i;

        a[i]=x;

////////////////////////////

void taoHeapMax(long a[],long n)

        long l,r;

        l=n/2+1;r=n-1;

        while(l>0)

               l--;

               hieuChinhHM(a,l,r);

////////////////////////////

void heapSort(long a[], long n)

        long tam;long r;r=n-1;

        taoHeapMax(a,n);

        while(r>0)

               tam=a[0];

               a[0]=a[r];

               a[r]=tam;

               r--;

               hieuChinhHM(a,0,r);

//////////////////////////////////////////////////////////////////////////////////////////////////

/*void heapSort(long a[],long n)

        long x,s,f,endHeap;

        for(i=0;i<n;i++)

               x=a[i];

               s=i;

               f=(s-1)/2;

               while(s>0 && a[f]<x)

                       a[s]=a[f];

                       s=f;

                       f=(s-1)/2;

               a[s]=x;

        for(i=n-1;i>0;i--)

               endHeap=a[i];

               a[i]=a[0];

               f=0;

               if(i==1)

                       s=-1;

               else

                       s=1;

               if(i>2 && a[2]>a[1])

                       s=2;

               while(s>=0 && endHeap<a[s])

                       a[f]=a[s];

                       f=s;

                       s=2*f+1;

                       if(s+1<=i-1 && a[s]<a[s+1])

                               s=s+1;

                       if(s>i-1)

                               s=-1;

               a[f]=endHeap;

*/

//////////////////////////////////////////////////////////////////////////////////////////////////

void ghiTep(long a[],long n)

        ofstream f;

        f.open("D:\\data11.txt",ios::out);

        srand(time(0));

        f<<"So luong:"<<n<<endl;

        for(long i=0;i<n;i++)

               f<<a[i]<<" ";

        f<<endl;

        f<<"thoi gian chay:"<<t<<endl;

        f.close();

void docFile(long a[],long ab, char *tFile)

        int t;

    ifstream f(tFile);

    if (!f) cout << "Error!!" << endl;

    f >> ab;

    cout << "So phan tu:"<< ab<<endl;

        abc=new long [ab];

        n=ab;

    if (!abc) cout << "Error!!" << endl;

    for(long i=0;i<ab;i++)

        f >> t;

               abc[i]=t;

    cout << endl;

    f.close();

//////////////////////////////////////////////////////////////////////////////////////////////

void main()

        char *tFile;int d;char c;

        int k=-1;

        int sel=-1;

        cout<<"Chon tu 1 den 5:";

        cin>>k;

        switch(k)

               case 1:tFile="C:\\Documents and Settings\\Thuy Trang\\My Documents\\data1.txt"; break;

               case 2:tFile="C:\\Documents and Settings\\Thuy Trang\\My Documents\\data2.txt"; break;

               case 3:tFile="C:\\Documents and Settings\\Thuy Trang\\My Documents\\data3.txt"; break;

               case 4:tFile="C:\\Documents and Settings\\Thuy Trang\\My Documents\\data4.txt"; break;

               case 5:tFile="C:\\Documents and Settings\\Thuy Trang\\My Documents\\data5.txt"; break;

        cout<<"file dc doc:"<<tFile<<endl;

        docFile(abc,n,tFile);

        cout<<"CHON 1 TRON CAC GIAI THUAT SAU:"<<endl;

        cout<<"     1:Bubble sort"<<endl;

        cout<<"     2:Chen nhi phan"<<endl;

        cout<<"     3:Chon truc tiep"<<endl;

        cout<<"     4:Chen truc tiep"<<endl;

        cout<<"     5:Tron tu nhien"<<endl;

        cout<<"     6:Chen truc tiep linh canh"<<endl;

        cout<<"     7:Quick Sort"<<endl;

        cout<<"     8:Heap sort"<<endl;

        cin>>sel;

        start=clock();

        switch(sel)

               case 1:bubbleSort(abc,n);             break;

               case 2:chenNP(abc,n);                 break;

               case 3:chonTrucTiep(abc,n);           break;

               case 4:chenTrucTiep(abc,n);           break;

               case 5:tronTuNhien(abc,0,n);   break;

               case 6:chenTrucTiepLC(abc,n);  break;

               case 7:quickSort(abc,0,n-1);   break;

               case 8:heapSort(abc,n);                       break;

        end=clock();

        t=double(end-start)/CLOCKS_PER_SEC ;

        cout<<"Thoi gian chay:"<<t<<endl;

        cout<<"Xuat day sau khi sap xep(c/k)?";

        cin>>c;d=c;

        if(d==67 || d==99)

               xuat(abc);

        ghiTep(abc,n);

        cout<<"Ket thuc chuong trinh"<<endl;

        getch();

Radix Sort

#include <stdio.h>
	#include <stdlib.h>

	#include <math.h>
004	#include <conio.h>

005	////Radix sort
006	int getMax(int a[],int n)

007	{
008	int max=a[0];

009	for(int i=1;i<n;i++)
010	if(max<a[i])

011	max=a[i];
012	return max;

013	}
014	int countDigit(int n)

015	{
016	int count=0;

017	while(n)
018	{

019	count++;
020	n/=10;

021	}
022	return count;

023	}
024	int getDigit(int n,int t)

025	{
026	int tt=1;

027	for(int i=0;i<t;i++)tt*=10;
028	return ((n/tt)%10);

029	}
030	void send2Box(int a[],int n,int *b[10],int num[10],int t)

031	{
032	for(int i=0;i<n;i++)

033	{
034	int tt=getDigit(a[i],t);

035	b[tt][num[tt]++]=a[i];
036	}

037	}
038	void getValue(int a[],int *b[10],int nn[10])

039	{
040	int j=0;

041	for(int i=0;i<10;i++)
042	{

043	if(nn[i]!=0)
044	{

045	for(int k=0;
046	k<nn[i];

047	k++)a[j++]=b[i][k];
048	nn[i]=0;

049	}
050	}

051	}
052	void radixsort(int a[],int n)

053	{
054	int *Box[10];

055	int number[10];
056	for(int i=0;i<10;i++)

057	{
058	Box[i]=new int [n];

059	if(Box[i]==NULL)
060	{

061	printf("Not enough");
062	exit(0);

063	}
064	number[i]=0;

065	}
066	int nn=countDigit(getMax(a,n));

067	for(int i=0;i<nn;i++)
068	{

069	send2Box(a,n,Box,number,i);
070	getValue(a,Box,number);

071	}
072	}

073	void xuat(int a[], int n)
074	{

075	int i=0;
076	printf("\n\t");

077	for (i=0;i<n;i++)
078	{

079	printf("%-6d",a[i]) ;
080	if ((i+1) % 10 == 0)

081	printf("\n\t");
082	}

083	}
084	void main()

085	{
086	clrscr();

087	int i,n,A[100];
088	do

089	{
090	printf("\n\tNhap so phan tu mang\n\t( n>0 va n<=100) : ");

091	scanf("%d",&n);
092	}while (n<0\|\|n>100);

093	for (i=0;i<n;i++)
094	{

095	printf("Nhap A[%d]=",i);
096	scanf("%d",&A[i]);

097	}
098	printf("\n\tMang moi nhap vao:\n");

099	xuat(A,n);
100	printf("\n\n\tMang da sap xep :\n");

101	radixsort(A,n);
102	xuat(A,n);

103	getch();
104	}

Các thao tác trên danh sách liên kết đơn(single-link list)
1.Định nghĩa tổng quát

Code:

struct tq {

thtin_t phantu;

struc tq*tiep;

};

typedef struct tq tq_t;

2.Con trỏ tới 1 node

Code:

struct node {

int infor;

struct node *next;

};

typedef struct node *NODEPTR;

3.Cấp phát bộ nhớ cho 1 node

Code:

NODEPTR Getnode(void) {

NODEPTR p;

P = (NODEPTR) malloc(sizeof( struct node));

Return(p);

}

4.Giải phóng 1 node

Code:

NODEPTR Freenode( NODEPTR p){

free(p);

}

5.Thêm phần tử vào đỉnh danh sách

Code:

void Push_Top( NODEPTR *plist, int x) {

NODEPTR p;

p= Getnode();

p -> infor = x;

p ->next = *plist;

*plist = p;

}

6.Thêm node mới vào cuối danh sách

Code:

void Push_Bottom( NODEPTR *plist, int x) {

NODEPTR p, q;

p= Getnode(); //

p->infor = x;

q = *plist;

while (q-> next != NULL)

q = q -> next;

q -> next = p;

p ->next = NULL;

}

7.Thêm node mới vào giữa danh sách

Code:

void Push_Before( NODEPTR p, int x ){

NODEPTR q;

if (p->next==NULL)

Push_Bottom(p, x);

else {

q= Getnode();

q -> infor = x;

q-> next = p-> next;

p->next = q;

}

8.Xóa 1 node đầu danh sách

Code:

void Del_Top( NODEPTR *plist) {

NODEPTR p;

p = *plist;

if (p==NULL) return;

(*plist) = (*plist) -> next;

p-> next = NULL;

Freenode(p);

}

9.Xóa node cuối danh sách

Code:

void Del_Bottom(NODEPTR *plist) {

NODEPTR p, q;

if (*plist==NULL) return;

else if ( (*plist)->next==NULL))

Del_Top(plist);

else {

p = *plist;

while (p->next!=NULL){

q = p;

p = p->next;

}

// p lµ node cuèi danh s¸ch;

q->next =NULL;

Freenode(p);

}

10.Xóa node giữa danh sách

Code:

void Del_before(NODEPTR p){

NODEPTR q;

if (p->next==NULL) return;

q = p ->next;

p->next = q->next;

Freenode(q);

}

Ôn cấu trúc dữ liệu & giải thuật

No comments :

Post a Comment

Labels

Popular Posts

Recent Posts

Labels

Contact Form