اشاره گرها

اشاره گرها

اسلاید 1: اشاره گرها

اسلاید 2: مقدمه:در درس مباني كامپيوتر با اشاره گرها آشنا شديم و نحوه استفاده و كاربرد آنها رابررسي كرديم.در اين قسمت ابتدا يادآوري از مباحث گذشته آورده ميشود،سپس به ذكر مباحث پيشرفته تري از اشاره گرها مي پردازيم.

اسلاید 3: اشاره گرها در c++ كاربردهاي فراواني دارند،زيراداراي قابليتهاي بسياري هستند كه تعدادي از آنها عبارتند از:بهبود كارائي بسياري از توابعدسترسي آسان به عناصر آرايه هاتسهيل انجام كاربارشته هاو آرايه هاانتقال آرايه هاورشته ها به توابعارسال آرگومان ها ازطريق فراخواني با ارجاعتخصيص حافظه پوياايجاد ساختمان داده هائي نظيرليستهاي پيوندياشاره گرها :

اسلاید 4: آدرس هاواشاره گرها:مقدارa آدرس apaاشاره گر چيست؟اشاره گر يك متغير است كه آدرس يك متغير ديگر را در خود نگه ميدارد. حافظه كامپيوتر مجموعه اي از چندين بايت است.هر بايت داراي يك شماره رديف است.شماره رديف هر بايت از حافظه را آدرس آن محل از حافظه گويند.آدرس اولين بايتي از حافظه كه به متغير اختصاص مي يابد،آدرس آن متغير مي ناميم. به شكل زير توجه كنيد:

اسلاید 5: متغيرهاي اشاره گر:تعريف متغيراشاره گردر c++ به صورت زير عمل مي كنيم:متغير * نوع;int *ptr;كه در اينجا * به معني تعريف اشاره گر مي باشد.دليل اين نوع تعريف نيز اين مي باشد كه كامپايلر نيازمند اين است كه بداند اين اشاره گر به چه نوع متغيري اشاره ميكند.

اسلاید 6: عملگرهاي اشاره گر:int a=5,b;int *ptr;ptr = &a;b=*ptr;عملگر & آدرس عملوند خودرامشخص مي كند. عملگر * محتويات جائي را مشخص مي نمايدكه عملوندش به آن اشاره مي كند.به عملگر * ،عملگر دسترسي به اطلاعات يا عملگر غيرمستقيم ميگويند. در اكثر كتب برنامه نويسي به اين عملگر، نام عملگر محتوا اطلاق شده است زيرابيانگر محتواي يك متغير است.

اسلاید 7: حال به مثال زير توجه كنيد:int main ( ){int var1=11, var2=22;int *ptr;ptr=&var1;cout<<”ptr point to “<<&var1<<”& ptr contents is”<<*ptr;ptr=&var2;cout<<”ptr point to “<<&var2<<”& ptr contents is”<<* ptr;return 0;}خروجي اين برنامه عبارت است از:ptr point to 0x8f4ffff2 & ptr contents is 11ptr point to 0x8f4ffff0 & ptr contents is 22

اسلاید 8: اشاره گر به void:معمولا آدرسي كه در يك اشاره گر قرار ميگيردبايد همنوع با اشاره گر باشد.براي مثال نمي توان آدرس يك متغير float رادر يك اشاره گر از نوع int جايگزين كنيد.اما يك نوع اشاره گر همه منظوره وجود دارد كه مي تواند به هرنوع داده اي اشاره كند.اينگونه اشاره گرها داراي كاربرد ويژه و معيني نظير انتقال اشاره گر به تابعي هستند كه بطور مستقل برروي انواع داده اي مختلف عمل ميكند. كه به صورت زير تعريف مي شود:void *نام متغير;

اسلاید 9: به مثال زير توجه كنيد:int *intptr, a=3;float *floatptr, b=4;void *ptr;intptr = &a;//OKintptr = &b;//Errorfloatptr = &a;//Errorfloatptr = &b;//OKptr = &a;//OKptr = &b;//OKتوضيح مثال:برطبق تعريف بالا آدرس متغير aرا نميتوان در متغير floatptr ذخيره كرد ونيز آدرس متغير bرا هم نمي توان در متغير intptr ذخيره كرد.اما آدرس هر دو متغير aوb را مي توان در متغيرptr كه از نوع void است ذخيره كرد.

اسلاید 10: اعمال روي اشاره گرها:اعمالي كه مي توان برروي اشاره گرها انجام داد عبارتند از:عمل انتساب اشاره گرهابه يكديگراعمال محاسباتي جمع وتفريقعمل مقايسه اشاره گرها

