s14.ps

来自「c programming pearls answer」· PS 代码 · 共 1,353 行 · 第 1/2 页

%!PS-Adobe-2.0
%%Copyright: Copyright (c) 1993 AT&T, All Rights Reserved
%%Version: 3.4
%%DocumentFonts: (atend)
%%Pages: (atend)
%%BoundingBox: (atend)
%%EndComments
/DpostDict 200 dict def
DpostDict begin
%
% Copyright (c) 1993 AT&T, All Rights Reserved
%
% Version 3.4 prologue for troff files.
%

/#copies 1 store
/Prologue (dpost.ps) def
/aspectratio 1 def
/formsperpage 1 def
/landscape false def
/linewidth .3 def
/magnification 1 def
/margin 0 def
/orientation 0 def
/resolution 720 def
/rotation 1 def
/xoffset 0 def
/yoffset 0 def

/roundpage true def
/useclippath true def
/pagebbox [0 0 612 792] def

/R  /Times-Roman def
/I  /Times-Italic def
/B  /Times-Bold def
/BI /Times-BoldItalic def
/H  /Helvetica def
/HI /Helvetica-Oblique def
/HB /Helvetica-Bold def
/HX /Helvetica-BoldOblique def
/CW /Courier def
/CO /Courier def
/CI /Courier-Oblique def
/CB /Courier-Bold def
/CX /Courier-BoldOblique def
/PA /Palatino-Roman def
/PI /Palatino-Italic def
/PB /Palatino-Bold def
/PX /Palatino-BoldItalic def
/Hr /Helvetica-Narrow def
/Hi /Helvetica-Narrow-Oblique def
/Hb /Helvetica-Narrow-Bold def
/Hx /Helvetica-Narrow-BoldOblique def
/KR /Bookman-Light def
/KI /Bookman-LightItalic def
/KB /Bookman-Demi def
/KX /Bookman-DemiItalic def
/AR /AvantGarde-Book def
/AI /AvantGarde-BookOblique def
/AB /AvantGarde-Demi def
/AX /AvantGarde-DemiOblique def
/NR /NewCenturySchlbk-Roman def
/NI /NewCenturySchlbk-Italic def
/NB /NewCenturySchlbk-Bold def
/NX /NewCenturySchlbk-BoldItalic def
/ZD /ZapfDingbats def
/ZI /ZapfChancery-MediumItalic def
/S  /S def
/S1 /S1 def
/GR /Symbol def

/inch {72 mul} bind def
/min {2 copy gt {exch} if pop} bind def

/setup {
	counttomark 2 idiv {def} repeat pop

	landscape {/orientation 90 orientation add def} if
	/scaling 72 resolution div def
	linewidth setlinewidth
	1 setlinecap

	pagedimensions
	xcenter ycenter translate
	orientation rotation mul rotate
	width 2 div neg height 2 div translate
	xoffset inch yoffset inch neg translate
	margin 2 div dup neg translate
	magnification dup aspectratio mul scale
	scaling scaling scale

	addmetrics
	0 0 moveto
} def

/pagedimensions {
	useclippath userdict /gotpagebbox known not and {
		/pagebbox [clippath pathbbox newpath] def
		roundpage currentdict /roundpagebbox known and {roundpagebbox} if
	} if
	pagebbox aload pop
	4 -1 roll exch 4 1 roll 4 copy
	landscape {4 2 roll} if
	sub /width exch def
	sub /height exch def
	add 2 div /xcenter exch def
	add 2 div /ycenter exch def
	userdict /gotpagebbox true put
} def

/landscapepage {
	landscape not {
		0 height scaling div neg translate	% not quite
		90 rotate
	} if
} bind def

/portraitpage {
	landscape {
		width scaling div 0 translate	% not quite
		-90 rotate
	} if
} bind def

/addmetrics {
	/Symbol /S null Sdefs cf
	/Times-Roman /S1 StandardEncoding dup length array copy S1defs cf
} def

/pagesetup {
	/page exch def
	currentdict /pagedict known currentdict page known and {
		page load pagedict exch get cvx exec
	} if
} def

/decodingdefs [
	{counttomark 2 idiv {y moveto show} repeat}
	{neg /y exch def counttomark 2 idiv {y moveto show} repeat}
	{neg moveto {2 index stringwidth pop sub exch div 0 32 4 -1 roll widthshow} repeat}
	{neg moveto {spacewidth sub 0.0 32 4 -1 roll widthshow} repeat}
	{counttomark 2 idiv {y moveto show} repeat}
	{neg setfunnytext}
] def

/setdecoding {/t decodingdefs 3 -1 roll get bind def} bind def

/w {neg moveto show} bind def
/m {neg dup /y exch def moveto} bind def
/done {/lastpage where {pop lastpage} if} def

