用C链表 [英] linked list in C
问题描述
我创建href=\"http://stackoverflow.com/questions/973654/single-linked-list\">链表作为在previous问题，我问一个 我已经实现了初始化，添加和CLEAN_UP。但是，我不知道，我已经正确地做到这一点。 当我将产品添加到列表中，我宣布使用释放calloc一些内存。不过，我想我不应该被宣布该产品的内存而不是。我真搞不清楚这个增加。 非常感谢您的任何建议，
的#include＆LT;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;
＃包括LT＆;＆string.h中GT;＃定义PRODUCT_NAME_LEN 128typedef结构product_data
{
INT product_ code;
焦炭PRODUCT_NAME [PRODUCT_NAME_LEN]
INT product_cost;
结构product_data_t *接下来的;
} product_data_t;typedef结构列表
{
product_data_t *头;
product_data_t *尾;
} list_t;无效添加（list_t *名单，诠释code，CHAR名称[]，诠释成本）;
void初始化（list_t *清单）;
无效CLEAN_UP（list_t *清单）;INT主要（无效）
{
list_t *名单= NULL; 初始化（清单）;
添加（列表，10，戴尔Inspiron，1500）;
CLEAN_UP（名单）; 的getchar（）; 返回0;
}无效添加（list_t *名单，诠释code，CHAR名称[]，诠释成本）
{
//分配内存为新产品
清单=释放calloc（1，sizeof的（list_t））;
如果（！名单）
{
fprintf中（标准错误，无法分配内存）;
出口（1）;
} 如果（名单）
{
//第一项添加到列表
列表 - ＆GT;流浆＆GT; product_ code = code;
列表 - ＆GT;流浆＆GT; product_cost =成本;
函数strncpy（列表 - ＆GT;流浆＆GT; PRODUCT_NAME，名称的sizeof（列表 - ＆GT;流浆＆GT; PRODUCT_NAME））;
//终止字符串
列表 - ＆GT;流浆＆GT; PRODUCT_NAME [127] ='/ 0';
}
}//初始化链表
void初始化（list_t *名单）
{
//设置列表节点为null
名单= NULL;
名单= NULL;
}//释放所有的资源
无效CLEAN_UP（list_t *名单）
{
list_t * TEMP = NULL; 而（名单）
{
TEMP =列表 - ＆GT;头;
列表 - ＆GT;头=列表 - ＆GT;流浆＆gt;接下来，
免费（TEMP）;
}
名单= NULL;
名单= NULL;
TEMP = NULL;
}
==============================编辑================ ============
的#include＆LT;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;
＃包括LT＆;＆string.h中GT;＃定义PRODUCT_NAME_LEN 64// typedef结构product_data product_data_t;
typedef结构product_data
{
INT product_ code;
焦炭PRODUCT_NAME [PRODUCT_NAME_LEN]
INT product_cost;
} product_data_t;typedef结构列表
{
结构列表*头;
结构列表*尾;
结构列表*接下来的;
结构列表* CURRENT_NODE;
product_data_t *数据;} list_t;无效添加（list_t *名单，诠释code，CHAR名称[]，诠释成本）;INT主要（无效）
{
list_t *名单= NULL;
清单=初始化（清单）;
添加（列表中，1001，戴尔Inspiron 2.66，1299）; 添加（列表中，1002，MacBook Pro的2.66，1499）; CLEAN_UP（名单）; 的getchar（）; 返回0;
}无效添加（list_t *名单，诠释code，CHAR名称[]，诠释成本）
{
/ *分配内存为新产品* /
product_data_t *产品=（product_data_t *）释放calloc（1，sizeof的（*产品））;
如果（！产品）
{
fprintf中（标准错误，无法分配内存。）;
出口（1）;
} / *这是在该列表中的第一项* /
产品展示＆GT; product_ code = code;
产品展示＆GT; product_cost =成本;
函数strncpy（产品 - ＆GT; PRODUCT_NAME，名称的sizeof（产品 - ＆GT; PRODUCT_NAME））;
产品展示＆GT; PRODUCT_NAME [PRODUCT_NAME_LEN - 1] ='\\ 0'; 如果（列表 - ＆GT;！头）
{
/ *分配产品的地址。 * /
名单=（list_t *）的产品;
/ *头尾设置为这个产品* /
列表 - ＆GT;头=（list_t *）的产品;
列表 - ＆GT;尾=（list_t *）的产品;
}
其他
{
/ *追加到列表的尾部。 * /
列表 - ＆GT; tail-＆gt;接下来=（list_t *）的产品;
列表 - ＆GT;尾=（list_t *）的产品;
} / *产物的地址分配给列表中的数据。 * /
列表 - ＆GT;数据=（list_t *）的产品;
}
在你的情况下，头部和尾部可以简单地指向一个链表的开始和结束。用单链表，是真正需要的只有头部。在它的最基本的，一个链表可以通过使用就像一个结构进行：
typedef结构listnode
{
//一些数据
结构listnode *接下来的;
} listnodeT;listnodeT *名单;
listnodeT * CURRENT_NODE;
名单=（listnodeT *）malloc的（的sizeof（listnodeT））;
CURRENT_NODE =清单;
只要列表始终指向列表的开头和最后一个项目旁边都有设置为NULL，你没事，并且可以使用CURRENT_NODE遍历列表。但有时使遍历列表更容易和任何其他数据存储有关的列表中，头部和尾部标记被使用，并包裹成自己的结构，像已完成。于是你的插件和初始化功能将类似（负误差检测）
//初始化链表
void初始化（list_t *名单）
{
列表 - ＆GT;头= NULL;
列表 - ＆GT;尾= NULL;
}无效添加（list_t *名单，诠释code，CHAR名称[]，诠释成本）
{
//设置新节点
product_data_t *节点=（product_data_t *）malloc的（的sizeof（product_data_t））;
与于节点GT; code = code;
与于节点GT;成本=成本;
函数strncpy（与于节点GT; PRODUCT_NAME，名称的sizeof（与于节点GT; PRODUCT_NAME））;
于节点＆gt;接着= NULL; 如果（列表 - ＆GT;头== NULL）{//如果这是第一个节点，总得点的头吧
列表 - ＆GT;头=节点;
列表 - ＆GT;尾=节点; //为第一个节点，头部和尾部指向同一节点
}其他{
tail-＆gt;接下来=节点; //添加节点
尾=节点; //在终点的尾巴
}
}
在这种情况下，因为它是一个单链接列表，尾部只用于附加项列表真正有用。要插入一个项目，你必须遍历起始于头部列表。凡尾巴真的派上用场是一个双向链表，它可以让你遍历列表起始于两端。你可以遍历该列表像
//返回一个指向元素与产品code
product_data_t *寻求（list_t *名单，诠释code）{
product_data_t * ITER =列表 - ＆GT;头;
而（ITER！= NULL）
如果（iter-＆GT; code == code）
返回ITER;
ITER = iter-＆gt;接下来，
}
返回NULL; //用code元素不存在
}
很多时候，头部和尾部被完全构造本身用作定点表示列表的开始和结束的节点。他们不存储数据本身（而不是很好，他们的数据重新present定点令牌），他们只是占位的正面和背面。这可以更容易地code一些算法在具有有两个额外的元素的费用与链表处理。总体而言，链表与几种方式灵活的数据结构来实现它们。
噢，和尼克是正确的，具有链接列表播放是一个伟大的方式获得良好的指针和间接。而且他们也练习过递归的好方法！你已经得到了很好的使用链表后，尝试构建下一个一棵树，用递归遍历树。
I am creating a linked list as in the previous question I asked. I have found that the best way to develop the linked list is to have the head and tail in another structure. My products struct will be nested inside this structure. And I should be passing the list to the function for adding and deleting. I find this concept confusing.
I have implemented the initialize, add, and clean_up. However, I am not sure that I have done that correctly.
When I add a product to the list I declare some memory using calloc. But I am thinking shouldn't I be declaring the memory for the product instead. I am really confused about this adding.
Many thanks for any suggestions,
#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;
}
============================== Edited ============================
#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;
}
In your case the head and tail could simply point to the beginning and end of a linked-list. With a singly linked-list, only the head is really needed. At it's most basic, a linked-list can be made by using just a struct like:
typedef struct listnode
{
//some data
struct listnode *next;
}listnodeT;
listnodeT *list;
listnodeT *current_node;
list = (listnodeT*)malloc(sizeof(listnodeT));
current_node = list;
and as long as list is always pointing to the beginning of the list and the last item has next set to NULL, you're fine and can use current_node to traverse the list. But sometimes to make traversing the list easier and to store any other data about the list, a head and tail token are used, and wrapped into their own structure, like you have done. So then your add and initialize functions would be something like (minus error detection)
// 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
}
}
In this case, since it's a singly linked-list, the tail is only really useful for appending items to the list. To insert an item, you'll have to traverse the list starting at the head. Where the tail really comes in handy is with a doubly-linked list, it allows you to traverse the list starting at either end. You can traverse this list like
// 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
}
Often times, the head and tail are fully constructed nodes themselves used as a sentinel to denote the beginning and end of a list. They don't store data themselves (well rather, their data represent a sentinel token), they are just place holders for the front and back. This can make it easier to code some algorithms dealing with linked lists at the expense of having to have two extra elements. Overall, linked lists are flexible data structures with several ways to implement them.
oh yeah, and nik is right, playing with linked-lists are a great way to get good with pointers and indirection. And they are also a great way to practice recursion too! After you have gotten good with linked-list, try building a tree next and use recursion to walk the tree.
这篇关于用C链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
