9

我正在创建一个链接列表,就像我问的上一个问题一样。我发现开发链表的最佳方法是将头部和尾部置于另一种结构中。我的产品结构将嵌套在这个结构中。我应该将列表传递给添加和删除的函数。我觉得这个概念很混乱。

我已经实现了初始化、添加和清理。但是,我不确定我是否正确地做到了这一点。

当我将产品添加到列表中时,我使用 calloc 声明了一些内存。但我在想我不应该为产品声明内存。我真的很困惑这个添加。

非常感谢您的任何建议,

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

#define PRODUCT_NAME_LEN 128

typedef struct product_data 
{
    int product_code;
    char product_name[PRODUCT_NAME_LEN];
    int product_cost;
    struct product_data_t *next;
}product_data_t;

typedef struct list 
{
    product_data_t *head;
    product_data_t *tail;
}list_t;

void add(list_t *list, int code, char name[], int cost); 
void initialize(list_t *list);
void clean_up(list_t *list);

int main(void)
{
    list_t *list = NULL;

    initialize(list);
    add(list, 10, "Dell Inspiron", 1500);
    clean_up(list);

    getchar();

    return 0;
}

void add(list_t *list, int code, char name[], int cost)
{
    // Allocate memory for the new product
    list = calloc(1, sizeof(list_t));
    if(!list)
    {
        fprintf(stderr, "Cannot allocated memory");
        exit(1);
    }

    if(list)
    {
        // First item to add to the list
        list->head->product_code = code;
        list->head->product_cost = cost;
        strncpy(list->head->product_name, name, sizeof(list->head->product_name));
        // Terminate the string
        list->head->product_name[127] = '/0';
    } 
}

// Initialize linked list
void initialize(list_t *list)
{
    // Set list node to null
    list = NULL;
    list = NULL;
}

// Release all resources
void clean_up(list_t *list)
{    
    list_t *temp = NULL;

    while(list)
    {
        temp = list->head;
        list->head = list->head->next;
        free(temp);    
    }
    list = NULL;
    list = NULL;
    temp = NULL;
}

===============================已编辑=================== =========

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

#define PRODUCT_NAME_LEN 64

// typedef struct product_data product_data_t;
typedef struct product_data 
{
    int product_code;
    char product_name[PRODUCT_NAME_LEN];
    int product_cost;
}product_data_t;

typedef struct list
{
    struct list *head;
    struct list *tail;
    struct list *next;
    struct list *current_node;
    product_data_t *data;

}list_t;

void add(list_t *list, int code, char name[], int cost); 

int main(void)
{
    list_t *list = NULL;
    list = initialize(list);
    add(list, 1001, "Dell Inspiron 2.66", 1299);

    add(list, 1002, "Macbook Pro 2.66", 1499);

    clean_up(list);

    getchar();

    return 0;
}

void add(list_t *list, int code, char name[], int cost)
{
    /* Allocate memory for the new product */
    product_data_t *product = (product_data_t*) calloc(1, sizeof(*product));
    if(!product)
    {
        fprintf(stderr, "Cannot allocate memory.");
        exit(1);
    }

    /* This is the first item in the list */
    product->product_code = code;
    product->product_cost = cost;
    strncpy(product->product_name, name, sizeof(product->product_name));
    product->product_name[PRODUCT_NAME_LEN - 1] = '\0';

    if(!list->head)
    {
        /* Assign the address of the product. */
        list = (list_t*) product;   
        /* Set the head and tail to this product */
        list->head = (list_t*) product;
        list->tail = (list_t*) product;
    }
    else
    {
        /* Append to the tail of the list. */
        list->tail->next = (list_t*) product;
        list->tail = (list_t*) product;
    }

    /* Assign the address of the product to the data on the list. */
    list->data = (list_t*) product;
}
4

14 回答 14

6

可以说,您希望您的列表数据结构位于其存储的数据之外。

假设你有:

结构随便
{
   诠释 x_;
}

然后您的列表结构将如下所示:

结构Whatever_Node
{
   不管_Node* next_
   随便*数据_
}

Ryan Oberoi 发表了类似的评论,但没有示例。

于 2009-06-11T17:25:27.563 回答
5

如果您希望更好地了解链表的基础知识,请查看以下文档:

http://cslibrary.stanford.edu/103/LinkedListBasics.pdf

于 2009-06-11T17:16:21.623 回答
4

在您的情况下,头部和尾部可以简单地指向链表的开头和结尾。对于单链表,真正需要的只是头部。在最基本的情况下,可以通过使用如下结构来制作链表:

typedef struct listnode
{
   //some data
   struct listnode *next;
}listnodeT;

