DANH SÁCH LIÊN KẾT ARRAY - LẬP TRÌNH C/C++

13:08:00  Unknown  0 comments

1. Cài đặt (khai báo) danh sách

Để khai báo danh sách này ta cần có 1 mảng có số phần tử tối đa là N có kiểu dữ liệu là item (item này là kiểu dữ liệu tổng quan, khi làm nó sẽ là kiểu int, float hay kiểu cấu trúc sinh viên). Cần thêm 1 biến size thể hiện số phần tử hiện có của danh sách.
Cụ thể như sau:

1
2
3
4
5
6
7
8
9
#define N 100 //so phan tu toi da la 100
typedef int item;
/*kieu cac phan tu la item
ma cu the o day item la kieu int */
typedef struct
{
    item Elems[N]; //mang kieu item
    int size; //so phan tu toi da cua mang
}List; //kieu danh sach List

2. Khởi tạo danh sách rỗng

Danh sách của ta rỗng khi số phần tử trong danh sách bằng 0. Vì vậy chỉ cần khai báo trường size của ta bằng 0 là được.

1
2
3
4
5
6
void Init(List *L) //ham khoi tao danh sach rong
/*Danh sach L duoc khai bao kieu con tro
de khi ra khoi ham no co the thay doi duoc*/
{
    (*L).size = 0; //size = 0.
}

3. Kiểm tra danh sách rỗng, danh sách đầy

Để kiểm tra danh sách rỗng hay đầy ta chỉ việc xem số phần tử của danh sách có bằng 0 hay không (rỗng) và có bằng N hay không (đầy).
1
2
3
4
5
6
7
8
9
int Isempty (List L)
{
    return (L.size==0);
}
int Isfull (List L)
{
    return (L.size==N);
}

4. Chèn phần tử vào vị trí k trong danh sách

Trước khi chèn phần tử vào trong danh sách chúng ta nên xây dựng 1 hàm trả về dữ liệu (nhập vào dữ liệu) của phần tử cần chèn đó.
1
2
3
4
5
6
item init_x() //khoi tao gia tri x
{
    int temp;
    scanf("%d",&temp);
    return temp;
}
Sau đó tiến hành chèn:
Trong quá trình chèn chúng ta cần kiểm tra xem danh sách đầy chưa, nhập vị trí k cần chèn và kiểm tra nó, nếu phù hợp (0<k<=N) thì sẽ tiến hành chèn.
Để chèn được phần tử x vào vị trí k trong danh sách (trong mảng) ta cần dùng 1 vòng for để di chuyển các phần tử từ vị trí k về phía cuối mảng, sau đó chèn x vào vị trí k. Cuối cùng ta tăng size lên 1 đơn vị.
Chèn phần tử vào danh sách
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int Insert_k (List *L, item x, int k)//chen x vao vi tri k
{
    if (Isfull(*L)) //kiem tra danh sach day
    {
        printf("Danh sach day !");
        return 0;
    }
    if (k<1 || k>(*L).size+1) //kiem tra dieu kien vi tri chen
    {
        printf("Vi tri chen khong hop le !\n");
        return 0;
    }
    printf ("Nhap thong tin: ");
    x = init_x(); //gan x = ham khoi tao x
    int i;
    //di chuyen cac phan tu ve cuoi danh sach
    for (i = (*L).size; i >= k; i--)
        (*L).Elems[i] = (*L).Elems[i-1];
    (*L).Elems[k-1]=x;//chen x vao vi tri k
    (*L).size++;//tang size len 1 don vi.
    return 1;
}

5. Nhập danh sách

Nhập như bình thường với mảng
01
02
03
04
05
06
07
08
09
10
11
12
void Input (List *L)
{
    int n;
    printf("Nhap so phan tu cua danh sach: ");
    scanf("%d",&(*L).size);
    int i;
    for (i=0; i<(*L).size; i++)
    {
        printf("Nhap phan tu thu %d : ",i+1);
        (*L).Elems[i] = init_x();
    }
}

6. Tìm phần tử x trong danh sách

Ta duyệt từ đầu đến cuối danh sách nếu có giá trị x thì đưa ra vị trí của nó.

1
2
3
4
5
6
7
8
int Search (List L, item x)
{
    int i;
    for (i=0; i<L.size; i++)
        if (L.Elems[i] == x)
            return i+1;
    return 0;
}

7. Xóa phần tử thứ k trong danh sách

Trước khi xóa ta phải kiểm tra xem danh sách có rỗng không. Nếu không rỗng ta nhập vào vị trí cần xóa và kiểm tra (phù hợp nếu 0<k<=N).
Ta dùng vòng for chạy đến vị trí thứ k, sau đó dồn các phần tử từ k+1 về trước 1 đơn vị. tuy nhiên ta cần lưu lại giá trị của phần tử xóa trước khi xóa để giữ lại thông tin nếu ta cần dùng đến nó. Cuối cùng là giảm size xuống 1 đơn vị.
Xóa phần tử trong danh sách

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
int Del_k (List *L, item *x, int k)
{
    if (Isempty(*L))
    {
        printf("Danh sach rong !");
        return 0;
    }
    if (k<1 || k>(*L).size)
    {
        printf("Vi tri xoa khong hop le !");
        return 0;
    }
    *x=(*L).Elems[k-1]; //luu lai gia tri cua phan tu can xoa
    int i;
    for (i=k-1; i<(*L).size-1; i++) //don cac phan tu ve truoc
    (*L).Elems[i]=(*L).Elems[i+1];
    (*L).size--; //giam size
    return 1;
}

8. Xóa phần tử có nội dung x trong danh sách

Để xóa phần tử có nội dung x trong danh sách ta tiến hành tìm phần tử x trước bằng hàm search sau đó giá trị trả về là vị trí của x, ta tiếp tục sử dụng hàm del_k để xóa phần tử ở vị trí mà ta tìm được.
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
int Del_x (List *L, item x)
{
    if (Isempty(*L))
    {
        printf("Danh sach rong !");
        return 0;
    }
    int i = Search(*L,x);
    if (!i)
    {
        printf("Danh sach khong co %d",x);
        return 0;
    }
    do
    {
        Del_k(L,&x,i);
        i = Search(*L,x);
    }
    while (i);
    return 1;
}

Posted in:

0 Comment:

Đăng nhận xét

Thank you for your comments!