DANH SÁCH LIÊN KẾT (LINKED LIST) - NODES

ĐỊNH NGHĨA VỀ DANH SÁCH LIÊN KẾT :

ở bài trước ta đã biết về danh sách tuyến tính. Trong danh sách tuyến tính ta dùng một mảng các phần tử để lưu trữ, điều đó có nghĩa là ta cấp phát tĩnh một bộ nhớ do đó các phần tử nằm liên tiếp trong vùng nhớ.

Còn đối với danh sách liên kết, các phần tử sẽ được cấp phát vùng nhớ trong quá trình thực thi chương trình, do đó chúng có thể nằm rải rác ở nhiều nơi khác nhau trong bộ nhớ (không liên tục).

Khai báo danh sách liên kết:

Các phần tử trong danh sách được kết nối với nhau theo chùm liên kết như  hình trên:

- First  là con trỏ chỉ đến phần tử đầu của danh sách liên kết.

- Phần tử cuối của danh sách liên kết với vùng liên kết có giá trị NULL

- Mỗi nút của danh sách có trường info chứa nội dung của nút và trường next là con trỏ chỉ đến nút kế tiếp trong danh sách.

1 2 3 4 5 6 7

// struct nodeType {     int info ;     nodeType * next ; }; typedef nodeType* NODEPTR ; NODEPTR myFirst ;

Ở đây, ta giả sử nội dung info lưu trữ giá trị kiểu int.

---

KHỞI TẠO DANH SÁCH LIÊN KẾT :

Để khởi tạo danh sách, ta gán biến First = NULL. Ta có thể tạo một hàm có tên là intilizeList để thực hiện khởi tạo danh sách liên kết.

1 2 3 4 5

// Khởi tạo danh sách liên kết   void initilizeList ( NODEPTR & first ) {     first = NULL ; }

---

THÊM PHẦN TỬ VÀO DANH SÁCH LIÊN KẾT :

Đối với danh sách liên kết, ta có hai hình thức thêm phần tử chính đó là thêm phần vào đầu hoặc vào vị trí cuối của danh sách liên kết.

THÊM PHẦN TỬ VÀO ĐẤU DANH SÁCH LIÊN KẾT :

Việc thêm phần tử ở đâu danh sách liên kết là đơn giản nhất. Độ phức tạp là O(1).

Giả sử gọi p là phần tử cần thêm vào đầu danh sách liên kết. Ta lấy First liên kết với p và lấy p liên kết với địa chỉ phần tử đầu tiên (địa chỉ mà First lưu trữ là địa chỉ phần tử đầu tiên).

1 2 3 4 5 6 7 8 9

// Thêm phần tử vào đầu danh sách liên kết   void insertFirst( NODEPTR & first , int x ) {     NODEPTR p = new nodeType ;     p->info = x ;     p->next = first;       first = p ;   }

THÊM PHẦN TỬ VÀO CUỐI DANH SÁCH LIÊN KẾT:

Do danh sách liên kết không thể truy xuất bằng thứ tự, ta chỉ có cách là duyệt từ đầu đến cuối, tìm phần tử cuối cùng của danh sách liên kết. Biết rằng, phần tử cuối cùng của danh sách liên kết có next = NULL.

Độ phức tạp O(n).

DUYỆT DANH SÁCH LIÊN KIẾT:

 Ta lần lượt duyệt các phần từ đầu đến cuối danh sách liên kết. Để đơn giản, ta giả sử chỉ in các phần tử ra.

Ta biết rằng, phần tử đầu tiên trong danh sách liên kết có địa chỉ chứa trong con trỏ First và phần tử cuối danh sách liên kết là NULL.

1 2 3 4 5 6 7 8 9 10

// Duyệt danh sách liên kết   void traverse( NODEPTR first) {     NODEPTR p = first ;     while( p!=NULL) {         printf("%d " , p->info) ;         p = p->next ;     }     printf("\n") ; }

---

 XÓA PHẦN TỬ TRONG DANH SÁCH LIÊN KẾT:

Danh sách liên kết không thể truy cập các phần theo các chỉ số 0,1,2 nên tốt nhất là trong danh sách liên kết ta thực hiện xóa  phần tử theo nội dung.

Chức năng: cho trước giá trị của một phần tử, tìm và loại bỏ phần tử ra khỏi danh sách liên kết.

Để xóa một phần tử có nội dung X ra khỏi danh sách liên kết, ta di chuyển con trỏ đến ngay trước phần tử cần xóa, thực hiện móc liên kết vòng qua phần tử cần xóa.

Ta cần lưu ý, trường hợp đặc biệt sau:

Danh sách rỗng: không thể xóa.

Phần tử xóa ở vị trí đầu tiên: Dời địa chỉ first qua phần tử tiếp theo.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

