• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 252
  • Last Modified:

Pointers

I have made a program (for practic wise)to find the highest and lowest value of a set of numbers using arrays. But I am having trouble converting the program so that it would use pointers instead, not limiting how much data the user is allowed to input.

This is my current code:
program HighestLowest;

uses crt;

Const
Maxnum = 1000;

type
from1toMax = 1..Maxnum;
hmax = array [from1toMax] of real;

var
counter : from1toMax;  
new : string;          
high, low : real;      
times : integer;    
exit : char;          
realnum : hmax;            
error : integer;            

procedure sortarray (var realnum:hmax; times:integer; counter:from1toMax);

var
Exchanged : boolean;
temp : real;
contin : char;

begin
clrscr;
writeln('The order of the numbers from the biggest to the smallest');
writeln;

if times = 0 then writeln('No Data available')

else
begin
repeat
Exchanged := False;
for counter := 2 to times do
if realnum[counter - 1] < realnum[counter] then
begin
temp := realnum[counter - 1];
realnum[counter - 1] := realnum[counter];
realnum[counter] := temp;
Exchanged := True
end;
until not (Exchanged);

for counter := 1 to times do
begin
write(counter, ':', realnum[counter],'    ');

if (counter mod 3 = 0) then writeln;

if (counter mod 60 = 0) then
begin
writeln;
writeln('press C to view the rest of the data');
repeat
contin := UpCase(ReadKey);
until contin = 'C';
writeln;
end;        
end;          
writeln;
end;            
end;            

begin          
repeat      
times := 0;

clrscr;
writeln('Type in a maximum of 999 numbers - one on each line');
writeln('The number should be no longer than 39 digits in length');
writeln('The computer will display the numbers in descending order');
writeln('Type -exit- when you wish to stop inputting');
writeln('If you type other letters you would be asked to r''enter');
writeln;

repeat
times := times + 1;

repeat
write('Number ', times, ' --- ');
readln(new);
val(new, realnum[times] , error);
until (error = 0) or (new = 'exit');      

until (times = Maxnum) or (new = 'exit');  
writeln;
times := times - 1;
sortarray(realnum,times,counter);

writeln;
writeln('Now do you wish to -r-un the program again or -q-uit');
write('selection --- ');
repeat
exit := UpCase(Readkey);
until (exit = 'Q') or (exit = 'R');

until exit = 'Q';  { end main repeat }
end.              { end of program }
0
dech
Asked:
dech
  • 9
  • 8
  • 4
  • +1
1 Solution
 
_lychee_Commented:
use a linked list structure... if i dun recall wrongly, just use something like:

type
  lstptr = ^lst;
  lst = record
      data: integer;
      next: lstptr;
  end;

to insert a value of say 5 to a list at lsthdr, u just have

var bozo: lstptr;
begin
   new(bozo);
   bozo^.data = 5;
   bozo^.next = lsthdr;
   lsthdr = bozo;
end;

something like that...
anyway, if u want a sorted list i suggest u do insertion sort...
0
 
BatalfCommented:
Hi

First of all, I hope Lychee won't be offended when I proposed the explanation and code below as an answer:-)

-------
I think this one would solve your problem.

First of all, you should avoid using "new" as a variable in your code.
Reason : It's a reserved word in Pascal, used to initialize Pointers.
Therefore I "renamed" it to "new1".

The changes I have done is in the Type-declaration :
   phmax = ^hmax;
in the var-declaration :
   new1 : string;
   realnum : phmax;

In the the program-code I have
put in
    new(realnum);
    and the ^ sign after all
    references to the realnum variable
    (the sign for a pointer)

   
   
program HighestLowest;

uses crt;

Const
Maxnum = 1000;

type
from1toMax = 1..Maxnum;
hmax = array [from1toMax] of real;
phmax = ^hmax;

var
counter : from1toMax;
new1 : string;
high, low : real;
times : integer;      
exit : char;          
realnum : phmax;
error : integer;

procedure sortarray (var realnum:hmax; times:integer; counter:from1toMax);

var
Exchanged : boolean;
temp : real;
contin : char;

begin

clrscr;
writeln('The order of the numbers from the biggest to the smallest');
writeln;

if times = 0 then writeln('No Data available')

else
begin
repeat
Exchanged := False;
for counter := 2 to times do
if realnum[counter - 1] < realnum[counter] then
begin
temp := realnum[counter - 1];
realnum[counter - 1] := realnum[counter];
realnum[counter] := temp;
Exchanged := True
end;
until not (Exchanged);

