ساختمان داده ها ( قسمت دوم )

در قسمت قبل کمی با آرایه آشنا شدیم که عناصرش چطور در حافظه ذخیره می شود و گفتیم که در آرایه میتونیم عملیاتی رو انجام دهیم ، مانند : جستجو ، درج ، حذف و ... در جستجو مدل خطی یا Linear Search و مدل دودویی یا Binary Search داریم. در جستجوی خطی گفتیم که عنصر مورد جستجو با هر یک از عناصر آرایه مقایسه می شود ، چنانچه با هم برابر بودند جستجو تمام می شود وگرنه عمل مقایسه با عنصر بعدی انجام می شود. این روند تا پایان عنصر مورد نظر و یا جستجوی تمام آرایه ادامه می یابد. می خواهیم ببینیم جستجوی دودویی چی هستش ؟ چطور می تونیم یه عنصری از آرایه را حذف کنیم ؟ با الگوریتم هاشون آشنا شده و یه مثال ساده با زبان #C پیاده سازی می کنیم.

جستجوی دودویی یا Binary Search : فقط در آرایه های مرتب استفاده می شود. با فرض اینکه آرایه به صورت صعودی مرتب شده است : در این روش عنصر مورد نظر با خانه وسط آرایه مقایسه می شود ، اگر با این خانه برابر بود ، جستجو تمام می شود. اگر عنصر مورد جستجو از خانه وسط بزرگتر بود ، جستجو در بخش بالایی آرایه و در غیر این صورت جستجو در بخش پایینی آرایه انجام می شود.

مثال : در لیست زیر ، می خواهیم ببینیم عدد 23 در کدام خانه قرار دارد ؟

ابتدا خانه وسطی ( mid ) کلید 4 را با عدد 23 مقایسه می کنیم ، اگر کلید کمتر از عنصر mid است، به چپ و اگر بزرگتر از وسط است، فضای جستجو را به سمت راست می بریم.

کلید (یعنی 23) بزرگتر از عنصر میانی فعلی (یعنی 16) است. پس فضای جستجو به سمت راست حرکت میکنه. کلید کمتر از Mid 56 فعلی است. فضای جستجو به سمت چپ حرکت می کند.

اگر کلید با مقدار عنصر mid مطابقت داشته باشد ، عنصر پیدا شده و جستجو متوقف می شود.

الگوریتم جستجوی دودویی Binary Search به زبان #C :

    public int BinarySearch(int[] array, int x)
    {
        int i = 0, r = array.Length - 1;
        while (i <= r)
        {
            int mid = i + (r - 1) / 2;
            if (array[mid] == x)
                return mid;
         if (array[mid] < x)
                i = mid + 1;
            else
                r = mid - 1;
        }
        return -1;
   }

نوع الگوریتم اینطور هستش با یک حلقه این کار انجام میشود ، تا وقتی i کمتر یا مساوی از r هست mid را پیدا میکند ، mid = (i + r ) / 2 ، بعد از اینکه mid را پیدا کرد ، اگر عنصر وسط با عنصر مورد نظر برابر بود mid را برمیگرداند ، اگر عنصر مورد نظر از عنصر وسط بزرگتر بود ، در بخش بالایی آرایه دنبالش میگردد ، در بخش بالایی mid + 1 خواهد شد در غیر این صورت یعنی عنصر مورد نظر از عنصر وسط کوچکتر هستش ، در بخش پایینی آرایه دنبالش میگردد ، در بخش پایینی mid - 1 خواهد شد. اگر هم عنصر مورد نظر در آرایه وجود نداشته باشد 1- را برمیگرداند.

مثال :در آرایه زیر با استفاده از الگوریتم Binary Search می خواهیم عدد 10 رو پیدا کنیم :

 public class Program
 {
     public int BinarySearch(int[] array, int x)
     {
         int i = 0, r = array.Length - 1;
         while (i <= r)
         {
             int mid = i + (r - 1) / 2;
             if (array[mid] == x)
                 return mid;
             if (array[mid] < x)
                 i = mid + 1;
             else
                 r = mid - 1;
         }
         return -1;
}
     public void Main()
     {
         int[] array = { 2, 3, 4, 10, 40 };
         int x = 10;

         int result = BinarySearch(array, x);

         if (result == -1)
             Console.WriteLine(
                 &quotElement is not present in array&quot);
         else
             Console.WriteLine(&quotElement is present at &quot
                         + &quotindex &quot + result);
     }
 }

خروجی :

Element is present at index 3

حذف از آرایه (نامرتب) : در عملیات حذف، عنصری که باید حذف شود با استفاده از جستجوی خطی جستجو می شود (چون آرایه نامرتب) ، سپس عملیات حذف و سپس جابجایی عناصر انجام می شود.

الگوریتم حذف از آرایه (نامرتب) به زبان #C :

      int Delete(int[] arr, int n, int key)
 {
     int pos = FindElement(arr, n, key);
     if (pos == -1)
     {
         Console.WriteLine(&quotElement not found&quot);
         return n;
     }
     int i;
     for (i = pos; i < n - 1; i++)
         arr[i] = arr[i + 1];
     return n - 1;
 }

الگوریتم 3 ورودی دارد : آرایه ای به اسم a کل عناصر ، n تعداد عناصر موجود در آرایه ، key عنصری که می خواهیم حذفش کنیم. ابتدا با تابع ;()FindElement یک جستجوی خطی انجام می دهیم (چون آرایه نامرتب) ، اگر key وجود داشته باشد ، این تابع ، pos را به ما میدهد ، اگر هم عددی که دنبالش هستیم داخل آرایه نباشد ، یعنی pos == -1 باشد ، n را بر میگرداند چون حذفی انجام نشده و تعداد خانه های آرایه همان هستش. اگر عددی که دنبالش هستیم داخل آرایه باشد عمل شیفت را انجام میدهد. یعنی از pos تا 1 - n

مثال : در آرایه زیر می خواهیم عدد 30 را حذف کنیم :

    public class Program
    {
        int FindElement(int[] arr, int n, int key)
        {
            for (int i = 0; i < n; i++)
               if (arr[i] == key)
                    return i;
            return -1;
        }

        int DeleteElement(int[] arr, int n, int key)
        {
            int pos = FindElement(arr, n, key);
            if (pos == -1)
            {
                Console.WriteLine(&quotElement not found&quot);
                return n;
            }
            for (int i = pos; i < n - 1; i++)
                arr[i] = arr[i + 1];
            return n - 1;
        }

          public void Main()
        {
            int i;
            int[] arr = { 10, 50, 30, 40, 20 };
           int n = arr.Length;
            int key = 30;
           Console.Write(&quotArray before deletion  : &quot);
            for (i = 0; i < n; i++)
              Console.Write(arr[i] + &quot &quot);
              Console.WriteLine();

              // Function call
              n = DeleteElement(arr, n, key);
             Console.Write(&quotArray after deletion  : &quot);
              for (i = 0; i < n; i++)
              Console.Write(arr[i] + &quot &quot);
        }
    }
}

خروجی :

 Array before deletion  : 10 50 30 40 20
 Array after deletion  : 10 50 40 20