دانلود پاورپوینت آرایه ها و ساختار ها در زبان برنامه نویسی

بنام خدا آرایه ها و ساختار ها در زبان برنامه نویسی آرايه ها و ساختارها ‏ADT (Abstraction data type)  آرايه ها يونيون ها و ساختارها ماتريس هاي اسپارس آرايه هاي چند بعدي چند جمله اي ها رشته ها آرايـه Array - ‏ ‏ ‏ مجموعه ای از داده كه در خانه های پشت سرهم حافظه قرارمی گيرند. مجموعه ای از زوجها شامل انديس و مقدار< >i .xاست. به ازای هر انديس يک مقدار مربوط به آن انديس وجود دارد (تناظر يا نگاشت) }int a [7] = { 3,5,2,7,9,10,11 ]a[6 ]a[5 ]a[4 ]a[3 ]a[2 ]a[1 ]a[0 11 10 9 7 2 5 3 مربوط به آرايه هاADT - GeneralArray(int j, RangList list ,float InitialValue=DefaultValue); /* Creates a j dimension array of floats where the range of the kth dimension is given by the kth element of list.*/ - float Retrieve (index i); //if(i is in the index set )return the item associated with i in the array else return error -void Store( index i, float x); //if (i is in the index set ) insert new pair<i,x> else return error. آرايه در حافظه ‏ ‏ يک آرايه يک بعدی به سادگی بوِس له نسبت دادن دو کروشه به نام يک متغير تعريف ميشود: ;]int list[5 آدرس اولين عنصر آدرس مبنا يا پايه ناميده می شود. ‏Memory addres ‏base address = a )a+1*sizeof(int )a+2*sizeof(int )a+3*sizeof(int )a+4*sizeof(int ‏Variable ]List[0 ]List[1 ]List[2 ]List[3 ]List[4 آدرس دهی آرايه يک بعدی ElementType List [n]; List [0]= (٭base address = α) List [i] = (٭α + i * size of (ElementType)) ساختار Structure - ‏ آرايه ها مجموعه داده های از يک نوع. ساختارها داده هايی از انواع مختلف در کنار هم. ‏ ساختار= .struct ساختار = Record ‏ ‏ – مجموعه ای از اقالم داده ها ()Field تعريف و دسترسي به عناصر struct { char name [ 10 ] ; int age ; float salary ; } person ; Strcpy ( person.name , “james” ); Person.age = 32 ; Person.salary = 250000; يونيون – Union ‏ يونِيون ها مانند ساختارها ولي .1 .2 در آن واحد فقط از يک نوع تعريف شده استفاده می کند. از بزرگتِرن مقداردهی برای آن نوع استفاده می کند. {union test ;int x ;char y } ماتريس اسپارس – Sparse Matrix ماتريسی که عناصر صفر آن زياد باشد . صرفه جويی در زمان و حافظه. چگونه بايستي اطالعات يك ماتريس پرصفر را در حافظه ذخيره كنيم تا حافظه كمتري مصرف شود؟ (چه ساختمان داده اي ؟) آيا عملياتهاي مربوط به آرايه ها ( )ADTبر روي اين ساختمان داده قابل پياده سازي است؟ ماتريس اسپارس ‏ نگهداري عناصر غير صفر ماتريس و اطالعات مربوط <> row , column ,value ‏ عناصر بترتيب سطري و در هر سطر بترتيب ستوني مي شود. ذخيره ماتريس اسپارس – مثال col0 col1 col2 col3 col4 col5 Row0 Row1 Row2 Row3 Row4 Row5 15 0 0 0 91 0 0 11 0 0 0 0 0 3 0 0 0 28 22 0 -6 0 0 0 0 0 0 0 0 0 -15 0 0 0 0 0 ماتريس اسپارس – مثال تعداد سطرهاي ماتريس اوليه تعداد ستونهاي ماتريس اوليه تعداد عناصرغير صفر ماتريس اوليه ‏row ‏col ‏value 8 6 6 ]A[0 15 22 -15 11 3 -6 91 28 0 3 5 1 2 3 0 2 0 0 0 1 1 2 4 5 ]A[1 ]A[2 ]A[3 ]A[4 ]A[5 ]A[6 ]A[7 ]A[8  ماتريس اسپارسADT Class SparseMatrix { //Object: A set of triples <row, column, value> … public: SparseMatrix(int MaxRow,int MaxCol); /* Create a SparseMatrix that can hold up to MaxItems=MaxRow*MaxCol */ SparseMartix Transpose(); SparseMatrix Add(SparseMatrix b); SparseMatrix Multiply(SparceMatrix b); } ترانهاده ماتريس اسپارس براي ترانهاده كردن اين ماتريس شماره ي سطر و ستون را عوض كرده مقدار عنصر را در ستون valueقرار مي دهيم: ()0,0,15 ()0,3,22 ()15-,0,5 ()0,0,15 ()3,0,22 ()15-,5,0  مثال- ترانهاده ماتريس اسپارس row col value row col value A[0] 3 5 4 B[0] 5 3 4 A[1] 0 1 1 B[1] 0 2 6 A[2] A[3] 0 1 2 1 2 5 B[2] 1 0 1 B[3] 0 6 B[4] 1 2 1 0 5 2 A[4] 2 ويژگيهاي كالس اسپارس class MatrixTerm { friend class SparseMatrix private : int row, col, value;} In SparseMatrix: private: int Rows, Cols, Terms; MatrixTerm smArray [MaxTerms]; تابع ترانهاده ي ماتريس اسپارس SparseMartix SparseMartix::Transpose() //return the transpose of a (*this) { SparseMatrix b; b.Rows=Cols; //rows in b = columns in a b.Cols=Rows; //columns in b = rows in a b.Terms=Terms; //terms in b = terms in a if ( Terms> 0){ int currentb = 1; for ( int c = 0; c < Cols ; c++) for( int j = 0; j < Terms; j ++) if( smArray[j].col ==c) { b. smArray[currentb].row = c; b. smArray[currentb].col = smArray [j].row; b. smArray[currentb].value = smArray [j].value; currentb ++;} } return b;} تحليل تابع ترانهاده حلقه های تودرتو عبارات ifو انتسابها در زمان ثابتی انجام ميشود. حلقه forخارجی به تعداد ستونهای ماتريس اوليه حلقه forداخلی به تعداد عناصر در ماتريس اوليه )O(columns * terms تابع ترانهاده ي سريعتر؟ می توان ترانهاده ی يک ماتريس را در زمانی که تابع سطر و ستون است بدست آورد؟ )O(columns + terms ترانهاده ی سريع محاسبه تعداد عناصر در هر ستون ماتريس اصلی؛ با اين عمل تعداد عناصر در هر رديف ماتريس ترانهاده مشخص می شود. با اين اطالعات موقعيت شروع هر سطر در ماتريس ترانهاده را داريم. حال ميتوانيم عناصر ماتريس اصلی را يکی يکی به موقعيت صحيح در ماتريس ترانهاده منتقل کنيم. الگوريتم ترانهاده ي سريع SparseMatrix SparseMatrix :: fast_transpose() { int *RowSize = new int[Cols]; int *RowStart= new int[Cols]; SparseMatrix b; b.Rows = Cols; b.Cols = Rows; b.Terms = Terms; If (Terms > 0) { for (i = 0; i < Cols ; i++) RowSize[i] = 0; for(I = 0 ; i<Terms ; i++) RowSize[smArray[i].col]++; // compute RowSize[i]= number of terms in row i of b  ادامه- الگوريتم ترانهاده ی سريع RowStart[0] = 0; for ( i=1;I <Cols; i++) RowStart[i] = RowStart[i-1]+ RowSize[i-1]; // RowStart[i] = starting position of row i in b; for( i = 1; i <Terms; i++) { j = RowStart [smArray[i].col] ++ ; b. smArray[j].row = smArray[i].col; b. smArray[j].com = smArray[i].row; b. smArray[j].value = smArray [i].value; } }// end if (Terms>0) delete [] RowSize; delete [] RowStart; return b;} سواالت؟ تحليل تابع ترانهاده سريع FastTranspose (قسمت )3-4-2 ضرب دو ماتريس اسپارس (قسمت )4-4-2 آيا ساختمان داده ديگري براي نمايش ماتريس اسپارس مي شناسيد؟ (سواالت 7و 8از تمرينات بخش )4-2 نمايش آرايه ها تعداد عناصر آرايه ‏aL1 U1 L2 U 2 Ln U n  ‏n ) (U  L 1 ‏i ‏i ‏i 1 چگونه مي توانيم عناصراين آرايه چند بعدي را در حافظه يك بعدي ذخيره سازي نماييم ؟ ( نگاشت از فضاي چند بعدي به يك بعدي ) نمايش آرايه ها -ادامه دو راه متداول :سطری و ستونی. آرایه دو بعدی ]a[u0][u1 – دارای u0سطربه نحوی که هر سطر شامل u1عنصر مي باشد (سطري) – دارای u1ستون به نحوی که هر ستون شامل u0عنصر مي باشد (ستوني) آدرس دهی سطري در آرایه دوبعدی ElementType A[u0][u1]; E=sizeof (ElementType) base address = α Variable Memory address A[0][0] α +(0 * u1+ 0)*E A[0][1] α +(0 * u1+ 1)*E … A[1][0] α +(1 * u1+ 0)*E … A[i][0] α +(i * u1 + 0)*E … A[i][j] α +(i * u1 + j)*E نمایش آرايه سه بعدی ‏Au1 u2 u3  u1 آرايه دوبعدی با ابعاد .u2*u3 تعيين مکان ]A[i][j][k – – – از مكان شروع ذخيره سازي ماتريس αبه تعداد iماتريس u2*u3 ذخيره شده استA[i][0][0] . حال jسطر u3عنصري در ادامه قرار گرفته استA[i][j][0] . از اين نقطه kعنصر جاي مي گيرد. آرايه سه بعدی فرمول کلی برای آرايه های چندبعدی A[u1][u2]………..[un] A[i1][i2]…[in] فرمول آدرس عنصر α +i1 u1 u2….un +i2 u2 u3….un . . +in-1 un +in a j n uk 1  j n k j 1    i j a j where   an 1 j 1 n ذخيره سازي ماتريسهاي خاص ذخيره سازي ماتريسهاي خاص - ادامه اين ماتريسها را مي توان نوع خاصي از ماتريس اسپارس دانست. ذخيره سازي عناصر غير صفر در يك آرايه يك بعدي جهت صرفه جويي در حافظه. ذخيره سازي ماتريسهاي خاص - ادامه ارائه فرمول نگاشت از فضاي دو بعدي به يك بعدي )k is index in array= f(i , j ‏k  i (i  1)  j 1 2 سواالت فرمول كلي ذخيره سازي ستوني آرايه هاي چند بعدي فرمول ذخيره سازي براي ماتريسهاي خاص (تمرينات 4تا 8 قسمت 2-8تمرين هاي تكميلي فصل )2 براي ذخيره سازي چندجمله اي ها و عمليانهاي ويژه آنها ساختمان داده اي مناسب طراحي كنيد ADT .مربوطه را بنويسيد ؟(بخش )3-2 رشته ها يک نوع داده ی ديگری که عناصر آن کاراکتر هستند. عملکردهای زيادی برای کار با رشته هاوجود دارد: – ايجاد يک رشته تهی – ضميمه کردن دو رشته به هم (, )concatenation – خواندن يا نوشتن يک رشته – کپی کردن يک رشته – مقايسه رشته ها – درج کردن يک زير رشته – برداشتن يک زير رشته از يک رشته مشخص.  رشته هاADT class String { //object: A finite ordered set of zero or more character public: String (char *init ,int m); int operator == (String t); int operator !();//if *this is empty return 1 int Length(); String Concate (String t); String Substr (int i, int j); int Find(String Pat); //Return on index I such that Pat matches the substring of *this that begins at position i. Return -1 is either empty or not a substring of *this. } تطابق الگو)1(pattern matching يک الگو يا يک زير رشته را در يک رشته بزرگتر جستجو کنيم. تست متوالی هر کاراکتر رشته تا زمان پيدا شدن الگو يا رسيدن به انتهای رشته ميباشد. اگر nطول رشته و mطول الگو باشد )O(mn تطابق الگو كنوث-موريس-پرات زمان اجرايي )O(m+n در بدترين حالت الزم است تمام كاراكترهاي داخل الگو و رشته حداقل يكبار با هم مقايسه شوند. بخش 2-6-2 پایان