C中链表的问题

Question

我得到的提示要求在c中使用一个程序来实现链表，并为用户提供在链表上执行不同功能的选项。所需的功能有：

• isempty()：检查列表是否为空，并返回指示其是否为空的值
• add()：在列表的尾部添加一个元素
• insert()：在列表中的特定索引处插入元素
• find()：查找存储特定值的索引。如果函数失败，则返回一个值，指示
• get()：获取存储在特定索引中的值
• remove()：删除列表中第一个出现的特定值。如果函数失败，则返回一个值，指示
• replace()：替换存储在特定索引中的值
• delete()：删除特定索引处的元素。如果函数失败，则返回一个值，指示
• list()：以[a，b，c]格式打印列表中的元素

当我调用add_tail函数时，它允许我输入我想要添加的值，但大约一分钟后，我在终端中收到一条消息，说程序被终止。是什么原因造成的？我还遇到了主函数中while循环的问题，该函数用于打印菜单和接受用户输入。当我第一次运行程序时，菜单将正常打印，但在操作完成后，菜单打印一次，但跳过用户输入，然后再次打印，但第二次接受用户输入。

头文件：

#ifndef LAB8_H_
#define LAB8_H_
#define FIND 'F'
#define EMPTY 'E'
#define ADD 'A'
#define INSERT 'I'
#define DELETE 'D'
#define REMOVE 'R'
#define REPLACE 'S'
#define GET 'G'
#define LIST 'L'
#define QUIT 'Q'
#define FAIL -100
struct node_t {
struct node_t * next;
int value;
};
struct node_t * create_node(int value);
struct node_t * add_tail(struct node_t * head, int value);
struct node_t * insert_node(struct node_t * head, int index, int value);
int is_empty(struct node_t * head);
int find_val(struct node_t * head, int value);
int get_value(struct node_t * head, int index);
struct node_t * replace_val(struct node_t * head, int index, int value);
struct node_t * remove_val(struct node_t * head, int value);
struct node_t * delete_node(struct node_t * head, int index);
void print_list(struct node_t * head);
#endif 

.c文件：

#include <stdio.h>
#include <stdlib.h>
#include "func.h"
struct node_t * create_node(int value)
{
struct node_t * new_node = malloc(sizeof(struct node_t));
new_node -> next = NULL;
new_node -> value = value;
return new_node;
}

struct node_t * add_tail(struct node_t * head, int value)
{
struct node_t * tmp;
if(head == NULL){
printf("Cannot add tail to an empty list. Try againn");
return NULL;
} else{
while(head != NULL){
if(head -> next == NULL){
tmp = create_node(value);
head -> next = tmp;
} else{
head = head -> next;
}
}
}
return head;
}

