c - C中的链表(中间插入)
问题描述
编写一个包含整数链表的程序,允许您在列表中的 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]: %d\n", 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 - Insert\n");
printf("2 - Print\n");
printf("3 - Duplicate X\n");
printf("5 - Close\n");
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;
}
解决方案
在提出解决方案之前,我首先建议更改代码中的一些内容:
不要在专用功能(如
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("NULL\n");
}
// 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 - Insert\n");
printf("2 - Print\n");
printf("3 - Duplicate X\n");
printf("5 - Close\n");
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;
}
推荐阅读
- react-native - React Native Expo App 在生产模式下崩溃
- python - 如何为 NoSQL/DynamoDB 生成低字符主键?
- sql - 在亚马逊红移中取消列出数组
- azure-sql-database - Azure Sql 数据库中的 CXSYNC_PORT 等待类型
- android - 无法从 android 支持库加载控件
- javascript - 将 Javascript 对象数组减少为对象
- c++ - 使用 ios_base::sync_with_stdio(false) 编译错误;
- flutter - 如何使用分隔线在一行内布局网格
- sql - Full Join 差异左 + 右关节
- java - javax.websocket.DeploymentException