Chưa hiểu được bản chất của danh sách liên kết đơn, mong được gải đáp

[huyenthoai (Interns)]

Khi chạy nó chỉ in ra bệnh nhân đầu tiên. Em nghĩ là XuatMotBN(l.pHeap->info, i); sai nhưng không hiểu tại sao nó lại sai, Và sẽ sửa nó như thế nào. Mọi người cố gáng đọc tí code của em hơi dài. Xin cảm ơn!

#include <stdio.h>
struct BN
{
	int maBN;
	char hoten[30];
	char ngaynhap[20];
	float vienphi;
};
struct Node
{
	BN info;
	Node *Next;
};
struct List
{
	Node *pHeap;
	Node *pTail;
};

Node* TaoMotNode(BN x)
{
	Node *p = new Node;
	if(p == NULL)
	{
		printf("khong du bo nho");
		return NULL;
	}
	p->info = x;
	p->Next = NULL;
	return p;	
}

void NhapMotBN(BN &bn)
{
	printf("Nhap ma so benh nhan: ");
	scanf("%d", &bn.maBN);
	printf("Nhap ho ten benh nhan: "); fflush(stdin);
	gets(bn.hoten);
	printf("Nhap ngay nhap vien: ");	fflush(stdin);
	gets(bn.ngaynhap);
	printf("Nhap vien phi: ");
	scanf("%f", &bn.vienphi);
}
void XuatMotBN(BN bn, int i)
{
	printf("%-3d %-5d %-20s %-10s %10.2f\n", i, bn.maBN, bn.hoten, bn.ngaynhap, bn.vienphi);
}
void ThemDauDS(List &l, Node *x)
{
	if(l.pHeap == NULL)	//ds rong
		l.pHeap = l.pTail = x;
		/*
		l.pHeap = x;
		l.pTail = l.pHeap;
		*/
	else
	{
		x->Next = l.pHeap;
		l.pHeap = x;
	}
}
void TaoDS(List &l, int &n)
{
	BN x;
	Node *p = new Node;
	
	for(int i=1; i<=n; i++)
	{
		NhapMotBN(x);
		p= TaoMotNode(x);
		ThemDauDS(l,p);
	}
	
}
void Output(List l)
{
	Node *p = l.pHeap;
	int i=1;
	printf("%-3s %-5s %-20s %-10s %10s\n", "STT", "MA BN", "HO TEN", "NGAY NHAP", "VIEN PHI");
	while(l.pHeap != NULL)
	{
		XuatMotBN(l.pHeap->info, i);  //có vấn đề
		i++;
        p = p->Next;
	}
}

void main()
{
	List l;
	l.pHeap = l.pTail = NULL; //tao danh sach rong
	int n;
	printf("Nhap so luong benh nhan: ");
	scanf("%d", &n);
	TaoDS(l,n);
	Output(l);
}

[tntxtnt]

while(l.pHeap != NULL)
{
XuatMotBN(l.pHeap->info, i); //có vấn đề
i++;
p = p->Next;
}

vòng lặp có vấn đề mới đúng. Có phải là in ra bệnh nhân đầu tiên liên tục rồi báo lỗi dereference NULL?

XuatMotBN(l.pHeap->info, i); ở đây l.pHeap ko thay đổi (mà chỉ có p thay đổi) vậy thì làm sao in ra đúng được. p trỏ tới bệnh nhân cần in, phải xuất p chứ ko phải xuất l.pHeap

và cuối cùng là điều kiện vòng lặp. l.pHeap cố định ko thay đổi thì vòng lặp chạy mãi? Với lại dòng p = p->Next; nếu p->Next là NULL vậy thì vòng lặp tiếp theo làm sao dereference nó để lấy p->Next được?

thêm mấy lỗi nữa (ko cần sửa vẫn chạy được nhưng ko ổn)

• Ko có hàm hủy/giải phóng List
• Trong hàm TaoDS(), p ban đầu trỏ vào 1 Node mà ko xài, cũng ko giải phóng => dù có viết hàm hủy thì cũng tràn bộ nhớ. Sửa lại là Node *p = NULL;
• Hàm TaoMotNode() thì truyền BN là truyền bản copy, mất công copy dư 1 bệnh nhân. Thêm 100 bệnh nhân là copy dư 100 bệnh nhân ko xài. Hơn nữa lại copy x vào p->info, như vậy là dư 1 lần copy nữa. Để nhập 1 bệnh nhân thì cần tới 3 struct BN (x trong TaoDS(), bản copy của x khi truyền vào hàm TaoMotNode(), và p->info trong hàm TaoMotNode()). Chỉ cần xài 1 bản là đủ rồi…
• Ngoài ra pHeap cũng sai chính tả… Heap là đống, head mới là đầu. pHead mới đúng chính tả…

