单链表 [英] Single linked list
本文介绍了单链表的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我创建了一个单链表。一切工作正常。
我只是想知道，如果我在code做了什么潜在的危险。在code段，我关心的是我的PUSH，POP，和清理。在code的部分仅仅是用户交互所以并不重要（我张贴无论如何，这样它在我在做什么，更清晰）。就在链表的应用程序。
任何建议非常感谢，因为这是我的拳头尝试。
的#include＆LT;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;
＃包括LT＆;＆string.h中GT;typedef结构product_data product_data_t;
结构product_data
{
INT product_ code;
CHAR PRODUCT_NAME [128];
INT product_cost;
product_data_t *接下来的;
};静态product_data_t *头= NULL;
静态product_data_t *尾= NULL;
静态product_data_t * new_product = NULL;//到列表推的产物。
无效的push（INT code，CHAR名称[]，诠释成本）;
//流行（删除）从列表中的产品。
无效POP（INT code）;
//显示列表中的所有产品。
无效display_list（）;
//删除列表中分配的所有内存
无效CLEAN_UP（）;
//显示菜单
无效菜单（）;INT主要（无效）
{
菜单（）; 的getchar（）; 返回0;
}无效的push（INT code，CHAR名称[]，诠释成本）
{
//分配内存为新产品
new_product =释放calloc（1，sizeof的（product_data_t））;
如果（！new_product）
{
fprintf中（标准错误，无法分配内存）;
出口（1）;
} / *填充新产品元素的字段* /
new_product-＆GT; product_ code = code;
函数strncpy（new_product-＆GT; PRODUCT_NAME，名称的sizeof（new_product-＆GT; PRODUCT_NAME））;
new_product-＆GT; product_cost =成本;
new_product-＆gt;接着= NULL; //设置链表的头和尾
如果（头== NULL）
{
//首先，只有产品
头= new_product;
}
其他
{
tail-＆gt;接下来= new_product;
} 尾= new_product;
}//查找code的产品和删除
无效POP（INT code）
{
product_data_t *产品=头;
product_data_t * TEMP = NULL;
product_data_t * previous =头;
INT发现= 0; // 0 - 没有找到，1 - 发现 如果（！头）
{
看跌期权（以下简称列表为空）;
返回;
} 而（产品）
{
如果（产品 - ＆GT; product_ code == code）
{
找到= 1; //找到
//检查，如果这是在第一个节点 - 从头部删除
如果（流浆＆GT; product_ code == code）
{
TEMP =头;
头=流浆＆gt;接下来，
免费（TEMP）; //完成删除产品
返回;
} //检查，如果这是终端节点 - 从尾部删除
如果（tail-＆GT; product_ code == code）
{
TEMP =尾;
尾= previous;
免费（TEMP）; //完成删除产品
返回;
} //从列表中，如果不是头部或尾部删除
TEMP =产品;
previous-＆gt;接下来=产品 - ＆gt;接下来，
免费（TEMP）; //完成删除产品
返回;
}
//获取previous指针的地址。
previous =产品;
产品=产品 - ＆gt;接下来，
} 如果（！找到）
{
的printf（code [％D]。未找到\\ n，code）;
} //设置所有为NULL与他们完成后，
产物= NULL;
TEMP = NULL;
previous = NULL;
}//遍历链表
无效display_list（）
{
//开始之初
product_data_t *产品=头; 而（产品）
{
的printf（=================================== \\ n）;
的printf（产品code：\\ t \\ t％d个\\ N的产品 - ＆GT; product_ code）;
输出（产品名称：\\ t \\ t％S \\ N的产品 - ＆GT; PRODUCT_NAME）;
输出（产品成本（USD）：\\ t％d个\\ N的产品 - ＆GT; product_cost）;
的printf（=================================== \\ n \\ n）; //指向下一个产品
产品=产品 - ＆gt;接下来，
}
//说完设置为null
产物= NULL;
}//释放所有的资源
无效CLEAN_UP（）
{
product_data_t * TEMP = NULL; 而（头）
{
TEMP =头;
头=流浆＆gt;接下来，
免费（TEMP）;
}
头= NULL;
TEMP = NULL; //程序结束 - 再见
出口（0）;
}无效菜单（）
{
INT选择= 0，code = 0，成本= 0;
CHAR名称[128] = {0}; 做
{
fflush（标准输入）; //刷新输入缓冲区 看跌期权（========= Welecome到链表===============）;
看跌期权（[1]新产品添加到列表）;
卖出期权（[2]从列表中删除一个产品）;
看跌期权（[3]显示所有产品）;
看跌期权（[4]退出和清理）;
的printf（请输入您的选择：）;
scanf函数（％d个，＆安培;选择）; 开关（选择）
{
情况1：
的printf（请输入产品code：）;
scanf函数（％d个，＆安培; code）;
的printf（进入成本）;
scanf函数（％d个，＆安培;成本）;
的printf（输入名称：）;
scanf函数（％S，名）;
推（code，名称，成本）;
打破; 案例2：
的printf（请输入产品code：）;
scanf函数（％d个，＆安培; code）;
POP（code）;
打破; 案例3：
display_list（）;
打破; 情况4：
清理（）;
打破; 默认：
看跌期权（错误的选择）;
打破;
}
}而（选择= 4！）;
}
解决方案
从弹出（）
如果（流浆＆GT; product_ code == code）
{
TEMP =头;
头=流浆＆gt;接下来，
免费（TEMP）; //完成删除产品
返回;
}
在那里只被一个项目，头和尾将指向同一节点的情况。但是，如果你弹出这一项，头部将进行调整，但尾巴还是会指向free'd节点。这会留下一个坏的指针，这可能会导致您的计算机发生爆炸。
附录：同样，new_product'将被晃来晃去，如果你曾经流行被推开的最后一个节点，和CLEAN_UP（）将离开尾巴晃来晃去的指针，以及。即使提供的code样品将永远不会取消引用这些他们free'd后，在C code悬摆指针应始终被视为潜在的危险。
I have created a single linked list. Everything works fine.
I just want to know if I have done anything potentially dangerous in my code. The code snippets I am concerned about is my push, pop, and clean-up. The parts of the code is just for user interaction so not really important (I posted anyway so that it was more clear in what I was doing). Just the linked list application.
Many thanks for any suggestions, as this is my fist attempt.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct product_data product_data_t;
struct product_data
{
int product_code;
char product_name[128];
int product_cost;
product_data_t *next;
};
static product_data_t *head = NULL;
static product_data_t *tail = NULL;
static product_data_t *new_product = NULL;
// Push a product on to the list.
void push(int code, char name[], int cost);
// Pop (delete) a product from the list.
void pop(int code);
// Display all product in the list.
void display_list();
// Delete all memory allocated on the list
void clean_up();
// Display menu
void menu();
int main(void)
{
menu();
getchar();
return 0;
}
void push(int code, char name[], int cost)
{
// Allocate memory for the new product
new_product = calloc(1, sizeof(product_data_t));
if(!new_product)
{
fprintf(stderr, "Cannot allocated memory");
exit(1);
}
/* Populate new products elements fields */
new_product->product_code = code;
strncpy(new_product->product_name, name, sizeof(new_product->product_name));
new_product->product_cost = cost;
new_product->next = NULL;
// Set the head and tail of the linked list
if(head == NULL)
{
// First and only product
head = new_product;
}
else
{
tail->next = new_product;
}
tail = new_product;
}
// Find the product by code and delete
void pop(int code)
{
product_data_t *product = head;
product_data_t *temp = NULL;
product_data_t *previous = head;
int found = 0; // 0 - Not Found, 1 - Found
if(!head)
{
puts("The list is empty");
return;
}
while(product)
{
if(product->product_code == code)
{
found = 1; // Found
// Check if this is in the first node - deleting from head
if(head->product_code == code)
{
temp = head;
head = head->next;
free(temp);
// Finished Deleting product
return;
}
// Check if this is the end node - deleting from the tail
if(tail->product_code == code)
{
temp = tail;
tail = previous;
free(temp);
// Finished deleting product
return;
}
// delete from list if not a head or tail
temp = product;
previous->next = product->next;
free(temp);
// Finished deleting product
return;
}
// Get the address of the previous pointer.
previous = product;
product = product->next;
}
if(!found)
{
printf("code [ %d ] was not found\n", code);
}
// Set all to null after finished with them
product = NULL;
temp = NULL;
previous = NULL;
}
// Traverse the linked list
void display_list()
{
// Start at the beginning
product_data_t *product = head;
while(product)
{
printf("===================================\n");
printf("Product code: \t\t%d\n", product->product_code);
printf("Product name: \t\t%s\n", product->product_name);
printf("product cost (USD): \t%d\n", product->product_cost);
printf("===================================\n\n");
// Point to the next product
product = product->next;
}
// Finished set to null
product = NULL;
}
// Release all resources
void clean_up()
{
product_data_t *temp = NULL;
while(head)
{
temp = head;
head = head->next;
free(temp);
}
head = NULL;
temp = NULL;
// End program - goodbye
exit(0);
}
void menu()
{
int choice = 0, code = 0, cost = 0;
char name[128] = {0};
do
{
fflush(stdin); // Flush the input buffer
puts("========= Welecome to linked list ===============");
puts("[1] Add new product to the list");
puts("[2] Delete a product from the list");
puts("[3] Display all products");
puts("[4] Exit and clean up");
printf("Enter your choice: ");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter product code: ");
scanf("%d", &code);
printf("Enter cost: ");
scanf("%d", &cost);
printf("Enter name: ");
scanf("%s", name);
push(code, name, cost);
break;
case 2:
printf("Enter product code: ");
scanf("%d", &code);
pop(code);
break;
case 3:
display_list();
break;
case 4:
clean_up();
break;
default:
puts("Incorrect choice");
break;
}
}while(choice != 4);
}
解决方案
From pop()
if(head->product_code == code)
{
temp = head;
head = head->next;
free(temp);
// Finished Deleting product
return;
}
In the case of there only being one item, 'head' and 'tail' would be pointing to the same node. However, if you pop this one item, 'head' will be adjusted but 'tail' will still be pointing to the free'd node. This will leave a bad pointer, which may cause your computer to explode.
Addendum: Similarly, 'new_product' will be dangling if you ever pop the last node that was pushed, and clean_up() will leave the 'tail' pointer dangling as well. Even if the code sample provided will never dereference these after they're free'd, dangling pointers in C code should always be treated as "potentially dangerous".
这篇关于单链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
