Đọc truyện Cau truc du lieu

Cau truc du lieu

Trước Sau

Màu nền

Font chữ

Font size

Chiều cao dòng

1. Cấu trúc dữ liệu là sự sắp xếp , tập hợp DLCS theo 1 trình tự nào đó nhằm liên kết chúng thành 1 cấu trúc thống nhất để tạo điều kiện thuận tiện nhất cho quá trình xử lý.

Các loại cấu trúc dữ liệu thông dụng trong thiết kế giải thuật là:

Mảng (Array)

Danh sách kiểu LIFO( Stack)

Danh sách kiểu FIFO (Queue)

Danh sách liên kết đơn ( Singly linked list)

Danh sách liên kết vòng ( Circularity linked list)

Danh sách liên kết ghép ( Double linked list)

Cấu trúc dữ liệu phi tuyến cây ( Tree)

Cấu trúc dữ liệu phi tuyến kiểu đồ thị (Graph).

Các phương pháp diễn đạt giải thuật:

Để diễn đạt 1 giải thuật, thông thường người ta có thể dùng 3 phương pháp chủ yếu sau đây:

Phương pháp 1

: diễn đạt giải thuật bằng lời

Người ta diễn đạt các bước của giải thuật 1 cách tổng quát để nhằm cho người sử dụng nắm được kỹ thuật, ý tưởng chính của giải thuật

Phương pháp diễn đạt bằng lời chưa cụ thể để diễn giải ngay được trên máy tính nhưng giúp ta nắm được ngay ý tưởng chính. Đối với những giải thuật phức tạp trên nền kinh tế, thương mại, phương pháp này giúp người sử dụng nắm được tư tưởng trực tiếp của giải thuật.

Ví dụ: bài toàn thiết lập giải thuật quản lý những người gửi tiền trong 1 ngân hàng theo chế độ không rút quỹ hàng tháng-quý-năm.

B1: Nạp số liệu: HOTEN; TIEN; THOIGIAN

B2: Tính giá trị lãi gộp( lũy kế) của số tiền nhận được ở cuối giai đoạn: FV=PV*(1+RATE)^PER

Trong đó: FV: giá trị tương lai; PV: giá trị quá khứ; RATE: lãi suất; PER: thời gian gửi.

B3: Kiểm tra danh sách khách hàng, nếu đã kết thúc thì in kết quả FV; không thì quay lại B2

B4: In ra danh sách FV của khách hàng.

B5: kết thúc giải thuật.

Phương pháp 2

: diễn đạt bằng lưu đồ

Lưu đồ là 1 công cụ được sử dụng rộng rãi trong các công ty phần mềm và được thông nhất trên toàn thế giới.

Khối xử lý

---------> dòng thông tin

( có mệnh để true false t ko biết vẽ)

Tư tưởng của phương pháp này là trên cơ sở ý đồ chủ đạo của giải thuật, người ta tiến hành xây dựng các khối biểu diễn các quy tring tính toán và mối liên hệ giữa các khối với nhau. Người ta có thể dùng lưu đô để biểu diễn các quy trình TQ có tính chất tổng hợp cao hoặc biểu diễn những quy trình tính toán cụ thể.

Ví dụ: giải pt bậc 2 (TL)

Phương pháp 3

: diễn đạt giải thuật bằng 1 ngôn ngữ lập trình cụ thể

Theo phương pháp này, người ta sử dụng 1 ngôn ngữ lập trình có cấu trúc ( như Pascal chẳng hạn) để biểu diễn 1 thuật toán.

VD: giải thuật của bài toán tính giá tri tổng sản lượng của doanh nghiệp.

Type A= array [1..n,1..m] of real;

B= array [1..m] of real;

C= array[1.,n] of real;

Var soluong: A; stsp: C; gia: B; i,j: integer; tong: real;

Begin For i:=1 to n do

For j:=1 to m do readln(soluong[i,j]);

For j:=1 to m do readln(gia[j]);

For i:=1 to n do

Begin gtsp[i]:=0;

For j:=1 to m do gtsp[i]=gtsp[i]+soluong[i,j]*gia[j];

End;

Tong:=0; for i:=1 to n do tong:=tong+gtsp[i];

Write(‘gia tri tong san luong’);

Writeln(tong:12:2);

End;

3. Phương pháp thiết kế từ đỉnh xuống:

Đây là phương pháp dựa trên ý tưởng của modul hóa, tức là khi thiết kế 1 phần mềm người ta thiết kế modul tổng quát sau đó chia thành các modul thành phần càng nhỏ và chi tiết hơn để giải quyết 1 vấn đề cụ thể, tức là chuyển dàn từ modul chính đến các modul con từ trên xuống dưới, do vậy phương pháp có tên gọi là “thiết kế từ đỉnh xuống” (top down design)

Lĩnh vức áp dụng của phương pháp này là HTQL đang thực hiện theo cơ chế thủ công.

VD: nghiên cứu bài toán thống kê HTQL trong 1 trung tâm thương mại. Quy trình thiết kế được thực hiện theo các bước sau đc gọi là phác thảo:

Phác thảo 1

: design menu tổng quát:

QL TTTM

QL kho hàng

QL nhân lực

QL kinh doanh

Ta tiếp tục chi tiết hóa các modul cấp 2

Phác thảo 2:

QL kho

QL xuất kho QL lưu kho QL nhập kho

Phác thảo 3:

QL nhân lực

