ساختمان داده در C++
1- فصل اول:
نوع داده انتزاعي(مجرد): ADT : وقتي در برنامه ايي به نوعي داده نياز باشد كه در آن زبان وجود ندارد برنامه نويس بايد نوع مورد نظرش را ايجاد كند. نوع داده ايي را كه برنامه نويس ايجاد مي كند نوع داده انتزاعي مي گويند.
ADT يك مدل رياضي است كه عملياتي بر روي آن مدل تعريف مي شود. هرنوع داده متشكل از چند مقدار و مجموعه اي از عمليات بر روي آنها است.
مانند نوع داده int كه در زبان C عملياتهايي مانند * + - = / > < و غيره براي آنها تعريف شده است.
در اين درس انواع مختلفي از ADT ها را بوجود مي آوريم مانند آرايه ها و ماتريس ها و درخت ها و غيره
1-1-نحوه تجزيه و تحليل و سنجش كارايي يك برنامه:
تعريف : ميزان حافظه يا پيچيدگي فضاي يك برنامه مقدار حافظه مورد نياز براي اجراي كامل يك برنامه است. مقدار زمان يا پيچيدگي زماني يك برنامه مقدار زماني از كامپيوتر است كه براي اجراي كامل برنامه لازم است.
1-1-1- ميزان حافظه (پيچيدگي حافظه): فضاي مورد نياز براي يك برنامه شامل موارد زير است:
· بخش ثابت كه مستقل از بعضي خصيصه هاي ورودي و خروجي مانند تعداد وو اندازه است. اين بخش شامل فضاي دستورالعمل (كد برنامه) ، فضاي لازم براي متغيرهاي ساده و ثابت ها مي باشد
· بخش متغير كه شامل فضاي مورد نياز متغيرهاي ساختاري برنامه كه اندازه آن بستگي به نمونه مسئله ايي كه حل مي شود، دارد و فضاي لازم براي متغيرهاي مرجع كه اندازه آنها نيز به خصيصه هاي نمونه بستگي دارد و فضاي لازم براي پشته بازگشتي مي باشد.
1-1-2-پيچيدگي زماني:
زمان برنامه (T(P) ) مجموع زمان كامپايل و زمان اجراي برنامه است. زمان كامپايل براي يك برنامه فقط يك بار رخ مي دهد در ضمن به خصيصه هاي نمونه بستگي ندارد. بنابراين زمان اجرا يك برنامه Tpمورد بررسي قرار مي گيرد.
براي بدست آوردن زمان اجراي برنامه راه هاي مختلفي وجود دارد مثلا تعداد جمع ها و ضرب ها و تقسيمات و تفريقات يك برنامه را بدست آوريم و زمان را به صورت زير محاسبه كنيم:
Tp= C1ADD(n) + C2Sub(n) + C3Mul(n) + C4Div(n)
كه n نشان دهنده مشخصه هاي نمونه است. بدست آوردن چنين فرمول دقيقي يك كار غير ممكن است زيرا زمان مورد نياز براي جمع و ضرب و تفريق و تقسيم به عوامل متعددي بستگي دارد. در ضمن بين كامپيوتر هاي مختلف نيز متعدد است.
روش ديگري كه براي بدست آوردن پيچيدگي زماني يك برنامه استفاده مي شود اين است كه تعداد مراحل برنامه را بشماريم. پيچيدگي زماني يك برنامه را بر اساس تعداد مراحل آن بدست مي آوريم.
براي بدست آوردن تعداد مراحل يك برنامه با توجه به نوع دستورات عمل مي كنيم. مثلا دستورات انتساب را يك مرحله محسوب مي كنيم. دستورات تكرار را با توجه به تعداد تكرارشان محاسبه مي كنيم. دستورات تعريفي را جزء مراحل محسوب نمي كنيم. شرط IF را يك مرحله محسوب مي كنيم. ص 35 و 36
تعداد مراحل فراخواني يك تابع مساوي مجموع تعداد مراحل فراخواني هر تابع است.
يك از روشهايي كه براي محاسبه تعداد مراحل يك برنامه استفاده مي شود استفاده از متغيري به نام count است كه در ازاي هر مرحله Count++ مي شود.
|
Float Sum(Float *A , Const int n) { Float S=0; Int i; Count ++; For (I=0 ; I Count ++; S+ = A[ I ]; Count++; } Coumt++; // For Last time of for Return (S); Count++; } |
|
Float Sum(Float *A , Const int n) { Float S=0; Int i; For (I=0 ; I S+ = A[ I ]; Return (s); } |
كه پيچيدگي زماني آن 2n+3 است.
|
For ( I=0 ; I Count++; For ( J=0 ; J Count++; C[I][j]=A[I][j]+B[I][j]; Count++; } Count++; // For Last time of for } Count++; // For last time of for
|
|
For ( I=0 ; I For ( j=0 ; j C[I][j]=A[I][j]+B[I][j]; |
كه پيچيدگي زماني آن
2mn+2n+1 مي شود.
البته اين روش نيز چندان دقيق نيست. مثلا ما دستور A:=5*2+4 –B رايك مرحله مي گيريم و A:=8 را نيز يك مرحله مي گيريم در صورتيكه از نظر زماني با هم متفاوتند.
تعداد مراحل لزوما پيچيدگي جمله را منعكس نمي كند.
ولي در يك برنامه بزرگ مي توان تعداد مراحل را با كمي اغماض پيچيدگي برنامه دانست و مي توان برنامه ها را براساس پيچيدگي زماني آنها با هم مقايسه كرد.
روش ديگر در كتاب بحث شده است كه به روش S/e نام برده مي شود كه شباهت زيادي به روش Count دارد. ص41
تحقيق : پيچيدگي الگوريتم فيبوناچي 4n+1 است چرا؟
هدف از تعيين تعداد مراحل اين است كه بتوانيم پيچيدگي زماني دوبرنامه كه عمل مشابهي را انجام مي دهند مقايسه كنيم و همچنين بتوانيم ميزان افزايش زمان اجرا را وقتي مشخصات نمونه تغيير مي كنند پيشگويي كنيم.
مثلا اگر پيچيدگي زماني برنامه ايي 2n باشد و پيچيدگي زماني برنامة ديگريn2است كدام يك سريعتر است؟
البنه هر دوبرنامه يك الگوريتم است.
در مورد پيچيدگي زماني يك برنامه تعاريف رياضي(نشانه گذاري مجانبي) وجود دارد كه در اينجا به اختصار بحث مي شود تا بتوانيم عبارات با معني(ولي غيردقيق) در مورد پيچيدگي زماني يك برنامه بدست آوريم.
تعريف Big Oh : f(n) = O(g(n) است اگر و فقط اگر مقادير ثابتي مانند C و n0 باشد كه رابطه زير برقرار باشد:
f(n) ≤C g(n) براي تمام n≥n0
مثال) فرض كنيد f(n)=3n+2 باشد كه دراين صورت اگر n0=2 باشد و C=4 باشد و g(n)=n رابطه زير برقرار است
3n+2≤4 n
پس 3n+2=O(n)
البته مي توان g(n) هاي ديگري نيز پيدا كرد كه اين خاصيت را داشته باشند.
3n+2 ≤ n2
C=1 و n0=4
ولي معمولا تابعي را به عنوان g(n) در نظر مي گيرند كه از بقيه كوچكتر باشد.
n≤n2
f(n)=O(g(n)) فقط نشان مي دهد كه g(n) حد بالايي مقدار f(n) است براي تمام n≥n0
قضيه: اگرf(n)=amnm+…+a1n+a0در اين صورت f(n)=O(nm)
تمرين: نشان دهيد كه n! = O(nn)
تعريف امگا: f(n)=Ω(g(n)) اگر و فقط اگر به ازاي مقادير ثابت C و n0 رابطه f(n)≥C.g(n) براي n≥n0 هميشه برقرار باشد.
مثال) مثلا 3n+2≥3.n است در ازاي n≥1 3n+2= Ω(n)
10n2+4n+7≥n2 در ازاي n≥1 يعني 10n2+4n+7= Ω (n2) البته مي توان نوشت كه 10n2+4n+7= Ω (n)
اما معمولا تابعي را در نظر مي گيرند كه از بقيه بزرگتر باشد.
عبارت f(n)=Ω(g(n)) فقط نشان مي دهد كه g(n) يك حد پايين براي تابع f(n) است.
قضيه: اگرf(n)=amnm+…+a1n+a0در اين صورت f(n)= Ω (nm)
تعريف تتا: f(n)=θ(g(n)) است اگر و فقط اگر به ازاي مقادير c1 و c2 و n0 رابطه زير درست باشد
c1.g(n)≤f(n) ≤c2.g(n) در ازاي n≥n0
قضيه: اگرf(n)=amnm+…+a1n+a0در اين صورت f(n)= θ (nm)
نشانه گذاري تتا از امگا و Big oh دقيق تر است زيرا هم بعنوان كران بالا و هم بعنوان كران پايين f(n) مي باشد.
سئوالي كه مطرح مي شود اين است كه اين نشانه گذاري ها اگر يكي بخواهد دقيقا شمارش مراحل را انجام دهد، چه استفاده ايي دارد؟ پاسخ اين است كه پيچيدگي مجانبي(θ, Ω,O) بدون تعيين شمارش مراحل براحتي تعيين مي گردد.
|
Void ADD(int *a) { int I , j; For (I=0 ; I For (j=0 ; j C[I][j]=a[I][j]+b[I][j] //è θ(Rows.Cols) } |
حال حداكثر پيچيدگي زماني را به عنوان
پيچيدگي در نظر بگيريم يعني
θ(Rows.Cols)
بوسيله اين پيچيدگي ها مي توان دو برنامه را كه عمل يكساني را انجام مي دهند را با هم مقايسه كرد.
مثلا برنامه ايي كه O(n2) است و برنامه ايي كه O(2n) را با هم مقايسه مي كنيم. اگر n=10 باشد n2=100 و 2n=1024
مي شود.
فصل دوم: آرايه ها
از ديدگاه برنامه نويسان آرايه مجموعه ايي از خانه هاي پشت سر هم در حافظه است. ولي هميشه اين طور تصور نمي شود. اگر آرايه را به عنوان يك ADT در نظر بگيريم مجموعه اي از زوج هاي است طوري كه يك تناظر يك به يك بين انديس و محتواي سلول دارد.
آرايه را مي توان يك ADT با عمل هاي Stroe , Retrieve تعريف كرد به صورت زير:
|
#include #define Max 1024 class Array{ float Ar[Max]; int end; public: Array(int n){ end=n-1; } void store(int i, int value) { if (i>end){ printf("Error in index"); return;} else Ar[i]=value; } float Retrieve(int i) { if (i>end){ printf("Error in index"); return(0); } else return(Ar[i]); } } ;
|
تمرين: كلاس آرايه روبرو را به صورت زير كامل تر كنيد:
الف) تابعي بنويسيد كه اندازه آرايه را برگرداند.
ب) تابعي براي چاپ محتواي آرايه بنويسيد.
سربارگذاري عملگر:
عملگر = = براي بررسي تساوي دو داده ساده مانند int يا
Float و غيره استفاده مي شود. اما نمي توان اين عملگر را
براي نوع داده ساخته شده(ADT) استفاده كرد.
به عنوان مثال اكر كلاسي براي شي مستطيل تعريف كرده
باشيم نمي توانيم دو شي از اين كلاس را با عملگر = = مقايسه
كرد.
مي توانيم عملگر هاي را براي كلاس هايي كه تعريف مي كنيم
سربارگذاري كنيم. يعني مثلا عملگر تساوي نيز براي دو شي
مستطيل بكار رود و درصورتي كه دو مستطيل با هم برابر باشند
يك برگرداند و درغير اين صورت صفر برگرداند.
اين عمل را مي توان براي عملگرهاي ديگر مانند + يا >> و غيره انجام داد.
#include
#define Max 1024
class Rectangle{
int x1,x2,y1,y2;
public:
set(int a1,int b1,int a2,int b2)
{
x1=a1; x2=a2;
y1=b1; y2=b2;
}
operator==(const Rectangle &s)
{
if (this==&s) return 1;
if ((x1==s.x1) && (y1==s.y1) && (x2==s.x2) &&(y2==s.y2))
return 1;
else
return 0;
}
};
void main()
{
Rectangle m,n;
m.set(1,2,3,4);
n.set(1,2,3,4);
if (m==n)
printf("Yes\n");
else
printf("No\n");
}
تمرين الف: برايADT آرايه يك عملگر = = براي تساوي دو آرايه تعريف كنيد.
تمرين ب : براي ADT آرايه يك عملگر + جهت جمع محتواي دو آرايه با طول يكسان تعريف كنيد.
نمايش چند جمله ايي ها بوسيله آرايه: amXm+am-1Xm-1+…+a0
سه روش مختلف را براي نمايش چند جمله ايي ها بحث مي كنيم.
الف) يك روش به اين صورت است كه يك آرايه به اندازه MaxDegree تعريف كنيم و MaxDegree بزرگ ترين درجه چندجمله ايي است.
Class Polynomial{
Int degree;
Float coef[MaxDegree+1];
|
|
|
|
|
|
|
a.degree=n;
با اين نحوه نمايش الگوريتمهاي بسيار ساده براي بسياري از اعمال چندجمله اي(جمع و تفريق و …) بدست مي آوريم. اما اين روش از نظر حافظه بسيار ضعيف عمل مي كند زيرا براي همه اشيا اين كلاس يك آرايه به طول Maxdegree استفاده مي شود. مثلا براي چند جمله ايي درجه 2
ب)روش دوم استفاده از حافظه پويا براي ايجاد يك آرايه با طول مشخصي(درجه چند جمله ايي) است.
Cofe=new float[degree+1];
اين روش نيز معايبي دارد مثلا براي نمايش يك چند جمله ايي خلوت(Sparce) فضاي اضافي تخصيص داده مي شود مانند X1000+1
ج) روش سوم: در اين روش يك آرايه به طول MaxDegree براي همه چند جمله اي ها تعريف مي شود.
Private:
Static Ar[MaxTerm , 2];
Static int free;
Int start, finish;
مثلا براي نمايش دادن دو چند جمله ايي A(x)=2X1000+1 و B(x)=X4+3X2+4X+8 به صورت زير عمل مي كنيم.
|
|
|
|
|
8 |
4 |
3 |
1 |
1 |
2 |
|
|
|
|
|
0 |
1 |
2 |
4 |
0 |
1000 |
نكته ايي كه در اين روش وجود دارد اين است كه يك آرايه Ar براي همه اشيا اين كلاس استفاده مي شوند و همگي يك متغيرFree دارند كه انتهاي آرايه را مشخص مي كند و هركدام از چند جمله ايي ها داراي يك Start و يك finish هستند.
عيب اين روش اين است كه الگوريتمهاي اعمال چند جمله ايي ها مانند جمع و … ساده نيست. درضمن اگر يك شي از بين برود بايد بقيه اشيا شيفت به چپ داشته باشند.
پروژه: روش سوم نمايش چند جمله اي ها را پياده سازي كنيد. در پياده سازي بايد بتوان حاصل جمع دو چند جمله اي را محاسبه كرد. ص 84
ADT ماتريس اسپارس:
ماتريس اسپارس ماتريسي است كه بيشتر عناصر آن صفر است و تعداد اندكي از عناصر آن غير صفر است. به عنوان مثال يك ماتريس 1000×1000 را در نظر بگيريد كه فقط 100 عنصر غير صفر داشته باشد.
معمولا براي نمايش ماتريس آرايه دو بعدي استفاده مي شود اما براي ماتريس اسپارس استفاده از اين روش كارآمد نيست زيرا فضاي بسيار زيادي از حافظه هدر مي شود.
در بيشتر مسائل اطراف ما ماتريس اسپارس ديده مي شود به عنوان مثال يك تصوير سياه و سفيد كه بيشتر تصوير سياه باشد را مي توان يك ماتريس اسپارس در نظر گرفت.(مانند تصاوير راديولوژي)
ترانهاده ماتريس |
ماتريس |
|
در نمايش سطري نمايش ماتريس اسپارس ماتريس
بر اساس سطرها مرتب است.
ترانهاده يك ماتريس اسپارس:
ترانهاده يك ماتريس يعني جاي سطرها و ستونهاي آن را عوض كنيم.
براي نحوه نمايش ماتريس اسپارسي كه بحث شد(سطري) بايد وقتي جاي سطرها و ستونها را تغيير داديد برحسب سطر ها (كه حال همان ستونها هستند)مرتب كنيد.
اگر ماتريس اسپارس را به صورت آرابه دو بعدي ذخيره كنيم براي جابجا كردن سطرها و ستونها زماني معادل O(Rows.Cols) نياز است كه بسيار زياد است.
اما اگر ماتريس اسپارس به صورت سه گانه ها (سطري) ذخيره شود با يك الگوريتم مناسب مي توان ترانهاده آن را محاسبه كرد كه داراي پيچيدگي زماني O(Terms.Columns) خواهد بود. Terms نشان دهنده تعداد عناصر غير صفر در ماتريس اسپارس است.
For (all elements in Column j)
Place element (I , j , Value) in position (j, I ,Value)
اين حلقه نشان مي دهد كه تمام عضوهاي ستون 0 را پيدا كرده و آنها را سطر 0 ذخيره مي كند و سپس تمام عضوهاي ستون 1 را پيدا كرده و آنها را در سطر 1 ذخيره مي كند و …
البته در صفحه 93 كتاب روش بهتري براي اينكار نوشته شده است كه داراي پيچيدگي زماني O(cols+Rows) است.
ضرب ماتريس اسپارس:
حاصل ضرب دو ماتريس اسپارس لزوما اسپارس نيست.
|
|
|
حاصل ضرب دو ماتريس از ضرب سطرها در ستونها بدست مي آيد. اگر دوماتريس اسپارسA,B را به صورت سه گانه ها (سطري)ذخيره كنيم براي محاسبه A*B ابتدا ترانهاده ماتريس B را به روشي كه بحث شد بدست آوريم حال مي توانيم سطرها را در ستونها ضرب كنيم. دليل اين كار اين است كه اگر براي پيدا كردن ستون J در ماتريس B بايد كل سه گانه ها پويش (جستجو) شود اما وقتي ترانهاده B بدست مي آيد عناصر ستون J كنار هم قرار مي گيرند.
در صفحه 96 كتاب برنامه ضرب دو ماتريس اسپارس نوشته شده است؟
تحقيق: پيچيدگي زماني اين برنامه را پيچيدگي زماني برنامه ضرب معمولي دو ماتريس مقايسه كنيد؟
تمرين: برنامه ايي بنويسيد كه دو ماتريس اسپارس هم درجه را دريافت كند و با هم جمع بزند و نمايش دهد؟
نمايش آرايه هاي چند بعدي:
آرايه هاي چند بعدي معمولا با ذخيره عناصر در يك آرايه يك بعدي پياده سازي مي شوند.
به عنوان مثال ماتريس را مي توان يك آرايه يك بعدي در نظر گرفت.
|
2,3 |
2,2 |
2,1 |
2,0 |
1,3 |
1,2 |
1,1 |
1,0 |
0,3 |
0,2 |
0,1 |
0,0 |
آرايه بالا مي تواند نشان دهنده يك ماتريس 4×3 باشد.
|
A[1][2]= A + 2 + 1*5 A[1][3] = A+ 3 + 1*5 A[2][4] = A+ 4 + 2*5 A[6][2] = A+ 2 + 6*5
A[X][Y] = A + Y +X*N N è Number of Columns |
|
A[0][1]= A+1+0*5
A[0][2]= A+2+0*5
A[0][4]= A+4+0*5
A[1][0]= A+0+1*5
A[1][1]= A+1+1*5
ADT رشته ها:
رشته در واقع آرايه اي از نوع char است و مي توان براي ADT آن عملياتهايي مانند ايجاد يك رشته تهي جديذ، خواندن و نوشتن رشته، كپي كردن رشته، مقايسه رشته ها، درج يك رشته داخل رشته ديگر،پيداكردن يك الگو در يك رشته و غيره .
در زبان C رشته ها به صورت آرايه از كاراكترها كه به كاراكتر \0 ختم مي شوند نمايش داده مي شوند.
تمرين: برنامه ايي بنويسيد كه دو رشته را دريافت كند و با هم مقايسه كنددرصورت بزرگتر بودن رشته اولي 1 و در صورت كوچك تر بودن رشته اولي –1 درصورت مساوي بودن صفر برگرداند.
تطابق الگو:Pattern Matching
دو رشته را دريافت كرده ايم و مي خواهيم رشته دومي را در اولي جستجو كنيم.
يكي از اين روشها(راحترين و غير موثرترين) اين است كه هر كاراكتر رشته را تا زمان پيدا شدن الگو و يا رسيدن به انتهاي رشته تست متوالي كنيم. S1=’aabbaababbabc’ , S2=’aba’
اين روش داراي زمان محاسباتي O(n.m) است كه n,m طول رشته S1 و S2 است.
اما روش ديگري براي پيدا كردن الگو وجود دارد كه به الگوريتم كنوث،موريس و پرات معروف است.ص 108
|
Int nfind (char *string , Char *pat) { int I,j,start=0; int lasts=strlen(string)-1; // انتهاي رشته اولي را مشخص مي كند int lastp=strlen(pat)-1 ; // انتهاي رشته دومي را مشخص ميكند int endmatch=lastp; for (I=0 ; endmatch<=lasts ; endmatch++ , start++) { if (string[endmatch]=pat[lastp]) for (j=0 , I=start ; j ; if (j=lastp) return(start); } return -1; } |
در واقع در اين الگوريتم هر گاه انتهاي رشتة
Pat با محل مقايسه String مطابق شد به اندازه
طول رشته Pat مقايسه انجام مي شود.
فصل سوم: پشته ها و صف ها
پشته (stack) نوعي ADT است كه به نام LIFO معروف است. معروفترين پشته كه كاربرد زيادي نيز دارد پشته سيستم است كه براي فراخواني توابع در زمان اجرا استفاده مي شود.(در دروس برنامه سازي بحث شده است.)
Template در زبان C++:
قبلا وقتي يك كلاس در زبان C تعريف مي شد همه اجزا ان داراي يك نوع خاصي بودند براي اينكه اين نوع ها تغيير كنند لازم است كه كد كلاس تغيير كند. به عنوان مثال وقتي يك آرايه int را براي نمايش چند جمله اي ها تعريف مي كنيد،ضرايب معادله فقط مي توانند int باشند حال اگر بخواهيد ضرايب اعشاري نيز داشته باشيد بايد كلاس مربوط به چند جمله اي ها را تغيير دهيد و يا يك كلاس ديگر بنويسيد.
اما با استفاده از خاصيت template مي توانيد اين مشكل را حل كنيد.
|
Template Class Array { mytype F; mytype A[20];
public: viod store(mytype h , int index) { A[index]=h; } mytype retrieve(int index) { F:=A[index]; Return F; } } // end of class viod main() { Array M1; Array M2; Array M3; } |
آرايه A براي شي M1 از نوع float و براي M2 از نوع
char و براي M3 از نوع int خواهد بود.
براي پياده سازي يك ADT پشته مي توان از يك آرايه ثابت استفاده كرد. و عملياتهايي مانند empty،Full ، Push , Pop و Top را تعريف كرد.
يكي از موارد استفاده پشته ارزيابي يك عبارت است. براي اين كه بتوان عبارات را ارزيابي كرد ابتدا آنها را به روش PreFix تبديل مي كنيم. مثلا a+b را به صورت +ab مي نويسيم.
مثال: 5 -7 * 2 * (4-2) / 8
- 5 / * - 4 2 * 7 2 8
بوسيله دو پشته مي توان برنامه ايي نوشت كه حاصل عبارت بالا را محاسبه
كند.
پياده سازي ADT براي يك پشته:
#include
#include
#define MAX 127
templateclass stack
{
private:
int ptr;
eltype item[MAX];
public:
stack(void)
{
ptr=0;
}
int empty(void)
{
return(ptr==0);
}
int full(void)
{
return(ptr==MAX);
}
void push(const eltype element)
{
if(full())
{
cout<<"\n stack is full !!! run again program \n";
exit(0);
}
else
item[ptr++]=element;
}
eltype pop(void)
{
if(empty())
return(0);
else
return(item[--ptr]);
}
eltype top(void)
{
eltype element;
element=pop();
push(element);
return(element);
}
};
برنامه ايي بنويسيد كه با استفاده از پشته طراحي شده حاصل عبارت Prefix را محاسبه كند.
|
#include"stack.hpp" #include #include #include #include #include #include #define MAX 127 void main() { float a,b,c; stack s1; stack s2; char s[MAX]; int i=0; gets(s); while (s[i]!='\0'){ if ((s[i]>=48) && (s[i]<=57)) s1.push(s[i]-48); else s1.push(s[i]); i++; } //*****************
|
|
while (!s1.empty()) { while ( (!s1.empty() ) &&( ((s1.top()!='+') && (s1.top()!='*') && (s1.top()!='-') && (s1.top()!='%') && (s1.top()!='/')))) { s2.push(s1.pop()); } c=s1.pop(); if (c=='+') { a=s2.pop(); b=s2.pop(); s1.push(a+b); }else if (c=='*') { a=s2.pop(); b=s2.pop(); s1.push(a*b); }else if (c=='-') { a=s2.pop(); b=s2.pop(); s1.push(a-b); }else if(c=='/') { a=s2.pop(); b=s2.pop(); s1.push(a/b); }else if (c=='%') { a=s2.pop(); b=s2.pop(); s1.push(int(a)%(int)b); }; } cout< }
|
در اين برنامه فرض شده است اعداد تك رقمي هستندو فقط + * / % عملگر هستند.
مثال: 8 + (9 –2) % 5 * 2 + (4 –2 ) ç + + 8 * % - 9 2 5 2 – 4 2
اگر اين عبارت به برنامه بالا داده شود حاصل 14 خواهد شد.
ADT صف : (QUEUE)
صف نوعي ADT است كه به عنوان FIFO معروف است. اولين عضوي كه وارد مي شود اولين عنصري است كه از ليست خارج مي شود. براي پياده سازي آن مي توان از يك آرايه ثابت استفاده كرد.
در زير يك كلاس جهت پياده سازي Queue نوشته شده است. متغير tail هميشه سرصف را نمايش مي دهد.
#include
#include
#define MAXQEUE 200
templateclass Qeue{
int tail;
Mytype store[MAXQEUE];
public:
//************************************
void Qeue()
{
tail=0;
}
//*************************************
void Addqeue(Mytype elmnt)
{
if(Isfull())
{
cout<<"\n Qeue is full !!! \n";
return;
}
else
store[tail++]=elmnt;
}
//************************************
Mytype Exitqeue()
{
int Cntqeue;
Mytype Tmp;
if(!Isempty())
{
for(Cntqeue=0;Cntqeue
store[Cntqeue]=store[Cntqeue+1];
--tail;
return(Tmp);
}
else
cout<<"\n Qeue is empty !!! \n";
}
//*********************************
int Isempty()
{
return(tail==0);
}
//*******************************
int Isfull()
{
return(tail==MAXQEUE);
}
} // end class
يكي از معايب اين روش اين است كه با خارج شدن يك عضو از صف بقيه داده ها شيفت پيدا مي كنند و روش موثري نيست. براي حل اين مشكل مي توان يك آراية حلقوي را به عنوان صف طراحي كرد.
تمرين :كلاسي بنويسيد كه يك صف حلقوي را با عملياتهاي ذكر شده در كلاس بالا پياده سازي كند.
مساله مسير پرپيچ و خم (Mazing):
ارزشيابي عبارات:
اولين كاري كه بايد براي ارزيابي مقدار يك عبارت انجام دهيم انتخاب يك ترتيب براي اعمال است.
روش استانداردي كه براي ارزيابي عبارات به كار مي رود روش infix (ميانوندي) است. زيرا در اين روش علموند ها ميان عملگر قرار مي گيرند. روش ديگري كه براي ارزيابي عبارات استفاده مي شود روش Postfix (پسوندي) ا ست كه در اين روش ابتدا دو عملوند و سپس عملگر ظاهر مي شود مثال: A+B*C ç ABC*+
نمادگذاري پسوندي خصوصياتي دارد كه باعث سادگي ارزيابي عبارت ها مي شود1- احتياجي به پرانتز ندارد 2- به اولويت عملگرها كاري ندارد.
ليست ها:
ليست تك پيوندي :
ليست هاي پيوندي گره هاي متوالي هستند كه به صورت فلش هايي(اشاره گرها) به هم متصل هستند.
نكاتي كه بايد در مورد گره ها مي توان استباط كرد اين است كه الف) گره ها واقعا پست سرهم در حافظه نيستند
ب) موقعيت گره ها در هر بار اجرا مي تواند تغيير كند.
|
struct Node{ int code; char name[20]; float avg; struct Node *Next; }; struct Node *Start;
|
malloc براي تخصيص حافظه و free براي از بين بردن حافظه تخصيص
داده شده استفاده مي شود.
در تكه برنامه روبرو يك ساختار براي هر گره تعريف شده است
و سپس اشاره گر ابتداي ليست (Start) تعريف شده است.
يك ليست پيوندي مي تواند يك ADT تلقي شود كه داراي عملياتهايي مانند ADDToList و RemoveNode و SearchList و NumberNode و DeleteList و غيره باشد.
|
void AddToList() { if (Start==NULL) { Start=(struct Node *)malloc(sizeof(Node)); cout<<"Enter Code , Name , Avg"; cin>>Start->code>>Start->name>>Start->avg; Start->Next=NULL; } else { struct Node *PTR; PTR=(struct Node *)malloc(sizeof(Node)); cout<<"Enter Code , Name , Avg"; cin>>PTR->code>>PTR->name>>PTR->avg; PTR->Next=Start; Start=PTR; } }
|
براي اضافه كردن به انتهاي ليست بايد ابتدا از اول ليست تا انتهاي ليست راپيمايش كرد و سپس گره جديد را به انتها متصل كرد اين كاررا مي توانيد به عنوان تمرين انجام دهيد.
حذف كردن يك گره بخصوص از ليست:
struct Node * SearchList(int code)
|
ابتدا گره ايي كه قرار است حذف شود را Search مي كنيم البته بايد آدرس گره قبلي را نيز داشته باشيم تا بتوانيم پيوند را برقرار كنيم. و بايد حالت خاصي كه گره اول حذف شود را نيز بررسي كنيم. |
struct Node *LINK;
LINK=Start;
while ((LINK!=NULL) && (LINK->code!=code))
LINK=LINK->Next;
if (LINK==NULL)
return(NULL);
else
return(LINK);
}//*****************************
void RemoveNode(int code)
{
struct Node *PTR,*LastPTR;
PTR=SearchList(code);
if (PTR==NULL) return;
if (PTR==Start)
{//حالتي كه ممكن است گره اول حذف شود
Start=PTR->Next;
free(PTR);
return;
}
LastPTR=Start;
while (LastPTR->Next!=PTR)
LastPTR->Next;
LastPTR->Next=PTR->Next;
free(PTR);
}
مثال ) برنامه اي بازگشتي بنويسيد كه ليست تك پيوندي را معكوس كند؟
|
struct Node * Inverse(struct Node *Last,struct Node *First) { struct Node *temp; if(First->Next==NULL) { First->Next=Last; Last->Next=NULL; return(First); } else { temp=Inverse(First,First->Next); if (First->Next ==NULL) { First->Next=Last; Last->Next=NULL; } return(temp); } // end else }
|
تابع پارامترهاي
Start,Start
تحويل داده خواهد شد.
تكليف: برنامه ايي بنويسيد كه ابتداي دوليست پيوندي را دريافت كند و با يكديگر Merge كند.
پياده سازي پشته و صف بوسيله ليست هاي تك پيوندي:
در فصل قبلي پشته و صف را با آرايه ها پياده سازي كرديم كه يكي از معايب اين روش اتلاف فضا است. با توجه به اينكه تعداد گره ها در يك ليست پيوندي متغير است ميتوان به جاي آرايه از يك ليست پيوندي براي نمايش صف و پشته استفاده كرد.
|
Top |
|
Front |
|
Rear |
پروژه درسي: يك Stack با عملياتهاي قبلي ولي با حافظه پويا و ليست پيوندي را پياده سازي كنيد.
نمايش چند جمله اي ها بصورت ليست تك پيوندي:
براي نمايش چند جمله اي ها مي توان از يك ليست پيوندي استفاده كرد و هر گره مي تواند داراي فيلدهاي ضريب(Coef) و توان(Expon) باشد. مثلا a=3x14+2x8-3x2+1
|
|
|
|
براي جمع كردن دو چند جمله ايي بايد دو ليست را نشان دهنده چند جمله ايي ها هستند را با يكديگرMerge كرد البته گره هايي كه ضريب يكسان دارند با هم جمع مي شوند.
معمولا در برنامه ها حذف كردن يك گره (Free) و اضافه كردن به گره ها(Malloc) بسيار كند انجام مي شود به همين دليل راهي به صورت زير ارائه مي شود: هنگامي كه مي خواهيم از يك ليست پيوندي گره ايي را حذف كنيم آن را Free نمي كنيم بلكه يك ليست به نام DeleteNode ايجاد كرده گره را از ليست اصلي برداشته و داخل اين ليست قرار مي دهيم. هنگامي كه مي خواهيم يك گره جديد اضافه كنيم در صورتي كه ليست DeleteNode تهي نباشد گره ايي از ان را برداشته و دوباره به ليست اصلي اضافه مي كنيم و در صورتي كه DeleteNode تهي باشد آنگاه Malloc مي كنيم.
ليستهاي تك پيوندي حلقوي:
ليست پيوندي كه انتهاي آن به ابتداي متصل باشد را حلقوي مي گويند.
|
Start |
عمل درج در ليست حلقوي و در ابتداي ليست كمي مشكل است زيرا گره آخري نيز بايد به روز شود به همين دليل معمولا عمل اضافه كردن گره بين گره اول و گره دوم انجام مي شود.
عمل حذف يك گره نيز ممكن است دردسر آفرين باشد و آن زماني است كه بخواهيم گره اول را حذف كنيم.
براي شمارش تعداد گره هاي يك ليست حلقوي چه راه حلي را پيشنهاد مي دهيد؟
نمايش ماتريس اسپارس بوسيله ليست هاي پيوندي:
|
در شكل روبرو نحوة اتصال گره هاي
هر ستون و هر سطر نمايش داده شده است.
البته كامل نيست آنرا كامل كنيد؟
هر سطر يك ليست پيوندي حلقوي است
و هر ستون نيز يك ليست پيوندي حلقوي است.
ليستهاي پيوندي دو گانه:
|
Struct Node { int Code; char name[10]; Struct Node * Last; Struct Node * Next; }; |
آدرس گره قبلي را داشته باشيم تا بتوانيم آن گره را آزاد كنيم كه پيدا كردن گره
قبلي مستلزم پيمايش ليست بود اما براي ليست هاي پيوندي دو گانه لازم به اين
كار نيست.
برنامه هاي نوشته شده در زير جهت اضافه كردن يك گره به ابتداي ليست و حذف كردن
يك گرة بخصوص از ليست پيوندي دو گانه است:(با فرض اينكه گرة Start يك گرة سراسري است)
|
Void Insert(void ) { if (Start==NULL) { Start=(struct Node *) malloc(sizeof(Node)); Cin>> Start -> Code >> Start ->Name; Start->Next=Start->Last=NULL; } else { struct Node * Ptr; Ptr=(struct Node *) malloc(sizeof(Node)); Cin >> Ptr->Code >> Ptr->Name; Ptr->Next=Start; Start->Last=Ptr; Ptr->Last=NULL; Start=Ptr; } } |
|
Void delete(struct Node * Ptr) { if (Ptr==Start) {گره ايي كه حذف مي شود گره اول باشد// Ptr->Next->Last=NULL; Start=Ptr->Next; Free(Ptr); } else { Ptr->Last->Next=Ptr->Next; Ptr->Next-Last=Ptr->Last; Free(Ptr); } }
|
تمرين) برنامه ايي بنويسيد كه يك ليست پيوندي دو گانه را معكوس كند؟
ليست هاي ناهمگن:
ليست هايي كه تا حال بررسي كرده ايم گره هاي آنها از نوع Struct بودند و همه گره ها از نظر نوع با هم يكسان بودند.حال اگر ليست پيوندي ايجاد كنيم كه گره هاي آن با هم متفاوت باشند ليست پيوندي ناهمگن بوجود مي آيد براي اين كار مي توان بجاي استفاده از Struct از union ها استفاده كرد.
مطالب مشابه :
ترانهاده كردن ماتريس اسپارس
تکنیک های پیشرفته کامپیوتر - ترانهاده كردن ماتريس اسپارس - ترانهاده كردن ماتريس
بردار و ماتریس در متلب
ترانهاده کردن ماتریس با تک کوتیشن انجام می تبدیل یک ماتریس تقریبا خالی به ماتریس اسپارس :
ساختمان داده در C++
ترانهاده يك ماتريس اسپارس: ترانهاده يك ماتريس يعني جاي سطرها و ستونهاي آن را عوض كنيم.
آرم کافی نت جگوار
كافي نت جگوار گچساران - آرم کافی نت جگوار - سرعت- امنيت- كيفيت- آرامش - با خطوط پرسرعت adsl
دانلود چندین برنامه برای درس ساختمان داده ها
الگوریتم تبدیل ماتریس پایین مثلثی ضرب دو ماتریس اسپارس ایجاد ترانهاده یک ماتریس
نمونه سوالات ساختمان داه استاد شمس الدینی
16- الف ) ماتریس اسپارس روبرو را به شکل ویژه نمایش دهید .ب) ترانهاده آن را بیابید .ج)
برچسب :
ترانهاده ماتریس اسپارس