listnodeT *list;
listnodeT *current_node;
list = (listnodeT*)malloc(sizeof(listnodeT));
current_node = list;

并且只要列表始终指向列表的开头并且最后一项设置为 NULL,就可以了,可以使用 current_node 遍历列表。但有时为了使遍历列表更容易并存储有关列表的任何其他数据,使用头和尾标记,并将其包装到它们自己的结构中,就像您所做的那样。那么您的添加和初始化函数将类似于(减去错误检测)

    // Initialize linked list
void initialize(list_t *list)
{
    list->head = NULL;
    list->tail = NULL;
}

void add(list_t *list, int code, char name[], int cost)
{
    // set up the new node
    product_data_t *node = (product_data_t*)malloc(sizeof(product_data_t));
    node->code = code;
    node->cost = cost;
    strncpy(node->product_name, name, sizeof(node->product_name));
    node->next = NULL;

    if(list->head == NULL){ // if this is the first node, gotta point head to it
        list->head = node;
        list->tail = node;  // for the first node, head and tail point to the same node
    }else{
        tail->next = node;  // append the node
        tail = node;        // point the tail at the end
    }
}

在这种情况下,因为它是一个单链表,所以尾部仅在将项目附加到列表时才真正有用。要插入一个项目,您必须从头部开始遍历列表。尾部真正派上用场的是双向链表,它允许您从任一端开始遍历列表。你可以像这样遍历这个列表

// return a pointer to element with product code
product_data_t*  seek(list_t *list, int code){
   product_data_t* iter = list->head;
   while(iter != NULL)
       if(iter->code == code)
           return iter;
       iter = iter->next;
   }
   return NULL; // element with code doesn't exist
}

通常,头部和尾部是完全构造的节点,它们本身用作标记来表示列表的开头和结尾。他们自己不存储数据(更确切地说,他们的数据代表一个哨兵令牌),他们只是正面和背面的占位符。这可以使编写一些处理链表的算法更容易,但代价是必须有两个额外的元素。总的来说,链表是灵活的数据结构,有多种实现方式。

哦,是的,nik 是对的,使用链表是一个很好的方法来获得指针和间接。它们也是练习递归的好方法!熟练使用链表后,接下来尝试构建一棵树并使用递归遍历这棵树。

于 2009-06-11T19:04:05.000 回答
2

我不是在这里编写代码,但您需要执行以下操作:

  • 创建列表对象,这将在程序长度内保持全局。
  • malloc 产品的大小_data_t。
  • 对于第一个元素(head 为 NULL),将 head 指向 malloced 的地址。
  • 要添加下一个元素,请移动到列表的末尾,然后将分配地址的指针添加到最后一个元素的下一个。(最后一个元素的下一个将始终为 NULL,所以这就是您遍历到结束的方式。)
  • 暂时忘记尾巴。
于 2009-06-11T17:20:49.413 回答
2

如果您正在学习 C 指针理论,这是一个很好的练习。否则,对于非通用代码(如库中的代码)来说,感觉太多间接了。

与其分配一个静态的 128 字节字符串,您可能想要做更多的指针练习,并使用您在退出时清理的已分配的精确长度字符串。

在学术上,kungfucraigs 的结构看起来比您定义的结构更通用。

于 2009-06-11T17:25:46.937 回答
1

在内存中,您的项目由列表结构中的指针链接

项目 1 -> 项目 2

为什么不将列表结构作为项目的一部分?

然后你分配一个产品项目,列表结构就在其中。

typedef struct product_data 
{
    int product_code;
    char product_name[PRODUCT_NAME_LEN];
    int product_cost;
    struct list_t list; // contains the pointers to other product data in the list
}product_data_t;
于 2009-06-11T17:16:30.860 回答
1

您正在为您的 list_t 结构分配空间,只是指向列表头和尾的指针,这不是您想要做的。

添加到链表时,为链表中的实际节点分配空间,即您的 product_data_t 结构。

于 2009-06-11T17:19:13.427 回答
1

您分配了错误的内存块。您不是为每个列表元素分配内存,而是为列表头和尾分配内存。

为简单起见,去掉头部和尾部的单独结构。使它们成为全局变量(它们现在所在的范围相同)并将它们更改为 listhead 和 listtail。这将使代码更具可读性(您不会不必要地通过单独的结构)并且您不会犯分配错误结构的错误。

除非您要创建一个双向链表,否则您不需要尾指针。创建链表后,它不是要添加的主要元素,但也不是必需的。

于 2009-06-11T17:20:00.587 回答
1

