• بازدید : 51 views
  • بدون نظر
این فایل در ۱۲۳صفحه قابل ویرایش تهیه شده وشامل موارد زیر است:

در اصطلاح کامپیوتری، ساختمان داده به روشهایی از ذخیره اطلاعات گفته می شود که برای استفاده بهینه از اطلاعات ذخیره شده اتخاذ می شود. غالباً انتخاب یک ساختمان داده موجب ایجاد الگوریتم (الخوارزمی) های متناسب با آن خواهد شد که این دو در کنار هم موجب افزایش سرعت انجام یک وظیفه یا کاهش مصرف حافظه برای پردازش داده می شود؛ سنگ بنای ساختمان های داده انواع داده و اشاره گرهای گوناگون است. که با توجه به چگونگی تعریف کاربرد آنها در هر زبان برنامه نویسی پیاده سازی آنها متفاوت خواهد بود. ما اکنون به پیاده سازی ساختمان های داده نمی پردازیم بلکه به توضیح انواع داده موجود در زبان پایتون می پردازیم؛ به دلیل سطح بالای این زبان انواع داده موجود در آن دارای ساختار پیچیده ای هستند که باعث شد ما از این انواع به عنوان ساختمانهای داده یاد کنیم.
در زبان های سطح پایین تر که اکثر آنها از پایه های پایتون به حساب می آیند انواع داده پیش فرض انواعی ابتدایی هستند که در زبان اسمبلی نیز قابل تعریف هستند. مثلاً در زبان C از انواع int , char,float, double, long ,short استفاده می شود که همه آنها دارای خاصیتی مشترک هستند و این خاصیت این است که بر روی پردازنده به طور مستقیم دارای دستور العمل هایی هستند که می توان با آنها کار کرد. همچنین برای ایجاد یک زنجیره(آرایه) از این انواع از علامت “[]” استفاده می شد، ولی از این انواع داده غیر از عملیات ریاضی کاری بر نمی آید ، مگر اینکه از آنها با قرار دادهای خاصی ساختمان داده هایی بسازیم.
انواع ساختمان داده در پایتون
یکی از مهمترین و پرکاربرد ترین این ساختمان های داده رشته های کاراکتری می باشند که در واقع یک زنجیره (Sequence) از بایت ها می باشند که در کار با ورودی ها، خروجی ها و ارتباطات گوناگون نقش مهمی ایفا می کنند، زیرا یکی از راههای محدود فهم انسان از دنیای کامپیوتر ارتباط متنی با این جهان می باشد.
دبگر ساختمان داده ای مهم در این زبان لیست ها (آرایه ها) هستند. در واقع این نوع داده یک نوع بسیار پیشرفته از آرایه های زبانهای سطح پایین است که علاوه بر خاصیت اندیس پذیری ، خاصیت تغییر اندازه و نگهداری انواع داده را بطور هم زمان دارا می باشد.
چند تایی های مرتب (Tuple)در پایتون نوعی از داده با شباهت هایی به لیست می باشد که در بخش مربوطه به تفاوت ها و شباهت های این دو نوع خواهیم پرداخت.
یک نوع دیگر داده در پایتون چرخنده(Iterator)است که به عنوان یک فریم یا واحد چرخنده در طول لیست ها ، چند تایی ها و رشته ها محسوب می شود.
ساختمان داده های دیگر
در جملات فوقالذکر مشاهده کردید که ما با تعداد محدودی ساختمان داده روبرو هستیم. اما ما مجبورنیستیم که با این ساختمان داده ها بسوزیم و بسازیم. بلکه این ساختمانهای داده سنگ بنای چندین ساختمان داده دیگر هستند که هر کدام کاربرد و پیچیدگیهای خاص خود را دارند از آنجمله می توان موارد زیر را نام برد:
لیست های پیوندی
یکطرفه
دوطرفه
حلقوی
صف ها
صف های دو طرفه
صفهای با اولویت
درختها
دودویی
دودویی جستجو
درختهای دو-سه
heap
Deap
MinMax Heap
  • بازدید : 36 views
  • بدون نظر

این فایل در ۱۰صفحه قابل ویرایش تهیه شده وشامل موارد زیر است:

اگر چه مفهوم جستجوی دودویی ساده است اما باید دز هنگام نوشتن الگوریتم نکاتی را در نظرگرفت:
۱٫در مورد بردارهایی که تعداد عناصرشان زوج است، عنصر وسط بردار منحصر به فرد نسیت
۲٫ در مواردی که جستجو ناموفق باشد زمان خاتمه کار الگوریتم بسادگی مشخص نمی شود
 در اینجا با تشریح روش فوق به صورت ساده تر شما را با جزییات کار آشنا می سازیم.
*فرض کنید بردار N  عنصریA  به صورت مرتب شده صعودی وجود داشته باشد ، در این صورت الگوریتم جستجوی کلمه یا عدد p در بردار فوق به صورت زیر خواهد بود :
 مرحله اول :مقدار صفر را در متغیرlowومقدار  N+1را در متغیرHIGH قرار می دهیم.
 
                       HIGH N +1   و      LOW  ۰
مقدار ابتدایی ترینLOW و مقدار انتهایی ترینHIGH ناحیه جستجو می باشند.
مرحله دوم : برای پیدا کردن نقطه میانی بردار فوق ، خارج قسمت صحیح تقسیم LOW+HIGH)) بر ۲ را در  MIDقرار می دهیم
                               2/(LOW+HIGH) می رود در MID
مرحله سوم : اگر MID= LOW است ، کلمهp  در بردار وجود ندارد در این صورت الگوریتم پایان می پذیرد، در غیر این صورت نرخله چهارم را انجام می دهیم 
مرحله چهارم : اگر  P= A( IMD )است ،جسحجو موفقیت آمیز بوده والگوریتم پایان می یابد در غیر این صورت اگرP <A (MID)  است مقدار MID در HIGH  قرار داده و به مرحله دوم باز می گردیم و در غیر این صورت اگر P > A( MID) است مقدارMID را در LOW قرار داده وبه مرخله دوم باز می گردیم
****** (( الگوریتم فوق در برداری حاویN کلمه که عناصر آن با ترتیب صعودی قرار گرفته اند،به دنبال کلمه مورد نظرP  می گردد. ابتداP با عنصر میانی جدول مقایسه می شود . اگرP از این عنصر میانی بزرگتر یاشد در مرحله بعد با عنصر میانی نیمه دوم جدول مقایسه می گردد اگرP از این عنصر میانی کوچکتر باشد در مرحله بعد با عنصر میانی نیمه اول مورد مقایسه قرار می گیرد.این عمل هر بار با حذف نیمی از بردار ادامه می یابد  تا اینکه یاP در بردارپیدا شود ویا اینکه معلوم شود که  Pدر بردار نیست.))****** 
الگوریتمی که اسامی دانشجویان را که به طور صعودی مرتب هستند از ورودی خوانده، در آرایه قرار      می گیرد .سپس نامی را از روش دودویی در آرایه جستجو می کند.
 متغیر ها
تعداد دانشجویان                  N
آرایه                                 S                  
متغیر کمکی                    SW
حد پایین آرایه                    L  
حد بالای آرایه                     H
اندیس وسط آرایه               M  
نام مورد جستجو                  

عتیقه زیرخاکی گنج