sugaray wrote:
[color=blue]
> 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;
> };[/color]
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.
[color=blue]
>
> LinkList *CreateList(int size) {
> LinkList *head=new LinkList;
> LinkList *node,*current=head;[/color]
Prefer one declaration per line.
[color=blue]
> 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;
> }[/color]
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.
[color=blue]
>
> LinkList *ListTail(LinkList *head) {
> LinkList *prev,*ptr=head;
> while(ptr) {
> prev=ptr;
> ptr=ptr->next;
> }
>
> return prev;
> }[/color]
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;
};
[color=blue]
> 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;
> }[/color]
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;
}
[color=blue]
>
> 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;
> }[/color]
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
