Chào các bạn, mình đang tìm hiểu về danh sách liên kết , mình đang học tới phần Danh sách liên kết kép và làm theo blog của anh nguyễn văn quân .
đây là code của mình .
#include <stdio.h>
#include <stdlib.h>
typedef int item;
typedef struct Node //cấu trúc một node
{
item Data; //dữ liệu của node
Node *left; //Con trỏ phải
Node *right; //con trỏ trái
};
typedef struct DList
{
Node *head; //con trỏ đầu
Node *tail; //con trỏ cuối
};
void init(DList &L); //khởi tạo danh sách
int isempty(DList L); //kiểm tra ds
int len(DList L); //độ dài ds
Node *make_node(Node *p, item x); //tạo 1 node p chứa thông tin là x
void insert_first(DList &L, item x); //chèn x vào vị trí đầu trong danh sách
void insert_last(DList &L, item x); //chèn x vào vị trí cuối trong ds
void insert_k(DList &L, item x, int k);// chèn x vào vị trí k trong danh sách
void del_first(DList &L, item &x); // xóa phần tử đầu tiên trong ds
void del_k(DList &L,item &x,int k); //xóa node k trong ds
int Search(DList L, item x); //tìm x trong danh sách
void del_x(DList &L, item x); //xóa phần tử x trong danh sách
void Input(DList &L); //nhập danh sách
void Output(DList L); //xuất danh sách
void init(DList &L)// hàm khởi tạo danh sách
{
L.head=NULL; //con trỏ đầu trỏ đến NULL
L.tail=NULL; //con trỏ cuối trỏ đến NULL
}
int isempty(DList L) //hàm kiểm tra danh sách
{
return (L.head==NULL);
}
int len(DList L) //hàm kiểm tra độ dài danh sách
{
Node *PH = L.head, *PT = L.tail ;//tạo 1 node ph(con trỏ duyệt từ đầu ds) và pt(con trỏ duyệt từ cuối ds)
int i = 0; //biến đếm
if(PH!=NULL)
i = 1;
while(PH!=NULL) // vòng lặp chạy đến khi gặp NULL
{
if(PH==PT) break;
PH = PH ->right; //cho PH trỏ đến node tiếp theo
i++;
if(PH==PT) break;
PT = PT->left; //cho PH trỏ đến node phía trước
i++;
}
return i; // trả lại số node của p
}
Node *make_node(item x)
{
Node *p = (Node *)malloc(sizeof(Node));//cấp phát vùng nhớ cho p
p->Data; //ghi dữ liệu vào data
p->left = NULL;
p->right= NULL;
return p;
}
void insert_first(DList &L, item x) //chèn x vào vị trí đầu tiên trong danh sách
{
Node *p;
p = make_node(x); //tạo 1 node p
if(isempty(L)) // kiểm tra nếu danh sách rỗng
{
L.head=p;
L.tail=p;
}
else
{
p->right = L.head;
L.head->left = p;
L.head = p;
}
}
// chèn vào danh sách cuối cũng tương tự
void insert_last(DList &L, item x)
{
Node *p;
p = make_node(x); //tạo 1 node p
if(isempty(L))
{
L.head=p;
L.tail=p;
}
else
{
L.tail->right = p; //kết nối với danh sách
p->left = L.tail; //p trỏ về node trước
L.tail = p; //lưu lại vị trí cuối
}
}
void insert_k(DList &L, item x, int k) // chèn x vào vị trí k
{
Node *PH = L.head, *PT, *R;
int i = 1, l = len(L);
if(k<1||k>l+1)
printf("\nvi tri chen khong hop le\n"); //kiểm tra điều kiện
else
{
R = make_node(x); //tạo 1 node p
if(k==1)
insert_first(L,x); // chèn vào vị trí đầu tiện
else
if(k == l+1)
insert_last(L,x); //chèn vào vị trí cuối
else //chèn vào vị trí 1<k<l+1
{
while(PH!=NULL&&i!=k-1) // duyệt đến vị trí k-1
{
i++;
PH = PH ->right;
}
PT = PH->right; //xác định vị trí k
R->right = PT; //cho r trỏ đến bên phải danh sách PT
R->left = PH; // cho r trỏ đến bên trái danh sách PH
PH->right = R; //cho ph trỏ đến bên phải danh sách = R
PT->left = R; //cho pt trỏ đến bên trái danh sách = R
}
}
}
void del_first(DList &L,item &x)
{
if(!isempty(L))
{
x = L.head->Data; // lưu giá trị
L.head = L.head->right; //Cho L tro den Node thu 2 trong danh sach
}
}
void del_last(DList &L, item &x) //xóa phần tử cuối cùng trong danh sách
{
if(!isempty(L))
{
x = L.tail->Data; // lưu lại phần tử
L.tail = L.tail->left; // dồn các phần tử phía sau về trước
L.tail->right = NULL; //xóa các phần tử phía sau
}
}
void del_k(DList &L, item &x, int k) // xóa node k trong danh sách
{
Node *PH = L.head, *PT;
int i = 1, l = len(L);
if(k<1||k>l)
printf("\nVi tri xoa khong hop le: "); //kt điều kiện
else
{
if(k==1)
del_first(L,x); // xóa vị trí đầu
else
if(k==1)
del_last(L,x); //xóa vị trí cuối
else // xóa vị trí 1<k<l+1
{
while(PH !=NULL && i!=k-1) // duyệt từ đầu đến vị trí k - 1
{
i++;
PH = PH->right;
}
x = PH->right->Data; // lưu giá trị
PT = PH->right->right; // xác định vị trí k+1
PH->right = PT; // ph trỏ đến bên phải pt
PT->left = PH; //pt trỏ đến bên trái
}
}
}
int Search(DList L, item x) //tìm x trong danh sách
{
Node *P = L.head;
int i = 1;
while(P!=NULL && P->Data!=x) //duyệt danh sách đến khi tìm đc x hoặc kết thúc thì ngưng
{
P = P->right;
i++;
}
if(P!=NULL)
return i; //trả về vị trí i
else
return 0;
}
void del_x(DList &L,item x) //xóa phần tử x trong danh sách
{
int l = Search(L,x);
while(l)
{
del_k(L,x,l); // trong khi chua tim thay x thi van xoa
l = Search(L,x);
}
}
void Input(DList &L) //nhập danh sách
{
int i = 0;
item x;
do
{
i++;
printf("Nhap phan tu thu %d, nhap 0 de dung: ",i);
scanf("%d",&x);
if(x!=0) insert_k(L,x,len(L)+1);
}while(x!=0);
}
void Output(DList L)
{
Node *P = L.head;
while (P!=L.tail->right)
{
printf("%5d ",P->Data);
P = P->right;
}
printf("\n");
}
int main()
{
DList L;
init(L); // gọi hàm khởi tạo danh sách
Input(L);
Output(L);
int lua_chon;
printf("\n\nMoi ban chon phep toan voi DSLKK: ");
printf("\n1 Kiem tra danh sach: ");
printf("\n2 Kiem tra do dai danh sach: ");
printf("\n3 Chen phan tu x vao vi tri k trong danh sach: ");
printf("\n4 Tim mot phan tu trong danh sach");
printf("\n5 Xoa phan tu tai vi tri k trong danh sach");
printf("\n6 Xoa phan tu x trong danh sach ");
printf("\n7 Thoat");
do
{
printf("\nMoi ban lua chon: ");
scanf("%d",&lua_chon);
switch(lua_chon)
{
case 1:
{
if(isempty(L))
printf("Ds rong\n");
else
printf("Ds khong rong\n");
break;
}
case 2: printf("\nDo dai danh sach = %d",len(L)); break;
case 3:
{
item x;
int k;
printf("\nNhap phan tu can chen vao danh sach: ");
scanf("%d",&x);
printf("\nNhap vi tri can chen: ");
scanf("%d",&k);
insert_k(L,x,k);
printf("\n Danh sach sau khi chen: ");
Output(L);
break;
}
case 4:
{
item x;
printf("\nNhap vao phan tu can tim: ");
scanf("%d",&x);
int k = Search(L,x);
if(k)
printf("\nTim thay %d trong danh sach tai vi tri %d",x,k);
else
printf("\nKhong tim thay phan tu %d trong danh sach",x);
break;
}
case 5:
{
int k;
item x;
printf("\nNhap vi tri can xoa: ");
scanf("%d",&k);
del_k(L,x,k);
printf("\nDanh sach sau khi xoa: ");
Output(L);
break;
}
case 6:
{
item x;
printf("\nNhap phan tu can xoa: ");
scanf("%d",&x);
del_x(L,x);
printf("\nDanh sach sau khi xoa\n");
Output(L);
break;
}
case 7: break;
}
}while(lua_chon!=7);
return 0;
}
còn đây là code trên blog của anh quân
#include <stdlib.h>
#include <stdio.h>
typedef int item;
typedef struct Node //cau truc 1 Node
{
item Data; //du lieu cua Node
Node *Left; //Con tro trai
Node *Right; //con tro phai
};
typedef struct DList //cau truc Cua List
{
Node *Head; //con tro dau
Node *Tail; //con tro cuoi
};
void Init(DList &L);
int Isempty (DList L); //kiem tra DS rong
int Len (DList L); // Do dai danh sach
Node *Make_Node (Node *P, item x); //tao 1 Node P chua thong tin la x
void Insert_first (DList &L, item x); //Chen x vao vi tri dau tien trong danh sach
void Insert_last (DList &L, item x); //Chen x vao vi tri dau tien trong danh sach
void Insert_k (DList &L, item x, int k); //chen x vao vi tri k trong danh sach
void Del_first (DList &L, item &x); //Xoa phan tu dau tien
void Del_k (DList &L, item &x, int k); //Xoa Node k trong danh sach
int Search (DList L, item x); //tim x trong danh sach
void Del_x (DList &L, item x); //xoa phan tu x trong danh sach
void Input (DList &L); //nhap danh sach
void Output (DList L); //xuat danh sach
void Init(DList &L)
{
L.Head = NULL; // Con tro dau tro den NULL
L.Tail = NULL; // Con tro cuoi tro den NULL
}
int Isempty (DList L) //kiem tra DS rong
{
return (L.Head == NULL);
}
int Len (DList L) // Do dai danh sach
{
Node *PH = L.Head, *PT = L.Tail; //tao Node PH (con tro duyet tu dau DS) và PT (con tro duyet tu cuoi DS) de duyet danh sach L
int i = 0; //bien dem
if (PH != NULL) i = 1;
while (PH != NULL) //trong khi P chua tro den NULL (cuoi danh sach thi lam)
{
if (PH == PT) break;
PH = PH->Right; //cho PH tro den Node tiep theo
i++;
if (PH == PT) break;
PT = PT->Left; //cho PT tro den Node truoc do
i++;
}
return i; //tra lai so Node cua L
}
Node *Make_Node (item x) //tao 1 Node P chua thong tin la x
{
Node *P = (Node *) malloc (sizeof (Node)); //Cap phat vung nho cho P
P->Data = x; //Ghi du lieu vao Data
P->Left = NULL;
P->Right = NULL;
return P;
}
void Insert_first (DList &L, item x) //Chen x vao vi tri dau tien trong danh sach
{
Node *P;
P = Make_Node(x); //tao 1 Node P
if (Isempty(L)) //Neu danh sach rong
{
L.Head = P;
L.Tail = P;
}
else
{
P->Right = L.Head;
L.Head->Left = P;
L.Head = P;
}
}
//Chen vao cuoi danh sach cung tuong tu
void Insert_last (DList &L, item x) //Chen x vao vi tri cuoi trong danh sach
{
Node *P;
P = Make_Node(x); //tao 1 Node P
if (Isempty(L)) //Neu danh sach rong
{
L.Head = P;
L.Tail = P;
}
else
{
L.Tail->Right = P; //ket noi voi danh sach
P->Left = L.Tail; //P tro ve Node truoc
L.Tail = P; //luu lai vi tri cuoi
}
}
void Insert_k (DList &L, item x, int k) //chen x vao vi tri k trong danh sach
{
Node *PH = L.Head, *PT, *R;
int i=1, l = Len(L);
if (k<1 || k> l+1) printf("Vi tri chen khong hop le !"); //kiem tra dieu kien
else
{
R = Make_Node(x); //tao 1 Node P
if (k == 1) Insert_first(L,x); //chen vao vi tri dau tien
else
if (k == l+1) Insert_last(L,x); //chen vao vi tri cuoi
else //chen vao vi tri 1<k<l+1
{
while (PH != NULL && i != k-1) //duyet den vi tri k-1
{
i++;
PH = PH->Right;
}
PT = PH->Right; //xac dinh vi tri k
R->Right = PT; //(1)
R->Left = PH; //(2)
PH->Right = R; //(3)
PT->Left = R; //(4)
}
}
}
void Del_first (DList &L, item &x) //Xoa phan tu dau tien
{
if (!Isempty(L))
{
x = L.Head->Data; //lay gia tri ra neu can dung
L.Head = L.Head->Right; //Cho L tro den Node thu 2 trong danh sach
}
}
void Del_last (DList &L, item &x) //Xoa phan tu dau tien
{
if (!Isempty(L))
{
x = L.Tail->Data;
L.Tail = L.Tail->Left;
L.Tail->Right = NULL;
}
}
void Del_k (DList &L, item &x, int k) //Xoa Node k trong danh sach
{
Node *PH = L.Head, *PT;
int i=1, l = Len(L);
if (k<1 || k> l) printf("Vi tri xoa khong hop le !"); //kiem tra dieu kien
else
{
if (k == 1) Del_first(L,x); //xoa vi tri dau tien
else
if (k == l) Del_last(L,x); //xoa vi tri cuoi
else //xoa vi tri 1<k<l+1
{
while (PH != NULL && i != k-1) //duyet den vi tri k-1
{
i++;
PH = PH->Right;
}
x = PH->Right->Data;
PT = PH->Right->Right; //xac dinh vi tri k+1
PH->Right = PT;
PT->Left = PH;
}
}
}
int Search (DList L, item x) //tim x trong danh sach
{
Node *P=L.Head;
int i=1;
while (P != NULL && P->Data != x) //duyet danh sach den khi tim thay hoac ket thuc danh sach
{
P = P->Right;
i++;
}
if (P != NULL) return i; //tra ve vi tri tim thay
else return 0; //khong tim thay
}
void Del_x (DList &L, item x) //xoa phan tu x trong danh sach
{
int l = Search(L,x);
while (l)
{
Del_k (L,x,l); //trong khi van tim thay x thi van xoa
l = Search(L,x);
}
}
void Input (DList &L) //nhap danh sach
{
int i=0;
item x;
do
{
i++;
printf ("Nhap phan tu thu %d : ",i);
scanf("%d",&x);
if (x != 0) Insert_k(L,x,Len(L)+1);
} while(x != 0); //nhap 0 de ket thuc
}
void Output (DList L) //xuat danh sach
{
Node *P=L.Head;
while (P != L.Tail->Right)
{
printf("%5d",P->Data);
P = P->Right;
}
printf("\n");
}
int main()
{
DList L;
Init(L);
Input(L);
Output(L);
int lua_chon;
printf("Moi ban chon phep toan voi DS LKD:");
printf("\n1: Kiem tra DS rong");
printf("\n2: Do dai DS");
printf("\n3: Chen phan tu x vao vi tri k trong DS");
printf("\n4: Tim mot phan tu trong DS");
printf("\n5: Xoa phan tu tai vi tri k");
printf("\n6: XOa phan tu x trong DS");
printf("\n7: Thoat");
do
{
printf("\nBan 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.",Len(L));break;
case 3:
{
item x;
int k;
printf ("Nhap phan tu can chen vao DS: ");
scanf("%d",&x);
printf ("Nhap vi tri can chen: ");
scanf ("%d",&k);
Insert_k (L,x,k);
printf ("DS sau khi chen:\n");
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);
Del_k (L,x,k);
printf ("DS sau khi xoa:\n");
Output(L);
break;
}
case 6:
{
item x;
printf ("Nhap phan tu can xoa: ");
scanf ("%d",&x);
Del_x (L,x);
printf ("DS sau khi xoa:\n");
Output(L);
break;
}
case 7: break;
}
}while (lua_chon !=7);
return 0;
}
Lỗi mà mình đang gặp là đoạn code của mình , khi mà mình nhập vào một dãy số sau khi in ra màn hình thì nó không in ra giá trị mà lại in ra địa chỉ của giá trị, còn code của anh quân thì mình copy về chạy thử thì nó in ra giá trị và chương trình hoạt động ngon lành, mình có thử so sánh code của mình với của anh quân và thấy không sai gì cả, nhưng mà mình chả biết code của mình bị lỗi gì luôn , mong các bạn giúp mình , xin cảm ơn.
P/s về cách truyền tham chiếu thì mình có chuyển sang c++(mình dùng code block), code của anh quân vẫn chạy được, code của mình cũng vậy , nhưng lại mắc lỗi như mình đã nêu ở trên .
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?