Chapter 2: Các kiểu dữ liệu cơ bản

Chương 2 Các kiểu dữ liệu cơ bản

(cid:67)(cid:104)(cid:432)(cid:417)(cid:110)(cid:103) (cid:50)

CCáác cc cấấu tru trúúc lưu tr c lưu trữữ trên b trên bộộ nhnhớớ chchíínhnh

(cid:67)(cid:225)(cid:99)(cid:32)(cid:107)(cid:105)ể(cid:117)(cid:32)(cid:100)ữ (cid:108)(cid:105)ệ(cid:117)(cid:32)(cid:99)(cid:417)(cid:32)(cid:98)ả(cid:110) (cid:67)(cid:225)(cid:99)(cid:32)(cid:107)(cid:105)ể(cid:117)(cid:32)(cid:100)ữ (cid:108)(cid:105)ệ(cid:117)(cid:32)(cid:99)(cid:417)(cid:32)(cid:98)ả(cid:110)

KiKiểểu chu

i (String) u chuỗỗi (String)

(cid:61607) Một chuỗi là dãy liên tiếp các ký tự kết thúc bằng ký tự \0 có mã ASCII bằng 0 (NULL character)

i dung NNộội dung Nội dung

1 Kiểu mảng và chuỗi

(cid:61607) Trong C chuỗi có tối đa 65535 ký tự (cid:61607) Các hàm xử lý chuỗi được đặt trong thư viện

2 Kiểu cấu trúc

string.h của C.

3 Kiểu con trỏ

4 Kiểu tập tin

3/11/2010

www.lhu.edu.vn

5 Độ phức tạp thuật toán

Chương 2 Các kiểu dữ liệu cơ bản

CCáác cc cấấu tru trúúc lưu tr CCáác kic kiểểu du dữữ liliệệu cu cóó ccấấu tru trúúcc c lưu trữữ trên b trên bộộ nhnhớớ chchíínhnh CCáác cc cấấu tru trúúc lưu tr CCáác kic kiểểu du dữữ liliệệu cu cóó ccấấu tru trúúcc c lưu trữữ trên b trên bộộ nhnhớớ chchíínhnh

thao táác trên chu c trên chuỗỗii

i (String) MMộột st sốố thao t

KiKiểểu chu

i (String) u chuỗỗi (String)

KiKiểểu chu

u chuỗỗi (String)

Khai báo chuỗi: có thể dùng các cách sau

(cid:61607) char S[10]; //Khai báo một chuỗi ký tự S có chiều dài // tối đa 10 (kể cả kí tự kết thúc) (cid:61607) char S[]="ABC";// Khai báo một chuỗi ký tự S có chiều

(cid:61607) So sánh 2 chuỗi: strcmp (cid:61607) Sao chép chuỗi: strcpy (cid:61607) Độ dài chuỗi: strlen (cid:61607) Kiểm tra 1 chuỗi nằm trong chuỗi kia: strstr (cid:61607) Cắt 1 từ ra khỏi 1 chuỗi: strtok (cid:61607) Đổi 1 số ra chuỗi: itoa (cid:61607) Đổi 1 chuỗi ra số: atoi, atof, ... (cid:61607) Nhập một chuỗi: gets (cid:61607) Xuất một chuỗi: puts

3/11/2010

www.lhu.edu.vn

// dài bằng chiều dài của chuỗi "ABC" // và giá trị khởi đầu của S là "ABC" (cid:61607) char *S ="ABC";//Giống cách khai báo trên.

1

Chương 2 Các kiểu dữ liệu cơ bản

Khai bááo mo mảảngng

ng (Array): Khai b

ng (Array) KiKiểểu mu mảảng (Array)

KiKiểểu mu mảảng (Array):

(cid:61607) Mảng là một tập hợp các biến có cùng tên và

kiểu dữ liệu, được lưu trữ liên tiếp trong bộ nhớ (cid:61607) Mỗi phần tử được đánh chỉ số (Index), phần tử

đầu tiên có chỉ số là 0

[][]...; Ví dụ, ta có thể khai báo: //khai báo mảng 1 chiều có 10 phần tử

(cid:61607) Trong C, một mảng n chiều có thể coi là mảng 1 chiều trong đó mỗi phần tử là 1 mảng n-1 chiều.

3/11/2010

www.lhu.edu.vn

