Re: What's WRONG With My Code ???

From: Thomas Matthews (Thomas_MatthewsSpitsOnSpamBots_at_sbcglobal.net)
Date: 02/23/04 

Date: Mon, 23 Feb 2004 15:01:37 GMT

sugaray wrote:

> 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[i]=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

Relevant Pages