Danh sách liên kết đơn nhập xuất[P1]

Con trỏ danh sách liên kết trong lập trình c, cơ bản dễ hiểu,..

1. Khởi tạo danh sách liên kết
Cấu tạo đơn thuần một danh sách liên kết đơn.

1.1 Cách 1 khai báo đơn thuần

struct nut
{
    int data;
    struct nut *next;
};
struct nut *dau, *cuoi;

1.2 Cách2 khai báo kiểu mới(Typedef)

typedef struct SV{
        int data;
        struct SV* next;        
} nut;
nut* dau,* cuoi;

2. Cấp phát ô nhớ

Code:

nut *p = (nut *)malloc(sizeof(nut));    //1. Khai báo và cấp phát vùng nhớ cho p

3. Thêm phần tử vào danh sách.3.1 Thêm đầu

Giả sử danh sách ban đầu có 3 nút có giá trị lần lượt là 5, 3 và 6. Để thêm nút có giá trị 4 vào đầu danh sách ta cần thực hiện lần lượt 4 bước sau:

Đầu tiên (bước 1) ta phải cấp phát vùng nhớ cho nút mới này và cho con trỏ p trỏ đến (quản lý), sau đó (bước 2) sẽ đưa giá trị vào nút. Thao tác cuối cùng là gắn nút mới này vào đầu danh sách bằng cách (bước 3) cho nút này quản lý nút đầu tiên của danh sách (p->next=dau), tiếp đến (bước 4) cho con trỏ dau trỏ đến nút mới (nút mà p cũng đang trỏ). Chú ý là bước 3 phải thực hiện trước bước 4 vì rằng nếu bước 4 thực hiện trước (con trỏ dau trỏ đến nút mới ngay) thì danh sách sẽ bị "lạc lối", kiểu như "chuyển công tác" mà chưa bàn giao công việc cho người thay thế! (người thay thế ở đây là con trỏ p->next.

Code:

void ThemDau(int giatri){
     nut *p;
     p=(nut* )malloc(sizeof(nut)); // 1.Cấp phát ô nhớ cho p 
     p->data=giatri;               // 2.Gán giá trị cho p
     p->next=dau;                  // 3.Gán p vào đầu con trỏ
     dau=p;                        // 4.Cập nhật con trỏ
}

3.2 Thêm cuối

Có nhiều cách để thêm một nút mới vào cuối danh sách. Dưới đây là cách có sử dụng thêm con trỏ cuoi (luôn trỏ đến phần tử cuối cùng của danh sách). Nếu không có con trỏ này, trước mỗi lần thêm nút mới ta phải "duyệt" toàn bộ danh sách để tìm được con trỏ trỏ đến phần tử cuối cùng (chính là con trỏ cuoi). Khi đã có được con trỏ cuoi, để gắn nút mới vào danh sách ta chỉ việc gắn nút này vào ngay sau nút được trỏ bởi cuoi.

code:

void ThemCuoi(int giatri)
{
    nut *p = (nut *)malloc(sizeof(nut));  //1.Khai báo và cấp phát ô nhớ cho p
    p->data = giatri;                     //2. Gán giá trị cho p
    p->next = NULL;  
    if (dau == NULL)                      //3.Gắn p vào danh sách
        dau = p;
    else
        cuoi->next = p;
    cuoi = p;                              //4.Cập nhật con trỏ cuối
}

4.Hiển thị ra màn hình

Muốn hiển thị ta cần phải duyệt danh sách.
Để duyệt danh sách, ta cần thêm một con trỏ p. Ban đầu p trỏ đến nút đầu tiên (p=dau). Ta sẽ "lặp" việc di chuyển p cho đến khi hết danh sách (p=NULL). Đoạn mã cho việc duyệt danh sách có thể viết như sau:
Code:

void HienThi(){
     nut *p;                       //1.Khai báo p
     p=dau;                        //2.Gán p vào đầu để quản lí DS 
     while(p != NULL){             //3.Nếu danh sách rỗng
          printf("%d",p->data);
          p=p->next;               //4.Duyệt p                
     }     
}

5.Chương trình hoàn thiện

#include &ltstdio.h&gt
#include &ltstdlib.h&gt
typedef struct SV{
        int data;
        struct SV* next;        
} nut;
nut* dau,* cuoi;
void ThemDau(int giatri){
     nut *p;
     p=(nut* )malloc(sizeof(nut)); 
     p->data=giatri;
     p->next=dau;
     dau=p;   
}
void ThemCuoi(int giatri)
{
    nut *p = (nut *)malloc(sizeof(nut));    
    p->data = giatri;                     
    p->next = NULL;  
    if (dau == NULL)                        
        dau = p;
    else
        cuoi->next = p;
    cuoi = p;                              
}
void HienThi(){
     nut *p;
     p=dau;
     while(p != NULL){
          printf("%d",p->data);
          p=p->next;                               
     }     
}

int main(int argc, char *argv[])
{
   int n,i,s;
    printf("Nhap vao tong so: ");
    scanf("%d",&n);
    for(i=0;i<n;i++){
         printf("Nhap vao so %d: ",i+1);
         scanf("%d",&s);    
         ThemCuoi(s);        
    }
    HienThi();
  
  system("PAUSE"); 
  return 0;
}

Jundat95

Header Ads

Danh sách liên kết đơn nhập xuất[P1]