[huyenthoai (Interns)]

Đã sửa rồi nhưng không hiểu tại sao nó lại in danh sách theo thứ tự từ cuối đi lên đầu bạn @tntxtnt ơi

[huyenthoai (Interns)]

p ban đầu trỏ vào 1 Node mà ko xài

Không hiểu cho lắm lúc đầu mình cấp phát bộ nhớ cho con trỏ p *Node p = new Node; và sau đó thì gán p= TaoMotNode(x); là đã dùng nó rồi nhỉ

[tntxtnt]

Node *p = new Node; là p đã trỏ tới 1 Node rồi, p= TaoMotNode(x); là p nó trỏ tới Node khác (được cấp phát trong hàm TaoMotNode). Vậy là 1 Node ban đầu bị thừa ko xài.

[tntxtnt]

từ cuối đi lên đầu là đúng rồi, tại bạn thêm Node vào pHead, ví dụ như xếp 1 chồng tập vậy. Thêm tập thì nó cao dần lên (head tăng, tail ko đổi), tập cuối cùng ở trên đầu. Khi lấy tập ra thì lấy từ trên xuống (head -> tail) vậy là lấy tập cuối rồi kế cuối rồi kế kế cuối v.v… tới tập đầu tiên.

muốn nó in đúng thì 1 là khi xuất ra xuất từ tail ngược về head. 2 là khi thêm node thì thêm vào phía sau tail chứ ko phải thêm vào phía trước head.

[huyenthoai (Interns)]

Hàm TaoMotNode() thì truyền BN là truyền bản copy, mất công copy dư 1 bệnh nhân. Thêm 100 bệnh nhân là copy dư 100 bệnh nhân ko xài. Hơn nữa lại copy x vào p->info, như vậy là dư 1 lần copy nữa. Để nhập 1 bệnh nhân thì cần tới 3 struct BN (x trong TaoDS(), bản copy của x khi truyền vào hàm TaoMotNode(), và p->info trong hàm TaoMotNode()). Chỉ cần xài 1 bản là đủ rồi…

Ok nhưng còn chỗ này mình chưa rõ cho lắm, Bạn giúp mình sửa lại hàm TaoMotNode() với

[tntxtnt]

à đây là dslk đơn thì ko đọc ngược từ tail về head được, phải thêm từ đuôi thôi.

[tntxtnt]

đơn giản lắm:

Node* TaoMotNode()
{
    Node *p = new Node;
    if (p == NULL)
    {
        printf("khong du bo nho");
        exit(1); //lỗi là thoát chương trình luôn
    }
    NhapMotBN(p->info); //nhập thẳng vào p->info. Như vậy là chỉ cần 1 struct BN
    p->Next = NULL;
    return p;    
}

hàm TaoDS chuyển thành 2 dòng:

void TaoDS(List &l, int n) //ko cần truyền tham chiếu n ở đây
{
    for(int i = 0; i < n; i++) //[0,n)
        ThemDauDS(l, TaoMotNode()); //ko có x ở đây...
}

TaoMotNode trả về con trỏ, lấy con trỏ đó cho vào ThemDauDS luôn, khỏi cần tạo biến trung gian.

hoặc nếu ko thích nhập bệnh nhân ở TaoMotNode thì có thể chuyển về TaoDS như ban đầu. Gọi NhapMotBN(l.pHead->info); sau khi ThemDauDS là được.

nếu muốn in xuôi thì viết hàm ThemDuoiDS (thêm vào đuôi). Chỉ sửa có 2 dòng trong ThemDauDS thôi.

[huyenthoai (Interns)]

ok thật là thâm thuý Phải nói là cảm ơn @tntxtnt rất nhiều! Nhưng còn chỗ này chưa hiểu lắm Hàm ThemDauDS()
x->Next = l.pHead;
l.pHead = x; //Lúc này pHead nó đã trỏ về đầu danh sách (1)

void Output(List l)
{
	Node *p = l.pHead;
	int i=1;
	printf("%-3s %-5s %-20s %-10s %10s\n", "STT", "MA BN", "HO TEN", "NGAY NHAP", "VIEN PHI");
	while(p != NULL)
	{
		XuatMotBN(p->info, i);
		i++;
        p = p->Next;
	}
}

