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 14244
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 discussion thread is closed Replies have been disabled for this discussion. Similar topics
9 posts
views
Thread by Perpetual Snow |
last post: by
|
19 posts
views
Thread by RAJASEKHAR KONDABALA |
last post: by
|
4 posts
views
Thread by dssuresh6 |
last post: by
|
11 posts
views
Thread by Neo |
last post: by
|
11 posts
views
Thread by sam_cit |
last post: by
| | |
6 posts
views
Thread by Hamster |
last post: by
| | | | | | | | | | |