zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Ngôn ngữ lập trình C - Chương 7 - Bài 1. Dynamic allocation, Single linked list

Chia sẻ: Nguyen Duc Anh | Ngày: | Loại File: PDF | Số trang:15

Báo xấu

151
lượt xem 33
download

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

Ví dụ - Mảng có kích thước cố định, lưu trữ một số lượng phần tử đã biết trước. - Kích thước mảng đã biết ở thời điểm dịch, không thể thay đổi - Bạn có luôn luôn biết số phần tử thực sự mà một mảng cần lưu?

Chủ đề:

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

Lưu

Nội dung Text: Ngôn ngữ lập trình C - Chương 7 - Bài 1. Dynamic allocation, Single linked list

4/25/2010 Chương 7. Bài 1. Dynamic allocation, Single linked list ĐỖ BÁ LÂM ViỆN CNTT&TT, TRƯỜNG ĐHBK HÀ NỘI Nội dung  1. Cấp phát bộ nhớ động (Dynamic Allocation)  1.1. Khái niệm  1.2. Hàm malloc  1.3. Hàm free  2. Single linked list  2.1. Tổng quan  2.2. Các thao tác cơ bản  2.3. Bài tập 2 1.1. Khái niệm  Cấp phát động (dynamic) ? cố định (fix)  Ví dụ  Mảng có kích thước cố định, lưu trữ một số lượng phần tử đã biết trước.  Kích thước mảng đã biết ở thời điểm dịch, không thể thay đổi  Bạn có luôn luôn biết số phần tử thực sự mà một mảng cần lưu? => Cấp phát động >< cấp phát cố định 3 1
4/25/2010 1.2. Hàm malloc Cú pháp void * malloc(unsigned int nbytes);  Cấp phát động nBytes trong bộ nhớ  Thành công: trả về con trỏ - trỏ tới vùng nhớ được cấp phát.  Không thành công: NULL  Luôn kiểm tra xem việc cấp phát có thành công hay không  Thư viện stdlib.h 4 1.2. Hàm malloc  Ép kiểu (chuyển kiểu) – casing  Hàm malloc void * malloc(unsigned int nbytes);  Ép sang một kiểu khác bởi malloc trả về void*  Ví dụ p = (int *) malloc (n*sizeof(int)); cấp phát một vùng nhớ chứa n số int 5 1.3. Hàm free  free()  void free(void *);  Giải phóng vùng nhớ được cấp phát  Ví dụ:  free(ptr);  Nếu ptr không trỏ tới vùng nhớ nào được cấp phát bởi malloc sẽ gây lỗi run-time  Luôn giải phóng vùng nhớ nếu không sử dụng nữa 6 2
4/25/2010 Ví dụ  Ví dụ 1. Nhập từ bàn phím một mảng các số nguyên với số phần tử cũng được nhập từ bàn phím. Hiển thị các phần tử trong mảng  Ví dụ 2. Xây dựng hàm với tham số hai xâu kí tự. Hàm trả về một con trỏ trỏ tới xâu ghép từ hai xâu trên. 7 Hướng dẫn  Ví dụ 1.  scanf(“%d”,&n);  p = (int *) malloc(sizeof(int) * n);  Ví dụ 2.  n1 = strlen (str1);  n2 = strlen (str2);  str = (char *) malloc(sizeof(char) * (n1+n2+1));  strcpy 8 2. Danh sách liên kết đơn  2.1. Tổng quan  2.1.1. Khái niệm  2.1.2. Thành phần của một nút  2.1.3. Con trỏ đầu - head 9 3
4/25/2010 2. Danh sách liên kết đơn  2.2. Các thao tác cơ bản  2.2.1. Khai báo danh sách  2.2.2. Cấp phát bộ nhớ cho một nút  2.2.3. Thêm một nút vào sau nút hiện tại  2.2.4. Loại bỏ nút đầu tiên trong danh sách  2.2.5. Duyệt danh sách  2.2.6. Giải phóng danh sách 10 2.1.1. Khái niệm  Là một cấu trúc dữ liệu xác định bao gồm một tập tuần tự các “nút” (node) chứa dữ liệu  Trong mỗi nút có một liên kết đến nút kế tiếp ... „A‟ „b‟ „C‟ „Z‟ X 1 nút 11 2.1.2. Thành phần của một nút  Mỗi nút gồm có:  Thành phần dữ liệu - data: Chứa dữ liệu của nút (số nguyên, số thực, ký tự hay cấu trúc...)  Thành phần liên kết – next: Con trỏ trỏ đến nút kế tiếp trong danh sách „C‟ data: Con trỏ Ký tự „C‟ 12 4
4/25/2010 2.1.2. Thành phần của một nút  Đặc biệt:  Đối với nút cuối cùng trong danh sách: • next = NULL ... „A‟ „b‟ „C‟ „Z‟ X next = NULL 13 2.1.3. Con trỏ đầu - head  Để xác định một danh sách liên kết đơn ta dùng một con trỏ trỏ đến nút đầu tiên trong danh sách – Con trỏ đầu (head) ... „A‟ „b‟ „C‟ „Z‟ X head  Khi danh sách rỗng: head = NULL 14 2.2.1. Khai báo danh sách  B1. Định nghĩa cấu trúc một “nút”: struct node { data; // dataType: int, char… dataType struct node *next; };  B2. Khai báo con trỏ đầu: struct node *head;  B3. Khởi tạo danh sách: head = NULL; 15 5
4/25/2010 2.2.2. Cấp phát bộ nhớ cho nút  Chúng ta cần cấp phát bộ nhớ cho mỗi nút thông qua con trỏ struct node *new_item; new_item = (struct node*) malloc(sizeof(struct node)); new_item->element = …; new_item->next = NULL; 16 2.2.3. Thêm một nút vào sau nút hiện tại  head: trỏ tới đầu danh sách  NULL: giá trị của con trỏ, cho biết ở đuôi của danh sách  cur: trỏ tới nút đang được xem xét cur head (or root) NULL 17 2.2.3. Thêm một nút vào sau nút hiện tại tạo new_item; new_item → next = cur → next; cur → next = new_item; cur= cur → next; // sai cur → next = new_item; new_item → next = cur → next; cur= cur → next; cur head … new_item 18 6
4/25/2010 2.2.3. Thêm một nút vào sau nút hiện tại //Tạo danh sách new_item = (struct node * ) malloc( sizeof( struct node ) ); new_item → data = …; // khởi tạo giá trị new_item → next = NULL; if ( head == NULL ) { /* Neu danh sach rong*/ head = new_item; cur = head; } else { cur → next = new_item; cur = cur → next; // cur = new_item; } 19 2.2.4. Loại bỏ nút ở đầu danh sách  Nếu danh sách đang rỗng:  Thoát khỏi hàm head  Ngược lại 1 3 5X  Cho con trỏ head trỏ đến phần tử được trỏ tiếp theo  Giải phóng bộ nhớ được cấp phát cho phần tử đầu tiên 20 2.2.4. Loại bỏ nút ở đầu danh sách struct node *p; if (head == NULL) return; //ds rỗng p = head; head = head → next;//ds khong rong free(p); 21 7
4/25/2010 2.2.5. Duyệt danh sách  Giải pháp  Nút cuối cùng trong danh sách có thành phần next là NULL  Duyệt từ nút đầu tiên head, thông qua trường next để xác định nút tiếp theo cho đến khi thu được con trỏ NULL 22 2.2.5. Duyệt danh sách  Thực hiện struct node *p; p = head; while (p != NULL){ //Thao tác với p->data: hiển thị… p = p->next; } 23 2.2.6. Giải phóng danh sách  Giải pháp  Duyệt danh sách từ trái qua phải, loại bỏ từng nút  Mỗi lần duyệt, phải thay đổi lại con trỏ head 24 8
4/25/2010 2.2.6. Giải phóng danh sách to_free = head ; while (to_free != NULL) to_free head { head = head->next; free(to_free); to_free = head; } 25 2.2.6. Giải phóng danh sách to_free = head ; to_free head while (to_free != NULL) { head = head->next; free(to_free); to_free = head; } 26 2.2.6. Giải phóng danh sách while (to_free != NULL) to_free head { head = head ->next; free(to_free); to_free = head; } 27 9
4/25/2010 2.2.6. Giải phóng danh sách while (to_free != NULL) to_free head { head = head->next; free(to_free); to_free = head; } 28 2.2.6. Giải phóng danh sách while (to_free != NULL) to_free head { head = head->next; free(to_free); to_free = head; } 29 2.2.6. Giải phóng danh sách while (to_free != NULL) to_free head { head = head->next; free(to_free); to_free = head; } 30 10
4/25/2010 2.2.6. Giải phóng danh sách while (to_free != NULL) to_free head { head = head ->next; free(to_free); to_free = head; } 31 2.2.6. Giải phóng danh sách while (to_free != NULL) to_free head { head = head->next; free(to_free); to_free = head; } 32 2.2.6. Giải phóng danh sách while (to_free != NULL) to_free head { head = head->next; free(to_free); to_free = head; } 33 11
4/25/2010 2.2.6. Giải phóng danh sách while (to_free != NULL) to_free head { head = head->next; free(to_free); to_free = head; } 34 2.2.6. Giải phóng danh sách while (to_free != NULL) to_free head { head = head->next; free(to_free); to_free = head; } 35 2.2.6. Giải phóng danh sách while (to_free != NULL) to_free head { head = head->next; free(to_free); to_free = head; } 36 12
4/25/2010 2.2.8. Giải phóng danh sách while (to_free != NULL) to_free head { head = head->next; free(to_free); to_free = head; } 37 2.2.8. Giải phóng danh sách while (to_free != NULL) to_free head { head = head->next; free(to_free); to_free = head; } 38 2.2.8. Giải phóng danh sách while (to_free != NULL) to_free head { head = head->next; free(to_free); to_free = head; } 39 13
4/25/2010 2.2.6. Giải phóng danh sách while (to_free != NULL) to_free head { head = head->next; free(to_free); to_free = head; } 40 2.2.6. Giải phóng danh sách while (to_free != NULL) to_free head { head = head->next; free(to_free); to_free = head; } NULL 41 2.2.6. Giải phóng danh sách while (to_free != NULL) to_free head { head = head->next; free(to_free); to_free = head; } NULL 42 14
4/25/2010 3. Bài toán quản lý sinh viên • Thông tin về mỗi sinh viên bao gồm: – MSSV: xâu ký tự, tối đa 8 ký tự – HoTen: xâu ký tự, tối đa 30 ký tự – DiemTB: float • Tổ chức thông tin SV dưới dạng danh sách liên kết: – Thêm thông tin sinh viên vào danh sách cho đến khi MSSV là xâu rỗng – Viết hàm hiển thị thông tin tất cả các SV trong danh sách – Giải phóng danh sách 43 Mở rộng  Hàm chèn nút vào đầu danh sách  Hàm xóa một nút theo MSSV được nhập từ bàn phím … 44 Thảo luận 45 15

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.