/f {
	dup /font exch def findfont exch
	dup /ptsize exch def scaling div dup /size exch def scalefont setfont
	linewidth ptsize mul scaling 10 mul div setlinewidth
	/spacewidth ( ) stringwidth pop def
} bind def

/changefont {
	/fontheight exch def
	/fontslant exch def
	currentfont [
		1 0
		fontheight ptsize div fontslant sin mul fontslant cos div
		fontheight ptsize div
		0 0
	] makefont setfont
} bind def

/sf {f} bind def

/cf {
	dup length 2 idiv
	/entries exch def
	/chtab exch def
	/newencoding exch def
	/newfont exch def

	findfont dup length 1 add dict
	/newdict exch def
	{1 index /FID ne {newdict 3 1 roll put}{pop pop} ifelse} forall

	newencoding type /arraytype eq {newdict /Encoding newencoding put} if

	newdict /Metrics entries dict put
	newdict /Metrics get
	begin
		chtab aload pop
		1 1 entries {pop def} for
		newfont newdict definefont pop
	end
} bind def

%
% A few arrays used to adjust reference points and character widths in some
% of the printer resident fonts. If square roots are too high try changing
% the lines describing /radical and /radicalex to,
%
%	/radical	[0 -75 550 0]
%	/radicalex	[-50 -75 500 0]
%
% Move braceleftbt a bit - default PostScript character is off a bit.
%

/Sdefs [
	/bracketlefttp		[201 500]
	/bracketleftbt		[201 500]
	/bracketrighttp		[-81 380]
	/bracketrightbt		[-83 380]
	/braceleftbt		[203 490]
	/bracketrightex		[220 -125 500 0]
	/radical		[0 0 550 0]
	/radicalex		[-50 0 500 0]
	/parenleftex		[-20 -170 0 0]
	/integral		[100 -50 500 0]
	/infinity		[10 -75 730 0]
] def

/S1defs [
	/underscore		[0 80 500 0]
	/endash			[7 90 650 0]
] def
end
%%EndProlog
%%BeginSetup
DpostDict begin
mark
/rotation 1 def
/gotpagebbox true def
/linewidth 0.5 def
/xoffset 0 def
/yoffset 0 def
/#copies 1 store
/magnification 1 def
%%FormsPerPage: 1
/formsperpage 1 def
%%Patch from lp
%%EndPatch from lp
/landscape false def
/resolution 720 def
setup
2 setdecoding
%
% Copyright (c) 1993 AT&T, All Rights Reserved
%
% Version 3.4 drawing procedures for dpost. Automatically pulled in when
% needed.
%

/inpath false def
/savematrix matrix def

/Dl {
	inpath
		{pop pop neg lineto}
		{newpath neg moveto neg lineto stroke}
	ifelse
} bind def

/De {
	/y1 exch 2 div def
	/x1 exch 2 div def
	/savematrix savematrix currentmatrix def
	neg exch x1 add exch translate
	x1 y1 scale
	0 0 1 0 360
	inpath
		{1 0 moveto arc savematrix setmatrix}
		{newpath arc savematrix setmatrix stroke}
	ifelse
} bind def

/Da {
	/dy2 exch def
	/dx2 exch def
	/dy1 exch def
	/dx1 exch def
	dy1 add neg exch dx1 add exch
	dx1 dx1 mul dy1 dy1 mul add sqrt
	dy1 dx1 neg atan
	dy2 neg dx2 atan
	inpath
		{arc}
		{newpath arc stroke}
	ifelse
} bind def

/DA {
	/dy2 exch def
	/dx2 exch def
	/dy1 exch def
	/dx1 exch def
	dy1 add neg exch dx1 add exch
	dx1 dx1 mul dy1 dy1 mul add sqrt
	dy1 dx1 neg atan
	dy2 neg dx2 atan
	inpath
		{arcn}
		{newpath arcn stroke}
	ifelse
} bind def

