Pascal problems.

[EW128720]

Hello, I'm kind of new to Pascal, just Pascal not Turbo mind you, but I've been at it for about 3 months trying to learn it by myself, more as a foundation to programming. Though my problem lays with these practice problems I am getting from a book that I bought, any help is appreciated, I'm looking for more of an actual program for replies to this thread, in order so that I may see the structure of the program and how everything is laid out, thank you:

1) Create a linked list with 5-7 records. Your program will take an input value. It will then split the list into two: the first list will contain values from the start of the list until the input value and the second list will contain values after input value till the end of the list. If the input value is not in the list, the output will be just the original list.

Hence, if the original list is 1,2,3,4,5 and the input value is 3, the output will be:

List1: 1, 2, 3 and List2: 4, 5

If the input happens to be 5 the output will be:

List1: 1, 2, 3, 4, 5 and LIST2: (Empty List)

2) Consider and array with a sorted input. Write a program to remove all duplicate entries in the array, without disturbing the order.

 

[Glenn9999]

Have you considered searching for this? I know I've personally put several examples of this kind of stuff out that is all over the net, and I'm sure there's many other examples. In fact, I just googled it and found several adequate examples for your question.

 

[Glenn9999]

and you might consider posting your programs and your troubles you are having as opposed to saying "do my work for me". People are often wary of people posting their classwork assignments and hoping some gullible soul comes along to do it for them.

 

[EW128720]

Thanks Glenn, I understand that students try and post their problems up here hoping someone will come in and do the work for them, but I'm just doing this on my own and I don't know where to start on these problems, I was just hoping someone could show me the structure of an example program. Well, I dunno, I guess I'll look for help elsewhere then. Thanks!

 

[earthandfire]

Linked Lists are one of the more advanced features of Pascal.

If you are intending to learn the language you should really consider simpler exercises to start with.

If, on the other hand, you need help creating a linked list, please let us know and we can post an example of that particular structure for you.

Because of the "student" problem, there is often suspicion when someone says:

I'm looking for more of an actual program for replies to this thread

Hope this helps.

 

[EW128720]

Thanks earthandfire, yea I was looking for a way on how to create a linked list for this particular program, I got kind of bewildered on how to start this off. Thanks.

 

[earthandfire]

The structure of the three types of linked list are shown below

Single Linked List:

A Queue (FIFO):
Type
   PQueue = ^TQueue;
   TQueue = Record
      <Your data fields go here>
      NextItem: PQueue;
   End;
 
Var
   FirstItem, LastItem, CurrentItem: PQueue;


A Stack (LIFO):
Type
   PStack = ^TStack;
   TStack = Record
      <Your data fields go here>
      PreviousItem: PStack;
   End;
 
Var
   FirstItem, LastItem, CurrentItem: PStack;


A Double Linked List:
Type
  PDoubleList = ^TDoubleList;
  TDoubleList = Record
      <Your data fields go here>
      PreviousItem, NextItem: PDoubleList;
   End;

Var
   FirstItem, LastItem, CurrentItem: PDoubleList;

Hope this helps.

 

[lionelhill]

OK, here's a little go at linked lists. I am a turbo person, but I'd imagine most of this is not very turbo specific.

Yes, you can define your structures as earthandfire has done. But this is only the start of the story: you will need procedures to add new entries in your list, or do other things to the list as necessary.

I tend not to think about LIFO or FIFO, but just think about where my data will be, and how I intend to manipulate it. If you merely remember the begining of the list, and it's singly linked (i.e. it's got a simple one-way direction; you can search it forwards but there's no backward link, so searching backwards is hard), does it matter that some data are right at the end? If so, either reverse the list, or if that also makes problems, consider a different structure (possibly doubly-linked).

You need to mark the end of a linked list in some recogniseable way. A simple method is a dummy entry whose next-entry pointer points to nil. A good textbook will help you with more efficient methods, for instance sentinels.

To find the end of the list (non-sentinel version):

function ListEnd(ListStart : pointer) : pointer;
var
qptr : pointer;
begin
qptr := ListStart;
while ListEntryType(qptr^).nextEntry <> nil do
qptr := ListEntryType(qptr^).nextEntry;
ListEnd := qptr;
end;

(note that this assumes you haven't actually defined your variables as pointers to ListEntries. It uses any old pointer and type-casts. It's more typing, but I can never remember what my variables are when there are too many different types. A personal weakness).

To make a new list:

function NewList : pointer;
var
qptr : pointer;
begin
getmem(qptr, sizeof(ListEntryType);
ListEntryType(qptr^).nextEntry := nil;
NewList := qptr;
end;

To add something to the end of the list, just use listend as above to find the end, and then getmem a new entry into the final entry's NextEntry. Put the data here too (it was the dummy, so it contained no data). Finally fill in the new entry's nextentry to be nil, to make this new one the new dummy.

Note that you're procedure for adding a new entry is probably a procedure, not a function, and that it needs to enter the data as well as sort out the node and its links.

To add something to the beginning of the list, simply getmem a ListEntryType, and set its nextentry to point to ListStart. Then set ListStart to point to the thing you just made.

Try drawing diagrams to illustrate how these all work. It really helps (particularly when you start getting to circular lists, binary trees, doubly-linked lists, and lists-of-lists.

Just to return to sentinels, say you want to put a new entry into the middle of the list, so as to keep your data sorted. Now you have to check for two things on each loop: have I reached the end of the list, and have I reached the right place. The reason you need both is that if you're adding a bigger value than ever before, you will run off the end of the list without finding the "right" place.
A sentinel is a dummy node at the end of the list, which contains the largest possible number (bigger than any expected data). With a sentinel in place, you can merely check whether you've reached the "right" place, because there will never be a piece of data that could scan past the sentinel. Clever, eh?