QL sd nhân lực QL tuyển NL Tính toán lương

Phác thảo 4:

QL kinh doanh

Lập kế hoạch KD Tính toán doanh số Tính toán lợi nhuận

Phác thảo 5

: trên cơ sở 4 phác thảo đầu tiên, ta tích hợp thành 1 HT hoàn chỉnh thường đgl kiến trúc của 1 HT ( vẽ hình ra)

Đây là nền tảng trong quá trình phát triển hệ thống, đgl toàn bộ xương sống của HT

Việc thiết kế kiến trúc là khâu cơ bẩn nhất của việc xây dựng 1 phần mềm cũng như bản vẽ trong xây dựng.

4. Phương pháp thiết kế từ dưới lên:

Tư tưởng của phương pháp thiết kế này ngược lại với phuwong pháp thiết kế tử đỉnh xuống: trước hết ng ta giải quyết các vấn đề cụ thể, sau đó trên cơ sở đánh giá mức dộ tương tự về chức năng của các vấn đề này trong việc giải quyết bài toán người ta gộp chúng lại thành từng nhóm cùng chức năng từ dưới lên trên cho đến modul chính. Sau đó sẽ thiết kế thêm 1 số chương trình làm phong phú hơn, đầy đủ chức năng của các phân hệ và cuối cùng là thiết kế 1 chương trình làm nhiệm vụ tập hợp các modul thành 1 hệ chương trình thống nhất, hoàn chỉnh.

<B1: phân tích chức năng của các ứng dụng cụ thể và gộp chúng thành từng nhóm có chùng chức năng

B2: phát triển thêm ứng dụng trong các nhóm

B3: tích hợp hệ thống>

Lĩnh vực ứng dụng của phương pháp này là HT tin học hóa từng phần.

VD: XD 1 HT ứng dụng để quản lý 1 doanh nghiệp. Doanh nghiệp này đã tin học hóa ở 1 số bộ phận, bao giờ BG Đ cũng muốn phát triển và hoàn thiện thêm HT. Quy trình thiết kế minh họa theo chương trình sau:

B1: Chi tiết các ứng dụng

program1: đưa vào hồ sơ bộ.

program2: sữa chữa bổ sung hồ sơ

program3: nhập nguyên vật liệu

program4: nhập hóa đơn

program5: tính lương

program6: dự toán nguyên vật liệu

program7: quản lý cán bộ

program8: giá trị sản phẩm.

Ta có phác thảo: Phân tích gộp từng nhóm theo chức năng:

phác thảo 1: gộp các program 1-2-5-7 : quản lý nhân sự

phác thảo 2: gộp program 4-8: quản lý bán hàng

phác thảo 3: gộp program 3-6: quản lý kho.

( VẼ SƠ ĐỒ phác thảo)

B2: phát triển các ứng dụng trong mỗi nhóm

program 9: dự báo mưc tiêu thụ hàng hóa

program 10: bảng tổng hợp hàng tồn kho

B3: tích hợp trên cơ sở các ứng dụng ban đầu và các ứng dụng phát triển thêm ta tích hợp thành một hệ thống hoàn chỉnh

( VẼ SƠ ĐỒ HOÀN CHỈNH)

5. Độ phức tạp của giải thuật

: giải thuật là 1 vấn đề trung tâm của tin học vì nói 1 cách đơn giản và dễ hiểu thì giải thuật chính là trả lời cho câu hỏi làm thế nào để giải quyết vấn đề đặt ra.

Để đánh giá độ phức tạp của 1 giải thuật ng ta dùng 1 hằng số T(n) trong đó n là số lượng các phép toán của giải thuật. Ng ta sử dụng kí pháp chữ “O” của toán học để xác định mức dộ phức tạp của giải thuật như sau:

1 giải thuật A có hàm đánh giá độ phức tạp T(n), bậc phức tạp n nếu: lim khi n tiến đến vô cùng của T(n)/n là 1 hằng số. (VIẾT BIỂU THỨC LIM)

Dựa vào định nghĩa này để xác định độ phức tpaj của 1 giải thuật, chúng ta thức hiện các bước sau đây:

B1: Diễn giải từng bước của giải thuật

B2: Xác định hàm T(n)

B3: Xác định giới hạn của T(n)/n nếu giới hạn này là 1 hằng số thì bậc phức tạp của giải thuật là n.

VD: Xác định độ phức tạp của giải thuật:” tính năng suất lao động TB của n doanh nghiệp” (TRONG VỞ)

CÁC KIỂU CẤU TRÚC DỮ LIỆU

MẢNG MỘT CHIỀU

Khái niệm

Mảng (array) là một tạp hợp có thứ tự bao gồm một số lượng cố định các phần tử, được truy cập với cùng một tên.

Mảng một chiều (vector) là một kiểu cấu trúc dữ liệu có số lượng nhất đinh các phần tử được truy cập với cùng một tên nhưng với các chỉ số khác nhau.

Mảng một chiều rất dễ bắt gặp trong cuộc sống: năng suất lao động của 10 Doanh nghiệp; một dãy số thống kê gồm 20 giá trị về doanh số bán hàng …

Phương pháp lưu trữ

Để lữu trữ mảng một chiều trong bộ nhớ người ta dùng một không gian nhớ tuyến tính liên tiếp để chứa từng phần từ mảng theo mô hình sau:

Địa chỉ Vùng nhớ Phần tử mảng

Base(A)+0

<--

A[1]

Base(A)+1

<--

