C中的链表(中间插入)

Question

编写一个包含整数链表的程序，允许您复制列表中X元素旁边的X元素(X由用户给出)。例子:列表:1、4、3、2、5、3、7;X = 3。结果列表:1、4、3、3、2、5、3、3、7.

这是我需要解决的问题，但我尝试了所有方法。链表是我不会想到的东西。我知道如何在结尾和开头加上一个数字，但在这个问题中，我甚至不知道从哪里开始。这就是我目前所看到的:

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int x;
struct node *next;
}Node;
// Check if the list is empty
int empty(Node *list){
if(list->next == NULL)
return 1;
else
return 0;
}
// Insert a number
void insert(Node *list){
Node *newn=(Node *) malloc(sizeof(Node));
printf("nNumber: "); 
scanf("%d", &newn->x);
newn->next = NULL;
if(empty(list))
list->next=newn;
else{
Node *aux = list->next;
while(aux->next != NULL){
aux = aux->next;
}
aux->next = newn;
}
}
// Print the list
void print(Node *list){
Node *next = list;
int i=1;
printf("n");
if(empty(list)){
printf("EMPTY!n");
}else{
list = list->next;
while(list!=NULL){
printf("NUMBER [%2d]: %dn", i++, list->x);
list = list->next;
}
}
}
// Duplicate X values in the list
void duplicate(Node *lista){
}
int main(void) {
Node *list = (Node*)malloc(sizeof(Node));
int op, val;
do{
printf("n1 - Insertn");
printf("2 - Printn");
printf("3 - Duplicate Xn");
printf("5 - Closen");
printf("OPERATION: ");
scanf("%d", &op);
switch(op){
case 1:
insert(list);
break;
case 2:
print(list);
break;
case 3:
duplicate(list);
break;
case 5:
printf("Closed!n");
break;
default:
printf("Invalid option!n");
}
}while(op != 5);
return 0;
}

Answer 1

在提出解决方案之前，我首先建议更改代码中的一些内容:

• 不要在专用函数(如insert)中要求输入。在你的main中这样做。

• 将一些逻辑拆分到单独的函数中:

  • createNode用于创建节点，
  • getTail查找对列表
  中最后一个节点的引用

  然后使用这些使您的insert函数非常简单。然后，您还可以重用createNode来创建"哨兵"。list节点，你也可以用它来实现duplicate。

建议代码如下:

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int x;
struct node *next;
}Node;
// Check if the list is empty
int empty(Node *list){
if(list->next == NULL)
return 1;
else
return 0;
}
// Get a reference to the last node in the list, 
//   even if it is the sentinel node
Node *getTail(Node * list) {
Node *tail = list;
while (tail->next != NULL) {
tail = tail->next;
}
return tail;
}
// Generic function for creating a Node instance
Node *createNode(int val, Node *next) {
Node *newn = (Node *) malloc(sizeof(Node));
newn->x = val;
newn->next = next;
return newn;
}
// Insert a number
void insert(Node *list, int val) {
getTail(list)->next = createNode(val, NULL);
}
// Print the list (I changed the output format)
void print(Node *list) {
list = list->next;
while (list!=NULL) {
printf("%d -> ", list->x);
list = list->next;
}
printf("NULLn");
}
// Duplicate X values in the list
void duplicate(Node *list, int val) {
list = list->next;
while (list != NULL) {
if (list->x == val) {
list->next = createNode(val, list->next);
list = list->next; // reference the new node
}
list = list->next;
}
}
int main(void) {
Node *list = createNode(0, NULL); // Also use here!
int op, val;
do{
printf("n1 - Insertn");
printf("2 - Printn");
printf("3 - Duplicate Xn");
printf("5 - Closen");
printf("OPERATION: ");
scanf("%d", &op);
switch(op){
case 1:
// Perform input in main program
printf("nNumber to insert: "); 
scanf("%d", &val);
insert(list, val);
break;
case 2:
print(list);
break;
case 3:
printf("nNumber to duplicate: "); 
scanf("%d", &val);
duplicate(list, val);
break;
case 5:
printf("Closed!n");
break;
default:
printf("Invalid option!n");
}
} while(op != 5);
return 0;
}