Solved

Graphics and Linked List Under C++

Posted on 1998-09-08
6
205 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
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

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
The viewer will learn how to use and create new code templates in NetBeans IDE 8.0 for Windows.
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.

749 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