(cid:61607) Float a[10]; (cid:61607) int a[100][150];//khai báo mảng 2 chiều (cid:61607) int a[][]={{1, 7, -3, 8, 19},{4, 5, 2, 8, 9},{21, -7, 45, -3, 4}};

Chương 2 Các kiểu dữ liệu cơ bản

u union Khai bááo kio kiểểu union

p (Union): Khai b

p (Union) KiKiểểu hu hợợp (Union)

KiKiểểu hu hợợp (Union):

(cid:61607) Union là một kiểu dữ liệu đặc biệt trong C, nó

Ví dụ, ta có thể định nghĩa kiểu số sau:

tương tự kiểu struct nhưng các phần tử lại dùng chung một vùng nhớ

typedef union tagNumber {

(cid:61607) Cách thức truy xuất đến các thành phần trong

typedef union { ; ; ……… }[];

kiểu Union giống như kiểu cấu trúc

int i; long l;

(cid:61607) Dùng kiểu Union khi cần lưu trữ dữ liệu thay đổi

}Number; Number N;

theo trạng thái

Khi gán N.l=0xFF09 thì thành phần N.i sẽ nhận giá trị là 9

3/11/2010

www.lhu.edu.vn

2

Chương 2 Các kiểu dữ liệu cơ bản

Khai bááo kio kiểểu cu cấấu tru trúúcc

c (Structure): Khai b

c (Structure) KiKiểểu cu cấấu tru trúúc (Structure)

KiKiểểu cu cấấu tru trúúc (Structure):

Ví dụ, ta có thể định nghĩa kiểu cấu trúc ngày tháng như sau:

(cid:61607) Kiểu cấu trúc (hay kiểu mẫu tin) là một tập hợp các biến khác tên và có thể khác nhau về kiểu dữ liệu

typedef struct {

typedef struct { ; ; ……… }[];

int ngay; int thang; int nam;

(cid:61607) Cách thức truy xuất đến các thành phần trong kiểu cấu trúc: Têncấutrúc.Tênthànhphần (cid:61607) Dùng kiểu cấu trúc khi muốn lưu trữ thông tin

}Ngaythang; Ngaythang N;//khai báo biến

của các đối tượng phức tạp và đa dạng

3/11/2010

www.lhu.edu.vn

Chương 2 Các kiểu dữ liệu cơ bản

Truy xuấất dt dữữ liliệệuu

c (Structure): HHààm vm vàà kikiểểu cu cấấu tru trúúcc

KiKiểểu cu cấấu tru trúúc (Structure): (cid:61607) Đối của hàm có thể là:

c (Structure): Truy xu KiKiểểu cu cấấu tru trúúc (Structure): (cid:61607) Cách thức truy xuất đến các thành phần trong kiểu

cấu trúc: Têncấutrúc.Tênthànhphần

- Biến mẫu tin: khi đó tham số thực tương ứng là một giá trị mẫu tin - Tham chiếu mẫu tin: khi đó tham số thực tương ứng là một địa chỉ

(cid:61607) Để lấy địa chỉ của một thành phần trong cấu trúc, ta

mẫu tin

- Con trỏ mẫu tin: khi đó tham số thực là địa chỉ của biến cấu trúc.

dùng toán tử &: &Têncấutrúc.Tênthànhphần

Vd:

(cid:61607) Hàm có thể trả về: - Giá trị mẫu tin: Ngaythang tênhàm(...) - Con trỏ mẫu tin: Ngaythang *tênhàm(....)

3/11/2010

www.lhu.edu.vn

Ngaythang N,M; printf(“Nhập ngày tháng: ”); scanf(“%d/%d/%d”,&N.ngay,&N.thang,&N.nam); M=N;//gán biến cấu trúc N vào biến M

3

Chương 2 Các kiểu dữ liệu cơ bản

Khai bááo bio biếến con tr

n con trỏỏ

(Pointer) Khai b

KiKiểểu con tr

(Pointer) u con trỏỏ (Pointer)

KiKiểểu con tr

u con trỏỏ (Pointer)

(cid:61607)(cid:61607) TrTrựực tic tiếếpp:

ncontrỏỏ>;>;

> *

(cid:61607) Kiểu con trỏ là một kiểu dữ liệu đặc biệt trong C, có kích thước 2 bytes và dùng để chứa địa chỉ của một biến đã được cấp phát bộ nhớ

(cid:61607)(cid:61607) GiGiáán tin tiếếpp: typedef

