[̲] [] [] [ ]

 

10.3.

10.3.1.

 

, :

1.    .

2.    ; .

, , (. 10.9).

 

. 10.9

 

, :

1.    .

2.    ?

3.    .

4.    .

 

ij 1, 3, 4 ; 2 .

.

, .

. . .

 

. 10.10. : . 璺 . nil. , : . , . , , nil.

 

. 10.10

 

, IntQueue. qref ; qelem ; queue ; bg , en .

 

unit IntQueue;

 

interface

 

type qref = ^qelem; { }

qelem = record { }

d: integer;

next: qref

end;

queue = record { }

bg, en: qref

end;

 

procedure Init(var q: queue); { }

function Empty (q: queue): boolean; { ?}

procedure Add (var q: queue; n: integer); { }

procedure Take (var q: queue; var n: integer); { }

 

implementation

 

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

 

procedure Add (var q: queue; n: integer);

var p: qref;

begin

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

if q.bg=nil then q.bg := p

else q.en^.next:=p;

q.en := p

end;

 

procedure Take (var q: queue; var n: integer);

var p: qref;

begin

if q.bg = nil then begin

writeln(' Take: '); halt

end;

p:=q.bg; n:=q.bg^.d;

q.bg:=q.bg^.next;

if q.bg=nil then q.en:=nil;

dispose(p)

end;

 

end.

 

ϳ Init Empty . . .

䳿 ( Add) . 10.11. , (. 10.11 )-) ) (. 10.11 )-) ). ϳ new(p) (. 10.11 ), ) ) . p^.d:=n; p^.next:=nil (. 10.11 ), ) ) n nil . (q.bg=nil), (q.bg:=p), , q.en, (q.en^.next:=p). , (q.en:=p). 䳿 . 10.11 ), ).

 

. 10.11

 

䳿 ( Take) . 10.12. , , . , : , (. 10.12 )-) ), (. 10.12 )-) ). ϳ p:=q.bg; n:=q.bg^.d (. 10.12 ), ) ) . q.bg:=q.bg^.next q.bg (. 10.12 ) ), nil (. 10.12 ) ). q.bg=nil, 1 , q.en:=nil, . , , (dispose(p)). 䳿 . 10.12 ), ).

 

. 10.12

 

q1 q2, 䳿 . (q1:=q2) , q1 q2 . q2, q1. ³ QueueTst . SetQueue. q1 q2 - , q2 . , , . q2 q3. ϳ q2 , . , . ShowQueue , . , , q2 q1, q2.

 

Program QueueTst;

 

uses IntQueue;

 

{q1:=q2}

procedure SetQueue(var q1, q2: queue);

 

var q3: queue;

n: integer;

 

begin

Init(q3);

while not Empty(q2) do begin

Take(q2,n);

Add(q1,n); Add(q3,n);

end;

while not Empty(q3) do begin

Take(q3,n);

Add(q2,n);

end;

end;

 

{ }

procedure ShowQueue(var q: queue);

 

var n: integer;

 

begin

while not Empty(q) do begin

Take(q,n);

write(n,' ')

end;

writeln

end;

 

var q1,q2: queue;

n: integer;

i,m: word;

 

begin

Init(q2);

writeln('ʳ ');

readln(m);

for i:=1 to m do begin

write(' ',i,' = ');

readln(n);

Add(q2,n)

end;

SetQueue(q1,q2);

write('q2 = ');

ShowQueue(q2);

write('q1 = ');

ShowQueue(q1);

end.

 

, ѳ queue.h.

 

/* queue.h */

typedef struct qelem *qref; /* */

struct qelem { /* */

int d;

qref next;

};

typedef struct { /* */

qref bg, en;

} queue;

 

extern void init(queue *pq); /* */

extern int empty(queue q); /* ? */

extern void add(queue *pq, int n); /* */

extern void take(queue *pq, int *pn); /* */

 

10.3.2.

 

. :

1.    .

2.    ; .

3.    ; .

, , (. 10.9).

 

. 10.13

 

, :

1.    .

2.    ?

3.    .

4.    .

5.    .

6.    .

 

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

.

, .

. . .

, .

. . .

 