// Xóa phần tử theo nội dung   int deleteInfo(NODEPTR & first , int x ) {     if(first ==NULL) // danh sách rỗng         return 0 ;       if( first->info ==x ) { // trường hợp phần tử xóa ở đầu         first = first->next;         return 1 ;     }       NODEPTR i = first; // trường hợp xóa không ở đầu dãy     while( (i->next)->info != x) {         i = i->next ;     }     i->next  = (i->next)->next  ;     return 1 ; }

---

CHẠY THỬ DANH SÁCH LIÊN KẾT:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73

// Chạy thử danh sách liên kết   #include <stdio.h>   struct nodeType {     int info ;     nodeType * next ; }; typedef nodeType* NODEPTR ; NODEPTR myFirst ;   void initilizeList ( NODEPTR & first ) {     first = NULL ; } void insertFirst( NODEPTR & first , int x ) {     NODEPTR p = new nodeType ;     p->info = x ;     p->next = first;     first = p ;   } void insertLast(NODEPTR & first, int x ) {     NODEPTR p = first ; // p: con trỏ duyệt từ đầu đến cuối     while(p->next!=NULL) {         p = p->next ;     }     NODEPTR q = new nodeType ; // phần tử thêm vào     q->info = x ;     q->next = NULL ;       p->next = q;   } void traverse( NODEPTR first) {     NODEPTR p = first ;     while( p!=NULL) {         printf("%d " , p->info) ;         p = p->next ;     }     printf("\n") ; }   int deleteInfo(NODEPTR & first , int x ) {     if(first ==NULL) // danh sách rỗng         return 0 ;       if( first->info ==x ) { // trường hợp phần tử xóa ở đầu         first = first->next;         return 1 ;     }       NODEPTR i = first; // trường hợp xóa không ở đầu dãy     while( (i->next)->info != x) {         i = i->next ;     }     i->next  = (i->next)->next  ;     return 1 ; } int main() {     initilizeList(myFirst) ;     insertFirst(myFirst,10)  ;     insertFirst(myFirst,20) ;     insertLast(myFirst,30) ;     insertLast(myFirst,40) ;     traverse(myFirst) ;     deleteInfo(myFirst,40) ;     traverse(myFirst) ;           return 0; }

NGĂN XẾP TUYẾN TÍNH – STACK

Lưu ý: Các bạn biết về danh sách tuyến tính trước khi xem bài viết này. 

---

 ĐỊNH NGHĨA :

Stack là một danh sách mà việc thêm vào và loại bỏ chỉ diễn ra cùng một đầu của danh sách, tức là theo cơ chế LIFO (Last In First Out).

Để cài đặt Stack có thể dùng danh sách tuyến tính hoặc danh sách liên kết đơn, trong bài viết nãy sẽ hướng dẫn cài đặt stack bằng danh sách tuyến tính .

---

 KHAI BÁO :

Stack tuyến tính thực chất cũng là một danh sách tuyến tính, nhưng chỉ khác ở chỗ là ta quy định quy tắc thêm và loại bỏ phần tử của stack xảy ra chỉ ở một đầu danh sách. Do đó, khai báo stack tuyến tính cũng tương tự như danh sách tuyến tính .

Để khai báo một stack tuyến tính chức các phần tử kiểu int, ta khai báo một struct như sau :

          –  int sp  (viết tắt của stack pointer ) :Biến đóng vai trò như con trỏ luôn chứa thứ tự của phần tử cuối cùng(đỉnh stack)

Ban đầu, sp gán giá trị -1 để danh dấu là stack tuyến tính rỗng.

Khi có phần tử, giá trị của sp sẽ từ 0 đến MAXSIZE -1 ( MAXSIZE là giá trị kích thước tối đa của stack tuyến tính do ta định nghĩa).

          –  int nodes[ ]  : mảng để lưu giá trị các phần tử của stack tuyến tính.

1 2 3 4 5 6 7 8 9

// khai báo stack tuyến tính   #include <stdio.h> #define MAXSIZE 1000   struct stackType {     int sp = -1  ;     int nodes[MAXSIZE]  ; };

---

 THÊM PHẦN TỬ VÀO STACK TUYẾN TÍNH:

Nếu danh sách tuyến tính thông thường thì ta có thể thêm các phần tử vào một ví trí bất kì thì stack  tuyến tính quy định việc thêm phần tử vào chỉ xảy ở một đầu.

Ở đây ta cài đặt thêm phần tử vào ở cuối danh sách. Lí do: nếu ta chọn việc thêm phần tử vào đầu thì ta phải thực hiện thao tác dời các phần tử. 

Hình ảnh so sánh 2 cách thêm vào :

  Lưu ý: Để thêm một phần tử vào stack tuyến tính ta cần xét xem stack tuyến tính có bị đầy hay chưa.  Ta biết rằng, nếu một stack tuyến tính có n phần tử thì các phần tử sẽ đánh số từ 0 đến n -1 , do đó stack tuyến tính đầy khi giá trị sp = MAXSIZE -1 . 