for counter := 1 to times do
begin
write(counter, ':', realnum[counter],'    ');

if (counter mod 3 = 0) then writeln;

if (counter mod 60 = 0) then
begin
writeln;
writeln('press C to view the rest of the data');
repeat
contin := UpCase(ReadKey);
until contin = 'C';
writeln;
end;
end;
writeln;
end;
end;

begin
new(realnum);
repeat
times := 0;

clrscr;
writeln('Type in a maximum of 999 numbers - one on each line');
writeln('The number should be no longer than 39 digits in length');
writeln('The computer will display the numbers in descending order');
writeln('Type -exit- when you wish to stop inputting');
writeln('If you type other letters you would be asked to r''enter');
writeln;

repeat
times := times + 1;

repeat
write('Number ', times, ' --- ');
readln(new1);
val(new1, realnum^[times] , error);
until (error = 0) or (new1 = 'exit');

until (times = Maxnum) or (new1 = 'exit');
writeln;
times := times - 1;
sortarray(realnum^,times,counter);

writeln;
writeln('Now do you wish to -r-un the program again or -q-uit');
write('selection --- ');
repeat
exit := UpCase(Readkey);
until (exit = 'Q') or (exit = 'R');

until exit = 'Q';  { end main repeat }
end.              { end of program }
 





0
 
BatalfCommented:
A little comment :
I haven't made these variables to pointers :


var
counter : from1toMax;    
new1 : string;            
high, low : real;      
times : integer;      
exit : char;          
error : integer;

They don't need much memory, so it shouldn't be important.

Batalf            
 
 
 
 
0
The 14th Annual Expert Award Winners

The results are in! Meet the top members of our 2017 Expert Awards. Congratulations to all who qualified!

 
dechAuthor Commented:
This method is still limited by the maximum value that you put when coding the program.
0
 
BatalfCommented:
Do you get any error-messages when you increase maxnum?

Batalf
0
 
BatalfCommented:
Do you get any error-messages when you increase maxnum?

Batalf
0
 
BatalfCommented:
In case of error : Does the errror message refer to the type-declaration or the var-declaration?
0
 
BatalfCommented:
In case of error : Does the errror message refer to the type-declaration or the var-declaration?
0
 
_lychee_Commented:
urrmm....
Batalf: i dun think he wants a array pointer... he wants to use pointers so that he can enter any number of numbers he wants... i din check ur code when u posted it originally...

dech: like i said, use linked lists....
sorting can either be done during data entry (in which case it is insertion sort) or after data entry (in which case a mergesort is the best option i think)...
0
 
BatalfCommented:
Lychee : Maybe you're right. I thought the clue her was to be able to have more records in an array.

Dech : Have you tried Lychees tip?
0
 
_lychee_Commented:
a mergesort function from sedgewick's algorithms:

z is a dummy node that ends lists... it points to itself (ie. z^.next=z) and serves as a sentinel (ie. z^.key=maximum possible value -- call it maxint)

type
    link = ^node;
    node = record
            key: integer;
            next: link;
    end;

var
    t, z: link;

function merge(a, b:link): link;
var c:link;
begin
   c:=z;
   repeat
     if (a^.key<=b^.key) then begin
       c^.next:=a; c:=a; a:=a^.next;
     end else begin
       c^.next:=b; c:=b; b:=b^.next;
     end;
   until c^.key=maxint;
   merge:=z^.next; z^.next:=z;
end;

function mergesort(c:link):link;
var a, b, head, todo, t:link;
    i, N:integer;
begin
   N:=1; new(head); head^.next:=c;
   repeat
     todo:=head^.next; c:=head;
     repeat
       t:=todo;
       a:=t; for i:=1 to N-1 do t:=t^.next;
       b:=t^.next; t^.next:=z;
       t:=b; for i:=1 to N-1 do t:=t^.next;
       todo:=t^.next; t^.next:=z;
       c^.next:=merge(a, b);
       for i:=1 to N+N do c:=c^.next;
     until todo=z;
     N:=N+N;
   until a=head^.next;
   mergesort:=head^.next;
end;


end;
0
 
_lychee_Commented:
oh dear... u dun need t in the main body... just need z..
the initialisation for z is

z^.next:=z;
z^.key:=maxint;
0
 
_lychee_Commented:
hmmm... perhaps it wasn't too wise of me to just put the mergesort code there... after all it IS more instructive to derive it urself.... but anyway, here's how mergesort works (in english...):