اسلاید 11: اعمال محاسباتي بر روي اشاره گرها:اعمال جمع و تفريق را مي توان بر روي اشاره گرها انجام داد. با افزايش يك واحدبه اشاره گر به اندازه طول نوع اشاره گر به آن اضافه مي شود.به عنوان مثال اگر p اشاره گري از نوع int باشد كه محل 1000 حافظه اشاره مي نمايد p++ موجب مي شودكه p به عدد صحيح بعدي اشاره كند. و p برابر 1004 شود.

اسلاید 12: مقايسه اشاره گرها:اشاره گرها را نيز مي توان با عملگرهاي رابطه اي مقايسه كرد.به عنوان مثال به دستورات زير توجه كنيد:*p1 == *p2; براي مقايسه محتواي محل اشارهp1 == p2براي مقايسه محلي كه اشاره گر به آنجا اشاره مي كند براي مثال دستور زير معتبر است به شرطي كه px و py هردو اشاره گر به يك نوع داده (مثلا int ) باشند.if (px<py) printf (px points to lower memory than py) ;else printf (px points to upper memory than py) ;

اسلاید 13: انتقال اشاره‌گر به تابع:وقتي كه يك اشاره‌گر به يك تابع گذر داده مي‌شود، در واقع آدرس آن قلم از داده به تابع فرستاده مي‌شود. هر گونه تغييراتي كه در محتواي آدرس مورد نظر انجام گيرد، هم در تابع فراخوانده شده و هم در برنامه يا تابع فراخواننده تأثير مي‌گذارد .پارامتر متناظر تابعي كه يك آدرس را به عنوان آرگومان دريافت مي‌كند ، بايد يك اشاره‌گر باشد .

اسلاید 14: پارامتر متناظر تابعي كه يك آدرس را به عنوان آرگومان دريافت مي‌كند ، بايد يك اشاره‌گر باشد . # include <stdio.h>void add (int *) ;void main ( ) { int count = 7 ; printf(the original value of count is %dn , count) ; add (& count) ; printf (the new value of count is %dn , count) ; }void add (int *countptr) { ++ (*countptr) ; /* increments count in main */ }خروجي:the original value of count is 7the new value of count is 8

اسلاید 15: مثال: برنامه زير، تفاوت بين آرگومانهاي معمولي که بوسيله مقدارعبور داده مي شوند و آرگومانهاي اشاره گر را که بوسيله مرجع عبور داده مي شوند روشن مي سازد . void func1 ( int u , int v ) ;void func2 ( int *pu , int *pv ) ;void main ( ){ int u = 1 ; int v = 3 ; printf (“n Before calling func1 : u=%d v=%d , u , v ) ; func1(u , v ) ; printf (“n After calling func1 : u=%d v=%d , u , v ) ; printf (“n Before calling func2 : u=%d v=%d , u , v ) ; func2(&u , &v ) ; printf (“n After calling func2 : u=%d v=%d , u , v ) ; getch();}…

اسلاید 16: void func1 ( int u , int v ) { u = 0 ; v = 0 ; printf (“n Within func1 : u=%d v=%d , u , v ) ; return ;}void func2 ( int *pu , int *pv ) { *pu = 0 ; *pv = 0 ; printf (“n Within func2 : *pu=%d *pv=%d , *pu , *pv ) ; return ;}ادامه مثال:Before calling func1 : u = 1 v = 3Within func1 : u = 0 v = 0After calling func1 : u = 1 v = 3Before calling func2 : u = 1 v = 3Within func2 : *pu = 0 *pv = 0After calling func2 : u = 0 v = 0 خروجي:

اسلاید 17: اشاره‌گر و آرايه: 3726111510141549138121923182217211620262524pكاراكتر مخصوص ‘0’str str[4] يا *(p+4) كاراكتر مخصوص ‘0’027بين اشاره‌گرها و آرايه‌ها رابطه نزديكي وجود دارد . نام يک آرايه در واقع اشاره گري به اولين عنصر آرايه است.char str[18] , *p ;p = str;اگر بخواهيم به پنجمين عنصر در str دسترسي داشته باشيم ، مي‌توانيم اين كار را به دو روش زير انجام دهيم :

اسلاید 18: 8575797478737772767d817c807b7f7a7e848382xx+1x+2x+310111213x+515x+414int x[6]

