Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Вставка элементов в массив, удаление, сортировка, поиск элемента по ключу на ассемблере. Вариант 12 - файл l5.doc


Вставка элементов в массив, удаление, сортировка, поиск элемента по ключу на ассемблере. Вариант 12
скачать (118.5 kb.)

Доступные файлы (6):

l5.doc254kb.23.03.2010 14:49скачать
L5.EXE
L5.LST
L5.MAP
L5.OBJ
L5.TR

содержание
Загрузка...

l5.doc

Реклама MarketGid:
Загрузка...

Міністерство освіти і науки України

Національний технічний університет України

Київський політехнічний інститут”

Факультет інформатики та обчиcлювальної техніки

Кафедра обчиcлювальної техніки

Дисципліна:

«системне програмування»





Розрахунково-графічна РОБОТА

Тема: «Методи cортування, вcтавлення та видалення елементів таблиць»


Виконав студент: Хіміченко В.Б.___

Група: ЗІО-81___________________

Варіант №12____________________

Прийняв викладач: Муcіна Т.В.____


Підпис викладача _______________


Дата здачі _______________*******



Київ 2010
1 завдання на розрахунково-графічну роботу згідно з варіантом

frame1Организовать процедуры линейного и бинарного поиска
2 екранні форми програми:






























3 ліcтинг програми:

;определение структурного типа таблицы

str_table struc

key dw 2031h;ключ

field dw 2031h;характеристика

str_table ends

