0的單向鏈表頭

我遇到了單鏈表問題。

當我在頭前插入東西時。head 總是有 0 個資料。我認為init_list()函式有問題。我認為 0 的頭部來自隨機初始化的資料。

沒有 head 0 問題，一切都很好。

我確定初始化方法是錯誤的。但是不知道怎么解決..

這是我的 I/0 和所需的輸出

Input

2
insert 0 1
size

Output I got

1->0->NULL
2
1->0->NULL

Desired Output

1->NULL
1
1->NULL

這是我的代碼

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h>

typedef int Element;
typedef struct LinkedNode {
    Element data;
    struct LinkedNode* link;
} Node;
Node* head;
void init_list() { 
    head = (Node*)malloc(sizeof(Node));
    head->link = NULL;
}
int is_empty() { 
    if (head == NULL) return 1;
    else return 0;
}

Node* get_entry(int pos)
{
    Node* p = head; 
    int i;
    for (i = 0; i < pos; i  , p=p->link){
        if (p == NULL) return NULL; 
    }
    return p;
}

int size() 
{
    Node* p;
    int count = 0;
    for (p = head; p != NULL; p = p->link)
        count  ; 
    return count;
}

void replace(int pos, Element val) 
{
    Node* node = get_entry(pos); 
    if (node != NULL) 
        node->data = val; // replace
}

Node* search_list(Element val) 
{
    Node* p;
    for (p = head; p != NULL; p = p->link) 
        if (p->data == val) return p;
    return NULL; 
}

void insert_next(Node * before, Node * node) 
{
    if (node != NULL) {
        node->link = before->link; 
        before->link = node; 
    }
}

void insert(int pos, Element val) 
{
    Node* new_node, * prev;
    new_node = (Node*)malloc(sizeof(Node)); 
    new_node->data = val; 
    if (pos == 0) { 
        new_node->link = head; 
        
        head = new_node; 
    }
    else {
        prev = get_entry(pos-1); 
        if (prev != NULL)
            insert_next(prev, new_node); 
        else free(new_node);
    }
}

Node * remove_next(Node * prev) 
{
    Node* removed = prev->link; 
    if (removed != NULL) {
        prev->link = removed->link;
    }
    return removed; 
}

void delete(int pos) 
{
    Node* prev, * removed;

    if (pos == 0 && is_empty() == 0) { 
        removed = get_entry(pos); 
        head = head->link;
        free(removed); 
    }
    else {
        prev = get_entry(pos-1); 
        if (prev != NULL) {
            remove_next(prev); 
            free(removed); 
        }
    }
}

void clear_list()
{
    while (is_empty() == 0) 
        delete(0);
}

void print_list()
{
    Node* p;
    for (p = head; p != NULL; p = p->link)
        printf("%d->", p->data);
    printf("NULL\n");
}

Node * concat_list(Node * new_node)
{
    if(is_empty()) return new_node; 
    else if(new_node == NULL) return new_node; 
    else{
        Node* p; 
        p = head;
        while (p->link != NULL) {
            p = p->link;
        } 
        p->link = new_node; 
        return head;
    }
}
int main(void)
{
    Element num;
    int pos;
    int n, i, j, len;
    char c[15];
    Node* tmp_head= NULL;
    Node* new_head= NULL;
    init_list();
    scanf("%d", &n);
    for (i = 0; i < n; i  )
    {
        scanf("%s", c);

        if (strcmp(c, "insert") == 0) { scanf("%d %d\n",&pos, &num); insert(pos,num); print_list();}
        else if (strcmp(c, "delete") == 0) { scanf("%d\n", &pos); delete(pos); print_list();}
        else if (strcmp(c, "size") == 0) {printf("%d\n", size()); print_list();}
        else if (strcmp(c, "empty") == 0) {printf("%d\n", is_empty()); print_list();}
        else if (strcmp(c, "getEntry") == 0) { scanf("%d\n", &pos); printf("%d\n", get_entry(pos)->data); print_list();}
        else if (strcmp(c, "search_list") == 0) { scanf("%d\n", &num); printf("%d\n", search_list(num)->data); print_list();}
        else if (strcmp(c, "replace") == 0) { scanf("%d %d\n", &pos, &num); replace(pos,num); print_list();}
        else if (strcmp(c, "concat_list") == 0) { 
            tmp_head = head;
            init_list();
            scanf("%d", &len);
            for (j = 0; j < len; j  )
            {
                scanf("%d %d\n",&pos, &num); insert(pos,num);
            }
            printf("new_node: ");
            print_list();
            new_head = head;
            head = tmp_head;
            head = concat_list(new_head); 
            print_list();
        }
        else printf("error\n");
    }
    return 0;
}

uj5u.com熱心網友回復：

基本問題是，在 內init_list，代碼只初始化link而不初始化data。我建議，而不是你初始化head到NULL，簡單地使用insert，以創建節點。

標籤：C 算法 数据结构 链表

上一篇：分而治之：多項式乘法時間復雜度

下一篇：仍然不理解Big-OvsWorstCaseTimeComplexity