ucơsởởT> *

ucontrỏỏ>;>;

(cid:61607) Khi biến con trỏ chứa địa chỉ của biến A ta nói

ucơsởở> *

nó đang trỏ tới biến (vùng nhớ) A

(cid:61607) Nếu con trỏ chứa giá trị NULL nghĩa là nó không

T> *;>; ucontrỏỏ>

trỏ đến vùng nhớ nào hết

3/11/2010

www.lhu.edu.vn

Chương 2 Các kiểu dữ liệu cơ bản

Khai bááo bio biếến con tr

n con trỏỏ

c thao táácc (Pointer) CCáác thao t KiKiểểu con tr u con trỏỏ (Pointer)

(Pointer) Khai b

KiKiểểu con tr

u con trỏỏ (Pointer)

tênbiếncontrỏ = &tênbiếncầnlấyđịachỉ; tênbiếncontrỏ = NULL;

(cid:61607) Con trỏ void: con trỏ được khai báo kiểu void có thể chứa địa chỉ của bất kỳ kiểu nào. Tuy nhiên trước khi sử dụng phải ép về một kiểu cụ thể Vd:

(cid:61607) Gán địa chỉ một biến cho con trỏ

float *P, B[3][4]; --> P = (float*) B;

//P trỏ đến X

(cid:61607) Chứa địa chỉ của 1 biến cấu trúc:

struct HocSinh *P, hs; --> P = &hs;

int X; float Y; void *P; P=&X; (float*) P=&Y; (float*) P=&Y; (int*) P=&X; (int*) P=&X;

//P trỏỏ đ đếến Yn Y //P tr //P trỏỏ đ đếến Xn X //P tr

3/11/2010

www.lhu.edu.vn

Ví dụ: (cid:61607) Chứa địa chỉ của mảng 1 chiều: int *P , A[10]; --> P = A; (cid:61607) Chứa địa chỉ của mảng 2 chiều:

4

Chương 2 Các kiểu dữ liệu cơ bản

c thao táácc

(Pointer) CCáác thao t

KiKiểểu con tr

u con trỏỏ (Pointer)

(Pointer) CCáác phc phéép top toáánn

KiKiểểu con tr

u con trỏỏ (Pointer)

(cid:61607) Truy xuất nội dung 1 biến do biến con trỏ trỏ đến

(cid:61607) So sánh địa chỉ chứa trong hai con trỏ, dùng

toán tử == hoặc !=

(cid:61607) Khi sử dụng con trỏ trên mảng, ta có thể thực

Cú pháp:*tênbiếncontrỏ Lưu ý: toán tử * và & có cùng độ ưu tiên Ví dụ:

int X, *P; X=10; P=&X; //P trỏ đến X printf(“Giá trị X là: %d”,X); printf(“Giá trị do P trỏ đến: %d”,*P);

hiện các phép toán sau (cid:61607) Cộng địa chỉ con trỏ: pt + i ==>Cộng địa chỉ vùng nhớ lưu trong pt với i*sizeof(T) (cid:61607) Trừ hai con trỏ: pt1-pt2 ==>số phần tử có kích thước sizeof(T) giữa 2 địa chỉ.

3/11/2010

www.lhu.edu.vn

Chương 2 Các kiểu dữ liệu cơ bản

Con trỏỏ vvàà mmảảng 1 chi ng 1 chiềềuu (Pointer) Con tr KiKiểểu con tr u con trỏỏ (Pointer) Con trỏỏ vvàà mmảảng 2 chi ng 2 chiềềuu (Pointer) Con tr KiKiểểu con tr u con trỏỏ (Pointer)

(cid:61607) Tên mảng là hằng địa chỉ của phần tử đầu tiên trong (cid:61607) Tên mảng là hằng địa chỉ của phần tử đầu tiên trong

Vd:

mảng, có thể thực hiện phép cộng địa chỉ với tên mảng. Khi đó (A+i) tương ứng với &A[i] mảng, có thể thực hiện phép cộng địa chỉ với tên mảng. Khi đó (A+i) tương ứng với &A[i][0] Vd: float A[3][2]; ta có A ứng với &A[0][0]; (cid:61607) Ta cũng có thể sử dụng con trỏ trên mảng với các phép (A+1) ứng với &A[1][0]; (A+2) ứng với &A[2][0] (cid:61607) Ta cũng có thể sử dụng con trỏ trên mảng với các phép toán sau (cid:61607) Lấy địa chỉ phần tử thứ i : &A[i] (cid:61607) Cộng địa chỉ

