Giáo trình Cấu trúc dữ liệu và giải thuật (Ngành/Nghề: Công nghệ thông tin – Trình độ: Cao đẳng) - Trường CĐ Kinh tế - Kỹ thuật Vinatex TP. HCM (2019)

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:119

Thêm vào BST

Báo xấu

12
lượt xem 5
download

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

Giáo trình Cấu trúc dữ liệu và giải thuật được biên soạn gồm có 6 chương với những nội dung chính sau: Chương I: Tổng quan về cấu trúc dữ liệu và giải thuật; Chương II: Đệ quy và giải thuật đệ quy; Chương III: Tìm kiếm; Chương IV: Các phương pháp sắp xếp cơ bản; Chương V: Danh sách; Chương VI: Cây nhị phân. Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết.

Chủ đề:

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

Lưu

Nội dung Text: Giáo trình Cấu trúc dữ liệu và giải thuật (Ngành/Nghề: Công nghệ thông tin – Trình độ: Cao đẳng) - Trường CĐ Kinh tế - Kỹ thuật Vinatex TP. HCM (2019)

TẬP ĐOÀN DỆT MAY VIỆT NAM TRƢỜNG CAO ĐẲNG KINH TẾ - KỸ THUẬT VINATEX TP.HCM  Giáo Trình CẤU TRÚC DỮ LIỆU và GIẢI THUẬT Nghề: Công nghệ thông tin Trình độ: Cao Đẳng (Ban hành theo Quyết định số: ngày tháng năm của trường Cao đẳng Kinh tế - Kỹ thuật Vinatex Tp.HCM) TP.HỒ CHÍ MINH, THÁNG 03 NĂM 2019
Tuyên bố bản quyền Giáo trình này sử dụng làm tài liệu giảng dạy lƣu hành nội bộ trong trƣờng Cao đẳng Kinh tế - Kỹ thuật Vinatex Tp.HCM Cao đẳng Kinh tế - Kỹ thuật Vinatex Tp.HCM không sử dụng và không cho phép bất kỳ cá nhân hay tổ chức nào sử dụng giáo trình này với mục đích kinh doanh. Mọi trích dẫn, sử dụng giáo trình này với mục đích khác hay ở nơi khác đều phải đƣợc sự đồng ý bằng văn bản của Cao đẳng Kinh tế - Kỹ thuật Vinatex Tp.HCM
LỜI NÓI ĐẦU Tài liệu này dùng cho học sinh hệ Trung cấp và sinh viên hệ Cao đẳng ngành công nghệ thông tin học tập và nghiêm cứu về “Cấu trúc dữ liệu và giải thuật” Tài liệu gồm các nội dung chisng sau: Chƣơng 1: Tổng quan về cấu trúc dữ liệu và giải thuật, các tiêu chuẩn danh gia cấu trúc dữ liệu ,phản ánh đúng thực tếp, phù hợp với các thao tác trên đó, tiết kiệm tài nguyên hệ thống. Kiểu dữ liệu, kiểu dữ liệu cơ bản, các kiểu dữ liệu có cấu trúc, kiểu chuỗi ký tự, kiểu mảng, kiểu union, kiểu mẫu tin (cấu trúc), kiểu con trỏ, kiểu tập tin, mối quan hệ giữa cấu trúc dữ liệu và giải thuật. Chƣơng 2: ệ quy và giải thuật đệ quy, khái niệm đệ quy, thuật toán đệ quy và các chƣơng trình đệ quy, giải thuật đệ quy, các chƣơng trình đệ quy. Các bài toán đệ quy căn bản, hàm tính giai thừa, dãy số fibonacci. Chƣơng 3: Tìm kiếm, tìm kiếm tuyến tính,tìm kiếm nhị phân, giải thuật, cài đặt, đánh giá giải. Chƣơng 4: Các phƣơng pháp sắp xếp cơ bản, định nghĩa bài toán sắp xếp, phƣơng pháp chọn (Selection Sort), chèn (Insertion Sort), đổi chỗ (Interchange Sort), nổi bọt (Bubble Sort), sắp xếp nhanh Quick Sort, giải thuật phân hoạch dãy al, al+1, ., ar thành 2 dãy con, giải thuật phân hoạch dãy sắp xếp dãy al, al+1, ., ar, cài đánh giá giải thuật Chƣơng 5: Danh sách, danh sách liên kết (Xâu liên kết), định nghiã, biểu diễn Xâu liên kết, danh sách liên kết đơn (Xâu đơn), khai báo xâu liên kết đơn, các thao tác trên xâu liên kết đơn, loại bỏ một phần tủ trong xâu, duyệt xâu, sắp thứ tự Xâu, thuật Toán QuickSort, ngăn xếp – stack,cài đặt ngăn xếp bằng xâu đơn, cài đặt ngăn xếp bằng mảng và các thao tác, ứng dụng ngăn xếp trong xử lý biểu thức hậu tố. Hàng đợi – Queue, khái niệm, cài đặt hàng đợi bằng xâu liên kết, cài đặt hàng đợi bằng mảng. Chƣơng 6: Cây nhị phân, định nghĩa và các khái niệm cơ bản, định nghĩa cây, các khái niệm khác, cây nhị phân, định nghĩa, vài tính chất của cây nhị phân, biểu diễn cây nhị phân, duyệt cây nhị phân, định nghĩa, các thuật toán duyệt cây nhị phân, cài đặt thuật toán duyệt qua cây nhị phân LNR, cài đặt cây nhị phân. Cây tìm kiếm nhị phân (Binary Search Trees), định nghĩa, cài đặt cây tìm kiếm nhị phân, tìm kiếm một phần tử trên cây BST, chèn một phần tử vào cây BST, xây dựng cây BST, phƣơng pháp sắp xếp bằng cây BST, xóa một phần tử khỏi cây BST, hủy cây nhị phân. Tài liệu không chỉ đề cập đến những vấn đề cơ sở lý luận mà còn trình bày một số kỹ năng, kinh nghiệm cần thiết để thiết kế và cài đặt các mạng máy tính. Hy vọng sẽ có ích cho các bạn học sinh sinh viên và những ngƣời muốn xây dựng các hệ thống tin học ứng dụng phục vụ cho sản xuất, quản lý trong các doanh nghiệp. Có thể còn nhiều thiếu sót trong trình bày và biên soạn do khả năng, trình độ, nhƣng ngƣời biên soạn mạnh dạn giới thiệu tài liệu này và mong nhận đƣợc sự góp ý của bạn đọc.
CHƢƠNG TRÌNH MÔN HỌC ....................................................................................................... 7 I. Vị trí, tính chất môn học: ...................................................................................................... 7 II. Mục tiêu môn học: .............................................................................................................. 7 III. Nội dung môn học: ............................................................................................................ 7 Chương 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT ................................... 8 I. CÁC TIÊU CHUẨN DANH GIA CẤU TRÚC DỮ LIỆU ...................................................... 8 1. Phản ánh đúng thực tế :........................................................................................................ 8 2. Phù hợp với các thao tác trên đó: ......................................................................................... 8 3. Tiết kiệm tài nguyên hệ thống: ............................................................................................ 9 II. KIỂU DỮ LIỆU ...................................................................................................................... 9 III. KIỂU DỮ LIỆU CƠ BẢN ................................................................................................... 10 IV. CÁC KIỂU DỮ LIỆU CÓ CẤU TRÚC .............................................................................. 11 1. Kiểu chuỗi ký tự ................................................................................................................ 11 2. Kiểu mảng .......................................................................................................................... 12 3. Kiểu union.......................................................................................................................... 13 4. Kiểu mẫu tin (cấu trúc) ...................................................................................................... 14 5. Kiểu con trỏ ....................................................................................................................... 18 6. Kiểu tập tin......................................................................................................................... 32 7. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật ............................................................... 42 Chương 2: Ệ QUY V GIẢI THUẬT Ệ QUY ....................................................................... 44 I. KHAI NIỆM DỆ QUI ............................................................................................................ 44 II. THUẬT TOÁN Ệ QUI....................................................................................................... 44 III. HIỆU LỰC CỦA Ệ QUI ................................................................................................... 46 1. Ƣu nhƣợc điểm .................................................................................................................. 47 2. Phân loại ............................................................................................................................ 48 III. CÁC B I TOÁN Ệ QUY CĂN BẢN .............................................................................. 51 1. Hàm tính giai thừa ............................................................................................................. 51 2. Dãy số Fibonacci ............................................................................................................... 52 Chương 3: TÌM I M................................................................................................................... 53 I. TIM KI M TUY N TINH .................................................................................................... 53 1. Giải thuật............................................................................................................................ 53 2. Cài đặt ................................................................................................................................ 54 3. Ðánh giá giải thuật ............................................................................................................. 55 II. TÌM KI M NHỊ PHÂN ........................................................................................................ 55 1. Giải thuật............................................................................................................................ 55 2. Cài đặt ................................................................................................................................ 56 3. Ðánh giá giải thuật ............................................................................................................. 57
Chương 4: CÁC PHƢƠNG PHÁP SẮP X P CƠ BẢN .............................................................. 58 I. PHƢƠNG PHÁP CHỌN TRỰC TI P (SELECTION SORT) .............................................. 58 1. Giải thuật............................................................................................................................ 58 2. Ví dụ .................................................................................................................................. 58 3. Cài đặt ................................................................................................................................ 59 4. Ðánh giá giải thuật ............................................................................................................. 60 II. PHƢƠNG PHÁP CHÈN TRỰC TI P (INSERTION SORT) ............................................. 60 1. Giải thuật............................................................................................................................ 60 2. Ví dụ .................................................................................................................................. 61 3. Cài đặt ................................................................................................................................ 62 4. ánh giá giải thuật ............................................................................................................. 63 III. PHƢƠNG PHÁP ỔI CHỖ TRỰC TI P (INTERCHANGE SORT) ............................... 63 1. Giải thuật............................................................................................................................ 63 2. Ví dụ : ................................................................................................................................ 64 3. Cài đặt ................................................................................................................................ 67 4. Ðánh giá giải thuật ............................................................................................................. 67 IV. PHƢƠNG PHÁP NỔI BỌT (BUBBLE SORT) ................................................................. 68 1. Giải thuật............................................................................................................................ 68 2. Ví dụ .................................................................................................................................. 68 3. Cài đặt ................................................................................................................................ 71 4. Ðánh giá giải thuật ............................................................................................................. 71 Nhận xét ......................................................................................................................................... 71 V. PHƢƠNG PHÁP QUIC SORT......................................................................................... 71 1. Giải thuật phân hoạch dãy al, al+1, ., ar thành 2 dãy con: ................................................... 72 2. Giải thuật phân hoạch dãy sắp xếp dãy al, al+1, ., ar: .......................................................... 72 3. Cài đặt ................................................................................................................................ 74 4. Ðánh giá giải thuật ............................................................................................................. 75 Chương 5: DANH SÁCH .............................................................................................................. 76 I. DANH SÁCH LIÊN K T (XÂU LIÊN K T ) ...................................................................... 76 1. ịnh nghiã: ........................................................................................................................ 76 2. Biểu diễn Xâu liên kết: ...................................................................................................... 76 II. DANH SÁCH LIÊN K T ƠN (XÂU ƠN) ..................................................................... 77 1. Khai báo xâu liên kết đơn: ................................................................................................. 77 2. Các thao tác trên xâu liên kết đơn:..................................................................................... 78 3. Loại bỏ 1 phần tử trong xâu: .............................................................................................. 83 4. Duyệt xâu: .......................................................................................................................... 87 5. Sắp thứ tự Xâu: .................................................................................................................. 87
6. Thuật Toán QuickSort: ...................................................................................................... 88 III. NGĂN X P - STACK ......................................................................................................... 89 1. ịnh nghiã.......................................................................................................................... 89 2. Cài đặt ngăn xếp bằng xâu đơn .......................................................................................... 89 3. Cài đặt ngăn xếp bằng mảng và các thao tác: .................................................................... 92 4. Ứng dụng ngăn xếp trong xử lý biểu thức hậu tố: ............................................................. 93 IV. H NG ỢI - QUEUE ........................................................................................................ 96 1. Khái niệm ........................................................................................................................... 96 2. Cài đặt hàng đợi bằng xâu liên kết: ................................................................................... 96 3. Cài đặt hàng đợi bằng mảng: ............................................................................................. 97 Chương 6: CÂY NHỊ PHÂN ...................................................................................................... 101 I. ỊNH NGHĨA V CÁC HÁI NIỆM CƠ BẢN ................................................................ 101 1. ịnh nghĩa cây ................................................................................................................. 101 II. CÂY NHỊ PHÂN ................................................................................................................ 103 1. ịnh nghĩa: ...................................................................................................................... 103 2. Vài tính chất của cây nhị phân ......................................................................................... 103 3. Biểu diễn cây nhị phân..................................................................................................... 103 III. DUYỆT CÂY NHỊ PHÂN ................................................................................................ 105 1. ịnh nghĩa: ...................................................................................................................... 105 2. Các thuật toán duyệt cây nhị phân ................................................................................... 105 3. Cài đặt thuật toán duyệt qua cây nhị phân LNR .............................................................. 106 4. Cài đặt cây nhị phân......................................................................................................... 108 IV. CÂY TÌM KI M NHỊ PHÂN (BINARY SEARCH TREES) .......................................... 110 1. ịnh nghĩa........................................................................................................................ 110 2. Cài đặt cây tìm kiếm nhị phân ......................................................................................... 111 3. Tìm kiếm một phần tử trên cây BST ............................................................................... 112 4. Chèn một phần tử vào cây BST, xây dựng cây BST ....................................................... 113 5. Phƣơng pháp sắp xếp bằng cây BST ............................................................................... 115 6. Xóa một phần tử khỏi cây BST, hủy cây nhị phân .......................................................... 116
CHƢƠNG TRÌNH MÔN HỌC Tên môn học: Cấu trúc dữ liệu và giải thuật Mã môn học: MH 12 Thời gian thực hiện môn học: 75 giờ; (Lý thuyết: 15 giờ; Thực hành, thí nghiệm, thảo luận, bài tập: 55 giờ; Kiểm tra: 5 giờ) I. Vị trí, tính chất môn học: - Vị trí: môn học đƣợc bố trí sau khi ngƣời học học xong môn học: Lập trình căn bản, Cơ sở dữ liệu. - Tính chất: là môn học cơ sở ngành bắt buộc. II. Mục tiêu môn học: - Về kiến thức:  Hiểu đƣợc mối quan hệ giữa cấu trúc dữ liệu và giải thuật.  Phân tích đƣợc các kiểu dữ liệu, giải thuật, sự kết hợp chúng để tạo thành một chƣơng trình máy tính.  Biết cách tổ chức dữ liệu hợp lý, khoa học cho một chƣơng trình đơn giản.  Biết áp dụng thuật toán hợp lý đối với cấu trúc dữ liệu tƣơng thích để giải quyết bài toán thực tế.  Biết và áp dụng đƣợc các phƣơng pháp sắp xếp, tìm kiếm đơn giản. - Về kỹ năng:  ánh giá kỹ năng thực hành của ngƣời học:  Dùng ngôn ngữ lập trình bất kỳ nào đó thể hiện trên máy tính các bài toán cần kiểm nghiệm về: đệ qui, danh sách, cây, đồ thị, sắp xếp, tìm kiếm... - Về năng lực tự chủ và trách nhiệm:  Rèn luyện tƣ duy logic để phân tích, tổng hợp.  Thao tác cẩn thận, tỉ mỉ. III. Nội dung môn học:
Chương 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1. Mục tiêu: - Mô tả đƣợc khái niệm giải thuật, mối quan hệ giữa cấu trúc dữ liệu và giải thuật, đánh giá đƣợc độ phức tạp của giải thuật. - Ghi nhớ đƣợc các kiểu dữ liệu cơ bản, kiểu dữ liệu trừu tƣợng và các cấu trúc dữ liệu cơ bản. 2. Nội dung chƣơng: I. CÁC TIÊU CHUẨN DANH GIA CẤU TRÚC DỮ LIỆU 1. Phản ánh đúng thực tế : ây là tiêu chuẩn quan trọng nhất, quyết định tính đúng đắn của toàn bộ bài toán. Cần xem xét kỹ lƣỡng cũng nhƣ dự trù các trạng thái biến đổi của dữ liệu trong chu trình sống để có thể chọn cấu trúc dữ liệu lƣu trữ thể hiện chính xác đối tƣợng thực tế. Ví dụ: Một số tình huống chọn cấu trúc lƣu trữ sai : - Chọn một biến số nguyên int để lƣu trữ tiền thƣởng bán hàng (đƣợc tính theo công thức tiền thƣởng bán hàng = trị giá hàng * 5%), do vậy sẽ làm tròn mọi giá trị tiền thƣởng gây thiệt hại cho nhân viên bán hàng. Trƣờng hợp này phải sử dụng biến số thực để phản ánh đúng kết quả của công thức tính thực tế. - Trong trƣờng trung học, mỗi lớp có thể nhận tối đa 28 học sinh. Lớp hiện có 20 học sinh, mỗi tháng mỗi học sinh đóng học phí $10. Chọn một biến số nguyên unsigned char ( khả năng lƣu trữ 0 - 255) để lƣu trữ tổng học phí của lớp học trong tháng, nếu xảy ra trƣờng hợp có thêm 6 học sinh đƣợc nhận vào lớp thì giá trị tổng học phí thu đƣợc là $260, vƣợt khỏi khả năng lƣu trữ của biến đã chọn, gây ra tình trạng tràn, sai lệch. 2. Phù hợp với các thao tác trên đó: Tiêu chuẩn này giúp tăng tính hiệu quả của đề án: việc phát triển các thuật toán đơn giản, tự nhiên hơn; chƣơng trình đạt hiệu quả cao hơn về tốc độ xử lý. Ví dụ: Một tình huống chọn cấu trúc lƣu trữ không phù hợp: Cần xây dựng một chƣơng trình soạn thảo văn bản, các thao tác xử lý thƣờng xảy ra là chèn, xoá sửa các ký tự trên văn bản. Trong thời gian xử lý văn bản, nếu chọn cấu trúc lƣu trữ văn bản trực tiếp lên tập tin thì sẽ gây khó khăn khi xây dựng các giải thuật cập nhật văn bản và làm chậm tốc độ xử lý của chƣơng trình vì phải làm việc trên bộ nhớ ngoài. Trƣờng hợp này nên tìm một cấu trúc dữ liệu có thể tổ chức ở bộ nhớ trong để lƣu trữ văn bản suốt thời gian soạn thảo.
Lưu ý: ối với mỗi ứng dụng , cần chú ý đến thao tác nào đƣợc sử dụng nhiều nhất để lựa chọn cấu trúc dữ liệu cho thích hợp. 3. Tiết kiệm tài nguyên hệ thống: Cấu trúc dữ liệu chỉ nên sử dụng tài nguyên hệ thống vừa đủ để đảm nhiệm đƣợc chức năng của nó. Thông thƣờng có 2 loại tài nguyên cần lƣu tâm nhất : CPU và bộ nhớ.Tiêu chuẩn này nên cân nhắc tùy vào tình huống cụ thể khi thực hiện đề án . Nếu tổ chức sử dụng đề án cần có những xử lý nhanh thì khi chọn cấu trúc dữ liệu yếu tố tiết kiệm thời gian xử lý phải đặt nặng hơn tiêu chuẩn sử dụng tối ƣu bộ nhớ, và ngƣợc lại. Ví dụ: Một số tình huống chọn cấu trúc lƣu trữ lãng phí: - Sử dụng biến int (2 bytes) để lƣu trữ một giá trị cho biết tháng hiện hành . Biết rằng tháng chỉ có thể nhận các giá trị từ 1-12, nên chỉ cần sử dụng kiểu char (1 byte) là đủ. - ể lƣu trữ danh sách học viên trong một lớp, sử dụng mảng 50 phần tử (giới hạn số học viên trong lớp tối đa là 50). Nếu số lƣợng học viên thật sự ít hơn 50, thì gây lãng phí. Trƣờng hợp này cần có một cấu trúc dữ liệu linh động hơn mảng- ví dụ xâu liên kết - sẽ đƣợc đề cập trong chƣơng sau II. KIỂU DỮ LIỆU iểu dữ liệu T đƣợc xác định bởi một bộ < V, O > , với : V (Value): tập các giá trị hợp lệ mà một đối tƣợng kiểu T có thể lƣu trữ O (Operation): tập các thao tác xử lý có thể thi hành trên đối tƣợng kiểu T. Ví du: Giả sử có kiểu dữ liệu mẫu tự = < Vc , Oc > với Vc = { a-z,A-Z} Oc = { lấy mã ASCII của ký tự, biến đổi ký tự thƣờng thành ký tự hoa…} Giả sử có kiểu dữ liệu số nguyên = < Vi, Oi > với Vi = { -32768..32767} Oi = { +, -, *, /, %} Nhƣ vậy, muốn sử dụng một kiểu dữ liệu cần nắm vững cả nội dung dữ liệu đƣợc phép lƣu trữ và các xử lý tác động trên đó. Các thuộc tính của 1 DL bao gồm: Tên KDL Miền giá trị ích thƣớc lƣu trữ
Tập các toán tử tác động lên DL III. KIỂU DỮ LIỆU CƠ BẢN Các loại dữ liệu cơ bản thƣờng là các loại dữ liệu đơn giản, không có cấu trúc nhƣ số nguyên, số thực, các ký tự, các giá trị logic ... Các loại dữ liệu này, do tính thông dụng và đơn giản của mình, thƣờng đƣợc các ngôn ngữ lập trình (NNLT) cấp cao xây dựng sẵn nhƣ một thành phần của ngôn ngữ để giảm nhẹ công việc cho ngƣời lập trình. Chính vì vậy đôi khi ngƣời ta còn gọi chúng là các kiểu dữ liệu định sẵn. Thông thƣờng, các kiểu dữ liệu cơ bản bao gồm : Kiểu có thứ tự rời rạc: số nguyên, ký tự, logic, liệt kê, miền con … Kiểu không rời rạc: số thực Tùy ngôn ngữ lập trình, các kiểu dữ liệu định nghĩa sẵn có thể khác nhau đôi chút. Với ngôn ngữ C, các kiểu dữ liệu này chỉ gồm số nguyên, số thực, ký tự. Và theo quan điểm của C, kiểu ký tự thực chất cũng là kiểu số nguyên về mặt lƣu trữ, chỉ khác về cách sử dụng. Ngoài ra, giá trị logic ÚNG (TRUE) và giá trị logic SAI (FALSE) đƣợc biểu diễn trong C nhƣ là các giá trị nguyên khác zero và zero. Các kiểu dữ liệu định sẵn trong C gồm các kiểu sau: Tên kiểu Kích thƣớc Miền giá trị Ghi chú Có thể dùng nhƣ số nguyên 1 byte Char 01 byte -128 đến 127 có dấu hoặc kiểu ký tự Unsign char 01 byte 0 đến 255 Số nguyên 1 byte không dấu Int 02 byte -32738 đến 32767 Số nguyên 2 byte Unsign int 02 byte 0 đến 65535 Có thể gọi tắt là unsign Long 04 byte -232 đến 231 -1 Unsign long 04 byte 0 đến 232-1 Giới hạn chỉ trị tuyệt đối.Các giá trị < 3.4E-38 đƣợc coi = 0. Tuy Float 04 byte 3.4E-38 đến 3.4E38 nhiên kiểu float chỉ có 7 chữ số có nghĩa.
Double 08 byte 1.7E-308 đến 1.7E308 Long double 10 byte 3.4E-4932 đến 1.1E4932 Nhƣ vậy, trong C xét cho cùng chỉ có 2 loại dữ liệu cơ bản là số nguyên và số thực. Tức là chỉ có dữ liệu số. Hơn nữa các số nguyên trong C có thể đƣợc thể hiện trong 3 hệ cơ số là hệ thập phân, hệ thập lục phân và hệ bát phân. Các kiểu cơ sở rất đơn giản và không thể hiện rõ sự tổ chức dữ liệu trong một cấu trúc, thƣờng chỉ đƣợc sử dụng làm nền để xây dựng các kiểu dữ liệu phức tạp khác. IV. CÁC KIỂU DỮ LIỆU CÓ CẤU TRÚC Tuy nhiên trong nhiều trƣờng hợp, chỉ với các kiểu dữ liệu cơ sở không đủ để phản ánh tự nhiên và đầy đủ bản chất của sự vật thực tế, dẫn đến nhu cầu phải xây dựng các kiểu dữ liệu mới dựa trên việc tổ chức, liên kết các thành phần dữ liệu có kiểu dữ liệu đã đƣợc định nghĩa. Những kiểu dữ liệu đƣợc xây dựng nhƣ thế gọi là kiểu dữ liệu có cấu trúc. Một số kiểu dữ liệu có cấu trúc cơ bản : 1. Kiểu chuỗi ký tự Chuỗi ký tự là một trong các kiểu dữ liệu có cấu trúc đơn giản nhất và thƣờng các ngôn ngữ lập trình đều định nghĩa nó nhƣ một kiểu cơ bản. Do tính thông dụng của kiểu chuỗi ký tự các ngôn ngữ lập trình luôn cung cấp sẵn một bộ các hàm thƣ viện các xử lý trên kiểu dữ liệu này. Các hàm này đƣợc đặt trong thƣ viện string.lib của C. Chuỗi ký tự trong C đƣợc cấu trúc nhƣ một chuỗi 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). Nhƣ vậy, giới hạn chiều dài của một chuỗi ký tự trong C là 1 Segment (tối đa chứa 65535 ký tự), ký tự đầu tiên đƣợc đánh số là ký tự thứ 0. Ta có thể khai báo một chuỗi ký tự theo một số cách sau đây: char S[10]; // hai 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) char S[]="ABC"; // hai báo một chuỗi ký tự S có chiều // dài bằng chiều dài của chuỗi "ABC" // và giá trị khởi đầu của S là "ABC" char *S ="ABC"; //Giống cách khai báo trên. Trong ví dụ trên ta cũng thấy đƣợc một hằng chuỗi ký tự đƣợc thể hiện bằng một chuỗi ký tự đặt trong cặp ngoặc kép “”. Các thao tác trên chuỗi ký tự rất đa dạng. Sau đây là một số thao tác thông dụng:
So sánh 2 chuỗi: strcmp Sao chép chuỗi: strcpy ộ dài chuỗi: strlen iểm tra 1 chuỗi nằm trong chuỗi kia: strstr Cắt 1 từ ra khỏi 1 chuỗi: strtok ổi 1 số ra chuỗi: itoa ổi 1 chuỗi ra số: atoi, atof, ... Nhập một chuỗi: gets Xuất một chuỗi: puts 2. Kiểu mảng iểu dữ liệu mảng là kiểu dữ liệu trong đó mỗi phần tử của nó là một tập hợp có thứ tự các giá trị có cùng cấu trúc đƣợc lƣu trữ liên tiếp nhau trong bộ nhớ. Mảng có thể một chiều hay nhiều chiều. Một dãy số chính là hình tƣợng của mảng 1 chiều, ma trận là hình tƣợng của mảng 2 chiều. Một điều đáng lƣu ý là mảng 2 chiều có thể coi là mảng một chiều trong đó mỗi phần tử của nó là 1 mảng một chiều. Tƣơng tự nhƣ vậy, 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. Mảng 1 chiều đƣợc khai báo nhƣ sau: []; Ví dụ: để khai báo một biến có tên a là một mảng nguyên 1 chiều có tối đa 100 phần tử ta phải khai báo nhƣ sau: int a[100]; Ta cũng có thể vừa khai báo vừa gán giá trị khởi động cho một mảng nhƣ sau: int a[5] = {1, 7, -3, 8, 19}; Trong trƣờng hợp này C cho phép ta khai báo một cách tiện lợi hơn int a[] = {1, 7, -3, 8, 19}; Nhƣ ta thấy, ta không cần chỉ ra số lƣợng phần tử cụ thể trong khai báo. Trình biên dịch của C sẽ tự động làm việc này cho chúng ta. Tƣơng tự ta có thể khai báo một mảng 2 chiều hay nhiều chiều theo cú pháp sau: < iểu dữ liệu> [][]...; Ví dụ, ta có thể khai báo:
int a[100][150]; hay int a[][]={{1, 7, -3, 8, 19}, {4, 5, 2, 8, 9}, {21, -7, 45, -3, 4}}; (mảng a sẽ có kích thƣớc là 3x5). 3. Kiểu union Kiểu union là một dạng cấu trúc dữ liệu đặc biệt của ngôn ngữ C. Nó rất giống với kiểu struct. Chỉ khác một điều, trong kiểu union, các trƣờng đƣợc phép dùng chung một vùng nhớ. Hay nói cách khác, cùng một vùng nhớ ta có thể truy xuất dƣới các dạng khác nhau. Khai báo tổng quát của kiểu union nhƣ sau: typedef union { < DL> ; < DL> ; ……… }[]; Ví dụ, ta có thể định nghĩa kiểu số sau: typedef union tagNumber { int i; long l; }Number; Việc truy xuất đến một trƣờng trong union đƣợc thực hiện hoàn toàn giống nhƣ trong struct. Giả sử có biến n kiểu Number. hi đó, n.i cho ta một số kiểu int còn n.l cho ta một số kiểu long, nhƣng cả hai đều dùng chung một vùng nhớ. Vì vậy, khi ta gán n.l = 0xfd03; thì giá trị của n.i cũng bị thay đổi (n.i sẽ bằng 3);
Việc dùng kiểu union rất có lợi khi cần khai báo các cấu trúc dữ liệu mà nội dung của nó thay đổi tùy trạng thái. Ví dụ để mô tả các thông tin về một con ngƣời ta có thể khai báo một kiểu dữ liệu nhƣ sau: struct tag Nguoi { char HoTen[35]; int NamSinh; char NoiSinh[40]; char GioiTinh; //0: Nữ, 1: Nam char DiaChi[50]; char Ttgd; //0: hông có gia đình, 1: Có gia đình union { char tenVo[35]; char tenChong[35]; } }Nguoi; Tùy theo ngƣời mà ta đang xét là nam hay nữ ta sẽ truy xuất thông tin qua trƣờng có tên tenVo hay tenChong. 4. Kiểu mẫu tin (cấu trúc) Nếu kiểu dữ liệu mảng là kiểu dữ liệu trong đó mỗi phần tử của nó là một tập hợp có thứ tự các giá trị có cùng cấu trúc đƣợc lƣu trữ liên tiếp nhau trong bộ nhớ thì mẫu tin là kiểu dữ liệu mà trong đó mỗi phần tử của nó là tập hợp các giá trị có thể khác cấu trúc. iểu mẫu tin cho phép chúng ta mô tả các đối tƣợng có cấu trúc phức tạp. hai báo tổng quát của kiểu struct nhƣ sau: typedef struct { < DL> ; ; … }[];
Ví dụ để mô tả các thông tin về một con ngƣời ta có thể khai báo một kiểu dữ liệu nhƣ sau: struct tag Nguoi { char HoTen[35]; int NamSinh; char NoiSinh[40]; char GioiTinh; //0: Nữ, 1: Nam char DiaChi[50]; char Ttgd; //0: hông có gia đình, 1: Có gia đình }Nguoi; iểu mẫu tin bổ sung những thiếu sót của kiểu mảng, giúp ta có khả năng thể hiện các đối tƣợng đa dạng của thể giới thực vào trong máy tính một cách dễ dàng và chính xác hơn. 4.1. Các thao tác trên biến cấu trúc: o Truy xuất đến 1 thành phần của biến cấu trúc: Tên biến.tên thành phần Trong C, địa chỉ của một thành phần trong biến cấu trúc đƣợc xác định bởi phép toán lấy địa chỉ: &tên biến.tên thành phần o Gán 2 biến cấu trúc cho nhau 4.2. Hàm và kiểu mẫu tin: * ối của hàm có thể là: - 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 giá trị mẫu tin - Con trỏ mẫu tin: khi đó tham số thực là địa chỉ của biến cấu trúc. * Hàm có thể trả về: - Giá trị mẫu tin: nguoi tênhàm(...) - Con trỏ mẫu tin: nguoi *tênhàm(....) Ví dụ: Nhập và in danh sách thí sinh theo thứ tự tên và họ # include # include # include
# include typedef struct { int ngay, thang, nam; } date; typedef struct { int sbd; char ho[25],ten[7]; date ngaysinh; float toan,ly,hoa; int phongthi; }hoso; hoso thisinh[100]; int n; void NhapHoso (hoso ts[], int &n) { int i=0; hoso hs; printf ("\nNhap Ho so thi sinh \"Ho bang rong de ket thuc\""); do { hs.sbd = n+1; printf ("\nNhap ho so cho thi sinh: %3d",hs.sbd); printf ("\nHo : "); gets(hs.ho); if (hs.ho[0]=='\0') break; printf ("Ten: "); gets(hs.ten); printf ("Ngay sinh: "); scanf ("%d/%d/%d%*c",&hs.ngaysinh.ngay,&hs.ngaysinh.thang, &hs.ngaysinh.nam); printf ("Diem Toan: "); scanf("%f%*c",&hs.toan); printf ("Diem Ly: "); scanf("%f%*c",&hs.ly);
printf ("Diem Hoa: "); scanf("%f%*c",&hs.hoa); printf ("Phong thi: "); scanf("%d%*c",&hs.phongthi); ts[i] = hs; n++; i++; } while (iten,((hoso*)q)->ten); if (kq == 0) return strcmp(((hoso*)p)->ho,((hoso*)q)->ho); return kq; } void InKQ (hoso ts[], int n) { int i; qsort (ts,n,sizeof(ts[0]),sosanh); printf ("\n%-4s %-25s %-10s %-4s %-4s %-4s %-5s","SBD", "Ho Ten","Ngay sinh","Toan","Ly","Hoa","Phong"); for (i=0;i
hs.ho[0]= hs.ten[0] = 0; for (i=0; i
o Chỉ phát sinh trong quá trình thực hiện chƣơng trình chứ không phát sinh lúc bắt đầu chƣơng trình. o Khi chạy chƣơng trình, kích thƣớc của biến, vùng nhớ và địa chỉ vùng nhớ đƣợc cấp phát cho biến có thể thay đổi. o Sau khi sử dụng xong có thể giải phóng để tiết kiệm chỗ trong bộ nhớ. Tuy nhiên các biến động không có địa chỉ nhất định nên ta không thể truy cập đến chúng đƣợc. Vì thế, ngôn ngữ C lại cung cấp cho ta một loại biến đặc biệt nữa để khắc phục tình trạng này, đó là biến con trỏ (pointer) với các đặc điểm: o Biến con trỏ không chứa dữ liệu mà chỉ chứa địa chỉ của dữ liệu hay chứa địa chỉ của ô nhớ chứa dữ liệu. o ích thƣớc của biến con trỏ không phụ thuộc vào kiểu dữ liệu, luôn có kích thƣớc cố định là 2 byte. 5.2. hai áo và dụng iến con tr 5.2.1. Khai báo biến con trỏ Cú pháp: * Ý nghĩa: Khai báo một biến có tên là Tên con trỏ dùng để chứa địa chỉ của các biến có kiểu Kiểu. Ví dụ 1: Khai báo 2 biến a,b có kiểu int và 2 biến pa, pb là 2 biến con trỏ kiểu int. int a, b, *pa, *pb; Ví dụ 2: Khai báo biến f kiểu float và biến pf là con trỏ float float f, *pf; Ghi chú: Nếu chƣa muốn khai báo kiểu dữ liệu mà con trỏ ptr đang chỉ đến, ta sử dụng: void *ptr; Sau đó, nếu ta muốn con trỏ ptr chỉ đến kiểu dữ liệu gì cũng đƣợc. Tác dụng của khai báo này là chỉ dành ra 2 bytes trong bộ nhớ để cấp phát cho biến con trỏ ptr. 5.2.2. Các thao tác trên con trỏ a/ Gán địa chỉ của biến cho biến con trỏ Toán tử & dùng để định vị con trỏ đến địa chỉ của một biến đang làm việc. Cú pháp: = & Giải thích: Ta gán địa chỉ của biến Tên biến cho con trỏ Tên biến con trỏ. Ví dụ: Gán địa chỉ của biến a cho con trỏ pa, gán địa chỉ của biến b cho con trỏ pb. pa=&a; pb=&b;
Lúc này, hình ảnh của các biến trong bộ nhớ đƣợc mô tả: Lư ý: hi gán địa chỉ của biến tĩnh cho con trỏ cần phải lƣu ý kiểu dữ liệu của chúng. Ví dụ sau đây không đúng do không tƣơng thích kiểu: int Bien_Nguyen; float *Con_Tro_Thuc; ... Con_Tro_Thuc=&Bien_Nguyen; Phép gán ở đây là sai vì Con_Tro_Thuc là một con trỏ kiểu float (nó chỉ có thể chứa đƣợc địa chỉ của biến kiểu float); trong khi đó, Bien_Nguyen có kiểu int. b/ Nội dung của ô nhớ con trỏ chỉ tới ể truy cập đến nội dung của ô nhớ mà con trỏ chỉ tới, ta sử dụng cú pháp: * Với cách truy cập này thì * có thể coi là một biến có kiểu đƣợc mô tả trong phần khai báo biến con trỏ. Ví dụ: Ví dụ sau đây cho phép khai báo, gán địa chỉ cũng nhƣ lấy nội dung vùng nhớ của biến con trỏ: int x=100; int *ptr; ptr=&x; int y= *ptr; Lư ý: hi gán địa chỉ của một biến cho một biến con trỏ, mọi sự thay đổi trên nội dung ô nhớ con trỏ chỉ tới sẽ làm giá trị của biến thay đổi theo (thực chất nội dung ô nhớ và biến chỉ là một). Ví dụ: oạn chƣơng trình sau thấy rõ sự thay đổi này :