. 10.14. : . 璺 . nil, nil. , : . , , nil.

 

. 10.14

 

ѳ, .

 

unit IntDeque;

 

interface

 

type dref = ^delem; { }

delem = record { }

d: integer;

next, prev: dref

end;

deque = record {}

bg, en: dref

end;

 

procedure Init(var d: deque); { }

function Empty (d: deque): boolean; { ?}

procedure PutBg (var d: deque; n: integer); { }

procedure GetBg (var d: deque; var n: integer); { }

procedure PutEn (var d: deque; n: integer); { }

procedure GetEn (var d: deque; var n: integer); { }

 

implementation

 

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

 

end.

 

ѳ deque.h deque.c. init, empty, put_en, get_en . init empty . put_en get_en, .

 

/* deque.h */

 

typedef struct delem *dref; /* */

struct delem { /* */

int d;

dref next, prev;

};

typedef struct { /* */

dref bg, en;

} deque;

 

extern void init(deque *pd); /* */

extern int empty(deque d); /* ? */

extern void put_bg(deque *pd, int n); /* */

extern void get_bg(deque *pd, int *pn); /* */

extern void put_en(deque *pd, int n); /* */

extern void get_en(deque *pd, int *pn); /* */

 

 

/* deque.c*/

 

#include <stdio.h>

#include <stdlib.h>

#include "deque.h"

 

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

 

void put_bg(deque *pd, int n)

{

dref p;

 

p = (dref) malloc(sizeof(struct delem));

p -> d = n;

p -> prev = NULL;

p -> next = pd -> bg;

if (pd -> bg == NULL) pd -> en = p;

else pd -> bg -> prev = p;

pd -> bg = p;

}

 

 

void get_bg(deque *pd, int *pn)

{

dref p;

 

if (pd -> bg ==NULL)

{

printf("get_bg: i\n");

exit(1);

}

p = pd -> bg;

*pn = p -> d;

pd -> bg = pd -> bg -> next;

if (pd -> bg == NULL) pd -> en = NULL;

else pd -> bg -> prev = NULL;

free(p);

}

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

 

䳿 ( put_bg) . 10.15. , , (. 10.15 )-) ) (. 10.15 )-) ). p = (dref) malloc(sizeof(struct delem)); p -> d = n; p -> prev = NULL; p -> next = pd -> bg; (. 10.15 ), ) ) , n , NULL ( NULL) . (pd -> bg == NULL), (pd -> en = p;), , pd -> bg, (pd -> bg -> prev = p;). , (pd -> bg = p;). 䳿 . 10.15 ), ).

 

. 10.15

 

䳿 ( get_bg) . 10.16. , , . , : , (. 10.16 )-) ), (. 10.16 )-) ). ϳ p = pd -> bg; *pn = p -> d; pd -> bg = pd -> bg -> next; (. 10.16 ), ) ) , , pd -> bg NULL. pd -> bg == NULL, 1 , (pd -> en) NULL;, . , 1 , (pd -> bg -> prev) NULL. , , (free(p)). 䳿 . 10.16 ), ).

, put_en get_en. put_bg get_bg next prev, prev next, bg en en bg.

. 10.16

 

. . . . , , . ϳ , . put_to_deque. pd n k.

 

/* dqtst.c */

 

#include <stdio.h>

#include "deque.h"

 

#define FALSE 0

 

put_to_deque(deque *pd, unsigned k, int n)

{

unsigned j, i=0;

int m, b=FALSE;

 

while (i<k && !b)

{

i++;

get_bg(pd,&m);

b = m >= n;

if (!b) put_en(pd,m);

else

{

put_bg(pd,m); i--;

}

}

put_bg(pd,n);

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

{

get_en(pd,&m);

put_bg(pd,m);

}

}

 

main()

{

deque d;

int n;

unsigned k=0;

 

init(&d);

printf"i ii i <=0\n");

while(1)

{

scanf("%d",&n);

if (n<=0) break;

put_to_deque(&d,k,n);

k++;

}

printf" ii\n");

while(!empty(d))

{

get_bg(&d,&n);

printf("%d\n",n);

}

}

 

[̲] [] [] [ ]