C语言 如何创建节点，然后将其添加到链接列表

Question

这是我目前为止所做的!我有点困惑，因为我不知道在哪里加上它们。我们在课堂上研究节点已经有一段时间了，但是即使你问问题，我的教授也不喜欢解释。这是我们的家庭作业。所以我想知道如何创建一个函数来添加节点到链接列表?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Node 
{ 
    double nodeData;
    int nodeLink;
};
void main(void)
{
    struct Node  List[15];
    int Begin, current;
    Begin = 0;
    for (current = Begin; current < 15; current++)
        List[current].nodeLink = 0;
    List[0].nodeData = 3.141593;
    List[0].nodeLink = -1;
    List[1].nodeData = 25.992;
    List[1].nodeLink = -1;
    List[0].nodeLink = 1;
    for (int i = Begin; i != -1; i = List[i].nodeLink)
        printf("%fn", List[i].nodeData);

}

Answer 1

Node.h

#ifndef NODE_H
#define NODE_H
struct Node {
    double nodeData;
    int nodeLink;
};
extern struct Node *new_Node(double value);
extern void free_Node(struct Node *node);
extern struct Node *next_Node(struct Node *node);
extern void add_to_last_Node(struct Node *list, struct Node *node);
#endif

---

Node.c

#include <stddef.h>
#include "Node.h"
#define NUM_OF_NODES 15
#define END_OF_NODE  -1
#define UNUSED       -2
static int initialized = 0;
static int current = 0;
static struct Node Node_pool[NUM_OF_NODES];
static void init(void){
    for(int i=0; i < NUM_OF_NODES; i++){
        Node_pool[i].nodeLink = UNUSED;
    }
    initialized = 1;
}
struct Node *new_Node(double value){
    if(!initialized)
        init();
    if(current < NUM_OF_NODES){
        Node_pool[current].nodeData = value;
        Node_pool[current].nodeLink = END_OF_NODE;
        return &Node_pool[current++];
    } else {
        for(int i=0; i < NUM_OF_NODES; ++i){
            if(Node_pool[i].nodeLink == UNUSED){
                Node_pool[i].nodeData = value;
                Node_pool[i].nodeLink = END_OF_NODE;
                return &Node_pool[i];
            }
        }
        return NULL;
    }
}
void free_Node(struct Node *node){
    node->nodeLink = UNUSED;
}
struct Node *next_Node(struct Node *node){
    return node->nodeLink < 0 ? NULL : Node_pool + node->nodeLink;
}
void add_to_last_Node(struct Node *list, struct Node *node){
    if(!list || !node)
        return ;
    struct Node *temp = list, *prev = NULL;
    while(temp = next_Node(prev = temp))
        ;
    prev->nodeLink = node - Node_pool;
}

---

c

#include <stdio.h>
#include "Node.h"
int main(void){
    struct Node *begin, *aNode, *temp;
    begin = new_Node(3.141593);
    aNode = new_Node(25.992);
    add_to_last_Node(begin, aNode);
    aNode = new_Node(2.2360679);
    add_to_last_Node(begin, aNode);
    for(temp = begin; temp != NULL; temp = next_Node(temp))
        printf("%fn", temp->nodeData);
    temp = begin;
    while(temp){
        struct Node *save = temp;
        temp = next_Node(temp);
        free_Node(save);
    }
    return 0;
}

---

>gcc main.c Node.c -std=c99 -o sample
>sample
3.141593
25.992000
2.236068

Answer 2

链表的字面意思是:它是一个节点列表，所有节点都指向下一个节点(顺便说一下，nodeLink应该是node *类型，而不是int)，以形成彼此之间的链接。一个基本的单向链表将跟踪头部指针(这也只是一个节点*)，并使用它来递归下一行(从头部开始，得到下一个指针，然后得到下一个指针，然后从下一个…)，直到你找到你想要影响的位置，或者直到下一个nodeLink为NULL。从那里它只是创建一个新的节点，并分配相应的nodeLink值:

Node* newNode = new Node();
newNode->nodeData = 3.14d;
currentNode->nodeLink = newNode;

如果由于某种原因需要为整型，可以使用重新解释强制转换:

Node* currentNode = reinterpret_cast<Node*>(currentNode->nodeLink); // Grab the next link
currentNode->nodeLink = reinterpret_cast<int>(newNode); // Do the assignment

但是这将在sizeof(void*) != sizeof(int)的系统上中断，比如x86_64系统，所以这就是为什么@Michael在评论中说应该是一个实际的指针值，而不是int。毫无理由地做这样的事情通常也是糟糕的编程实践。

Answer 3

下面是一个可能的函数签名:

#define MAXIMUM_NODES 15
void Add_To_List(double value, Node singly_list[MAXIMUM_NODES])
{
}

你可以从你的main函数调用它:

  Add_To_List(3.14159, list);