A[2]

Base(A)+2 <---

A[3]

Base(A)+3 <---

A[4]

……. 110010101111001

Base(A)+(n-1)

<--

A[n]

Base(A) : địa chỉ cơ sở

A: array[1..n] of real;

Các phép toán với mảng một chiều

Các phép toán thông dụng với mảng một chiều gồm :

CREATE: Tạo lập mảng một chiều

SORTING: Sắp xếp mảng một chiều

SEACHING: Tìm kiếm trong mảng một chiều

CALCULATE: Tính toán với mảng một chiều

* Tạo lập mảng một chiều:

Cho vector: array[1..n] of real;

Giải thuật tạo lập lần lượt đặt các phần tử của vector bắt đầu từ thành phần đầu tiên vào vùng không gian nhớ cơ sở được chọn và lần lượt cho đến phần tử cuối cùng.

Procedure CreateVector

(a: Vector; vả n: integer);

Var

i: integer;

Begin

for i:=1 to n do

Begin

Write(‘a[‘,i,’]=’);

Readln(a[i]);

End;

* Sắp xếp mảng 1 chiều

Sắp xếp là một phép toán tương đối thông dụng. Trong thực tế thường xuất hiện nhu cầu sản xuất các thành phần của mảng một chiều theo một trình tự xác định tiện lời cho việc xử lý.

Có nhiều giải thuật sản xuất khác nhua trong đó có 1 giải thuật rất thông dụng là so sánh liên tiếp 2 thành phần với nhau, thành phần nào lớn hơn sẽ bị đẩy về phía sau ( sản xuất tăng dần) và ngược lại.

Procedure SortVector

( a: Vector; var n: integer);

Var

j,i: integer;

tg: real;

begin

for i:= 1 to n-1 do

for j:= i+1 to n do

if a[i] >a[j] then

begin

tg := a[i];

a[i] := a[j];

a[j] := tg;

(*Đổi chỗ a[i] và a[j] *)

end;

* Tìm kiếm trong mảng một chiều:

Cho mảng một chiều A gồm n phần tử. Giải thuật tìm kiếm một phần tử của mảng có giá trị bằng một đại lượng T cho trước:

Function SeachingVector

(a: Vector; var n: integer): real;

Var

I: integer;

T: real;

Begin

For i:= 1 to n do

If a[i] = T then SeachingVector:= a[i] else Writeln(‘Không có’)

End;

* Tính toán với mảng một chiều

Trong kinh tế thường phải tính toán:

Giá trị trung bình

Phương sai

Độ lệch chuẩn

Cho vector A[i] i=1,n giải thuật được biểu diễn dưới dạng một thủ thuật sau:

Procedure CalculateVector

( a: vector; var n: integer)

Var

I: integer;

TB, PS, ĐLC: real;

Tong: real;

Begin

Tong:= 0;

For i:= 1 to n do

Tong: = Tong + a[i];

TB:= Tong/n;

For i:=1 to n do

Tong: = Tong + sqr( TB – a[i]);

PS:= Tong/n;

ĐLC:= sqrt(PS);

End;

II.

MẢNG HAI CHIỀU

Khái niệm

Mảng hai chiều được truy cập với cùng một tên nhưng với 2 chỉ số khác nhau, Do đó có sự phân biệt vị trí của các chỉ số.

A=[aij] với i – dòng j – cột

Cấu trúc mảng 2 chiều rất thường gặp trong kinh tế. Chẳng hạn như bảng tổng hợp kinh doanh trong một trung tâm thương mại bán ra m mặt hàng cho n khách hàng là một mảng 2 chiều…

Phương pháp lưu trữ

Mảng 2 chiều có 2 phương pháp lưu trữ phụ thuộc vào ngôn ngữ kaaj trình được sử dụng:

Lưu trữ theo dòng ( trong BASIC, PASCAL)

Lưu trữ các thành phần lần lượt của các dòng hết dòng này đến dòng khác.

Lưu trữ theo cột ( trong FORTRAN)

Lưu trữ các thành phần các cột của ma trận từ hết cột này đến cột khác.

VD:

A = 3 4 7

5 6 5

7 6 4

ROW: Địa chỉ Vùng nhớ Phần tử mảng

Base(A) + 0 011 A[1,1]

100 A[1,2]

111 A[1,3]

101 Row 2

110

101

111 Row 3

110

100

COLUMN: Địa chỉ Vùng nhớ Phần tử mảng

Base(A) + 0 011 A[1,1]

101 A[2,1]

111 A[3,1]

100 column 2

110

111 column 3

101

100

Phép toán

* Mô tả biến Matrix

Var

matrix: array[1..n,1..m] of real;

* Tạo lập

Procedure CreateMatrix

