תקציר שימושי מחשב, סמסטר ב תשעג, גיא בלשר, מבני נתונים

חזרה לקישורים לתקצירים

המטרה: לכתוב פונקציות להוספה, למחיקה, לחיפוש ולמיון במערך. נחלק את הפעולות לשני מקרים: המערך אינו ממוין והמערך ממוין.

מערך שאינו ממוין

נגדיר איזשהו מערך:

;[v=[79,100,31,5,84

ונבצע עליו את הפעולות הבאות:

הוספה

(function [u] = add2array (v,k
הפונקציה מוסיפה איבר k למערך v ומחזירה u %
;u=v
;u(end+1)=k
end

מחיקה

אפשרות 1:

(function [u] = deleteFromArray (v,p
הפונקציה מוחקת את האיבר ה־p־י במערך ומחזירה u %
;(u=zeros(length(v)-1,1
;(u(1:p-1)=v(1:p-1
;(u(p:length(v)-1)=v(p+1:end
end

אפשרות 2:

(function [u] = deleteFromArray2 (v,p
הפונקציה מוחקת את האיבר ה־p־י במערך ומחזירה u %
;(u=zeros(length(v)-1,1
for i=1:p-1
   ;(u(i)=v(i
end
(for i=p+1:length(v
   ;(u(i-1)=v(i
end
end

חיפוש

(function [p] = findInArray (v,x
הפונקציה מחזירה את המקום במערך שבו x נמצא או אפס אם x אינו במערך %
;k=1
;p=0
;(n=length(v
while p==0 && k<=n
   if v(k)==x
      ;p=k
   else
      ;k=k+1
   end
end
end

מערך ממוין

כעת נניח שיש לנו מערך ממוין v, למשל מהקטן לגדול.

מחיקה

בדיוק כמו במערך שאינו ממוין.

חיפוש

ישנן שתי שיטות חיפוש: חיפוש בינארי ואריה במדבר.

חיפוש בינארי:

(function [p] = binarySearch (v,x
;(n=length(v
;L=1
;H=n
while L<H-1
   ;(M=floor((L+H)/2
      (if x<v(M
         ;H=M
      else
         ;L=M
      end
end
(if x==v(H
   ;p=H
else
   ;p=L
end
end

מספר הפעולות בחיפוש בינארי: [math]\displaystyle{ \log_2 n }[/math]

הוספה

אם x קטן מ־(v(1, נכניס אותו בהתחלה. אחרת נחפש את x ונכניס אותו אחרי L.

מיון פשוט

ראשית, נכתוב פונקציית עזר:

(function [m,p] = findSmallest (v,k
הפונקציה מוצאת את המקום p ואת הערך m הנמצא במערך v והמינימלי מהמקום ה־k־י והלאה %
;p=k
;(m=v(k
;(n=length(v
for i=k+1:n
   if v(i)<m
      ;p=i
      ;(m=v(i
   end
end
end

כעת, נכתוב את התוכנית למיון:

for i=1:n-1
   ;(m,p]=findSmallest(v,i]
   ;(v(p)=v(i
   ;v(i)=m
end