This is the 16th day of my participation in the Gwen Challenge.More article challenges
Linked list is one of the most basic data structures. It is a linear list realized by chained storage structure. Compared with a sequential table, it does not have to move subsequent elements when inserting and deleting. Now you’re given some integers, and it inserts and deletes some of them frequently, and at some point it lets you look up an element or print out all of the elements in the current list.
The input
There is only one set of input data. The first line has n+1 integers. The first integer is the number of integers left in the line, n, followed by n integers. This line of integers is used to initialize the list, and the order of input is the reverse of the order in the list, that is, if the list is 1, 2, 3, the order of input is 3, 2, 1. The second row has an integer m, which means there are more m rows down here. Each line has a string of “get”, “insert”, “delete”, or “show”. If it is “get” or “delete”, it is followed by an integer, a, to obtain or delete the a-th element. If it is “insert”, it is followed by two integers a and e, representing the insertion of E before position A; There are no integers after “show”.
The output
If successful, the element is printed; If the deletion succeeds, delete OK is displayed. If the command fails to be obtained or deleted, get fail and Delete Fail are displayed. If the insert is successful, “INSERT OK” is displayed; otherwise, “Insert fail” is displayed. If it is “show” all elements in the list are printed, if the list is empty, “Link list is empty” is printed. Note: All double quotes are not printed.
The sample input
3 3 2 1 21 show delete 1 show delete 2 show delete 1 show delete 2 insert 2 5 show insert 1 5 show insert 1 7 show insert 2 5 show insert 3 6 show insert 1 8 show get 2
Sample output
1 2 3 delete OK 2 3 delete OK 2 delete OK Link list is empty delete fail insert fail Link list is empty insert OK 5 insert OK 7 5 insert OK 7 5 5 insert OK 7 5 6 5 insert OK 8 7 5 6 5 7
prompt
Tip: 1. Because there is a lot of insert and delete in the input data (believe it or not, I believe it), you have to use linked lists, otherwise you are likely to time out. This is also to examine the characteristics of linked lists. 2. Initialize the list of elements in reverse order, using the same method as in the problem (insert the list from the header). Summary: This question examines the characteristics of linked lists. How do you tell when to use a sequential list and when to use a linked list? It depends on their characteristics. The characteristics of sequential table are random access and random access, that is to say, if the access and query are more frequent, the use of sequential table is more appropriate; A linked list can be inserted or deleted without moving the nodes behind it. If the insertion or deletion operation is frequent, the linked list is suitable.
I want to review some basic knowledge of data structure, so I did this single linked list problem, in fact, it is relatively simple, just review the algorithm of related operations of single linked list
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
using namespace std;
typedef struct node
{
int data;
struct node *next;
}LNode,*LinkList;
LinkList L;
LNode *head=(LNode *)malloc(sizeof(LNode)); / / head node
/** create a single linked list */
LNode *great_L(a)
{
L=head;
LNode *r=head;
int a[1000]; // Since I don't like to insert from the head, I define an array to insert from the tail
int t;
scanf("%d",&t);
int num1;
for(int i=1; i<=t; i++) {scanf("%d",&num1);
a[i]=num1;
}
while(t--)
{
LNode *p=(LNode *)malloc(sizeof(LNode));
p->data=a[t+1];
r->next=p;
r=p;
//printf("%d ",r->data); // The node is inserted successfully
}
r->next=NULL;
return L;
}
/** Prints a single linked list */
void show_L(LinkList L)
{
if(L->next==NULL)
{
printf("Link list is empty\n");
}
else
{
LNode *p=L->next;
printf("%d",p->data);
while(p->next! =NULL)
{
p=p->next;
printf(" %d",p->data);
}
printf("\n"); }}/** Gets an element in the list */
LNode *get_L(LinkList L,int location)
{
LNode *p=L;
int i=0;
while(p->next! =NULL&&i<location)
{
p=p->next;
i++;
}
if(i==location)
return p;
else
return NULL;
}
/** Delete a node */ from the linked list
int delete_L(LinkList L,int location)
{
LNode *p,*s;
p=get_L(L,location- 1); // find the previous node
if(p==NULL||p->next==NULL) // Determine whether the delete operation is feasible
return 0;
else
{
s=p->next;
p->next=s->next;
free(s);
return 1; }}/** insert a node */
int insert_L(LinkList L,int location,int num)
{
LNode *p,*s;
p=get_L(L,location- 1); // Find the previous node as well
if(p==NULL)
return 0;
else
{
s=(LNode *)malloc(sizeof(LNode));
s->data=num;
s->next=p->next;
p->next=s;
return 1; }}int main(a)
{
L=great_L(a);int t2;
scanf("%d",&t2);
char str[20];
while(t2--)
{
scanf("%s",str);
if(strcmp(str,"insert") = =0)
{
int location;
int num;
scanf("%d%d",&location,&num);
int flag=insert_L(L,location,num);
if(flag==1)
printf("insert OK\n");
else
printf("insert fail\n");
}
if(strcmp(str,"show") = =0)
{
show_L(L);
}
if(strcmp(str,"delete") = =0)
{
int location;
scanf("%d",&location);
int flag=delete_L(L,location);
if(flag==1)
printf("delete OK\n");
else
printf("delete fail\n");
}
if(strcmp(str,"get") = =0)
{
int location;
scanf("%d",&location);
LNode *p=get_L(L,location);
if(p==NULL)
{
printf("get fail\n");
}
else
printf("%d\n",p->data); }}}Copy the codeHere gives single linked list insert (insert), delete (delete), find (get), output (show) and other functions, away from the topic may be more practical point
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
typedef struct node
{
int data;
struct node *next;
} LNode,*LinkList;
LinkList L;
LNode *head=(LNode *)malloc(sizeof(LNode));
LNode *creat_L(a)
{
L=head;
LNode *r=head;
printf("Please enter a number to create a linked list. Enter 0 to end \n");
int num;
scanf("%d",&num);
while(num! =0)
{
LNode *p=(LNode*)malloc(sizeof(LNode));
p->data=num;
r->next=p;
r=p;
scanf("%d",&num);
}
r->next=NULL;
return L;
}
void show_L(LinkList L)
{
if(L->next==NULL)
{
printf("Link is empty");
}
else
{
LNode *p=L->next;
printf("%d",p->data);
while(p->next! =NULL)
{
p=p->next;
printf(" %d",p->data);
}
printf("\n"); }}LNode *get_L(LinkList L,int location)
{
LNode *p=L;
int i=0;
while(p->next! =NULL&&i<location)
{
p=p->next;
i++;
}
if(i==location)
return p;
else
return NULL;
}
int delete_L(LinkList L,int location)
{
LNode *p,*s;
p=get_L(L,location- 1);
if(p==NULL||p->next==NULL)
return 0;
else
{
s=p->next;
p->next=s->next;
free(s);
return 1; }}int insert_L(LinkList L,int location,int num)
{
LNode *p,*s;
p=get_L(L,location- 1);
if(p==NULL)
return 0;
else
{
s=(LNode *)malloc(sizeof(LNode));
s->data=num;
s->next=p->next;
p->next=s;
return 1; }}int main(a)
{
L=creat_L(a);char str[20];
printf("Please enter relevant instructions, including: insert, show, delete, get\n");
while(~scanf("%s",str))
{
if(strcmp(str,"insert") = =0)
{
printf("Please enter the address and value you want to insert \n");
int location;
int num;
scanf("%d%d",&location,&num);
int flag=insert_L(L,location,num);
if(flag==1)
{
printf("insert OK\n");
printf("Insert successful, linked list after insert: \n");
show_L(L);
}
else
printf("insert fail\n");
}
if(strcmp(str,"show") = =0)
{
printf("The linked list is: \n");
show_L(L);
}
if(strcmp(str,"delete") = =0)
{
printf("Please enter the location you want to delete :\n");
int location;
scanf("%d",&location);
int flag=delete_L(L,location);
if(flag==1)
{
printf("delete OK\n");
show_L(L);
}
else
printf("delete fail\n");
}
if(strcmp(str,"get") = =0)
{
printf("Please enter the position where you want the value :\n");
int location;
scanf("%d",&location);
LNode *p=get_L(L,location);
if(p==NULL)
{
printf("get fail\n");
}
else
{
printf("Success, the value is: \n");
printf("%d\n",p->data); }}}return 0;
}
Copy the codeOnly for their own review, if there is a mistake also hope to point out