( a: matrix; var n,m: integer0;

Var

i, j: integer;

Begin

For i: = 1 to n do

For j: = 1 to m do

Begin

Write(‘a[‘, i ,’, j , ‘]=’);

Readln (a[i,j]);

End;

end;

Giải thuật này lần lượt sản xuất các phần tử của mảng theo dòng, hết dòng này đến dòng khác.

* Tìm kiếm

Cho mảng 2 chiều A= a[i,j] i= 1,..,n

j= 1,...,m

Giải thuật tìm kiếm 1 phần tử của mảng có giá trị bằng một đại lượng L cho trước được biểu diễn như sau:

Function SeachingMatrix

(a: matrix; Var n, m: integer) : real;

Var

i,j: integer;

L: real;

Begin

For i: =1 to n do

For j: = 1 to m do

If a[i,j] = L then seachingMatrix: = a[i,j]

Else writeln(‘Không có’);

End;

* Nhân mảng 2 chiều với một vector

Cho mảng 2 chiều A=a[i,j] và vector B=[bj]

Nhân mảng 2 chiều A với vector B. Mỗi thành phần của mảng kết quả là mảng một chiều Ci được xác định theo công thức

Ci = Tổng từ j=1 đến m ( aij*bj) i=1…n

Giải thuật biểu diễn như sau:

Procedure MultiMatrix

( a: matrix; b,c: vector; Var n,m: integer);

Var

I,j: integer;

Begin

For i:= 1 to n do

For j:=1 to m do

Begin

Write(‘a[‘, i ,’, j , ‘]=’);

Readln (a[i,j]);

End;

For j:= 1 to m do

Begin

Writeln(‘b[‘, j ,’]=’);

Readln(b[j]);

End;

For i:= 1 to n do

Begin

C[i]:= 0;

For j:=1 to m do

C[i]: = c[i] + a[i,j]* b[j];

End;

For i:= 1to n do

Begin

Write(‘c[‘, i ,’]=’);

Writeln(c[i]);

End;

* Cộng mảng 2 chiều

Cho 2 mảng 2 chiều A=a[i,j] và B=b[i,j]

C = A + B trong đó mỗi thành phần của mảng kết quả c[i,j] được xác định theo công thức:

Cij = Aij + Bij

Procedure AdditionMatrix(a,b,c: matrix; Var n,m: integer);

Var

i,j: integer;

Begin

For i: = 1 to n do

For j: = 1 to m do

Begin Write(‘a[‘, i ,’, j , ‘]=’);

Readln (a[i,j]);

End;

For i: = 1 to n do

For j: = 1 to m do

Begin Write(‘b[‘, i ,’, j , ‘]=’);

Readln (b[i,j]);

End;

For i: = 1 to n do

For j: = 1 to m do

Begin

c[i,j] = a[i,j] +b[i,j];

end;

For i: = 1 to n do

Begin

For j: = 1 to m do Write(c[i,j]);

Writeln;

End;

* Nhân mảng 2 chiều A và B

C = A* B trong đó mỗi thành phần của mảng kết quả Cij được xác định theo công thức

Cij = Tổng từ K=1 đến q ( Aik * Bkj)

Procedure MultiMatrix

( a,b,c: Matrix; var n,m,q: integer);

Var

k, i, j : integer;

Begin

For i: = 1 to n do

For k: = 1 to q do

Begin write(‘a[‘, i ,’,’, k ,’]=’);

Readln(a[i,k]);

End;

For k: = 1 to q do

For j: = 1 to m do

Begin write(‘b[‘, k ,’,’, j ,’]=’);

Readln(b[k,j]);

End;

For i: = 1 to n do

For j: = 1 to m do

Begin c[i,j]: = 0;

For k: = 1 to q do

C[i,j]:= c[i,j] + a[i,k] *b[k,j];

End;

For i: = 1 to n do

Begin

For j: = 1 to m do Write(c[i,j]);

Writeln;

End;

III.

DANH SÁCH ĐẶC

Khái Niệm Cấu Trúc Danh Sách

Danh sách (List) là một tập hợp gồm nhiều phần tử a1, a2,…an có tính chất cấu trúc thứ tự giữa các phần tử với nhau: nếu biết được vị trí phần tử ai thì sẽ biết được vị trí của phần tử ai+1

n: là độ dài danh sách

n = 0 danh sách rỗng

độ dài danh sách > n : danh sách bị tràn

* So sánh CTDL danh sách và mảng 1 chiều A[i] i=1,n

Giống nhau: Danh sách và mảng 1 chiều đều là tập hợp dữ liệu có thứ tự cố định và 1 số lượng xác định các phần tử

Khác nhau

Mảng 1 chiều : các phép toán thông dụng được thực hiện đồng thời với tất cả các thành phần của mảng. Rất ít khi thực hiện phép toán bổ sung hoặc loại bỏ phần tử của mảng.

Danh sách: các phép toán bổ sung và loại bỏ phần tử được thực hiện thường xuyên.

Khái Niệm Danh Sách Đặc

Danh sách đặc là một tập hợp gồm nhiều phần tử a1, a2,…an có tính chất cấu trúc thứ tự, các phần tử kế tiếp nhau, không có khoảng trống giữa các phần tử

Các Phép Toán Với Danh Sách Đặc

Tìm kiếm 1 phần tử trong Danh sách:

thông tin để tìm kiếm gọi là khoa (Key). Kết quả của phép tìm kiếm là vị trí của phần tử trong Danh sách nếu tìm thấy.

Bổ sung phần tử vào Danh sách:

Có thể bổ sung thêm vào đầu, giữa hoặc cuối danh sách. Sau khi bổ sung thì số lượng các phần tử của danh sách sẽ tăng thêm 1. Các phần tử đi sau “phần tử thêm vào” sẽ bị thay đổi vị trí sau khi thực hiện phép bổ sung.

Loại bỏ 1 phần tử khỏi danh sách:

Trước khi loại bỏ phải tìm kiếm phần tử đó, nếu tìm thấy thì thực hiện việc loại bổ, sau đó số lượng các thành phần của danh sách sẽ giảm đi 1. Các phần tử đings sau phần tử bị loại bỏ sẽ bị thau đổi vị trí trong danh sách.

Thay thế 1 phần tử của danh sách bởi 1 phần tử khác:

Các phần tử của danh sách có thể bị thay đổi vị trí sau khi thực hiện phép toán thay thế nếu danh sách phải thoả mãn một điều kiện ràng buộc nào đó.

Tách 1 danh sách thành nhiều danh sách:

Sau khi tách thì tổng số các phần tử của các danh sách mới phải bằng số phần tử của danh sách cũ. Phép tách phải căn cứ vào 1 tiêu chuẩn nào đó.

Ghép nhiều danh sách thành 1 danh sách:

kết quả của phép ghép là tạo ra 1 danh sách có số lượng các phần tử bằng tổng các phần tử của các danh sách thành phần.

Trộn nhiều danh sách thành 1 danh sách mới:

Khi trộn phải dựa vào 1 quy tắc nào đó. VD: sắp xếp phần tử tăng dần hay giảm dần.

Sắp xếp thứ tự một danh sách:

Khi sản xuất ta phải dựa vào 1 khoá nào đó. Việc sản xuất sẽ làm thay đổi vị trí của các phần tử trong danh sách theo trình tự của khoá.

IV.

CẤU TRÚC DỮ LIỆU STACK(danh sách kiểu ngăn xếp)

Khái niệm

Stack là một kiểu danh sách tuyến tính đặc biệt mà việc bổ sung hay loại 1 phần tử chỉ thực hiện ở một đầu gọi là đỉnh (Top)

VD: Một tệp đơn trong ngân hàng được đánh số từ 1 đến 9. Khi thu hoá đơn, người ta xếp chúng vào một cái hộp theo trình tự từ 1 đến 9. Khi lấy các hoá đơn ra khỏi hộp, hoá đơn xếp vào hộp sau cùng sẽ được lấy ra đầu tiên và hoá đơn xếp vào đầu tiên sẽ được lấy ra cuối cùng. Giả sử I (Input) là phép đưa vào hộp một hoá đơn, O (Output) là phép toán lấy từ hộp ra 1 hoá đơn.

Nguyên tắc “vào sau ra trước” là đặc trưng cơ bản của stack . Cũng do đó người ta gọi stack là danh sách kiểu LIFO (Last – In – First – Out).

Phương pháp lữu trữ

Chúng ta xem xét việc lưu trữ Stack kế tiếp bằng một mảng. Vì stack là một dãy các mục dữ liệu chúng ta có thể dùng mảng để lưu trữ các mục này. Mỗi phần tử của ngăn xếp chiếm 1 vị trí trong mảng và vị trí thứ nhất phục vụ như là đỉnh của Stack. Giả sử ta muốn lưu trữ Stack bằng vector lưu trữ S(n) gồm n phần tử. Gọi Top là địa chỉ phần tử đỉnh của Stack, Top là một biến động. Khi Stack rỗng ta qui ước Top=0; khi Stack bị tràn (overflow) thì Top = n. Giả sử mỗi phần tử của Stack chiếm một từ máy. Khi bổ sung 1 phần tử thì Top: = Top +1, khi loại bỏ 1 phần tử thì Top:= Top – 1.

Các phép toán với Stack

* Tạo lập Stack

Procedure CreateS

( Var Stack: StackType);

( Thủ tục tạo lập một Stack rỗng)

Begin

Stack.Top := 0;

End;

*Xác định Stack rỗng

Function EmptyS

( Stack: StackType): Boolean;

(Giá trị của hàm là đúng nếu Stack rỗng)

Begin

Empty:= (Stack.Top=0);

End;

*Bổ sung 1 phần tử vào Stack

Procedure Push

( Var Stack: StackType; Item: ElementType);

Begin

If Stack.Top = StackLimit then Halt (Đẩy vào một ngăn xếp đã đầy)

Else

With Stack do

Begin

Top:= Top+1;

Element[Top]:= Item;

End;

*Loại bỏ 1 phần tử khỏi Stack

Xét giải thuật loại bỏ phần tử ở đỉnh của Stack được lưu trữ bởi vector lưu trữ S gồm n phần tử

Procedure Pop

( Var Stack: StackType; Var Item: ElementType);

Begin

If EmptyS(Stack) then

Halt (Lấy ra từ một ngăn xếp đã rỗng)

Else

With Stack do

Begin

Item:= Element[Top];

Top: = Top - 1;

End;

CẤU TRÚC DỮ LIỆU QUEUE (danh sách kiểu hàng đợi)

Khái niệm

Queue là kiểu danh sách tuyến tính mà phép bổ sung một phần tử được thực hiện ở một đầu gọi là lối sau (Rear); còn phép loại bỏ 1 phần tử thực hiện ở một đầu khác gọi là lối trước (Front).

Hàng đợi là 1 kiểu cấu trúc dữ liệu – danh sách không đầy đủ. Hàng đợi là kiểu danh sách mà việc bổ sung 1 phần tử được thực hiện ở 1 đầu còn việc loại bỏ 1 phần tử được thực hiện ở 1 đầu khác.

Nguyên tắc cơ bản của cấu trúc kiểu hàng đợi là First – In – First – Out (FIFO)

Danh sách kiểu hàng đợi vì vậy có nhiều ứng dụng trong giải quyết các bài toán thực tế:

1 hàng xe ô tô xếp hàng vào kho lấy hàng hoặc qua cửa soát vé.

Trong một mạng máy tính người ta tổ chức 1 hàng đợi ghi yêu cầu của người sử dụng khác nhau, ai gửi yêu cầu đến trước sẽ được xử lý trước.

Để quản lý máy bay cất cánh trong 1 sân bay người ta tổ chức 2 hàng đợi, 1 hàng đợi máy bay chờ cất cánh và hàng đợi máy bay hạ cánh, hàng hạ cánh được ưu tiên.

Phương pháp lữu trữ

Có 2 phương pháp lữu trữ:

Tuyến tính lưu trữ Queue

Lưu trữ queue bằng danh sách nối vòng

Tuyến tính lưu trữ Queue

Trong trường hợp này Queue được lưu trữ trong một vector lưu trữ Q có n phần tử. Để có thể truy cập vào Queue ta dùng 2 biến con trỏ:

Biến R trỏ vào lối sau của Queue

Biến F trỏ vào lối trước của Queue

Nếu Queue rỗng thì R = 0 và F = 0

Giả sử mỗi phần tử của Queue chứa trong 1 từ máy thfi khi bổ sung thêm 1 phần tử R:= R +1

Còn khi loại 1 phần tử thì F:= F +1

Căn cứ vào chiều quy định mà việc tính toán khác nhau.

Nếu tổ chức theo kiểu tuyến tính thì sau khi bổ sung/ loại bỏ 1 phần tử hàng đợi sẽ có sự dịch chuyển và xảy ra tình huống tuy còn chỗ trống nhưung không thể bổ sung thêm phần tử.

Phương pháp lưu trữ tuyến tính Queue bằng mảng tương tự như lưu trữ Stack có 1 nhược điểm dễ thấy là khi ta thực hiện liên tiếp các phép bổ sung và loại bỏ dù chỉ 1 phần tử thì Queue sẽ di chuyển khắp vùng không gian nhớ tuy số lượng phần tử là cố định. Để khắc phục vấn đề này người ta áp dụng phương pháp thứ 2 để lưu trữ Queue, đó là lưu trữ kiểu danh sách nối vòng.

Lưu trữ queue bằng danh sách nối vòng

Trong trường hợp này chúng ta coi không gian nhớ như được tổ chức theo kiểu hình tròn. Đầu và cuối hàng đợi được nối liền với nhau, tức là phần tử Q[1] của vector lưu trữ sẽ đứng sau Q[n].

Giả sử Queue được lưu trữ bởi vector lưu trữ Q có n phần tử, F và R là 2 con trỏ, trỏ vào lối trước và lối sau của nó.

Với cách lưu trữ này ta không cần dịch chuyển các vùng không gian nhớ. Giả sử đến tận cùng Q(n) sau đó sẽ chuyển về đầu danh sách Q(1).

Trong thực tiễn khi xây dựng các phần mềm tuỳ từng bài toán cụ thể mà người ta sử dụng bài toán tuyến tính hay nối vòng để có được 1 phương pháp tổ chức dữ liệu tối ưu và hiệu quả.

Các phép toán với Queue

* Tạo lập

Procedure CreateQ

( Var Queue:QueueType);

(Tạo một Queue rỗng)

Begin

Queue.Front: = 0;

Queue.Rear: = 0;

End;

* Kiểm tra Queue rỗng

Function EmptyQ

( Queue: QueueType) : Boolean;

(Hàm có giá trị đúng nếu Queue rỗng)

Begin

EmptyQ: = ( Queue.Front = Queue. Rear);

End;

* Chèn vào Queue

Procedure AddQ

( Var Queue: QueueType; Item: ElementType);

Var

Newrear : 0 …MaxPosition;

Begin

With Queue do

Begin

NewRear:= (Rear+1) mod MaxSize;

If NewRear = Front then

Halt

Else

Begin

Element[Rear] := Item;

Rear:= Newrear;

End;

* Giải thuật loại khỏi Queue

Procedure RemoveQ

( Var Queue: QueueType; Var Item: ElementType);

Begin

If EmptyQ(Queue) then

Halt

Else

With Queue do

Begin

Item: = Element[Front];

Front:= ( Front +1) mod MaxSize

End;

Câu 14. Khái niệm DSLK, cho VD:

Chúng ta nghiên cứu các loại danh sách khác nhau trong đó có 1 nét đặc trưng là để lưu trữ các danh sách này phải dùng 1 vùng không gian chứa đủ lớn. Khi bài toán giải quyết xong, vùng không gian nhớ này được giải phóng. Nhưng trong thực tiễn khi phân phối bộ nhớ động, chúng ta có nhiều miền không gian nhớ nằm rải rác riêng từng phần thì không đủ chứa DL của bài toán, nhưng nếu kết hợp lại thì vẫn đủ. Từ đó người ta nảy sinh ý tưởng là liên kết các vùng không gian nhớ nằm rải rác. Ý tưởng này chính là cơ sở để hình thành danh sách liên kết.

“Danh sách liên kết cũng là một kiểu danh sách tuyến tính gồm các phần tử vào lần lượt theo thứ tự tuy nhiên nó khác stack và queue ở chỗ là nó được cấp phát trong bộ nhớ bởi các phần tử rời rạc nhau, không nằm kề nhau, tuy nhiên giữa phần tử trước thì có 1 liên kết đến phần tử sau nó”.

-> chính vì ý tưởng này mà người ta gọi danh sách liên kết là phương pháp thu hồi chỗ bị thải trong bộ nhớ.

Câu 15. Phương pháp lưu trữ DSLK

Mỗi một DSLK được tạo nên từ các đơn vị gọi là node, mỗi node bao gồm 1 số lượng ô nhớ liên tiếp nhau, mỗi node có thể nằm rải rác. Với mỗi node người ta chia làm 2 phần: 1 phần chứa DL, 1 phần chứa địa chỉ node đứng sau. Còn để truy cập vào DSLK người ta sử dụng con trỏ L:

Node[x

].data: chứa dữ liệu

Node[x].next: địa chỉ node sau

Có 2 phương pháp biểu diễn:

Biểu diễn bằng mảng

Biểu diễn bằng biến con trỏ

=> Biểu diễn bằng mảng

Vì DSLK là 1 loại CTDL phức tạp, không được thiết kế sẵn trong các ngôn ngữ lập trình vì thế người ta phải nảy ra ý tưởng lưu trữ chúng thông qua 1 kiểu cấu trúc thông dụng là mảng. Giả sử ta có danh sách với các giá trị A, B, C, D. Khi đó hình ảnh lưu trữ bằng mảng được biểu diễn như sau:

Chỉ số Dữ liệu Địa chỉ (Next)

1 C 6

4 A 8

6 D Rỗng

8 B 1

Kí hiệu nil : 0, cuối LL

Node[4].data=A

Node[4].next=8

Node[8].data=B

Node[8].next=1

Node[1].data=C

Node[1].next=6

Node[6].data=D

Node[6].next=0

Trong trường hợp là mảng thì chỉ số sẽ lần lượt tăng dần, nhưng trong DSLK thì không phải như vậy mà có thể tăng hoặc giảm.

Câu 16. Phân tích giải thuật duyệt DSLK bằng mảng

Procedure( Linked Traverse( L: pointẻ Type)

Var

Curptr: Pointer type

Begin

Currptr:=L; (1)

While Currptr<>0 do (2)

Begin

Write(node[Currptr].data); (3)

Currptr:=node[Currptr].next; (4)

End;

End.

Bước 1: Giải thích

Câu lệnh 1: Truy cập vào đầu danh sách

Câu lệnh 2: Lần lượt xư lí từng node của DSLK

Câu lệnh 3: In ra trường dữ liệu của node đầu tiên(hiện thời)

Câu lệnh 4: Con trỏ hiện thời được gán bằng giá trị địa chỉ của con trỏ chỉ đến

Bước 2: Graphic

Chỉ số Dữ liệu Địa chỉ (Next)

1 C rỗng

4 A 8

8 B 1

Bước 3: Phân tích

(1)

Currptr:=4, vì 4<>0 nên in ra A, Currptr:=8

+ vì 8<>0 nên in ra B

Currptr:=1

+ vì 1<>0 nên in ra C

Currptr=0 =>kết thúc in ra A, B, C

Câu 17. DSLK lưu trữ bằng con trỏ

Con trỏ trả về tính chất là 1 ô nhớ.

X^.data: phần dữ liệu

X^.next: địa chỉ của con trỏ sau

VD: L=30

30 10 40 50

----> A | --------> B | -----------> C | -----------> D |

30^.data=A

30^.next=10

10^.data=B

10^.next=40

40^.data=C

40^.next=50

50^.data=D

50^.next=0

Câu 18. Phân tích một số giải thuật đối với DSLK bằng con trỏ

Xét giải thuật duyệt danh sách lưu trữ bằng con trỏ. Khái niệm duyệt được hiểu là truy cập vào 1 danh sách để lấy dữ liệu nhằm 1 mục đích nào đó.

Giải thuật:

Procedure Linked Pointer(L: pointer type)

Var

Currptr: pointer type;

Begin

Currptr:=L; (1)

While Currptr<>0 do (2)

Begin

Write(Currptr^.data); (3)

Currptr:= Currptr^.next; (4)

End;

End.

Bước 1: Giải thích

(1): Truy cập vào DSLK

(2): Xử lí lần lượt các Pointer

(3): In ra trường dữ liệu của pointer hiện thời

(4): Chuyển đến pointer sau

Bước 2: Graphic

10 20 7 25

----> A | --------> B | -----------> C | -----------> D |

Bước 3: Phân tích

1, L=10, vì 10<>0 nên in ra A

Currptr:=20

2, vì 20<>0 nên in ra B

Currptr:=7

3, vì 7<>0 nên in ra C

Currptr:=25

4, vì 25<> nên in ra D

Currptr=0 => kết thúc in ra A, B, C, D

Câu 19. Các khái niệm:

Cây

: là 1 kiểu CTDL phi tuyến bao gồm 1 tập hợp các nút có mối quan hệ phân cấp xuất phát từ một nút gọi là gốc(Root)

Cây nhị phân

: là 1 trường hợp riêng của cây tổng quát, trong đó ở mỗi nút chỉ có 2 nhánh: nhánh trái và nhánh phải. Mỗi nút của cây có thể nhận giá trị là chữ hay số.

Để lưu trữ cây nhị phân, người ta dùng 2 phương pháp:

1 Lưu trữ bằng mảng

người ta đánh số liên tiếp từ trái qua phải thứ tự các nút và lưu trữ vào vùng nhớ.

10101101 <----- 1

10101110 <----- 2

2 3

Khi biết địa chỉ của 1 nút n nào đó, ta xác định được địa chỉ của 2 nút con của nó là 2n và 2n+1.

2 Lưu trữ bằng DSLK

người ta xét thêm khái niệm liên kết kép: nút của nó có công thức như sau:

Data

L child R child

Câu 20

Có 3 phương pháp cơ bản để duyệt cây nhị phân:

*)PP duyệt theo tiền tự:

B1: thăm gốc của cây

B2:duyệt cây con trái theo thứ tự tiền tự

B3:duyệt cây con phải theo thứ tự tiền tự

*)Pp duyệt theo trung tự:

B1:duyệt cây con trái theo thứ tự trung tự

B2: thăm gốc của cây

B3:duyệt cây con phải theo thứ tự trung tự

*)PP duyệt theo hậu tự:

B1:duyệt cây con trái theo thứ tự hậu tự

B2: duyệt cây con phải theo thứ tự hậu tự

B3:thăm gốc của cây

*) Ví dụ: cho cây nhị phân:

B C

E F G H

+) trình tự duyệt cây theo tiền tự:

A B E F C G H

+) trình tự duyệt theo trung tự:

E B F A G C H

+) trình tự duyệt cây theo hậu tự:

E F B G H C A

Câu 21

K/n: Cây nhị phân tìm kiếm là một trường hợp đặc biệt của cây nhị phân, mà mỗi nút của nó thỏa mãn 2 điều kiện sau:

+ Cây con trái có giá trị nhỏ hơn giá trị nút gốc trực tiếp của nó

+ Cây con phải có giá trị lớn hơn giá trị nút gốc trực tiếp của nó

*) PP xd cay nhị phân tìm kiếm

B1:lấy số đầu tiên trong dãy số làm nút gốc.

B2:lấy số thứ 2 trong dãy số so sánh vs nút gốc, nếu nhỏ hơn nút gốc thì là cây con bên trái, nếu lớn hơn nút gốc thì là cây con bên phải.