اسلاید 19: مديريت حافظه : عملگر هاي new و delete c++ روش ديگري براي بدست آوردن قسمت هايي از حافظه با استفاده از عملگر new فراهم ساخته. اين عملگر از سيستم عامل حافظه اي با طول مشخص مي گيردو يك اشاره گركه به نقطه شروع آن اشاره ميكند را بر ميگرداند.Student *pSt;1) pSt = new Student; //حافظه به اندازه يك دانشجو اخذ ميشود2) pSt = new Student[10];//حافظه براي نگهداري اطلاعات 10 دانشجو از سيستم گرفته ميشود

اسلاید 20: int *x,ncin>>nx = new int [n];تكه برنامه اي بنويسيد كه تعداد المانهاي يك آرايه صحيح را گرفته و با توجه به مقدار وارد شده يك آرايه از نوع صحيح ايجاد نمايدمثال

اسلاید 21: عملگر delete : اگر در برنامه خود با استفاده از عملگر new ، مقدار زيادي حافظه بگيريم آنگاه تمام حافظه موجود در اختيار برنامه خواهد بود . براي برگرداندن حافظه گرفته شده توسط دستور new از دستور delete استفاده مي كنيم .ptr =new SomeClassdelete ptr البته با خاتمه اجراي برنامه ، حافظه گرفته شده توسط دستور new به صورت اتوماتيك به سيستم بر ميگردد و احتياجي به دستور delete نيست .

اسلاید 22: اشاره گر هايي به اشيا :اشيا مي توانند به انواع داده اي ساده و آرايه ها اشاره كنند . تعريف كلاس زير را در نظر بگيريد :Class Distance { ….Void get(){…}….} به عنوان مثال دستور زير براي ايجاد يك كلاس استفاده ميشود .Distance dist;مي توان اشاره گري به صورت زير تعريف كرد كه به انواع داده اي از نوع اين كلاس اشاره كند :Distance *ptr;

اسلاید 23: ميتوان از عملگر هاي new و delete نيز استفاده كرد.Distance *ptr = new Distance;new Distance آدرس يك شي جديد كه در حافظه ايجاد ميشود را برميگرداند و اين آدرس در متغير ptr نگهداري ميشود.دسترسي به اعضا :براي دسترسي به اعضاي يك شي داده وقتي اشاره گري به آن نسبت داده ايم بايد از علامت خاصي به شكل زير استفاده كنيم :ptr->get()البته از اين روش نيز ميتوان استفاده كرد : *(ptr).get()

اسلاید 24: تمرينيك كلاس براي نگهداري اطلاعات دانشجو تعريف نماييد.توابع مناسب براي مقداردهي به متغيرهاي عضو كلاس و نمايش اطلاعات كلاس را تعريف نماييديك اشاره گر از نوع Student تعريف نماييدفضاي لازم براي نگهداري اطلاعات يك دانشجو را از سيستم بگيريدبا استفاده از توابع عضو كلاس پس از مقدار دهي به شي دانشجو اطلاعات وارد شده را نمايش دهيد.حافظه اخذ شده را به سيستم برگردانيدحال مجدداً با استفاده از همان اشاره گر فضا براي نگهداري اطلاعات 3 دانشجو را اخذ نماييد و پس از گرفتن اطلاعات دانشجويان، آنرا نمايش داده و حافظه را به سيستم برگردانيد.

اسلاید 25: در صورتي كه تخصيص حافظه بصورت آرايه اي باشد بايد آزادسازي حافظه به شكل زير انجام گيرد:int *ptr;ptr = new int[n];…delete [] ptr;

اسلاید 26: ليست پيوندي Link ListA. . .0ZBتعريف : مجموعه ای از گره ها که هرگره حداقل شامل يک فيلد داده ويک فيلد اشاره گر است.اشاره گر هر گره از نوع خود گره است.هر گره به وسيله ی اشاره گر خود به گره بعدی اشاره می کند.

اسلاید 27: - عمليات ليست پيوندي- ايجاد ليست - درج گره در ليست- حذف گره از ليست- جستجو در ليست- مرتب سازي ليست- معكوس كردن ليست- و ...

اسلاید 28: پياده سازي با اشاره گرتعريف يك نودلازم است اين مسئله مشخص شود که فيلدهای ما چه نوع داده ای هستند.(به عنوان مثال می توان يک کاراکتر)class CNode{ private: char data; CNode *link; public: CNode(char d , CNode* l=NULL);};

اسلاید 29: كلاس ليست پيونديclass CLinkList { private: CNode *first,*last; public:CLinkList();CLinkList(const CLinkList &l);void InsertFirst(char new_char);void InsertAfter(CNode *pNode , char new_char);void InsertBefore(CNode *pNode , char new_char);void InsertLast(char new_char);void DeleteItem(CNode *pNode);char GetItemData(int ItemIndex);void Display()const;CNode* Find(char ch);void DestroyList();~CLinkList();};

