This is my code for insertion in the end of a circular linked list for which I am getting correct result
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head;
void insert(int val)
{
struct node *temp;
struct node *tail;
temp = (struct node *)malloc(sizeof(struct node));
temp->data = val;
if (head == NULL)
{
head = temp;
tail = temp;
temp->next = head;
}
else
{
tail->next = temp;
tail = temp;
tail->next = head;
}
}
void printlist()
{
struct node *temp = head;
printf("The elements of the linked list area \n ");
while (temp->next != head)
{
printf("%d ", temp->data);
temp = temp->next;
}
printf("%d ", temp->data);
printf("%d", temp->next->data);
}
int main()
{
int n, i, val;
printf("Enter how many elements in a circular likedlist you want \n");
scanf("%d",&n);
head = NULL;
for(i=0;i<n;i )
{
// printf("Enter the value\n");
// scanf("%d,&val");
insert(i);
}
printlist();
}
for which the output is
Enter how many elements in a circular likedlist you want
10
The elements of the linked list area
0 1 2 3 4 5 6 7 8 9 0
However, for the same code when I try to take values from the user it gives me incorrect output.here in this code I just changed a part of the main function inside the for loop where I am taking input for the val instead of passing an integer in function insert
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head;
void insert(int val)
{
struct node *temp;
struct node *tail;
temp = (struct node *)malloc(sizeof(struct node));
temp->data = val;
if (head == NULL)
{
head = temp;
tail = temp;
temp->next = head;
}
else
{
tail->next = temp;
tail = temp;
tail->next = head;
}
}
void printlist()
{
struct node *temp = head;
printf("The elements of the linked list area \n ");
while (temp->next != head)
{
printf("%d ", temp->data);
temp = temp->next;
}
printf("%d ", temp->data);
printf("%d", temp->next->data);
}
int main()
{
int n, i, val;
printf("Enter how many elements in a circular likedlist you want \n");
scanf("%d",&n);
head = NULL;
for(i=0;i<n;i )
{
printf("Enter the value\n");
scanf("%d,&val");
insert(val);
}
printlist();
}
For this program, the output I am getting is
Enter how many elements in a circular likedlist you want
5
Enter the value
1
The elements of the linked list area
0 0
Can anyone suggest me where my code is going wrong?
CodePudding user response：
Symptoms: "It worked, then it didn't." This is the hallmark of UB. Your compiler didn't output code that affected the stack between iterative calls in your first example. The bytes used for tail during each invocation were not overwritten. In the second example ("user input"), scanf() has made use of the same region of stack (as it should), and the fortunate behaviour of the first example became unfortunate. This is why "It worked, then it didn't." Undefined behaviour has many guises...
If you want to be respected as a coder, you don't use global variables, and then compound the mistake with adding more globals. Or 'scanning' what could be millions of nodes to find the tail of a LL.
The code below declares an ordinary node, and a special header node that are compatible.
The testing in main() uses two LLs; one for some integer values, and one that grows with only the odd numbered integer values.
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *next;
} node_t;
typedef struct {
int data; // NB: same name & order of 1st two struct members
node_t *next; // (ditto)
node_t *tail; // head knows where its backend is
int cnt; // meta-information becomes simple to implement
int id;
} head_t;
head_t *append( head_t *ph, int val ) {
static int take_a_number = 0;
node_t *nn = (node_t *)calloc( 1, ph ? sizeof(node_t) : sizeof(head_t) );
/* omitting check */
nn->data = val;
nn->next = nn; // for now, a 'ringlet'
if( ph == NULL ) {
ph = (head_t*)nn; // notice the casting of compatible struct entities
ph->tail = nn;
ph->id = take_a_number;
} else {
nn->next = (node_t*)ph;
ph->tail = ph->tail->next = nn;
}
ph->cnt ;
// debug traversal showing results
printf( "list #%d - %d nodes: ", ph->id, ph->cnt );
node_t *p = (node_t*)ph;
do
printf( "%d ", p->data );
while( (p = p->next) != (node_t*)ph );
puts( "" );
return ph;
}
int main() {
int i;
// two lists. Could be 100, or an array of them...
head_t *p1 = NULL, *p2 = NULL;
for( i = 7; i <= 49; i = 7 ) { // just some arbitrary data
p1 = append( p1, i );
if( i%2 )
p2 = append( p2, i );
}
printf( "Two laps around first list: " );
node_t *pFun = (node_t*)p1;
for( i = 2*p1->cnt 1; i; i-- )
printf( "%d ", pFun->data ), pFun = pFun->next;
puts( "" );
/* omitting `free()` of heap */
return 0;
}
Output
list #1 - 1 nodes: 7
list #2 - 1 nodes: 7
list #1 - 2 nodes: 7 14
list #1 - 3 nodes: 7 14 21
list #2 - 2 nodes: 7 21
list #1 - 4 nodes: 7 14 21 28
list #1 - 5 nodes: 7 14 21 28 35
list #2 - 3 nodes: 7 21 35
list #1 - 6 nodes: 7 14 21 28 35 42
list #1 - 7 nodes: 7 14 21 28 35 42 49
list #2 - 4 nodes: 7 21 35 49
Two laps around first list: 7 14 21 28 35 42 49 7 14 21 28 35 42 49 7
0 global variables, and traversing the LL is only done when printing. This is part of structured programming.
CodePudding user response：
The easiest fix is probably to make tail a global variable like head. I also refactored insert() to reduce duplication, added error checking for malloc() and scanf(), tweaked printlist() to not print the head twice:
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *head;
struct node *tail;
void insert(int val) {
struct node *temp = malloc(sizeof(*temp));
if(!temp) {
printf("malloc failed\n");
exit(1);
}
temp->data = val;
if (head == NULL) {
head = temp;
} else {
tail->next = temp;
}
tail = temp;
tail->next = head;
}
void printlist() {
printf("The elements of the linked list area \n ");
for(struct node *temp = head; temp; ) {
printf("%d ", temp->data);
temp = temp->next;
if(temp == head) break;
}
printf("\n");
}
int main(void) {
printf("Enter how many elements in a circular likedlist you want \n");
int n;
if(scanf("%d", &n) != 1) {
printf("scanf failed\n");
return 1;
}
head = NULL;
for(int i=0; i<n; i ) {
insert(i);
}
printlist();
}
and it the output is now:
The elements of the linked list area
0 1 2 3 4 5 6 7 8 9
You could eliminate the head pointer (tail->next == head) if you want.
CodePudding user response：
In the insert function, the else branch is dereferencing pointer variable tail that has not been initialized. (The variable tail has automatic storage class, i.e. it is a "stack" variable, so it's value is not preserved between calls to the function.) The tail variable needs to point to the last element on the list.
The function can be changed to search for the last element of the list like this:
void insert(int val)
{
struct node *temp;
struct node *tail;
temp = (struct node *)malloc(sizeof(struct node));
temp->data = val;
if (head == NULL)
{
head = temp;
}
else
{
/* find last element */
for (tail = head; tail->next != head; tail = tail->next)
;
tail->next = temp;
}
temp->next = head;
}
(However, it probably makes more sense to store the tail statically outside the function as in Allan Wind's answer so that the function does not have to waste time finding the last element of the list each time it is called. It should also check for memory allocation failure, as in that answer.)
The printList function does not currently work if the list is empty. It will dereference head even if it is NULL, leading to undefined behavior. That can be fixed by moving the all code that accesses the elements of the list inside a if (head != NULL) { } block:
void printlist(void)
{
struct node *temp = head;
printf("The elements of the linked list are \n ");
if (head != NULL)
{
while (temp->next != head)
{
printf("%d ", temp->data);
temp = temp->next;
}
printf("%d ", temp->data);
printf("%d", temp->next->data);
}
printf("\n");
}