B3:Quá trình cứ tiếp diễn như vậy cho dến hết dãy số.

*Nếu dãy tìm kiếm là một dãy các chữ cái thì thứ tự xét sẽ là thứ tự của chúng trong bảng chữ cái.

*)VD: cho dãy số: 15,12,24,9,14,21,30

Cây nhị phân tìm kiếm:

12 24

9 14 21 30

Cho dãy chữ cái:D,G,B,H,E,C,A

cây nhị phân:

G B

H E C A

Câu 22

*)k/n: đồ thị có hướng gồm một tập hợp hữu hạn các phần tử gọi là nút hay đỉnh, cùng vs một tập hữu hạn các cạch có hướng nối các cặp đỉnh vs nhau.

*)Pp lưu trữ đồ thị bằng ma trận kề:

Ta sd ma trận A=[aij] i=1,n; j=1,m

Aij = 1 nếu có cạnh từ i đến j

0 ko có cạnh từ i đến j

*)Pp lưu trữ bằng danh sách kề:

Ta sử dụng vecto Vn[n] để biểu diễn các danh sách lien kết. trong đó ở nút đầu tiên luôn chứa trường dữ liệu, các nút tiếp theo là các cạnh có lien hệ nút đầu tiên.

+)Vd: cho đồ thị có hướng:

A B E

C D

Ma trận kề:

0 1 1 1 0

0 0 0 0 1

0 1 0 0 0

0 0 1 0 1

0 1 0 0 0

Danh sách kề:

V1[1]

V2[2]

V3[3]

V4[4]

V5[5]

(chúng m tự vẽ thẳng nhá, t ko vẽ thẳng hang đc.sr!)

Câu 23

+ k/n: đồ thị vô hướng gồm một tập hợp hữu hạn các phần tử gọi là nút hay đỉnh cùng vs một tập hợp hữu hạn các cạnh nối các cặp định vs nhau.

+pp ma trận kề”

Sử dụng ma trận A=aij ; i=1,n; j=1,m

Aij = 1 khi có cạnh nối giữa i và j

0 kho ko có cạnh nối giữa i và j

+ PP danh sách liên kết:

VD: cho đồ thị vô hướng:

A B

E C D

Ma trận kề:

0 1 0 1 1

1 0 1 0 0

0 1 0 1 1

1 0 1 0 0

Danh sách kề:

V1[1]

V2[2]

V3[3] C 2 4 5

V4[4] D 1 3

V5[5] E 1 3

Câu 24

*) Giải thuật sắp xếp theo pp nổi bọt:

Procedure bubble_Sort;

Var

i,j”integer;

x: item;

begin

for i:=2 to n do

for j:=n down to I do

if a[j-1].key>a[j].key then

begin{đổi chỗ a[j-1] với a[i]}

x:=a[j-1];

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

a[j]:=x

end

end;

Câu 25

*) Giải thuật tìm kiếm tuần tự:

Function SeqSearch (x:integer):integer;

Var

Found: boolean;

i: integer;

begin

found:= false;

i:= 1;

while (i<=n) and (not found) do

if k[i].key=x then found:=true else i:= i+1;

if found then search:=I else search:= 0

end;

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

Function BynarySearch (x:integer): integer;

Var

J,k,m:integer;

Found: Boolean;

Begin

Found:=false;

k:=1;

m:=n;

while(j<=m) and (not found) do

begin

j:=(k+m) div 2;

if a[j].key=x then found:=true

else

if a[j].key<x then k:=j

else

m:=j-1

end;

Bạn đang đọc truyện trên: Truyen2U.Pro

Trước Sau