;макрос вставки элемента в таблицу (beg_table – начало таблицы, in_position – ;позиция для вставки, ins_Key – ключ вставляемого элемента, ins_Field – ;характеристика вставляемого элемента,len_table – текущая длина таблицы

insertElementAt macro beg_table, in_position, ins_Key, ins_Field, len_table

local right_shift,no_shift,set_single_count_value

mov si,in_position

dec si

shl si,2

mov cx,len_table

sub cx,in_position

push ins_Key

push ins_Field

mov ax,beg_table[si].key

mov bx,beg_table[si].field

push bx

push bp

mov bp,sp

mov ins_Key,[bp+6]

mov ins_Field,[bp+4]

mov beg_table[si].key,ins_Key

mov beg_table[si].field,ins_Field

mov bx,[bp+2]

jb no_shift

add si,4

jcxz set_single_count_value

jmp right_shift

set_single_count_value: mov cx,1

right_shift: mov beg_table[si].key,ax

mov beg_table[si].field,bx

add si,4

mov ax,beg_table[si].key

mov bx,beg_table[si].field

;add si,4

loop right_shift

no_shift: inc len_table

pop bp

add sp,6

endm

;

removeElementAt macro beg_table,position,len_table

local left_shift

mov cx,len_table

sub cx,position

dec len_table

mov si,position

dec si

shl si,2

left_shift: add si,4

mov bx,beg_table[si].key

mov dx,beg_table[si].field

sub si,4

mov beg_table[si].key,bx

mov beg_table[si].field,dx

add si,4

loop left_shift

endm

;выводит строку s в позиции курсора, занесенной в dx (dl – x, dh - y)

out_str macro msg

mov ax,0200h

mov bx,0000h

int 10h

lea dx, msg

mov ah,09h

int 21h

endm

;выводит строку s в текущей позиции курсора

out_msg macro s

lea dx,s

mov ah,09h

int 21h

endm

;читает с клавиатуры в текущей позиции курсора символ (заносит в al его ASCII ;код)

getchar macro

mov ah,01h

int 21h

endm

;выводит на экран в текущей позиции курсора символ character

outchar macro character

mov dl,character

mov ah,02h

int 21h

endm

data segment

t_len dw 05h; текущая длина таблицы

CR_LF db 0dh,0ah,'$';перевод на новую строку

delete db 'Нажмите (Y/N) для удаления элемента из таблицы $'

insert db 'Нажмите (Y/N) для вcтавки элемента в таблицу $'

open_angle db ' <$'

sort db 'Нажмите (Y/N) для шейкерной cортировки таблицы $'

lsearch db 'Нажмите (Y/N) для линейного поиска $'

bsearch db 'Нажмите (Y/N) для бинарного поиска $'

table_content db 'Cодержимое таблицы: $'

view_table db 'Нажмите (Y/N) для проcмотра таблицы $'

exit_pass db 'Нажмите (Y/N) для выхода $'

inp_pos db 'Введите номер позиции: -> ','$'

inp_key db 'ВВедите ключ искомого элемента: -> $'

inp_val db ' ВВедите поля элемента < $'

between_val db ' , $'

any_key db ' Нажмите любую клавишу для продолжения $'

end_str db '>',0dh,0ah,'$'

pos0 dw 0202h

pos1 dw 0303h

key_value dw 3131h

field_value dw 3131h

bin_v dw 00h

bin dw 02h

between_index dw 00h

between_v dw 00h

high_index dw 00h

high_v dw 00h

key_v dw 00h

low_index dw 00h

low_v dw 00h

founded db 'Найденный элемент $'

not_founded db 'Элемент с указанным ключом не найден $'

i dw 0000h;нижний индекс последнего обмена соседних элементов при обратном ;проходе

j dw 0010h;верхний индекс последнего обмена соседних элементов при прямом ;проходе

coeff db 11

divider db 128

rand_val db 3

exchange_counter db 00h

t_element str_table <'05','ab'>

str_table <'16','cd'>

str_table <'32','ef'>

str_table <'01','gh'>

str_table <'07','ij'>;<'03','kl'><'45','mn'>

;250 dup(str_table <'11','qw'>)

data ends

stk segment stack

dw 32 dup(3131h)

stk ends

code segment

assume cs:code,ds:data, ss:stk

clear_screen proc

mov ax,0600h

mov bx,0700h

mov cx,0000h

mov dx,184fh

int 10h

ret

clear_screen endp

goto_xy proc

mov ax,0200h

mov bx,0000h

int 10h

ret

goto_xy endp

out_Char proc

mov ah,02h

int 21h

out_Char endp

;процедура помещающая в ах значение шестнадцатиричной цифры в al, ;представленной в ASCII коде

ascii_to_bin proc

push dx

xor dx,dx

mov dl,al

mov ax,dx

pop dx

cmp al,39h

jbe lbl09

cmp al,46h

jbe AF_Upper_case

cmp al,66h

jbe af_lower_case

lbl09: sub al,30h

jmp end_conv

AF_Upper_Case: sub al,37h

jmp end_conv

af_lower_case: sub al,57h

end_conv: ret

ascii_to_bin endp

getyn proc

getchar

cmp al,59h

ret

getyn endp

get_y_n proc

getchar

cmp al,79h

ret

get_y_n endp

;процедура, выводящая на экран текущее содержимое таблицы

show_table proc

xor si,si

call clear_screen

mov dx,pos0

out_str table_content

out_msg CR_LF

mov cx,t_len

out_Element: out_msg open_angle

mov bx,t_element[si].key

outchar bh

outchar bl

out_msg between_val

mov bx,t_element[si].field

outchar bh

outchar bl

out_msg end_str

add si,type str_table

loop out_Element

out_msg any_key

getchar

ret

show_table endp

;процедура, организующая бинарный поиск

bin_search proc

call clear_screen;ввод ключа для поиска (две буквы)

mov dx,pos0

out_str inp_key

getchar

mov byte ptr key_v+1,al

getchar

mov byte ptr key_v, al

mov ax,t_len

dec ax

mov high_index,ax

search: mov ax,low_index

cmp ax,high_index

ja overl

xor dx,dx

mov ax,low_index

add ax,high_index

div bin_v

mov between_index,ax

mov si,ax

shl si,2

mov ax,t_element[si].key

mov between_v,ax

mov ax,between_v

cmp key_v,ax

jz bin_element_found

jb lesser

ja greater

jmp lesser

overl: jmp bin_element_nofound

lesser: mov ax,between_index

mov high_index,ax

dec high_index

jmp search

greater: mov ax,between_index

mov low_index,ax

inc low_index

jmp search

bin_element_found: mov si,between_index

call clear_screen

mov dx,pos0

out_str founded

mov si,between_index

shl si,2

mov bx,t_element[si].key

outChar bh

outChar bl

out_msg between_val

mov bx,t_element[si].field

outChar bh

outChar bl

out_msg end_str

out_msg any_key

getchar

jmp fin_b_search

bin_element_nofound: call clear_screen

mov dx,pos0

out_str not_founded

out_msg CR_LF

out_msg any_key

getchar

fin_b_search: ret

bin_search endp

;процедура, организующая линейный поиск

linear_search proc

call clear_screen;ввод ключа для поиска

mov dx,pos0

out_str inp_key

getchar

mov byte ptr key_v+1,al

getchar

mov byte ptr key_v,al

xor si,si

mov cx,t_len

repeat_compare: mov ax,t_element[si].key

add si,type str_table

cmp ax,key_v

loopnz repeat_compare

jcxz linear_nofound

linear_found: call clear_screen

mov dx,pos0

outChar al

out_str founded

sub si, type str_table

mov bx,t_element[si].key

outChar bh

outChar bl

out_msg between_val

mov bx,t_element[si].field

outChar bh

outChar bl

out_msg end_str

out_msg any_key

getchar

jmp fin_l_search

linear_nofound: sub si,type str_table

mov ax,t_element[si].key

add si,type str_table

cmp ax,key_v

jz linear_found

call clear_screen

mov dx,pos0

out_str not_founded

out_msg CR_LF

out_msg any_key

getchar

fin_l_search: ret

linear_search endp

;прямой проход с последовательным обменом соседних элементов при необходимости

direct_pass proc

direct: mov ax,t_element[si].key

cmp si,j

jz fin_frw_pass

add si,4

cmp ax,t_element[si].key

ja direct_exchange

cmp si,j

jz fin_frw_pass

jmp direct

direct_exchange: inc exchange_counter

mov ax,t_element[si].key

mov bx,t_element[si].field

sub si,4

push t_element[si].key

push t_element[si].field

mov t_element[si].key,ax

mov t_element[si].field,bx

add si,4

pop bx

pop ax

mov t_element[si].key,ax

mov t_element[si].field,bx

mov i,si

jmp direct

fin_frw_pass: ret

direct_pass endp

;обратный проход с последовательным обменом соседних элементов при необходимости

back_pass proc

rever_pass: mov ax,t_element[si].key

cmp si,i

jz fin_back_pass

sub si,4

cmp ax,t_element[si].key

jb rever_exchange

cmp si,i

jz fin_back_pass

jmp rever_pass

rever_exchange: inc exchange_counter

mov ax,t_element[si].key

mov bx,t_element[si].field

add si,4

push t_element[si].key

push t_element[si].field

mov t_element[si].key,ax

mov t_element[si].field,bx

pop bx

pop ax

sub si,4

mov t_element[si].key,ax

mov t_element[si].field,bx

mov j,si

jmp rever_pass

fin_back_pass: ret

back_pass endp

;процедура организующая шейкерную сортировку таблицы

shaker_sort proc

xor si,si

next_iteration: push i

call direct_pass

mov ax,i

mov j,ax

pop i

cmp exchange_counter,00h

jz show_result

mov exchange_counter,00h

push j

call back_pass

mov ax,j

mov i,ax

pop j

cmp exchange_counter,00h

jnz next_iteration

show_result: call show_table

ret

shaker_sort endp

;процедура обработки запроса удаления элемента из таблицы

remove_element proc

inp_del_pos: call clear_screen

mov dx,pos0

out_str inp_pos;ввод номера позиции удаляемого элемента

getchar; (две шестнадцатиричные цифры)

call ascii_to_bin

mov dl,10h

mul dl

mov bx,ax

getchar

call ascii_to_bin

add bx,ax

cmp bx,t_len

ja inp_del_pos

removeElementAt t_element,bx,t_len

ret

remove_element endp

;процедураобработки запроса вставки элемента в таблицу

insert_element proc

inp_ins_pos: call clear_screen

mov dx,pos0

out_str inp_pos;ввод номера позиции для вставки

getchar

call ascii_to_bin

mov dl,10h

mul dl

mov bx,ax

getchar

call ascii_to_bin

add bx,ax

dec bx

cmp bx,t_len

ja inp_ins_pos

inc bx

mov ax,bx

push ax

out_msg CR_LF

out_msg inp_val

getchar

mov bh,al

getchar

mov bl,al

push bx

out_msg between_val

getchar

mov dh,al

getchar

mov dl,al

pop bx

pop ax

insertElementAt t_element,ax,bx,dx,t_len

out_msg end_str

out_msg any_key

getchar

ret

insert_element endp

main:

mov ax,data

mov ds,ax

mov es,ax ;последовательный цикл запросов на удаление, вставку

retry_again: call clear_screen;поиск элементов и сортировку таблицы

mov dx,pos0; пока на последнем шаге (Нажмите (Y/N) для выхода)

out_str delete ;не нажата клавиша <y>

call get_y_n

jz remove_Elt

jmp check_insert

remove_Elt: call remove_element

jmp retry_again

check_insert: call clear_screen

mov dx,pos0

out_str insert

call get_y_n

jz insert_Elt

jmp check_sorting

insert_Elt: call insert_element

jmp retry_again

check_sorting: call clear_screen

mov dx,pos0

out_str sort

call get_y_n

jz t_sort

jmp check_linear_seach

t_sort: call shaker_sort

retry_check_pass: jmp retry_again

check_linear_search: call clear_screen

mov dx,pos0

out_str lsearch

call get_y_n

jz t_l_search

jmp check_binary_search

t_l_search: call linear_search

retry_check_pass1: jmp retry_again

check_binary_search: call clear_screen

mov dx,pos0

out_str bsearch

call get_y_n

jz t_b_search

jmp check_bin_search

t_b_search: call bin_search

jmp retry_again

check_bin_search: call clear_screen

mov dx,pos0

out_str view_table

call get_y_n

jz check_table_content

jmp check_exit

check_table_content: call show_table

jmp retry_check_pass1

check_exit: call clear_screen

mov dx,pos0

out_str exit_pass

call get_y_n

jnz retry_check_pass1

mov ax,4c00h ;выход из программы (завершение сеанса ms-dos)

int 21h

code ends

end main

4 выводы

в этой расчетно-графической работе мы научились работать с основными операциями над массивами структурного типа на ассемблере, выполнять сортировку, поиск, а также вставлять и удалять элементы.



Содержание


11. Список литературы 18


^


11. Список литературы


  1. Юров В. «Assembler». Учебник — СПб.: Издательский дом «Питер», 2001 г. 624с.

  2. Юров В. «Assembler: специальный справочник» — СПб.: Издательский дом «Питер», 2001 г. 496с.

  3. Корнеев В.В., Киселёв А.В. «Современные микропроцессоры» — М. «Нолидж», 1998г. — 240с.

  4. Джордейн Р. «справочник программиста персональных компьютеров тип IBM PC, XT и AT: Пер. с англ. /Предисл. Н. В. Гайского. — М.: «Финансы и статистика», 1991 г. —544 с.

  5. Пирогов В. Ю. «Assembler. Учебный курс». — М.: «Нолидж», 2001 г. — 848с.





Скачать файл (118.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации