cơ sở kỷ thuật lập trình

LINK DOWNLOAD MIỄN PHÍ TÀI LIỆU "cơ sở kỷ thuật lập trình ": http://123doc.vn/document/563775-co-so-ky-thuat-lap-trinh.htm

Chng 1: i cng v k thut lp trình cu trúc

4
ging nh nhng hot đng ngh thut nhum màu sc cá nhân hn là khoa hc. Mt s
ngi nm đc mt vài ngôn ng lp trình, cùng mt s mo vt tn dng cu hình vt lý
c th ca h thng máy tính, to nên mt s sn phm l ca phn mm đc coi là mt
chuyên gia nm bt đc nhng bí 
n ca ngh thut lp trình.
Các h thng máy tính trong giai đon này có cu hình yu, b nh nh, tc đ các
thit b vào ra thp làm chm quá trình np và thc hin chng trình. Chng trình đc
xây dng bng k thut lp trình tuyn tính mà ni bt nht là ngôn ng lp trình Assembler
và Fortran. Vi phng pháp lp trình tuyn tính, lp trình viên ch đc phép th hin
chng trình ca mình trên hai c
u trúc lnh, đó là cu trúc lnh tun t (sequential) và
nhy không điu kin (goto). H thng th vin vào ra nghèo nàn làm cho vic lp trình tr
nên khó khn, chi phí cho các sn phm phn mm quá ln, đ tin cy ca các sn phm
phn mm không cao dn ti hàng lot các d án tin hc b tht bi, đc bit là các h thng
tin hc có tm c ln. Nm 1973, Hoare khng
đnh, nguyên nhân tht bi mà ngi M
gp phi khi phóng v tinh nhân to v phía sao V n (Sao Kim) là do li ca chng trình
điu khin vit bng Fortran. Thay vì vit:
DO 50 I = 12, 523
(Thc hin s 50 vi I là 12, 13, , 523)
Lp trình viên (hoc thao tác viên đc bìa) vit thành:
DO 50 I = 12.523
(Du phy đã thay bng du chm)
Gp câu lnh này, chng trình dch ca Fortran đã hiu là gán giá tr thc 12.523
cho bin DO 50 I làm cho kt qu
chng trình sai.
 gii quyt nhng vng mc trong k thut lp trình, các nhà tin hc lý thuyt đã
đi sâu vào nghiên cu tìm hiu bn cht ca ngôn ng, thut toán và hot đng lp trình,
nâng ni dung ca k thut lp trình lên thành các nguyên lý khoa hc ngày nay. Kt qu
ni bt nht trong giai đon này là Knuth xut bn b 3 tp sách mang tên “Ngh thut lp
trình” gii thiu ht sc t
m c s lý thuyt đm bo toán hc và các thut toán c bn x
lý d liu na s, sp xp và tìm kim. Nm 1968, Dijkstra công b lá th “V s nguy hi
ca toán t goto”. Trong công trình này, Dijkstra khng đnh, có mt s li do goto gây nên
không th xác đnh đc đim bt đu ca li. Dijkstra còn khng đnh thêm: “Tay ngh
ca mt lp trình viên t l ngh
ch vi s lng toán t goto mà anh ta s dng trong
chng trình”, đng thi kêu gi hu b trit đ toán t goto trong mi ngôn ng lp trình
ngoi tr ngôn ng lp trình bc thp. Dijkstra còn đa ra khng đnh, đng thái ca chng
trình có th đc đánh giá tng minh qua các cu trúc lp, r nhánh, gi đ qui là c s
ca lp trình cu trúc ngày nay.
Nhng kt qu
đc Dijikstra công b đã to nên mt cuc cách mng trong k
thut lp trình, Knuth lit kê mt s trng hp có li ca goto nh vòng lp kt thúc gia
chng, bt li . . ., Dijkstra, Hoare, Knuth tip tc phát trin t tng coi chng trình máy
tính cùng vi lp trình viên là đi tng nghiên cu ca k thut lp trình và phng pháp
Chng 1: i cng v k thut lp trình cu trúc

5
làm ch s phc tp ca các hot đng lp trình. Nm 1969, Hoare đã phát biu các tiên đ
phc v cho vic chng minh tính đúng đn ca chng trình, phát hin tính bt bin ca
vòng lp bng cách coi chng trình va là bn mã hoá thut toán đng thi là bn chng
minh tính đúng đn ca chng trình. Sau đó Dahl, Hoare, Dijiksta đã phát trin thành ngôn
ng lp trình cu trúc.
 trin khai các nguyên lý lp trình c
u trúc, L. Wirth đã thit k và cài đt ngôn
ng ALGOL W là mt bin th ca ALGOL 60. Sau này, L. Wirth tip tc hoàn thin đ
tr thành ngôn ng lp trình Pascal. ây là ngôn ng lp trình gin d, sáng sa v cú pháp,
d minh ha nhng vn đ phc tp ca lp trình hin đi và đc coi là mt chun mc
trong ging dy lp trình.
Nm 1978, Brian Barninghan cùng Denit Ritche thit k ngôn ng lp trình C vi t
i
thiu các cu trúc lnh và hàm khá phù hp vi t duy và tâm lý ca ca ngi lp trình.
ng thi, hai tác gi đã phát hành phiên bn h điu hành UNIX vit ch yu bng ngôn
ng C, khng đnh thêm uy th ca C trong lp trình h thng.
1.2. CU TRÚC LNH, LNH CÓ CU TRÚC, CU TRÚC D LIU
1.2.1. Cu trúc lnh (cu trúc điu khin)
Mi chng trình máy tính v bn cht là mt bn mã hoá thut toán. Thut toán
đc coi là dãy hu hn các thao tác s cp trên tp đi tng vào (Input) nhm thu đc
kt qu ra (output). Các thao tác trong mt ngôn ng lp trình c th đc điu khin bi
các lnh hay các cu trúc điu khin, còn các đi tng chu thao tác thì đc mô t và biu
di
n thông qua các cu trúc d liu.
Trong các ngôn ng lp trình cu trúc, nhng cu trúc lnh sau đc s dng đ xây
dng chng trình. D nhiên, chúng ta s không bàn ti cu trúc nhy không điu kin goto
mc dù ngôn ng lp trình cu trúc nào cng trang b cu trúc lnh goto.

câu lnh GOTO.






Hình 1.1: Cu trúc tun t và cu trúc r nhánh dng đy đ
Cu trúc tun t
A;


B;

Sau khi thc hin lnh A thì thc hin lnh B
A
B
Cu trúc r nhánh dng đy đ
If (E) A; S
Else B; 




Nu biu thc E có giá tr đúng (khác 0) thì
thchinA;NuEsaithìthchinB;
AB
Chng 1: i cng v k thut lp trình cu trúc

6
















Hình 1.2. Các cu trúc lp
A, B : ký hiu cho các câu lnh đn hoc lnh hp thành. Mi lnh đn l đc gi là
mt lnh đn, lnh hp thành là lnh hay cu trúc lnh đc ghép li vi nhau theo qui đnh
ca ngôn ng, trong Pascal là tp lnh hay cu trúc lnh đc bao trong thân ca begin . . .
end; trong C là tp các lnh hay cu trúc lnh đc bao trong hai ký hiu { }.
E, E1, E2, E3 là các biu thc s hc hoc logic. Mt s ngôn ng lp trình coi giá tr

ca biu thc logic hoc đúng (TRUE) hoc sai (FALSE), mt s ngôn ng lp trình khác
nh C coi giá tr ca biu thc logic là đúng nu nó có giá tr khác 0, ngc li biu thc
logic có giá tr sai.
Cn lu ý rng, mt chng trình đc th hin bng các cu trúc điu khin lnh :
tun t, tuyn chn if else, switch . . case default, lp vi đi
u kin trc while , lp vi
điu kin sau do . . while, vòng lp for bao gi cng chuyn đc v mt chng trình, ch
s dng ti thiu hai cu trúc lnh là tun t và lp vi điu kin trc while. Phng pháp
lp trình này còn đc gi là phng pháp lp trình hn ch.
Cu trúc lp vi điu kin sau
do


A; S 
while (E);
Thc hin A cho ti khi nào E vn còn
đúng;
Cu trúc lp FOR
For (E1; E2;E3)
A;



S 

Cu trúc lp vi điu kin trc
While (E) A;

S



Trong khi biu thc E còn có giá tr đúng thì
thc hin A;
E
A
A
E
E1
E2
E3
A
Chng 1: i cng v k thut lp trình cu trúc

7
1.2.2. Lnh có cu trúc
Lnh có cu trúc là lnh cho phép cha các cu trúc điu khin trong nó. Khi tìm hiu
mt cu trúc điu khin cn xác đnh rõ v trí đc phép đt mt cu trúc điu khin trong
nó, cng nh nó là mt phn ca cu trúc điu khin nào. iu này tng nh rt tm
thng nhng có ý ngha ht sc quan trng trong khi xây d
ng và kim tra li có th xy
ra trong chng trình. Nguyên tc vit chng trình theo cu trúc: Cu trúc con phi đc
vit lt trong cu trúc cha, đim vào và đim ra ca mi cu trúc phi nm trên cùng mt
hàng dc. Ví d sau s minh ha cho nguyên tc vit chng trình:
if (E)
while (E1)
A;
else
do
B;
while(E2);
Trong ví d trên, while (E1) A; là cu trúc con nm trong thân ca cu trúc cha là if
(E) ; còn do B while(E2); là cu trúc con trong thân ca else. Do vy, câu lnh while(E1);
do . . . while(E2) có cùng cp vi nhau nên nó phi nm trên cùng mt ct, tng t nh
vy vi A, B và if vi else.
1.2.3. Cu trúc d liu
Các ngôn ng lp trình cu trúc nói chung đu ging nhau v cu trúc lnh và cu
trúc d liu. im khác nhau duy nht gia các ngôn ng
 lp trình cu trúc là phng pháp
đt tên, cách khai báo, cú pháp câu lnh và tp các phép toán đc phép thc hin trên các
cu trúc d liu c th. Nm bt đc nguyên tc này, chúng ta s d dàng chuyn đi cách
th hin chng trình t ngôn ng lp trình này sang ngôn ng lp trình khác mt cánh
nhanh chóng mà không tn quá nhiu thi gian cho vic hc tp ngôn ng lp trình.
Thông thng, các cu trúc d liu đc phân thành hai loi: cu trúc d li
u có kiu
c bn (Base type) và cu trúc d liu có kiu do ngi dùng đnh ngha (User type) hay
còn gi là kiu d liu có cu trúc. Kiu d liu c bn bao gm: Kiu kí t (char), kiu s
nguyên có du (signed int), kiu s nguyên không du (unsigned int), kiu s nguyên dài có
du (signed long), kiu s nguyên dài không du (unsigned long ), kiu s thc (float) và
kiu s
thc có đ chính xác gp đôi (double).
Kiu d liu do ngi dùng đnh ngha bao gm kiu xâu kí t (string), kiu mng
(array), kiu tp hp (union), kiu cu trúc (struct), kiu file, kiu con tr (pointer) và các
kiu d liu đc đnh ngha mi hoàn toàn nh kiu danh sách móc ni (link list), kiu cây
(tree) . . .
Kích c ca kiu c bn đ
ng ngha vi min xác đnh ca kiu vi biu din nh
phân ca nó, và ph thuc vào tng h thng máy tính c th.  xác đnh kích c ca kiu
nên dùng toán t sizeof( type). Chng trình sau s lit kê kích c ca các kiu c bn.
Chng 1: i cng v k thut lp trình cu trúc

