Please disregard "pascal problems" post.

[EW128720]

Ok, this time I've actually tired to do this problem before asking for assistence, but anyway the problem is to create a linked list with 5-7 records. Your program will take an input input value. It will then search for a record, which has the same value as the input value. If the search is successful, it will insert the matching record at the fron of the list. If not, it will output the original list. So far I have this:


program searchrecord;
type
ptr = ^node;
node = record
number: integer;
next: ptr;
end;
var betw, last, extra, head, prev, curr, point, next: ptr;
i, data, moveDistance: integer;
done: boolean;
x: integer;

begin
{----- start of list creation--------}
head := nil;
prev := nil;
for i := 1 to 5 do
begin
if head = nil then
begin
new (head);
writeln('Enter #');
readln(head^.number);
last := head;
end
else
begin
new (extra);
writeln('Enter #');
readln(extra^.number);
last^.next := extra;
last := extra;
end;
end;
last^.next := nil;
{-----------end of list creation-------------}
{----------start of list search--------------}
curr := head;
prev := nil;
writeln('Enter data to be moved');
readln(data);
done := false;
while(done = false) and (curr <> nil) do
begin
if data <> curr^.number then
begin
prev := curr;
curr:= curr^.next;
end
else done:= true;
end;
{----------------end of list search--------------}
{-------start of list print--------------}

point:= head;
while (point <> nil) do
begin
writeln(point^.number);
point := point^.next;
end;
{-------end of list print----------------}
end.

Now what I trying to do is put data in for those records, and trying to search for the input value and move that matching record to the front of the list. Thanks.

 

[earthandfire]

Because you need to manage both previous and next positions, a double linked list would be easier to work with.

I've made some minor changes to you list structure and assignment code to point you in the right direction. I've changed as little as possible because in principle your code does most of what you require.

type
  ptr = ^node;
  node = record
  number: integer;
  [b]previous,[/b] next: ptr;
end;

if head = nil then
begin
  new (head);
  writeln('Enter #');
  readln(head^.number);
  [b]head^.Previous :=nil;
  head^.Next := nil;[/b]
  last := head
end

else
begin
  new (extra);
  writeln('Enter #');
  readln(extra^.number);
  [b]extra^.Previous := last;[/b]
  last^.next := extra;
  last := extra
end;

Hope this helps.

 

[Glenn9999]

a doubly-linked list is not necessary for this project or for any linked-list project that EW128720 has posted so far. A doubly-linked list is only necessary if it is a requirement to navigate backwards, which it is NOT the case here (I should know, I went ahead and wrote up this one in TP 7.0 since I haven't done linked-list stuff in a while, and wanted the practice).

The main thing, I think for the OP, is that they're trying to get your mind around this stuff. Plan before you code. It would be great if you used procedures in this program, as well, since it would make it a lot easier on you, too.

OK, first question is can you do the procedures well? Next step after that, can you create the list, write it out, and then dispose of it after you are done (which I notice you make no attempt to do)? What kind of examples do you have in your book? Have you simply just typed them out and gone from there?

Walk before you run. Get the easy stuff down before you try harder things. Just try creating the list, writing it, and disposing of it, before you worry about searching and moving nodes around.

Of course if you don't know what procedures are (and I don't know that for sure), I would definitely say you have no business attempting linked-list programs.

 

[earthandfire]

Glenn9999, I agree a doubly linked list is not necessary for EW128720's requirements - I just think it would be easier.

I've put together a sample for both splitting the list at a given point and for moving a selected value to the head of the list. Both, in my opinion, were simplified by using a doubly linked list. I think in a situation like this, though, personal preference for one structure over another probably goes a long way.

{This extract moves the selected node to the head of the list}
  if CurrRec <> nil then
  begin
    [b]CurrRec^.PPrevious^.PNext := CurrRec^.PNext;[/b]
    CurrRec^.PNext := Head1;
    Head1 := CurrRec
  end

{This extract splits the list into two at a given point}
  if CurrRec <> nil then
  begin
    Tail2 := Tail1;
    [b]Tail1 := CurrRec^.PPrevious;[/b]
    Tail1.PNext := nil;
    Head2 := CurrRec
  end

 

[lionelhill]

Earthandfire, I think you might be mistaken in your first code snippet.

(1) If you wish to remove the current node "G" from its current position and put it at the start of the list you have to change, assuming you use a doubly-linked list:

A------F-G-H------Z

F.next to point to H
H.previous to point to F
G.previous to point to nil (dummy end of list)
G.next to point to A
A.previous to point to G

This is 5 changes to the list; you've only made 3 in your first code snippet. The work is exactly the same if you want to put G at the end of the list. You must maintain all links in all directions, and the dummy nil at both ends of the list; otherwise you can't handle it working in both directions, which is the point of a doubly linked list.

(2) But Beware! Think what happens if you move a record that already IS at the end of the list... it can all get very messy. With the doubly linked scenario you need two end records that can't get moved, dummies or sentinels.

(3) Doubly linked lists are beautiful things, but they're lots of work compared to singly. In this case you only need to search the list forwards to find a particular entry. There is no reason to search the list backwards. You only need to find the start of the list having found the middle, and searching backwards from the middle is not a very efficient way to get back to the start!

 

[earthandfire]

Well spotted lionhill. I actaully wrote the program at 5 am (thats my excuse for any errors), and it worked perfectly based on the very specific requirements - so I posted it.

Adding / deleting and / or subsequent moving would have caused a problem due to those two missing lines.

However, as I said before, personal preference carries a lot of weight.

I've not used Pascal / Delphi since early 2002 - I've been required to use VB, VB.NET & VBA, so pointer management has been non-existent. I need to produce a couple of Win32 dlls, so I've reinstalled Delphi.

Pascal has always been my language of choice - unfortunately "beggars can't be choosers", so I've had to use MS languages almost exclusively for the last few years. But when using Pascal regularly in the past, I tended towards doubly linked lists and variant type records where ever I could justify their use - my favourite structures.

My rustiness showed though

 

[earthandfire]

lionhill - sorry - should have been lionelhill

 

[lionelhill]

Earthandfire, No worries, I'm a mere technical user, and completely lost in VB-world. I used to do some scientific programming in good-ol' Turbo Pascal, and still have a very soft spot for it (given half a chance I still use it, but hardly feel professional doing so). My major dislike in Pascal is arrays having to be a predefined size. And as for pointer handling, I'd hate to be without it, but it's responsible for a good 50% of my crashes (the rest are loops where I forgot to make sure they actually stop somewhere).

EW128720, if you've read this far, at least you've had a discussion of the pros and cons of two different sorts of lists, and I agree with earthandfire that doubly linked lists are very useful in many circumstances where you need to be able to scan a list either way. Little drawings showing the links are really handy...

 

[earthandfire]