What's WRONG With My Code ???

[sugaray]

hi, I wrote a simple program which merge two single linked lists into one
for practice, but it always freezes after the creation of the first list,
hope someone might help me out with this. thanx in advance.


#include <cstdio>
#include <cstdlib>
#include <ctime>

struct LinkList {
int data;
LinkList *next;
};

LinkList *CreateList(int size) {
LinkList *head=new LinkList;
LinkList *node,*current=head;
bool *f=new bool[size]; // sentinel for distribution
int i;

for(i=0;i<size;++i) f=false;

for(i=0;i<size;++i) {
LinkList *node=new LinkList;

// to distribute random numbers equally
do node->data=rand()%size+1;
while(f[node->data]);
f[node->data]=true;

current->next=node;
current=node;
}
current->next=NULL;

delete[] f;

return head;
}

LinkList *ListTail(LinkList *head) {
LinkList *prev,*ptr=head;
while(ptr) {
prev=ptr;
ptr=ptr->next;
}

return prev;
}

void DisplayList(LinkList *head,int column) {
LinkList *ptr=head->next;
int count=0;
while(ptr) {
if(count%column==0)
printf("\n");
cout<<ptr->data;
ptr=ptr->next;
count++;
}
cout<<endl<<"NUll"<<endl;
}

int main(int argc,char **argv)
{
if(argc!=3) exit(1); // expect two arguments

srand(time(NULL));
int size=atoi(argv[1]); // size of the list
int column=atoi(argv[2]); // column for each row when displayed on the screen

LinkList *head1=CreateList(size);
DisplayList(head1); // the program cease execution after this line
LinkList *head2=CreateList(size);
DisplayList(head2);
LinkList *tail1=ListTail(head1); // get the tail of the first list
tail1->next=head2; // merge by pointing to the head of the second list
DisplayList(head1,column);

return 0;
}

 

[Sharad Kala]

hi, I wrote a simple program which merge two single linked lists into one
for practice, but it always freezes after the creation of the first list,
hope someone might help me out with this. thanx in advance.

The code you posted does not even compile.
Post the minimal code that can reproduce your problem so that
someone here can help you.

-Sharad

 

[Ivan Vecerina]

bool *f=new bool[size]; // sentinel for distribution
int i;
for(i=0;i<size;++i) f=false;

This is unnecessarily complicated.
You really should consider using something like:
std::vector<bool> f(size);
This allocates and initializes (to 0) the array.
And the memory will automatically be released when done.
(Note: because vector<bool> is a rather hacked special
case in the standard, best is to replace it with

for(i=0;i<size;++i) {
LinkList *node=new LinkList;

// to distribute random numbers equally
do node->data=rand()%size+1;
while(f[node->data]);

Range error here. node->data is in range [1..size],
while valid values in f[...] are [0..size-1].
This is undefined behavior.

In practice on your platform, the program probably
reads a non-false value in f[size], so the last
random number will never be generated.

A quick work-around could be to increase the size
of your array of flags:
std::vector<char> f(size+1);

But there are better ways to generate a randomly ordered
sequence. For example using std::random_shuffle.


hth,
Ivan

 

[Thomas Matthews]

hi, I wrote a simple program which merge two single linked lists into one
for practice, but it always freezes after the creation of the first list,
hope someone might help me out with this. thanx in advance.


#include <cstdio>
#include <cstdlib>
#include <ctime>

struct LinkList {
int data;
LinkList *next;
};

1. I would call the structure a node. A linked list is
a collection of nodes.
2. Place the structure definition in a header file and the
functions into another source file. You will probably
be using this data type for other programs.

LinkList *CreateList(int size) {
LinkList *head=new LinkList;
LinkList *node,*current=head;

Prefer one declaration per line.

bool *f=new bool[size]; // sentinel for distribution
int i;

for(i=0;i<size;++i) f=false;

for(i=0;i<size;++i) {
LinkList *node=new LinkList;

// to distribute random numbers equally
do node->data=rand()%size+1;
while(f[node->data]);
f[node->data]=true;

current->next=node;
current=node;
}
current->next=NULL;

delete[] f;

return head;
}

The traditional approach is to separate creation of a list
from the insertion (or removal) of items in the container.
For example, create an empty list, then insert your random
numbers into the list. Have the list create a new node,
populate it with the data you pass, then insert it into
the list.

LinkList *ListTail(LinkList *head) {
LinkList *prev,*ptr=head;
while(ptr) {
prev=ptr;
ptr=ptr->next;
}

return prev;
}

If you care to add another pointer to the List header structure
you could save a pointer to the tail node and avoid this
searching.

struct Node
{
unsigned int data;
Node * next;
};

struct Double_Link_Node
: public Node
{
Double_Link_Node * prev;
};

struct Linked_List
{
unsigned int size; // items in container.
Node * head;
Node * tail;
};

void DisplayList(LinkList *head,int column) {
LinkList *ptr=head->next;
int count=0;
while(ptr) {
if(count%column==0)
printf("\n");
cout<<ptr->data;
ptr=ptr->next;
count++;
}
cout<<endl<<"NUll"<<endl;
}

I would move the display and tail methods into the
Linked List structure:
struct Linked_List
{
unsigned int size;
Node * head;
Node * tail;

void Display(ostream& out);
Node * Tail(void) const
{
return tail;
}
};

void
Linked_List ::
Display(ostream& out)
{
Node * p = head;
while (p)
{
out << p->data << '\n';
// If you overload operator<< for the Node
// structure, the above statement becomes:
// out << *p << '\n';
p = p->next;
}
out.flush();
return;
}

int main(int argc,char **argv)
{
if(argc!=3) exit(1); // expect two arguments

srand(time(NULL));
int size=atoi(argv[1]); // size of the list
int column=atoi(argv[2]); // column for each row when displayed on the screen

LinkList *head1=CreateList(size);
DisplayList(head1); // the program cease execution after this line
LinkList *head2=CreateList(size);
DisplayList(head2);
LinkList *tail1=ListTail(head1); // get the tail of the first list
tail1->next=head2; // merge by pointing to the head of the second list
DisplayList(head1,column);

return 0;
}

int main(void)
{
Linked_List list_one;
list_one.insert(5);
list_one.Display(cout);
return 0;
}


--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book