[̲] [] [] [ ]

 

10.4.

 

, . ij, , , , ( ). , , , . . , , .

 

10.4.1

 

:

1.    .

2.    ; .

. .

 

1.    .

2.    ?

3.    .

4.    .

5.    .

 

ij 1, 3, 4, 5 ; 2 .

.

, .

. . .

. .

 

. 10.17. : . 璺 . nil. . , , nil.

 

. 10.17

 

. , 䳿 . Init, Empty, Head . Add (. 10.18) . , , Add , , , . Tail nil .

 

unit ListClassic;

 

interface

 

type list = ^lelem; {}

lelem = record { }

d: integer;

next: list

end;

 

function Init: list; { }

function Empty(l: list): boolean; { ?}

function Add(l: list; n: integer): list; { }

function Head(l: list): integer; { }

function Tail(l: list): list; { }

 

implementation

 

.................

 

function Add(l: list; n: integer): list;

var p: list;

begin

new(p); p^.d:=n; p^.next:=l;

Add:=p

end;

 

.................

 

function Tail(l: list): list;

begin

if l=nil then Tail:=nil

else Tail:=l^.next

end;

end.

 

. 10.18

 

, . , Tail dispose. . . . 10.19. , . ij,

 

l2:=Tail(l1); l2:=Add(l2,x); l2:=Add(l2,y)

 

l1 l2 ( ). , . l:=Add(l,x); l:=Tail(l), , l, . , , .

 

. 10.19

 

. CmpLists , l1 l2. 2 .

 

Program ListClassTst;

uses ListClassic;

 

function CmpLists(l1,l2: list): boolean;

var b: boolean;

begin

b:=true;

while not Empty(l1) and not Empty(l2) and b do

begin

b:=Head(l1)=Head(l2);

l1:=Tail(l1); l2:=Tail(l2)

end;

CmpLists:=b and Empty(l1) and Empty(l2)

end;

 

var l1,l2: list;

i,n,m,k: word;

begin

l1:=Init;

write('ʳ 1- : '); readln(n);

for i:=1 to n do begin

write('l1(',i,')'); readln(k);

l1:=Add(l1,k)

end;

l2:=Init;

write('ʳ 2- : '); readln(m);

for i:=1 to m do begin

write('l2(',i,')'); readln(k);

l2:=Add(l2,k)

end;

write(' ');

if not CmpLists(l1,l2) then write(' ');

writeln('')

end.

 

.

 

/* classlst.h */

 

typedef struct lelem *list; /* */

struct lelem { /* */

int d;

list next;

};

 

extern list init(); /* */

extern int empty(list l); /* ? */

extern list add(list l, int n); /* */

extern int head(list l); /* */

extern list tail(list l); /* */

 

10.4.2

 

, , . :

1.    .

2.    ; ; .

3.    .

 

:

1.    .

2.    ?

3.    .

4.    .

5.    .

6.    .

7.    .

 

ij 1, 3, 4, 6, 7 ; 2 ; 5 - .

.

³ ? , , .

.

. , .

. . , .

.

. . , .

 

. 10.20. : . 璺 . nil. : . , , nil. , , ( nil). , - .

 

. 10.20

 

ѳ. .

 

 

unit ListCurrent;

 

interface

 

type lref = ^lelem; { }

lelem = record { }

d: integer;

next: lref

end;

list = record {}

beg, cur: lref

end;

 

procedure Init(var l: list); { }

function EmpEnd(l: list): boolean; { ?}

procedure First(var l: list); { }

procedure Next(var l: list); { }

function Current(l: list): integer; { }

procedure Insert(var l: list; n: integer);{ }

procedure Delete(var l: list); { }

 

implementation

 

.................

 

end.

 

ѳ 2 : listcur.h listcur.c. init, emp_end, first, next, current .

 

/* listcur.h */

 

typedef struct lelem *lref; /* */

struct lelem { /* */

int d;

lref next;

};

typedef struct { /* */

lref beg, cur;

} list;

 

extern void init(list *pl); /* */

extern int emp_end(list l); /* ?*/

extern void first(list *pl); /* */

extern void next(list *pl); /* */

extern int current(list l); /* */

extern void insert(list *pl, int n);/* */

extern void delete(list *pl); /* */

 

 

/* listcur.c */

 

#include <stdio.h>

#include <stdlib.h>

#include "listcur.h"

 

lref find_prev(list l)

{

lref p;

 

if (l.beg == l.cur) p=NULL;

else

{

p = l.beg;

while (p -> next != l.cur)

p = p ->next;

}

return p;

}

 

.................

 

void insert(list *pl, int n)

{

lref p;

 

p = (lref) malloc(sizeof(struct lelem));

p -> d = n;

p -> next = pl -> cur;

/* . 10.21 ), ) */

if(pl -> beg == pl -> cur) pl -> beg = p; /* . 10.21 ) */

else find_prev(*pl) -> next = p; /* . 10.21 ) */

}

 

void delete(list *pl)

{

lref p;

 

if(pl -> cur == NULL)

{

printf("delete: \n");

exit(1);

}

p = pl -> cur;

if(pl -> beg == p) pl -> beg = pl -> cur -> next; /* . 10.22 ) */

else find_prev(*pl) -> next = pl -> cur -> next; /* . 10.22 ) */

pl -> cur = pl -> cur -> next;

free(p);

/* . 10.22 ), ) */

}

. 10.21. 2 : ( ) . 10.21 ), ), - 10.21 ), ). insert delete find_prev. (p1 . 10.21).

. 10.21

 

. 10.22. (pl -> cur == NULL), delete . , , 2 : ( ) . 10.22 ), ), - 10.22 ), ).

 

. 10.22

 

. cmp_list , l1 l2. input_list . 2 .

 

/* listcurt.c */

 

#include <stdio.h>

#include "listcur.h"

 

#define TRUE 1

 

int cmp_list(list l1, list l2)

{

int b;

 

first(&l1); first(&l2); b = TRUE;

while(!emp_end(l1) && !emp_end(l2) && b)

{

b = current(l1)==current(l2);

next(&l1); next(&l2);

}

return b && emp_end(l1) && emp_end(l2);

}

 

void input_list(list *pl)

{

unsigned n, i;

int k;

 

init(pl);

printf(" : ");

scanf("%u", &n);

for(i=1; i<=n; i++)

{

printf(" %u= ", i);

scanf("%d", &k);

insert(pl, k);

}

}

 

main()

{

list l1, l2;

 

printf("\n \n");

input_list(&l1);

printf("\n \n");

input_list(&l2);

printf(" ");

if (!cmp_list(l1,l2)) printf(" ");

printf("\n");

}

 

[̲] [] [] [ ]