Solving Aizu Online Judge ALDS1_3_C.
Bidirectional Concatenated Lists | Algorithms and Data Structures | Aizu Online Judge
I'm worried about an unknown cause error.Here's the source code:
#include<stdio.h>
# include <stdlib.h>
# include <string.h>
#define QUEUE_SIZE 2000000
#define next(x)(x+1)%QUEUE_SIZE)
structure job {
char*command;
int key;
} jobs [QUEUE_SIZE];
US>structure cell{
int key;
structure cell*prev;
structure cell*next;
} head;
int front, real;
void init (void);
void enqueue(char*command, int key);
structure job request (void);
void insert (int key);
void delete (int key);
void deleteFirst(void);
void deleteLast (void);
int main (void)
{
int n, key;
char*command;
structure cell*p;
scanf("%d", & n);
init();
for(inti=0;i<n;i++){
scanf("%s%d", command, & key);
enqueue(command, key);
}
while(front!=real){
structure job deq = dequeue();
if(deq.command=="insert"){
insert(deq.key);
} else if(deq.command=="delete"){
delete(deq.key);
} else if(deq.command=="deleteFirst"){
deleteFirst();
} else if(deq.command=="deleteLast"){
deleteLast();
} else{
exit(1);
}
}
// list output
for(p=head.next;p!=NULL;p=p->next){
printf("%d", p->key);
}
printf("\n");
return 0;
}
void init (void)
{
front = real = 0;
}
void enqueue (char*command, int key)
{
if(next(real)==front){
fprintf(stderr, "queue is full.");
exit(1);
}
jobs[real].command=(char*)malloc(sizeof(char)*sizeof(command)+1);
strcpy(jobs[real].command, command);
jobs[real].key=key;
real = next(real);
}
structure job request()
{
structure job deq;
if(front==real){
fprintf(stderr, "queue is empty.\n");
exit(1);
}
deq = jobs [front];
front = next(front);
return deq;
}
void insert (int key)
{
structure cell*new;
new->key=key;
new->next=head.next;
new->prev=&head;
head.next = new;
}
void delete (int key)
{
structure cell*p;
if(head.next==NULL){
fprintf(stderr, "double linked list is empty.\n";
exit(1);
}
p=head.next;
while(p!=NULL&p->key!=key){
p=p->next;
}
p->prev->next=p->next;
p->next->prev=p->prev;
}
void deleteFirst()
{
if(head.next==NULL){
fprintf(stderr, "double linked list is empty.\n";
exit(1);
}
head.next->next->prev=&head;
head.next =head.next ->next;
}
void deleteLast()
{
if(head.next==NULL){
fprintf(stderr, "double linked list is empty.\n";
exit(1);
}
structure cell*p;
p=head.next;
while(p->next!=NULL){
p=p->next;
}
p->prev->next=NULL;
}
Now, if you declare a variable of type structure job in the main function, the scanf function will not receive input.As a trial, I commented out the while statement of the main function and received it when I ran it.If you declare a variable of type structure job within the main function, the second scanf function will not receive input immediately.Please tell me the solution.
c algorithm
I think it's a side effect of the so-called memory corruption.
Since command is a pointer and has not been initialized, the results of scanf() are stored in an unusual location, and subsequent operations are not expected to work properly.
Declare the variable command as an array or modify it to point to areas dynamically reserved by malloc() etc.
int n, key;
char*command;
structure cell*p;
scanf("%d", & n);
init();
for(inti=0;i<n;i++){
scanf("%s%d", command, & key);
enqueue(command, key);
}
Also, the following comparison statement is also incorrectly implemented, so I think it is necessary to compare strings with strcmp().
if(deq.command=="insert"){
insert(deq.key);
} else if(deq.command=="delete"){
delete(deq.key);
} else if(deq.command=="deleteFirst"){
deleteFirst();
} else if(deq.command=="deleteLast"){
deleteLast();
} else{
exit(1);
}
First of all, making the corrections as described below will not result in your code acting as a queue as expected.
(If I correct it while explaining everything, it will be an ultra-long sentence that almost directly translates the description of the pointer in the C language textbook and the description of the double link queue in the data structure textbook, so I focused on the uninitialized pointer.)
For the time being, this line in main is fatal.
char*command;
Now you have declared the command as a pointer of type char*, but you have never initialized the value of this pointer before rewriting the pointer reference.
scanf("%s%d", command, & key);
If the command remains uninitialized, you have no idea where the memory in the system is pointing.Running scanf as it is will destroy some memory in the system.The behavior of declaring a variable of type structure job in the main function has changed, but it just happens that some memory will break the moment the scanf above runs even once, and subsequent behavior will be unpredictable (and, in bad luck, it may seem to be working).
A declaration of the command in main should, for example, be as follows:
char command [32];//# Free up real space.Never use an uninitialized pointer.
There are other parts of your code that use uninitialized pointers.
void insert (int key)
{
structure cell*new;
new->key=key;
new->next=head.next;
new->prev=&head;
head.next = new;
}
The new in the insert function is declared as a pointer of type structure cell* but has not been initialized again.You should not place addresses that will be stored on other pointers in a local array, so malloc should dynamically allocate space.
void insert(intkey){
structure cell*new=(structure cell*) malloc(sizeof(structure cell)));//#
new->key=key;
new->next=head.next;
new->prev=&head;
head.next = new;
}
(Of course, the allocated memory should be released somewhere.)
Other
- I use == instead of strcmp for string comparison (second half of user20098's answer)
- malloc size calculation for string (command in structure cell) is incorrect
- ...
You'll have to rewrite everywhere to keep things moving.
Correcting the above undefined pointer references should stabilize the operation a little bit, so please remove the problem little by little.
© 2024 OneMinuteCode. All rights reserved.