Solved

Graphics and Linked List Under C++

Posted on 1998-09-08
6
196 Views
Last Modified: 2013-12-14
1 - I Have Borland C++ Compiler (DOS) 3.0 , My Problem .. When i tried to load my graphic program, i've got error message in this compiler. althought i loaded this program under different system it works .. but under my compiler doesn't.

2 - I tried to do my Linked list and i done it .. my problem  how can i do my SORTING PROGRAM under Linked List ...

0
Comment
Question by:seyedsaatchi
  • 4
  • 2
6 Comments
 
LVL 6

Expert Comment

by:snoegler
ID: 1172308
1 : ???

Each graphics subsystem is usually compiler & system dependent. Can you give some more
infos( e.g. on which 'different' system did it work)?

2:

I remember there are various methods to sort linked lists. I know a quite simple method, it isn't
the fastest i think ...

a) Assign all your linked list items some sort of hash value which is sort order dependent,
perhaps like this:

unsigned long buildHash(char *text)
{
unsigned long ulValue=0;
int nPos;
for(nPos=0;nPos<4;nPos++) {
if(text[nPos]==0) break;
ulValue |= ((unsigned char)text[nPos])<<((3-nPos)*8);
}
return ulValue;
}
// example: HELLO -> 0x48454c4c

Then define a struct which takes the linked list item and its hash value:

struct _helper {
linkedlistitem *item;
unsigned long hash;
};

Build an array so that each linked-list item is contained, and then you can use the qsort()
function of C( or the STL implementation).
Then you can either use a bubble sort on the linked-list items which have the same hash
value - or you can proceed like above, assign those items with the same hash value a new
array, where the hash value starts with the 4th character.
In the worst case (all items are identical), you'll get O(N*N), in the best case, where all
(first) hash values are different, you'll get O(N).
0
 
LVL 4

Accepted Solution

by:
sganta earned 170 total points
ID: 1172309

Hi !
 The algorithm which I am giving is BUBBLE SORT.


      #include <stdio.h>

      #define NULL 0

      struct ptr {
                   int num;
                   struct ptr *next;
                 };

      typedef struct ptr pointer;

      void bubble_sort(pointer *node);

      void main(void)
      {
          pointer *list; /* This is a linked list */

          /* Here I am assuming that you've created a linked list
             i.e., ptr
          */

          bubble_sort(list);
      }

      void bubble_sort(pointer *node)
      {
         pointer *first,*second,*first_prev,*temp;
         int n=1;

         temp = node;
         first = node;
         first_prev = node;

         /* Get the no. of nodes in the linked list */
           
         while (first->link != NULL)
         {
            n++;
            first= first->link;
         }


         for (i=1; i<n; i++)
         {
            first = temp;
            first_prev = temp;
            second = first->next;

            for (j=1; j<=(n-i); j++)
            {
               if (first->num > second->num)
               {
                  if (first == temp)  /* If it is an header node */
                  {
                      first->next = second->next;
                      second->next = first;
                      temp = second;
                      first = second;
                   }
                  else
                  {
                      first->next = second->next;
                      second->next = first;
                      first_prev->next = second;
                      first = second;
                  }
                }
               
                first_prev = first;
                first = first->next;
                second = first->next;
             }                
          }

This is tested already and it works fine.
I hope this is acceptable to you.

If you have any specific doubts, pl. let me know.
0
 
LVL 6

Expert Comment

by:snoegler
ID: 1172310
Bubble sort is the slowest algorithm possible. Don't use it  ...
If you sort more than 1000 elements, even a Pentium II 400 goes down :)
0
Highfive Gives IT Their Time Back

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 
LVL 6

Expert Comment

by:snoegler
ID: 1172311
sganta:
Don't get me wrong - i don't want to insult you in any way.
But bubble sort is *really* slow. If we're talking of only 200 elements, it's okay :)
0
 
LVL 4

Expert Comment

by:sganta
ID: 1172312
Snolger !
Thank you for your comment. It is good to share the knowledge.

Regards
sganta

0
 
LVL 6

Expert Comment

by:snoegler
ID: 1172313
sganta, please don't get me wrong - i just *hate* the bubblesort algorithm.
0

Featured Post

Highfive Gives IT Their Time Back

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
Programmer's Notepad is, one of the best free text editing tools available, simply because the developers appear to have second-guessed every weird problem or issue a programmer is likely to run into. One of these problems is selecting and deleti…
The viewer will learn how to use and create new code templates in NetBeans IDE 8.0 for Windows.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

758 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

22 Experts available now in Live!

Get 1:1 Help Now