int i, *p, A[3]={10,20,30}; p=A;// hoặc p=&A[0]; for (i=0;i<3;i++) printf(“A[%d]=%d”,i,*(A+i)); for (i=0;i<3;i++) printf(“A[%d]=%d”,i,*(p+i));

3/11/2010

www.lhu.edu.vn

toán sau (cid:61607) Lấy địa chỉ phần tử A[i][j] : p+i*sốcột+j (cid:61607) Cộng địa chỉ

5

Chương 2 Các kiểu dữ liệu cơ bản

Con trỏỏ vvàà kikiểểu cu cấấu tru trúúcc

Con trỏỏ vvàà mmảảng 2 chi ng 2 chiềềuu (Pointer) Con tr KiKiểểu con tr u con trỏỏ (Pointer)

(Pointer) Con tr

KiKiểểu con tr

u con trỏỏ (Pointer)

(cid:61607) Lấy địa chỉ của một phần tử trong cấu trúc ta

dùng toán tử & Vd :struct Ngay{ int ngay,thang,nam;}X;

Vd:

struct Ngay *p; p=&X; //p trỏ đến cấu trúc X

(cid:61607) Để truy xuất giá trị của pt trong cấu trúc ta có thể

int i,j,k; float *p, A[3][3]; p=(float*)A;// hoặc p=(float*)&A[0][0]; for (i=0;i<3;i++) //In theo mảng 2 chiều for (j=0;j<3;j++)

3/11/2010

www.lhu.edu.vn

printf(“A[%d][%d]=%d”,i,j,*(p+i*3+j)); for (k=0;k<3*3;k++) //In theo mảng 1 chiều printf(“A[%d]=%d”,k,*(p+k)); (cid:61607) Cách 1: *(p).ngay, *(p).thang, *(p).nam (cid:61607) Cách 2: p(cid:61664)ngay, p(cid:61664)thang, p(cid:61664)nam

Chương 2 Các kiểu dữ liệu cơ bản

CCáác cc cấấu tru trúúc lưu tr CCáác kic kiểểu du dữữ liliệệu cu cóó ccấấu tru trúúcc c lưu trữữ trên b trên bộộ nhnhớớ chchíínhnh c lưu trữữ trên b CCáác kic kiểểu du dữữ liliệệu cu cóó ccấấu tru trúúcc CCấấu tru trúúc lưu tr trên bộộ nhnhớớ ngongoààii

Con trỏỏ hhààmm (Pointer) Con tr KiKiểểu con tr u con trỏỏ (Pointer)

p tin (File) KiKiểểu tu tậập tin (File)

(cid:61607) Ưu điểm của RAM: truy xuất nhanh (cid:61607) Nhược điểm của RAM: kích thước hạn chế,

không lưu trữ thông tin khi mất điện

(cid:61607) Là con trỏ dùng để chứa địa chỉ của hàm (cid:61607) Khai báo hàm và con trỏ hàm phải trung khớp với nhau về các đối số và kiểu dữ liệu trả về (cid:61607) Trước khi dùng phải gán tên hàm cho con trỏ hàm

(cid:61672) Giải pháp: lưu trữ trên bộ nhớ ngoài (ổ đĩa)

Vd : int Hoanvi( int *x, int *y); //khai báo hàm

(cid:61607) Ưu: kích thước lớn, lưu trữ lâu dài (cid:61607) Nhược: truy xuất chậm do sử dụng thiết bị cơ khí

3/11/2010

www.lhu.edu.vn

int (*p)( int*, int*)=Hoanvi; //khai báo con trỏ hàm int x=2, y=3; Hoanvi(&x, &y); //dùng tên hàm p(&x, &y); //dùng con trỏ hàm

6

Chương 2 Các kiểu dữ liệu cơ bản

CCấấu tru trúúc lưu tr c lưu trữữ trên b trên bộộ nhnhớớ ngongoààii c lưu trữữ trên b CCáác kic kiểểu du dữữ liliệệu cu cóó ccấấu tru trúúcc CCấấu tru trúúc lưu tr trên bộộ nhnhớớ ngongoààii

(cid:61607)

File được kết thúc bởi ký tự có mã 26 (EOF)

