Doubly Linked List? 1

[Mercfh]

I was given an assignment for class (new class just started a week ago) for fortran.
I've done some reading on fortran and get the general syntax but had a question of what the "best" way to go about this would be.
here's the inquery:
"Write a program in Fortran that (1) reads in an integer n, (2) computes the sine of 1, 2, ..., n (in degrees), generating n floats, (3) inserts those n floats, one at a time, into an ordered doubly-linked list, then (4) prints the contents of the list in reverse order.

You may assume that n is less than 10,000. You must compute the sine values by using these relations:

sin (1) = 0.017452406437284
cos (1) = 0.999847695156391
sin (a + b) = sin (a) cos (b) + cos (a) sin (b)
cos (a + b) = cos (a) cos (b) - sin (a) sin (b)
By an ordered doubly-linked list I mean a list with nodes having pointers both to the next and the previous node, and with a dummy head node, ordered so that following the "next" pointers leads to non-decreasing values of the sines."

Problem is...I thought you couldn't do pointers in fortran?
either way I assume my best bet would be to create 3 linked lists? one to insert them. then sort, then insert the sorted list into another and reverse it?

Sorry I wish I had more ideas but i have never used a language like fortran before? so any ideas?

thanks

 

[mikrom]

Yes there are pointers in Fortran and /although I never tried it so far/ you can do linked lists - see here:

http://cs.ubishops.ca/ljensen/fortran/pointer.htm

For more examples google: Fortran linked list

 

[xwb]

There are many ways of doing this depending on which version of Fortran you're using. If you're using F90, there are pointers. If you're using F77, you can just declare an array and use the indices.

 

[Mercfh]

hmmm ok that makes sense.
I think we can do either tbh, i guess doing an array would be easier.

So would this be a good plan:
-->Read in n
:loop till n computing sine of n
in loop insert each into an array
:finish loop after n

start at tail of loop:
print n
go back n-1: till head is reached?

success?

 

[Mercfh]

actually nm ill just have to do the above but with a doubly linked list. <_<

 

[xwb]

Plan looks ok. You need 2 arrays: one 2d with integers, one 1D with reals.
The 2D uses index 1 as previous, 2 as next, 3 as index into the real array.

Say 1st value is 0.4, 2nd is 0.9, 3rd is 0.96

The index array will read

Index prev next index to real
1     -1   2    1
2      1   3    2
3      2   -1   3

Alternatively, you can make it into a circular list by changing the prev -1 to 3 and the next -1 to 1.

 

[Mercfh]

According to the program description it'll have to be a doubly linked list

so that kinda changes things

 

[xwb]

The tip I've given you is a doubly linked list in the integer array - if you want to use arrays instead of pointers.

Note that there are two types of pointers in Fortran. There are the normal Fortran pointers and something called Cray or C pointers. Fortran pointers are not interchangeable with other types of pointer but Cray pointers are. Not all compilers support Cray pointers.

 

[Mercfh]

Ya I think what you were saying is right. he said we have to use g77.
and said we'd prolly need 3 arrays to represent pointers. It makes more sense now that I read what you said.

all these diff fortran types are confusing you know lol especially when you've never sued fortran before ever in your life and are sos used to using c++

 

[xwb]

Well you might like to know that there are 4 versions of C++: version 1 in 1983, version 2 in 1989, version 3 in 1998 and the new proposed version 4.

Fortran has been around since the 50s which is 30 years longer: hence a lot more versions. F77 is version 5.

 

[Mercfh]

Well I tried populating the sin/cos array (to store) with this. but I keep getting an error about the DO statement ending with an integer?

	program dlink

c Matt Smith
c CS450
c sDatae Fortran Doubly Linked List Assignment 1
c23456789

        
        real n
	real sDatae,cDatae,sDatae1,cDatae1
	real sData(10000)
	real cData(10000)
        write(*,*), 'Input n for Number of sin Computations'
	read (*,*), n
	sData(1) = 0.017452406437284
	cData(1) = 0.999847695156391
	sData(2) = 0.0348994967025009
	cData(2) = 0.9993908270190958


	
	do 10 i = 2, n
	if(MODULO(i,2) .EQ. 0) GOTO 11
 11     sData(i) = (sData(i/2)*cData(i/2))+(cData(i/2)*sData(i/2))
	cData(i) = (cData(i/2)*cData(i/2))-(sData(i/2)*sData(i/2))
	goto 79
	if(MODULO(i,2) .EQ. 1) GOTO 12
 12	sData(i)= (sData(i/2)*cData(i/2+1))+(cData(i/2)*sData(i/2+1))
	cData(i)= (cData(i/2)*cData(i/2+1))-(sData(i/2)*sData(i/2+1))
	goto 79
 79	continue
 10     end do

	stop


		
	
	


	stop
	end

 

