Bài giảng Tin học đại cương: Bài 9 - ĐH Bách khoa Hà Nội

Chia sẻ: Khang Duy | Ngày: | Loại File: PDF | Số trang:16

Thêm vào BST

Báo xấu

130
lượt xem 11
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài 9 Mảng và xâu ký tự thuộc bài giảng "Tin học đại cương", cùng nắm kiến thức trong chương này thông qua các các nội dung sau: mảng, xâu kí tự, con trỏ và địa chỉ (optional). Mời các bạn cùng tham khảo để nắm kiến thức đã được trình bày trong bài này.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Tin học đại cương: Bài 9 - ĐH Bách khoa Hà Nội

TRƯỜNG ĐẠI HỌC B\CH KHOA H[ NỘI Nội dung VIỆN CÔNG NGHỆ THÔNG TIN V[ TRUYỀN THÔNG 9.1. Mảng 9.2. X}u kí tự TIN HỌC ĐẠI CƯƠNG 9.3. Con trỏ v{ địa chỉ (optional) Phần 3. Lập trình C Bài 9. Mảng và xâu ký tự 2 Nội dung 9.1.1. Kh|i niệm mảng 9.1. Mảng • Tập hợp hữu hạn c|c phần tử cùng kiểu, lưu 9.1.1. Kh|i niệm mảng trữ kế tiếp nhau trong bộ nhớ 9.1.2. Khai b|o v{ sử dụng mảng • C|c phần tử trong mảng có cùng tên (l{ tên 9.1.3. C|c thao t|c cơ bản trên mảng mảng) nhưng ph}n biệt với nhau ở chỉ số 9.1.4. Tìm kiếm trên mảng cho biết vị trí của nó trong mảng 9.1.5. Sắp xếp trên mảng • Ví dụ: 9.2. X}u kí tự – Bảng điểm của sinh viên – Vector – Ma trận 3 4 1
9.1.2. Khai b|o v{ sử dụng mảng 9.1.2. Khai b|o v{ sử dụng mảng • Khai b|o mảng (một chiều) • Cấp ph|t bộ nhớ kiểu_dữ_liệu tên_mảng[kích_thước_mảng]; – C|c phần tử trong mảng được cấp ph|t c|c ô • Trong đó nhớ kế tiếp nhau trong bộ nhớ – kiểu_dữ_liệu: kiểu dữ liệu của c|c phần tử trong – Biến mảng lưu trữ địa chỉ ô nhớ đầu tiên trong mảng vùng nhớ được cấp ph|t – tên_mảng: tên của mảng • Ngôn ngữ C đ|nh chỉ số c|c phần tử trong – kích_thước_mảng: số phần tử trong mảng mảng bắt đầu từ 0 • Ví dụ – Phần tử thứ i trong mang_nguyen được x|c định bởi mang_nguyen[i-1] int mang_nguyen[10]; // khai b|o mảng 10 phần tử có kiểu dữ liệu int mang_nguyen[0] mang_nguyen[1] ……….. mang_nguyen[9] 5 6 mang_nguyen 9.1.2. Khai b|o v{ sử dụng mảng 9.1.2. Khai b|o v{ sử dụng mảng • Ví dụ khai báo mảng: • Mảng một chiều v{ mảng nhiều chiều char c[12]; – Mỗi phần tử của mảng cũng l{ một mảng => mảng nhiều chiều Khai báo một mảng: c[0] -45 c[1] 6 • Ví dụ Tên là c, có 12 phần tử, c[2] 0 c[0], c[1],...,c[11] c[3] 72 – int a[6][5] ; c[4] 15 c[5] -89 mảng a gồm 6 phần tử Các phần tử thuộc kiểu char c[6] c[7] 0 62 mỗi phần tử l{ mảng gồm 5 số nguyên int c[8] c[9] -3 1 – int b[3][4][5]; // mảng b gồm 3 phần tử, mỗi c[10] 64 phần tử l{ mảng hai chiều gồm 4 phần tử. Mỗi c[11] 78 phần tử mảng hai chiều l{ mảng gồm 5 số nguyên int. b l{ mảng 3 chiều 8 2
9.1.2. Khai b|o v{ sử dụng mảng 9.1.2. Khai b|o v{ sử dụng mảng • Khai b|o mảng nhiều chiều • Sử dụng mảng kiểu_dữ_liệu tên_mảng[size1][size2]…[sizek]; – Truy cập v{o phần tử thông qua tên mảng v{ chỉ Trong đó số của phần tử trong mảng • sizei l{ kích thước chiều thứ i của mảng tên_mảng[chỉ_số_phần_tử] – Chú ý: chỉ số bắt đầu từ 0 • Ví dụ – int a[4]; – phần tử đầu tiên (thứ nhất) của mảng: a[0] – phần tử cuối cùng (thứ tư) của mảng: a[3] – a[i]: l{ phần tử thứ i+1 của a 9 10 9.1.2. Khai b|o v{ sử dụng mảng 9.1.3. C|c thao t|c cơ bản trên mảng a. Nhập dữ liệu cho mảng • Ví dụ (tiếp) • Khởi tạo gi| trị cho mảng ngay khi khai b|o – int b[3][4]; – Ví dụ: – phần tử đầu tiên của mảng: b[0] l{ một mảng • int a[4] = {1,4,6,2}; một chiều • float b[ ] = {40.5, 20.1, 100}; – phần tử đầu tiên của mảng b[0]: b[0][0] • char c[5] = {‘h’, ‘e’, ‘l’, ‘l’, ‘o’}; – b[i][j]: l{ phần tử thứ j+1 của b[i], b[i] l{ phần • int b[2][3]={ {1,2,3}, {4,5,6} }; tử thứ i+1 của b – Số lượng gi| trị khởi tạo không được lớn hơn số lượng phần tử trong mảng – Nếu số lượng n{y nhỏ hơn, c|c phần tử còn lại được khởi tạo gi| trị 0 – Nếu để trống kích thước mảng bằng số phần tử khởi tạo. 11 12 3
9.1.3. C|c thao t|c cơ bản trên mảng 9.1.3. C|c thao t|c cơ bản trên mảng a. Nhập dữ liệu cho mảng #include #define MONTHS 12 • Nhập dữ liệu từ b{n phím bằng h{m scanf int main(){ – int a[10]; int rainfall[MONTHS], i; – Nhập dữ liệu cho a[1]: scanf(“%d”, & a[1]); for ( i=0; i < MONTHS; i++ ){ – Nhập dữ liệu cho to{n bộ phần tử của mảng a printf(“Nhap vao phan tu thu %d: “, i+1); => Sử dụng vòng lặp for scanf("%d", &rainfall[i] ); • Lưu ý } return 0; – Tên mảng l{ một hằng (hằng con trỏ) do đó } không thể thực hiện phép to|n với tên mảng như phép g|n sau khi đ~ khai b|o 13 14 9.1.3. C|c thao t|c cơ bản trên mảng 9.1.3. C|c thao t|c cơ bản trên mảng a. Nhập dữ liệu cho mảng #include • Lưu ý #include – Nếu số phần tử của mảng được nhập từ b{n void main(){ phím v{ chỉ biết trước số phần tử tối đa tối đa int a[100]; => khai b|o mảng với kích thước tối đa v{ sử int n, i; dụng biến lưu số phần tử thực sự của mảng. do{ – Ví dụ: Khai b|o mảng số nguyên a có tối đa 100 printf(“\n Cho biet so phan phần tử. Nhập từ b{n phím số phần tử trong tu cua mang: “); mảng v{ gi| trị c|c phần tử đó…. scanf(“%d”,&n); }while (n>100||n
9.1.3. C|c thao t|c cơ bản trên mảng 9.1.3. C|c thao t|c cơ bản trên mảng for(i = 0; i < n; i++){ b. Xuất dữ liệu trong mảng printf(“a[%d] = ", i); – Dùng hàm printf() scanf("%d",&a[i]); – Để hiển thị tất cả c|c phần tử: dùng vòng for } • Ví dụ getch(); – Hiển thị một phần tử bất kì } – Hiển thị tất cả c|c phần tử, mỗi phần tử trên một dòng – Hiển thị tất cả c|c phần tử trên một dòng, c|ch nhau 2 vị trí – Hiển thị từng k phần tử trên một dòng 17 18 9.1.3. C|c thao t|c cơ bản trên mảng 9.1.3. C|c thao t|c cơ bản trên mảng #include c. Tìm gi| trị lớn nhất, nhỏ nhất #define MONTHS 12 int main(){ • Tìm gi| trị lớn nhất int rainfall[MONTHS], i; – Giả sử phần tử đó l{ phần tử đầu tiên for ( i=0; i < MONTHS; i++ ){ – Lần lượt so s|nh với c|c phần tử còn lại printf(“Nhap vao phan tu thu – Nếu lớn hơn hoặc bằng => so s|nh tiếp %d: “, i+1); scanf("%d", &rainfall[i] ); – Nếu nhỏ hơn => coi phần tử n{y l{ phần tử lớn } nhất v{ tiếp tục so s|nh for ( i=0; i < MONTHS; i++ ) – Cách làm? printf( "%5d ” , rainfall[i]); • Tìm gi| trị nhỏ nhất: tương tự printf("\n"); return 0; 19 20 } 5
9.1.3. C|c thao t|c cơ bản trên mảng 9.1.4. Tìm kiếm trên mảng max = rainfall[0]; • Bài toán – Cho mảng dữ liệu a v{ một gi| trị k for(i = 1; i < n; i++) – Tìm c|c phần tử trong mảng a có gi| trị bằng if(max < a[i]) (giống) với k. Nếu có in ra vị trí (chỉ số) c|c max = a[i]; phần tử n{y. Ngược lại thông b|o không tìm thấy printf("\n Luong mua nhieu nhat la: • Cách làm %d", max); – Duyệt to{n bộ c|c phần tử trong mảng – Nếu a[i] bằng (giống) k thì lưu lại chỉ số i – Sử dụng một biến để x|c định tìm thấy hay 21 không tìm thấy 22 9.1.4. Tìm kiếm trên mảng 9.1.4. Tìm kiếm trên mảng • Phân tích #include – Duyệt to{n bộ c|c phần tử #include • Vòng lặp for (while, do while) void main(){ – Lưu lại i nếu a[i] bằng (giống) k int a[100], chi_so[100]; • Sử dụng mảng lưu chỉ số int n;//n la số phần tử trong mảng – Biến x|c định tìm thấy hay không tìm thấy int i, k, kiem_tra; • Biến nhận gi| trị 0 hoặc 1 printf(“ Nhap vao so phan tu cua • Biến nhận gi| trị 0 hoặc >=1 (tìm thấy thì tăng gi| trị) mang: “); scanf(“%d”,&n); printf(“Nhap vao giá trị tim kiem“); 23 scanf(“%d”,&k); 24 6
9.1.4. Tìm kiếm trên mảng 9.1.4. Tìm kiếm trên mảng //Nhap cac phan tu cho mang a ..... if(kiem_tra > 0){ printf(“Trong mang co %d phan tu co //Phan xu ly tim kiem gia tri bang %d”,kiem_tra,k); kiem_tra = 0; printf(“\nChi so cua cac phan tula:“); // Duyệt qua tất cả các phần tử for(i = 0;i < kiem_tra;i++) for(i = 0;i
9.1.5. Sắp xếp mảng 9.1.5. Sắp xếp mảng • Giải thuật sắp xếp lựa chọn • Ý tưởng – Tìm phần tử nhỏ nhất chưa được sắp xếp trong – Lần sắp xếp thứ 1 mảng • So s|nh a[0] với c|c a[i], i = 1..n-1 – Đổi chỗ nó với phần tử đầu tiên trong phần a[0] > a[i] => đổi chỗ a[0] v{ a[i] chưa được sắp • Thu được a[0] l{ phần tử nhỏ nhất – Lần sắp xếp thứ 2 • So s|nh a[1] với c|c a[i], i = 2..n-1 a[1] > a[i] => đổi chỗ a[1] v{ a[i] • Thu được a[1] l{ phần tử nhỏ thứ 2 29 30 9.1.5. Sắp xếp mảng 9.1.5. Sắp xếp mảng • Ý tưởng • A = { 12, 5, 3, 4 }; – Lần sắp xếp thứ k • So sánh a[k-1] với c|c a[i], i = k..n-1 Lượt 1 Lượt 2 Lượt 3 a[k-1] > a[i] => đổi chỗ a[k-1] và a[i] • Thu được a[k-1] l{ phần tử nhỏ thứ k 12 3 3 3 – ….. 5 12 4 4 – Lần sắp xếp thứ n-1 3 5 12 5 • So sánh a[n-2] và a[n-1] 4 4 5 12 a[n-2] > a[n-1] => đổi chỗ a[n-2] và a[n-1] • Thu được a[n-2] l{ phần tử nhó thứ n-1 => còn lại a[n-1] l{ phần tử nhỏ thứ n (lớn nhất) 31 32 8
9.1.5. Sắp xếp mảng 9.1.5. Sắp xếp mảng //Khai bao cac bien • Ví dụ (Trang 168) int a[100]; – Nhập v{o từ b{n phím một mảng số nguyên m int i, j, tmp; trong đó số phần tử cũng được nhập từ b{n //Sap xep phím for (i = 0; i < n-1; i++) – Hiển thị c|c phần tử vừa được nhập v{o for (j = i+1; j a[j]){ có hiển thị c|c phần tử trong mỗi lượt sắp xếp. tmp= a[i]; a[i]= a[j]; a[j] = tmp; } 33 34 9.1.5. Sắp xếp mảng 9.1.5. Sắp xếp mảng #include // nhập giá trị cho các phần tử #include for(i = 0;i
9.1.5. Sắp xếp mảng Nội dung for(i = 0; i
9.2.2. Khai b|o v{ sử dụng x}u 9.2.2. Khai b|o v{ sử dụng x}u a. Khai báo xâu b. Truy cập v{o một phần tử của x}u • Cú pháp • Cú pháp: char tên_xâu [số_kí_tự_tối_đa]; tên_xâu [chỉ_số_của_kí_tự] • Lưu ý: • Ví dụ – Để lưu trữ một x}u có n kí tự chúng ta cần một char quequan[10]; mảng có kích thước n+1 quequan = “Ha noi” ;//x}u n{y có nội dung l{ “Ha noi” • Ví dụ  quequan[0] lưu trữ ‘q’ – Để lưu trữ x}u “Tin hoc” chúng ta phải khai b|o quequan[1] ‘u’ x}u có số phần tử tối đa ít nhất l{ 8 quequan[5] ‘i’ char str [8]; 41 quequan[6] ‘\0’ 42 9.2.3. C|c h{m xử lý kí tự 9.2.3. C|c h{m xử lý kí tự • Tệp tiêu đề sử dụng: ctype.h • int isalpha(int ch): kiểm tra xem kí tự có phải chữ c|i hay không (‘a’…’z’,’A’,..’Z’) • int toupper(int ch): chuyển kí tự thường • int isdigit(int ch): kiểm tra chữ số (‘0‘,‘1‘,..‘9‘) th{nh kí tự hoa • int islower(int ch): kiểm tra chữ thường toupper(‘a’) => ‘A’ • int isupper(int ch): kiểm tra chữ hoa • int tolower(int ch): chuyển kí tự hoa th{nh • int iscntrl(int ch): kiểm tra kí tự điều khiển (0-31) kí tự thường • int isspace(int ch): kiểm tra kí tự dấu c|ch (m~ 32), tolower(‘B’) => ‘b’ xuống dòng (‘\n’ 10), đầu dòng (‘\r’ 13), tab ngang (‘\t’ 9), tab dọc (‘\v’ 11) 43 • trả về kh|c 0 nếu đúng, ngược lại trả về 0 44 11
9.2.3. C|c h{m xử lý kí tự 9.2.3. C|c h{m xử lý kí tự #include if(isupper(ch)){ #include printf(“Ki tu nay la chu hoa\n”); #include printf(“Ki tu chu thuong tuong void main(){ ung %c\n”,tolower(ch)); char ch; }else if(islower(ch)){ printf(“Nhap vao mot ki tu: “); printf(“Ki tu nay la chu thuong\n”); scanf(“%c”, &ch); printf(“Ki tu chu hoa tuong ung %c\n”,toupper(ch)); } getch(); 45 } 46 9.2.3. C|c h{m xử lý kí tự 9.2.4. C|c h{m xử lý x}u kí tự V{o ra x}u kí tự Tệp tiêu đề: string.h • Tệp tiêu đề: stdio.h • size_t strlen(char* tên_xâu): trả về độ d{i x}u • char* strcpy(char* x}u_đích, char* x}u_nguồn): • Nhập x}u kí tự sao chép xâu – gets(tên_xâu); • int strcmp(char* x}u_thứ_nhất, char* – scanf(“%s”,tên_xâu); x}u_thứ_hai): so s|nh hai x}u • Hiển thị x}u kí tự – gi| trị 0 : hai x}u giống nhau – puts(tên_xâu); – gi| trị0: x}u thứ nhất nhỏ hơn x}u thứ hai • char* strcat(char* x}u_đích, char* x}u_nguồn): • Sự kh|c nhau giữa gets v{ scanf? ghép nối x}u nguồn v{o ngay sau x}u đích 47 48 12
9.2.4. C|c h{m xử lý x}u kí tự 9.2.4. C|c h{m xử lý x}u kí tựp (ví dụ p183) Tệp tiêu đề: stdlib.h #include • int atoi(char* str): chuyển một x}u kí tự #include th{nh một số nguyên tương ứng #include void main(){ • int atol(char*str): chuyển th{nh số long int clrscr(); • float atof(char* str): chuyển th{nh số thực char str1[10] = “abc”; • Không th{nh công cả 3 h{m: trả về 0 char str2[10] = “def”; printf(“ str1: %s”,str1); printf(“\n str2: %s”,str2); printf(“\n strcmp(str1,str2)= %d”, 49 strcmp(str1,str2)); 50 9.2.4. C|c h{m xử lý x}u kí tự 9.3. Con trỏ v{ địa chỉ printf(“\n strcpy(str1,str2) = %s”, • 9.3.1. Tổng quan về con trỏ strcpy(str1,str2)); • 9.3.2. Các phép toán làm việc với con trỏ printf(“ str1: %s”,str1); printf(“\n str2: %s”,str2); • 9.3.3. Sử dụng con trỏ làm việc với mảng strcpy(str1,”ab”);strcpy(str2,”abc”); printf(“ str1: %s”,str1); printf(“\n str2: %s”,str2); printf(“\n strcmp(str1,str2) = %d”, strcmp(str1,str2)); getch(); } 51 13
9.3.1. Tổng quan về con trỏ 9.3.1. Tổng quan về con trỏ • a. Địa chỉ v{ gi| trị của một biến • a. Địa chỉ v{ gi| trị của một biến (tiếp) – Bộ nhớ như một d~y c|c byte nhớ. – Một biến luôn có hai đặc tính: – C|c byte nhớ được x|c định một c|ch duy nhất qua một • Địa chỉ của biến. địa chỉ. • Gi| trị của biến. – Biến được lưu trong bộ nhớ. – Ví dụ: – Khi khai b|o một biến • int i, j; • Chương trình dịch sẽ cấp ph|t cho biến đó một số ô nhớ liên tiếp • i = 3; đủ để chứa nội dung của biến. Ví dụ một biến số nguyên (int) Biến Địa chỉ Giá trị • j = i + 1; được cấp ph|t 2 byte. i FFEC 3 • Địa chỉ của một biến chính l{ địa chỉ của byte đầu tiên trong số đó. j FFEE 4 53 54 9.3.1. Tổng quan về con trỏ 9.3.1. Tổng quan về con trỏ • b. Kh|i niệm v{ khai b|o con trỏ • To|n tử & và * – To|n tử &: Trả về địa chỉ của biến. – Con trỏ l{ một biến m{ gi| trị của nó l{ địa chỉ của một – To|n tử *: Trả về gi| trị chứa trong vùng nhớ được trỏ vùng nhớ. bởi gi| trị của biến con trỏ. – Khai b|o con trỏ: ... p ... a ... – Cả hai to|n tử * v{ & có độ ưu tiên cao hơn tất cả c|c • Cú ph|p khai b|o một con trỏ như sau: to|n tử số học ngoại trừ to|n tử đảo dấu. Kieu_du_lieu *ten_bien_con_tro; – Ví dụ: void main() – Ví dụ Biến Địa chỉ Giá trị { • int i = 3; int i = 3; int *p; i FFEC 3 • int *p; p = &i; • p = &i; p FFEE FFEC printf("*p = %d \n",*p); getch(); – Một con trỏ chỉ có thể trỏ tới một đối tượng cùng kiểu. } 55 56 14
9.3.1. Tổng quan về con trỏ 9.3.1. Tổng quan về con trỏ • c. Sử dụng biến con trỏ: • Ví dụ 1: – Một biến con trỏ có thể được g|n bởi: main() • Địa chỉ của một biến kh|c: { ten_bien_con_tro = &ten_bien; int i = 3, j = 6; • Gi| trị của một con trỏ kh|c (tốt nhất l{ cùng kiểu): ten_bien_con_tro2 = ten_bien_con_tro1; int *p1, *p2; • Gi| trị NULL (số 0): p1 = &i; ten_bien_con_tro = 0; p2 = &j; – G|n gi| trị cho biến(vùng nhớ) m{ biến con trỏ *p1 = *p2; trỏ tới: } • *ten_bien_con_tro = 10; 57 58 9.3.1. Tổng quan về con trỏ • Ví dụ 2: main() { int i = 3, j = 6; int *p1, *p2; p1 = &i; p2 = &j; p1 = p2; } 59 60 15
9.3.1. Tổng quan về con trỏ 9.3.2. C|c phép to|n l{m việc với con trỏ • d. Con trỏ void • Cộng/trừ con trỏ với một số nguyên (int, long)  Kết quả l{ một con trỏ cùng kiểu – void *ten_bien_con_tro; – ptr--; //ptr trỏ đến vị trí của phần tử đứng trước nó. – Con trỏ đặc biệt, không có kiểu, • Trừ hai con trỏ cho nhau – Có thể nhận gi| trị l{ địa chỉ của một biến thuộc – Kết quả l{ một số nguyên – Kết quả n{y nói lên khoảng c|ch (số phần tử thuộc kiểu dữ liệu của bất kỳ kiểu dữ liệu n{o. con trỏ) ở giữa hai con trỏ. – Ví dụ: • C|c phép to|n: Cộng, nh}n, chia, lấy số dư trên con trỏ l{ • void *p, *q; không hợp lệ. • int x = 21; • Ví dụ: (p2 trỏ đến số nguyên nằm ngay sau x trong bộ nhớ) • float y = 34.34; int x, *p1, *p2; p1= &x; • p = &x; q = &y; p2= p1+1; 61 16