/Ds {
	/y2 exch def
	/x2 exch def
	/y1 exch def
	/x1 exch def
	/y0 exch def
	/x0 exch def
	x0 5 x1 mul add 6 div
	y0 5 y1 mul add -6 div
	x2 5 x1 mul add 6 div
	y2 5 y1 mul add -6 div
	x1 x2 add 2 div
	y1 y2 add -2 div
	inpath
		{curveto}
		{newpath x0 x1 add 2 div y0 y1 add -2 div moveto curveto stroke}
	ifelse
} bind def
end
%%EndSetup
%%Page: 1 1
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
1 pagesetup
20 H f
(Heaps)2590 960 w
(The Data Structure)2 1696 1 720 1548 t
(Two Critical Functions)2 1970 1 720 1788 t
(Priority Queues)1 1382 1 720 2028 t
(A Sorting Algorithm)2 1728 1 720 2268 t
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-14-1)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 1 1
%%Page: 2 2
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
2 pagesetup
20 H f
(The Data Structure)2 1696 1 2212 960 t
(A Heap of Twelve Integers)4 2366 1 720 1488 t
16 H f
(12)3089 1984 w
(20)2138 2272 w
3102 2064 2228 2100 Dl
(15)4039 2272 w
3255 2064 4129 2100 Dl
(29)1663 2560 w
2152 2352 1753 2388 Dl
(23)2614 2560 w
2305 2352 2704 2388 Dl
(17)3564 2560 w
4053 2352 3654 2388 Dl
(22)4514 2560 w
4205 2352 4604 2388 Dl
(35)1426 2848 w
1678 2640 1516 2676 Dl
(40)1901 2848 w
1829 2640 1991 2676 Dl
(26)2376 2848 w
2628 2640 2466 2676 Dl
(51)2851 2848 w
2779 2640 2941 2676 Dl
(19)3326 2848 w
3578 2640 3416 2676 Dl
20 H f
(Two Properties of a Heap)4 2276 1 720 3492 t
20 HI f
(Order:)1008 3900 w
20 H f
(The value at any node is less than or)8 3284 1 1632 3900 t
( \(Thus)1 624(equal to the values of the node's children.)7 3710 2 1008 4140 t
(the least element of the set is at the root\).)9 3698 1 1008 4380 t
20 HI f
(Shape:)1008 4788 w
3368 5729 2340 5729 Dl
3368 5647 3368 5729 Dl
3779 5646 3368 5646 Dl
3060 5112 3780 5646 Dl
2340 5729 3060 5112 Dl
20 H f
(Warning)720 6293 w
(These heaps all use 1-based arrays)5 3192 1 1008 6701 t
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-14-2)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 2 2
%%Page: 3 3
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
3 pagesetup
20 H f
(Implementation of Trees with Shape)4 3214 1 1597 960 t
(A 12-Element Example)2 2052 1 720 1488 t
16 HI f
(x)3030 1948 w
16 H f
([ 1 ])2 206 1 3123 1948 t
16 HI f
(x)2079 2164 w
16 H f
([ 2 ])2 206 1 2172 2164 t
3135 1992 2228 2028 Dl
16 HI f
(x)3980 2164 w
16 H f
([ 3 ])2 206 1 4073 2164 t
3222 1992 4129 2028 Dl
16 HI f
(x)1604 2380 w
16 H f
([ 4 ])2 206 1 1697 2380 t
2185 2208 1753 2244 Dl
16 HI f
(x)2555 2380 w
16 H f
([ 5 ])2 206 1 2648 2380 t
2272 2208 2704 2244 Dl
16 HI f
(x)3505 2380 w
16 H f
([ 6 ])2 206 1 3598 2380 t
4086 2208 3654 2244 Dl
16 HI f
(x)4455 2380 w
16 H f
([ 7 ])2 206 1 4548 2380 t
4172 2208 4604 2244 Dl
16 HI f
(x)1367 2596 w
16 H f
([ 8 ])2 206 1 1460 2596 t
1710 2424 1516 2460 Dl
16 HI f
(x)1842 2596 w
16 H f
([ 9 ])2 206 1 1935 2596 t
1797 2424 1991 2460 Dl
16 HI f
(x)2272 2596 w
16 H f
([ 10 ])2 296 1 2365 2596 t
2660 2424 2466 2460 Dl
16 HI f
(x)2747 2596 w
16 H f
([ 11 ])2 296 1 2840 2596 t
2747 2424 2941 2460 Dl
16 HI f
(x)3222 2596 w
16 H f
([ 12 ])2 296 1 3315 2596 t
3610 2424 3416 2460 Dl
20 H f
(Definitions in a Program)3 2140 1 720 3204 t
20 CW f
(root = 1)2 960 1 1296 3499 t
(value\(i\) = x[i])2 1800 1 1296 3734 t
(leftchild\(i\) = 2*i)2 2160 1 1296 3969 t
(rightchild\(i\) = 2*i+1)2 2520 1 1296 4204 t
(parent\(i\) = i / 2)4 2040 1 1296 4439 t
(null\(i\) = \(i < 1\) or \(i > n\))8 3360 1 1296 4674 t
20 H f
(A Tree and Its Array)4 1796 1 720 5142 t
16 H f
(12)2970 5584 w
(20)2250 5764 w
3016 5610 2340 5646 Dl
(15)3690 5764 w
3104 5610 3780 5646 Dl
(29)1890 5944 w
2296 5790 1980 5826 Dl
(23)2610 5944 w
2384 5790 2700 5826 Dl
(17)3330 5944 w
3736 5790 3420 5826 Dl
(22)4050 5944 w
3824 5790 4140 5826 Dl
(35)1710 6124 w
1936 5970 1800 6006 Dl
(40)2070 6124 w
2024 5970 2160 6006 Dl
(26)2430 6124 w
2656 5970 2520 6006 Dl
(51)2790 6124 w
2744 5970 2880 6006 Dl
(19)3150 6124 w
3376 5970 3240 6006 Dl
(12)1386 6614 w
1332 6654 1332 6510 Dl
(1)1431 6806 w
1620 6654 1332 6654 Dl
(20)1674 6614 w
1908 6654 1620 6654 Dl
(15)1962 6614 w
2196 6654 1908 6654 Dl
(29)2250 6614 w
2484 6654 2196 6654 Dl
(23)2538 6614 w
2772 6654 2484 6654 Dl
(17)2826 6614 w
3060 6654 2772 6654 Dl
(22)3114 6614 w
3348 6654 3060 6654 Dl
(35)3402 6614 w
3636 6654 3348 6654 Dl
(40)3690 6614 w
3924 6654 3636 6654 Dl
(26)3978 6614 w
4212 6654 3924 6654 Dl
(51)4266 6614 w
4500 6654 4212 6654 Dl
(19)4554 6614 w
4788 6654 4500 6654 Dl
4788 6510 4788 6654 Dl
(12)4554 6806 w
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-14-3)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 3 3
%%Page: 4 4
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
4 pagesetup
20 H f
(The siftup Function)2 1708 1 2206 960 t
(The Goal)1 826 1 720 1488 t
20 HI f
(x)1008 1896 w
20 H f
([ 1)1 184 1 1124 1896 t
20 HI f
(.)1324 1896 w
20 H f
(.)1380 1896 w
20 HI f
(n)1452 1896 w
20 S f
(-)1613 1896 w
20 H f
( is a heap; put a new element in)8 2838(1 ])1 184 2 1756 1896 t
20 HI f
(x)4834 1896 w
20 H f
([)4950 1896 w
20 HI f
(n)5022 1896 w
20 H f
(].)5150 1896 w
(Sift the new element up the tree.)6 2894 1 1008 2136 t
(Inserting 13)1 1050 1 720 2544 t
16 H f
(12)1450 2979 w
(20)1018 3231 w
1501 2998 1108 3120 Dl
(15)1882 3231 w
1579 2998 1972 3120 Dl
(29)802 3483 w
1069 3250 892 3372 Dl
(23)1234 3483 w
1147 3250 1324 3372 Dl
(17)1666 3483 w
1933 3250 1756 3372 Dl
(22)2098 3483 w
2011 3250 2188 3372 Dl
(35)694 3735 w
853 3502 784 3624 Dl
(40)910 3735 w
931 3502 1000 3624 Dl
(26)1126 3735 w
1285 3502 1216 3624 Dl
(51)1342 3735 w
1363 3502 1432 3624 Dl
(19)1558 3735 w
1717 3502 1648 3624 Dl
(13)1774 3735 w
1795 3502 1864 3624 Dl
1791 3697 146 146 De
(12)3178 2979 w
(20)2746 3231 w
3229 2998 2836 3120 Dl
(15)3610 3231 w
3307 2998 3700 3120 Dl
(29)2530 3483 w
2797 3250 2620 3372 Dl
(23)2962 3483 w
2875 3250 3052 3372 Dl
(13)3394 3483 w
3661 3250 3484 3372 Dl
(22)3826 3483 w
3739 3250 3916 3372 Dl
(35)2422 3735 w
2581 3502 2512 3624 Dl
(40)2638 3735 w
2659 3502 2728 3624 Dl
(26)2854 3735 w
3013 3502 2944 3624 Dl
(51)3070 3735 w
3091 3502 3160 3624 Dl
(19)3286 3735 w
3445 3502 3376 3624 Dl
(17)3502 3735 w
3523 3502 3592 3624 Dl
3411 3445 146 146 De
(12)4906 2979 w
(20)4474 3231 w
4957 2998 4564 3120 Dl
(13)5338 3231 w
5035 2998 5428 3120 Dl
(29)4258 3483 w
4525 3250 4348 3372 Dl
(23)4690 3483 w
4603 3250 4780 3372 Dl
(15)5122 3483 w
5389 3250 5212 3372 Dl
(22)5554 3483 w
5467 3250 5644 3372 Dl
(35)4150 3735 w
4309 3502 4240 3624 Dl
(40)4366 3735 w
4387 3502 4456 3624 Dl
(26)4582 3735 w
4741 3502 4672 3624 Dl
(51)4798 3735 w
4819 3502 4888 3624 Dl
(19)5014 3735 w
5173 3502 5104 3624 Dl
(17)5230 3735 w
5251 3502 5320 3624 Dl
5355 3193 146 146 De