CTDL_II
Cấu trúc dữ liệu và giải thuật 2:
Một số ví dụ thuật toán:
Vd1: tính tổng của số tự nhiên từ 1-n:
Begin
Input n
I:=1
Sum:=0
While (i<=n) do
Sum:=sum +1;
I:=i+1;
End
Vd2: tìm ước chung lớn nhất của 2 số
Cách 1:
Function ucln(a,b:integer) : integer
Var
Begin
If (a:=0) or (b:=0) then
ucln := a+b
Else begin
While (a<>b) do
If a>b then
a:= a-b
else b:= b-a
end;
ucln1:= a;
end
cách 2: euclid
var x,y: integer
x:=a; y:=b;
while (y<>0) do
r:= x mod y;
x:=y;
y:=r;
end;
ucln:=x
vd3:hàm kiểm tra n có là số nguyên tố ko?
Function check_NT (n: integer) : boolean
Var i;
flag:= boolean;
i:= integer;
i:=2; flag:= false;
while (i<= sqrt(n)) do
if n mod i = 0 then
flag := true;
break;
end;
i:=i+1;
end;
check_NT:= flag;
end.
1)TÌM KIẾM
A) TÌM KIẾM TUẦN TỰ
Type mang=array[1..5] of integer
Function search_TT(var a : mang; n: integer; key: integer): boolean
Var i:integer ; flag: boolean;
Begin
Flag:= false; i:=1;
While (i<= N and notflag) do
Begin
a[i] := key then flag := false;
i:=i+1;
end;
search_TT = flag;
end.
B) TÌM KIẾM NHỊ PHÂN
Type mang=array[1..5] of integer
Function search_NP( var a: mang; n:integer; key:integer): boolean;
Var low, high , mid : integer;
flag : boolean;
flag:=false;
low:=1; high:=n;
while (low<= high and not flag) do
mid:= (low + high) div 2;
if a[mid] := key then
flag := true
else if key < a[mid] then
high:= mid -1
else low :=mid;
end;
search_NP:= flag;
end.
BTVN: viết 1 thủ tục để in số nguyên tố từ 1-n:
Procedure indayso(n:integer)
Var i: integer;
Begin
For i: =1 to n do
If check_NT(i) = false then
Display(i)
End;
2) SẮP XẾP
A) SELECTION SORT
Procedure selectionsort(var a:mang; n: integer);
Var i,j: integer;
Min_index : integer;
Begin
For i:=1 to n -1 do
Begin
Min_index :=1 ;
For j:= i+1 to n do
If a[j] < a[Min_index] then
Min_index := j;
If Min_index <> I then
Hoanvi(a[i] , a[Min_index]);
B) BUBBLE SORT (SẮP XẾP NỔI BỌT)
* BOTTOM UP < DƯỚI – TRÊN>:
Procedure bubble_sort (var a: mang; n: integer)
Var i,j : integer ;
Begin
For i:=1 to n-1 do
For j:=1 to n-I do
If a[j] > a[j+1] then
Hoanvi(a[j],a[j+1]);
End;
------------------------------
C) ĐỆ QUY
1 SỐ VÍ DỤ:
Viết hàm tính n!
Function giaithua(n: integer) : integer;
Var
Begin if n=0 then
Giaithua:=1
Else giaithua := giaithua(n-1)*n;
BT1: tính USCLN của 2 số nguyên dương :
Funtion UCLN (a,b:integer) : integer;
Var
Begin
If a=0 or b:=0 then
UCLN := a+b;
Else begin
If a>b then
UCLN1:= UCLN1(a-b,a)
Else
UCLN1:= UCLN1(a,b-a)
End;
BT2: euclid
Function UCLN(a,b: integer): integer;
Var
Begin
If b=0 then
UCLN2:=a
Else
UCLN2:= UCLN2(b,amodb);
+ viết chương trình con in ra dãy số Fibonaci
C1: không dùng đệ quy
a:=0 ; b:=1; c:=0; n=5;
for i:=1 to n do
c:=a+b;
a:=b;
b:=c;
display (c)
end;
C2: đệ quy:
Function fb(n: integer): integer;
Begin
If (n=0 or n=1) then fb:=n;
Else
fb:= fb(n-1) + fb(n-2);
end;
for i:=1 to n do
display fb(i)
+tìm kiếm nhị phân:
Function search_BR(var a: mang; low,high:integer; n: integer; key: integer);
Var
Begin
if low>high then
Search_BR : = false;
Else begin
Mid:= (low+high) div2;
If a[mid] >= key then
search_BR:= true ;
else if a[mid] < key then
search_BR(a, mid+1, high,nn key)
-----------------------
D) QUICKSORT (SẮP XẾP NHANH)
Procedure quicksort(var a: mang; l,r: integer);
Var i,j,x: integer;
Begin j:=r;
i:=l;
x:= a[(l+r) div 2];
repeat
while a[i] < x do inc(i); //i:=i+1
while a[j] >x do dec(j); // j:=j+1
if (i<=j) then
hoanvi(a[i],a[j]);
inc(i);
dec(j);
end;
until i>j;
if l < j then quicksort(a,l,j);
if r > i then quicksort(a,i,r);
end;
---------------------
3) TẬP HỢP
CÀI DẶT TẬP HỢP TỪ DANH SÁCH (MẢNG)
Const maxsize – 100;
Type set= record;
count : integer;
element:array [1..maxsize] of elementtype
End;
- Khởi tạo tập rỗng:
Procedure initialize(var a:set );
Begin
a.count := 0;
end;
- Xác định phần tử có trong tập a?
Function member (x:elementtype; a:set) : boolean;
Var flag : boolean;
i: integer;
flag:= false;
i:=1;
while (i <= a.count) and (not flag) do
if x = a.element[i] then
flag := true
else
i:= i+1;
end;
member:= flag;
end;
- Chèn 1 phần tử từ tập x vào tập a
Procedure insert(x: elementtype; var a:set);
Var
Begin
If (a.count <= maxsize) and (notmember(x,a))
Then
Begin
a.count := a.count +1;
a.element[a.count] := x;
end
else write(‘the set is full’);
end.
- phép hợp
Procedure union(a,b: set ; var c: set);
Var i : integer;
Begin
For i:=1 to a.count do
insert(a. element[i], c );
for i:=1 to b.count do
if notmember(b.element[i],a) then
insert (b.element[i],c);
end;
- Phép toán giao:
Procedure intersection (a,b: set ; var c: set)
Var i: integer;
Begin
Initialize(c)
For i:=1 to b.count do
If member(b. element[i],a)
Then
insert( b. element[i],c)
end;
- Phép trừ:
Procedure diference(a,b: set, var c: set)
Var i: integer;
Begin
initialize(c);
for i:= 1 to a.count do
if notmember( a. element[i],b) then
insert(a. element[i],c)
end;
4) DANH SÁCH LIÊN KẾT
(1) DANH SÁCH LIÊN KẾT ĐƠN
A) CẤU TRÚC DỮ LIỆU
List = ^pointer;
pointer = record
data: elementtype;
next: list
end;
var head.list;
B) MỘT SỐ PHÉP TOÁN
Khởi tạo danh sách rỗng:
head:= nil;
+ Chèn một phần tử p vào sau phần tử được trỏ bởi con trỏ q:
Procedure InsertAfter(x: elementtype; q: list; var head: list);
Var p: list;
Begin
New(p) //cấp phát bộ nhớ
P^.next := x;
If head = nil then
Begin
p^.next:= nil;
head := p;
end;
else
p^.next := q^.next;
q^.next := p;
end;
+ Chèn phần tử p vào trước 1 phần tử được trỏ bởi q:
Procedure InsertBefore( x: elementtype; q: list; var head: list);
Var p: list;
Begin
New(p);
If ( q = head) then
Begin
p^.data := x;
p^.next := q;
head := p;
end
else begin
p^.next := q^.next;
q^.next := p;
p^.data := q^.data;
q^.data := x;
end;
+ xóa phần tử được trỏ bởi q:
Procedure Delete( q,r : list ; var head);
Begin if q = head then
head := q^.next;
else
r^.next := q^.next;
disponse(q);
end;
+ phép toán tìm kiếm:
Procedure Search (x: elementtype; head : list; var q: list; var found : boolean);
Begin
q:= head;
while (q <> nil) and (not found) do
if (q^.data = x) then
found := true
else q^ := q^.next;
end;
---
Procedure Search2 (x: elementtype; head : list; var q,r : list; var found : boolean);
Begin
a:= head;
found := false;
r:= nil;
while ( q <> nil ) and ( not found) do
if a^.data =x then
found := true
else begin r := q;
q := q^.next;
end;
end;
+ duyệt danh sách:
Procedure Traverse( head : list);
Var q: list;
Begin
q:= head;
while ( q <> nil) do
writeln(q^.data);
q := q^.next;
end;
VD:
BÀI 1: BIỂU DIỄN ĐA THỨC BỞI DANH SÁCH LIÊN KẾT ĐƠN
a0 + a1 x^1 + a2 x^2 + … + aN x^N
list = ^pointer;
pointer = record ;
heso: real;
luythua: integer;
next : list
end;
(2) DANH SÁCH LIÊN KẾT KÉP
A) CẤU TRÚC DỮ LIỆU
Note = ^pointer;
Pointer = record
Data : elementtype;
Pre,next : Note;
End;
List : record
First, last : Note;
End;
B) MỘT SỐ THAO TÁC
+ duyệt xuôi:
Procedure forwards(q: list)
Var p: Note;
Begin
p:= q.first;
while p<> nil do
writeln( p^.data);
p:= p^.next;
end;
end;
+ duyệt ngược:
Procedure backwards(q: list);
Var p: list;
Begin p:= q^.last;
While ( p <> nil) do
Begin
Writeln(p^.data);
p:= p^.pre;
end;
end;
+ chèn 1 phần tử mới vào sau phần tử được trỏ bởi con trỏ q
Procedure InsertAfter (x: elementtype; p: Note ; var DS: list)
var p: Note;
new(p);
p^.data := x;
p^.next = q^.next;
p^.pre =q;
if q^.next = nil then
DS.last := p;
Else
(q^.next)^.pre := p;
q^.next := p;
end;
+Chèn 1 phần tử mới vào trước phần tử được trỏ bởi q:
Procedure InsertBefore (x: elementtype; p: Note ; var DS: list)
var p: Note;
new (p); p^.data:= x;
p^.next := q;
p^.pre := q^.pre;
if p^.pre = nil then
DS.first := p
Else
(q^.pre)^.next := p;
q^.pre := p;
end;
+ chèn vào đầu danh sách:
Procedure InsertBeginning(x: elementtype; p: Note ; var DS: list)
var p: Note;
if DS.first = nil then
new(p);
p^.data := x;
p^.next := nil;
p^.pre:= nil;
DS.first := p;
DS.last := p;
End
Else InsertBefore (x,DS.first;DS);
End;
+ chèn 1 phần tử mới vào cuối danh sách:
Procedure InsertEnd(x: elementtype; p: Note ; var DS: list)
var p: Note;
if DS.last =nil then
InsertBeginning(x,DS)
Else
InsertAfter(x; DS.last, DS);
End;
+ xóa 1 phần tử được trỏ bởi con trỏ q
Procedure Delete(p: Note ; var DS: list)
if q^.next := nil then
DS.last := q^.pre;
End
Else q^.pre := nil then
Begin
DS.first := q^.next;
End
Else
Begin
q^.pre^.next := q^.next;
q^.next^.pre := q^.pre;
end;
disponse(q);
end;
(3) DANH SÁCH LIÊN KẾT VÒNG
A) CẤU TRÚC DỮ LIỆU
list = ^pointer;
pointer = record
data : elementtype ;
next : list;
end;
var basic: list;
B) BA THAO TÁC CƠ BẢN (CHÈN TRÁI, PHẢI, XÓA TRÁI)
+ chèn 1 phần tử vào bên trái danh sách
Procedure insertleft(x: elementtype, var basic : list)
Var p: list;
Begin
If basic := nil then
Begin
New(p);
P^.data := x;
P^.next := p;
basic := p^.next;
end
else begin
p^.next := basic;
basic^.next := p;
end;
+Chèn 1 phần tử vào bên phải danh sách
Procedure insertright(x: elementtype, var basic : list)
Var p: list;
Begin
If basic := nil then
Begin
New(p);
P^.data := x;
P^.next := p;
basic := p^.next;
end
else
basic^.next := p;
p^.next := basic;
end;
5) STACK
(1) CÀI ĐẶT STACK = CẤU TRÚC MẢNG
A) CẤU TRÚC DỮ LIỆU
Const max = n;
Type stack = record
Top : 0..max
Data : array[1..max] of elementtype;
End;
Var s: stack;
B) MỘT SỐ THAO TÁC
+ khởi tạo stack rỗng:
Procedure initialize(var s: stack);
Begin
Stop := 0;
End;
+ kiểm tra stack rỗng
Function isempty( s: stack): boolean;
Begin
isempty := (s.top =0 );
end.
+ kiểm tra stack đầy:
Funtion isfull( s: stack): boolean;
Begin
Isfull := (stop = max);
End.
+ thêm 1 phần tử vào đỉnh stack:
Procedure push(x: elementtype; var s: stack)
Begin
If not isnull(s) then
Begin
s.top : s.top + 1;
s.data[s.top]:= x
end;
end;
+lấy 1 phần tử ra khỏi stack:
Procedure pop(var x: elementtype; var s: stack)
Begin
If not isempty(s) then
Begin
x:= s.data[s.top];
s.top:= s.top -1;
end;
end;
(2) CÀI ĐẶT STACK BỞI DANH SÁCH LIÊN KẾT
A) CẤU TRÚC DỮ LIỆU
Type stack = ^pointer;
Pointer = record
Data: elementtype;
Next : list;
End;
Var s : stack;
B) MỘT SỐ THAO TÁC
+ khởi tạo stack rỗng:
Procedure initialize(var s: stack);
Begin
s:= nil;
end;
+kiểm tra stack rỗng:
Function isempty( var s: stack): boolean;
Begin
isempty:= (s = nill);
end;
+ thêm 1 phần tử vào đỉnh stack
Procedure push(x: elementtype; var s:stack)
Var p: stack;
new(p);
p^.data:= x;
p^.next := s;
s:=p;
end;
+lấy 1 phần tử ra khỏi danh sách
Procedure pop(x: elementtype; var s:stack)
Var p: stack;
if not isempty (s) then
p:=s;
x:= p^.data;
s:= s^.next;
dispose(p);
end;
(3) BÀI TẬP ÁP DỤNG
A) DÙNG STACK ĐỂ CHUYỂN ĐỔI 1 SỐ HỆ THẬP PHÂN SANG HỆ NHỊ PHÂN
Procedure nhiphan( n: integer);
Begin
While (n <> 0) do
Begin
Push(nmod2,s);
n:= ndiv2;
end
while (not isempty(s)) do
pop(x,s);
write(x);
end
end;
C) CHUYỂN ĐỔI BIỂU THỨC TRUNG TỐ THÀNH HẬU TỐ( INFIX --> POSTFIX)
#: kết thúc biểu thức
top: phần tử đỉnh stack
pri(x): độ ưu tiên của x
procedure convert(E: infix; var E1: postfix);
read(E,x);
while x<>’#’ do
if x là toán hạng then E1 = E1 + x;
if x= ‘(‘ then push(x,s);
if x=’)’ then
while (top <> ‘(‘ ) do
pop(y,s);
E1:= E1 +y;
End;
End;
If x là toán tử then begin
While (pri(top) >= pri(x)) do
Begin
Pop(y,s);
E1 := E1 +y ;
Pop(y,s); // xóa ‘(‘
End;
Push (x, s);
End;
Read(E,x);
6) HÀNG ĐỢI (QUEUE) (FIFO)
1) Cài đặt queue bằng mảng
a)CTDL
const max=N
type queue =record
first, list : 0.. max;
data: array[0..max] of elementtype;
end;
var Q: queue;
b) một số thao tác
+thêm
procedure Addqueue( x: elementtype; var Q: queue)
if not isfull(Q) then
Q.last:= Q.last +1;
Q.data[Q.last]:= x;
End;
+xóa
Procedure DeleteQueue( var x: elementtype; var Q: queue)
if not isempty(Q) then
x := Q.data[Q.first];
if Q.first = Q.last then
Q.first := 1;
Q.last := 0;
End
Else Q.first := Q.first +1;
End;
End;
2) cài đặt queue bởi danh sách liên kết
a) cấu trúc dữ liệu
List : ^pointer
Pointer = record
data : elementtype;
next: list;
end;
queue =record
first, list : list;
end;
b) thao tác
+ khởi tạo
Procedure initialize (var Q: queue);
Begin
Q.first =nil;
End;
+ thêm 1 phần tử vào cuối hàng
Procedure addqueue(x: elementtype;var Q: queue)
Var p: list;
Begin
New(p);
p^.data := x;
p^.next := nil;
if isempty(Q) then
Q.first :=p;
Q.list :=p;
End
Else
Begin
Q.list^.next := p;
Q.list := p;
End;
+ lấy 1 phần tử từ đầu queue
Procedure deletequeue (var x: elementtype;var Q: queue)
Var p: list;
if not isempty(Q) then
p:= Q.first;
x:= p^.data;
Q.first := Q.first^.next;
Disponse(Q);
End;
Bạn đang đọc truyện trên: Truyen247.Pro