我认为你首先需要想象后端。代码并不重要。去这里可视化所有插入的后端基本 c 代码。1)在开始时插入访问并滚动以在后端执行每条指令 你需要前端和想象到这里 后端想象

以及所有其他可能的插入。

重要的是你可以用这种方式。

结构节点{
int data;//数据字段
struct Node*next;//指针字段
};

结构节点*头,*尾;// 试试这个方法

或捷径

结构节点{
int data;//数据字段
struct Node*next;//指针字段
}*头,*尾;//全局根指针

<<点击>> 可视化其他链表问题。

谢谢。

于 2018-03-04T11:25:27.053 回答
1

单链表的演示。如果您愿意,请尝试检查Circular Linked ListDouble Linked List

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


typedef struct node {
    int val;
    struct node * next;
} node_t;


// Iterating over a list
void
print_list(node_t *head)
{
    node_t *current = head;

    while(current != NULL)
    {
        printf("%d\n", current->val);
        current = current->next;
    }
}


// Adding an item to the end of the list
void
push_end(node_t *head, int val)
{
    node_t *current = head;
    while (current->next != NULL)
    {
        current = current->next;
    }

    current->next = malloc(sizeof(node_t));
    current->next->val = val;
    current->next->next = NULL;
}

// Adding an item to the head of the list
void
push_head(node_t **head, int val)
{
    node_t *new_node = NULL;

    new_node = malloc(sizeof(node_t));
    new_node->val = val;
    new_node->next = *head;

    *head = new_node;
}

// Removing the head item of the list
int
pop_head(node_t **head)
{
    int retval = -1;
    node_t *next_node = NULL;

    if (*head == NULL) {
        return -1;
    }

    next_node = (*head)->next;
    retval = (*head)->val;
    free(*head);
    *head = next_node;

    return retval;
}

// Removing the last item of the list
int
pop_last(node_t *head)
{
    int retval = 0;
    node_t *current = NULL;

    if (head->next == NULL) {
        retval = head->val;
        free(head);
        return retval;
    }

    /* get to the second to last node in the list */
    current = head;
    while (current->next->next != NULL) {
        current = current->next;
    }

    /* now current points to the second to last item of the list.
       so let's remove current->next */
    retval = current->next->val;
    free(current->next);
    current->next = NULL;

    return retval;
}

// Removing a specific item
int
remove_by_index(node_t **head, int n)
{
    int i = 0;
    int retval = -1;
    node_t *current = *head;
    node_t *temp_node = NULL;

    if (n == 0) {
        return pop_head(head);
    }

    for (i = 0; i < n - 1; i++) {
        if (current->next == NULL) {
            return -1;
        }
        current = current->next;
    }

    temp_node = current->next;
    retval = temp_node->val;
    current->next = temp_node->next;
    free(temp_node);

    return retval;
}


int
main(int argc, const char *argv[])
{
    int i;
    node_t * testnode;

    for (i = 0; i < argc; i++)
    {
        push_head(&testnode, atoi(argv[i]));
    }

    print_list(testnode);

    return 0;
}

// http://www.learn-c.org/en/Linked_lists
// https://www.geeksforgeeks.org/data-structures/linked-list/
于 2018-05-31T05:18:39.867 回答
1

受 Linux 内核中使用的实现启发的链表实现:

// for 'offsetof', see: https://stackoverflow.com/q/6433339/5447906.
#include <stddef.h>

// See: https://stackoverflow.com/q/10269685/5447906.
#define CONTAINER_OF(ptr, type, member) \
    ( (type *) ((char *)(ptr) - offsetof(type, member)) )

// The macro can't be used for list head.
#define LIST_DATA(ptr, type, member) \
    CONTAINER_OF(ptr, type, member);

// The struct is used for both: list head and list nodes.
typedef struct list_node
{
    struct list_node *prev, *next;
}
list_node;

// List heads must be initialized by this function.
// Using the function for list nodes is not required.
static inline void list_head_init(list_node *node)
{
    node->prev = node->next = node;
}

// The helper function, mustn't be used directly.
static inline void list_add_helper(list_node *prev, list_node *next, list_node *nnew)
{
    next->prev = nnew;
    nnew->next = next;
    nnew->prev = prev;
    prev->next = nnew;
}

// 'node' must be a list head or a part of a list.
// 'nnew' must not be a list head or a part of a list. It may
//   be uninitialized or contain any data (even garbage).
static inline void list_add_after(list_node *node, list_node *nnew)
{
    list_add_helper(node, node->next, nnew);
}

// 'node' must be a list head or a part of a list.
// 'nnew' must not be a list head or a part of a list. It may
//   be uninitialized or contain any data (even garbage).
static inline void list_add_before(list_node *node, list_node *nnew)
{
    list_add_helper(node->prev, node, nnew);
}

