C: Tạo danh sách theo thứ tự bằng cách kiểm tra 2 giá trị

Question

Tôi mới sử dụng C nên hãy kiên nhẫn với tôi nếu bạn thấy một số lỗi mới của người mới trong mã của tôi!

Là một phần của bài tập về nhà, tôi cần tạo danh sách theo thứ tự để lưu trữ một số dữ liệu. Những gì tôi đã làm cho đến nay là tạo cấu trúc sẽ đại diện cho mỗi nút của danh sách (firstNode là một biến toàn cục trỏ đến nút đầu tiên của danh sách):

typedef struct Node { 
    struct Node *next; 
    int id; 
    int value; 
}Node; 

Node *firstNode = NULL; 

Sau đó tôi đã tạo một hàm chèn một nút mới vào danh sách bằng cách kiểm tra các giá trị của các nút. Các nút có giá trị nhỏ hơn phải được đặt trước các giá trị khác. Vì vậy, những gì tôi đã làm là:

void addNewNode(int nodeId, int nodeValue) { 
    Node *newNode = (Node*) malloc(sizeof(Node)); 
    Node *temp, *tempPrev; 
    newNode->id = nodeId; 
    newNode->value = nodeValue; 

    if(firstNode == NULL) { 
     newNode->next = firstNode; 
     firstNode = newNode; 
    } 
    temp = firstNode; 
    tempPrev = NULL; 
    while(temp->value < newNode->value) { 
     tempPrev = temp; 
     temp = temp->next; 
    } 
    if(tempPrev == NULL) { 
     newNode->next = firstNode; 
     firstNode = newNode; 
    } 
    else { 
     tempPrev->next = newNode; 
     newNode->next = temp; 
    } 
} 

Vấn đề với mã ở trên đôi khi chương trình gặp sự cố, nhưng tôi không thể tìm thấy lỗi!

Ngoài ra, những gì tôi đang cố gắng làm tiếp theo là, nếu một số nút có cùng giá trị, thì chúng được sắp xếp theo id của chúng (các nút có ID nhỏ hơn đến trước). Tôi có thể làm cái này như thế nào? Tôi thực sự bối rối!

Answer 1

Các chương trình bị treo vì trong điều kiện vòng lặp while, bạn không kiểm tra xem tạm bằng để NULL. Nói cách khác, nếu bạn cố gắng chèn một nút mới có giá trị lớn hơn tất cả các nút khác đã có trong danh sách, temp đạt đến cuối danh sách (do đó temp bằng NULL) và bạn cố gắng lấy giá trị của nút đó ! Vì vậy, một sửa chữa sẽ là:

while(temp!=NULL && temp->value>newNode->value) 
{ 
    .... 
} 

Đối với các id của các nút, bạn có thể mở rộng điều kiện vòng lặp while của bạn như thế này:

while(temp!=NULL && (temp->value<newNode->value || (temp->value==newNode->value && temp->id<newNode->id)) 
{ 
    .... 
} 

Ngoài ra, người đầu tiên nếu-tuyên bố, nơi bạn kiểm tra xem firstNode là NULL, không cần thiết trong trường hợp của bạn. Nếu đó là NULL, chương trình sẽ không nhận được vào vòng lặp while và sẽ đi trực tiếp đến câu lệnh if đầu tiên sau vòng lặp while.

Bằng cách này, mã tốt đẹp cho một lập trình viên mới trong C :-)

Answer 2

1.

if(firstNode == NULL) { 
     newNode->next = firstNode; 
     firstNode = newNode; 
     return; // done with inserting the first node...need not continue. 
    } 

2.

// ensure temp is not null only then access its value. 
while(temp && (temp->value < nodeId->value)) { 
     tempPrev = temp; 
     temp = temp->next; 
    } 

Answer 3

cho một điều, bạn có nodeID -> giá trị trong đó. NodeID là một int, do đó, điều này sẽ không hoạt động.

Answer 4

Là một phương pháp gỡ lỗi, tôi sẽ tạo một khai thác thử nghiệm đơn giản. Nói cách khác, một chương trình thử nghiệm bạn viết chạy qua tất cả các tình huống phổ biến mà bạn có thể nghĩ đến (còn gọi là kiểm thử đơn vị). Mỗi bài kiểm tra đơn vị kiểm tra để đảm bảo rằng nó chạy đúng và tạo ra kết quả mong đợi. Bằng cách này, bạn có thể tự tin rằng nếu tất cả mọi thứ kiểm tra ok, bạn tốt để đi. Nếu một bài kiểm tra đơn vị không thành công, bạn biết chính xác những gì bị hỏng.

Answer 5

Tôi khuyên bạn nên xây dựng một vài trường hợp kiểm tra để kiểm tra điều kiện biên của bạn (ví dụ: thêm phần tử vào danh sách trống; thêm phần tử sẽ kết thúc ở trước danh sách hiện có; ở cuối danh sách hiện có, thêm phần tử sẽ kết thúc ở đâu đó ở giữa danh sách hiện có). Thực hiện chức năng "in" sẽ in các phần tử trong danh sách vào bảng điều khiển để gỡ lỗi. Điều đó ít nhất sẽ giúp bạn thu hẹp bối cảnh vụ tai nạn của bạn là gì. Một khả năng (tôi không biết có bao nhiêu bổ sung bạn đang làm) là chương trình hết bộ nhớ và malloc không thành công. Bạn có thể kiểm tra vì tôi nghĩ malloc trả về NULL nếu nó không cấp phát bộ nhớ cần thiết.

Node *newNode = (Node*) malloc(sizeof(Node)); 
if(newNode == NULL) 
{ 
    printf("Out of Memory!"); 
    return; 
}