اسلاید 30: درج گره در ابتداي ليستABCfirstABCfirstAvoid CLinkList::InsertFirst (char new_char){CNode *t = new CNode(new_char, first);first = t;if(!last)last = first;}

اسلاید 31: اضافه کردن به ابتدای ليستfirst00newNodeABCDE

اسلاید 32: first0newNodeاضافه کردن به ابتدای ليست-ادامهABCDEnewNode  link = first;

اسلاید 33: اضافه کردن به ابتدای ليست-ادامهfirst0newNodeEDCBAfirst = newNode;

اسلاید 34: اضافه کردن به ابتدای ليست-ادامهfirstnewNode0ABCDE

اسلاید 35: نمايش ليست پيوندی (پيمايش)void CLinkList ::Display(){if( !first ) return;//no nodeNode *temp = first;while(temp)//traverse list{cout << tempdata;temp = templink;//next node}}

اسلاید 36: اضافه کردن عنصر جديدالبته برای کاربردهای مختلف اضافه کردن فرق می کند.ما در اينجا اضافه کردن عنصر جديد بعد از يک عنصر مشخص را نشان می دهيم.مراحل کار:1) نصب عنصر جديد2) تنظيم اشاره گرهای مربوط به عنصر جديد

اسلاید 37: firstcurNode00newNodeدرج عنصر جديد

اسلاید 38: firstcurNode0newNodeاضافه کردن عنصر جديد-ادامهCBADEnewNode  link = curNode  link ;

اسلاید 39: firstcurNode0newNodeاضافه کردن عنصر جديد-ادامهABDECcurNode  link = newNode ;

اسلاید 40: firstcurNode0newNodeاضافه کردن عنصر جديد-ادامهABCDE

اسلاید 41: اضافه کردن عنصر جديد-ادامهvoid CLinkList::InsertAfter(CNode *pNode , char new_char){CNode*newNode = new CNode(new_char); newNodelink = curNodelink ;//assign newNodecurNodelink = newNode ;//assign curNode}

اسلاید 42: حذف عنصر از ليست پيوندیمراحل کار:1) تنظيم اشاره گرها2) حذف کردن گره (آزاد کردن حافظه)

اسلاید 43: firstcurNode0ِAِBCِDِEحذف عنصر از ابتدای ليست پيوندی

اسلاید 44: firstcurNode0ِAِBCِDِEحذف عنصر از ليست پيوندی-ادامهfirst = first link;

اسلاید 45: first0ِBCِDِEحذف عنصر از ابتدای ليست پيوندی-ادامهdelete cur;

اسلاید 46: firstcurNode0ِAِBCِDِEحذف عنصر از ليست پيوندی-ادامهtempNode *temp = first;

اسلاید 47: firstcurNode0ِAِBCِDِEحذف عنصر از ليست پيوندی-ادامهtempwhile( temp  link != cur) temp = temp  link;

اسلاید 48: firstcurNode0ِAِBCِDِEحذف عنصر از ليست پيوندی-ادامهtempwhile( temp  link != cur) temp = temp  link;

اسلاید 49: حذف عنصر از ليست پيوندی-ادامهfirstcurNode0ِAِBCِDِEtemptemp  link = cur  link;

اسلاید 50: حذف عنصر از ليست پيوندی-ادامهdelete cur;first0ِAِBِDِEtemp

اسلاید 51: void CLinkList::DeleteItem(CNode *cur){if( cur == first ){first = first  link;delete cur;return;} Node *temp = first;while( templink != cur) temp = temp  link;templink = curlink;delete cur;}حذف عنصر از ليست پيوندی-ادامه

اسلاید 52: تمرينكلاس ليست پيوندي كه prototype آن در اسلايدهاي قبل آورده شده است را پياده سازي نماييد.براي نمايش ليست پيوندي در صورتي كه در محيط VisualC برنامه نويسي ميكنيد در تابع Display يك اشاره گر از نوع CListBox گرفته شود و درون ليست نمايش اطلاعات صورت پذيرد. ديالوگهاي مناسب جهت اضافه و حذف را طراحي نموده و پيامهاي مناسب نيز نمايش داده شود.

اسلاید 53: ليست های حلقویبه وسيله ی اتصال آخرين گره به اولين گره می توان ليست حلقوی را توليد کرد.در اين گونه ليست ها به راحتی می توان از آخر ليست به اول ليست پرش کرد.

اسلاید 54: نمونه ای از ليست حلقویfirstِAِBCِDِE

