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

Bài giảng "Lập trình C: Chương 8 - Danh sách móc nối" được biên soạn với các nội dung chính sau: Danh sách liên kết đơn; Danh sách đa liên kết; STACK và QUEUE;... Mời các bạn cũng tham khảo bài giảng tại đây!
Nội dung trích xuất từ tài liệu:
Bài giảng Lập trình C: Chương 8 - Danh sách móc nối 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)           I. Danh sách liên kết đơn: 1. Đị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; }; 2. Các phép toán trên danh sách liên kết a. 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; } b. 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á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 = (POINT *) malloc (sizeof(POINT)); if  (p==NULL) { printf(“Malloc falled.\n”); exit(1); } printf(“Input data for Node info = ”);  scanf(“%d”, p­>info); p­>Next = NULL return p; } Bổ sung phần tư vào danh sách Hàm CreatNode() chỉ cấp phát bộ nhớ nhưng nó  không nối phần tử này vào danh sách. Để làm điều  này, ta cần thêm một hàm nữa, gọi là hàm AddNode().  Được định nghĩa như sau: static POINT *Head; void AddNode(POINT *e) { POINT *p; if (Head ==NULL) { Head = e; return; } for (p=Head; p­>Next!=NULL; p=p­>Next); p­>Next=e; } Chú ý: Biến  Head  là  con  trỏ  trỏ  đến  đầu  danh  sách,  nên  cần  được  khai  báo  đầu  chương  trình.(Sau  phần  khai định nghĩa kiểu con trỏ). Chèn phần tư vào danh sách Để chèn phần tử vào danh sách liên kết, ta phải  chỉ rỏ phần tử mới sẽ được chèn vào vị trí nào.Sau  đây là hàm sẽ thực hiện công việc trên. void InsertNode(POINT *p, POINT *q) { if (p=NULL || q=NULL || p==q || q­>Next ==p) { printf (“Cannot Insert \n”);    return; } p­>Next =q­>Next; q­>Next=p; }; Xoá phần tư vào danh sách Xoá một phần tử khỏi danh sách liên kết đơn,  ta cần phải tìm phần tử trước phần tử cần xoá để  nhằm mục đích nối lại với phần tử sau phần tử  cần xoá. Ta dùng hàm free() để giải phống bộ nhớ  chiếm bởi phần tử bị xoá.  Có thể xây dưng là: void DeleteNode(POINT *goner) { POINT *p; p=Head; if (goner ==Head) Head = goner­>Next; else  { while (p!=NULL && p­>Next!=goner)      p=p­>Next;   if (p=NULL) { printf(“Cannot find Node \n”); return; } p­>Next=p­>Next­>Next; }; free(goner) }; Tìm phần tư vào danh sách Thật khó tạo một hàm FindNode() tổng quát,  bởi vì khi tìm kiếm thì ta phải dựa vào một trong  những trường dữ liệu của cấu trúc, điều này phụ  thuộc  vào  cấu  trúc  dang  sử  dụng.  Để  viết  hàm  FindNode() tổng quát ta phảisử dụng con trỏ trỏ  đến hàm. Với cấu trúc trên ta xây dựng hàm FindNode()  như sau: POINT *FindNode(int *n) { POINT *p; for (p=Head; p!=NULL; p=p­>Next) if (p­>Info=n)  return p; return NULL; }; II. Danh sách đa liên kết Đị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,*Previous; }; III. STACK và QUEUE 1. STACK Là danh sách có móc nối đặc biệt. Mặc dầu ta  có thể thực hiệm nhiều phép toán trên danh sách  tổng quát, Stack vẫn có những tính chất riêng  biệt: chỉ cho phép thêm và xoá bỏ các phần tử ở  một vị trí duy nhất, tại đỉnh của Stack. Với đặc trưng như vậy thì Stack có kiểu cấu  trúc dữ liệu là LIFO (Last In First Out) a. Khởi tạo Stack Sử dụng mảng: int stack[100], p; Stackinit() { p=0; } Sử dụng danh sách liên kết struct Node  {     int info;         struct Node *Next;  }; typedef struct Node NODE; NODE *Head, *p, *q; StackInit() {  Head = (NODE *) malloc (sizeof *Head);  p=(NODE *) malloc (sizeof *p);   Head­>Next=p;   Head­>info=0;   p­>Next=NULL;   return 0; } ...