Đề cương tin học đại cương (ngôn ngữ c)

TRƯỜNG ðẠI HỌC SƯ PHẠM KỸ THUẬT HƯNG YÊN KHOA CÔNG NGHỆ THÔNG TIN ðỀ CƯƠNG BÀI GIẢNG HỌC PHẦN: TIN HỌC ðẠI CƯƠNG Trình ñộ ñào tạo Hệ ñào tạo : : ðại học Chính quy ðề cương Tin học ñại cương --------- ñào tạo tín chỉ Khoa CNTT – Trường ðHSP Kỹ thuật Hưng Yên Trang 2 MỤC LỤC BÀI 1: THÔNG TIN VÀ XỬ LÝ THÔNG TIN - HỆ THỐNG TÍNH TOÁN VÀ BIỂU DIỄN THÔNG TIN TRONG MÁY TÍNH .......................................................................................................... 4 1.1 Thông tin và xử lý thông tin, hệ thống tính toán và biểu diễn thông tin trong máy tính ................................................................................................................. 4 1.2. Tổng quan về hệ thống máy tính ................................................................... 17 BÀI 2: GIẢI BÀI TOÁN TRÊN MÁY TÍNH ðIỆN TỬ ................................................................ 33 2.1. Thuật toán ..................................................................................................... 33 2.2. Một số thuật toán thông dụng ........................................................................ 36 2.3. Các phương pháp lập trình ............................................................................ 41 2.4. Một số ngôn ngữ lập trình ............................................................................. 46 2.5. Ngôn ngữ lập trình C/C++ ............................................................................ 49 BÀI 3: CÁC THÀNH PHẦN CƠ BẢN CỦA NGÔN NGỮ LẬP TRÌNH C/C++ ......................................52 3.1. Cấu trúc một chương trình C/C++ ñơn giản .................................................. 52 3.2. Các phần tử cơ bản của một ngôn ngữ lập trình ............................................ 54 3.3. Các kiểu dữ liệu cơ bản ................................................................................. 55 3.4. Biến, hằng và cách khai báo .......................................................................... 57 3.5. Các phép toán ................................................................................................ 64 Bài 4: CÁC THÀNH PHẦN CƠ BẢN CỦA NGÔN NGỮ LẬP TRÌNH C/C++(tiếp)........................ 69 4.1. Biểu thức ....................................................................................................... 69 4.2. Một số hàm thường dùng .............................................................................. 69 4.3. Nhập/xuất dữ liệu (bàn phím, màn hình) ....................................................... 70 Bài 5: CẤU TRÚC RẼ NHÁNH ............................................................................................ 76 5.1. Câu lệnh ñơn, khối lệnh ................................................................................ 76 5.2. Các cấu trúc rẽ nhánh .................................................................................... 76 5.3. Bài tập ........................................................................................................... 80 Bài 6: THỰC HÀNH VỀ VÀO RA DỮ LIỆU VÀ CẤU TRÚC RẼ NHÁNH ................................... 81 Bài 7: MỘT SỐ CẤU TRÚC LẶP VÀ LỆNH ðIỀU KHIỂN ....................................................... 82 7.1. Cấu trúc lặp while ......................................................................................... 82 7.2. Cấu trúc lặp do .. while ................................................................................. 83 7.3. Cấu trúc lặp for.............................................................................................. 84 7.4. Break, continue, return .................................................................................. 86 7.5. Bài tập ........................................................................................................... 88 BÀI 8: BÀI TẬP VỀ CÁC CẤU TRÚC ðIỀU KHIỂN ............................................................... 90 Bài 9: THỰC HÀNH VỀ CẤU TRÚC LẶP .............................................................................. 91 Bài 10: CHƯƠNG TRÌNH CON ............................................................................................. 91 10.1. ðặt vấn ñề ................................................................................................... 91 10.2. Ví dụ về một chương trình có sử dụng chương trình con ............................ 91 10.3. Phạm vi hoạt ñộng của biến ........................................................................ 92 10.4. Cấu trúc một chương trình con .................................................................... 95 10.5. Truyền tham số cho chương trình con ......................................................... 96 10.6. Nguyên tắc hoạt ñộng của chương trình con ............................................... 97 10.7. Nguyên tắc sử dụng chương trình con ......................................................... 97 Bài 11: THỰC HÀNH VỀ CHƯƠNG TRÌNH CON .................................................................... 99 ðề cương Tin học ñại cương --------- ñào tạo tín chỉ Khoa CNTT – Trường ðHSP Kỹ thuật Hưng Yên Trang 3 Bài 12: THI GIỮA KỲ .......................................................................................................... 99 Bài 13: KIỂU DỮ LIỆU MẢNG ............................................................................................. 99 13.1 Kiểu dữ diệu mảng một chiều ..................................................................... 99 13.2 Kiểu dữ diệu mảng hai chiều ..................................................................... 105 13.3. Bài tập ....................................................................................................... 109 Bài 14: BÀI TẬP VỀ MẢNG VÀ CHƯƠNG TRÌNH CON ...................................................... 111 Bài 15: THỰC HÀNH VỀ KIỂU DỮ LIỆU MẢNG .................................................................. 113 Sinh viên thực hành theo sự hướng dẫn của giáo viên .................................................... 113 Bài 16: KIỂU DỮ LIỆU CON TRỎ ...................................................................................... 113 16.1. Khái niệm và cách khai báo con trỏ ............................................................... 113 16.2. Con trỏ và cách sử dụng ............................................................................... 114 16.3. Các phép toán trên con trỏ ............................................................................ 116 16.4. Các kiểu con trỏ ........................................................................................... 117 16.5. Liên hệ giữa con trỏ và mảng ........................................................................ 117 16.6. XÂU KÝ TỰ .............................................................................................. 120 16.7. Bài tập ........................................................................................................ 128 Bài 17: THỰC HÀNH VỀ KIỂU DỮ LIỆU CON TRỎ.............................................................. 129 ðề cương Tin học ñại cương --------- ñào tạo tín chỉ BÀI 1: THÔNG TIN VÀ XỬ LÝ THÔNG TIN - HỆ THỐNG TÍNH TOÁN VÀ BIỂU DIỄN THÔNG TIN TRONG MÁY TÍNH 1.1 Thông tin và xử lý thông tin, hệ thống tính toán và biểu diễn thông tin trong máy tính 1.1.1. Thông tin 1.1.1.1. Khái niệm về thông tin Thông tin (informations) là một khái niệm ñược sử dụng thường ngày. Con người có nhu cầu ñọc báo, nghe ñài, xem phim, video, ñi tham quan, du lịch, tham khảo ý kiến người khác, ... ñể nhận ñược thêm thông tin mới. Thông tin mang lại cho con người sự hiểu biết, nhận thức tốt hơn về những ñối tượng trong ñời sống xã hội, trong thiên nhiên, ... giúp cho họ thực hiện hợp lý công việc cần làm ñể ñạt tới mục ñích một cách tốt nhất. Những ñám mây ñen ñùn lên ở chân trời phía ñông cũng chứa ñựng thông tin báo hiệu về trận mưa lớn sắp xảy ra. Màu ñen của mây, tốc ñộ vận chuyển của mây chứa các thông tin về khí tượng. Biểu ñồ thống kê sản phẩm hàng tháng của từng phân xưởng bánh kẹo chứa ñựng các thông tin về năng suất lao ñộng, về mức ñộ thực hiện kế hoạch sản xuất của phân xưởng ñó. Nốt nhạc trong bản sô-nát ánh trăng của Beethoven làm cho người nghe cảm thấy ñược sự tươi mát, êm dịu của ñêm trăng. Những thông tin về cảm xúc của tác giả ñó ñược truyền ñạt lại. Khi tiếp nhận ñược thông tin, con người thường phải xử lý nó ñể tạo ra những thông tin mới, có ích hơn, từ ñó có những phản ứng nhất ñịnh. Người tài xế chăm chú quan sát người, xe cộ ñi lại trên ñường, ñộ tốt xấu mặt ñường, tính năng kỹ thuật cũng như vị trí của chiếc xe ñể quyết ñịnh, cần tăng tốc ñộ hay hãm phanh, cần bẻ lái sang trái hay sang phải... nhằm ñảm bảo an toàn tối ña cho chuyến xe ñi. Thông tin có thể ñược phát sinh, ñược lưu trữ, ñược truyền, ñược tìm kiếm, ñược sao chép, ñược xử lý, nhân bản. Thông tin cũng có thể biến dạng, sai lệch hoặc bị phá hủy. 1.1.1.2. ðơn vị ño thông tin Thông tin cũng có thể ño ñược. ðơn vị ño thông tin gọi là bit. Lượng thông tin chứa trong một bít là vừa ñủ ñể nhận biết một trong hai trạng thái của một biến cố có xác xuất xuất hiện như nhau. Trong số học nhị phân mà ta sẽ giới thiệu sau này chỉ sử dụng hai chữ số là chữ số 0 và chữ số 1. Khả năng hai chữ số ñó ñược sử dụng là như nhau. Tại mỗi thời ñiểm, trong một bít chỉ lưu trữ ñược hoặc là chữ số 0 hoặc là chữ số 1. Từ bít là viết tắt của Binary digit (chữ số nhị phân). Trong tin học ta thường dùng một số ñơn vị bội của bít sau ñây: ðề cương Tin học ñại cương Tên gọi Byte Kilobyte Megabyte Gigabyte Terabyte 1.1.1.3. Khái niệm về dữ liệu Dữ liệu (data) là khái ni dữ liệu người ta xử lý ñể có thông tin. Thông tin và dữ liệu khác nhau c liệu là những dữ kiện không có cấu trúc v chức và xử lý. Cùng một thông tin có thể biểu diễn bằng những dữ liệu khác nhau. Ví dụ: Cùng ñể biểu diễn 1 ñ trong hệ ñếm La Mã thì lại d
Chú ý: Trong thực tế cuộc sống ng giống nhau. 1.2. 1.1.2. Xử lý thông tin 1.2.1.1. Sơ ñồ tổng quát của quá tr Mọi quá trình xử lý thông tin bằng máy tính hay theo một quy trình sau: Dữ liệu (data) ñược nhập ở ñầu v trình xử lý nào ñó ñể nhân ñ và xuất thông tin ñều có thể ñ Hình 1.1. Mô hình t 1.1.2.2 Xử lý thông tin bằng MTðT Quá trình xử lý thông tin tr tay (trên giấy, với bút, bàn tính ...). Do v hiện việc xử lý thủ công nói chung: --------- ñào tạo tín chỉ Viết tắt Giá trị B 8 Bit KB 1024 byte =210B MB 1024KB = 210KB GB 1024MB = 210MB TB 1024GB = 210TB ệm rộng hơn của thông tin, nó là nguồn gốc của thông tin, từ ơ bản ở chỗ: Thông tin chứa ñựng ý nghĩa, c à không có ý nghĩa rõ ràng nếu nó không ñ ơn vị thì trong hệ ñếm thập phân biểu diễn l ùng kí hiệu I…. ười ta sử dụng 2 khái niệm thông tin v ình xử lý thông tin bằng con người ñều ñ ào (input). Máy tính hay con người sẽ thực hiện quá ược thông tin ở ñầu ra (output). Quá trình nh ược lưu trữ. ổng quát quá trình xử lý thông tin ên máy tính ñiện tử (MTðT) cũng tương t ậy trước hết ta phải lưu ý một số ñiểm khi thực òn dữ ược tổ à ‘1’ còn à dữ liệu ược thực hiện ập dữ liệu, xử lý ự như làm bằng ðề cương Tin học ñại cương --------- ñào tạo tín chỉ Khoa CNTT – Trường ðHSP Kỹ thuật Hưng Yên Trang 6 ðể mô tả cách thức xử lý, dữ liệu vào, các kết quả trung gian và kết quả cuối cùng con người cần phải sử dụng một số công cụ nhất ñịnh như: giấy, bút, ... và trí nhớ của con người. - Cần sử dụng một số công cụ nào ñó như: bàn gẩy, thước tính, ... ñể thực hiện các phép toán. - Quá trình thực hiện mỗi phép toán nói chung ñều qua các bước sau: chọn giá trị vào (các giá trị, các toán hạng tham gia phép toán), thực hiện phép toán và ghi nhớ kết quả phép toán lên một giá mang tin nào ñó. - Con người trực tiếp xác ñịnh trình tự thực hiện liên tiếp các phép toán trong từng thời ñiểm của toàn bộ quá trình xử lý. MTðT là công cụ xử lý thông tin tự ñộng, không cần sự tham gia trực tiếp của con người. Tuy nhiên, MTðT tự nó không thể quyết ñịnh ñược khi nào thì phải làm gì, cộng hay trừ, nhân hay chia, các dữ liệu tham gia xử lý sẽ lấy ở ñâu ... ðể làm ñược ñiều ñó con người cần phải cung cấp ñầy ñủ ngay từ ñầu cho MTðT các mã lệnh, chỉ thị (tất nhiên phải bằng ngôn ngữ mà máy có thể “hiểu” ñược) ñể hướng dẫn MTðT thực hiện công việc theo ñúng yêu cầu do con người ñề ra cho nó. Tập hợp các chỉ thị như vậy ñược con người soạn thảo bằng một ngôn ngữ mà máy hiểu ñược gọi là chương trình và ñược lưu trữ trong bộ nhớ của máy. Chương trình ñó sẽ thay cho con người ñể ñiều khiển MTðT làm việc. Tương ứng với hai lớp thông tin liên tục và rời rạc, máy tính ñược chia thành hai loại. MTðT xử lý thông tin liên tục gọi là máy tính tương tự (Analog computer), còn máy tính xử lý thông tin rời rạc gọi là máy tính số (Digital computer). Máy tính số cũng có thể dùng ñể xử lý thông tin liên tục, nếu nó ñược trang bị thêm thiết bị bién ñổi thông tin từ dạng liên tục sang dạng số (trước khi xử lý) và thiết bị biến ñổi thông tin từ dạng rời rạc sang dạng liên tục (sau khi xử lý) ñể ñưa ra môi trường ngoài. Lược ñồ cấu trúc kiểu xử lý như vậy ñược mô tả ở hình sau: Trong ñó: A: Kí hiệu thông tin dạng liên tục. D: Kí hiệu thông tin rời rạc. A/D: Kí hiệu thiết bị biến ñổi “ Liên tục thành rời rạc”. D/A: Kí hiệu thiết bị biến ñổi ngược lại. MTðT có cả các ñặc tính của máy tính tương tự và số ñược gọi là máy tính lai (Hybrit computer). Trong giáo trình này ta chỉ xét loại máy tính số, do vậy từ ñây thuật ngữ MTðT ñược hiểu là máy tính số. Quá trình xử lý thông tin bằng MTðT diễn ra nhờ thực hiện một dãy các phép toán cơ sở (cộng, trừ, nhân, chia số học và logic, ...) trên các dữ liệu ñược lưu trữ trong một MÁY TÍNH SỐ D A/D D D/A ðề cương Tin học ñại cương --------- ñào tạo tín chỉ Khoa CNTT – Trường ðHSP Kỹ thuật Hưng Yên Trang 7 khối chức năng gọi là bộ nhớ. Bộ nhớ là giá mang thông tin của MTðT. ðể thiết lập thứ tự thực hiện các phép toán cơ sở và ñiều khiển toàn bộ quá trình xử lý, MTðT có một khối chức năng gọi là bộ ñiều khiển. Một khối chức năng khác là bộ số học và logic ñược dùng ñể thực hiện các phép toán cơ sở. Mỗi MTðT có thể thực hiện một số phép toán cơ sở nhất ñịnh nào ñó. ðể mô tả một phép toán cơ sở, người ta dùng một lệnh tương ứng. Tập các lệnh gọi là hệ lệnh của máy. Mỗi loại (họ) máy có hệ lệnh riêng của nó. Dãy các lệnh dược xây dựng nhằm xác ñịnh trật tự và thực hiện một yêu cầu cụ thể nào ñó gọi là chương trình (Program). Công việc tạo ra chương trình gọi là lập trình (Programing). Hình 1.1. Hình ảnh minh hoạ câu lệnh và chương trình. Tóm lại MTðT xử lý dữ liệu dựa trên những chỉ dẫn ñưa vào, không cần phải nói, những chỉ dẫn ñó phải có nghĩa và hoàn chỉnh. Ngoài ra chúng phải: 1. Có tính tuần tự. 2. Có giới hạn. 3. Chính xác. Và MTðT hoạt ñộng theo nguyên tắc: “ Tự ñộng ñiều khiển bằng chương trình ”. Ta có thể minh hoạ quá trình xử lý dữ liệu trong MTðT bằng lược ñồ ở hình dưới ñây: Hình 1.2. Quá trình xử lý dữ liệu trong MTðT. Cụ thể hơn, giả sử ta có dữ liệu vào là X cần xử lý. Bằng một công cụ tính toán không phải là MTðT, con người có thể thực hiện tính toán theo một giải thuật f ñể thu ñược kết quả Y. Quá trình xử lý ñó khi sử dụng MTðT ñược tiến hành tự ñộng như sau: Mã hoá X nhờ phép mã hoá C ñể thu ñược mã x (ðiều quan trọng luôn luôn ghi nhớ là MTðT chỉ xử lý trực tiếp với dữ liệu ở mã nhị phân nên mã x là ở dạng nhị phân). Thay cho giải thuật MTðT Kết quả Chương trình Dữ liệu vào Software Program 2 Program 1 Commands Commands Commands ðề cương Tin học ñại cương --------- ñào tạo tín chỉ Khoa CNTT – Trường ðHSP Kỹ thuật Hưng Yên Trang 8 (tập các quy tắc xử lý) f MTðT xử lý tự ñộng dữ liệu x theo sự ñiều khiển của chương trình P do con người lập ra và lưu trữ sẵn trong bộ nhớ của máy tính. Sau khi chương trình P thực hiện xong, ta thu ñược kết quả Y (mã Y ở trong dạng nhị phân). Nhờ phép giải mã C-1 ta thu ñược kết quả phải tìm Y (dưới dạng biểu diễn thông dụng mà con người quen dùng). Sự tương ứng hai cách xử lý có thể mô tả như hình vẽ dưới ñây: Ta có thể tóm tắt một quá trình xử lý dữ liệu bằng MTðT thường ñược tiến hành qua các bước chính sau: - Trước hết, ñưa chương trình cần thực hiện (do người lập sẵn) vào bộ nhớ của máy. - Theo các chỉ dẫn của chương trình: + Máy bắt ñầu xử lý, dữ liệu ñược nhập từ môi trường ngoài vào bộ nhớ thông qua thiết bị nhập dữ liệu. + Máy thao tác dữ liệu và ghi kết quả trong bộ nhớ. + ðưa kết quả từ bộ nhớ ra môi trường ngoài thông qua thiết bị xuất dữ liệu. Hoạt ñộng trên của MTðT ñược thực hiện dựa trên nguyên lý do Von Neumann ñề xuất năm 1946. Nội dung nguyên lý thể hiện: - ðiều khiển chương trình: MTðT hoạt ñộng theo sự chỉ dẫn, ñiều khiển của chương trình lưu trữ trong bộ nhớ của nó. Các bước tác ñộng ñược tiến hành theo các lệnh của chương trình. Chương trình chỉ dẫn cho MTðT biết phải làm gì và phải làm như thế nào. - Truy nhập theo ñịa chỉ: Như ñã biết, dữ liệu theo nghĩa rộng (dữ liệu vào, kết quả trung gian, kết quả cuối cùng, chương trình ...) ñược lưu trữ trong bộ nhớ trong, những vùng nhớ ñược ñịnh vị bằng các số mà ta gọi là ñịa chỉ. Trong chương trình, dữ liệu ñược chỉ ñịnh thông qua ñịa chỉ. Như vậy việc truy nhập tới dữ liệu là gián tiếp. Hai nội dung trên là cơ sở ñảm bảo cho MTðT thực hiện ñược chức năng xử lý thông tin một cách tự ñộng. y MTðT x C X Y C-1 P f ðề cương Tin học ñại cương --------- ñào tạo tín chỉ Khoa CNTT – Trường ðHSP Kỹ thuật Hưng Yên Trang 9 1.3. 1.1.3. Hệ thống tính toán và biểu diễn thông tin trong máy tính 1.3.1. 1.1.3.1. Biểu diễn thông tin trong các hệ ñếm ðể có cơ sở hình dung quá trình xử lý dữ liệu xảy ra bên trong MTðT như thế nào, trước hết chúng ta xét các hệ ñếm. Hệ ñếm là tập hợp các ký hiệu và qui tắc sử dụng tập ký hiệu ñó ñể biểu diễn và xác ñịnh các giá trị các số. Mỗi hệ ñếm có một số ký số (digits) hữu hạn. Tổng số ký số của mỗi hệ ñếm ñược gọi là cơ số (base hay radix), kí hiệu là b. Trong ngành toán - tin học hiện nay phổ biến 4 hệ ñếm là hệ thập phân, hệ nhị phân, hệ bát phân và hệ thập lục phân. 1.3.2. 1.1.3.2. Hệ ñếm thập phân (Decimal system, b=10) Hệ ñếm thập phân hay hệ ñếm cơ số 10 là một trong các phát minh của người Ả rập cổ, bao gồm 10 ký số theo ký hiệu sau: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 Qui tắc tính giá trị của hệ ñếm này là mỗi ñơn vị ở một hàng bất kỳ có giá trị bằng 10 ñơn vị của hàng kế cận bên phải. Ở ñây b=10. Bất kỳ số nguyên dương trong hệ thập phân có thể biểu diễn như là một tổng các số hạng, mỗi số hạng là tích của một số với 10 lũy thừa, trong ñó số mũ lũy thừa ñược tăng thêm 1 ñơn vị kể từ số mũ lũy thừa phía bên phải nó. Số mũ lũy thừa của hàng ñơn vị trong hệ thập phân là 0. Ví dụ: Số 5246 có thể ñược biểu diễn như sau: 5246 = 5 x 103 + 2 x 102 + 4 x 101 + 6 x 100 = 5 x 1000 + 2 x 100 + 4 x 10 + 6 x 1 Thể hiện như trên gọi là ký hiệu mở rộng của số nguyên. Vì 5246 = 5000 + 200 + 40 + 6 Như vậy, trong số 5246 : ký số 6 trong số nguyên ñại diện cho giá trị 6 ñơn vị (1s), ký số 4 ñại diện cho giá trị 4 chục (10s), ký số 2 ñại diện cho giá trị 2 trăm (100s) và ký số 5 ñại diện cho giá trị 5 ngàn (1000s). Nghĩa là, số lũy thừa của 10 tăng dần 1 ñơn vị từ trái sang phải tương ứng với vị trí ký hiệu số, 100 = 1 101 = 10 102 = 100 103 = 1000 104 = 10000 ... Mỗi ký số ở thứ tự khác nhau trong số sẽ có giá trị khác nhau, ta gọi là giá trị vị trí (place value). Phần thập phân trong hệ thập phân sau dấu chấm phân cách thập phân (theo qui ước của Mỹ) thể hiện trong ký hiệu mở rộng bởi 10 lũy thừa âm tính từ phải sang trái kể từ dấu chấm phân cách. 1.1.3.3. Hệ ñếm nhị phân (Binary system, b=2) Với b=2, chúng ta có hệ ñếm nhị ph