8
Ví d 1.1. Kim tra kích c ca kiu.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <io.h>
void main(void) {
printf(“\n Kích c kiu kí t:%d”, sizeof(char));
printf(“\n Kích c kiu kí t không du:%d”, sizeof(unsigned char));
printf(“\n Kích c kiu s nguyên không du:%d”, sizeof(unsigned int));
printf(“\n Kích c kiu s nguyên có du:%d”, sizeof(signed int));
printf(“\n Kích c kiu s nguyên dài không du:%d”, sizeof(unsigned long ));
printf(“\n Kích c kiu s nguyên dài có du:%d”, sizeof(signed long ));
printf(“\n Kích c kiu s thc có đ chính xác đn:%d”, sizeof(float ));
printf(“\n Kích c kiu s thc có đ chính xác kép:%d”, sizeof(double ));
getch();
}
Kích c ca các kiu d liu do ngi dùng đnh ngha là tng kích c ca mi kiu
thành viên trong nó. Chúng ta cng vn dùng toán t sizeof(tên kiu) đ xác đnh đ ln tính
theo byte ca các kiu d liu này.
Mt đim đc bit chú ý trong khi lp trình trên các cu trúc d liu là cu trúc d liu
nào thì phi kèm theo phép toán đó, vì mt bin đc gi là thuc kiu d liu nào
đó nu
nh nó nhn mt giá tr t min xác đnh ca kiu và các phép toán trên kiu d liu đó.
1.3. NGUYÊN LÝ TI THIU
Hãy bt đu t mt tp nguyên tc và ti thiu các phng tin là các cu trúc lnh, kiu
d liu cùng các phép toán trên nó và thc hin vit chng trình. Sau khi nm chc nhng
công c vòng đu mi đt vn đ m rng sang h thng th vin tin ích ca ngôn ng.
Khi làm quen vi mt ngôn ng lp trình nào đó, không nht thit phi l thuc quá
nhiu vào h
 thng th vin hàm ca ngôn ng, mà điu quan trng hn là trc mt bài
toán c th, chúng ta s dng ngôn ng đ gii quyt nó th nào, và phng án tt nht là
lp trình bng chính h thng th vin hàm ca riêng mình. Do vy, đi vi các ngôn ng
lp trình, chúng ta ch cn nm vng mt s các công c ti thiu nh sau:
1.3.1. Tp các phép toán
Tp các phép toán s
 hc: + (cng); - (tr); * (nhân); % (ly phn d); / (chia).
Tp các phép toán s hc m rng:
++a ú a = a +1; // tng giá tr bin nguyên a lên mt đn v;
a ú a = a-1; //gim giá tr bin nguyên a mt đn v;
a+= n ú a = a+n; // tng giá tr bin nguyên a lên n đn v;
Chng 1: i cng v k thut lp trình cu trúc

9
a-=n ú a = a - n; // gim giá tr bin nguyên a n đn v);
a%=n ú a = a%n; // ly giá tr bin a modul vi n;
a/=n ú a=a/n;// ly giá tr bin a chia cho n;
a*=n ú a = a*n; // ly giá tr bin a nhân vi n;
Tp các phép toán so sánh: >, <, >=, <=, ==, != ( ln hn, nh hn, ln hn
hoc bng, nh hn hoc bng, đúng bng, khác). Qui tc vit đc th hin nh sau:
if ( a>b) { . . } // nu a ln hn b
if ( a<b) { . . } // nu a nh
 hn b
if ( a>=b) { . . } // nu a ln hn hoc bng b
if ( a<=b) { . . } // nu a nh hn hoc bng b
if ( a==b) { . . } // nu a đúng bng b
if ( a!=b) { . . } // nu a khác b
Tp các phép toán logic: &&, ||, ! (và, hoc, ph đnh)
&&: Phép và logic ch cho giá tr đúng khi hai biu thc tham gia đu có giá tr
đúng (giá tr đúng ca mt biu thc trong C đc hiu là biu thc có giá tr khác 0).
||: Phép hoc logic ch cho giá tr sai khi c hai biu thc tham gia đu có giá
tr
 sai.