split the list in two.
sort the two halves.
merge the two halves.

as u can see, it is obviously recursive (the sort used for the 2 halves is mergesort) and also it is a divide and conquer with the recurrence relation (i think) T(n) = 2T(n/2) + O(n) which makes
O(n)=nlgn which is the best u can do for sorting...

how to merge?? well... the principle is easy... merging of 2 lists (A and B) to 1 (C) follows the following rules:

1. if A or B is empty, add the remaining one to C.
2. add the min(start of A, start of B) to C and advance A or B accordingly.

nice and elegant right?

i gave the code for insertion in my first comment... basically the principle is

1. put the current list at the end of the new item
2. the new item becomes the head of the list
0
 
_lychee_Commented:
oops again... it should be
T(n)=O(nlgn) sorry for the mistake...
0
 
dechAuthor Commented:
Thanks lychee but I am not familiar with what you have suggusted, so I will time to look it up. Could you actually change my original program so that I can study the method knowing what it does. I will adjust the points accordingly.
0
 
_lychee_Commented:
here goes.... i'm not entirely sure it works perfectly, since i'm coding direct into the comment box (pascal's not accessible at the mmt).... i'm not going to implement some parts (like the re-running) and i might miss out some others accidentally but the basic thing'll be there...

program something;

uses crt;

const
   maxreal=1.7e38;

type
   listptr = ^list;
   list = record
      val: real;
      next: listptr;
   end;

var
   head, z, t: listptr;
   s: string;
   r: real;
   i: integer;

procedure listinsert(var h: listptr; k: real);
var t: listptr;
begin
   new(t);
   t^.next:=h;
   t^.val:=k;
   h:=t;
end;

function merge(a, b: listptr):listptr;
var
   s, t: listptr;
begin
   { more understandable i guess.... }
   if (a=z) then begin
      merge:=b; exit;
   end;
   if (b=z) then begin
      merge:=a; exit;
   end;
   if (a^.val<b^.val) then begin
      s:=a; a:=a^.next;
   end else begin
      s:=b; b:=b^.next;
   end;

   t:=s;
   while (t<>z) do begin
      if (a^.val<b^.val) then begin
         t^.next:=a; a:=a^.next;
         t:=t^.next;
      end else begin
         t^.next:=b; b:=b^.next;
         t:=t^.next;
      end;
   end;
   merge:=s;
end;

function sort(h: listptr): listptr;
var
   a, b, c: listptr;
begin
   { split the 2 lists }
   a:=h; b:=h^.next;
   while (b<>z) do begin
      a:=a^.next;
      b:=b^.next; b:=b^.next;
   end; { can u see that when b=z, a is halfway in? }

   b:=a^.next;
   a^.next:=z;  
   if (h<>z) then sort:=merge(sort(h), sort(b)) else sort:=z;
end;

begin
   new(z);
   z^.next:=z; z^.val:=maxreal;
   head:=z;
   n:=0;

   repeat
      writeln('Enter number or "exit"');
      readln(s);
      val(s, r, i);    
      if (i=0) then listinsert(head, r);
   until (UpCase(s)='EXIT');

   head:=sort(head);
   {print out the list and dispose at the same time}
   while (head<>z) do begin
      writeln(head^.val);
      t:=head;
      head:=head^.next;
      dispose(t);
   end;
end.


there.... i TEENK it should work....
0
 
BatalfCommented:
Any suggestions about the comment here dech?
0
 
hobbit123Commented:
OK. This is a code to do BubbleSort on a linked list.
You may find some lines strange, but I wrote it under Delphi. Replace readln's with readkey's in user-input parts;

type
 PListNode = ^TListNode;
 TListNode = record
  Value : real;
  Next : PListNode;
 end;

var
 ListHead : PListNode;
 ListTail : PListNode;

procedure AddNode(value : real);
{Add a node to our list}
var TmpNode : PListNode;
begin
 GetMem(TmpNode, SizeOf(TListNode));
 TmpNode^.Value:=Value;
 TmpNode^.Next:=nil;
 if Listhead=nil then begin
 {First node}
  ListHead:=TmpNode;
  ListTail:=TmpNode;
 end else begin
  ListTail^.Next:=TmpNode;
  ListTail:=TmpNode;
 end;
end;

procedure SwapNodes(var node1, node2 : PListNode);
{Swaps the values}
var tmp : real;
begin
 tmp:=Node1^.Value;
 Node1^.Value:=Node2^.Value;
 Node2^.Value:=tmp;
end;

procedure SortData;
var CurNode : PListNode;
    Exchanged : boolean;
begin
repeat
 CurNode:=ListHead;
 Exchanged:=FALSE;
 repeat {Go through the list}
  if CurNode^.Value<CurNode^.Next^.Value then begin
   SwapNodes(CurNode, CurNode^.Next);
   Exchanged:=TRUE;
  end;
  CurNode:=CurNode^.Next;
 until CurNode^.Next=nil;
until not Exchanged;
end;

procedure WriteList;
var
 counter : word;
 CurNode : PListNode;
 a       : string;
begin
 counter:=1;
 CurNode:=ListHead;
 repeat
  write(Counter,':',CurNode^.Value,' ');
  if (counter mod 3 = 0) then writeln;
  if (counter mod 3 = 60) then begin
   writeln('Press C to continue');
   repeat
    readln(a); {Change to ReadKey!}
   until a[1] in ['c','C'];
  end;
 CurNode:=CurNode^.Next;
 inc(counter);
 until CurNode=nil;
end;

procedure FreeList;
{Frees memory}
var Next, CurNode : PListNode;
begin
CurNode:=ListHead;
repeat
 Next:=CurNode^.Next;
 FreeMem(Next, SizeOf(TListNode));
 CurNode:=Next;
until CurNode=nil;
FreeMem(ListHead, SizeOf(TListNode));
ListHead:=nil;
ListTail:=nil;
end;

var
 Line : string;
 V    : real;
 Code : integer;
begin
 ListHead:=nil;
 ListTail:=nil;
 writeln('Enter numbers, press x to finish.');
 repeat
  readln(line);
  Val(line, V, Code);
  if Line[1]='x' then break; {Change to ReadKey}
  if Code<>0 then writeln('Error')
  else AddNode(V);
 until FALSE;
 SortData;
 WriteList;
 FreeList;
 readln;
end.
0
 
BatalfCommented:
To Hobbit123
Why do you propose an answer when lychee_ are just waiting for some respons for his comment? :-(
0
 
hobbit123Commented:
To Batalf
Sorry, but I think this is what dech was looking for. You know - I had some time to write BubbleSort for lists and I was so proud (it took me 15 minutes :-) that I had to put it here. And this is an answer. I didn't propose a new algorithm - that's why that was put as an answer instead of a comment. Dech, if it's not what you want, reject it.

Hobbit123
0
 
hobbit123Commented:
To Batalf
Sorry, but I think this is what dech was looking for. You know - I had some time to write BubbleSort for lists and I was so proud (it took me 15 minutes :-) that I had to put it here. And this is an answer. I didn't propose a new algorithm - that's why that was put as an answer instead of a comment. Dech, if it's not what you want, reject it.

Hobbit123
0
 
_lychee_Commented:
(i hope i don't come across as being grouchy cos i'm not but i don't feel that hobbit's reply was too good :)

the task at hand is "to find the highest and lowest value of a set of numbers"... not to implement bubblesort... i suggested merge sorting cos it is quite a natural sorting operation to perform on a linked list. Not to mention it's algorithmically more efficient...

also, i did not suggest it as an answer simply cos i just don't normally hit 'answer'... i do think that my code fits the requirements... of course i'm not too sure that it works perfectly but then again, so aren't u...

and if i wanted to be picky i could point out to you that your node insertion proc is not good... your AddNode could be changed to like:

..... [allocate memory for TmpNode]
TmpNode^.Value:=Value;
TmpNode^.Next:=ListHead;
ListHead:=TmpNode;

ListTail and the if-then-else statement are totally extraneous.

I also think procedurising the swap routine isn't very wise... u should just inline it... if the compiler's not smart enuff you're gonna waste time calling it and setting up the stack frame...

my 2 cents...
lychee
0
 
hobbit123Commented:
lychee,

The original program was using BubbleSort. That's why I proposed BubbleSort for linked lists.

I am adding new nodes at the end to preserve the original order of elements. This is sometimes important when comparing various sorting algorithms.
I moved the swap code into separate procedure to make my program easier to understand and show the similarity to the original one.
And I don't think it should be a speed daemon. If you want it to be _really_ fast, don't write it in Pascal :-)
Dech - say something. The question is locked due to my - MY - mistake. Accept it, reject it, post a comment - whatever. We are waiting ;-)

                    Hobbit
0
 
dechAuthor Commented:
Thanks to everyone who help
0

Featured Post

Keep up with what's happening at Experts Exchange!

Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.

  • 9
  • 8
  • 4
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now