Hàm Output() thì ta khởi tạo con trỏ p trỏ tới pHead (1) thì khi duyệt danh sách thì nó phải duyệt từ đầu chứ nhỉ

[tntxtnt]

bây giờ thêm 1 2 3 lần lượt vào đầu dslk:

thêm 1:
1
^ (pHead)
^ (pTail)

thêm 2:
2 1
^ (pHead)
  ^ (pTail)

thêm 3:
3 2 1
^ (pHead)
    ^ (pTail)

hay đơn giản là 1 rồi 2->1 rồi 3->2->1
thì nó bị thêm ngược rồi. Nếu thêm từ đuôi thì sẽ là 1 rồi 1->2 rồi 1->2->3

truy lần lượt từng dòng code là

• ban đầu: pHead trỏ tới 1, pTail trỏ tới 1
• x->Next = l.pHead; tức 2 trỏ tới địa chỉ mà pHead trỏ tới, tức là 1. Vậy là 2 trỏ tới 1, hay viết là 2->1. pHead vẫn trỏ tới 1, pTail vẫn trỏ tới 1
• l.pHead = x; pHead trỏ về 2.

Tương tự khi thêm 3 vào. Vậy là thành 3->2->1

[huyenthoai (Interns)]

ok đã thông não rồi cảm ơn @tntxtnt nhiều !

[tntxtnt]

viết hàm ThemDuoi đi. Có pTail rồi thì thêm cũng dễ mà

viết thêm hàm hủy nữa. Cũng lặp 1 vòng như khi in ra thôi, nhưng phải có thêm 1 con trỏ nữa để giữ địa chỉ Node tiếp theo cần delete, vì nếu delete con trỏ hiện tại thì ko thể lấy p = p->next được nữa.

[huyenthoai (Interns)]

Hàm thêm đuôi thì đã viết được còn huỷ với sắp xếp trên trường chưa học tới nhưng sẽ nghiên cứu làm tiếp có gì lên hỏi bạn nữa nhé

[huyenthoai (Interns)]

#include <stdio.h>
typedef struct BenhNhan
{
    int maBN;
    char hoten[30];
    char ngayNhap[20];
    float vienPhi;
}BN;
typedef struct Node
{
    BN info;
    Node *next;
}NODE;
typedef struct DanhSach
{
    Node *dau;
    Node *cuoi;
}DS;
void NhapMotBN(BN &bn)
{
    printf("\tMA SO BENH NHAN: ");
    scanf("%d", &bn.maBN);
    printf("\tHO TEN:          ");   fflush(stdin);
    gets(bn.hoten);
    printf("\tNGAY NHAP VIEN:  ");   fflush(stdin);
    gets(bn.ngayNhap);
    printf("\tVIEN PHI:        ");
    scanf("%f", &bn.vienPhi);
}
void XuatMotBN(BN bn, int i)
{
    printf("%-5d %-10d %-30s %-20s %-10.2f\n", i, bn.maBN, bn.hoten, bn.ngayNhap, bn.vienPhi);
}
NODE* TaoMotNode()
{
    NODE *p = new NODE;
    if(p == NULL)
    {
        printf("Khong du bo nho!");
        return NULL;
    }

    NhapMotBN(p->info);
    p->next = NULL;
    return p;
}
void ThemDau(DS &l)
{
    if(l.dau == NULL)
        l.dau = l.cuoi = TaoMotNode();
    else
    {
        TaoMotNode()->next = l.dau;
        l.dau = TaoMotNode();
    }
}
void ThemCuoi(DS &l)
{
    if(l.dau == NULL)
        l.dau = l.cuoi = TaoMotNode();
    else
    {
        l.cuoi->next = TaoMotNode();
        l.cuoi = TaoMotNode();
    }
}
void TaoDanhSachBN(DS &l, int n)
{
   for(int i=0; i<n; i++)
    {
        printf("Nhap thong tin benh nhan thu %d:\n", i+1);
        ThemCuoi(l);
    }
}
void XuatDanhSachBN(DS l)
{
    NODE *p = l.dau;
    int i=1;
    printf("%-5s %-10s %-30s %-20s %-10s\n", "STT", "MA SO", "HO TEN", "NGAY NHAP VIEN", "VIEN PHI");
    while(p!=NULL)
    {
        XuatMotBN(p->info, i);
        i++;
        p = p->next;
    }
}
int main()
{
    int key, n;
    char chon;
    DS ds;
    ds.dau = ds.cuoi = NULL;
    printf("-------------MENU-------------------\n");
    printf("1. Tao danh sach\n");
    printf("2. Nhap vao dau danh sach\n");
    printf("3. Nhap vao cuoi danh sach\n");
    printf("4. Xuat danh sach\n");

    do
    {
        printf("Ban chon: ");
        scanf("%d", &key);
        switch(key)
        {
            case 1:
                printf("Nhap so luong benh nhan: ");
                scanf("%d", &n);
                TaoDanhSachBN(ds,n);
                break;
            case 2:
                ThemDau(ds);
                break;
            case 3:
                ThemCuoi(ds);
                break;
            case 4:
                XuatDanhSachBN(ds);
                break;
            default:
                printf("Ban chon sai.\n");
                break;
        }
        printf("Ban co muon tiep tuc menu <c/k>: ");    fflush(stdin);
        scanf("%c", &chon);
    }while(chon == 'c' || chon == 'C');
}

