Зертханалық жұмыс №1 Тақырыбы: Ақпаратты көрсету. Ақпаратты есептеу
жүктеу/скачать 0.88 Mb.
|
- Бұл бет үшін навигация:
- Пирамида құру.
- Қорытынды алгоритм.
| Пирамиданы қайта құру. Ең үлкен элементті түпкі тамырдан тізімге көшіргенде түпкі тамыр торабы бос болып қалады. Оған екі тікелей ұрпақтың үлкені орналасу керек. Бұл кезде пирамида толық бұтаққа барынша жақын болып қалу керек. Қайта құру төменгі деңгейдің ең шеткі оң жақ элементтен басталады. Пирамиданы қайта құру процедурасы төменде көрсетілген.
List сұрыпталатын тізім/пирамида Root пирамиданың түп тамырының номері Key пирамидаға қосылатын кілттік мән bound пирамиданың оң жақ шеті (номері) Procedure FixHeap(list, root, key, bound); var vacant, largerChild: integer; Begin vacant=root; while 2*vacant<=bound do begin largerChild:=2*vacant; {екі тікелей ұрпақтың ең үлкенін іздестіру} if (largerChild< bound) and (list[largerChild+1]> list[largerChild]) then largerChild:= largerChild+1; {кілт ағымдағы ұрпақтан жоғары орналасқан ба?} if key> list[largerChild] then {иә, циклаяқталды} break else {жоқ, тікелей ұрпақтың үлкенін жоғары көтеру керек} begin list[vacant]:=list[largerChild]; vacant:= largerChild; end; end; list[vacant]:=key; End; Пирамида құру.Кез келген екі мәнді бос тораптың жапырақтары деп санауға болады. Соңғы элементтер жапырақтар болып табылатындықтан тізімнің екінші бөлігімен ештеңе істеудің қажеті жоқ. Жапырақтардан кішкене пирамидалар жасауға болады, одан кейін барлық мәндер тізімге кіргенге дейін оларды біртіндеп біріктіріп жинау керек. Келесі цикл осы процедураны жүзеге асыруға мүмкіндік береді: fori:=ndiv 2 downto 1 do FixHeap(list, i, list[i], N); Қорытынды алгоритм. for i:=n div 2 downto 1 do FixHeap(list, i, list[i], N); for i:=n downto 2 do begin max:= list[1]; FixHeap(list, 1, list[i], i-1); list[i]:= max; end; Тапсырмалар Төмендегі көрсетілген тізімге пирамида құру кезеңін қолданғаннан кейінгі реті қандай болады: (23, 17, 21, 3, 42, 9, 13, 1, 2, 7, 35, 4)? Мына тізімді (4, 1, 3, 2, 7, 6, 8, 9, 5) сұрыптаудың пирамидальды алгоритмінің барлық жүрістері-нің нәтижесін көрсетіңдер . жүктеу/скачать 0.88 Mb. Достарыңызбен бөлісу:
|