!: Phép ph đnh cho giá tr đúng nu biu thc có giá tr sai và ngc li cho
giá tr sai khi biu thc có giá tr đúng. Ng ngha ca các phép toán đc minh ha
thông qua các câu lnh sau:
int a =3, b =5;
if ( (a !=0) && (b!=0) ) // nu a khác 0 và b khác 0
if ((a!=0) || (b!=0)) // nu a khác 0 hoc b khác 0
if ( !a ) // ph đnh a khác 0
if (a==b) // nu a đúng bng b
Các toán t thao tác bít (không s dng cho float và double)
& : Phép hi các bít.
| : Phép tuyn các bít.
^ : Phép tuyn các bít có loi tr.
<< : Phép dch trái (dch sang trái n bít giá tr 0)
>> : Phép dch ph
i (dch sang phi n bít có giá tr 0)
~ : Phép ly phn bù.
Chng 1: i cng v k thut lp trình cu trúc

10
Ví d 1.2: Vit chng trình kim tra các toán t thao tác bít.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <io.h>
void main(void){
unsigned int a=3, b=5, c; clrscr();
c = a & b; printf(“\n c = a & b=%d”,c);
c = a | b; printf(“\n c = a | b=%d”,c);
c = a ^ b; printf(“\n c = a ^ b=%d”,c);
c = ~a; printf(“\n c = ~a =%d”,c);
c = a << b; printf(“\n c = a << b=%d”,c);
c = a >>b; printf(“\n c = a >> b=%d”,c);
getch();
}
Toán t chuyn đi kiu: Ta có th dùng toán t chuyn đi kiu đ nhn đc kt qu
tính toán nh mong mun. Qui tc chuyn đi kiu đc thc hin theo qui tc: (kiu) bin.
Ví d 1.3: Tính giá tr phép chia hai s nguyên a và b.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <io.h>
void main(voi)(
int a=3, b=5; float c;
c= (float) a / (float) b;
printf(“\n thng c = a / b =%6.2f”, c);
getch();
}
Th t u tiên các phép toán : Khi vit mt biu thc, chúng ta cn lu ý ti th t
u tiên tính toán các phép toán, các bng tng hp sau đây phn ánh trt t u tiên tính toán
ca các phép toán s hc và phép toán so sánh.
Bng tng hp th t u tiên tính toán các phép toán s hc và so sánh

TÊN TOÁN T CHIU TÍNH TOÁN
( ), [] , -> L -> R
- , ++, , ! , ~ , sizeof() R -> L
* , /, % L -> R
Chng 1: i cng v k thut lp trình cu trúc

11
+ , - L -> R
>>, << L -> R
<, <=, > , >=, L -> R
== != L -> R
& L -> R
^ L -> R
| L -> R
&& L -> R
|| L -> R
?: R -> L
=, +=, -=, *=, /=, %=, &=, ^=, |=, <<=, >>= R -> L
1.3.2. Tp các lnh vào ra c bn
Nhp d liu t bàn phím: scanf(“format_string, . . .”, &parameter . . .);
Nhp d liu t tp: fscanf( file_pointer,”format_string, . . .”, &parameter, . . .);
Nhn mt ký t t bàn phím: getch(); getchar();
Nhn mt ký t t file: fgetc(file_pointer, character_name);
Nhp mt string t bàn phím: gets(string_name);
Nhn mt string t file text : fgets(string_name, number_character, file_pointer);
Xut d liu ra màn hình: printf(“format_string . . .”, parameter . . .);
Xut d liu ra file : fprintf(file_pointer, “format_string . . .”, parameter. . .);
Xut mt ký t ra màn hình: putch(character_name);
Xut mt ký t ra file: fputc(file_pointer, character_name);
Xut mt string ra màn hình: puts(const_string_name);
Xut mt string ra file: fputs(file_pointer, const_string_name);
1.3.3. Thao tác trên các ki
u d liu có cu trúc
Tp thao tác trên string:
char *strchr(const char *s, int c) : tìm ký t c đu tiên xut hin trong xâu s;
char *stpcpy(char *dest, const char *src) : copy xâu scr vào dest;
Chng 1: i cng v k thut lp trình cu trúc

