مشاهده دست آورد نظرسنجی: ظاهرا از تاپیک استقبال چندانی نشد؛ ادامه بدیم یا نه؟

رای دهنده
262. شما نمی توانید در این رای گیری رای بدهید
  • بله

    248 94.66%
  • نه

    14 5.34%
نمایش نتایج 1 تا 32 از 32

نام تاپیک: نكاتي در مورد ساختمان داده

  1. #1
    کاربر دائمی آواتار mehdad.koulab
    تاریخ عضویت
    فروردین 1387
    محل زندگی
    تبریز
    پست
    345

    نكاتي در مورد ساختمان داده

    سلام
    چند وقتي بود ميخواستم يه تاپيك در مورد ساختمان داده بزنم و مطالب مفيد مربوط به ساختمان داده رو با كمك دوستان تو اون جمع كنيم تا يه تاپيك جالبي به وجود بياد. من خودم كه چيز زيادي بلد نيستم فقط الگوريتمها و ... تو دانشگاه گفتن رو بلدم كه اونارو هم يكي يكي ميذارم.
    از دوستان خواهش ميكنم اگه مطلبي دارن كه مفيد ميتونه باشه دريغ نكنند. با تشكر
    آخرین ویرایش به وسیله mehdad.koulab : یک شنبه 20 مرداد 1387 در 13:28 عصر

  2. #2
    کاربر دائمی آواتار mehdad.koulab
    تاریخ عضویت
    فروردین 1387
    محل زندگی
    تبریز
    پست
    345

    نقل قول: نكاتي در مورد ساختمان داده

    اينم رئوس مطالب

    1)آرائه

    2)پشته

    3)صف

    4)لیست هاي پيوندي (يك طرفه خطي و ...)

    5)درخت

    6)گراف

  3. #3
    کاربر دائمی آواتار mehdad.koulab
    تاریخ عضویت
    فروردین 1387
    محل زندگی
    تبریز
    پست
    345

    نقل قول: نكاتي در مورد ساختمان داده

    اولين مطلب رو هم خودم ميذارم
    اصلا ميگم اين ساختمان داده چيست؟
    عبارت است از ساختارهای دادهای که درحافظهء اصلی کامپیوتر در نظرمی گیریم تا بتوانیم الگوریتمهای برنامه نویسی را بر روی آنها به شکل مناسب پیاده سازی نماییم.

  4. #4
    کاربر دائمی آواتار mehdad.koulab
    تاریخ عضویت
    فروردین 1387
    محل زندگی
    تبریز
    پست
    345

    نقل قول: نكاتي در مورد ساختمان داده

    آرایه:
    مجموعه ای از داده ها هستند که نوعشان یکسان است به عنوان مثال:اگر 10 عدد صحیح را بخواهیم در حافظه اصلی قرار دهیم بجای انکه 10 متغیر (int) تعریف بکنیم یک آرایه (int) تعریف می کنیم که 10 خانه داشته باشد .

    [Int b [3][4 = آرایه 2 بعدی : مثال




    آرایه های 2 بعدی را ماتریس نیز می گویند .

    در آرایه های 2 بعد به بالا برای اینکه بتوانیم عناصر را به صورت صحیح از خانه هایی که ذخیره شده اند بازیابی نماییم بایستی مشخص گردد که اگر ذخیرهء عناصر به شکل سطری است بازیابی آنها نیز به شکل سطری باشد و اگر ستونی است بازیابی انها به صورت ستونی باشد.



    روش سطری پیمایش و ذخیرهء آرایه ها :


    b11 , b12 , b13 , b14 , b21 , b22 , b23 , b24 , b31 , b32 , b33 , b34

    در پیمایش سطری آرایه ها اندیسهای خانه های آرایه از سمت راست تغییر می کنند بطوریکه اندیس سمت چپ به صورت ثابت باقی می ماند و یک واحد یک واحد به اندیس سمت راست اضافه می شود تا زمانیکه به ماکسیمم مقدار خود برسد که در این لحظه یک واحد به اندیس سمت چپ اضافه می شود و دوباره اندیس سمت راست شروع به افزایش می یابد واین کار تا زمانی ادامه پیدا می کند که هر 2 اندیس به ماکسیمم مقدار خود برسد.
    مثال : ماتریس 3 بعدی زیر را به صورت سطری پیمایش کنید:
    [Int a [3][4][3

    a111 , a211 , a311 , a121 , a221 , a321 , a131 , a231 , a331 , a141 , a241 , a341 , a112 , a212 , a312 , a122 , a222 , a322 , a132 , a232 , a332 , a142 , a242 , a342 , a113 , a213 , a313 , a123 , a223 , a323 , a133 , a233 , a333 , a143 , a243 , a343



    روش ستونی پیمایش ذخیره ها :

    در روش ستونی اندیسهای آرایه از سمت چپ شروع به افزایش می کنند یعنی اندیسهای سمت چپ یک واحد یک واحد اضافه می شوند تا زمانی که به ماکسیمم مقدار خود برسند که در این لحظه یک واحد اندیس سمت راست اضافه می شود و دوباره اندیس سمت چپ از 1 شروع به افزایش می کند و این کار تا زمانی انجام می گیرد که تمامی اندیسها به ماکسیمم مقدار خود برسند .
    b11 , b21, b31 , b12 , b22 , b32 , b13 , b23 , b33 , b14 , b24 , b34


    a111 , a211 , a311 , a121 , a221 , a321 , a131 , a231 , a331 , a141 , a241 , a341 , a112 , a212 , a312 , a122 , a222 , a322 , a132 , a232 , a332 , a142 , a242 , a342 , a113 , a213 , a313 , a123 , a223 , a323 , a133 , a233 , a333 , a143 , a243 , a343
    دوستان تا اينجا رو داشته باشين بقيش رو هم ميذارم

  5. #5
    کاربر دائمی آواتار mehdad.koulab
    تاریخ عضویت
    فروردین 1387
    محل زندگی
    تبریز
    پست
    345

    نقل قول: نكاتي در مورد ساختمان داده

    ماتریس اسپارس (خلوت - پراکنده) :
    ماتریسی است که اکثریت عناصر ان مقدار ثابت و غیر قابل محاسبه ( معمولا صفر) می باشد و تنها تعداد کمی از خانه های ان داده ها به درد بخور می باشند بنابراین فضای بسیار زیادی از حافظه اصلی را برای ذخیره کردن این تعداد کم داده ها تلف می کنیم .


    مثال :


    0 0 0 2 0
    0 0 3 0 1
    0 0 0 0 0
    0 18 0 0 0

    به عنوان مثال در ماتریس فوق برای ذخیره کردن چهار عنصر غیر صفر یک ماتریس ( 5 * 4 ) و 20 خانه از حافظه را تلف کرده ایم روشی که برای ذخیرهء بهینهء این نوع ماتریسها استفاده می شود بدین صورت است که یک ماتریس در نظر می گیریم که همیشه 3 ستون خواهد داشت و به تعداد عناصر غیر صفر سطر خواهد داشت که در هر سطر در ستون اول شمارهء سطر مربوط به عنصر غیر صفر ودر ستون دوم شمارء مربوط به ستون عنصر غیر صفر ودر ستون سوم مقدار عنصر غیر صفر را ذخیره خواهیم کرد
    که کاهش قابل توجهی در میزان حافظه مصرفی خواهیم داشت.
    i j value
    2 2 1
    1 1 2
    3 3 2
    18 4 4
    آخرین ویرایش به وسیله mehdad.koulab : یک شنبه 13 مرداد 1387 در 19:09 عصر دلیل: مشكل چپ به راست داشت. شرمنده

  6. #6
    کاربر دائمی آواتار mehdad.koulab
    تاریخ عضویت
    فروردین 1387
    محل زندگی
    تبریز
    پست
    345

    نقل قول: نكاتي در مورد ساختمان داده

    الگوريتمهاي مربوط به پيمايش هاي سطري و ستوني


    [A [n][m

    پیمایش سطری:

    for i: =1 to n do
    for j: =1 to m do
    write (a [i,j] ) ;


    پیمایش ستونی :

    for j: =1 to m do
    for i: =1 to n do
    write (a[i,j] ) ;



    مثال : با استفاده ازfor های تو در تو یک ماتریس 3 بعدی

    ( 2* 3 * 4 ) به 2 روش سطری و ستونی پیمایش کنید:



    پیمایش سطری:

    for i: =1 to 4 do

    for j: =1 to 3 do

    for k: =1 to 2 do

    write ( a [i,j,k] ) ;



    پیمایش ستونی :

    for k: =1 to 2 do

    for j: =1 to 3 do

    for i: =1 to 4 do

    write (a[i,j,k]) ;

    مثال : با استفاده از for های تو در تو الگوريتمي بنویسید که 2 ماتریس (2 * 3 * 4) رابا یکدیگر جمع کرده ودر ماتریس سوم قرار دهد:

    پیمایش سطری:

    for i: =1 to 4 do

    for j: =1 to 3 do

    for k: =1 to 2 do

    c [i,j,k] = b [ i,j,k] + a [i,j,k]

    write (c [i,j,k]) ;

  7. #7
    کاربر دائمی آواتار mehdad.koulab
    تاریخ عضویت
    فروردین 1387
    محل زندگی
    تبریز
    پست
    345

    نقل قول: نكاتي در مورد ساختمان داده

    دوستان فايل مربوط به مطالب بالا است البته Office 2007 است convertor PDFام درست كار نكرد خوب حالا اينو داشته باشين تا بعد.
    فایل های ضمیمه فایل های ضمیمه
    • نوع فایل: rar 1.rar‏ (14.3 کیلوبایت, 548 دیدار)

  8. #8
    کاربر دائمی آواتار Daleeeeer
    تاریخ عضویت
    مرداد 1387
    محل زندگی
    پشت هيچستان
    پست
    183

    نقل قول: نكاتي در مورد ساختمان داده

    سلام. دوستم عزیزم درباره آرایه شروع به کار کرد. من هم می خوام براتون امروز در باره پشته و صفها صحبت کنم.
    پشته چیست؟
    پشته به لیست مرتبی گفته می شود که عملیات درج و حذف از اون از یک طرف صورت بگیره. عملکرد اون به صورت LIFO هست. (Last In First Out(. یعنی آخرین عنصر وردی، اولین عنصر خروجی هستش. مثل قرار دادن یک سری بشقاب روی هم دیگه که آخرین بشقاب قرار داده شده، اولین بشقابی هست که می شه اونو برداشت.
    اما مهمترین کاربرد پشته ذخیره آدرس های بازگشت تو برنامه نویسی و ساخت متغیرهای محلی در صدا زدن توابع است. یکی دیگه از کاربرد های مهم پشته اجرای عملیات undo و redo هست که همه باهاش کار کردیم.

  9. #9
    کاربر دائمی آواتار Daleeeeer
    تاریخ عضویت
    مرداد 1387
    محل زندگی
    پشت هيچستان
    پست
    183

    نقل قول: نكاتي در مورد ساختمان داده

    نمایش پشته
    ساده ترین روش برای نمایش پشته استفاده از یک آرایه 1 بعدی به طول n می باشد. در کنار آرایه متغیری به نام top وجود دارد که به عنصر بالایی اشاره دارد. top در ابتدای کار صفر است و از 0 تا n تغییر می کند.
    شرط خالی بودن پشته عبارت است از : if top=0
    شرط پر بودن پشته عبارت است از : if top= n
    زیر برنامه های حذف از پشته (pop) و اضافه کردن به پشته یا نوشتن در آن (push) در زبان C به صورت زیر است:
    void push (item k)
    {
    if (top ==n-1)
    stackfull ();
    else
    ;stack[++top]=k
    }


    items pop()
    }
    if (top==-1)
    stackempty();
    else return stack [top--];
    {

  10. #10
    کاربر دائمی آواتار Daleeeeer
    تاریخ عضویت
    مرداد 1387
    محل زندگی
    پشت هيچستان
    پست
    183

    نقل قول: نكاتي در مورد ساختمان داده

    پشته چندگانه:
    اگر فقط نیاز به دو پشته در برنامه داشته باشیم راه حل ساده است. برای این منظور از یک آرایه n خانه ای استفاده می کنیم. s[1] ابتدای پشته اول و s[n] ابتدای پشته دوم را نشان می دهد و پشته ها به سمت همدیگر می توانند رشد کنند. بدین ترتیب از حافظه موجد به صورت بهینه استفاده می شود.
    ولی اگر بخواهیم بیش از دو پشته داشته باشیم، روش فوق قابل استفاده نیست. در این حال برای نمایش n پشته حافظه s[1..n] را به n قسمت تقسیم می کنیم. تقسیم بندی آرایه ها متناسب با نیازها باشد. در این حالت مقادیر به صورت زیر خواهد بود:
    b[i]=t[i]=[m/n](i-1)+1

    که در آن n تعداد پشته ها و m حد بالای آرایه است.
    مثال: اگر در آرایه s[1..495] بخواهیم 4 پشته به وجود آوریمآدرس ابتدای هرپشته را بدست آورید. اندازه پشته ها یکسان است.

    پاسخ:
    m=495 , m=4
    b[1]=1
    b[2] [495/4](2-1)+1=124
    b[3]= [495/4](3-1)+1=247
    b[4]=[495/4](4-1)+1=370

    در حالت پشته های چندگانه (n>2) ممکن است یکی از پشته ها سریع تر از بقیه پر شود و به همین دلیل استفاده از حافظه بهینه نخواهد بود. برای رفع این مشکل باید عناصر شیفت داده شوند تا در انتهای پشته پشته پر شده فضای خالی تولید شود و این عمل در بدترین حالت o(m) خواهد بود. در پشته های چند گانه (n=2) استفاده از حافظه بهینه است و زمان پردازش نیز از مرتبه o(1) است.

    از همه کسانی که این مطلب رو خوندند می پرسم چرا این مرتبه o(1) است؟ لطفاً جواب رو مکتوب تو سایت قرار بدید!!!!!!!!!
    زیر برنامه های اضافه و حذف از پشته های چند گانه و صف ها رو در پست بعدی قرار می دهم. فعلاً خداحافظ!
    آخرین ویرایش به وسیله Daleeeeer : سه شنبه 15 مرداد 1387 در 20:32 عصر

  11. #11
    کاربر دائمی آواتار Daleeeeer
    تاریخ عضویت
    مرداد 1387
    محل زندگی
    پشت هيچستان
    پست
    183

    نقل قول: نكاتي در مورد ساختمان داده

    زیر برنامه های اضافه کردن و حذف کردن از پشته i ام در پشته های چندگانه:

    procedure pop (i:integer,var k:items);
    begin
    if t[i]=b[i] then stackempty(i)
    else begin
    k:=s[t[i]];
    t[i]:=t[i]-1;
    end;
    end;



    procedure push (i:integer,var k:items);
    begin
    if t[i]=b[i+1] then stackfull(i)
    else begin
    k:=t[i]+1;
    s[t[i]]:=k;
    end;
    end;

  12. #12
    کاربر دائمی آواتار Daleeeeer
    تاریخ عضویت
    مرداد 1387
    محل زندگی
    پشت هيچستان
    پست
    183

    نقل قول: نكاتي در مورد ساختمان داده

    صف (queue):

    صف لیست مرتبی است که عمل اضافه کردن (نوشتن) از یک طرف آن به نام انتهای صف (rear) و عمل خواندن (حذف کردن) از طرف دیگر صف به نام ابتدای صف (Front) می شود. ساختار صف به صورت FIFO است. (First In First Out). یکی از کاربردهای مهم صف در زمانبدی برنامه ها در سیستم عامل هستش. ساده ترین راه نمایش صف استفاده از یک آرایه یک بعدی به طول n می باشد.
    برای کار با صف معمولی به دو اشاره گر نیاز داریم: یکی Front که همیشه به یک عنصر قبل از عنصر ابتدایی اشاره می کنه و rear که همیشه به آخرین عنصر اشاره داره.
    دامنه تغییرات front و rear از 0 تا n هست و مقادیر اولیه اونها 0 قرار می گیره.
    شرط خال بودن صف عبارت است از :
    if front = rear
    و شرط پر بودن صف عبارت است از :
    if rear = n

  13. #13
    کاربر دائمی آواتار Daleeeeer
    تاریخ عضویت
    مرداد 1387
    محل زندگی
    پشت هيچستان
    پست
    183

    نقل قول: نكاتي در مورد ساختمان داده

    زیر برنامه های اضافه کردن و حذف کردن از پشته i ام در پشته های چندگانه:


    void addq(items k)
    {
    if (rear==n-1)
    queufull();
    else
    q[++rear]=k;
    }




    void delq()
    {
    if (front==rear)
    queuempty();
    else
    reaturn q[++front];
    }


    مشکل اصلی صف ها در این است که صف در یک لحظه می تونه پر و خالی (همزمان) باشه. مثلاً اگر n=5 داده را در یک صف 5 خانه ای ریخته و سپس آنها را بخوانیم در حالتی که r=f=5 داریم:
    صف خالی است چون: r=f
    صف پر است چون: r=n=5
    آخرین ویرایش به وسیله Daleeeeer : سه شنبه 15 مرداد 1387 در 20:31 عصر

  14. #14
    کاربر دائمی آواتار Daleeeeer
    تاریخ عضویت
    مرداد 1387
    محل زندگی
    پشت هيچستان
    پست
    183

    نقل قول: نكاتي در مورد ساختمان داده

    صف حلقوی:
    صف حلقوی همون صف ساده است ولی با این تفاوت که مشکل فوق رو نداره. تمام مقادیر اون با صف ساده یکسان هست مگر شرط پر بودن آن که به شکل زیر هست:
    if Front=(Rear+1) mod n
    زیر برنامه های حذف و اضافه کرن به صف حلقوی عبارتند از:

    void delq()
    {
    if (front==rear)
    queuempty();
    else {
    front=(front+1)%n;
    reaturn q[front];
    }




    void addq(items k)
    {
    if (front==(rear+1)%n)
    queufull();
    else {
    rear=(rear+1)%n;
    q[rear]=k;
    }



    در صف حلقوی در هر لحظه حداکثر n-1 عنصر وجود داره و بدین ترتیب می توان بین حالت پر و خالی تمایز قائل شد.

  15. #15
    کاربر دائمی آواتار Daleeeeer
    تاریخ عضویت
    مرداد 1387
    محل زندگی
    پشت هيچستان
    پست
    183

    نقل قول: نكاتي در مورد ساختمان داده

    دوباره سلام. امروز می خوام درباره لیست های پیوندی شروع به کار کنم.

    مفهوم لیست پیوندی:
    غالباً برای ذخیره تعداد زیادی داده ها از آرایه استفاده می کنند. ولی به دلیل ایستا بودن ساختار آرایه و محدودیت کار با آن از ساختار دیگه ای استفاده می شه به نام linked list یا همون لیست پیوندی.
    عناصر لیست پیوندی از نوع پویا بوده و عناصر اون الزاماً در کنارهم نمی باشند. (بر عکس آرایه) . به همین دلیل اعمال درج و حذف در اون به راحتی و سریعتر از آرایه است. در مقابل برخی از اعمال مثل جستجو یا مرتب سازی در آرایه سریع تر از لیست پیوندی است.
    هر عنصر یا گره (node) حداقل از دو فیلد داده (Data)و اشاره گری به گره بعدی (Link) تشکیل شده است.
    آخرین ویرایش به وسیله Daleeeeer : چهارشنبه 16 مرداد 1387 در 09:50 صبح

  16. #16
    کاربر دائمی آواتار Daleeeeer
    تاریخ عضویت
    مرداد 1387
    محل زندگی
    پشت هيچستان
    پست
    183

    نقل قول: نكاتي در مورد ساختمان داده

    فرم کلی گره ها در زبان c:

    typedef struct NODE *p_node;
    typedef struct NODE{
    char name[21];
    int num;
    p_node link;
    }

    ایجاد زنجیر و دستیابی به فیلدها:

    در تکه کد زیر مفهوم زنجیر و طرز ایجاد آنرا بیان می کنیم:

    var
    x,y,z:p_node;
    begin
    new(x);
    x^.name:='ali';
    x^.num:=123;
    x^link:=nil;

    z:=x;

    new (y);
    y^.name:='mohsen';
    y^.num:=456;
    y^link:=nil;
    x^.link=y;
    end.

    با دستور new می توان یک نود جدید را در زنجیر ساخت.
    در انتهای برنامه دو نود داریم . نود اول با نام ali و نود دوم با نام mohsen.
    لیست ها را از 3 من ظر می توان تقسیم کرد:
    1- یا یکطرفه هستند یا دو طرفه.
    2- یا خطی هستند یا حلقوی.
    3- یا بدون Head هستند یا Head دارند.
    در قسمت بعدی آنها را توضیح خواهیم داد.

  17. #17
    کاربر دائمی آواتار mehdad.koulab
    تاریخ عضویت
    فروردین 1387
    محل زندگی
    تبریز
    پست
    345

    نقل قول: نكاتي در مورد ساختمان داده

    سلام به دوستان و با تشكر از دوستم Daleeeeer
    ادامه مبحث
    انواع ليست پيوندي
    1)ليست پيوندي يك طرفه خطي
    2)ليست پيوندي يك طرفه حلقوي
    3)ليست پيوندي دوطرفه خطي
    4) ليست پيوندي دوطرفه حلقوي

  18. #18
    کاربر دائمی آواتار mehdad.koulab
    تاریخ عضویت
    فروردین 1387
    محل زندگی
    تبریز
    پست
    345

    نقل قول: نكاتي در مورد ساختمان داده

    هر لیست پیوندی با اشاره گر سر لیست مشخص می شود که معمولا آن رابا (First) یا (Head) مشخص می کنند .(First) یا (Head) اشاره گری است که آدرس گره اول لیست پیوندی را مشخص می کند ، همچنین آخرین گره از لیست پیوندی بخش اشاره گرش (Link) مقدار تهی خواهد داشت که در زبان پاسکال با (Nil) ودر زبان C با (Null) مشخص می شود. (شكل 1 رو ببينيد بزرگه)
    به مثال زير توجه كنيد.( شكل 2 رو ببينيد كوچيكه)

    Data (X) = ? (70)
    Link (X) = ? (Y)
    Data ( Link (x) ) = ? (60)
    Link ( Link (w) ) = ? (Y)
    Link (Z) = ? (Null)
    Data ( First ) = ? (50)
    Link ( First ) = ? (X)
    Link ( Data (y) ) = ? (بی معنی)
    عکس های ضمیمه عکس های ضمیمه   
    آخرین ویرایش به وسیله mehdad.koulab : جمعه 25 مرداد 1387 در 11:37 صبح

  19. #19

    Smile نقل قول: نكاتي در مورد ساختمان داده

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

  20. #20
    VIP آواتار xxxxx_xxxxx
    تاریخ عضویت
    شهریور 1386
    محل زندگی
    X place
    سن
    29
    پست
    4,767

    نقل قول: نكاتي در مورد ساختمان داده

    براي دوستاني كه مي خوان همزمان با پيشروي تاپيك مطالعاتي هم داشته باشند، يه سري اسلايد اينجا قرار ميدم.

    DS-1: مبناها
    DS-2: آرايه - مرتب سازي - جستجو
    DS-3: پشته و صف و كاربرد آنها
    DS-4: ليست پيوندي و انواع آن
    DS-5: درخت و گراف و كاربرد آنها
    فایل های ضمیمه فایل های ضمیمه
    الگوریتم هایی که تاریخچه خود را فراموش می کنند، محکوم به تکرار آن هستند.

  21. #21
    کاربر تازه وارد آواتار mrshcom
    تاریخ عضویت
    شهریور 1388
    محل زندگی
    مشهد
    پست
    42

    Thumbs up نقل قول: نكاتي در مورد ساختمان داده

    این یک کد ایجاد ایستک با استفاده از کلاسه به زبان سی پلاسه امیدوارم مفید باشه
    فایل های ضمیمه فایل های ضمیمه

  22. #22

    نقل قول: نكاتي در مورد ساختمان داده

    شروع خيلي خوبيه
    از دوست خوبم Daleeeeer ميخوام در مورد پشته هاي چندگانه بيشتر توضيح بده ما تو ساختمان داده همون يگانه شو خونديم كاربردشون چيه؟ و پياده سازي؟
    در مورد پشته همونطور كه ميدونيد استفاده از ارايه انعطاف پذيري چنداني نداره و به لحاظ حافظه بهينه نيست اينجاست كه سر و كله ي ليست پيوندي مياد وسط
    البته بعضي وقتها ارايه بهتره. بستگي به مساله داره.
    فایل های ضمیمه فایل های ضمیمه

  23. #23
    کاربر دائمی آواتار میلاد قاضی پور
    تاریخ عضویت
    بهمن 1388
    محل زندگی
    اوج بلند
    پست
    768

    نقل قول: نكاتي در مورد ساختمان داده

    البته دارای اشکالات املایی و دستوری بسیار زیادی هست ولی به دردتون میخوره

  24. #24

    نقل قول: نكاتي در مورد ساختمان داده

    نقل قول نوشته شده توسط mehdad.koulab مشاهده تاپیک
    سلام
    چند وقتي بود ميخواستم يه تاپيك در مورد ساختمان داده بزنم و مطالب مفيد مربوط به ساختمان داده رو با كمك دوستان تو اون جمع كنيم تا يه تاپيك جالبي به وجود بياد. من خودم كه چيز زيادي بلد نيستم فقط الگوريتمها و ... تو دانشگاه گفتن رو بلدم كه اونارو هم يكي يكي ميذارم.
    از دوستان خواهش ميكنم اگه مطلبي دارن كه مفيد ميتونه باشه دريغ نكنند. با تشكر
    سلام عزیزم میشه در مورد این قطعه کد توضیح بدین که چکار میکنه؟
    void hanoi ( int nDisk, char start, char temp, char finish )

    {

    if ( nDisk == 1 )

    cout << start << " --> " << finish << endl;

    else

    {

    hanoi ( nDisk - 1, start, finish, temp );

    cout << start << " --> " << finish << endl;

    hanoi ( nDisk - 1, temp, start, finish );

    }

    }
    اگه کمک کنید اندازه 1دنیا ممنون میشم
    شاد و پیروز باشید

  25. #25

    نقل قول: نكاتي در مورد ساختمان داده

    نقل قول نوشته شده توسط mehdad.koulab مشاهده تاپیک
    سلام
    چند وقتي بود ميخواستم يه تاپيك در مورد ساختمان داده بزنم و مطالب مفيد مربوط به ساختمان داده رو با كمك دوستان تو اون جمع كنيم تا يه تاپيك جالبي به وجود بياد. من خودم كه چيز زيادي بلد نيستم فقط الگوريتمها و ... تو دانشگاه گفتن رو بلدم كه اونارو هم يكي يكي ميذارم.
    از دوستان خواهش ميكنم اگه مطلبي دارن كه مفيد ميتونه باشه دريغ نكنند. با تشكر
    سلام دوست عزیز
    میشه لطفا در مورد پیچیدگی الگوریتم یه چند تا مثال سخت اینجا مطرح کنید.(البته اگه خواستید با جواب)

  26. #26

    نقل قول: نكاتي در مورد ساختمان داده

    نقل قول نوشته شده توسط samir_1991 مشاهده تاپیک
    سلام عزیزم میشه در مورد این قطعه کد توضیح بدین که چکار میکنه؟
    void hanoi ( int nDisk, char start, char temp, char finish )

    {

    if ( nDisk == 1 )

    cout << start << " --> " << finish << endl;

    else

    {

    hanoi ( nDisk - 1, start, finish, temp );

    cout << start << " --> " << finish << endl;

    hanoi ( nDisk - 1, temp, start, finish );

    }

    }
    اگه کمک کنید اندازه 1دنیا ممنون میشم
    شاد و پیروز باشید
    سلام samir
    این کد مربوط به برج هانوی هس.
    اگه یه دیسک داشته باشیم اونو از میله ی استارت به پایان میبریم.
    و اگه بیشتر باشه، مثلا n تا، اول n-1 رو باید منتقل کنیم که نیاز به فراخوانی همین تابع داره فقط باید جای میله ها برای این فراخوانی تغییر کنه.
    بعد از اون باید n امین مهره(بزرگترین مهره)رو از استارت به پایان ببریم .
    دوباره اون n-1 مهره رو با فراخوانی مجدد همین تابع منتقل میکنیم.

  27. جمعه 19 آذر 1389, 19:29 عصر

    دلیل
    درخواست انجام تمرین دانشجویی

  28. جمعه 19 آذر 1389, 19:32 عصر

    دلیل
    درخواست انجام تمرین دانشجویی

  29. چهارشنبه 20 بهمن 1389, 21:15 عصر


  30. چهارشنبه 20 بهمن 1389, 23:42 عصر


  31. چهارشنبه 20 بهمن 1389, 23:45 عصر


  32. شنبه 24 اردیبهشت 1390, 10:19 صبح


  33. دوشنبه 27 تیر 1390, 17:55 عصر


  34. دوشنبه 03 مرداد 1390, 13:25 عصر


  35. شنبه 24 تیر 1391, 00:25 صبح


  36. شنبه 24 تیر 1391, 00:28 صبح


  37. چهارشنبه 10 آبان 1391, 16:46 عصر


  38. جمعه 03 آذر 1391, 11:36 صبح


  39. #27
    کاربر تازه وارد آواتار amin.m1993
    تاریخ عضویت
    بهمن 1390
    محل زندگی
    select city from iran
    پست
    61

    نقل قول: نكاتي در مورد ساختمان داده

    سلام .
    امروز میخوام براتون پیاده سازی اسپارس رو توضیح بدم.
    اول از همه باید بدونید ماتریس اسپارس ماتریسی است که اکثر cell های اون یک مقدار ثابت (که ما میگیم صفر) بوده و بقیه ی عناصر غیر صفرند(که اینها رو استثنا میگیم).

    الگوریتمی که ما ازش استفاده میکنیم اینه که یه آرایه ی دو بعدی به صورت 3*(tedadestesna+1) تعریف میکنیم و سطر 0 ام این آرایه رو با مشخصات ماتریس اسپارسمون پر میکنیم(جلوتر با کد کامل توضیح میدم).

    با این مقدمه میریم سر پیاده سازی.
    ابتدا یک کلاس با اسم Espars می سازیم , یک متغیر از نوع int که تعداد استثنا ها رو در خودش نگه میداره (حالتهایی که غیر صفرند) و بعد یه اشاره گر به صورت زیر:
    int **value;


    در این قسمت سازنده ی کلاس رو تعریف میکنیم:
    Espars(int TedadEstesna,int Satr,int Sotun,int MeghdarKolli) 
    {
    tedadEstesna=TedadEstesna;
    value=new int*[tedadEstesna+1];
    for(int i=0;i<tedadEstesna+1;i++)
    {
    value[i]=new int[3];
    }
    value[0][0]=Satr;
    value[0][1]=Sotun;
    value[0][2]=MeghdarKolli;
    }

    سازنده تعداد کل حالتهای استثنا رو میگشره و اونو تو متغیر داخل کلاس (tedadEstesna) میزاره.
    بعد همون طور که گفتم آرایه پویا دو بعدی تعریف میکنه (tedadEstesna+1)*3)) و بعدش سطر 0 ام رو با مشخصات ماتریس مقداردهی میکنه .منظور از meghdarkolli همون صفره.الان ما یه آرایه دو بعدی داریم و مقادیر (حالتهای استثنا) رو از سطر 1 هم به بعد توش قرار خواهیم داد.(طبق قرارداد !)

    یه تابع هم برای دریافت مقادیر ماترسی مینویسیم به صورت زیر:
    void Daryaft() 
    {
    for(int i=1;i<tedadEstesna+1;i++)
    {
    cout<<i<<")\nSatr: ";
    cin>>value[i][0];
    cout<<"Sotun: ";
    cin>>value[i][1];
    cout<<"Meghdar: ";
    cin>>value[i][2];
    cout<<"\n";
    }
    }

    حالا نوبت میرسه به جمع دو ماتریس اسپارس که من اول کدشو قرار میدم و بعد توضیح میدم:
    Espars operator +(Espars b) 
    {
    if(value[0][0]!=b.value[0][0] || value[0][1]!=b.value[0][1])
    {
    cout<<"in 2 matris daraye satr va sotune barabar nistand";
    return *new Espars(0,0,0,0);
    }
    int tekrari=0;
    for(int i=1;i<tedadEstesna+1;i++)
    {
    for(int j=0;j<b.tedadEstesna+1;j++)
    {
    if(value[i][0]==b.value[j][0] && value[i][1]==b.value[j][1])
    {
    tekrari++;
    break;
    }
    }
    }
    Espars sum=Espars(tedadEstesna+b.tedadEstesna-tekrari,value[0][0],value[0][1],value[0][2]+b.value[0][2]);
    int index;
    for(index=1;index<tedadEstesna+1;index++)
    {
    sum.value[index][0]=value[index][0];
    sum.value[index][1]=value[index][1];
    sum.value[index][2]=value[index][2];
    }
    for(int i=1;i<b.tedadEstesna+1;i++)
    {
    int j=0;
    for(j=1;j<tedadEstesna+1;j++)
    {
    if(b.value[i][0]==sum.value[j][0] && b.value[i][1]==sum.value[j][1])
    {
    sum.value[j][2]=value[j][2]+b.value[i][2];
    break;
    }
    }
    if(j==tedadEstesna+1)
    {
    sum.value[index][0]=b.value[i][0];
    sum.value[index][1]=b.value[i][1];
    sum.value[index++][2]=b.value[i][2];
    }
    }
    return sum;
    }


    خوب و اما توضیح:
    در اینجا باید از طریق همون مشخصات ماتریس (سطر 0 ام) باید بررسی بشه که آیا دو ماترسی میتونند با هم جمع بشد یا نه:
    if(value[0][0]!=b.value[0][0] || value[0][1]!=b.value[0][1]) 
    {
    cout<<"in 2 matris daraye satr va sotune barabar nistand";
    return *new Espars(0,0,0,0);
    }


    حالا باید حالتهای تکراری رو حذف کنیم.منظور از حالتهای تکراری اینه که سطر و ستون یه فیلد از هر دو ماتریس برابر باشند که باید در ماتریس جدید اونا رو جمع کنیم:
    int tekrari=0; 
    for(int i=1;i<tedadEstesna+1;i++)
    {
    for(int j=0;j<b.tedadEstesna+1;j++)
    {
    if(value[i][0]==b.value[j][0] && value[i][1]==b.value[j][1])
    {
    tekrari++;
    break;
    }
    }
    }

    حالا یه ماترس اسپارس جدید ایجاد میکنیم به تعداد مجموع استثناهای دو ماتریس اول منهای تعداد تکراری که در قسمت قبل پیدا کریم بعدش ماترسی اول رو همون طور که هست در ماترس جدید جایگذاری میکنیم:
    Espars sum=Espars(tedadEstesna+b.tedadEstesna-tekrari,value[0][0],value[0][1],value[0][2]+b.value[0][2]); 
    int index;
    for(index=1;index<tedadEstesna+1;index++)
    {
    sum.value[index][0]=value[index][0];
    sum.value[index][1]=value[index][1];
    sum.value[index][2]=value[index][2];
    }


    در قسمت بعد هم که بررسی میکنیم اگه تکراری باشه جمع کن اگه نباشه ماتریس b رو هم بزار داخل sum.

    ترانهاده اش هم که جاس سطر و ستون عوض میشه و خیلی راحته:
    Espars Taranahadeh() 
    {
    Espars taranahadeh=*new Espars(tedadEstesna,value[0][1],value[0][0],value[0][2]);
    for(int i=1;i<tedadEstesna+1;i++)
    {
    taranahadeh.value[i][0]=value[i][1];
    taranahadeh.value[i][1]=value[i][0];
    taranahadeh.value[i][2]=value[i][2];
    }
    return taranahadeh;
    }


    در آخر خود برنامه رو هم قرار میدم تا استفاه کنید.
    http://barnamenevis.org/attachment.p...6&d=1357368970

    خوب دوستان موفق باشید .
    یا حق.

  40. #28
    کاربر تازه وارد آواتار amin.m1993
    تاریخ عضویت
    بهمن 1390
    محل زندگی
    select city from iran
    پست
    61

    نقل قول: نكاتي در مورد ساختمان داده

    با سلام امروز میخوام الگوریتم های مرتب سازی رو براتون بزارم.
    البته توضیح در مورد این الگوریتمها از لحاظ شرعی و عرفی جایز نیست چون واقعا راحتند ولی به هر حال اگه بازم مشکلی بود مطرح کنید.


    الگوریتم مرتب سازی سریع(Quick Sort):
    public void QuickSort(int[] arr, int low, int high)
    {
    if (high > low)
    {
    int pivotIndex = Partition(arr, low, high);
    QuickSort(arr, low, pivotIndex - 1);
    QuickSort(arr, pivotIndex + 1, high);
    }

    }

    public int Partition(int[] arr, int low, int high)
    {

    int pivotIndex = low;
    int pivotItem = arr[pivotIndex];


    // print
    Console.WriteLine("\nPivot Item={0}\nBefore:", pivotItem);
    for (int t = low; t <= high; t++)
    {
    Console.Write(" {0} ", arr[t]);
    }
    Console.WriteLine();


    int temp;
    for (int i = low + 1; i <= high; i++)
    {
    if (pivotItem > arr[i])
    {
    pivotIndex++;
    temp = arr[i];
    arr[i] = arr[pivotIndex];
    arr[pivotIndex] = temp;
    }
    }

    temp = arr[pivotIndex];
    arr[pivotIndex] = arr[low];
    arr[low] = temp;

    // print
    Console.WriteLine("After");
    for (int t = low; t <= high; t++)
    {
    Console.Write(" {0} ", arr[t]);
    }
    Console.WriteLine();

    return pivotIndex;
    }
    }


    الگوریتم مرتب سازی ادغامی(merge sort):
    public void MergeSort(int arraySize, int[] arr)
    {
    int size1 = arraySize / 2;
    int size2 = arraySize - size1;

    int[] array1 = new int[size1];
    int[] array2 = new int[size2];

    // copy
    for (int i = 0; i < size1; i++)
    {
    array1[i] = arr[i];
    }
    for (int i = size1; i < arraySize; i++)
    {
    array2[i - size1] = arr[i];
    }

    if (arraySize > 1)
    {
    MergeSort(size1, array1);
    MergeSort(size2, array2);
    Merge(size1, size2, array1, array2, arr);
    }
    }

    public void Merge(int arraySize1, int arraySize2, int[] array1, int[] array2, int[] arr)
    {
    int i = 0,j = 0;

    int k = 0;


    //print
    Console.WriteLine("\nBefore Merge:");
    for (int t = 0; t < arraySize1; t++)
    {
    Console.Write(" {0} ", array1[t]);
    }
    Console.Write(" ***** ");
    for (int t = 0; t < arraySize2; t++)
    {
    Console.Write(" {0} ", array2[t]);
    }


    //sort
    while (i < arraySize1 & j < arraySize2)
    {
    if (array1[i] <= array2[j])
    {
    arr[k] = array1[i];
    i++;
    }
    else
    {
    arr[k] = array2[j];
    j++;
    }
    k++;
    }

    if (i == arraySize1)
    {
    while (j < arraySize2)
    {
    arr[k] = array2[j];
    j++;
    k++;
    }
    }
    if (j == arraySize2)
    {
    while (i < arraySize1)
    {
    arr[k] = array1[i];
    i++;
    k++;
    }
    }

    // print merged array
    Console.WriteLine("\nMerged:");
    for (int t = 0; t < arr.Length; t++)
    {
    Console.Write(" {0} ", arr[t]);
    }
    }


    مرتب سازی تعویضی(Exchange sort):
    public int[] ExchangeSort(int[] arr)
    {
    int temp;

    for (int i = 0; i < arr.Length - 1; i++)
    {
    // Sort
    for (int j = i + 1; j < arr.Length; j++)
    {
    if (arr[i] > arr[j])
    {
    temp = arr[j];
    arr[j] = arr[i];
    arr[i] = temp;
    }
    }
    // Show result
    for (int k = 0; k < arr.Length; k++)
    {
    Console.Write(" {0} ", arr[k]);
    }
    Console.WriteLine();
    }

    return arr;
    }

    و در نهایت مرنب سازی حبابی:
    static void bubble_sort2(int [] arr,int n)

    {
    for(int i=n-1;i>0;i--)
    {
    int c = 0;
    for(int j=0;j<i ;j++)
    {
    if (arr[j]>arr[j + 1])
    {
    int t = arr [j];
    arr [j] = arr [j + 1];
    arr [j + 1] = t;
    C++‎;
    }
    }
    if (c == 0) break; //baraye behine kardane algorithm.agar nabashad ham dorost kar khahad kard.
    }
    }


    موفق باشید یا حق.

  41. #29

    نقل قول: نكاتي در مورد ساختمان داده

    پیمایش inorder - preorder - postorder : BST


    ابتدا یک کلاس به نام treenode طراحی میکنیم که ساختار گره های درخت را برایمان پیاده میکند :

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    namespace test_BST
    {
    class TreeNode
    {
    int data;
    TreeNode left;
    TreeNode right;
    public TreeNode()
    {
    data = 0;
    left = right = null;
    }
    public TreeNode(int value)
    {
    data = value;
    }
    public int Data
    {
    get { return data; }
    set { data = value; }
    }
    public TreeNode Left
    {
    get { return left; }
    set { left = value; }
    }
    public TreeNode Right
    {
    get { return right; }
    set { right = value; }
    }
    public void Display()
    {
    Console.WriteLine(" {0} ", data);
    }
    }
    }


    فرض میکنیم مقدار ذخیره شده در گره ها عدد صحیح باشد یک فیلد از نوع عدد صحیح برای ذخیره اعداد به نام data , فیلد های left و right که اشاره به زیر درخت ها دارند و متد display که محتوای گره را نشان می دهد

    حالا کلاس bst را پیاده سازی میکنیم که دارای یک فیلد به نام root که به ریشه درخت اشاره می کند. متد insert عمل درج در گره را بر عهده دارد :

    3 پیمایش inorder ( زیر درخت چپ - گره - زیر درخت راست ) preorder ( گره - زیر درخت چپ - زیر درخت راست ) postorder ( زیر درخت چپ - زیر درخت راست - گره ) " از راست به چپ عمل میکند " را پیاده سازی مکنیم

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    namespace test_BST
    {
    class BST
    {
    public TreeNode root;
    public BST()
    {
    root = null;
    }
    public void Insert(int data)
    {
    TreeNode _node = new TreeNode(data);
    TreeNode current = root;
    if (root==null)
    {
    root = _node;
    }
    else
    {
    while (true)
    {
    if (_node.Data > current.Data)
    {
    if (current.Right != null)
    {
    current = current.Right;
    }
    else
    {
    current.Right = _node;
    break;
    }
    }
    else
    {
    if (current.Left!=null)
    {
    current = current.Left;
    }
    else
    {
    current.Left = _node;
    break;
    }
    }
    }
    }
    }
    public void Inorder(TreeNode root)
    {
    if (root!=null)
    {
    Inorder(root.Left);
    root.Display();
    Inorder(root.Right);
    }
    }
    public void Preorder(TreeNode root)
    {
    if (root!=null)
    {
    root.Display();
    Preorder(root.Left);
    Preorder(root.Right);
    }
    }
    public void Postorder(TreeNode root)
    {
    if (root!=null)
    {
    Postorder(root.Left);
    Postorder(root.Right);
    root.Display();
    }
    }
    }
    }


    در قسمت main برنامه ابتدا یک ارایه از اعداد صحیح در نظر گرفته و بوسیله ی کلاس bst ، متد های پیمایش درخت دودویی جستجو را فرا میخوانیم

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    namespace test_BST
    {
    class Program
    {
    static void Main(string[] args)
    {
    int[] nums = { 12,45,32,87,52,16,37,23 };
    BST b = new BST();
    foreach (int item in nums)
    {
    b.Insert(item);
    }
    Console.WriteLine("Inorder traversal :");
    b.Inorder(b.root);
    Console.WriteLine("Preorder traversal :");
    b.Preorder(b.root);
    Console.WriteLine("Postorder traversal :");
    b.Postorder(b.root);
    Console.ReadKey();
    }
    }
    }


    برنامه :


    فایل های ضمیمه فایل های ضمیمه

  42. یک شنبه 15 اردیبهشت 1392, 19:45 عصر

    دلیل
    پروژه دانشجویی

  43. یک شنبه 15 اردیبهشت 1392, 19:59 عصر

    دلیل
    پروژه دانشجویی

  44. یک شنبه 15 اردیبهشت 1392, 21:20 عصر

    دلیل
    پروژه دانشجویی

  45. #30

    نقل قول: نكاتي در مورد ساختمان داده

    سلام. دوستان در خواست داشتم position را توضیح دهید و در صورت امکان مثال هایی برای heap و position و iterator به همراه کدشون قرار بدین. مثال ها لازم نیست خیلی پیچیده باشن در همین حد که کاربرد مفاهیم مشخص بشه کافیه.

  46. #31

    نقل قول: نكاتي در مورد ساختمان داده

    کامپیوتر در هر ثانیه 10 دستتور انجام میدهد و کامپیوتر دیگری در هر ثانیه 21 دستور انجام میدهد/کامپیوتر دوم چند
    برابر سریعتر از کامپیوتر اول هست؟

  47. #32

    نقل قول: نكاتي در مورد ساختمان داده

    نقل قول نوشته شده توسط navidmohammadi85 مشاهده تاپیک
    کامپیوتر در هر ثانیه 10 دستتور انجام میدهد و کامپیوتر دیگری در هر ثانیه 21 دستور انجام میدهد/کامپیوتر دوم چند
    برابر سریعتر از کامپیوتر اول هست؟
    1.1 برابر!!!!

  48. یک شنبه 27 اردیبهشت 1394, 00:27 صبح

    دلیل
    نقض قوانین

  49. چهارشنبه 03 تیر 1394, 10:10 صبح

    دلیل
    تبلیغات

برچسب های این تاپیک

قوانین ایجاد تاپیک در تالار

  • شما نمی توانید تاپیک جدید ایجاد کنید
  • شما نمی توانید به تاپیک ها پاسخ دهید
  • شما نمی توانید ضمیمه ارسال کنید
  • شما نمی توانید پاسخ هایتان را ویرایش کنید
  •