XXXXXX.working.in.my.blood wrote:
hi all,
i need help with linked lists...
the problem is this, "reverse the contents of a singly linked list
without using a temporary node"...
solution with code will be appreciated...
I can't imagine how a temporary node would be helpful.
/* BEGIN list.h */
#ifndef H_LIST
#define H_LIST
typedef struct list_node {
struct list_node *next;
void *data;
} list_type;
list_type *list_make(long unsigned);
list_type *list_rev(list_type *);
list_type *list_sort(list_type *,
int (*)(const list_type *, const list_type *));
void list_free(list_type *, void (*)(void *));
#endif
/* END list.h */
/* BEGIN list.c */
#include <stdlib.h>
#include "list.h"
static long unsigned list_count(list_type *);
static list_type *node_sort(list_type *, long unsigned,
int (*)(const list_type *, const list_type *));
static list_type *list_merge(list_type *, list_type *,
int (*)(const list_type *, const list_type *));
static list_type *list_split(list_type *, long unsigned);
list_type *list_rev(list_type *head)
{
list_type *next_node, *previous;
if (head != NULL) {
next_node = head -> next;
head -> next = NULL;
while (next_node != NULL) {
previous = next_node -> next;
next_node -> next = head;
head = next_node;
next_node = previous;
}
}
return head;
}
list_type *list_make(long unsigned count)
{
list_type *node, *list;
list = count != 0 ? malloc(sizeof *list) : NULL;
if (list != NULL) {
node = list;
while (--count != 0) {
node -> data = NULL;
node -> next = malloc(sizeof *node -> next);
if (node -> next == NULL) {
list_free(list, free);
return NULL;
} else {
node = node -> next;
}
}
node -> data = NULL;
node -> next = NULL;
}
return list;
}
void list_free(list_type *node, void (*free_data)(void *))
{
list_type *next_node;
while (node != NULL) {
next_node = node -> next;
free_data(node -> data);
free(node);
node = next_node;
}
}
list_type *list_sort(list_type *head,
int (*compar)(const list_type *, const list_type *))
{
return node_sort(head, list_count(head), compar);
}
static long unsigned list_count(list_type *head)
{
long unsigned count;
for (count = 0; head != NULL; head = head -> next) {
++count;
}
return count;
}
static list_type *node_sort(list_type *head, long unsigned count,
int (*compar)(const list_type *, const list_type *))
{
long unsigned half;
list_type *tail;
if (count > 1) {
half = count / 2;
tail = list_split(head, half);
tail = node_sort(tail, count - half, compar);
head = node_sort(head, half, compar);
head = list_merge(head, tail, compar);
}
return head;
}
static list_type *list_split(list_type *head, long unsigned count)
{
list_type *tail;
while (count-- > 1) {
head = head -> next;
}
tail = head -> next;
head -> next = NULL;
return tail;
}
static list_type *list_merge(list_type *head, list_type *tail,
int (*compar)(const list_type *, const list_type *))
{
list_type *list, *sorted, **node;
node = compar(head, tail) > 0 ? &tail : &head;
sorted = list = *node;
*node = sorted -> next;
while (*node != NULL) {
node = compar(head, tail) > 0 ? &tail : &head;
sorted -> next = *node;
sorted = *node;
*node = sorted -> next;
}
sorted -> next = head != NULL ? head : tail;
return list;
}
/* END list.c */
/* BEGIN list_sort.c */
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
#define NODES 17
#define LU_RAND_SEED 123456789LU
#define LU_RAND(S) ((S) * 69069 + 362437 & 0xffffffff)
struct score {
float literature;
float history;
float sociology;
};
int hist_score_comp(const list_type *, const list_type *);
void score_init(list_type *, long unsigned);
void score_print(list_type *);
int main(void)
{
list_type *score;
score = list_make(NODES);
if (score == NULL) {
fputs("The score list was not allocated.\n", stderr);
exit(EXIT_FAILURE);
}
score_init(score, LU_RAND_SEED);
puts("BEGIN output from list_sort.c\n\nRandom order");
score_print(score);
puts("Sorted on history");
score = list_sort(score, hist_score_comp);
score_print(score);
puts("Reverse Sorted order");
score = list_rev(score);
score_print(score);
puts("END output from list_sort.c\n");
list_free(score, free);
return 0;
}
void score_init(list_type *node, long unsigned seed)
{
while (node != NULL) {
node -> data = malloc(sizeof (struct score));
if (node -> data == NULL) {
fputs("malloc problem\n", stderr);
exit(EXIT_FAILURE);
}
seed = LU_RAND(seed);
((struct score *)node -> data) -> literature
= seed % 40 + 60.0f;
seed = LU_RAND(seed);
((struct score *)node -> data) -> history
= seed % 40 + 60.0f;
seed = LU_RAND(seed);
((struct score *)node -> data) -> sociology
= seed % 40 + 60.0f;
node = node -> next;
}
}
void score_print(list_type *node)
{
float score;
while (node != NULL) {
score = ((struct score *)node -> data) -> literature;
printf("literature %d ", (int)score);
score = ((struct score *)node -> data) -> history;
printf("history %d ", (int)score);
score = ((struct score *)node -> data) -> sociology;
printf("sociology %d\n", (int)score);
node = node -> next;
}
putchar('\n');
}
int hist_score_comp(const list_type *head, const list_type *tail)
{
float first = ((struct score *)head -> data) -> history;
float second = ((struct score *)tail -> data) -> history;
return second > first ? -1 : second != first;
}
/* END list_sort.c */
--
pete
