tailieunhanh - Bài giảng Ngôn ngữ lập trình C - Chương 8: Danh sách móc nối

Mời các bạn tham khảo "Bài giảng Ngôn ngữ lập trình C - Chương 8: Danh sách móc nối" để nắm bắt được những nội dung về danh sách liên kết đơn, stack và queue. Đây là tài liệu tham khảo hữu ích dành cho các bạn đang học và nghiên cứu về Công nghệ thông tin. | CHƯƠNG VIII DANH SÁCH MÓC NỐI Ta thương sử dụng mảng cấu trúc để xử lý với nhóm dữ liệu. Đây là một cách tiếp cận đúng khi ta biết trước chính xác số các cấu trúc cần có. Tuy nhiên, khi con số này không rõ ràng, mãng sẽ trở nên khá tốn kém vì chúng phải được cấp phát đủ bộ nhớ để hoạt động. Bố nhớ này được đăng ký và sẽ không dành cho nhứng tác vụ khác ngay cả khi ta chỉ dùng một sô nhỏ các phần tử mảng. Phương hướng giải quyết cho vấn đề này là cho phép cấp phát bộ nhớ cho một cấu trúc mới khi cần thiết. C cho phép ta thực hiện điều này thông qua cáhc cấp phát bộ nhớ động bằng: malloc() và calloc() Nhưng các cấu trúc nếu được cấp pháp xong sẽ không có đảm báo nào rằng các cấu trúc sẽ được đặt liên tiếp nhau trong bộ nhớ. Do đó điều cần thiết là kỹ thuật để nối kết tất cả các cấu trúc lại với nhau. Phương cách thông dụng để kết nối các phần tử đó lại là dùng danh sách liên kết (Linked list) Danh sách liên kết đơn: Định nghĩa Cú pháp: struct { . | CHƯƠNG VIII DANH SÁCH MÓC NỐI Ta thương sử dụng mảng cấu trúc để xử lý với nhóm dữ liệu. Đây là một cách tiếp cận đúng khi ta biết trước chính xác số các cấu trúc cần có. Tuy nhiên, khi con số này không rõ ràng, mãng sẽ trở nên khá tốn kém vì chúng phải được cấp phát đủ bộ nhớ để hoạt động. Bố nhớ này được đăng ký và sẽ không dành cho nhứng tác vụ khác ngay cả khi ta chỉ dùng một sô nhỏ các phần tử mảng. Phương hướng giải quyết cho vấn đề này là cho phép cấp phát bộ nhớ cho một cấu trúc mới khi cần thiết. C cho phép ta thực hiện điều này thông qua cáhc cấp phát bộ nhớ động bằng: malloc() và calloc() Nhưng các cấu trúc nếu được cấp pháp xong sẽ không có đảm báo nào rằng các cấu trúc sẽ được đặt liên tiếp nhau trong bộ nhớ. Do đó điều cần thiết là kỹ thuật để nối kết tất cả các cấu trúc lại với nhau. Phương cách thông dụng để kết nối các phần tử đó lại là dùng danh sách liên kết (Linked list) Danh sách liên kết đơn: Định nghĩa Cú pháp: struct { ; struct * } Ví dụ: Định nghĩa một danh sách liên kết để chứa các số nguyên. struct Point { int info; struct Point *Next; }; Các phép toán trên danh sách liên kết Cấp phát bô nhớ cho biến con trỏ mới Cú pháp: Point_New = (struct Point_Name *) malloc (sizeof(struct Point_Name) Ví dụ: typedef struct Point POINT; POINT Head, Last, p; CreatNode() { p=(POINT *) malloc (POINT) if (Head==(POINT* ) NULL) Head=Last=p; else { Last=Head; while (Last->Next!= (POINT*) NULL) Last=Last->Next; Last->Next=p; Last=p; } printf(“\nInput information for Node”); scanf(“%d”, p->.info); Last->Next=(POINT *) NULL; return; } Xoá một con trỏ: Cú pháp: free(Point_Variable) Giải phóng vùng nhớ được trỏ bởi Point_Variable Các phép toán thương dùng trong danh sách liên kết Tạo một phần tư của danh sách Điều phải làm là cấp pháp bộ nhớ cho cấu trúc và trả về con trỏ trỏ đến vùng nhớ này. Ví dụ: POINT *CreatNode() { POINT *p; p = .