Cấu trúc dữ liệu và giải thuật
I, THUẬT TOÁN ĐỆ QUY
1, định nghĩa đối tượng đệ quy,thuật toán đệ quy
- Đ/N đối tượng đệ quy: 1 đối tượng được gọi là đệ quy nếu trong nó chứa 1 đối tượng có cấu trúc đồng dạng với nó.
- Đ/N thuật toán đệ quy: 1 thuật toán là đệ quy nếu trong nó chứa lời gọi giải quyết chính bài toán đó nhưng có kích thước khác (thường là nhỏ hơn).
2, lược đồ thiết kế 1 thuật toán đệ quy
Tên kiểu A(danh sách các đối){
IF (là trường hợp suy biến)
Giải bài toán;
ELSE
A(danh sách đối mới);
}
Lưu ý: khi thiết kế các thuật toán đệ quy ta cần xác định:
+) trường hợp suy biến của bài toán
+) đối của hàm, phải dẫn bài toán về trường hợp suy biến.
3, Một số ví dụ
VD1: xây dựng hàm đệ quy tính số Fibonanci thứ n.biết F0=F1=1; Fn=Fn-1 + Fn-2 n≥ 2
Long Fibonanci (int n){
IF (n<2)
Return 1;
ELSE
Return Fibonanci (n-1) + Fibonanci(n-2);
}
VD2: xây dựng hàm đệ quy tìm giá trị lớn nhất của một dãy số
Int maxarray (int * x, int i ,int j){
Int mid,max1,max2;
If (i==j)
Return x[i];
Else{
Mid =(i+j)/2;
Max1= Maxarray(x,i,mid);
Max2= maxarray(x,mid+1,j);
If(max1>max2)
Return max1;
Else
Return max 2;
}
}
VD3: xây dựng hàm đệ quy tính giá trị của đa thức: Pn(x) = a0 + a1x +…+ anxn=Pn-1(x) + anxn
Float P(float *a, int n, float x){
If(n==0)
Return a[0];
Else
Return P(a,n-1,x) + a[n] * Pow (x,n);
}
II, DANH SÁCH
1, khái niệm danh sách tuyến tính
- Danh sách tuyến tính là 1 danh sách mà các phần tử trong nó có mối quan hệ thứ tự trc sau
2, danh sách kiểu ngăn xếp (stack)
- Đ/N: là 1 danh sách tuyến tính, việc bổ xung và lấy phần tử ra đc thực hiện ở cùng 1 đầu. ta gọi danh sách này là LIFO (last in first out)
- Đ/N 1 cấu trúc biểu diễn stack với các phần tử lưu trong mảng
#Define N giá trị nguyên
Typedef struct stack {
Tên kiểu S[N];
Int t;
};
- Các thao tác trên stack
+) khởi tạo một stack
Void create(stack *s) {s -> t=-1;}
+) kiểm tra stack có đầy không:
Int ISFULL(stack *s) {return s -> t==N-1;}
+) Kiểm tra stack có rỗng không:
Int ISEMPTY(stack *s) {return s -> t==-1;}
+) cho biết số phần tử có trong stack:
Int SIZE(stack *s) {return S -> t+1;}
+) thêm phần tử vào stack:
Int Push( stack *s, tên kiểu x) {
IF (ISFULL(s))
Return 0;
Else
{
s -> t++;
s -> S[s -> t]=x;
return 1;
}
}
+) lấy phần tử ra ngoài stack:
Int Pop(stack * s, tên kiểu x){
IF (ISEMPTY(s))
Return 0;
Else
{
*x = s -> S[s -> t];
s -> t--;
return 1;
}
}
3, Danh sách kiểu hàng đợi (Queue)
- Đ/N: ds kiểu hàng đợi là danh sách tuyến tính mà việc bổ xung phẩn tử dc thực hiện ở 1 đầu và lấy phần tử ở đầu còn lại. ta gọi danh sách này là FIFO( first in first out)
- Đ/N cấu trúc:
#define N giá trị nguyên
Typedef struct Queue{
Tên kiểu Q[N];
};
-Các thao tác trên Queue
+) khởi tạo Queue:
Void create (Queue *q) { q -> f=q -> r=0;}
+) kiểm tra Queue có đầy không:
Int ISFULL (Queue *q) { return size(q) == N-1;}
+) kiểm tra Queue có rỗng không:
Int ISEMPTY (Queue *q) { return q -> f==q -> r;}
+)cho số phần tử hiện có trong Queue
Int Size (Queue * q) {return (N-q -> f+q -> r)%N;}
+)thêm phần tử vào Queue
Int EnQueue (Queue * q, tên kiểu x){
IF (ISFULL(q))
Return 0;
Else
{
q -> Q[q -> r]=x;
q -> r=(q -> r++)%N;
return 1;
}
}
+) lấy phần tử ra khỏi Queue
Int DeQueue(Queue * q, tên kiểu *x){
IF (ISEMPTY(q))
Return 0;
Else
{
*x=q -> Q[q -> f];
q -> f=(q -> f++)%N;
return 1;
}
}
III, Danh sách liên kết
1, danh sách liên kết đơn
- Mỗi phần tử của danh sách liên kết đơn gồm 2 phần:
+) thông tin cần lưu trữ
+) địa chỉ phần tử kế tiếp, nếu không có phần tử kế tiếp thì lưu địa chỉ NULL
- Quản lý danh sách sử dụng 2 con trỏ lưu địa chỉ phần tử đầu và phần tử cuối của danh sách
- Cấu trúc dữ liệu biểu diễn 1 nút
Typedef Struct Node {
Tên kiểu dữ liệu info;
Node *next;
};
Quản lý danh sách ta khai báo 2 con trỏ: Node * header, *trailer ; ( header lưu đ/c đầu, trailer lưu đ/c cuối)
Danh sách rỗng khi header = trailer = NULL
*) Các thao tác trên danh sách liên kết đơn
- thao tác thêm phần tử vào danh sách
+) thêm vào đầu danh sách:
Void InsertFirst (Node * header, Node * trailer, tên kiểu * x){
Node *q;
q= (Node *) malloc(sizeof (node));
q -> info=x;
if (header == NULL)
header=trailer =q;
else
{
q -> next=header;
header=q;
}
}
+) thêm vào cuối danh sách
Void InsertLast (Node * header, Node * trailer, tên kiểu * x){
Node *q;
q= (node *) malloc(sizeof (node));
q -> Info=x;
q -> Next=NULL;
IF(header == NULL)
header=trailer=q;
Else
{
trailer -> Next=q;
trailer=q;
}
}
+)Thêm vào sau 1 nút
Void InsertAfter (Node * header, Node * trailer, Node *p, tên kiểu x){
Node * q;
q=
q -> info=x;
if(p!=trailer){
q -> next=p -> next;
}
Else // P là phần tử cuối
p -> next=q;
q -> next= NULL;
trailer=q;
}
}
+) Thao tác xóa
Void Delete (node * header, node * trailer, node *p){
Node * q;
If(p==header)
Header= header -> next;
Else
{
q=header;
while (q -> next !=p)
q=q -> next;
}
if (p!=trailer)
q -> next=p -> next;
else
{
Trailer =q;
}
p -> next=NULL;
Delete p;
}
Bài Tập:
Khai báo 1 cấu trúc danh sách liên kết đơn để lưu trữ các đối tượng sinh viên biết mỗi SV gồm các thông tin: Mã(số) họ tên( xâu kí tự), năm sinh(số).
- Viết hàm thêm 1 sinh viên vào cuối ds
- Viết hàm tìm kiếm 1 sinh viên khi biết mã hàm trả lại địa chỉ của nút chứa mã sinh viên tìm thấy, nếu không tìm thấy trả lại NULL
- Viết hàm in danh sách sinh viên lên màn hình
Typedef struct Node{
Long Ma;
Char Ht[30];
Int Ns;
Node * Next;
};
Void InsertLast (node * header, node * trailet){
Node * q;
q= (node *) malloc (sizeof (node));
printf (“nhap cac thong tin cua sinh vien:”);
printf (“
nhap ma:”);
scanf (“%d”, & q -> Ma);
printf(“nhap ho ten:”):
fflush(stdin);
gets(q -> Ht);
printf (“nhap nam sinh:”);
scanf(“%d”, &a -> Ns);
if (header == NULL)
header =trailer=q;
else
{
trailer -> next=q;
trailer=q;
q -> next=NULL;
}
Node * Search(node * header, node * trailer, long ma){
Node *q;
q=header;
while (q!=NULL && q -> ma !=Ma)
q= q -> next;
return q;
}
Void printer (node * header, node * trailer){
Node *q;
q=header;
while (q!= NULL)
printf(“
%ld \t %s \t %d”,q -> Ma, q -> Ht,q -> Ns);
q= q -> next;
}
}
2, Danh sách liên kết kép
Mỗi phân tử gồm 3 phần: +) thông tin lưu trữ trong nó +) địa chỉ của nút kế tiếp +) địa chỉ của nút liền trước
- Để quản lý ds ta sử dụng 2 con trỏ lưu trữu địa chỉ phần tử đầu và phần tử cuối của ds.
- Cấu trúc dữ liệu biểu diễn 1 nút của ds
Typedef Struct Node{
Tên kiểu Info;
Node * info;
Node * Next;
Node * Pre;
};
- Khai báo 2 con trỏ: node * header, * trailer;
- Để quản lý danh sách:
+) header lưu địa chỉ nút đầu
+)trailer lưu địa chỉ nút cuối
+)header=trailer=NULL khi đó danh sách rỗng
*) các thao tác trên danh sách liên kết kép
- Thao tác thêm:
+) thêm vào đầu:
Void InsertFirst (Node * header, Node * trailer, tên kiểu x){
Node *q;
q=
q -> info=x;
if (header== NULL){
header=trailer=q;
q -> next=q -> pre=NULL;
}
Else{
q -> next==header;
header -> pre=q;
q -> pre=NULL;
header=q;
}
}
+) thêm vào cuối
Void InsertFirst (Node * header, Node * trailer, tên kiểu x){
Node *q;
q=
q -> info=x;
if (header== NULL){
header=trailer=q;
q -> next=q -> pre=NULL;
}
Else{
trailer -> next==q;
q -> pre=trailer;
q -> next=NULL;
trailer=q;}}
+) thêm vào sau 1 phần tử
Void InsertAfter (Node * header, Node * trailer, Node * p, tên kiểu x){
Node *q;
q=
q -> info=x;
if(p!=trailer){
q -> next=p -> next;
p -> next -> pre=q;
q -> pre=p;
p -> next=q;
}
Else{
p -> next=q;
q -> pre=p;
q -> next=NULL;
trailer=q;}}
+) thêm vào trước 1 phần tử
Void InsertBefor (Node * header, Node * trailer, Node * p, tên kiểu x){
Node *q;
q=
q -> info=x;
if(p!=header){
p -> pre -> next=q;
q -> pre=p -> pre;
q -> next=p;
p -> pre=q;
}
Else{
p -> pre=q;
q -> next=p;
q -> pre=NULL;
header=q;}}
+) Xóa phần tử:
Void Delete (note * header, node * trailer, node *p)
If(header==trailer)
Delete p;
Else
If(p==header){
Header=header -> next;
header -> pre=NULL;}
Else
If(p==trailer){
Trailer=trailer -> pre;
trailer -> next=NULL;}
Else{
p -> pre -> next=p -> next;
p -> next -> pre=p -> pre;}
Delete p;}
3, Cây nhị phân
Đ/N cây: cây là tập hợp các nút,giữa các nút có mối quan hệ cha con với nhau.trong đó có nút đặc biệt không có cha gọi là nút gốc.
Đ/N cây nhị phân: là cây mà tại mỗi nút của nó có không quá 2 nút con.
-các nút con của nó được quy định là con trái hoặc con phải
- cấu trúc biểu diễn 1 nút của cây nhị phân,gồm có 3 phần: +) thông tin lưu trong nút +) địa chỉ của nút con trái +) địa chỉ của nút con phải.
Typedef struct node{
Tên kiểu INFO;
Node * left;
Node *right;
};
- để quản lý cây ta cần 1 con trỏ lưu địa chỉ của nút gốc: Node *root;
- nếu root==NULL có nghĩa cây rỗng
*) DYỆT CÂY: là quá trình đi thăm các nút của cây theo 1 hệ thống, mỗi nút được thăm 1 lần.
- Duyệt theo thứ tự trước:
+) thăm gốc nếu cây khác rỗng +) thăm cây con bên trái theo thứ tự trước +) thăm cây con bên phải theo thứ tự trước
Void preorder (node * root){
If( root!=NULL){
Visit (root);
Preorder (root -> left);
Preorder (root -> right);
}
}
- Duyệt theo thứ tự giữa:
+) thăm cây bên trái theo thứ tự giữa +) thăm gốc cây +) thăm cây bên phải theo thứ tự giữa
Void Inorder( node *root){
If(root != NULL){
Inorder (root -> left);
Visit(root);
Inorder (root -> right);
}
}
- Duyệt cây theo thứ tự sau:
+) thăm cây con bên trái theo thứ tự sau +) thăm cây con bên phải theo thứ tự sau +) thặm gốc
Void postorder(node*root){
If(root!= NULL){
Postorder (root -> left);
Postorder (root -> right);
Visit (root);
}
}
IV, Các thuật toán sắp xếp:
1,các thuật toán sắp xếp có độ phức tạp O(n2)
a, thuật toán sx nổi bọt (buble sort)
- Ý tưởng: b1) xuất phát từ cuối dãy so sánh phần tử ở cuối dãy với phần tử đứng trước nó, nếu nhỏ hơn thì đổi chỗ 2 phân tử cho nhau. Tiếp tục thực hiên so sánh phần tử thứ n-1 với phần tử trước nó nếu nhỏ hơn thì đổi chỗ 2 phần tử, lặp lại quá trình so sánh trên với phần tử n-2,n-3,…2. kết thúc quá trình ta được phần tử thứ 1 là phần tử nhỏ nhất của dãy
b2) xuất phát từ cuối dãy so sánh phần tử thứ n vơi n-1,nếu nhỏ hơn thì đổi chỗ 2 phần tử, lặp lại quá trình so sánh trên với các phần tử n-1,n-2,...3. kết thúc quá trình trên ta thu đc ptử 1,2 đã được sắp xếp.
bi) ) xuất phát từ cuối dãy so sánh phần tử thứ n với phần tử n-1, nếu nhỏ hơn thì đổi chỗ 2 phân tử cho nhau. lặp lại quá trình so sánh trên với phần tử n-1,n-2,…n-i+1. lặp lại các bước trên đến bước thứ n-1 ta được dãy được sắp theo thứ tự tăng dần.
-Hàm thể hiện thuật toán:
Void bublesort(int *a, int n){
Int tg,i,j;
For (i=1, i<n, i++)
For(j=n, j>I, J--)
If( a[j-1] > a[j]){
Tg=a[j];
a[j]=a[j-1];
a[j-1]=tg;
}
}
b, thuật toán sắp xếp chọn(selection sort)
- ý tưởng: chọn dần các phần tử nhỏ chuyển về đầu dãy
b1) chọn phần tử có giá trị nhỏ nhất trog số các phần tử từ 1..n, đổi chỗ nó với phần tử số 1.
b2) chọn phần tử có giá trị nhỏ nhất trong số các phần tử từ 2..n,đổi chỗ nó với phần tử số 2
bi) chọn phần tử có giá trị nhỏ nhất trong số các phần tử từ i..n,đổi chỗ nó với phần tử số i
lặp lại quá trình trên đến bước n-1 thì ta thu được dãy được sắp xếp theo thứ tự tăng dần.
- hàm thể hiện thuật toán:
void selectionsort( int *a,int n){
int i,j,vtmin,tg;
for (i=1,i<n,i++){
vtmin=i;
for (j=i+1,j<=n,j++)
if(a[j]<a[vtmin])
vtmin=j;
if(i!=vtmin){
tg=a[i];
a[i]=a[vtmin];
a[vtmim]=tg;
}
}
C, thuật toán sắp xếp chèn (insert sort)
- ý tưởng: giả sử ta có dãy a1,..,ai đã được sắp ta cần chèn phần tử ai+1 vào dãy đó để được dãy a1,…,ai+1 cũng được sắp.
- thuật toán chèn: thực hiện so sánh ai+1 (gọi là phần tử cần chèn) với phần tử ai, nếu ai+1 <ai thì chuyển ai về sau 1 vị trí, nếu ngược lại thì ai+1 đã đúng vị trí trong dãy được sắp quá trình chèn kết thúc.
- nếu phần tử cần chèn nhỏ hơn ai thì tiếp tục so sánh phần tử cần chèn với phần tử thứ i-1,i-2,… thực hiện như với phần tử thứ i, giả sử aj đầu tiên tìm thấy có aj nhỏ hơn hoặc bằng phần tử cần chèn thì quá trình trên dừng lại và đặt aj+1 bằng phần tử cần chèn.
- dãy có 1 phần tử được xem là dãy đã được sx, để sắp xếp cả dãy ta thực hiện như sau :
b1) chèn phần tử a2 vào dãy chỉ có a1 để được dãy a1’, a2’ được sắp
b2) chèn phần tử a3 vào dãy chỉ có a1 để được dãy a1’, a2’,…a1’+1 được sắp
lặp lại bước trên đến bước thứ n-1 ta thu được dãy sắp xếp.
- hàm thể hiện thuật toán :
void insertion sort( int * a, int n){
int i,j,x ;
for (i=2 ; 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;
}
}
2, Các thuật toán sắp xếp có độ phức tạp O(nlogn)
a, thuật toán sắp xếp nhanh (quicksort)
*) ý tưởng: dựa trên chiến lược chia để trị để thiết kế thuật toán.
- giả sử cần sx dãy s, ta thực hiện dãy s thành 3 dãy con s1,s2,s3 thỏa mãn các tính chất sau:
+) dãy s2 có 1 phần tử
+) các phần tử của dãy s1 nhỏ hơn hoặc bằng phần tử của dãy s2
+) các phần tử của dãy s3 lớn hơn phần tử của dãy s2
+) dãy s1,s3 có thể rỗng.
Tiếp tục thực hiện phân hoạch dãy s1,s3 độc lập cho tới khi phải phân hoạch dãy chỉ có 1 phần tử hoặc dãy rỗng.khi đó ta thu được dãy được sắp.
*)hàm thể hiện thuật toán:
Void quicksort( int *a, int i, int j){
int k;
if(i<j)
partition( a,i,j, &k);
quicksort( a,i, k-1);
quicksort( a,k+1,j);
}
Trong đó, hàm partition(a,i,j,&k) là hàm thực hiện phân hoạch dãy ai,..aj thành 3 dãy ai…ak1,ak,ak+1…aj. Trong đó: s2={ak} s1={ai…ak-1} s3{ak+1, aj} thỏa mãn các tính chất phân hoạch.
- thuật toán phân hoạch:
+) chọn phần tử đầu ai làm phần tử của s2 (gọi là phần tử chốt)
+) sử dụng 2 biến left, right. Left xuất phát từ i, right xuất phát từ j
+) trong khi left<right thì thực hiện tăng left cho đến khi a[left] lớn hơn phần tử chốt hoặc left>right. Thực hiện giảm right cho tới khi a[right]nhỏ hơn hoặc bằng phần tử chốt.
+) nếu left < right thì đổi chỗ a[left] và a[right]
+) lặp lại quá trình tăng left, giảm right ở trên cho tới khi left>right thì dừng lại
+)kiểm tra nếu right khác i thì đổi chỗ phần tử a[i] với phần tử a[right] khi đó ta thu được 3 dãy: ai..a[right-1], a[right], a[right+1]…aj thỏa mãn tính chất phân hoạch.
- hàm thể hiện thuật toán phân hoạch:
void partition (int *a,int i, int j, int *k){
int x,left,right,tg;
x=a[i];
left=i; right=j;
while (left<right){
while (a[left] <= x && left <= right)
left ++;
while (a[right] >x)
right--;
if( left < right){
tg=a[left];
a[left]=a[right];
a[right]=tg;
}
}
If(right !=i){
a[i]=a[right];
a[right]=x;
}
}
*k=right;
}
b, Thuật toán sắp xếp trộn( Merge sort)
*) Ý tưởng: giả sử ta có 2 dãy a[i]….a[k] và a[k+1]..a[j] đã được sắp xếp theo thứ tự tăng dần, thực hiện trộn 2 dãy đó để được dãy a[i]…a[j] cũng được sắp.
- thuật toán trộn 2 dãy sử dụng 2 biến left, right chạy trên mảng a, left xuất phát từ i, right xuất phát từ j.sử dụng 1 mảng phụ b[i]..b[j], biến t xuất phát từ i chạy trên mảng b.
- thực hiện so sánh a[left] và a[right]:
+) nếu a[left] nhỏ hơn hoặc bằng a[right] thì đặt b[t]=a[left], tăng left, t lên một đơn vị
+) nếu a[left] > a[right] thì đặt b[t] = a[right], tăng right, t lên 1 đơn vị
Lặp lại quá trình trên cho tới khi left > k hoặc right > j
- kiểm tra:
+) nếu left >k thực hiện gán lần lượt các phần tử a[right]..a[j] cho các phần tử b[t]…b[j]
+) nếu right>j thì thực hiện gán lần lượt các phần tử a[left]..a[k] cho các phần tử b[t]..b[j]
*) thuật toán trộn:
Void merge(int * a, int i, int k, int j){
int left,right,l,t;
left=i, right =j, t=i;
while (left <=k && right <=j){
if(a[left] <= a[right]){
b[t]=a[left];
left++; t++;}
else
{ b[t] = a[right];
Right ++; t++;
}
}
If ( left> k)
For(l= right; l<=j; l++){
b[t]=a[l];
t++;
}
Else
For (l= left; l<=k; l++){
b[t]=a[l];
t++;
}
For (l=i; l<=k; l++)
a[l]=b[l];
}
*) Thuật toán sắp xếp trộn:
Giả sử cần sx 1 dãy a[1]..a[n] ta thực hiện như sau: chia đôi dãy thành 2 dãy a[1]..a[k],a[k+1]..a[n].
Trong đó: k=(1+n)/2 ( lấy phần nguyên). Thực hiện sắp xếp a[1]..a[k] và a[k+1]..a[n] độc lập cũng bằng thuật toán sắp xếp trộn.
Trộn 2 dãy a[1]..a[k] và a[k+1]…a[n] để được dãy a[1]..a[n] được sắp.
*) Hàm thể hiện thuật toán sắp xếp trộn:
Void Mergesort (int * a, int i, int j){
If(i<j){
int k=(i+j)/2;
mergesort(a,i,k);
mergesort(a,k+1,j);
meger( a,i,k,j);
}
}
C, Thuật toán sắp xếp vun đống:
*) ý tưởng thuật toán sx vun đống:
bước1: biến đổi mảng ban đầu về mảng biểu diễn cây heap, tráo đổi phần tử a[1] với a[n]
bước2: biến đổi mảng có n-1 phần tử đầu về thành mảng biểu diễn cây heap, tráo đổi phần tử a[1] với a[n-1]
bước i: biến đổi mảng có n-i+1 phần tử đầu thành mảng biểu diễn cây heap,tráo đổi phần tử a[1] với a[n-i+1]. Thực hiện như trên đến bước thứ n-1 ta thu được dãy đã sắp.
*) thuật toán tạo đống
Ta có các phần tử từ n/2+1..n đã thỏa mãn tính chất cây heap. Thực hiện mở rộng mảng thỏa mãn tính chất cây heap với các phần tử thứ n/2,n/2-1…1
Giả sử ta có dãy a[i+1]..a[n] đã thỏa mãn tính chất cây heap. Ta cần bổ xung phần tử a[i] vào dãy đó để được dãy a[i]…a[n] cũng thỏa mãn tính chất cây heap.
*) hàm thể hiện thuật toán đẩy phần tử a[i] vào dãy a[i+1]…a[n] đã thỏa mãn tính chất cây heap thành dãy a[i]..a[n] cũng thỏa mãn tính chất cây heap.
Void pushdown(int * a, int i, n){
int j, max, tg;
j=i;
while (j<=n/2){
if(j==n/2)
max=2*j;
else
if (a[2*j] <=a[2*j+1])
max=2*j+1;
else
max=2*j;
if(a[j]>=a[max])
break;
else{
tg=a[j];
a[j]=a[max];
a[max]=tg;
j=max;
}
}
*) Hàm thể hiện thuật toán sắp xếp vun đống (heapsort)
Void heapsort(int *a, int n){
For (int i=n/2; i>=1; i--)
Pushdown(a,i,n);
For (int i=n; i>1; i--){
int tg=a[i];
a[i]=a[1];
a[1]=tg;
pushdown(a,1,i-1);
}
}
V, Thuật toán tìm kiếm
1, thuật toán tìm kiếm tuần tự: dãy các ftử s dc lưu bằng mảng or danh sách liên kết
-thuật toán: thực hiện so sánh khóa của phần tử số 1 với khóa cần tìm. Nếu bằng thì thông báo tìm thấy.kết thúc quá trình tìm kiếm. nếu không bằng chuyển sang phần tử kế tiếp.thực hiện lặp lại quá trình so sánh như trên.quá trình tìm kiếm dừng lại khi tìm thấy hoặc đã duyệt qua tất cả các phần tử của dãy.nếu đã duyệt qua tất cả các phần tử thì thông báo không tìm thấy.
- hàm thể hiện thuật toán:
int sequensearch(tên kiểu *s, int n, key k){
i=1;
while (i<=n)
if (s[i].key==k)
return 1;
else
i++;
return 0;
}
2,Thuật toán tìm kiếm nhị phân trên mảng:
Tập các phần tử s được lưu trữ trong 1 mảng và được sx theo thứ tự tăng dần của trường khóa
*)thuật toán: - so sánh phần tử ở giữa với khóa cần tìm nếu:
+) bằng nhau thì thông báo tìm thấy và dừng lại
+) nếu < khóa cần tìm thì thực hiện tìm ở nửa cuối của dãy cũng bằng thuật toán tìm kiếm nhị phân.
+) nếu > khóa cần tìm thì thực hiện ở nửa đầu của dãy cũng bằng thuật toán tìm kiếm nhị phân
- quá trình tìm kiếm dừng lại nếu tìm thấy hoặc phải tìm trong 1 dãy rỗng thì thông báo không tìm thấy.
*)hàm thể hiện thuật toán
int binsearch( tên kiểu *s,int n, key k){
int left,right,mid;
left=1; right =n;
while (left<=right){
mid=(left+right)/2;
if(s[mid].key==key)
return 1;
else
if(s[mid].key<k)
left=mid+1;
else
right=mid-1;
}
Return 0;
}
3, Thuật toán tìm kiếm trên cây tìm kiếm nhị phân
-Đ/N cây nhị phân tìm kiếm: cây nhị phân tìm kiếm là cây nhị phân thỏa mãn các tính chất sau:
+)giá trị của nút gốc lớn hơn giá trị khóa của tất cả các nút của cây con bên trái và nhỏ hơn giá trị khóa của tất cả các nút của cây con bên phải
+) cây con trái và cây con phải cũng là cây tìm kiếm nhị phân
- cấu trúc dữ liệu biểu diễn cây nhị phân
typedef struct node{
key key;
tên kiểu info;
node *left;
node *right;
};
- Thuật toán tìm kiếm
so sánh khóa của nút gốc với khóa cần tìm nếu:
+ bằng nhau thì thông báo tìm thấy và dừng lại
+ nếu nhỏ hơn khóa cần tìm thì tiếp tục tìm ở cây con bên phải
+ nếu lớn hơn khóa cần tìm thì tiếp tục tìm ở cây con bên trái
Quá trình tìm dừng lại khi tìm thấy hoặc phải tìm trong 1 cây rỗng, nếu phải tìm trong cây rỗng thì thông báo không tìm thấy.
*) hàm thể hiện thuật toán
int Binsearchtree( node *root, key k){
if(root==NULL)
return 0;
else
if(root -> key ==k)
return 1;
else
if(root -> key <k)
return binsearchtree (root -> right,k);
else
return binsearchtree (root -> left,k);
}
Bạn đang đọc truyện trên: Truyen2U.Pro