struct node_t * insert_node(struct node_t * head, int index, int value)
{
struct node_t * tmp;
struct node_t * new;
if(index < 0){
printf("Index cannot be a negative number. Please try againn");
return head;
}
if(index == 0){
tmp = head;
head = create_node(value);
head -> next = tmp;
} else {
tmp = head;
while(tmp != NULL){
if (index == 1){
struct node_t * prev = tmp;
tmp = tmp -> next;
new = create_node(value);
new -> next = tmp;
prev -> next = new;
head = prev;
} else if((tmp -> next == NULL) && (index != 0)){
printf("The index is not found in the bounds of the list. Try againn");
return head;
} else{
tmp = tmp -> next;
index--;
}
}
}
return head;
}
int is_empty(struct node_t * head)
{
if(head == NULL){
return 0;
} else{
return 1;
}
}
int find_val(struct node_t * head, int value)
{
int index = 0;
if(head == NULL){
printf("Cannot find value in empty list! Try againn");
index = -100;
} else{
while(head != NULL){
if((head -> next == NULL) && (head -> value != value)){
printf("The value does not exist in the listn");
index = -100;
} else if(head -> value == value){
return index;
} else{
head = head -> next;
index++;
}
}
}
return index;
}
int get_value(struct node_t * head, int index)
{
int value;
if(index < 0){
printf("Index cannot be a negative number. Try againn");
value = -100;
} else if(head == NULL){
printf("Cannot find index in empty list. Try againn");
value = -100;
} else{
while(head != NULL){
if(index == 0){
value = head -> value;
} else if((head -> next == NULL) && (index != 0)){
printf("Index does not exist in the bounds of the list. Try againn");
value= -100;
} else{
head = head -> next;
index--;
}
}
}
return value;
}
struct node_t * replace_val(struct node_t * head, int index, int value)
{
struct node_t * tmp;
if(index < 0){
printf("Index cannot be a negative number. Try againn");
return NULL;
} else if(head == NULL){
printf("Cannot replace elements in an empty list. Try againn");
return NULL;
} else{
while(head != NULL){
if (index == 0){
tmp = head;
tmp -> value = value;
free(head);
head = tmp;
} else if((head -> next == NULL) && (index != 0)){
printf("Index does not exist is the bounds of the list. Try againn");
return NULL;
} else{
head = head -> next;
index--;
}
}
}
return head;
}
struct node_t * remove_val(struct node_t * head, int value)
{
struct node_t * tmp;
if(head == NULL){
printf("Value cannot be found in an empty list. Try againn");
return NULL;
} else{
while(head != NULL){
if((head -> next == NULL) && (head -> value != value)){
printf("The value does not exist in the list. Try againn");
return NULL;
} else if(head -> next -> value == value){
tmp = head -> next;
head -> next = tmp -> next;
free(tmp);
} else{
head = head -> next;
}
}
}
return head;
}
struct node_t * delete_node(struct node_t * head, int index)
{
struct node_t * tmp;
if(index < 0){
printf("Index cannot be a negative number. Try againn");
return NULL;
} else if(head == NULL){
printf("Cannot delete elements from an empty list. Try againn");
return NULL;
} else{
while(head != NULL){
if((head -> next == NULL) && (index != 0)){
printf("The index is not found in the bounds of the list. Try againn");
return NULL;
} else if(index == 1){
tmp = head;
head = head -> next;
tmp -> next = head -> next;
head -> next = NULL;
free(head);
head = tmp;
} else{
head = head -> next;
index--;
}
}
}
return head;
}
void print_list(struct node_t * head)
{
if (head == NULL){
printf("The list is empty. Nothing to printn");
} else{
while(head != NULL){
if(head -> next != NULL){
printf("%d, ", head -> value);
} else{
printf("%d", head -> value);
}
head = head -> next;
}
}
}

主文件：

#include <stdio.h>
#include <stdlib.h>
#include "func.h"
int main(void)
{
struct node_t * head = NULL;
int index, value;
char choice;
int cont = 0;
while(cont == 0){
printf("Welcome to the Linked List operator. Here are the functions that can be performed:n");
printf("A) Add element to the end of the listn");
printf("I) Insert and element at a specific indexn");
printf("E) Check if the list is emptyn");
printf("F) Find a value in the list and return the indexn");
printf("G) Get the value at a specific indexn");
printf("S) Replace the value at a specific indexn");
printf("R) Remove the first occurance of a specific valuen");
printf("D) Delete the element at a specific indexn");
printf("L) List all the elements currently storedn");
printf("Q) Quit the programn");
printf("Please enter which action you would like to perform: ");
scanf("%c", &choice);
switch(choice){
case ADD:
printf("Please enter the value you would like to add: ");
scanf("%d", &value);
head = add_tail(head, value);
break;
case INSERT:
printf("Please enter the index at which you want to insert a new element: ");
scanf("%d", &index);
printf("Please enter the value you would like to insert: ");
scanf("%d", &value);
head = insert_node(head, index, value);
break;
case EMPTY:
if(is_empty(head) == 0){
printf("The list is empty!n");
} else if(is_empty(head) == 1){
printf("The list is not empty!n");
} else{
printf("Something went wrongn");
}
break;
case FIND:
printf("Please enter the value that you would like to find in the list: ");
scanf("%d", &value);
index = find_val(head, value);
if(index == FAIL){
printf("Error. Try againn");
} else{
printf("The index that the value %d exists at is %dn", value, index);
}
break;
case GET:
printf("Please enter the index for which you would like to know the value: ");
scanf("%d", &index);
if(value == FAIL){
printf("Error. Try againn");
} else{
printf("The value of the element at index %d is %dn", index, value);
}
break;
case REPLACE:
printf("Please enter the index of the element that you would like to replace: ");
scanf("%d", &index);
printf("Please enter the new value: ");
scanf("%d", &value);
if(replace_val(head, index, value) == NULL){
printf("Error. Could not replace noden");
} else{
printf("Success. Here is the new list:n");
print_list(head);
}
break;
case REMOVE:
printf("Please enter the value that you would like to remove the first occurance of: ");
scanf("%d", &value);
if(remove_val(head, value) == NULL){
printf("Error. Could not remove noden");
} else{
printf("Success! Here is the new list:n");
print_list(head);
}
break;
case DELETE:
printf("Please enter the index of the element you would like to delete: ");
scanf("%d", &index);
if(delete_node(head, index) == NULL){
printf("Error. Could not delete selected elementn");
} else{
printf("Success! Here is the new list:n");
print_list(head);
}
break;
case LIST:
printf("[");
print_list(head);
printf("]n");
break;
case QUIT:
printf("You have chosen to quit the program. Goodbye!n");
cont = 1;
break;
default:
printf("You entered an invalid choice. Please try again. Goodbye!n");
}
}
return 0;
}