[mikrom]

I thing, that according to the above relations for the functions sin(x) and cos(s), when you set k = (k-1)+1 = a + b
then for the first given elements
v_sin(1), v_cos(1)
you can simplify the computation of other array elements so:
do k = 2, n
v_sin(k) = v_sin(k-1)*v_cos(1) + v_cos(k-1)*v_sin(1)
v_cos(k) = v_cos(k-1)*v_cos(1) - v_sin(k-1)*v_sin(1)
end do

 

[Mercfh]

ok i got sine/cos arrays working (they dont print right but I checked the numbers they are correct (using print sData(15) etc..)

	program dlink

c Matt Smith
c CS450
c sDatae Fortran Doubly Linked List Assignment 1
c23456789

        
        real n
	real sDatae,cDatae,sDatae1,cDatae1
	real sData(10000)
	real cData(10000)
        write(*,*), 'Input n for Number of sin Computations'
	read (*,*), n
	sData(1) = 0.017452406437284
	cData(1) = 0.999847695156391
	sData(2) = 0.0348994967025009
	cData(2) = 0.9993908270190958



	do 10 i = 2, 100
	if(MODULO(i,2) .EQ. 0) GOTO 11
 11     sData(i) = (sData(i/2)*cData(i/2))+(cData(i/2)*sData(i/2))
	cData(i) = (cData(i/2)*cData(i/2))-(sData(i/2)*sData(i/2))
	goto 79
	if(MODULO(i,2) .EQ. 1) GOTO 12
 12	sData(i)= (sData(i/2)*cData(i/2+1))+(cData(i/2)*sData(i/2+1))
	cData(i)= (cData(i/2)*cData(i/2+1))-(sData(i/2)*sData(i/2+1))
	goto 79
 79	continue
 10     end do

	
	do 20 integer s = 1, 100
	write(*,*) sData(4)
 20	end do

	stop



	stop
	end

ignore the write sData(4). i was just making sure they were correct.
now whats the best way of array indexing them into a doubly linked list. im assuming ill need 3 arrays, and index/next/ and prev.

any hints?

 

[Mercfh]

crap modula didnt work
this code does work using 1 and n-1

	program dlink

c Matt Smith
c CS450
c sDatae Fortran Doubly Linked List Assignment 1
c23456789

        
        real n
	real sDatae,cDatae,sDatae1,cDatae1
	real sData(10000)
	real cData(10000)
        write(*,*), 'Input n for Number of sin Computations'
	read (*,*), n
	sData(1) = 0.017452406437284
	cData(1) = 0.999847695156391
	



	do 10 i = 2, 100
	sData(i) = sData(i-1)*cData(1) + cData(i-1)*sData(1)	
	cData(i) = cData(i-1)*cData(1) - sData(i-1)*sData(1)
 10     end do

	
	do 20 integer s = 1, 10
	write(*,*) sData(17)
 20	end do

	stop

	stop
	end

again ignore the sData(17) i was manually entering outputsto check (and they do work)

 

[mikrom]

If you are using end do in do-loop you don't need to use label.
the obsolete form of do-loop is

    do 10 k = 1, 100
      <statements>
10  continue

the current form of do-loop is

do k = 1, n
  <statements>
end do

The g77 compiler supports besides of position oriented source form (fixed-form) so called free-form too, so you can write your program more naturally (like in another prog. languages):

[COLOR=#a020f0]program[/color] sin_cos
  [COLOR=#2e8b57][b]integer[/b][/color] Nmax, k
[COLOR=#2e8b57][b]  real[/b][/color] v_sin([COLOR=#ff00ff]1000[/color]), v_cos([COLOR=#ff00ff]1000[/color])

  [COLOR=#0000ff]! initial values[/color]
  Nmax [COLOR=#804040][b]=[/b][/color] [COLOR=#ff00ff]360[/color]
  v_sin([COLOR=#ff00ff]1[/color])[COLOR=#804040][b]=[/b][/color][COLOR=#ff00ff]0.017452406437284[/color]
  v_cos([COLOR=#ff00ff]1[/color])[COLOR=#804040][b]=[/b][/color][COLOR=#ff00ff]0.999847695156391[/color]

  [COLOR=#0000ff]! compute other values[/color]
  [COLOR=#804040][b]do[/b][/color] k [COLOR=#804040][b]=[/b][/color] [COLOR=#ff00ff]2[/color], Nmax
    v_sin(k) [COLOR=#804040][b]=[/b][/color] v_sin(k[COLOR=#804040][b]-[/b][/color][COLOR=#ff00ff]1[/color])[COLOR=#804040][b]*[/b][/color]v_cos([COLOR=#ff00ff]1[/color]) [COLOR=#804040][b]+[/b][/color] v_cos(k[COLOR=#804040][b]-[/b][/color][COLOR=#ff00ff]1[/color])[COLOR=#804040][b]*[/b][/color]v_sin([COLOR=#ff00ff]1[/color])
    v_cos(k) [COLOR=#804040][b]=[/b][/color] v_cos(k[COLOR=#804040][b]-[/b][/color][COLOR=#ff00ff]1[/color])[COLOR=#804040][b]*[/b][/color]v_cos([COLOR=#ff00ff]1[/color]) [COLOR=#804040][b]-[/b][/color] v_sin(k[COLOR=#804040][b]-[/b][/color][COLOR=#ff00ff]1[/color])[COLOR=#804040][b]*[/b][/color]v_sin([COLOR=#ff00ff]1[/color])  
  [COLOR=#804040][b]end do[/b][/color]

  [COLOR=#0000ff]! print all[/color]
  [COLOR=#804040][b]do[/b][/color] k [COLOR=#804040][b]=[/b][/color] [COLOR=#ff00ff]1[/color], Nmax
    [COLOR=#804040][b]if[/b][/color] (k[COLOR=#804040][b]==[/b][/color][COLOR=#ff00ff]1[/color] [COLOR=#804040][b].or.[/b][/color] [COLOR=#008080]mod[/color](k, [COLOR=#ff00ff]10[/color]) [COLOR=#804040][b]==[/b][/color] [COLOR=#ff00ff]0[/color]) [COLOR=#804040][b]then[/b][/color]
      [COLOR=#804040][b]write[/b][/color]([COLOR=#804040][b]*[/b][/color],[COLOR=#ff00ff]10[/color]) k, v_sin(k), k, v_cos(k)
    [COLOR=#804040][b]end if[/b][/color]
  [COLOR=#804040][b]end do[/b][/color]

  [COLOR=#0000ff]! define format[/color]
  [COLOR=#6a5acd]10[/color] [COLOR=#804040][b]format[/b][/color] ([COLOR=#ff00ff]'sin('[/color], i3, [COLOR=#ff00ff]') = '[/color], [COLOR=#008080]f7.4[/color], [COLOR=#ff00ff]', '[/color], [COLOR=#ff00ff]'cos('[/color], i3, [COLOR=#ff00ff]') = '[/color], [COLOR=#008080]f7.4[/color]) 
[COLOR=#a020f0]end[/color]

$ g77 sin_cos.f -o sin_cos -ffree-form

$ sin_cos
sin(  1) =  0.0175, cos(  1) =  0.9998
sin( 10) =  0.1736, cos( 10) =  0.9848
sin( 20) =  0.3420, cos( 20) =  0.9397
sin( 30) =  0.5000, cos( 30) =  0.8660
sin( 40) =  0.6428, cos( 40) =  0.7660
sin( 50) =  0.7660, cos( 50) =  0.6428
sin( 60) =  0.8660, cos( 60) =  0.5000
sin( 70) =  0.9397, cos( 70) =  0.3420
sin( 80) =  0.9848, cos( 80) =  0.1736
sin( 90) =  1.0000, cos( 90) =  0.0000
sin(100) =  0.9848, cos(100) = -0.1736
sin(110) =  0.9397, cos(110) = -0.3420
sin(120) =  0.8660, cos(120) = -0.5000
sin(130) =  0.7660, cos(130) = -0.6428
sin(140) =  0.6428, cos(140) = -0.7660
sin(150) =  0.5000, cos(150) = -0.8660
sin(160) =  0.3420, cos(160) = -0.9397
sin(170) =  0.1736, cos(170) = -0.9848
sin(180) =  0.0000, cos(180) = -1.0000
sin(190) = -0.1736, cos(190) = -0.9848
sin(200) = -0.3420, cos(200) = -0.9397
sin(210) = -0.5000, cos(210) = -0.8660
sin(220) = -0.6428, cos(220) = -0.7660
sin(230) = -0.7660, cos(230) = -0.6428
sin(240) = -0.8660, cos(240) = -0.5000
sin(250) = -0.9397, cos(250) = -0.3420
sin(260) = -0.9848, cos(260) = -0.1736
sin(270) = -1.0000, cos(270) =  0.0000
sin(280) = -0.9848, cos(280) =  0.1736
sin(290) = -0.9397, cos(290) =  0.3420
sin(300) = -0.8660, cos(300) =  0.5000
sin(310) = -0.7660, cos(310) =  0.6428
sin(320) = -0.6428, cos(320) =  0.7660
sin(330) = -0.5000, cos(330) =  0.8660
sin(340) = -0.3420, cos(340) =  0.9397
sin(350) = -0.1736, cos(350) =  0.9848
sin(360) =  0.0000, cos(360) =  1.0000

 

[Mercfh]

wow thanks a ton mikron! u have to remember this is my first stab at fortran.

now I need to figure out some way to order these using a doubly linked list with arrays.

I for sure will have 3 arrays (prev/next/data)
I know sorta how it works on paper....but the logic is a little screwy. anyone ever done a doubly linked list ordered with arrays as indexs before?

 

[mikrom]

Although the approach using arrays to emulate linked list seems to be very clever, I thing that so constructed data structure doesn't have the same properties as linked list.
Originally, linked list (with pointers) is a dynamical data structure - you don't need to know at the beginning the maximal number of elements, it shrinks by deleting of some elements or grows by appending new elements. When an element will be deleted, the memory used by it will be deallocated.
But ok - it is usefull as a programming exercise

Btw, have you asked your teacher why he/she teaches you a 30+ years old Fortran 77 standard, when the compilers for Fortran 90/95 are freely awailable?

 

[Mercfh]

haha no clue.
he's old and did all this stuff when he was younger.

but I mean the assignment was how he gave it (dont ask me why)

i ended up getting it to work in C++
it prints out the next/prev arrays showing the correct index's

just gotta sort through them and convert to fortran. if I have some trouble converting ill post it here. thanks for everyones help tho

 

[Mercfh]

welp im back. got my C++ code of the same thing working perfectly.

	program dlink

c Matt Smith
c CS450
c Sine Fortran Doubly Linked List Assignment 1
c23456789

        
        integer nmax
	real sData(10000)
	real cData(10000)
        write(*,*), 'Input n for Number of sin Computations'
	read (*,*), nmax
	

	sData(1) = 0.017452406437284
	cData(1) = 0.999847695156391
	



	do 10 i = 2, nmax
	sData(i) = sData(i-1)*cData(1) + cData(i-1)*sData(1)	
	cData(i) = cData(i-1)*cData(1) - sData(i-1)*sData(1)
 10     end do

	
	integer prev(10000)
	integer next(10000)
	
	prev(1) = -1
	next(1) = -1

	do 20 integer j = 1, nmax
	integer ptr=0
	
	do 30 integer h = 1, nmax
	if(sData(j)-sData(ptr))11,12,12
 11	next(prev(ptr))=j
	prev(j)=prev(ptr)
	prev(ptr)=j
	next(j)=ptr
	GOTO 15
	
	if(next(ptr) .EQ. -1) goto 39

 39	prev(j)=ptr
	next(j)=next(ptr)
	next(ptr)=j
	ptr=next(ptr)
	goto 15

 12     continue
    


 
 	

 30     continue
 15	j=next(j)
	
 20	continue
		
	
	


	stop
	end

But this code is just giving me TONS of errors? anyone know why?
it's even complaining about the next(0)=-1 and such?

 

[Mercfh]

hmmm got it to stop making too many errors, but now I get a segmentation fault?

	program dlink

c Matt Smith
c CS450
c Sine Fortran Doubly Linked List Assignment 1
c23456789

        
        integer nmax
	real sData(10000)
	real cData(10000)
	integer prev(10000)
	integer next(10000)
        write(*,*), 'Input n for Number of sin Computations'
	read (*,*), nmax
	
	
	prev(1) = -1
	next(1) = -1

	sData(1) = 0.017452406437284
	cData(1) = 0.999847695156391
	



	do 10 i = 2, nmax
	sData(i) = sData(i-1)*cData(1) + cData(i-1)*sData(1)	
	cData(i) = cData(i-1)*cData(1) - sData(i-1)*sData(1)
 10     continue

	
	

	do 20 integer j = 1, nmax
	integer ptr=1
	do 30 integer h = 1, nmax
	if(sData(j)-sData(ptr))11,12,12
 11	next(prev(ptr))=j
	prev(j)=prev(ptr)
	prev(ptr)=j
	next(j)=ptr
	GOTO 15
	
	if(next(ptr) .EQ. -1) goto 39

 39	prev(j)=ptr
	next(j)=next(ptr)
	next(ptr)=j
	ptr=next(ptr)
	goto 15

 12     continue
    


 
 	

 30     continue
 15	j=next(j)
	
 20	continue
		
	write(*,*), next(5)
	


	stop
	end

the write(*,*), next(5) was just a test