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

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
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, ' --- ');
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
until (exit = 'Q') or (exit = 'R');

until exit = 'Q';  { end main repeat }
end.              { end of program }
0
dech
• 9
• 8
• 4
• +1
1 Solution

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

Commented:
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
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, ' --- ');
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
until (exit = 'Q') or (exit = 'R');

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

0

Commented:
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

Author Commented:
This method is still limited by the maximum value that you put when coding the program.
0

Commented:
Do you get any error-messages when you increase maxnum?

Batalf
0

Commented:
Do you get any error-messages when you increase maxnum?

Batalf
0

Commented:
In case of error : Does the errror message refer to the type-declaration or the var-declaration?
0

Commented:
In case of error : Does the errror message refer to the type-declaration or the var-declaration?
0

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

Commented:
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

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
node = record
key: integer;
end;

var

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;

i, N:integer;
begin
repeat
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;
end;

end;
0

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

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

Commented:
oops again... it should be
T(n)=O(nlgn) sorry for the mistake...
0

Author 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

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
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;
n:=0;

repeat
writeln('Enter number or "exit"');
val(s, r, i);
until (UpCase(s)='EXIT');

{print out the list and dispose at the same time}
dispose(t);
end;
end.

there.... i TEENK it should work....
0

Commented:
Any suggestions about the comment here dech?
0

Commented:
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
ListTail : PListNode;

{Add a node to our list}
var TmpNode : PListNode;
begin
GetMem(TmpNode, SizeOf(TListNode));
TmpNode^.Value:=Value;
TmpNode^.Next:=nil;
{First node}
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
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;
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
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
repeat
Next:=CurNode^.Next;
FreeMem(Next, SizeOf(TListNode));
CurNode:=Next;
until CurNode=nil;
ListTail:=nil;
end;

var
Line : string;
V    : real;
Code : integer;
begin
ListTail:=nil;
writeln('Enter numbers, press x to finish.');
repeat
Val(line, V, Code);
if Line[1]='x' then break; {Change to ReadKey}
if Code<>0 then writeln('Error')
until FALSE;
SortData;
WriteList;
FreeList;
end.
0

Commented:
To Hobbit123
Why do you propose an answer when lychee_ are just waiting for some respons for his comment? :-(
0

Commented:
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

Commented:
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

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;

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

Commented:
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

Author Commented:
Thanks to everyone who help
0

Featured Post

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