không biết lỗi gì luôn @tntxtnt vào xem giúp sai chỗ nào thế nhỉ.

[tntxtnt]

    l.cuoi->next = TaoMotNode();
    l.cuoi = TaoMotNode();


    TaoMotNode()->next = l.dau;
    l.dau = TaoMotNode();

mỗi lần gọi TaoMotNode() là nó ra 1 node mới rồi. Chỉ gọi đc TaoMotNode() 1 lần thôi

trong ThemCuoi thì có thể sửa thành

l.cuoi->next = TaoMotNode();
l.cuoi = l.cuoi->next;

còn ThemDau thì chắc phải có 1 con trỏ trung gian:

Node *p newNode = TaoMotNode();
newNode->next = l.pHead;
l.pHead = newNode;

ThemCuoi trường hợp l.pHead != NULL có thể viết thành 1 dòng:

l.cuoi = l.cuoi->next = TaoMotNode();

vì toán tử ‘=’ được xét từ phải sang trái, nên l.cuoi->next = TaoMotNode(); được tính trước rồi trả về l.cuoi->next, sau đó l.cuoi = l.cuoi->next được tính tiếp. Thành ra có thể viết gộp lại 1 dòng.

ThemDau thì ko gộp được

[huyenthoai (Interns)]

Node *p newNode = TaoMotNode();

chỗ này là sao không hiểu phải là Node *newNode = TaoMotNode(); chứ nhỉ
Bạn xem giúp mình có cần chỉnh sửa chổ nào cho nó tối ưu ngon lành luôn

[tntxtnt]

ờ đúng rồi ta ghi nhầm, copy chỉnh sửa

tại vì nếu ghi là TaoMotNode()->next = l.dau; thì ko biết Node phía trước l.dau hay Node mới tạo ở đâu (ko có con trỏ nào trỏ vào nó). Nên phải có 1 node tạm thời, gọi là newNode ghi địa chỉ nó ở đâu, rồi mới “gắn” vào l được.

còn trong ThemCuoi thì do node mới thêm vào liền sau l.cuoi hay có l.cuoi->next trỏ tới nên biết là nó ở đâu.

[tntxtnt]

trong hàm xuất vòng lặp có thể viết gọn lại, xài for

printf("%-5s %-10s %-30s %-20s %-10s\n", "STT", "MA SO", "HO TEN", "NGAY NHAP VIEN", "VIEN PHI");
int i = 1;
for (Node *p = l.dau; p; p = p->next) //p để không như vậy có thể hiểu là p != NULL
    XuatMotBN(p->info, i++);

i++ trả về i rồi mới tăng giá trị của i, viết gộp với XuatMotBN thành 1 dòng.
khai báo p, check p != NULL, rồi gán p = p->next 3 dòng có thể gộp thành 1 dòng for

cái này là clean up cho code gọn hơn thôi ko ảnh hưởng gì tới performance cả.

.
.
.

void XuatMotBN(BN bn, int i);
sửa thành
void XuatMotBN(const BN &bn, int i)
nếu ko thì mỗi lần xuất 1 BN lại mất công copy ra 1 bản.

Luôn luôn truyền bản chính (tham chiếu &). Nếu ko phải chỉnh sửa gì thì thêm const vào. Trừ vài trường hợp mới truyền bản copy: mấy type nhỏ hay primitive types như int, float, double, char, v.v… ở đây struct BN cả trăm bytes nên truyền bản chính.

[huyenthoai (Interns)]

const trong trường hợp này có tác dụng gì nhỉ