I was trying to implement a linked list by recursion, as I am weak at it.
The doubt is in recursion itself.
Say I have *temp (say 0x1) = rec_function(); --- call 1
in the next call if the address in temp change from 0x1 to 0x2 (say), will the output of call 1 be stored in 0x1 or 0x2?
temp is a global variable.
Code(if someone wants to go through it)
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
char* data ;
struct node* ptr ;
}node;
node* list = NULL ;
node* temp = NULL ;
node* create_stacked_list(int argc ,char* argv[]){
int i = 0 ;
if(argc == 2 ){
temp = malloc(sizeof(node)) ;
list = temp ;
(*list).ptr = NULL ;
(*list).data = argv[1] ;
return list ;
}
else{
temp = malloc(sizeof(node)) ;
(*temp).data = argv[argc -1 ] ;
argv[argc - 1 ] = NULL ;
argc-- ;
if(i==0) {list = temp ;}
temp -> ptr = create_stacked_list(argc ,argv);
printf("line28");
//list = temp ;
return list ;
}
i++;
} ;
int main(int argc , char * argv[]){
//format :elements in list as a stack ;
//create the list ;
list = create_stacked_list(argc,argv) ;
node* ptr = (*list).ptr ;
while ( ptr != NULL ) {
printf("%s\n" , (*(ptr)).data);
printf("%p \n " , ptr );
ptr = (*ptr).ptr;
}
}
new code for doubly linked lists :
#include<stdio.h>
#include<stddef.h>
#include<stdlib.h>
//define a node
typedef struct dllnode{
int val ;
struct dllnode* prev ;
struct dllnode* next ;
}node;
//globally declare head of list
node* list = NULL ;
//create the first node
node* first_node(int val){
list = malloc(sizeof(node));
(*list).prev = NULL ;
(*list).next = NULL ;
(*list).val = val ;
return list ;
}
//keep adding the other nodes
node* add_node(int val){
node* temp = malloc(sizeof(node));
(*temp).next = list ;
(*list).prev = temp ;
(*temp).val = val ;
(*temp).prev = NULL ;
list = temp ;
return list ;
}
//function to print out the list
void print_out(node* node){
while((*node).next != NULL){
printf("%i \n" , (*node).val) ;
node = (*node).next ;
}
printf("%i \n", (*node).val);
}
//function to delete an element from the list
void delete( node* node , int val ){
while(node->val != val){
node = node->next ;
}
if(node->val == val){
(*(node->next)).prev = node->prev ;
(*(node->prev)).next = node->next ;
node->prev = NULL ;
node->next = NULL ;
}
}
//main function
int main(void) {
int i = 1;
printf("Enter element number %i : " , i) ;
int val = 0 ;
scanf("%i" , &val) ;
first_node(val);
i++;
while(val != 314){
printf("Enter element number %i : " , i) ;
scanf("%i" , &val) ;
if(val == 314){
break;
}
add_node(val);
i++;
}
print_out(list);
int del ;
printf("delete the middle number : ");
scanf("%i" ,&del);
delete(list ,del);
print_out(list);
}
I know that it still has a lot of limitations but it feels nice.
You must first learn to make readable code, for others but also for your own sake. Proper indentation and spacing is key to make the program structure more visible, and also make problems in the code more obvious.
Here is a modified version:
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
char *data;
struct node *ptr;
} node;
node *list = NULL;
node *temp = NULL;
node *create_stacked_list(int argc, char *argv[]) {
int i = 0;
if (argc == 2) {
temp = malloc(sizeof(node));
list = temp;
(*list).ptr = NULL;
(*list).data = argv[1];
return list;
} else {
temp = malloc(sizeof(node));
(*temp).data = argv[argc - 1];
argv[argc - 1] = NULL;
argc--;
if (i == 0) {
list = temp;
}
temp->ptr = create_stacked_list(argc, argv);
printf("line28");
//list = temp;
return list;
}
i++;
};
int main(int argc, char *argv[]) {
//format :elements in list as a stack;
//create the list;
list = create_stacked_list(argc, argv);
node *ptr = (*list).ptr;
while (ptr != NULL) {
printf("%s\n", (*(ptr)).data);
printf("%p \n ", ptr);
ptr = (*ptr).ptr;
}
}
Using short informative names for variables and structure members with helps readability too: ptr should be next in the node structure.
Using global variables is not a good idea. In you example, there is no need for global variables: create_stacked_list returns a pointer to the allocated head node, and temp is only used in that function.
It is also more readable to use the pointer syntax ptr->data instead of the equivalent but cumbersome (*ptr).data.
Here is an improved version:
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
char *data;
struct node *next;
} node;
node *create_stacked_list(int argc, char *argv[]) {
node *list = NULL;
node *temp = NULL;
int i = 0;
if (argc == 2) {
temp = malloc(sizeof(node));
list = temp;
list->ptr = NULL;
list->data = argv[1];
return list;
} else {
node *temp = malloc(sizeof(node));
temp->data = argv[argc - 1];
argv[argc - 1] = NULL;
argc--;
if (i == 0) {
list = temp;
}
temp->next = create_stacked_list(argc, argv);
return list;
}
i++;
}
int main(int argc, char *argv[]) {
//format :elements in list as a stack;
//create the list;
node *list = create_stacked_list(argc, argv);
node *ptr = list->next;
while (ptr != NULL) {
printf("%s\n", ptr->data);
printf("%p\n", ptr);
ptr = ptr->next;
}
}
Regarding recursion, the principle is to break the task into an elementary one, such as allocating a list node, and using a recursive call to the same function for a shorter task. A simple test prevents infinite recursion for the simplest task.
In your case, the simplest task is returning NULL for a zero length array.
Here is a modified version of the recursive function:
node *create_stacked_list(int argc, char *argv[]) {
if (argc == 0) {
return NULL;
} else {
node *list = malloc(sizeof(node));
// Use the first array element for this node
list->data = argv[0];
// Create a list with the remaining elements in the array
// and store the pointer into the `next` member.
// There are `argc - 1` remaining elements
// `argv + 1`, or equivalently `&argv[1]` is a pointer to
// the next element in the array
list->next = create_stacked_list(argc - 1, argv + 1);
return list;
}
}
The same recursive approach can be used to free the list:
void free_stacked_list(node *list) {
if (list) {
free_stacked_list(list->next);
free(list);
}
}
The main function should also be modified so the full list is displayed and freed:
int main(int argc, char *argv[]) {
// create the list
node *list = create_stacked_list(argc, argv);
// print the list
for (node *ptr = list; ptr != NULL; ptr = ptr->next) {
printf("%p: %s\n", (void *)ptr, ptr->data);
}
free_stacked_list(list);
return 0;
}
Here is the final program you can study:
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
char *data;
struct node *next;
} node;
node *create_stacked_list(int argc, char *argv[]) {
if (argc == 0) {
return NULL;
} else {
node *list = malloc(sizeof(node));
// Use the first array element for this node
list->data = argv[0];
// Create a list with the remaining elements in the array
// and store the pointer into the `next` member.
// There are `argc - 1` remaining elements
// `argv + 1`, or equivalently `&argv[1]` is a pointer to
// the next element in the array
list->next = create_stacked_list(argc - 1, argv + 1);
return list;
}
}
void free_stacked_list(node *list) {
if (list) {
free_stacked_list(list->next);
free(list);
}
}
int main(int argc, char *argv[]) {
// create the list
node *list = create_stacked_list(argc, argv);
// print the list
for (node *ptr = list; ptr != NULL; ptr = ptr->next) {
printf("%p: %s\n", (void *)ptr, ptr->data);
}
free_stacked_list(list);
return 0;
}