0的单向链表头

Question

我遇到了单链表问题。

当我在头前插入东西时。 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;
}

Answer 1

基本问题是在 init_list 内，代码只初始化 link 而不是 data。我建议您将 head 初始化为 NULL 并简单地使用 insert 来创建节点。

0的单向链表头

Singly Linked List head of 0

c

algorithm

linked-list

data-structures