hcoolh
دوشنبه 27 آبان 1387, 00:38 صبح
سلام. من حسین هستم و اینم اولین پست من هست..امیدوارم به درد بخوره..
--مقدمه:
خيلی وقتا پيش مياد که می خوايم يه آرايه دو بعدی با اندازه ی دلخواه و غير ثابت در زمان اجرا(runtime) ايجاد کنيم. یعنی یه آرایه دوبعدی پویا!
خوب روشی که معمولاًً استفاده ميشه اينه که يه آرايه ی يک بعدی تعريف مي کنيم و اونو به صورت دو بعدی آدرس دهی ميکنيم .مثلاً برای مثال بالا مينويسيم:
int *d1Test=new int[nRow*nCol*sizeof(int)]; // in c++
يا اينکه :
int *d1Test=(int *)malloc(nRow*nCol*sizeof(int)); // in c
و بعد برای دسترسی به خانه های اين آرايه به صورت دو بعدی ، از عملگر* استفاده مي کنيم يعنی در حالت کلی برای دسترسی به خانه ی ij ام از آرايه d1Testمينويسيم (d1Test+i*nCol+j)* که i*nCol+j آفست-آدرس از ديد دو بعدی هست که با آدرس base جمع ميشه تا به آدرس واقعی اون خانه اشاره کنه.
ولی اگه به صورت ایستا دو بعدی تعريف می کردیم (يعنی مثلاً int sTest[4][5] ) برای منظور بالا مينوشتيم sTest[i][j]
حالا اگه بخوايم يه آرايه دو بعدی به صورت پويا تعريف کنيم که دسترسی به اون به صورت d1Test[i][j]باشه بايد چه کار کنيم؟!
--راه حل:
خوب ما ميخواهيم يک آرايه با nRow سطر و nCol ستون داشته باشيم، کاری که انجام ميديم اينه که nRow اشاره گر تعريف ميکنيم که هر کدام به ابتدای يه آرايه به اندازه nCol اشاره کنه، ولی چون که nRow ثابت نيست پس آرايه اي که اين nRow اشاره گر را نگه شون ميداره بايد خودشم اشاره گر باشه (برای پويا بودن)، حتماً متوجه شدين که ما در واقع يه اشاره گر به اشاره گر ميخوايم!
حالا مرحله به مرحله اين کار رو انجام ميديم..اول يه اشاره گر به اشاره گر تعريف ميکنيم:
int **d2Test;
خوب d2Test بايد در مرحله اول به يه آرايه از nRow اشاره گر اشاره کنه، يعنی:
d2Test=(int **)malloc(nRow*sizeof(int *));
دقت کنيد که مينويسيم sizeof(int *)چون ما داريم يه آرايه تعريف ميکنيم که تعدادی اشاره گر رو در خودش نگه ميداره. حالا d2Test[i] به ازای i=0 تا i=nRow-1 يه اشاره گر هست که فعلاً به جايی اشاره نميکنه.پس در مرحله دوم بايد کاری کنيم که هر کدام از اين d2Test[i]ها به يه آرايه nCol تايی اشاره کنه يعنی nCol خانه برای هر کدام تخصيص حافظه کنيم،پس داريم:
for(int c=0 ; c<nRow ; c++)
d2Test[i]=(int *)malloc(nCol * sizeof(int));
اگر همه memory allocation ها بدون خطا انجام شده باشه،آرايه آماده هست.
الان برای اينکه به خانه ی ij ام دسترسی پيدا کنيم خیلی راحت مينويسيم d2Test[i][j] دقيقاً مانند دسترسی به يک آرايه دو بعدی که ایستا تعريف شده. ولی يه فرق اساسی بين اونا وجود داره که حتماً تا الان متوجه ی اون شدين..تفاوتی که هست اينه که sTest[i][j] به هيچ وجه مثل d2Test[i][j] کامپايل نميشه، در واقع sTest[i][j] به صورت (sTest + i*nCol + j)* ترجمه ميشه در حالی که d2Test[i][j] به صورت *(*(d2Test+i)+j) ترجمه ميشه!!
و اين وظيفه کامپايلر هست که اين دو وضعيت رو از هم تشخيص بده.
--نقد و بررسی:
1.روش ايستا:
در زمان ايجاد بايد ابعاد آرایه ثابت (fixed) باشه(ایستا). اندازش هم محدود هست، که به کامپايلر و سيستم عامل و در صورت محلی بودن به اندازه پشته بستگی داره.
طريقه استفاده از اونا يعنی همون ظاهرشون توی برنامه واضح و ساده هست (sTest[i][j])
2.روش پويا يک بعدی:
در زمان ايجاد ابعادش ميتونه متغير باشه(پويا). اندازش تقریبا فقط به اندازه حافظه موجود بستگی داره.
زمان دسترسی به یک عنصر دقيقاً برابر حالت ايستا هست مگر اينکه آدرس دسترسی ثابت باشه. مثلاً (d1Test +4*nCol + 5)* چون در اين صورت برای حالت ايستا محاسبه ی آدرس عنصر در زمان کامپايل انجام ميشه.
طريقه استفادش تو برنامه به دليل شکل نامتعارف برای تازه کارها کمی دشوار هست.
3.روش پويا دو بعدی:
در زمان ايجاد، ابعادش ميتونه متغير باشه(پويا). تو این روش مدت زمان ايجاد صفر نيست یعنی چون برای ایجاد آرایه nRow+1بار عمل تخصیص حافظه رو انجام میدیم ایجادش به کمی زمان و پردازش اضافی نیاز داره(در حدود میلی ثانیه) .
اندازه اش مثل حالت پویای یک بعدی هست.
زمان دسترسی به یک عنصر اون از دو حالت قبل سريعتره؛ چون در دو حالت قبل برای محاسبه آدرس عنصر در حافظه یه ضرب و یه جمع انجام ميشد، ولی تو این حالت فقط 2 بار به صورت متوالی عمل qualification انجام ميشه.
پس اين روش دو تا مشکل داره : اول اينکه برای ايجادش باید چند خط کد بنویسیم(کی حال داره!) و دومیش اينکه ايجادش زمان می بره.خوب مشکل اول که با نوشتن يه تابع که اينکارو برای ما انجام بده تقريباً حل ميشه. ولی آيا ميتونیم از یه تعداد کمتری عمل تخصیص حافظه استفاده کنیم؟
جواب مثبته. برای اينکار ميتونيم مثل قبل تو مرحله اول يه آرايه nRow تايی از اشاره گر ها بگيريم،
ولی تو مرحله بعدی به جای اينکه nRow بار يه آرايه nCol تايی بگيريم، يه بار يه آرايه nCol*nRow تايی می گيريم
و بعد با يه حلقه اونو با فواصل nCol تايی به اشاره گر ها اختصاص میديم:
مرحله اول:
int **d2Test;
d2Test=(int **)malloc(nRow*sizeof(int *));
مرحله دوم:
Ed2Test[0]=(int *)malloc(nRow*nCol*sizeof(int));
For(int c=1 ; c<nRow ; c++)
Ed2Test[c]=Ed2Test[c-1]+nCol; //ya inke Ed2Test[c]=Ed2Test[0]+c*nCol;
خوب حالا ميتونيم يه تابع برای راحتی کار بنويسيم :
int TwoDimensionalMemAllocate(int ***x,int nRow,int nCol)
{
int i;
*x=(int **)malloc(nRow*sizeof(int *));
if(*x==NULL)
return -1;
for(i=0;i<nRow;i++){
(*x)[i]=(int *)malloc(nCol*sizeof(int));
if((*x)[i]==NULL)
return i+1; // baraye taiine mahalle daqiqe error.
}
return 0;
}
يا اينکه اگه بخوايم اين نکته آخرو رعايت کنيم، داريم:
int TwoDimensionalMemAllocateEx(int ***x,int nRow,int nCol)
{
int i;
*x=(int **)malloc(nRow*sizeof(int *));
if(*x==NULL)
return 1;
(*x)[0]=(int *)malloc(nCol*nRow*sizeof(int));
if((*x)[0]==NULL)
return 2;
for(i=1;i<nRow;i++)
(*x)[i]=(*x)[i-1]+nCol;
return 0;
}
بديهی هست که برای x از ***استفاده ميکنيم تا بتونيم مقدار پارامتر ارسالی رو خارج از حوزه تابع تغيير بديم.
برای استفاده از این تابع هم باید به صورت زیر عمل کنیم:
int **My2DimArray;
if(TwoDimensionalMemAllocateEx(&My2DimArray,10,1500)!=NULL){
//error
}
راستی این کدهای ایجاد رو میشه با عملگر new هم نوشت..که زحمتشو خودتون بکشید!
در پايان برای مشاهده يه مثال ساده می تونید به آدرس http://nullsector.blogspot.com (http://nullsector.blogspot.com) مراجعه کنید.
اگه تو حرفام اشتباهی کردم حتما بگین..ممنون.
ضمنا از مسئولای این سایت هم واقعا تشکر میکنم که یه محیط خوب برای برنامه نویسای ایرانی ایجاد کردن.
--مقدمه:
خيلی وقتا پيش مياد که می خوايم يه آرايه دو بعدی با اندازه ی دلخواه و غير ثابت در زمان اجرا(runtime) ايجاد کنيم. یعنی یه آرایه دوبعدی پویا!
خوب روشی که معمولاًً استفاده ميشه اينه که يه آرايه ی يک بعدی تعريف مي کنيم و اونو به صورت دو بعدی آدرس دهی ميکنيم .مثلاً برای مثال بالا مينويسيم:
int *d1Test=new int[nRow*nCol*sizeof(int)]; // in c++
يا اينکه :
int *d1Test=(int *)malloc(nRow*nCol*sizeof(int)); // in c
و بعد برای دسترسی به خانه های اين آرايه به صورت دو بعدی ، از عملگر* استفاده مي کنيم يعنی در حالت کلی برای دسترسی به خانه ی ij ام از آرايه d1Testمينويسيم (d1Test+i*nCol+j)* که i*nCol+j آفست-آدرس از ديد دو بعدی هست که با آدرس base جمع ميشه تا به آدرس واقعی اون خانه اشاره کنه.
ولی اگه به صورت ایستا دو بعدی تعريف می کردیم (يعنی مثلاً int sTest[4][5] ) برای منظور بالا مينوشتيم sTest[i][j]
حالا اگه بخوايم يه آرايه دو بعدی به صورت پويا تعريف کنيم که دسترسی به اون به صورت d1Test[i][j]باشه بايد چه کار کنيم؟!
--راه حل:
خوب ما ميخواهيم يک آرايه با nRow سطر و nCol ستون داشته باشيم، کاری که انجام ميديم اينه که nRow اشاره گر تعريف ميکنيم که هر کدام به ابتدای يه آرايه به اندازه nCol اشاره کنه، ولی چون که nRow ثابت نيست پس آرايه اي که اين nRow اشاره گر را نگه شون ميداره بايد خودشم اشاره گر باشه (برای پويا بودن)، حتماً متوجه شدين که ما در واقع يه اشاره گر به اشاره گر ميخوايم!
حالا مرحله به مرحله اين کار رو انجام ميديم..اول يه اشاره گر به اشاره گر تعريف ميکنيم:
int **d2Test;
خوب d2Test بايد در مرحله اول به يه آرايه از nRow اشاره گر اشاره کنه، يعنی:
d2Test=(int **)malloc(nRow*sizeof(int *));
دقت کنيد که مينويسيم sizeof(int *)چون ما داريم يه آرايه تعريف ميکنيم که تعدادی اشاره گر رو در خودش نگه ميداره. حالا d2Test[i] به ازای i=0 تا i=nRow-1 يه اشاره گر هست که فعلاً به جايی اشاره نميکنه.پس در مرحله دوم بايد کاری کنيم که هر کدام از اين d2Test[i]ها به يه آرايه nCol تايی اشاره کنه يعنی nCol خانه برای هر کدام تخصيص حافظه کنيم،پس داريم:
for(int c=0 ; c<nRow ; c++)
d2Test[i]=(int *)malloc(nCol * sizeof(int));
اگر همه memory allocation ها بدون خطا انجام شده باشه،آرايه آماده هست.
الان برای اينکه به خانه ی ij ام دسترسی پيدا کنيم خیلی راحت مينويسيم d2Test[i][j] دقيقاً مانند دسترسی به يک آرايه دو بعدی که ایستا تعريف شده. ولی يه فرق اساسی بين اونا وجود داره که حتماً تا الان متوجه ی اون شدين..تفاوتی که هست اينه که sTest[i][j] به هيچ وجه مثل d2Test[i][j] کامپايل نميشه، در واقع sTest[i][j] به صورت (sTest + i*nCol + j)* ترجمه ميشه در حالی که d2Test[i][j] به صورت *(*(d2Test+i)+j) ترجمه ميشه!!
و اين وظيفه کامپايلر هست که اين دو وضعيت رو از هم تشخيص بده.
--نقد و بررسی:
1.روش ايستا:
در زمان ايجاد بايد ابعاد آرایه ثابت (fixed) باشه(ایستا). اندازش هم محدود هست، که به کامپايلر و سيستم عامل و در صورت محلی بودن به اندازه پشته بستگی داره.
طريقه استفاده از اونا يعنی همون ظاهرشون توی برنامه واضح و ساده هست (sTest[i][j])
2.روش پويا يک بعدی:
در زمان ايجاد ابعادش ميتونه متغير باشه(پويا). اندازش تقریبا فقط به اندازه حافظه موجود بستگی داره.
زمان دسترسی به یک عنصر دقيقاً برابر حالت ايستا هست مگر اينکه آدرس دسترسی ثابت باشه. مثلاً (d1Test +4*nCol + 5)* چون در اين صورت برای حالت ايستا محاسبه ی آدرس عنصر در زمان کامپايل انجام ميشه.
طريقه استفادش تو برنامه به دليل شکل نامتعارف برای تازه کارها کمی دشوار هست.
3.روش پويا دو بعدی:
در زمان ايجاد، ابعادش ميتونه متغير باشه(پويا). تو این روش مدت زمان ايجاد صفر نيست یعنی چون برای ایجاد آرایه nRow+1بار عمل تخصیص حافظه رو انجام میدیم ایجادش به کمی زمان و پردازش اضافی نیاز داره(در حدود میلی ثانیه) .
اندازه اش مثل حالت پویای یک بعدی هست.
زمان دسترسی به یک عنصر اون از دو حالت قبل سريعتره؛ چون در دو حالت قبل برای محاسبه آدرس عنصر در حافظه یه ضرب و یه جمع انجام ميشد، ولی تو این حالت فقط 2 بار به صورت متوالی عمل qualification انجام ميشه.
پس اين روش دو تا مشکل داره : اول اينکه برای ايجادش باید چند خط کد بنویسیم(کی حال داره!) و دومیش اينکه ايجادش زمان می بره.خوب مشکل اول که با نوشتن يه تابع که اينکارو برای ما انجام بده تقريباً حل ميشه. ولی آيا ميتونیم از یه تعداد کمتری عمل تخصیص حافظه استفاده کنیم؟
جواب مثبته. برای اينکار ميتونيم مثل قبل تو مرحله اول يه آرايه nRow تايی از اشاره گر ها بگيريم،
ولی تو مرحله بعدی به جای اينکه nRow بار يه آرايه nCol تايی بگيريم، يه بار يه آرايه nCol*nRow تايی می گيريم
و بعد با يه حلقه اونو با فواصل nCol تايی به اشاره گر ها اختصاص میديم:
مرحله اول:
int **d2Test;
d2Test=(int **)malloc(nRow*sizeof(int *));
مرحله دوم:
Ed2Test[0]=(int *)malloc(nRow*nCol*sizeof(int));
For(int c=1 ; c<nRow ; c++)
Ed2Test[c]=Ed2Test[c-1]+nCol; //ya inke Ed2Test[c]=Ed2Test[0]+c*nCol;
خوب حالا ميتونيم يه تابع برای راحتی کار بنويسيم :
int TwoDimensionalMemAllocate(int ***x,int nRow,int nCol)
{
int i;
*x=(int **)malloc(nRow*sizeof(int *));
if(*x==NULL)
return -1;
for(i=0;i<nRow;i++){
(*x)[i]=(int *)malloc(nCol*sizeof(int));
if((*x)[i]==NULL)
return i+1; // baraye taiine mahalle daqiqe error.
}
return 0;
}
يا اينکه اگه بخوايم اين نکته آخرو رعايت کنيم، داريم:
int TwoDimensionalMemAllocateEx(int ***x,int nRow,int nCol)
{
int i;
*x=(int **)malloc(nRow*sizeof(int *));
if(*x==NULL)
return 1;
(*x)[0]=(int *)malloc(nCol*nRow*sizeof(int));
if((*x)[0]==NULL)
return 2;
for(i=1;i<nRow;i++)
(*x)[i]=(*x)[i-1]+nCol;
return 0;
}
بديهی هست که برای x از ***استفاده ميکنيم تا بتونيم مقدار پارامتر ارسالی رو خارج از حوزه تابع تغيير بديم.
برای استفاده از این تابع هم باید به صورت زیر عمل کنیم:
int **My2DimArray;
if(TwoDimensionalMemAllocateEx(&My2DimArray,10,1500)!=NULL){
//error
}
راستی این کدهای ایجاد رو میشه با عملگر new هم نوشت..که زحمتشو خودتون بکشید!
در پايان برای مشاهده يه مثال ساده می تونید به آدرس http://nullsector.blogspot.com (http://nullsector.blogspot.com) مراجعه کنید.
اگه تو حرفام اشتباهی کردم حتما بگین..ممنون.
ضمنا از مسئولای این سایت هم واقعا تشکر میکنم که یه محیط خوب برای برنامه نویسای ایرانی ایجاد کردن.