12
int strcmp(const char *s1, const char *s2) : so sánh hai xâu s1 và s2 theo th t t
đin, nu s1 < s2 thì hàm tr li giá tr nh hn 0. Nu s1>s2 hàm tr li giá tr
dng. Nu s1==s2 hàm tr li giá tr 0.
char *strcat(char *dest, const char *src) : thêm xâu scr vào sau xâu dest.
char *strlwr(char *s) : chuyn xâu s t ký t in hoa thành ký t in thng.
char *strupr(char *s): chuyn xâu s t ký t thng hoa thành ký t in hoa.
char *strrev(char *s): đo ngc xâu s.
char *strstr(const char *s1, const char *s2): tìm v trí đu tiên ca xâu s2 trong xâu s1.
int strlen(char *s): cho đ dài ca xâu ký t s.
Tp thao tác trên con tr:
Thao tác l
y đa ch ca bin: & parameter_name;
Thao tác ly ni dung bin (bin có kiu c bn): *pointer_name;
Thao tác tr ti phn t tip theo: ++pointer_name;
Thao tác tr ti phn t th n k t v trí hin ti: pointer_name = pointer_name +n;
Thao tác tr ti phn t sau con tr k t v trí hin ti: pointer_name;
Thao tác tr ti phn t sau n phn t k t v
trí hin ti:
Pointer_name = pointer_name - n;
Thao tác cp phát b nh cho con tr:
void *malloc(size_t size);
void *calloc(size_t nitems, size_t size);
Thao tác cp phát li b nh cho con tr : void *realloc(void *block, size_t size);
Thao tác gii phóng b nh cho con tr: void free(void *block);
Tp thao tác trên cu trúc:
nh ngha cu trúc:
struct struct_name{
type_1 parameter_name_1;
type_2 parameter_name_2;
. . . . . . . . . . . . . . . . . . . . . .
type_k parameter_name_k;
} struct_parameter_name;
Phép truy nhp ti thành phn cu trúc:
Chng 1: i cng v k thut lp trình cu trúc

13
struct_parameter_name.parameter_name.
Phép gán hai cu trúc cùng kiu:
struct_parameter_name1 = struct_parameter_name2;
Phép tham tr ti thành phn ca con tr cu trúc:
pointer_struct_parameter_name -> struct_parameter_name.
Tp thao tác trên file:
Khai báo con tr file: FILE * file_pointer;
Thao tác m file theo mode: FILE *fopen(const char *filename,const char *mode);
Thao tác đóng file: int fclose(FILE *stream);
Thao tác đc tng dòng trong file: char *fgets(char *s, int n, FILE *stream);
Thao tác đc tng khi trong file:
size_t fread(void *ptr, size_t size,size_t n, FILE *stream);
Thao tác ghi tng dòng vào file: int fputs(const char *s, FILE *stream);
Thao tác ghi tng khi vào file:
size_t fwrite(const void *ptr, size_t size, size_t n, FILE *stream);
Thao tác kim tra s tn ti ca file: int access(const char *filename, int amode);
Thao tác đi tên file: int rename(const char *oldname,const char *newname);
Thao tác loi b file: int unlink(const char *filename);
1.4. NGUYÊN LÝ A PHNG
̇ Các bin đa phng trong hàm, th tc hoc chu trình cho dù có trùng tên
vi bin toàn cc thì khi x lý bin đó trong hàm hoc th tc vn không làm
thay đi giá tr ca bin toàn cc.
̇ Tên ca các bin trong đi ca hàm hoc th tc đu là hình thc.
̇ Mi bin hình thc truyn theo tr cho hàm hoc th tc đu là các bin đa
phng.
̇ Các bin khai báo bên trong các ch
ng trình con, hàm hoc th tc đu là
bin đa phng.
̇ Khi phi s dng bin ph nên dùng bin đa phng và hn ch ti đa vic
s dng bin toàn cc đ tránh xy ra các hiu ng ph.
Ví d hoán đi giá tr ca hai s a và b sau đây s minh ha rõ hn v nguyên lý đa
phng.
Ví d 1.4. Hoán đi giá tr ca hai bi
n a và b.