// 'node' must be part of a list.
static inline list_node *list_del(list_node *node)
{
    node->prev->next = node->next;
    node->next->prev = node->prev;
    return node->prev;
}

使用示例:

#include <stdio.h>

// The struct must contain 'list_node' to be able to be inserted to a list
typedef struct
{
    int       data;
    list_node node;
}
my_struct;

// Convert 'list_node *' to 'my_struct*' that contains this 'list_node'
static inline my_struct* get_my_struct(list_node *node_ptr)
{
    return LIST_DATA(node_ptr, my_struct, node);
}

void print_my_list(list_node *head)
{
    printf("list: {");
    for (list_node *cur = head->next; cur != head; cur = cur->next)
    {
        my_struct *my = get_my_struct(cur);
        printf(" %d", my->data);
    }
    printf(" }\n");
}

// Print 'cmd' and run it. Note: newline is not printed.
#define TRACE(cmd) \
    (printf("%s -> ", #cmd), (cmd))

int main()
{
    // The head of the list and the list itself. It doesn't contain any data.
    list_node head;
    list_head_init(&head);

    // The list's nodes, contain 'int' data in 'data' member of 'my_struct'
    my_struct el1 = {1};
    my_struct el2 = {2};
    my_struct el3 = {3};

    print_my_list(&head); // print initial state of the list (that is an empty list)

    // Run commands and print their result.
    TRACE( list_add_after (&head    , &el1.node) ); print_my_list(&head);
    TRACE( list_add_after (&head    , &el2.node) ); print_my_list(&head);
    TRACE( list_add_before(&el1.node, &el3.node) ); print_my_list(&head);
    TRACE( list_del       (head.prev)            ); print_my_list(&head);
    TRACE( list_add_before(&head    , &el1.node) ); print_my_list(&head);
    TRACE( list_del       (&el3.node)            ); print_my_list(&head);

    return 0;
}

上面代码的执行结果:

list: { }
list_add_after (&head , &el1.node) -> list: { 1 }
list_add_after (&head , &el2.node) -> list: { 2 1 }
list_add_before(&el1.node, &el3.node) -> list: { 2 3 1 }
list_del (head.prev) -> list: { 2 3 }
list_add_before(&head , &el1.node) -> list: { 2 3 1 }
list_del (&el3.node) -> list: { 2 1 }

http://coliru.stacked-crooked.com/a/6e852a996fb42dc2

当然,在现实生活中,您很可能会使用malloc列表元素。

于 2018-05-31T07:46:39.673 回答
0

在 C 语言中,我们需要定义一个 Node 来存储一个整数数据和一个指向下一个值的指针。

struct Node{
    int data;
    struct Node *next;
};

为了添加一个新节点,我们有一个函数 add ,它有一个 int 参数的数据。首先,我们创建一个新节点 n。如果程序没有创建 n,那么我们打印一条错误消息并返回值 -1。如果我们创建 n 然后我们将 n 的数据设置为具有参数的数据,并且下一个将包含根,因为它具有堆栈的顶部。之后,我们将根设置为引用新节点 n。

于 2017-05-24T03:56:31.990 回答
0
#include <stdio.h>
struct node
 {
  int data;
  struct node* next;
 };

int main()
{

//create pointer node for every new element

struct node* head = NULL;
struct node* second = NULL;
struct node* third = NULL;

//initialize every new pointer with same structure memory

head = malloc(sizeof(struct node));
second = malloc(sizeof(struct node));
third = malloc(sizeof(struct node));

head->data = 18;
head->next = second;

second->data = 20;
second->next = third;


third->data = 31;
third->next = NULL;

//print the linked list just increment by address 

  for (int i = 0; i < 3; ++i)
    {
      printf("%d\n",head->data++);
      return 0;
    }
 }

这是了解指针如何与指针一起工作的简单方法。在这里,您只需使用新节点创建指针增量,以便我们可以将其设为自动。

于 2017-10-11T13:14:16.933 回答
-1

走 STL 路线。声明链表应该与数据无关。如果你真的要自己写,看看它是如何在 STL 或 Boost 中实现的。

您甚至不应该在数据结构中保留 *next 指针。这允许您在各种数据结构中使用您的产品数据结构 - 树、数组和队列。

希望这些信息对您的设计决策有所帮助。

编辑:

由于该帖子标记为 C,因此您可以使用遵循基本设计原则的 void* 指针进行等效实现。例如,请查看:

文档| 列表.c | 列表.h

于 2009-06-11T17:23:08.847 回答