Answer 1

函数add_tail中的This-if语句

if(head == NULL){
printf("Cannot add tail to an empty list. Try againn");
return NULL;

没有道理。它应该被移除。

在函数中的while循环中，指针head被更改。

while(head != NULL){
if(head -> next == NULL){
tmp = create_node(value);
head -> next = tmp;
} else{
head = head -> next;
}
}

添加节点后，循环不会中断。它将再次添加一个新节点。这就是循环是无限的。

但是，即使您将插入中断语句

while(head != NULL){
if(head -> next == NULL){
tmp = create_node(value);
head -> next = tmp;
break;
} else{
head = head -> next;
}
}

函数返回的指针将不是指向列表头节点的指针。

该功能可以通过以下方式定义

struct node_t * add_tail( struct node_t *head, int value )
{
struct node_t *new_node = create_node( value );
if ( head == NULL )
{
head = new_node;
}
else
{
struct node_t *current = head;

while ( current->next != NULL ) current = current->next;
current->next = new_node;
}
return head;
}

我确信你的程序中的代码还有其他问题。您可以在更新您在本问题中所指的函数add_tail后提出新问题。

Answer 2

注意：OP有几个问题与此有关：

1. 使用递归在C中实现单个链表：我做错了什么
2. C中链表的问题这个问题
3. 修改链表时出现分段故障

(3)是我想回答的问题，但在我回答之前它已经关闭了。所以，我在这里回答它。代码是类似的(我已经从(3)中获取了示例代码)。

---

不幸的是，有很多问题。。。

1. add_tail的if (head == NULL)是坏的(并且可能出现故障)
2. 通常，不需要特殊情况下的空列表或具有一个元素的列表(出现在许多函数中)
3. 在insert_node中，不清楚插入是发生在给定插入索引的之前还是发生在之后(在下面的代码中，选择了"之前")
4. 大多数函数中的循环逻辑过于复杂[而且容易出错]
5. 在可能失败的函数(即找不到索引或值的函数)中，为head返回NULL是一个错误。它泄露了整个列表
6. choice的scanf已损坏(例如，它需要是scanf(" %s",&choice);[注意额外的空间]
7. main中复制的代码太多，无法获得用户输入(请参阅下面代码中get*函数的使用)
8. 由于来自stdin的输入提示，因此很难重放给定的错误(例如，将输入数据存储在使用的文件中(例如，./myprogram < inp.txt)

---

这是重构后的代码。它带有错误和修复的注释。我已经重新编码了所有函数，并测试了一些但不是全部。

某些函数在未找到索引或值、空列表等情况下失败，仍需要进行一些清理。

我添加了getstr和getval函数，以便进行更好的回放测试。

#include <stdio.h>
#include <stdlib.h>
#if 1
#include <ctype.h>
#include <termios.h>
#include <string.h>
#endif
#define ADD 'A'
#define INSERT 'I'
#define DELETE 'D'
#define REMOVE 'R'
#define REPLACE 'S'
#if 1
#define PRINT 'P'
#endif
struct node_t {
struct node_t *next;
int value;
};
struct node_t *create_node(int value);
struct node_t *add_tail(struct node_t *head, int value);
struct node_t *insert_node(struct node_t *head, int index, int value);
#if 0
struct node_t *replace_val(struct node_t *head, int index, int value);
#else
struct node_t *replace_index(struct node_t *head, int index, int value);
#endif
struct node_t *remove_val(struct node_t *head, int value);
struct node_t *delete_node(struct node_t *head, int index);
void print_list(struct node_t *head);
#if 1
char *getstr(const char *prompt);
int getnum(const char *prompt);
#endif
#ifndef DOABORT
#define DOABORT     1
#endif
int
main(void)
{
struct node_t *head = NULL;
int index, value;
char *choice;
int cont = 0;
while (cont == 0) {
printf("nWelcome to the Linked List operator.nHere are the functions that can be performed:n");
printf("A) Add element to the end of the listn");
printf("I) Insert and element at a specific indexn");
printf("S) Replace the value at a specific indexn");
printf("R) Remove the first occurance of a specific valuen");
printf("D) Delete the element at a specific indexn");
printf("P) Print the listn");
choice = getstr("Please enter which action you would like to perform: ");
if (choice == NULL)
break;
choice[0] = toupper((unsigned char) choice[0]);
switch (choice[0]) {
case ADD:
value = getnum("Please enter the value you would like to add: ");
head = add_tail(head, value);
break;
case INSERT:
index = getnum("Please enter the index at which you want to insert a new element: ");
value = getnum("Please enter the value you would like to insert: ");
head = insert_node(head, index, value);
break;
case REPLACE:
index = getnum("Please enter the index of the element that you would like to replace: ");
value = getnum("Please enter the new value: ");
if (replace_index(head, index, value) == NULL) {
printf("Error. Could not replace noden");
}
else {
printf("Success. Here is the new list:n");
print_list(head);
}
break;
case REMOVE:
value = getnum("Please enter the value that you would like to remove the first occurance of: ");
if (remove_val(head, value) == NULL) {
printf("Error. Could not remove noden");
}
else {
printf("Success! Here is the new list:n");
print_list(head);
}
break;
case DELETE:
index = getnum("Please enter the index of the element you would like to delete: ");
if (delete_node(head, index) == NULL) {
printf("Error. Could not delete selected elementn");
}
else {
printf("Success! Here is the new list:n");
print_list(head);
}
break;
case PRINT:
print_list(head);
break;
default:
printf("You entered an invalid choice. Please try again. Goodbye!n");
break;
}
}
return 0;
}
//create a new node
struct node_t *
create_node(int value)
{
struct node_t *new_node = malloc(sizeof(struct node_t));
new_node->next = NULL;
new_node->value = value;
return new_node;
}
//insert an element at the end of the list
struct node_t *
add_tail(struct node_t *head, int value)
{
struct node_t *tmp;
#if 0
// NOTE/BUG: this is a defect and returning NULL is _not_ the solution
// NOTE/BUG: no need to special case this
if (head == NULL) {
printf("Cannot add tail to an empty list. Try againn");
head = NULL;
}
// NOTE/BUG: changing head to head->next breaks the list
else {
while (head != NULL) {
if (head->next == NULL) {
tmp = create_node(value);
head->next = tmp;
}
else {
head = head->next;
}
}
}
#else
// create the new node
tmp = create_node(value);
// find the tail of the list
struct node_t *tail = NULL;
for (struct node_t *cur = head;  cur != NULL;  cur = cur->next)
tail = cur;
// add to tail of non-empty list
if (tail != NULL)
tail->next = tmp;
// add to empty list
else
head = tmp;
#endif
return head;
}
//insert a new element at index i
struct node_t *
insert_node(struct node_t *head, int index, int value)
{
struct node_t *tmp;
if (index < 0) {
printf("Index cannot be a negative number. Please try againn");
return head;
}
// NOTE/BUG: it's unclear whether inserting _at_ a given index is inserting
// _before_ this index or _after_ -- we have to choose so we'll choose "before"
// [below]
#if 0
// NOTE/BUG: no need to special case
if (index == 0) {
tmp = head;
head = create_node(value);
head->next = tmp;
}
else {
tmp = head;
while (tmp != NULL) {
// NOTE/BUG: no need to special case this
if (index == 1) {
struct node_t *prev = tmp;
tmp = tmp->next;
new = create_node(value);
new->next = tmp;
prev->next = new;
head = prev;
}
else if ((tmp->next == NULL) && (index != 0)) {
printf("The index is not found in the bounds of the list. Try againn");
return head;
}
else {
tmp = tmp->next;
index--;
}
}
}
#else
// NOTE/FIX: we insert _before_ index (so we can insert before the head with 0)
// create new node
tmp = create_node(value);
// find the Nth index and insert before it
struct node_t *cur = head;
struct node_t *prev = NULL;
int curidx = 0;
for (;  cur != NULL;  cur = cur->next, ++curidx) {
if (curidx == index) {
if (prev != NULL)
prev->next = tmp;
else
head = tmp;
tmp->next = cur;
break;
}
prev = cur;
}
do {
// we did the insert in above loop
if (cur != NULL)
break;
// no index found
// we can add to tail (or abort)
if (prev != NULL)
prev->next = tmp;
else
head = tmp;
} while (0);
#endif
return head;
}
//replace the value of the element at index i
struct node_t *
replace_index(struct node_t *head, int index, int value)
{
if (index < 0) {
printf("Index cannot be a negative number. Try againn");
exit(1);
}
else if (head == NULL) {
printf("Cannot replace elements in an empty list. Try againn");
exit(1);
}
#if 0
// NOTE/BUG: changing head to head->next breaks the list
// NOTE/BUG: no need to free head -- this leaks memory and is undefined behavior
// NOTE/BUG: doing tmp = head before this does _not_ fix this
else {
while (head != NULL) {
if (index == 0) {
tmp = head;
tmp->value = value;
free(head);
head = tmp;
}
else if ((head->next == NULL) && (index != 0)) {
printf("Index does not exist is the bounds of the list. Try againn");
exit(1);
}
else {
head = head->next;
index--;
}
}
}
#else
struct node_t *cur = head;
int curidx = 0;
for (;  cur != NULL;  cur = cur->next, ++curidx) {
if (curidx == index) {
cur->value = value;
break;
}
}
// we could _not_ find the correct index -- abort or just ignore?
// NOTE: with a boolean return, we could just return true if the index
// was found
#if DOABORT
if (cur == NULL) {
printf("replace_index: index=%d not foundn",index);
exit(1);
}
#endif
#endif
return head;
}
//remove the first occurance of a value x in the list
struct node_t *
remove_val(struct node_t *head, int value)
{
#if 0
// NOTE/BUG: removing by value in an empty list _is_ valid
if (head == NULL) {
printf("Value cannot be found in an empty list. Try againn");
return NULL;
}
// NOTE/BUG: changing head to head->next breaks the list
else {
while (head != NULL) {
if ((head->next == NULL) && (head->value != value)) {
printf("The value does not exist in the list. Try againn");
return NULL;
}
else if (head->next->value == value) {
tmp = head->next;
head->next = tmp->next;
free(tmp);
}
else {
head = head->next;
}
}
}
#else
struct node_t *next;
struct node_t *prev = NULL;
struct node_t *cur = head;
for (;  cur != NULL;  cur = next) {
next = cur->next;
if (cur->value == value) {
if (prev != NULL)
prev->next = next;
else
head = next;
free(cur);
break;
}
prev = cur;
}
// same issue as above -- do we abort of just ignore
#if DOABORT
if (cur == NULL) {
printf("remove_val: value=%d not foundn",value);
exit(1);
}
#endif
#endif
return head;
}
//delete the node at index i
struct node_t *
delete_node(struct node_t *head, int index)
{
if (index < 0) {
printf("Index cannot be a negative number. Try againn");
return NULL;
}
#if 0
// NOTE/BUG: no need to special case an empty list
else if (head == NULL) {
printf("Cannot delete elements from an empty list. Try againn");
return NULL;
}
else {
while (head != NULL) {
if ((head->next == NULL) && (index != 0)) {
printf("The index is not found in the bounds of the list. Try againn");
return NULL;
}
else if (index == 1) {
tmp = head;
head = head->next;
tmp->next = head->next;
head->next = NULL;
free(head);
head = tmp;
}
else {
head = head->next;
index--;
}
}
}
#else
struct node_t *cur = head;
struct node_t *next;
struct node_t *prev = NULL;
int curidx = 0;
for (;  cur != NULL;  cur = next, ++curidx) {
next = cur->next;
if (curidx == index) {
if (prev != NULL)
prev->next = next;
else
head = next;
break;
}
prev = cur;
}
#if DOABORT
if (cur == NULL) {
printf("delete_node: index=%d not foundn",index);
exit(1);
}
#endif
#endif
return head;
}
//print elements of the list
void
print_list(struct node_t *head)
{
if (head == NULL) {
printf("The list is empty. Nothing to printn");
}
#if 0
else {
while (head != NULL) {
if (head->next == NULL) {
printf("%d", head->value);
}
else {
printf("%d, ", head->value);
head = head->next;
}
}
}
#else
for (struct node_t *cur = head;  cur != NULL;  cur = cur->next) {
if (cur != head)
printf(", ");
printf("%d",cur->value);
}
printf("n");
#endif
}
#if 1
char *
getstr(const char *prompt)
{
static char buf[100];
char *bp;
// echo input if _not_ a TTY
static int echoflg = -1;
if (echoflg < 0) {
struct termios tio;
echoflg = (tcgetattr(fileno(stdin),&tio) < 0);
}
while (1) {
printf("%s",prompt);
fflush(stdout);
bp = fgets(buf,sizeof(buf),stdin);
if (bp == NULL) {
if (echoflg)
printf("EOFn");
break;
}
if (echoflg)
fputs(buf,stdout);
buf[strcspn(buf,"n")] = 0;
// stop if _not_ blank line
if (buf[0] != 0)
break;
}
return bp;
}
int
getnum(const char *prompt)
{
char *buf = getstr(prompt);
int val = -1;
if (buf != NULL)
val = strtol(buf,&buf,10);
return val;
}
#endif

---

在上面的代码中，我使用了cpp条件词来表示旧代码与新代码：

#if 0
// old code
#else
// new code
#endif
#if 1
// new code
#endif

注意：这可以通过unifdef -k运行文件来清除

---

这是我使用的示例输入文件：

a
1
a
2
a
3
a
4
a
5
a
6
a
7
p
r
5
d
5
s
4
9

---

这是该输入文件的示例输出：

Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform: a
Please enter the value you would like to add: 1
Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform:
Please enter which action you would like to perform: a
Please enter the value you would like to add: 2
Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform:
Please enter which action you would like to perform: a
Please enter the value you would like to add: 3
Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform:
Please enter which action you would like to perform: a
Please enter the value you would like to add: 4
Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform:
Please enter which action you would like to perform: a
Please enter the value you would like to add: 5
Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform:
Please enter which action you would like to perform: a
Please enter the value you would like to add: 6
Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform:
Please enter which action you would like to perform: a
Please enter the value you would like to add: 7
Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform:
Please enter which action you would like to perform: p
1, 2, 3, 4, 5, 6, 7
Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform:
Please enter which action you would like to perform: r
Please enter the value that you would like to remove the first occurance of: 5
Success! Here is the new list:
1, 2, 3, 4, 6, 7
Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform:
Please enter which action you would like to perform: d
Please enter the index of the element you would like to delete: 5
Success! Here is the new list:
1, 2, 3, 4, 6
Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform:
Please enter which action you would like to perform: s
Please enter the index of the element that you would like to replace: 4
Please enter the new value: 9
Success. Here is the new list:
1, 2, 3, 4, 9
Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform: EOF

---

更新：

上述问题之一是搜索节点的功能可能会失败。也就是说，没有找到匹配项。如何将其传达给来电者？

对于链表，基本上有三种方法可以处理向调用者返回更新的head：

// current way ...
node_t *
add_tail(node_t *head,int value)
{
// do stuff and update head ...
return head;
}
// double pointer to head ...
void
add_tail(node_t **head,int value)
{
// do stuff and update *head ...
}
// use of list struct ...
void
add_tail(list_t *list,int value)
{
// do stuff and update list->head ...
}

我发现第三种选择(使用单独的列表结构)更安全、更灵活。

因为函数不再需要通过return head;返回更新的head值，所以我们可以将返回值重新定义为布尔值；成功；值(即0=失败，1=成功)。

另一个好处是，链表函数的调用者不需要知道该函数是否会更新head或不。它只传递列表指针，给定的函数可以随心所欲。

这里是一个重新编码为使用"；真实的"；列表(它也通过unifdef -k运行)：

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <termios.h>
#include <string.h>
#define ADD 'A'
#define INSERT 'I'
#define DELETE 'D'
#define REMOVE 'R'
#define REPLACE 'S'
#define PRINT 'P'
typedef struct node node_t;
struct node {
node_t *next;
int value;
};
typedef struct {
node_t *head;
int count;
} list_t;
node_t *create_node(int value);
void add_tail(list_t *list, int value);
int insert_node(list_t *list, int index, int value);
int replace_index(list_t *list, int index, int value);
int remove_val(list_t *list, int value);
int delete_node(list_t *list, int index);
void print_list(list_t *list);
char *getstr(const char *prompt);
int getnum(const char *prompt);
#ifndef DOABORT
#define DOABORT     1
#endif
int
main(void)
{
list_t *list = calloc(1,sizeof(*list));
int index, value;
char *choice;
int cont = 0;
while (cont == 0) {
printf("nWelcome to the Linked List operator.nHere are the functions that can be performed:n");
printf("A) Add element to the end of the listn");
printf("I) Insert and element at a specific indexn");
printf("S) Replace the value at a specific indexn");
printf("R) Remove the first occurance of a specific valuen");
printf("D) Delete the element at a specific indexn");
printf("P) Print the listn");
choice = getstr("Please enter which action you would like to perform: ");
if (choice == NULL)
break;
choice[0] = toupper((unsigned char) choice[0]);
switch (choice[0]) {
case ADD:
value = getnum("Please enter the value you would like to add: ");
add_tail(list, value);
break;
case INSERT:
index = getnum("Please enter the index at which you want to insert a new element: ");
value = getnum("Please enter the value you would like to insert: ");
insert_node(list, index, value);
break;
case REPLACE:
index = getnum("Please enter the index of the element that you would like to replace: ");
value = getnum("Please enter the new value: ");
if (replace_index(list, index, value) == 0) {
printf("Error. Could not replace noden");
}
else {
printf("Success. Here is the new list:n");
print_list(list);
}
break;
case REMOVE:
value = getnum("Please enter the value that you would like to remove the first occurance of: ");
if (remove_val(list, value) == 0) {
printf("Error. Could not remove noden");
}
else {
printf("Success! Here is the new list:n");
print_list(list);
}
break;
case DELETE:
index = getnum("Please enter the index of the element you would like to delete: ");
if (delete_node(list, index) == 0) {
printf("Error. Could not delete selected elementn");
}
else {
printf("Success! Here is the new list:n");
print_list(list);
}
break;
case PRINT:
print_list(list);
break;
default:
printf("You entered an invalid choice. Please try again. Goodbye!n");
break;
}
}
return 0;
}
//create a new node
node_t *
create_node(int value)
{
node_t *new_node = malloc(sizeof(node_t));
new_node->next = NULL;
new_node->value = value;
return new_node;
}
//insert an element at the end of the list
void
add_tail(list_t *list, int value)
{
node_t *tmp;
// create the new node
tmp = create_node(value);
// find the tail of the list
node_t *tail = NULL;
for (node_t *cur = list->head;  cur != NULL;  cur = cur->next)
tail = cur;
// add to tail of non-empty list
if (tail != NULL)
tail->next = tmp;
// add to empty list
else
list->head = tmp;
}
//insert a new element at index i
int
insert_node(list_t *list, int index, int value)
{
node_t *tmp;
if (index < 0) {
printf("Index cannot be a negative number. Please try againn");
return 0;
}
// create new node
tmp = create_node(value);
// find the Nth index and insert before it
node_t *cur = list->head;
node_t *prev = NULL;
int curidx = 0;
for (;  cur != NULL;  cur = cur->next, ++curidx) {
if (curidx == index) {
if (prev != NULL)
prev->next = tmp;
else
list->head = tmp;
tmp->next = cur;
break;
}
prev = cur;
}
do {
// we did the insert in above loop
if (cur != NULL)
break;
// no index found
// we can add to tail (or abort)
if (prev != NULL)
prev->next = tmp;
else
list->head = tmp;
} while (0);
return 1;
}
//replace the value of the element at index i
int
replace_index(list_t *list, int index, int value)
{
if (index < 0) {
printf("Index cannot be a negative number. Try againn");
return 0;
}
else if (list->head == NULL) {
printf("Cannot replace elements in an empty list. Try againn");
return 0;
}
node_t *cur = list->head;
int curidx = 0;
for (;  cur != NULL;  cur = cur->next, ++curidx) {
if (curidx == index) {
cur->value = value;
break;
}
}
if (cur == NULL) {
printf("replace_index: index=%d not foundn",index);
return 0;
}
return 1;
}
//remove the first occurance of a value x in the list
int
remove_val(list_t *list, int value)
{
node_t *next;
node_t *prev = NULL;
node_t *cur = list->head;
for (;  cur != NULL;  cur = next) {
next = cur->next;
if (cur->value == value) {
if (prev != NULL)
prev->next = next;
else
list->head = next;
free(cur);
break;
}
prev = cur;
}
// same issue as above -- do we abort of just ignore
if (cur == NULL) {
printf("remove_val: value=%d not foundn",value);
return 0;
}
return 1;
}
//delete the node at index i
int
delete_node(list_t *list, int index)
{
if (index < 0) {
printf("Index cannot be a negative number. Try againn");
return 0;
}
node_t *cur = list->head;
node_t *next;
node_t *prev = NULL;
int curidx = 0;
for (;  cur != NULL;  cur = next, ++curidx) {
next = cur->next;
if (curidx == index) {
if (prev != NULL)
prev->next = next;
else
list->head = next;
break;
}
prev = cur;
}
if (cur == NULL) {
printf("delete_node: index=%d not foundn",index);
return 0;
}
return 1;
}
//print elements of the list
void
print_list(list_t *list)
{
node_t *cur = list->head;
if (cur == NULL)
printf("The list is empty. Nothing to print");
for (;  cur != NULL;  cur = cur->next) {
if (cur != list->head)
printf(", ");
printf("%d",cur->value);
}
printf("n");
}
char *
getstr(const char *prompt)
{
static char buf[100];
char *bp;
// echo input if _not_ a TTY
static int echoflg = -1;
if (echoflg < 0) {
struct termios tio;
echoflg = (tcgetattr(fileno(stdin),&tio) < 0);
}
while (1) {
printf("%s",prompt);
fflush(stdout);
bp = fgets(buf,sizeof(buf),stdin);
if (bp == NULL) {
if (echoflg)
printf("EOFn");
break;
}
if (echoflg)
fputs(buf,stdout);
buf[strcspn(buf,"n")] = 0;
// stop if _not_ blank line
if (buf[0] != 0)
break;
}
return bp;
}
int
getnum(const char *prompt)
{
char *buf = getstr(prompt);
int val = -1;
if (buf != NULL)
val = strtol(buf,&buf,10);
return val;
}