Lập trình C: Bài 12 – Danh sách liên kết cài bằng mảng
Lập trình C: Bài 12 – Danh sách liên kết cài bằng mảng Tháng Một 20, 2018 nguyenvanquan7826 TUT Cấu trúc dữ liệu 33 responses Danh sách liên kết có thể được cài đặt bằng mảng hoặc bằng con trỏ. Trong bài viết này mình sẽ hướng ...
Lập trình C: Bài 12 – Danh sách liên kết cài bằng mảng
Danh sách liên kết có thể được cài đặt bằng mảng hoặc bằng con trỏ. Trong bài viết này mình sẽ hướng dẫn các bạn sử dụng mảng :), Loại danh sách này thường được gọi là danh sách kế tiếp.
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:
#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.
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).
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 đó.
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
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 !
");
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
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ó.
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
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.
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;
}
9. Chương trình hoàn chỉnh (full)
#include<stdio.h>
#include<stdlib.h>
#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
void Init(List *L); //ham khoi tao danh sach rong
void Init(List *L); //ham khoi tao danh sach rong
int Isempty (List L); //kiem tra danh sach rong
int Isfull (List L); //kiem tra danh sach day
int Insert_k (List *L, item x, int k); //chen x vao vi tri k
void Input (List *L);//nhap danh sach
void Output (List L);//xuat danh sach
int Search (List L, item x); //tim phan tu x trong danh sach
int Del_k (List *L, item *x, int k);//xoa phan tu tai vi tri k
int Del_x(List *L, item x);//xoa phan tu x trong danh sach
item init_x(); //tao phan tu x.
//-----------------------------------
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.
}
int Isempty (List L)
{
return (L.size==0);
}
int Isfull (List L)
{
return (L.size==N);
}
item init_x() //khoi tao gia tri x
{
int temp;
scanf("%d",&temp);
return temp;
}
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 !
");
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;
}
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();
}
}
void Output (List L)
{
printf("Danh sach:
");
int i;
for (i=0; i<L.size; i++)
printf("%5d",L.Elems[i]);
printf("
");
}
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;
}
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;
}
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;
}
int main()
{
List L;
Init(&L);
Input(&L);
Output(L);
int lua_chon;
printf("Moi ban chon phep toan voi DS LKD:");
printf("
1: Kiem tra DS rong");
printf("
2: Do dai DS");
printf("
3: Chen phan tu x vao vi tri k trong DS");
printf("
4: Tim mot phan tu trong DS");
printf("
5: Xoa phan tu tai vi tri k");
printf("
6: XOa phan tu x trong DS");
printf("
7: Thoat");
do
{
printf("
Ban chon: ");
scanf("%d",&lua_chon);
switch (lua_chon)
{
case 1:
{
if (Isempty(L)) printf("DS rong !");
else printf ("DS khong rong !");
break;
}
case 2: printf ("Do dai DS la: %d.",L.size);break;
case 3:
{
item x;
int k;
printf ("Nhap vi tri can chen: ");
scanf ("%d",&k);
if (Insert_k(&L,x,k))
{
printf ("DS sau khi chen:
"); //xuat danh sach sau khi chen
Output(L);
}
break;
}
case 4:
{
item x;
printf ("Moi ban nhap vao phan tu can tim: ");
scanf("%d",&x);
int k=Search(L,x);
if (k) printf ("Tim thay %d trong DS tai vi tri thu: %d",x,k);
else printf ("Khong tim thay %d trong danh sach !",x);
break;
}
case 5:
{
int k;
item x;
printf ("Nhap vi tri can xoa: ");
scanf ("%d",&k);
if (Del_k (&L,&x,k))
{
printf ("DS sau khi xoa:
");
Output(L);
}
break;
}
case 6:
{
item x;
printf ("Nhap phan tu can xoa: ");
scanf ("%d",&x);
if (Del_x(&L,x))
{
printf ("DS sau khi xoa:
");
Output(L);
}
break;
}
case 7: break;
}
}while (lua_chon !=7);
return 0;
}
[rps-include post=”2703″ shortcodes=”false”]