اسلاید 55: ليست های پيوندی دوگانه ( دو طرفه )مشکل اساسی ليست های يک طرفه عدم دسترسي به گره قبلیليست های دوگانه با اضافه کردن يک اشاره گر به گره ی قبلی اين مشكل را حل كرده است.

اسلاید 56: 0ABCDE0first ABCDE firstليست دوطرفه ی سادهليست دوطرفه ی حلقویانواع ليست های پيوندی دوگانه

اسلاید 57: اضافه کردن عنصر به ليست دوطرفه ساده0ABDE0firstCcurnewElenextpre

اسلاید 58: newEle  next = cur  next;0ABDE0firstCcurnewEleاضافه کردن عنصر به ليست دوطرفه ساده-ادامه

اسلاید 59: cur  next = newEle;0ABDE0firstCcurnewEleاضافه کردن عنصر به ليست دوطرفه ساده-ادامه

اسلاید 60: cur  next = newEle;0ABDE0firstCcurnewEleاضافه کردن عنصر به ليست دوطرفه ساده-ادامه

اسلاید 61: (newEle  next)  pre = newEle;0ABDE0firstCcurnewEleاضافه کردن عنصر به ليست دوطرفه ساده-ادامه

اسلاید 62: 0ABCDfirstE0curnewEleاضافه کردن عنصر به ليست دوطرفه ساده-ادامه

اسلاید 63: سوالاگر بخواهيم عنصر newEle را به ابتداي ليست اضافه كنيم؟اگر بخواهيم عنصر newEle را به انتهاي ليست اضافه كنيم؟اگر ليست خالي باشد؟

اسلاید 64: 0ABCDfirstE0curحذف از ليست دوطرفه ساده

اسلاید 65: A0BCDfirst0Ecur( cur  next )  pre = cur  pre;حذف از ليست دوطرفه ساده -ادامه

اسلاید 66: ( cur  pre )  next = cur  next;0ABCDfirstE0curحذف از ليست دوطرفه ساده-ادامه

اسلاید 67: ( cur  pre )  next = cur  next;0AnextpreBnextpreDnextfirstpreE0 حذف از ليست دوطرفه ساده -ادامه

اسلاید 68: 0AnextpreBnextpreDnextfirstpreE0حذف از ليست دوطرفه ساده -ادامه

اسلاید 69: سوالاگر بخواهيم عنصر ابتداي ليست را حذف كنيم؟اگر بخواهيم عنصر ابتداي ليست را حذف كنيم؟اگر ليست خالي باشد؟

اسلاید 70: تمريناپراتورهاي زير را در كلاس CLList تعريف نماييد+ : اين عملگر مشابه افزودن به انتهاي ليست عمل ميكندعملگر -: اين عملگر بدنبال يك كاركتر در ليست ميگردد و در صورت وجود اين عنصر در ليست آنرا حذف ميكندعمگر =: اين عملگر يك ليست را در ليست ديگر كپي ميكندعملگر ==: اين عملگر دو ليست را با هم مقايسه نموده و در صورتي كه با هم برابر باشند مقدار TRUE و در غير اينصورت مقدار FALSE برميگرداندعملگر [] كه يك انديس گرفته و مقدار موجود در گره با انديس وارد شده را برميگرداند.char operator[](int idx);

اسلاید 71: اشاره گر thisتوابع عضو هر شي به يك اشاره گر جادويي به نام this دسترسي دارند كه به خود شي اشاره ميكند.معناي وجود اين متغير در كلاس يعني هر شي آدرس خود در خافظه را ميداند و يا تعبير ديگر اينكه هر شي خودش را ميبيند و خودش را ميشناسد.

اسلاید 72: class where { private: char charArr[10]; public:void reveal(){cout<< “nMy object’s address is:”<<this;}};void main(){where w1,w2;w1. reveal();w2. reveal();cout <<“w1 Address is “<<&w1;cout <<“w2 Address is “<<&w2;}My objectْs address is:0012FF74My objectْs address is:0012FF68w1 Address is 0012FF74w2 Address is 0012FF68

اسلاید 73: كاربردهاي اشاره گر thisيكي از پركاربردترين كاربردها زماني است كه ميخواهيم خروجي يك تابع عضو خود شي و يا آدرس خود شي باشد.كاربرد ديگر زماني است كه ميخواهيم خود شي را بعنوان آرگومان يك تابع ارسال نماييمفرض كنيد تابعي داريم كه يك شي را گرفته و اطلاعات آنرا نمايش دهد. ما ميخواهيم همين تابع نمايش دادن بصورت يك تابع عضو كلاس نيز باشد. براي استفاده از تابع موجود ميتوانيم از اشاره گر this استفاده نماييم.