[̲] [] [] [ ]

 

10.4.3 ʳ

 

ʳ , . . :

1.    .

2.    ; ; .

 

:

1.    .

2.    .

3.    .

4.    .

5.    .

6.    .

 

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

.

.

. , .

. . , .

.

. . , .

 

. 10.12. : . 璺 . . , , nil.

 

. 10.23

 

. ѳ . ϳ Init, Next, Current . Len p. , p r, .

 

unit IntRList;

 

interface

 

type

rlist = ^relem; {}

relem = record { }

d: integer;

next: rlist

end;

 

procedure Init(var r: rlist); { }

function Len(r: rlist): integer; { }

procedure Next(var r: rlist); { }

function Current(r: rlist): integer; { }

procedure Insert(var r: rlist; n: integer);{ }

procedure Delete(var r: rlist); { }

 

implementation

 

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

 

function Len;

var i: word;

p: rlist;

begin

i:=0; p:=r;

if p<>nil then

repeat

p:=p^.next;

i:=i+1

until p=r;

Len:=i

end;

 

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

 

procedure Insert;

var p: rlist;

begin

new(p);

if r=nil then

begin

p^.d:=n; p^.next:=p; {. 10.24 ), )}

end

else

begin

p^:=r^; r^.d:=n; r^.next:=p; {. 10.24 ), )}

end;

r:=p;

end;

 

procedure Delete;

var p: rlist;

begin

if r=nil then begin

writeln('Delete: ');

halt

end;

if r^.next=r then

begin

p:=r; r:=nil {. 10.25 ), )}

end

else

begin

p:=r^.next; r^:=p^ {. 10.25 ), )}

end;

dispose(p)

end;

 

end.

. 10.24. 2 : . 10.24 ), ), - 10.24 ), ). , . : , . ( , , ). ϳ , , (. 10.24 ) ). , . , , , (. 10.24 ) ). , .

 

. 10.24

 

. 10.25. (r=nil), Delete . , , 2 : 1 , , 1 . 10.25 ), ), - 10.25 ), ). 䳺 . , , , .

 

. 10.25

 

, . , . . ϳ PutToList, put_to_deque 10.3.2, . , , . WriteList , . .

 

Program TstRList;

uses IntRList;

 

procedure PutToList(var r: rlist; n: integer);

var l,i,j: word;

b: boolean;

begin

l:=Len(r);

i:=0; b:=false;

while (i<l) and not b do begin

b:=n<Current(r);

if not b then begin

Next(r);

i:=i+1;

end

end;

Insert(r,n);

for j:=i+1 to l do

Next(r);

end;

 

procedure WriteList(r: rlist);

var i: word;

begin

for i:=1 to Len(r) do begin

write(Current(r),' ');

Next(r)

end;

writeln;

end;

 

var r: rlist;

i: word;

n: integer;

 

begin

Init(r);

writeln(' 䔺 ');

readln(n);

while n>0 do begin

PutToList(r,n);

readln(n)

end;

writeln(' ');

WriteList(r)

end.

 

ѳ .

 

/* rlist.h */

 

typedef struct relem *rlist; /* */

struct relem { /* */

int d;

rlist next;

};

 

extern void init(rlist *pr); /* */

extern int len(rlist r); /* */

extern void next(rlist *pr); /* */

extern int current(rlist r); /* */

extern void insert(rlist *pr, int n);/* */

extern void delete(rlist *pr); /* */

 

10.4.4

 

. , , , . :

1.    .

2.    ; ; .

 

:

1.         .

2.         ?

3.         ?

4.         ?

5.         .

6.         .

7.         .

8.         .

9.         .

10.     .

11.     .

12.     .

 

ij 1, 5, 6, 7, 8, 10, 11, 12 ; 2, 3, 4 ; 9 - .

.

³ ? , .

³ ? , .

.

.

. , .

. , .

. . , .

. , .

. , .

. , . , . , . , .

 

. - , .

. 10.26. : . 璺 . nil. nil. : , . , , nil. , nil , .

 

. 10.26

 

ѳ. .

 

 

unit IntDList;

 

interface

 

type dlref = ^dlelem; { }

dlelem = record { }

d: integer;

next: dlref

end;

dlist = record {}

bg, cur, en: dlref

end;

 

procedure Init(var dl: dlist); { }

function Empty(dl: dlist): boolean; { ?}

function EmpBeg(dl: dlist): boolean; { ?}

function EmpEnd(dl: dlist): boolean; { ?}

procedure First(var dl: dlist); { }

