linked list

[yudi1226]

Oh,sorry!

Please don't post C++ to comp.lang.c.

 

[junky_fellow]

If space and recursion are issues, consider reversing the list
(non-recursive, O(1) space, O(n) time), then printing the contents, then
reversing it again. Better than the O(n^2) stop element solution you've
proposed.

-nrk.

seems to be a nice solution. This is what i exactly wanted. i would also
suggest one improvement i.e. first reverse it, then reverse it while you
are printing. No need to first print and then reverse.
anyway, thanx a lot.

 

[pete]

assert(head != NULL); /* !! */

I don't swing that way.

 

[m...@home]

for a case have enough room without reverse the string:

struct node *list; //assume list is the head of the list

r_prt(struct node *list) {
if (list->next != NULL)
r_prt(node *list->next);
putchar(c);
}

main() {
:
r_prt(list);
putchar('\n');
}

enjoy it!

My DS-9000 could do it without filling its top-level cache. (-:

For any list being procesed by someone who needs to ask this
question, the scenario you posit seems improbable - and for
reasonable list sizes, I think it'd be a not-too-difficult and
instructive exercise - and hardly cruel.

Of course, it's also possible to count the list elements and
malloc an appropriate-sized array that could be filled backwards,
puts'd, and freed - I guess it'd all depend on whether the
exercise is intended to focus on memory management functions or
to explore solution techniques.

So, what does junky_fellow do if there isn't room to build this
horrendous string and malloc fails? Well, he could also consider
making a pass through the list for each character, moving the
stop point back by one element for each pass...

--
Morris Dovey
West Des Moines, Iowa USA
C links at http://www.iedu.com/c
Read my lips: The apple doesn't fall far from the tree.

~ Let us linux ~

 

[Brian MacBride]

nrk <[email protected]> wrote in message

seems to be a nice solution. This is what i exactly wanted. i would also
suggest one improvement i.e. first reverse it, then reverse it while you
are printing. No need to first print and then reverse.
anyway, thanx a lot.

Actually, you may want to do something else with the list once you have it
reversed. Or you may not need the list anymore so there is no need to rereverse
the list. Also, you need only one print function...

Consider...

#include <stdio.h>
#include <stdlib.h>

struct node {
char c;
struct node *next;
};

void enlist (struct node **np, const char c) {
while (*np)
np = &(*np)->next;
*np = calloc (1, sizeof **np);
(*np)->c = c;
}

void print (const struct node *n) {
while (n) {
printf ("%c", n->c);
n = n->next;
}
printf ("\n");
}

void silver (struct node **np) {
struct node *cur = *np, *last = 0;
while (cur) {
cur = (*np)->next;
(*np)->next = last;
if (cur) {
last = *np;
*np = cur;
}
}
}

void unlist (struct node **np) {
struct node *cur;
while (*np) {
cur = *np;
*np = (*np)->next;
free (cur);
}
}

int main (void) {
struct node *list = 0;
const char *const s = "12345", *p = s;
while (*p)
enlist (&list, *p++);

print (list);

silver (&list);
print (list);

unlist (&list);
return 0;
}

/*
12345
54321
*/

 

[Peter Nilsson]

I don't swing that way.

You don't think the function should handle the case where 'head' is an empty
list (i.e. a null pointer)?

 

[pete]

You don't think the function should handle
the case where 'head' is an empty list (i.e. a null pointer)?

No. There's no need to pass NULL to such a function.
You can check for NULL prior to calling the function,
if you have an algorithm which might attempt something like that.

 

[Peter Nilsson]

No. There's no need to pass NULL to such a function.
You can check for NULL prior to calling the function,
if you have an algorithm which might attempt something like that.

I see a _requirement_ for handling empty lists here on the grounds of
completeness. [For instance, I'm glad strlen() works on strings where the
first byte is null.]

Why should the caller be potentially lumbered with a tedious check when the
meaning of reversing an empty list is self evidently consistent with the
algorithm!

Would you require non empty lists for a list concatenation function too?!

 

[pete]

No. There's no need to pass NULL to such a function.
You can check for NULL prior to calling the function,
if you have an algorithm which might attempt something like that.

I see a _requirement_ for handling empty lists here on the grounds of
completeness.
[For instance, I'm glad strlen() works on strings where the
first byte is null.]

The function takes a pointer to a list.
NULL doesn't point to an empty list.

 

[Peter Nilsson]

Peter Nilsson wrote:

[re: node *list_reverse(node *head) ]

You don't think the function should handle
the case where 'head' is an empty list (i.e. a null pointer)?

No. There's no need to pass NULL to such a function.
You can check for NULL prior to calling the function,
if you have an algorithm which might attempt something like that.

I see a _requirement_ for handling empty lists here on the grounds
of completeness.
[For instance, I'm glad strlen() works on strings where the
first byte is null.]

The function takes a pointer to a list.
NULL doesn't point to an empty list.

It doesn't _point_ to one no, it _is_ an empty list precisely because it
doesn't point to a head node. In the same way, you tell a tail node by the
fact that its 'next' pointer is an empty list.

I'm still interested in an answer to...

Would you require a count (elements) function to only operate on non-empty
lists?

Why should _any_ list manipulation and algorithm functions not cater for
empty lists?

I just don't understand your philosophy of excluding a perfectly consistent
and unambiguous null pointer as an empty list.

 

[pete]

[For instance, I'm glad strlen() works on strings where the
first byte is null.]

I just don't understand your philosophy of excluding
a perfectly consistent
and unambiguous null pointer as an empty list.

It's along the same lines as strlen(NULL) being undefined.

 

[yudi1226]

I'm so sorry!

The follow :
/***************************************************/
#include <stdio.h>
#include <stdlib.h>

typedef struct _linklist
{
char data ;
struct _linklist *next ;
} LINKLIST;

int main()
{


LINKLIST * ll_begin,* ll_end ;
int i ;

LINKLIST *ll_store_end,*ll_store_begin ,*ll_cur;
LINKLIST *ll_temp ;

ll_begin = NULL ;
ll_end = NULL ;


for(i = 0 ; i < 5 ; i++ )
{
ll_temp = (LINKLIST *)malloc(sizeof(LINKLIST)) ;
printf("Pls input :") ;

scanf("%c",&ll_temp->data);

if(ll_begin == NULL )
{
ll_begin = ll_temp ;
ll_end = ll_temp ;
}
else
{
ll_end->next = ll_temp ;
ll_end = ll_temp ;
ll_end->next = NULL ;
}//if(ll_begin == NULL )

fflush(stdin);

} //for(int = 0 ; i < 5 ; i++ )



ll_store_end = ll_end ;
ll_store_begin = ll_begin;



//Loop LINKLIST
ll_store_end->next = ll_store_begin ;


ll_cur = ll_store_end ;
ll_store_begin = ll_store_end ;

do
{
printf("%c", ll_cur->data) ;
while(ll_cur->next != ll_store_end)
{
ll_cur = ll_cur->next ;
}
ll_store_end = ll_cur ;
}while(ll_cur != ll_end) ;
printf("\n");


//destructor loop LINKLIST
ll_end->next = NULL ;


return 0 ;
}

 

[pete]

fflush(stdin);

That's undefined behavior.

N869
7.19.5.2 The fflush function
Description
[#2] If stream points to an output stream or an update
stream in which the most recent operation was not input, the
fflush function causes any unwritten data for that stream to
be delivered to the host environment to be written to the
file; otherwise, the behavior is undefined.

 

[CBFalconer]

I'm so sorry!

The follow :
/***************************************************/
#include <stdio.h>
#include <stdlib.h>

typedef struct _linklist
{
char data ;
struct _linklist *next ;
} LINKLIST;

int main()
{

LINKLIST * ll_begin,* ll_end ;
int i ;

LINKLIST *ll_store_end,*ll_store_begin ,*ll_cur;
LINKLIST *ll_temp ;

ll_begin = NULL ;
ll_end = NULL ;

for(i = 0 ; i < 5 ; i++ )
{
ll_temp = (LINKLIST *)malloc(sizeof(LINKLIST)) ;
printf("Pls input :") ;

scanf("%c",&ll_temp->data);

if(ll_begin == NULL )
{
ll_begin = ll_temp ;
ll_end = ll_temp ;
}
else
{
ll_end->next = ll_temp ;
ll_end = ll_temp ;
ll_end->next = NULL ;
}//if(ll_begin == NULL )

fflush(stdin);

} //for(int = 0 ; i < 5 ; i++ )

ll_store_end = ll_end ;
ll_store_begin = ll_begin;

//Loop LINKLIST
ll_store_end->next = ll_store_begin ;

ll_cur = ll_store_end ;
ll_store_begin = ll_store_end ;

do
{
printf("%c", ll_cur->data) ;
while(ll_cur->next != ll_store_end)
{
ll_cur = ll_cur->next ;
}
ll_store_end = ll_cur ;
}while(ll_cur != ll_end) ;
printf("\n");

//destructor loop LINKLIST
ll_end->next = NULL ;

return 0 ;
}

What is your question? Before answering that try to improve your
code formatting and eliminate those C99 only // comments.