KiKiểểu tu tậập tin (File) p tin (File) CCáác bưc bướớc thao t c thao táác trên t c trên tậập tinp tin p tin (File) KiKiểểu tu tậập tin (File) 1. Khai báo biến tập tin: FILE *ContrỏFile; (cid:61607) Có 2 loại tập tin

(cid:61607) (cid:61607)

2. Mở tập tin: ContrỏFile = fopen (char *têntậptin, char *kiểu);

Ý nghiã

Kiểu

Tập tin văn bản (Text file) Tập tin nhị phân (Binary file) (cid:61607) Các bước làm việc với tập tin

Mở tập tin kiểu nhị phân

“b”

Mở tập tin kiểu văn bản

“t”

Mở để đọc. Nếu không có File sẽ báo lỗi

“r”

Mở để sửa

“r+”

Mở file mới để ghi. Nếu file đã có sẽ bị xóa

“w”

1. Khai báo biến tập tin 2. Mở tập tin 3. Truy xuất nội dung tập tin 4. Đóng tập tin

Mở file mới đọc hoặc ghi.

“w+”

Mở file để ghi thêm vào cuối file

“a”

“a+”

Mở file để đọc ghi. Nếu file cũ thì nối thêm,nếu không thì tạo mới

3/11/2010

www.lhu.edu.vn

(cid:61607) Trong C, các hàm xử lý tập tin có trong thư viện stdio.h

Chương 2 Các kiểu dữ liệu cơ bản

KiKiểểu tu tậập tin (File) p tin (File) CCáác bưc bướớc thao t c thao táác trên t c trên tậập tinp tin KiKiểểu tu tậập tin (File) p tin (File) CCáác bưc bướớc thao t c thao táác trên t c trên tậập tinp tin

(cid:61607)

File văn bản: đặc điểm ký tự xuống hàng gồm CR(13) và LF(10), khi đọc CR + LF (cid:61664) trả về ký tự “\n”, khi ghi ký tự “\n” (cid:61664) CR + LF

3. Truy xuất dữ liệu file văn bản

(cid:61607) Đọc ghi dữ liệu tuần tự (cid:61607) Ghi dữ liệu

DSHS.DBF””,, ““wbwb””););

•

