تمرينهاي ساختمان داده

[engeneer_19]

1- برنامه ايي بنويسيد كه صف را با استفاده از ليست پيوندي شبيه سازي كند؟

type
Addres=^Node;
Node=Record
Data:integer;
Next:Addres;
end;
var First:Addres;
{*******************}
procedure ADDQueue;
var D:integer; ptr:Addres;
begin
if First=NIL then
begin
new(First);
writeln('Enter a number');
Readln(First^.Data);
First^.Next:=Nil;
end
else
begin
new(Ptr);
writeln('Enter a number');
Readln(Ptr^.Data);
Ptr^.Next:=First;
First:=Ptr;
end;
end;
{********************}
function DeletefromQueue:integer;
var Ptr1,Ptr2:Addres;
begin
Ptr1:=First; Ptr2:=First;
if First=Nil then
begin
DeletefromQueue:=0;
Writeln('Qeue is Empty');
end
else
begin
while Ptr2^.Next <> NIL do
begin
Ptr1:=Ptr2;
Ptr2:=Ptr2^.Next;
end;
DeletefromQueue:=Ptr2^.Data;
Dispose(Ptr2);
Ptr1^.next:=Nil;
end;
end;
begin
First:=NIL;
AddQueue;
AddQueue;
AddQueue;
writeln(DeletefromQueue);
AddQueue;
writeln(DeletefromQueue);
writeln(DeletefromQueue);
writeln(DeletefromQueue);
end.

2-زيربرنامه ايي بنويسيد كه براي يك ليست پيوندي ساده تعداد گره هاي آن را چاپ كند؟

Procedure NumberOfNode;
Var Ptr:Addres; C:integer;
Begin
C:=0;
Ptr:=First;
While Ptr <> NIL Do
Begin
C:=C+1;
Ptr:=Ptr^.Next;
End;
Writeln( C);
End;
3-برنامه ايي بنويسيد كه عمليات مربوط به پشته(Pop , Push) را با يك ليست پيوندي انجام دهد؟


type
Addres=^Node;
Node=Record
Data:integer;
Next:Addres;
end;
var
First:Addres;
{*******************}
procedure Push;
var D:integer; ptr:Addres;
begin
if First=NIL then
begin
new(First);
writeln('Enter a number');
Readln(First^.Data);
First^.Next:=Nil;
end
else
begin
new(Ptr);
writeln('Enter a number');
Readln(Ptr^.Data);
Ptr^.Next:=First;
First:=Ptr;
end;
end;
{********************}
function Pop:integer;
var Ptr:Addres;
begin
Ptr:=First;
if First=Nil then
begin
Pop:=0;
Writeln('Stack is Empty');
end
else
begin
pop:=First^.Data;
First:=First^.Next;
Dispose(Ptr);
end;
end;

begin
First:=NIL;
Push;
Push;
Push;
writeln(Pop);
Writeln(Pop);
push;
Writeln(Pop);
writeln(Pop);
end.

begin
First:=NIL;
Push;
Push;
Push;
writeln(Pop);
Writeln(Pop);
push;
Writeln(Pop);
writeln(Pop);
end.


















































4-زيربرنامه ايي بنويسيد كه عمل اضافه كردن به ليست پيوندي ساده را در انتها انجام دهد؟

Procedure AddToEnd;
Var
Ptr :Addres;
Begin
Ptr:=First;
If First = NIL then
Begin
New(First);
Writeln(‘Enter a number ‘);
Readln(First^.Data);
First^.Next:=Nil;
End
Else
Begin
While Ptr^.Next<> NIL Do
Ptr:= Ptr^.Next;
New(Ptr^.Next);
Ptr:=Ptr^.Next;
Writeln(‘Enter a number ‘);
Readln(Ptr^.Data);
Ptr^.Next:=Nil;
End;
End;
5-زيربرنامه ايي بنويسيد كه يك گره با آدرس Ptr را در يك ليست پيوندي دو طرفه حذف كند.
اين برنامه با فرض اين نوشته شده است كه گره ايي كه قرار است حذف شود قبلا جستجو شده و آدرس آن را كه Ptr است را داريم.

Procedure Delete( Ptr : Address);
Var
Begin


If First = Ptr Then // گره ايي كه قرار است حذف شود گره اول است
Begin
First:=First^.Next;
First^.Last := Nil;
Dispose(Ptr);
End
Else
Begin
Ptr^. Last ^ . Next := Ptr ^ .Next;
Ptr^ . Next ^ .Last:=Ptr^ . Last;
Dispose(Ptr);
End;
End;
6-زير برنامه ايي بنويسيد كه با فرض اينكه يك ليست پيوندي ساده داريم همه گره هاي آن را حذف كند؟

‍Procedure DeleteAll;
Var Ptr:Addres;
Begin
While First <> NIL Do
Begin
Ptr:=First;
First:=First^.Next
Dispose(Ptr);
End;
End;
7-الگوريتمي را طراحي كنيد كه يك ليست پيوندي ساده را معكوس كند؟
با فرض اينكه يك پشته داريم كه مي توان عمليات Push و Pop و Isempty را دارد اين زيربرنامه را مي نويسيم.

Procedure INVERSE;
Var Ptr: Addres;
Begin
Ptr := First;
While Ptr <> NIL Do
Begin
Push(Ptr); // آدرس ها را داخل پشته مي ريزيم
Ptr:= Ptr ^ . Next;
End;
First := POP; // آخرين گره از پشته خارج شده و در ابتداي ليست قرار مي گيرد
Ptr := First;
While Not Isempty Do //تا زماني كه پشته خالي نشده است
Begin
Ptr^.Next:= POP;
Ptr:=Ptr ^. Next;
End;
Ptr ^. Next := NIL; // اشاره گر آخرين گره را تهي مي كنيم
End;
8-زيربرنامة بازگشتي بنويسيد كه يك ليست پيوندي ساده را به صورت معكوس چاپ كند؟
اين زيربرنامه در بلوك اصلي به صورت PRINTINVERSE(First); فراخواني مي شود.

Procedure PRINTINVERSE( PTR : Addres);
Begin
IF PTR^.Next = NIL THEN
Wrietln(PTR^. DATA)
Else
Begin
PRINTINVERSE(PTR^.Next);
Writeln(PTR^.DATA);
End;
End;