1 2 3 4 5 6 7 8

// thêm phần tử vào stack   int push(stackType & pstack , int value ) {     if ( pstack.sp == MAXSIZE -1 ) // stack đầy         return 0 ;     pstack.nodes[++pstack.sp] = value ;     return 1 ; }

---

 LẤY PHẦN TỬ RA KHỎI STACK TUYẾN TÍNH:

Tương tư như thao tác push, thao tác loại bỏ phần tử (pop) trên danh sách tuyến tính chỉ xảy ra ở một đầu. Ở đây, ta quy định loại bỏ phần tử ở cuối danh sách. 

Lưu ý, trước khi ta loại bỏ phần tử ra khỏi stack tuyến tính, ta phải xem stack tuyến tính có rỗng hay không . (stack tuyến tính rỗng khi sp = -1 )

Nếu muốn  lưu giá trị phần tử bị bỏ ra khỏi stack tuyến tính, ta dùng tham thêm một tham biến x ( lưu ý: phải dùng tham biến không phải tham trị) 

1 2 3 4 5 6 7 8 9

//   int pop(stackType &pstack , int &x  ) {     if( pstack.sp == -1)         return 0 ;     x = pstack.nodes[pstack.sp-- ] ;       return 1; }

---

CHẠY THỬ CHƯƠNG TRÌNH:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

// Demo stack // #include <stdio.h> #define MAXSIZE 1000   struct stackType {     int sp = -1  ;     int nodes[MAXSIZE]  ; }; stackType myStack ;   int push(stackType & pstack , int value ) {     if ( pstack.sp == MAXSIZE -1 ) // stack đầy         return 0 ;     pstack.nodes[++pstack.sp] = value ;     return 1 ; }   int pop(stackType &pstack , int &x  ) {     if( pstack.sp == -1)         return 0 ;     x = pstack.nodes[pstack.sp-- ] ;       return 1; } void printStack( stackType pstack) {     printf("my stack : ");     for(int i = 0 ; i <= pstack.sp ; i++) {         printf("%d " , pstack.nodes[i]) ;     }     printf("\n") ;   } int main() {     push(myStack,10) ;     push(myStack,20) ;     push(myStack,30) ;     push(myStack,40) ;     printStack(myStack) ;     int takeValue ;     pop(myStack ,takeValue) ;     printf("Gia tri lay gia : %d \n" ,takeValue) ;     printStack(myStack) ;       return 0; }

---

 TÓM TẮT:

Stack tuyến tính thêm và loại bỏ phần tử ở cùng một đầu (chọn thêm phía sau để tối ưuthuật toán). Stack tuyến tính dùng biến sp (  viết tắt của stack pointer)  để lưu địa chỉ phần tử cuối cùng.           

sp = -1 : stack tuyến tĩnh rỗng.            

sp = MAXSIZE -1 : stack tuyến tính đầy.

---

ỨNG DỤNG CỦA STACK TUYẾN TÍNH:

 Stack thường được dùng trong các bài toán có cơ chế LIFO (vào sau ra trước) Stack cũng được dùng trong các bài toán gỡ đệ qui (chuyển một giải thuật đệ qui thành giải thuật không đệ qui).

---

 LUYỆN TẬP:

Viết chương trình đổi số nguyên không âm ở hệ thập phân sang số ở hệ nhị phân.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

//  chương trình đổi thập phân sang nhị phân, ngôn ngữ C   #include <stdio.h> #include <stdlib.h> // sytem ("cls") #include <conio.h> #define STACKSIZE 100 #define TRUE 1 #define FALSE 0 struct stack {    int sp;    int nodes[STACKSIZE]; }; int empty(struct stack st) {    if(st.sp == -1)       return(TRUE);    else       return(FALSE); } int push(struct stack &st, int x) {    if(st.sp == STACKSIZE-1) return 0;    st.nodes[++(st.sp)] = x;    return 1; } int pop(struct stack &st, int &x) {    if(empty(st)) return 0;    x=st.nodes[(st.sp)--];    return 1; } int main() {    struct stack st;    int  sodu;    long  so;    char c;   do    {       st.sp =- 1;  // khoi dong stack       system("cls") ; printf("\n\nNhap vao mot so thap phan: ");       scanf("%ld", &so);       do       {           sodu = so % 2;           push(st, sodu);  // push so du vao stack           so = so / 2;       } while (so != 0); printf("So da doi la: ");       while(!empty(st))        {            int x ;             pop(st,x);           printf("%d", x);  // pop so du ra khoi stack         } printf("\n\nBan co muon tiep tuc khong? (c/k): ");       c = getche();    } while(c == 'c' || c == 'C'); }