procedure Last(var dl: dlist); { }

procedure Next(var dl: dlist); { }

procedure Previous(var dl: dlist); { }

function Current(dl: dlist): integer; { }

procedure InsBefore(var dl: dlist; n: integer);{ }

procedure InsAfter(var dl: dlist; n: integer);{ }

procedure Delete(var dl: dlist); { }

 

implementation

 

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

 

end.

 

ѳ 2 : dlist.h dlist.c. init, emp_beg, emp_end, first, last, next, previous, current, ins_after . , ins_after, . ins_after, ins_before ins_before next prev, prev next, bg en en bg. ins_before delete.

 

/* dlist.h */

 

typedef struct dlelem *dlref; /* */

struct dlelem { /* */

int d;

dlref next, prev;

};

typedef struct { /* */

dlref bg, cur, en;

} dlist;

 

extern void init(dlist *pdl); /* */

extern int empty(dlist dl); /* ?*/

extern int emp_beg(dlist dl); /* ?*/

extern int emp_end(dlist dl); /* ?*/

extern void first(dlist *pdl); /* */

extern void last(dlist *pdl); /* */

extern void next(dlist *pdl); /* */

extern void previous(dlist *pdl); /* */

extern int current(dlist dl); /* */

extern void ins_before(dlist *pdl, int n);/* */

extern void ins_after(dlist *pdl, int n); /* */

extern void delete(dlist *pdl); /* */

 

 

/* dlist.c*/

 

#include <stdio.h>

#include <stdlib.h>

#include "dlist.h"

 

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

 

void ins_before(dlist *pdl, int n)

{

dlref p;

 

p = (dlref) malloc(sizeof(struct dlelem));

p -> d = n;

p -> next = pdl -> cur;

/* . 10.27 ), ), ) */

if (pdl -> cur == NULL) /* */

{

p -> prev = NULL;

pdl -> bg = pdl -> en = pdl -> cur = p; /* . 10.27 ) */

}

else

{

if (pdl -> cur == pdl -> bg) /* */

{

p -> prev = NULL;

pdl -> bg = p;

}

else /* */

{

p -> prev = pdl -> cur -> prev;

pdl -> cur -> prev -> next = p;

}

pdl -> cur -> prev = p;

/* . 10.27 ), ) */

}

}

 

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

 

void delete(dlist *pdl)

{

dlref p;

 

if(pdl -> cur == NULL)

{

printf("delete: \n");

exit(1);

}

p = pdl -> cur;

if (pdl -> cur==pdl -> bg && pdl -> cur==pdl -> en) /* */

{

pdl -> bg = pdl -> cur = pdl -> en = NULL;

}

else if (pdl -> cur != pdl -> en) /* */

{

pdl -> cur = pdl -> cur -> next;

pdl -> cur -> prev = p -> prev;

if (p == pdl -> bg) pdl -> bg = pdl -> cur; /* */

else p -> prev -> next = pdl -> cur; /* */

}

else /* */

{

pdl -> cur = pdl -> cur -> prev;

pdl -> cur -> next = NULL;

pdl -> en = pdl -> cur;

}

free(p);

}

 

. 10.27. 3 : , . 10.27 ), ), - 10.27 ), ), - 10.27 ), ).

. 10.27

 

. 10.28. (pdl -> cur == NULL), delete . 4 : 1 , , . 10.28 ), ), - 10.28 ), ) ), - 10.28 ), ), - 10.28 ), ).

 

. 10.28

 

. is_symm , dl. 2 , dl2, dl. , 䳿 dl2 is_symm . input_list . .

 

/* dlisttst.c */

 

#include <stdio.h>

#include "dlist.h"

 

#define TRUE 1

 

 

int is_symm(dlist dl)

{

int b;

dlist dl2;

 

b = TRUE;

if (!empty(dl))

{

dl2 = dl;

first(&dl); last(&dl2);

while(1)

{

b = current(dl)==current(dl2);

if (!b || emp_end(dl)) break;

next(&dl); previous(&dl2);

}

}

return b;

}

 

void input_list(dlist *pdl)

{

unsigned n, i;

int k;

 

init(pdl);

printf(" : ");

scanf("%u", &n);

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

{

printf(" %u= ", i);

scanf("%d", &k);

ins_after(pdl, k);

next(pdl);

}

}

 

main()

{

dlist dl;

 

printf("\n \n");

input_list(&dl);

printf(" ");

if (!is_symm(dl)) printf(" ");

printf("\n");

}

 

[̲] [] [] [ ]