FILE *fp; VVíí ddụụ:: FILE *fp; fp = fopen(““C:C:\\\\DSHS.DBF fp = fopen( if ( fp == 0 ) if ( fp == 0 ) {{

int putc ( int ch, FILE *fp);

•

Loi Mo File:””););

int fputc (int ch, FILE *fp);

•

perror(““Loi Mo File: perror( exit(1); exit(1);

int fputs (const char Str, FILE fp);

•

}}

int fprintf (FILE fp, const char dk, các biểu thức);

3/11/2010

www.lhu.edu.vn

7

Chương 2 Các kiểu dữ liệu cơ bản

CCấấu tru trúúc lưu tr c lưu trữữ trên b trên bộộ nhnhớớ ngongoààii CCấấu tru trúúc lưu tr c lưu trữữ trên b trên bộộ nhnhớớ ngongoààii

(cid:61607)

(cid:61607) Đọc dữ liệu

File nhị phân: không có ký tự xuống dòng, mỗi lần đọc ghi theo một khối byte (Record)

•

3. Truy xuất dữ liệu file văn bản 3. Truy xuất dữ liệu file nhị phân

int getc (FILE *fp) ;

•

int fgetc (FILE *fp) ;

(cid:61607) Đọc ghi dữ liệu tại vị trí Record bất kỳ (cid:61607) Ghi các Record vào File:

•

char fgets (char Str, int n, FILE *fp);

int fwrite(void *ptr, int sizeofItem, int n, FILE *fp);

•

int fscanf (FILE fp, const char dk, địa chỉ các biến);

(cid:61607) Đọc các Record trên File:

int fread (void *ptr, int sizeofItem, int n, FILE *fp);

3/11/2010

www.lhu.edu.vn

Chương 2 Các kiểu dữ liệu cơ bản

CCấấu tru trúúc lưu tr c lưu trữữ trên b trên bộộ nhnhớớ ngongoààii CCấấu tru trúúc lưu tr c lưu trữữ trên b trên bộộ nhnhớớ ngongoààii

(cid:61607) Kiểm tra cuối file:

int feof (FILE *fp);

int fsetpos(FILE * fp, fpos_t *vịtrí);

(cid:61607)

3. Truy xuất dữ liệu file nhị phân 3. Truy xuất dữ liệu file nhị phân (cid:61607) Quay lại vị trí đã đánh dấu:

Vị trí con trỏ byte:

(cid:61607) Đổi tên / di chuyển file :

int rename (const char *OldFile, const char *NewFile);

long ftell (FILE *fp); (cid:61607) Di chuyển đầu đọc File:

(cid:61607)

Xóa tập tin:

int remove (const char * path);

void rewind (FILE *fp); int fseek (FILE *fp, long sốbyte, int vịtríxuấtphát);

(cid:61607) Đánh dấu vị trí đầu đọc ghi:

int fgetpos (FILE *fp, fpos_t *vịtrí);

3/11/2010

www.lhu.edu.vn

8

Chương 2 Các kiểu dữ liệu cơ bản

CCấấu tru trúúc lưu tr c lưu trữữ trên b trên bộộ nhnhớớ ngongoààii CCấấu tru trúúc lưu tr c lưu trữữ trên b trên bộộ nhnhớớ ngongoààii

KiKiểểu tu tậập tin (File) p tin (File) CCáác bưc bướớc thao t c thao táác trên t c trên tậập tinp tin KiKiểểu tu tậập tin (File) p tin (File) CCáác vc víí ddụụ

(cid:61607)

int fclose (FILE *fp);

int main(int n, char * a[]) //n là số đối số trên dòng lệnh kể cả 4. Đóng tập tin

Nếu có lỗi hàm cho EOF ngược lại cho giá trị 0.

(cid:61607)

int fcloseall ( );

Nếu có lỗi cho EOF nếu không cho số file được đóng.

//tên chương trình a[0] int sobyte=0; { puts("Loi cu phap: "); exit(1); }

FILE *fp; char c; if (n != 2) { fp = fopen(a[1], "wt"); while (( c = getchar()) != EOF) //hàm getchar() trả về EOF { putc( c, fp); sobyte++; } //khi có lỗi hoặc ấn F6

3/11/2010

www.lhu.edu.vn

printf("\n\t 1 file copy \t\t %d bytes ", sobyte); fclose(fp); }

Chương 2 Các kiểu dữ liệu cơ bản

CCấấu tru trúúc lưu tr c lưu trữữ trên b trên bộộ nhnhớớ ngongoààii CCấấu tru trúúc lưu tr c lưu trữữ trên b trên bộộ nhnhớớ ngongoààii

p tin (File) KiKiểểu tu tậập tin (File)

CCáác vc víí ddụụ

p tin (File) KiKiểểu tu tậập tin (File)

CCáác vc víí ddụụ

int main(int n, char * a[]) {

char st[80];

typedef struct pointtype Polygol[10]; Polygol P; void main(void) {

FILE *fp; int sobyte=0; if (n != 2) { puts("Loi cu phap: "); exit(1); } fp = fopen(a[1], "wt"); while ( gets(st)) != NULL) //hàm gets(st) trả về NULL khi có lỗi {

fputs("\n", fp); //hoặc ấn F6

int n,i;

fputs( st, fp); sobyte+=strlen(st);

} printf("\n\t 1 file copy \t\t %d bytes ", sobyte); fclose(fp);

}

FILE *fp; char c; fp = fopen("c:\\dagiac.dat","rt"); fscanf(fp,"%d",&n); printf("%d\n",n); for (i=0; i

3/11/2010

www.lhu.edu.vn

}

9

Chương 2 Các kiểu dữ liệu cơ bản

ĐĐáánh gi nh giáá đ độộ phphứức tc tạạp thu p thuậật tot toáánn ĐĐáánh gi nh giáá đ độộ phphứức tc tạạp thu p thuậật tot toáánn

ThThờời gian th i gian thựực hic hiệện cn củủa thu a thuậật tot toáánn TTỷỷ llệệ tăng c m (Growth Rate) tăng củủa ha hààm (Growth Rate)

3/11/2010

www.lhu.edu.vn

(cid:61607)(cid:61607) nh thựực hi c hiệện khi ch n khi chạạyy (cid:61607)(cid:61607) Cho hai h Cho hai hààm không âm T m không âm T11(n) v (n) vàà TT22(n)(n) LLàà ssốố llệệnh cnh cầần thi chương trìình snh sửử ddụụng thu chương tr n thiếết mt màà mmááy ty tíính th ng thuậật tot toáánn (cid:61607)(cid:61607) (n) cóó ttỷỷ llệệ gia tăng gi gia tăng giốống như T (n) nếếu tu tồồn tn tạại ci cáác hc hằằngng TT11(n) c ng như T22(n) n (cid:61607)(cid:61607) c hiệện mn mộột chương tr t chương trìình l (n) vớới mi mọọi ni n ≥≥ 11 ch thướớc dc dữữ liliệệu vu vàào, ký hi nh làà mmộột ht hààmm u T(n), o, ký hiệệu T(n), ssốố c vc vàà nn00 : T: T11(n)(n) ≤≤ c.Tc.T22(n) v ThThờời gian th i gian thựực hi không âm củủa ka kíích thư không âm c T(n)T(n) (cid:61619)(cid:61619)00 (cid:61474)(cid:61474)nn(cid:61619)(cid:61619)00 VVíí ddụụ: T: Tììm tm tỷỷ llệệ gia tăng c (n) =(n+1)22 gia tăng củủa ha hààm Tm T11(n) =(n+1) (cid:61607)(cid:61607) ng chỉỉ quan tâm đ quan tâm đếến thn thờời gian th i gian thựực hi c hiệệnn (n) =n22+2n+1 +2n+1 ≤≤ nn22+2n+2n22+n+n22=4n=4n22 vvớới mi mọọi ni n ≥≥ 11 Ta thấấyy TT11(n) =n Ta th Thông thườờng ch Thông thư trong trườờng hng hợợp xp xấấu nhu nhấấtt trong trư (n) =(n+1)22 ccóó ttỷỷ llệệ tăng như tăng như n c=4, n00=1=1 , ta nói TT11(n) =(n+1) (cid:61672)(cid:61672) chchọọn c=4, n (n) =n22 TT22(n) =n

Chương 2 Các kiểu dữ liệu cơ bản

ĐĐáánh gi nh giáá đ độộ phphứức tc tạạp thu p thuậật tot toáánn ĐĐáánh gi nh giáá đ độộ phphứức tc tạạp thu p thuậật tot toáánn

T(n)

ĐĐộộ phphứức tc tạạp cp củủa thu n (Complexity) a thuậật tot toáán (Complexity) ĐĐộộ phphứức tc tạạp cp củủa thu n (Complexity) a thuậật tot toáán (Complexity)

(cid:61607)(cid:61607) Cho hai h Cho hai hààm Tm T11(n) v (n) vàà TT22(n)(n) (cid:61607)(cid:61607) (n) nếếu tu tồồn tn tạại ci cáác hc hằằng sng sốố c vc vàà (n) cóó đ độộ phphứức tc tạạp lp làà TT22(n) n TT11(n) c nn00 : T: T11(n)(n) ≤≤ c.Tc.T22(n) v (n) vớới mi mọọi ni n ≥≥ nn00

(cid:61607)(cid:61607) Ký hiệệu: Tu: T11(n) = Ký hi (n) = O(O(TT22(n)(n))) đ đọọc lc làà ““ô cô củủa Ta T22(n)(n)””

O(1)

3/11/2010

www.lhu.edu.vn

(cid:61607)(cid:61607) m đã biếết như n, n, t như: log: log22n, n, (n) làà ddạạng hng hààm đã bi , n!, nnn ... Thông thườờng Tng T22(n) l Thông thư nlognlog22n, nn, n22, n, n33, 2, 2nn, n!, n

10

Chương 2 Các kiểu dữ liệu cơ bản

ĐĐáánh gi nh giáá đ độộ phphứức tc tạạp thu p thuậật tot toáánn ĐĐáánh gi nh giáá đ độộ phphứức tc tạạp thu p thuậật tot toáánn

void BubleSort(int a[], int N ) void BubleSort(int a[], int N ) i, j, tepm; {{ i, j, tepm;

CCáách tch tíính đnh độộ phphứức tc tạạp cp củủa thu n (Complexity) a thuậật tot toáán (Complexity) CCáách tch tíính đnh độộ phphứức tc tạạp cp củủa thu n (Complexity) a thuậật tot toáán (Complexity)

Cho hai đoạạn chương tr

n chương trìình P1v

(cid:61607)(cid:61607) Qui tQui tắắc nhân c nhân:: (cid:61607)(cid:61607) Cho hai đo