Hi,
I am not seeking a solution nor am I asking a homework problem. I have
my solution but it doesn't run correctly as expected because of some
error and I am trying to understand this error. Here is my code
node* Reverse_List(node *p)
{
/*Is there any problem with this statement */
static node *head = p;
static node *revHead = NULL;
if (p == NULL)
return NULL;
if (p->next == NULL)
revHead = p;
else
/* ***** Is this allowed in C99 specs***** */
reverse(p->next)->next = p;
if (p == head) {
p->next = NULL;
return revHead;
}
else
return p;
}
I get the following error. I am using gcc compiler
In function 'Reverse_List':
reverse_list_recursion_back.c:69: error: initializer element is not
constant
reverse_list_recursion_back.c:76: error: invalid type argument of '->'
Any and every help is appreciated. 9 14405
DanielJohnson wrote:
Hi,
I am not seeking a solution nor am I asking a homework problem. I have
my solution but it doesn't run correctly as expected because of some
error and I am trying to understand this error. Here is my code
node* Reverse_List(node *p)
{
/*Is there any problem with this statement */
static node *head = p;
Static variables are initialised before the program runs, so the
initialiser must be a compile time constant.
static node *revHead = NULL;
if (p == NULL)
return NULL;
if (p->next == NULL)
revHead = p;
else
/* ***** Is this allowed in C99 specs***** */
reverse(p->next)->next = p;
reverse is not declared.
--
Ian Collins.
The answer to your question is that you _can_ use a pointer value
returned from a function as a pointer to an object of appropriate
type. <g>
I couldn't resist playing along. I took a slightly different
approach by keeping an internal pointer ('tail') to the last node
in the list.
typedef struct node_d
{ struct node_d *next;
int data;
} node;
node *rev(node *p)
{ static node *head, *tail;
if (p)
{ rev(p->next);
p->next = NULL;
if (head) tail->next = p;
else head = p;
tail = p;
}
else head = NULL;
return head;
}
An interesting exercise. Thanks!
--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA http://www.iedu.com/DeSoto
On Feb 9, 9:09*pm, Morris Dovey <mrdo...@iedu.comwrote:
The answer to your question is that you _can_ use a pointer value
returned from a function as a pointer to an object of appropriate
type. <g>
I couldn't resist playing along. I took a slightly different
approach by keeping an internal pointer ('tail') to the last node
in the list.
* *typedef struct node_d
* *{ *struct node_d *next;
* * * int data;
* *} *node;
* *node *rev(node *p)
* *{ *static node *head, *tail;
* * * if (p)
* * * { *rev(p->next);
* * * * *p->next = NULL;
* * * * *if (head) tail->next = p;
* * * * *else head = p;
* * * * *tail = p;
* * * }
* * * else head = NULL;
* * * return head;
* *}
Well, since the cat is out of the bag, IMO it's more intuitive to
build the reversed list with a second parameter...
node *rev(node *head, *reversed_tail)
{
if (head) {
node *next = head->next;
head->next = reversed_tail;
return rev(next, head);
}
return reversed_tail;
}
Since this is tail-recursive, if you compile it with e.g. gcc -O2, it
will be transformed into a loop.
Initiate with
node *reversed_list = rev(list, NULL);
Gene wrote:
Well, since the cat is out of the bag, IMO it's more intuitive to
build the reversed list with a second parameter...
node *rev(node *head, *reversed_tail)
{
if (head) {
node *next = head->next;
head->next = reversed_tail;
return rev(next, head);
}
return reversed_tail;
}
It's _less_ intuitive to me, and (probably) uses 50% more stack
space - but I like this a lot better than what I cobbled
together. :-)
--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA http://www.iedu.com/DeSoto
Morris wrote:
) Gene wrote:
)Well, since the cat is out of the bag, IMO it's more intuitive to
)build the reversed list with a second parameter...
)>
)node *rev(node *head, *reversed_tail)
){
) if (head) {
) node *next = head->next;
) head->next = reversed_tail;
) return rev(next, head);
) }
) return reversed_tail;
)}
)
) It's _less_ intuitive to me, and (probably) uses 50% more stack
) space - but I like this a lot better than what I cobbled
) together. :-)
You may notice that it uses tail recursion.
A good compiler would rewrite the above code to:
node *rev(node *head, *reversed_tail)
{
tail_recurse:
if (head) {
node *next = head->next;
head->next = reversed_tail;
/* return rev(next, head); */
reversed_tail = head; head = next; goto tail_recurse;
}
return reversed_tail;
}
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
Willem wrote:
You may notice that it uses tail recursion.
A good compiler would rewrite the above code to:
node *rev(node *head, *reversed_tail)
{
tail_recurse:
if (head) {
node *next = head->next;
head->next = reversed_tail;
/* return rev(next, head); */
reversed_tail = head; head = next; goto tail_recurse;
}
return reversed_tail;
}
Which (with cut-n-paste + minor tweak) "cleans up" to
node *rev(node *head, *reversed_tail)
{ while (head)
{ node *next = head->next;
head->next = reversed_tail;
reversed_tail = head;
head = next;
}
return reversed_tail;
}
Which eliminates the goto, the call/stack overhead, Kaz's
re-entrancy issue - but doesn't address the Dan's interest in a
recursive function.
No matter - /I/ like it. :-)
--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA http://www.iedu.com/DeSoto
On Feb 10, 9:36*am, Morris Dovey <mrdo...@iedu.comwrote:
Willem wrote:
You may notice that it uses tail recursion.
A good compiler would rewrite the above code to:
*node *rev(node *head, *reversed_tail)
*{
* tail_recurse:
* *if (head) {
* * *node *next = head->next;
* * *head->next = reversed_tail;
* * */* return rev(next, head); */
* * *reversed_tail = head; head = next; goto tail_recurse;
* *}
* *return reversed_tail;
*}
Which (with cut-n-paste + minor tweak) "cleans up" to
* *node *rev(node *head, *reversed_tail)
* *{ *while (head)
* * * { *node *next = head->next;
* * * * *head->next = reversed_tail;
* * * * *reversed_tail = head;
* * * * *head = next;
* * * *}
* * * *return reversed_tail;
* *}
Which eliminates the goto, the call/stack overhead, Kaz's
re-entrancy issue - but doesn't address the Dan's interest in a
recursive function.
No matter - /I/ like it. :-)
You really aren't done tweaking yet. You can make reversed_tail a
local variable initialized to NULL, since that's all the caller does
with it.
Now you should _really_ like the fact that what this code does is, as
pseudocode,
set Y empty
while (list X is not empty)
push(pop(X), Y)
return Y
...which is the traditional iterative list reverser you will find in
some textbooks.
This is one of many cases where starting with a "recursive" functional
definition and transforming it with algebraic operations that preserve
behavior yields an efficient C code.
On Feb 10, 7:09*am, Morris Dovey <mrdo...@iedu.comwrote:
Gene wrote:
Well, since the cat is out of the bag, IMO it's more intuitive to
build the reversed list with a second parameter...
node *rev(node *head, *reversed_tail)
{
* if (head) {
* * node *next = head->next;
* * head->next = reversed_tail;
* * return rev(next, head);
* }
* return reversed_tail;
}
It's _less_ intuitive to me, and (probably) uses 50% more stack
space - but I like this a lot better than what I cobbled
together. :-)
--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USAhttp://www.iedu.com/DeSoto
It ought to use a small _constant_ stack space with a reasonable
compiler because the tail call becomes a loop. I know gcc -O2 will do
this. So will MS VC 2005 Express.
If the compiler is lame enought to miss the tail recursion, then it
will probably use 33% more stack than your code on most 32-bit
machines: 4 words rather than 3--frame pointer + return address + 2
vice 1 pointers per self-call.
Gene wrote:
You really aren't done tweaking yet. You can make reversed_tail a
local variable initialized to NULL, since that's all the caller does
with it.
Of course! I should have been paying more attention (besides, now
I can sneak away from not having typed reversed_tail <g>)
node *rev(node *head)
{ node *next, *reversed_tail = NULL;
while (head)
{ next = head->next;
head->next = reversed_tail;
reversed_tail = head;
head = next;
}
return reversed_tail;
}
...which is the traditional iterative list reverser you will find in
some textbooks.
I /do/ like this better. I don't think we're doing much for Dan,
but I'm having fun! :-)
I've missed a lot in never having taken any CS courses, and I'll
probably always be stuck in "catch-up" mode.
This is one of many cases where starting with a "recursive" functional
definition and transforming it with algebraic operations that preserve
behavior yields an efficient C code.
Looks like the proof is in the pudding. Thanks!
--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA http://www.iedu.com/DeSoto This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Perpetual Snow |
last post by:
How can I reverse a linked list with no memory allocation?
I'm searching for an algorithm which is constant in runtime and space.
Thanks
|
by: RAJASEKHAR KONDABALA |
last post by:
Hi,
Does anybody know what the fastest way is to "search for a value in a
singly-linked list from its tail" as oposed to its head?
I am talking about a non-circular singly-linked list, i.e.,...
|
by: dssuresh6 |
last post by:
Whether browsing forward or backward can be done using a singly linked
list. Is there any specific case where a doubly linked list is needed?
For people who say that singly linked list allows...
|
by: Neo |
last post by:
Hi Frns,
Could U plz. suggest me how can i reverse a link list (without recursion)???
here is my code (incomplete):
#include<stdio.h>
|
by: sam_cit |
last post by:
Hi Everyone,
I want to actually reverse a single linked list without using many
variables, i have a recurssive solution, but i wanted an iterative one.
can anyone help me on this?
|
by: Suyash Upadhyay |
last post by:
Hi All,
As a beginner in Computer Programming, I decided to create Linked List using recursion, but I am not getting right answer. I think it is fundamentally correct, but I am stuck.
...
|
by: tgnelson85 |
last post by:
Hello, C question here (running on Linux, though there should be no platform specific code).
After reading through a few examples, and following one in a book, for linked lists i thought i would...
|
by: Hamster |
last post by:
Hi,
Need help with my code on reversing a singly linked list, here's my
code:
void reverseList ( List& listObj)
{
ListNode*pHeadnew=listObj.lastPtr, *pTailnew=listObj.firstPtr;
|
by: isladogs |
last post by:
The next Access Europe meeting will be on Wednesday 6 Sept 2023 starting at 18:00 UK time (6PM UTC+1) and finishing at about 19:15 (7.15PM)
The start time is equivalent to 19:00 (7PM) in Central...
|
by: Mushico |
last post by:
How to calculate date of retirement from date of birth
|
by: DJRhino |
last post by:
Was curious if anyone else was having this same issue or not....
I was just Up/Down graded to windows 11 and now my access combo boxes are not acting right. With win 10 I could start typing...
|
by: Aliciasmith |
last post by:
In an age dominated by smartphones, having a mobile app for your business is no longer an option; it's a necessity. Whether you're a startup or an established enterprise, finding the right mobile app...
|
by: tracyyun |
last post by:
Hello everyone,
I have a question and would like some advice on network connectivity. I have one computer connected to my router via WiFi, but I have two other computers that I want to be able to...
|
by: NeoPa |
last post by:
Hello everyone.
I find myself stuck trying to find the VBA way to get Access to create a PDF of the currently-selected (and open) object (Form or Report).
I know it can be done by selecting :...
|
by: NeoPa |
last post by:
Introduction
For this article I'll be using a very simple database which has Form (clsForm) & Report (clsReport) classes that simply handle making the calling Form invisible until the Form, or all...
|
by: Teri B |
last post by:
Hi, I have created a sub-form Roles. In my course form the user selects the roles assigned to the course.
0ne-to-many. One course many roles.
Then I created a report based on the Course form and...
|
by: NeoPa |
last post by:
Introduction
For this article I'll be focusing on the Report (clsReport) class. This simply handles making the calling Form invisible until all of the Reports opened by it have been closed, when it...
| |