Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

sparce array in pascal-SOS

linked list array

  • Please log in to reply
3 replies to this topic

#1 galileo

galileo

    CC Lurker

  • Just Joined
  • Pip
  • 5 posts

Posted 27 October 2008 - 05:50 AM

hi to everyone...i would you to help me because i'm a newb in pascal and i have a homework to do till wednesday, thursday i must give the program to my professor...he wants us to write down a code in pascal so as to build a sparce array that we will after use it as base to build a spanning tree...we have already done a single list with one pointer looking the next record in list and after that we put another pointer that looks opposite, so we made a double linked list.now he wants us to make a sparse array only with the non-zero elements that will have lists: for the rows and for the columns and wants 4 pointers in each list up,down,next,previous..we must also make the program in away that recognizes what happens when we have an interception point. for example in the a[i,j] element that is non zero how the element is linked with the i-st row kai j-st column, to include dispose command because he says that we will need it for the spanning tree etc.can anyone send me the code in a txt or pas file, so that i can understand how the program is built???thanx everyone for your time...
  • 0

#2 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 27 October 2008 - 07:40 AM

First question: can you diagram out how the nodes will relate to each other? The issue isn't that you need code, the issue is that you need to understand the overall and detailed structure.
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/


#3 galileo

galileo

    CC Lurker

  • Just Joined
  • Pip
  • 5 posts

Posted 27 October 2008 - 09:08 AM

well i found the logic structure of the program in a book of turbo pascal, but it makes the code differently from what i want...in this example it says that we can register a column or a row of a sparse array A[i,j] into a cyclic linked list with one head-element.each head-element has 4 fields:down,head,right,next. down field is used to link the head-element with a column list and right field for its link with a row list.head field is used for the differentiation of the head-elements from the non zero elements of the array.finally next field just links the heads-elements between them.also the head-element for the i-st row may be also head for the j-st column.so the whole number of the heads-elements is max{n,m},n:number of rows, m:number of columns. every other element has besides head field, five more fields:row,column,down,right,value.down field is used for the link with the next non zero element of the same column, while right field is used for the link with the next non zero element of the same row. so if aij=/(:not equal)0 then head-false, value:=A[i,j], row:=i and column:=j,further this element is linked with the cyclic lists of the i-st row and j-st column, so it is common element for 2 different lists. now every head-element belongs to 3 lists; in one row list, one column list and into a list of heads-elements. [this last list has itself head-element that it is used for registering the dimensions of the array(where do we put that list,into the whole array or outside of it???)].[lets mention that a random selected element can be defined by using the head-element A of the list of heads-elements(???didn't understand why)].well except from my these 2questions i got the whole idea...but it's difficult for me to write down the code in one week...and i tried till now very hard...so because besides the master i also work and i don't have tle luxury of much free time,i was wondering if anyone can help me...if i see the code i will understand the theory(the logic) through the commands of pascal...thanx for your time!
  • 0

#4 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 27 October 2008 - 10:53 AM

A couple of comments.
1) I recommend you get a program that can produce flowcharts/diagrams. Dia and Dynamic Draw are both free and good quality (Dia is easier to use quickly, Dynamic Draw is more flexible/powerful).
2) I recommend you create a diagram of how the data in the sparse array is supposed to work. Looking at other people's code when you don't understand what is being modeled will only get you so far.
3) I strongly recommend that you break your thoughts into paragraphs, capitalize first letters of sentences, etc. This will make it easier for others to understand what you are attempting to say by breaking ideas into smaller chunks (also helpful when programming).

As an example, for a 10x10 sparse array, your data may look like the following:
0 0 0 0 0 0 0 4 0 0
0 1 0 0 0 3 0 0 0 0
0 0 0 0 2 0 0 0 5 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 7 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 9 0 0 0
This is the data we care about, but in reality, there will be additional overhead data, such as the four pointers at each non-zero value. This is where having a diagram can come in handy: write down all the data at each position. The data element itself, the 4 pointers, and anything else handy. Write down the data that exists outside the positions, the head pointer, any row/column head pointers, etc.

Once you've done that, you can look at what happens when you add a new non-zero entry (what pointers have to be updated? what will its data be?). You can also look at what happens when you clear a non-zero entry (what pointers are affected by the removal of this location? what should they point to now?). For both activities, are there any boundary conditions (such as updating the overall head pointer, or some of the location's pointers not pointing to anything)?

As you review other people's code, you will see the results of this type of thinking, but not the reasoning itself. You can write this code in a few hours once you understand what you are trying to accomplish in detail.
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/






Also tagged with one or more of these keywords: linked list, array

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download