ساختمان داده ها و الگوریتم
جلسه چهارم
تبدیل عبارت infix به post fix
فرض کنید عملگر op1 در عبارت infix قبل از عملگر op2 ظاهر شده باشد:
در این صورت تابع :
prcd ( op1 , op2 )
در صورتی که اولویت عملگر op1 از اولویت عملگر op2 بیشتر باشد مقدار true را بر می گرداند و در غیر این صورت مقدار false را بر می گرداند .
مثال
a + b - c : prcd ( + , - ) True
a + b * c : prcd ( + , * ) False
a / b / c : prcd ( / , / ) True
a $ b $ c : prcd ( $ , $ ) False
تبدیل infix به post fix :
infix = a + b * c $ d
post fix = a b c d $ * +
برای این کار عبارت از سمت چپ به راست ارزیابی می شود اگر symbol مورد نظر عملوند بود آن را در خروجی چاپ می کنیم و به سراغ symbol بعدی می رویم ، اگر symbol عملگر بود تا زمانی که پشته خالی نشده یا نتیجه تابع :
prcd ( top , عملگر جاری )
true باشد از پشته pop می کنیم و در خروجی چاپ می کنیم ، بعد از این مرحله در صورت false شدن prcd عملگر را درون stack قرار می دهیم ، زمانیکه به پایان عبارت رسیدیم کل محتویات پشته را pop کرده و چاپ می کنیم .
s = the empty stack
while ( ! end of infix expression )
{
rd = next symbol ;
if ( is operand ( rd) )
cout<< rd ;
else
{
while ( ! empty (s) && prcd ( top (s) , rd ) == true )
cout << pop ( s ) ;
push ( s , rd ) ;
}
}
while ( !empty (s) )
cout << pop ( s ) ;
homework 1
برنامه فوق را به گونه ای تغییر دهید که عبارتهای شامل پرانتز را از infix به post fix تبدیل کند .
تبدیل infix به prefix :
برای این الگوریتم کافی است از الگوریتم تبدیل infix به post fix استفاده کنیم ، با این تفاوت که بایستی عبارت را از آخر به اول ارزیابی کنیم و هر جا ")" بود "(" در نظر بگیریم ، و هر جا "(" بود ")" در نظر بگیریم ، در نهایت عبارت به دست آمده را برعکس کرده و چاپ می کنیم .
homework 2
شبه کد الگوریتم بالا را بنویسید .
پیاده سازی پشته توسط آرایه
آرایه item :
| max s-1 | ......... | 2 | 1 | 0 | نام خانه آرایه |
| ......... | 3 | 2 | 1 | مقدار |
پشته s :
| 3 |
| 2 |
| 1 |
در این مثال
نام آرایه : item
نام پشته : s
منظور از max s مقدار ظرفیت پشته s می باشد .
push
push ( s , x )
{
if ( ! full ( s ) )
{
s . top ++ ;
s . item [ s . top ] = x
}
}
full
full ( s )
{
if ( s . top == max s - 1)
return true ;
else
return false ;
}
pop
pop ( s )
{
if ( ! empty ( s ) )
{
x = s . item [ s . top ] ;
s . top -- ;
return x ;
}
}
empty
empty ( s )
{
if ( s . top == -1 )
return true ;
else
return false ;
}
top
top ( s )
{
if ( ! empty (s) )
{
x = s . item [ s . top ] ;
return x ;
}
}
پیاده سازی پشته توسط آرایه در ++C :
با این برنامه می توان n عدد را گرفته و برعکس چاپ کرد .
با این برنامه می توان n عدد را گرفته و برعکس چاپ کرد .
class sstack
{
private :
int maxsize ;
int top ;
int * item s ;
void stack full ( ) { cout << " stack overflow " ; exit ( 1 ) ; }
void stack empty ( ) { cout << " stack underflow " ; exit ( 1 ) ; }
public
sstack ( int max stack =100 ) ;
~ sstack ( ) ;
bool empty ( ) { return ( top == -1 ) ; }
bool full ( ) { return ( top == maxsize -1 ) ; }
void push ( int ) ;
int pop ( ) ;
int stack top ( ) ;
} ;
sstack : : sstack ( int ms )
{
maxsize = ms ;
item = new int [ ms ] ;
top = -1 ;
}
~ sstack : : sstack ( )
{
delete [ ] item ;
}
void sstack : : push ( int x)
{
if ( full ( ) )
stack full ( ) ;
else
{
top ++ ;
item s [ top ] = x ;
}
}
int sstack : : pop ( )
{
if ( empty ( ) )
stack empty ( ) ;
else
{
int x ;
x = item s [ top ] ;
top -- ;
return x ;
}
}
int sstack : : top ( )
{
if ( empty ( ) )
stack empty ( ) ;
else
next item s [ top ] ;
}
main ( )
{
int n , x ;
cin >> n ;
sstack s ( n ) ;
for ( int i=0 ; i < n ; i ++ )
{
cin >> x ;
s . push ( x ) ;
}
while ( ! s . empty ( ) )
{
x = s . pop ( ) ;
cout << x ;
}
}
توضیحات :
{
private :
int maxsize ;
int top ;
int * item s ;
void stack full ( ) { cout << " stack overflow " ; exit ( 1 ) ; }
void stack empty ( ) { cout << " stack underflow " ; exit ( 1 ) ; }
public
sstack ( int max stack =100 ) ;
~ sstack ( ) ;
bool empty ( ) { return ( top == -1 ) ; }
bool full ( ) { return ( top == maxsize -1 ) ; }
void push ( int ) ;
int pop ( ) ;
int stack top ( ) ;
} ;
sstack : : sstack ( int ms )
{
maxsize = ms ;
item = new int [ ms ] ;
top = -1 ;
}
~ sstack : : sstack ( )
{
delete [ ] item ;
}
void sstack : : push ( int x)
{
if ( full ( ) )
stack full ( ) ;
else
{
top ++ ;
item s [ top ] = x ;
}
}
int sstack : : pop ( )
{
if ( empty ( ) )
stack empty ( ) ;
else
{
int x ;
x = item s [ top ] ;
top -- ;
return x ;
}
}
int sstack : : top ( )
{
if ( empty ( ) )
stack empty ( ) ;
else
next item s [ top ] ;
}
main ( )
{
int n , x ;
cin >> n ;
sstack s ( n ) ;
for ( int i=0 ; i < n ; i ++ )
cin >> x ;
s . push ( x ) ;
}
while ( ! s . empty ( ) )
{
x = s . pop ( ) ;
cout << x ;
}
class
الگویی که شامل متغییر و تابع است و با آن می توان اشیا را تولید کرد .
private
فقط اشیا خاص به آن دسترسی دارند.
maxsize
حداکثر طول پشتهtop
بالای پشتهpublic
همه اشیا به آن دسترسی دارند.
sstack
سازنده~
مخربbool
جهت مقایسه به کار می بریم.
sstack : : sstack ( int ms )
sstack اول اسم کلاس و sstack دوم اسم پشته می باشد.
item = new int [ ms ] ;
به طول عددی که گرفته ایم ( ms ) آرایه درست می کند.
top ++ ;
top را یک خانه به جلو می برد .
sstack s ( n ) ;
یک شی به نام s از کلاس sstack تعریف و عدد n را برایش فرستادیم .
جلسه پنجم
* در کل مثال های این جلسه نام آرایه items می باشد .
صف ( queue )
توابع بخش queue :
جلسه پنجم
* در کل مثال های این جلسه نام آرایه items می باشد .
صف ( queue )
مجموعه ای مرتب از اقلام داده ها است که درج عنصر جدید در آن از یک طرف و حذف عناصر از طرف دیگر انجام می گیرد ، پس عنصری که قبل از بقیه وارد شده ، قبل از بقیه عناصر خارج می شود .
ساختار queue به صورت FIFO به معنی First in First out می باشد .
ساختار queue به صورت FIFO به معنی First in First out می باشد .
توابع بخش queue :
empty : این تابع مقدار true را بر می گرداند اگر queue خالی باشد و در غیر این صورت مقدار false را بر می گرداند .
full : این تابع مقدار true را بر می گرداند اگر queue پر باشد و در غیر این صورت مقدار false را بر می گرداند .
( insert ( q , x : این تابع متغییر x را در انتهای صف غیر پر ( q ) قرار می دهد .
( x = remove ( q : این تابع عنصر موجود در ابتدای صف غیر خالی ( q ) را حذف کرده و درون x قرار می دهد .
چند نمونه از کاربردهای صف :
1- صف تشکیل شده از اطلاعات ارسالی هنگام چاپ کردن اطلاعات .
2- صف موجود در صفحه کلید .
3- شبیه سازی صف های معمولی .
مثال : شبه کدی که بزرگترین عنصر موجود در یک صف را به انتهای صف ببرد :
چند نمونه از کاربردهای صف :
1- صف تشکیل شده از اطلاعات ارسالی هنگام چاپ کردن اطلاعات .
2- صف موجود در صفحه کلید .
3- شبیه سازی صف های معمولی .
مثال : شبه کدی که بزرگترین عنصر موجود در یک صف را به انتهای صف ببرد :
send max to end ( q1 )
{
if ( empty ( q1 ) )
return ;
else
}
max = remove ( q1 ) ;
insert ( q2 , max ) ;
while ( ! empty ( q1 ) )
{
x = remove ( q1 ) ;
if ( x > max )
max = x ;
insert ( q2 , x ) ;
}
c = 0 ;
while ( ! empty ( q2 ) )
{
x = remove ( q2 ) ;
if ( max == x )
c + + ;
else
insert ( q1 , x ) ;
}
for ( i = 0 ; i < c ; i + + )
insert ( q1 , max ) ;
}
2- صف اولویت نزولی :
تست خالی بودن صف :
این تابع مقدار true را بر می گرداند اگر صف اولویت pq خالی باشد ، در غیر این صورت مقدار false را بر می گرداند .
تست پر بودن صف :
این تابع مقدار true را بر می گرداند اگر صف اولویت pq پر باشد ، در غیر این صورت مقدار false را بر می گرداند .
درج عنصر جدید در صف اولویت :
حذف عنصر از صف اولویت :
مثال : شبه کدی که بیست عدد را از ورودی خوانده ، آنها را به صورت نزولی چاپ کند :
dpq = the empty desending precendence queue
for ( i = 0 ; i < 20 ; i + + )
{
cin >> x ;
}
while ( ! empty ( dpq ) )
{
x = pq maxdelete ( dpq ) ;
cout << x ;
}
{
if ( empty ( q1 ) )
return ;
else
}
max = remove ( q1 ) ;
insert ( q2 , max ) ;
while ( ! empty ( q1 ) )
{
x = remove ( q1 ) ;
if ( x > max )
max = x ;
insert ( q2 , x ) ;
}
c = 0 ;
while ( ! empty ( q2 ) )
{
x = remove ( q2 ) ;
if ( max == x )
c + + ;
else
insert ( q1 , x ) ;
}
for ( i = 0 ; i < c ; i + + )
insert ( q1 , max ) ;
}
homework 1 : برنامه فوق را به گونه ای تغییر دهید که فقط آخرین max را به ته صف ببرد .
پیاده سازی queue :
1- توسط آرایه :
الف ) حرکت اندیس های rear و front
rear ( درج کردن ) : اول به جلو می رود بعد وارد می کند .
front ( حذف کردن ) : اول حذف می کند بعد به جلو می رود .
مشکل این روش اتلاف حافظه زیاد است .
پیاده سازی queue :
1- توسط آرایه :
الف ) حرکت اندیس های rear و front
rear ( درج کردن ) : اول به جلو می رود بعد وارد می کند .
front ( حذف کردن ) : اول حذف می کند بعد به جلو می رود .
شرط خالی بودن
rear < = front
شرط پر بودن
rear = maxsize - 1
مشکل این روش اتلاف حافظه زیاد است .
توابع این بخش عبارت اند از :
insert ( q , x )
insert ( q , x )
{
if ( ! full ( q ) )
{
q = rear + + ;
q . items [ q . rear ] = x ;
}
}
{
if ( q . rear == max q - 1 )
return true ;
else
return false ;
}
{
if ( ! empty ( ) )
{
x = q . items [ q . front ] ;
q . front + + ;
}
}
{
if ( q . rear < q . front )
return true ;
else
return false ;
}
توابع این بخش عبارت اند از :
{
if ( q . rear == q . front )
return true ;
else
return false ;
}
{
if ( ! empty ( q ) )
{
if ( q . front == max - 1 )
q . front = 0 ;
else
q . front + + ;
x = q . items [ q . front ] ;
}
}
{
if ( ! full ( q ) )
{
if ( q . rear == max - 1 )
q . rear = 0 ;
else
q . rear + + ;
q . items [ q . rear ] = x ;
}
}
{
k = q . rear ;
if ( k == max - 1 )
k = 0 ;
else
k + + ;
if ( k = q . front )
return true ;
else
return false ;
}
صف اولویت ( pq ) :
صفی است که در آن بین عناصر موجود در صف ، اولویت خاصی برقرار است .
انواع صف اولویت :
1- صف اولویت صعودی :
{
if ( ! full ( q ) )
{
q = rear + + ;
q . items [ q . rear ] = x ;
}
}
full ( q )
full ( q ){
if ( q . rear == max q - 1 )
return true ;
else
return false ;
}
remove ( q , x )
remove ( q , x ){
if ( ! empty ( ) )
{
x = q . items [ q . front ] ;
q . front + + ;
}
}
empty ( q )
empty ( q ){
if ( q . rear < q . front )
return true ;
else
return false ;
}
ب ) حرکت عناصر صف :
این روش اتلاف زمان دارد به دلیل اینکه هر خانه که حذف شود بقیه خانه ها را تا آخر به عقب می آورد .
توابع این بخش مثل بخش قبل است فقط باید در تمام مراحل به جای front عدد 0 را گذاشت و تابع remove به شکل زیر تغییر می کند :
remove ( q , x )
{
x = q . items [ 0 ] ;
for ( i = 0 ; i < q . items ; i + + )
q . items [ i ] = q . items [ i + 1 ] ;
q . rear - - ;
}
{
x = q . items [ 0 ] ;
for ( i = 0 ; i < q . items ; i + + )
q . items [ i ] = q . items [ i + 1 ] ;
q . rear - - ;
}
ج ) در نظر گرفتن صف به صورت دایره ای :
در این روش هر وقت به آخر رسید به اول می رود فقط یک خانه خالی وجود دارد برای اینکه rear و front در یک خانه قرار نگیرند .
شرط پر بودن
rear = max - 1
شرط خالی بودن
rear = front
توابع این بخش عبارت اند از :
empty ( q )
empty ( q ){
if ( q . rear == q . front )
return true ;
else
return false ;
}
remove ( q . x )
remove ( q . x ){
if ( ! empty ( q ) )
{
if ( q . front == max - 1 )
q . front = 0 ;
else
q . front + + ;
x = q . items [ q . front ] ;
}
}
insert ( q . x )
insert ( q . x ){
if ( ! full ( q ) )
{
if ( q . rear == max - 1 )
q . rear = 0 ;
else
q . rear + + ;
q . items [ q . rear ] = x ;
}
}
full ( q )
full ( q ){
k = q . rear ;
if ( k == max - 1 )
k = 0 ;
else
k + + ;
if ( k = q . front )
return true ;
else
return false ;
}
همیشه شرط پر بودن این است که rear یک خانه قبل از front باشد .
صف اولویت ( pq ) :
صفی است که در آن بین عناصر موجود در صف ، اولویت خاصی برقرار است .
انواع صف اولویت :
1- صف اولویت صعودی :
صفی که در آن عناصر به ترتیب ورود در انتهای صف درج می شوند ، امّا در هنگام حذف عنصری که دارای کمترین اولویت است حذف می شود .
2- صف اولویت نزولی :
صفی که در آن عناصر به ترتیب ورود در انتهای صف درج می شوند ، امّا در هنگام حذف عنصری که دارای بیشترین اولویت است حذف می شود .
اعمال مجاز روی صف اولویت :
اعمال مجاز روی صف اولویت :
تست خالی بودن صف :
pq empty ( pq )
این تابع مقدار true را بر می گرداند اگر صف اولویت pq خالی باشد ، در غیر این صورت مقدار false را بر می گرداند .
تست پر بودن صف :
pq full ( pq )
این تابع مقدار true را بر می گرداند اگر صف اولویت pq پر باشد ، در غیر این صورت مقدار false را بر می گرداند .
درج عنصر جدید در صف اولویت :
pq insert ( pq . x )
این تابع مقدار x را در انتهای صف اولویت غیر پر pq اضافه می کند .حذف عنصر از صف اولویت :
x = pq mindelete ( pq )
عنصر دارای کمترین اولویت را از صف اولویت صعودی pq حذف می کند .x = maxdelete ( pq )
عنصر دارای بیشترین اولویت را از صف اولویت صعودی pq حذف می کند .مثال : شبه کدی که بیست عدد را از ورودی خوانده ، آنها را به صورت نزولی چاپ کند :
dpq = the empty desending precendence queue
for ( i = 0 ; i < 20 ; i + + )
{
cin >> x ;
}
while ( ! empty ( dpq ) )
{
x = pq maxdelete ( dpq ) ;
cout << x ;
}
پیاده سازی صف اولویت :
1- در هنگام درج عناصر در انتهای صف درج شوند ، سپس عناصر موجود در صف به طور صعودی یا نزولی مرتب شوند و در انتها عنصر موجود در ابتدای صف حذف شود .
2- در هنگام درج عناصر در انتهای صف درج شوند ، در هنگام حذف عنصر دارای بیشترین یا کمترین اولویت جستوجو شده و از صف اولویت خارج شود .
homework2 : یکی از عملیاتهای بالا را انجام دهید .
در روش اول عناصر موجود در صف بایستی جابه جا شوند تا به صورت مرتب شده در آیند که این کار بسیار وقت گیر است .
در روش دوم بعد از حذف عنصر از صف بقیه عناصر باید جابه جا شوند که این موضوع نیز بسیار وقت گیر است ، این وقت گیر بودن در صورتی است که از آرایه برای نگهداری عناصر صف اولویت استفاده شود ، پس پیاده سازی صف اولویت با آرایه مقرون به صرفه نیست .
جلسه ششم
لیست پیوندی ( Linked List ) :
تعاریف :
لیست خالی
لیستی است که اشاره گر خارجی آن null می باشد .
نکته : لیست پیوندی ساختمان داده ای پویا است به این معنا که تعداد گره های آن در حین اجرای برنامه تغییر می کند .
توابع لیست پیوندی :
مثال 1
مثال 2
نکته : در شمارش سرلیست حساب نمی شود .
%99 از مواقع می توان با حلقه for لیست پیوندی را انجام داد .
مثال 3
اگر در انتهای حلقه for علامت " ; " بود ، حلقه فقط به دور خودش می چرخد و دستوری را اجرا نمی کند .
پیاده سازی پشته به وسیله لیست پیوندی
مثال 4
تابعی به نام instail که گره ای با محتوای x را در انتهای لیست L قرار دهد .
مثال 5
پیاده سازی صف با استفاده از لیست پیوندی
مثال 6
تابعی به نام insafter که گره ای با محتوای x را بعد از گره p درج کند .
homework2 : یکی از عملیاتهای بالا را انجام دهید .
در روش اول عناصر موجود در صف بایستی جابه جا شوند تا به صورت مرتب شده در آیند که این کار بسیار وقت گیر است .
در روش دوم بعد از حذف عنصر از صف بقیه عناصر باید جابه جا شوند که این موضوع نیز بسیار وقت گیر است ، این وقت گیر بودن در صورتی است که از آرایه برای نگهداری عناصر صف اولویت استفاده شود ، پس پیاده سازی صف اولویت با آرایه مقرون به صرفه نیست .
جلسه ششم
لیست پیوندی ( Linked List ) :
تعاریف :
node(p)
گره ای که p به آن اشاره می کند .
info( p )
قسمت نگهداری اطلاعات( node ( p می باشد .
next ( p )
آدرس گره بعدی را نگه می دارد ، در واقع اشاره گری است که به گره بعدی اشاره می کند . لیست خالی
لیستی است که اشاره گر خارجی آن null می باشد .
نکته : لیست پیوندی ساختمان داده ای پویا است به این معنا که تعداد گره های آن در حین اجرای برنامه تغییر می کند .
توابع لیست پیوندی :
p=get node ( )
این تابع یک گره را در حافظه ایجاد کرده و آدرس آن را در p می ریزد . نوع p باید از جنس اشاره گر باشد ، در واقع p اشاره گری به خودش است .freenode ( p )
این تابع گره ای که p به آن اشاره می کند را از بین می برد و حافظه را آزاد می کند .k = node count ( L ) ;
این تابع تعداد گره های یک لیست پیوندی را می شمارد و در k قرار می دهد .inshead ( L , x )
این تابع گره ای با محتوای x را در ابتدای لیست l اضافه می کند .مثال 1
inshead ( L , X )
{
p = get node ( );
ساختن گره جدید info ( p )= x ;
در قسمت info مقدار x را بریزnext ( p ) = L ;
next به جایی که L اشاره می کندL = p ;
L به p اشاره کند }
x = delhead ( L )
این تابع گره موجود در ابتدای لیست L را حذف کرده و محتوای آن را بر می گرداند .مثال 2
x = delhead ( L )
{
p = L ;
L = next ( p ) ;
x = info ( p ) ;
freenode ( p ) ;
}
نکته : در شمارش سرلیست حساب نمی شود .
%99 از مواقع می توان با حلقه for لیست پیوندی را انجام داد .
مثال 3
k = node count ( l ) ;
{
for ( i = 0 , p = l ; p ! = null ; p = next ( p ) , i + + );
return i ;
}
اگر در انتهای حلقه for علامت " ; " بود ، حلقه فقط به دور خودش می چرخد و دستوری را اجرا نمی کند .
پیاده سازی پشته به وسیله لیست پیوندی
empty
empty ( s )
{
if ( s == null )
return true ;
else
return false ;
}
top
x = top ( s )
{
if ( ! empty ( s ) )
x = info ( s ) ;
}
pop
x = pop ( s ) ;
{
if ( ! empty ( s ) )
return delhead ( s ) ;
}
push
push ( s , x )
{
inshead ( s , x );
}
مثال 4
تابعی به نام instail که گره ای با محتوای x را در انتهای لیست L قرار دهد .
instail ( L , x )
{
p = get node ( ) ;
info ( p ) = x ;
next ( p ) = null ;
if ( L == null )
L= p ;
else
{
for ( q = L ; next ( q ) ! = null ; q = next ( q ) );
next ( q ) = p ;
}
}
مثال 5
تابعی با نام ( x = deltail ( L که آخرین گره از لیست پیوندی L را حذف کند و محتوای آن را درون x بریزد .
x = deltail ( L )
{
for ( p = L , q = null ; next ( p ) ! = null ; p = next ( p ) )
q = p ;
if ( q == null )
L = null ;
else
next ( q ) = null ;
x = info ( p ) ;
freenode ( p ) ;
}
پیاده سازی صف با استفاده از لیست پیوندی
empty
empty ( q )
{
if ( s == null )
return true ;
else
return false ;
}
remove
x = remove ( q )
{
if ( ! empty ( q ) )
return delhead ( q ) ;
}
insert
insert ( q , x )
{
instail ( q , x ) ;
}
مثال 6
تابعی به نام insafter که گره ای با محتوای x را بعد از گره p درج کند .
insafter ( p , x )
{
q = get node ( ) ;
info ( q ) = x ;
next ( q ) = next ( p ) ;
next ( p ) = q ;
}
home work 1 : تابعی بنویسید که گره ای با محتوای x را طوری در لیست مرتب L درج کند تا لیست همچنان مرتب باقی بماند ( لیست به صورت صعودی مرتب است ) .
لیست پیوندی دایره ای
لیستی است که آدرس اولین گره در گره آخر می باشد ، در این حالت هر گره می تواند گره اول باشد .
homework 2 : پیاده سازی صف توسط لیست پیوندی دایره ای را انجام دهید .
لیست دو پیوندی
لیست دو پیوندی دایره ای
کاربردهای لیست پیوندی
1 . مسأله نمایش اعداد بزرگ
مثال : حاصل جمع دو عدد زیر
جلسه هفتم
ادامه مثال های جلسه قبل
مثال 7 : تابعی که گره بعد از گره p را حذف کند .
ادامه مثال های جلسه قبل
مثال 7 : تابعی که گره بعد از گره p را حذف کند .
delafter ( p )
{
if ( next ( p ) ! = null )
{
q = next ( p ) ;
next ( p ) = next ( q )
x = info ( q ) ;
freenode ( q ) ;
}
}
مثال 8 : تابعی که گره ای با محتویات x را قبل از گره ای که p به آن اشاره می کند اضافه کند .
مثال 9 : تابعی که کلیه گره های موجود بین گره های p و q را حذف کند و محتویات آنها را درون آرایه a قرار دهد.
insbefore ( L , p , x )
{
if ( p ! = L )
{
for ( q = L ; next ( q ) ! = p ; q = next ( q ) );
k = get node ( ) ;
info ( k ) = x ;
next ( k ) = p ;
next ( q ) = k ;
}
}
مثال 9 : تابعی که کلیه گره های موجود بین گره های p و q را حذف کند و محتویات آنها را درون آرایه a قرار دهد.
delbetween ( p , q , x )
{
i = 0 ;
if ( p ! = q )
{
for ( k = next ( p ) ; next ( k ) ! = q ; k = next ( p ) , i + + )
{
next ( p ) = next ( k ) ;
a [ i ] = info ( k ) ;
freenode ( k ) ;
}
next ( p ) = next ( k ) ;
a [ i ] = info ( k ) ;
freenode ( k ) ;
}
}
home work 1 : تابعی بنویسید که گره ای با محتوای x را طوری در لیست مرتب L درج کند تا لیست همچنان مرتب باقی بماند ( لیست به صورت صعودی مرتب است ) .
place ( L , x )
{
q = null ;
p = L;
while ( p ! = null && x > info ( p ) )
{
q = p ;
p = next ( p ) ;
}
if ( q == null )
inshead ( L , x );
else
insafter ( q , x );
}
{
q = null ;
p = L;
while ( p ! = null && x > info ( p ) )
{
q = p ;
p = next ( p ) ;
}
if ( q == null )
inshead ( L , x );
else
insafter ( q , x );
}
لیست پیوندی دایره ای
لیستی است که آدرس اولین گره در گره آخر می باشد ، در این حالت هر گره می تواند گره اول باشد .
در این بخش سرلیست با CL نشان داده می شود .
homework 2 : پیاده سازی صف توسط لیست پیوندی دایره ای را انجام دهید .
لیست دو پیوندی
info ( p )
اشاره گری به محتوای pright ( p )
اشاره گر به بعد از pleft ( p )
اشاره گر به قبل از p لیست دو پیوندی دایره ای
کاربردهای لیست پیوندی
1 . مسأله نمایش اعداد بزرگ
مثال : حاصل جمع دو عدد زیر
n1 = 123540328649453270274
n2 = 83941784
برنامه مثال بالا :
n3 = add ( n1 , n2 )
{
n3 = null ;
for ( p1 = n1 ; right ( p1 ) ! = null ; p1 = right ( p1 ) );
for ( p2 = n2 ; right ( p2 ) ! = null ; right ( p2 ) ) ;
for ( c = 0 ; p1 ! = null && p2 ! = null ; p1 = left ( p1 ) , p2 = left ( p2 ) )
{
s = info ( p1 ) + info ( p2 ) + c ;
c = s / 10000 ;
inshead ( n3 , s % 10000 ) ;
}
if ( n2 == null )
while ( p1 ! = null )
{
s = info ( p1 ) + c ;
c = s / 10000 ;
inshead ( n3 , s % 10000 ) ;
}
else
while ( p2 ! null )
{
s = info ( p2 ) + c ;
c = s / 10000 ;
inshead ( n3 , s % 10000 ) ;
}
if ( c ! = 0 )
inshead ( n3 , c ) ;
}
جلسه هشتم
کاربرد دوم لیست پیوندی : چند جمله ایها
کاربرد دوم لیست پیوندی : چند جمله ایها
f ( x ) = a0 + a , x + a2x2+.......+anxn
تابع این قسمت :
fval ( fx , x )
{
s = 0 ;
i = 0 ;
p = fx ;
while ( p != null )
{
s = s + ( info ( p ) * pow ( x , i ) ) ;
i ++ ;
p = next ( p );
}
return s ;
}
{
s = 0 ;
i = 0 ;
p = fx ;
while ( p != null )
{
s = s + ( info ( p ) * pow ( x , i ) ) ;
i ++ ;
p = next ( p );
}
return s ;
}
درخت : ( tree )
درخت دودویی
در درخت دودویی هر پدر حداکثر دو پسر دارد .
درخت دودویی محض
اگر در یک درخت دودویی هر گره پدر دقیقاً دو پسر داشته باشد به آن درخت دودویی محض می گویند .
سطح گره های درخت دودویی : Level
ریشه اصلی یا root دارای سطح 0 است و سطح هر گره غیر ریشه یک واحد بیشتر از سطح گره پدرش است .
مثال : اگر یک درخت دودویی در سطح L دارای m گره باشد در سطح L+1 حداکثر چند گره دارد ؟ 2m
مثال : یک درخت دودویی در سطح L حداکثر می تواند چند گره داشته باشد ؟ 2L=L ، 33=9
عمق ( depth ) :
عمق یک درخت دودویی بیشترین سطح برگ های درخت می باشد .
نکته : در یک درخت دودویی محض تعداد کل گره برابر است با :
درخت گرافی است که دور ندارد ، مجموعه ای از عناصر می باشد که یا تهی است یا از سه زیرمجموعه مجزا تشکیل می شود که یکی از آنها فقط یک عضو به نام ریشه یا root دارد و دو زیرمجموعه دیگر هر کدام درخت هایی هستند که زیرمجموعه ی چپ و راست نامیده می شوند ، هر یک از این زیردرخت ها می تواند تهی باشد.
عناصر تشکیل دهنده ی درخت را node می نامند .درخت دودویی
در یک درخت دودویی اگر A یک گره و B,C زیر درخت های چپ و راست آن باشند ، در این صورت A را پدر B,C و B را پسر راست و C را پسر چپ A گویند ، همچنین B,C برادر یکدیگر هستند ، گره ای که پسر چپ و راست نداشته باشد را برگ درخت یا Leaf می گویند و گره ای که پدر نداشته باشد ریشه اصلی نام دارد .
در هر درخت ، هر پسر فقط یک پدر دارد .در درخت دودویی هر پدر حداکثر دو پسر دارد .
درخت دودویی محض
اگر در یک درخت دودویی هر گره پدر دقیقاً دو پسر داشته باشد به آن درخت دودویی محض می گویند .
سطح گره های درخت دودویی : Level
ریشه اصلی یا root دارای سطح 0 است و سطح هر گره غیر ریشه یک واحد بیشتر از سطح گره پدرش است .
مثال : اگر یک درخت دودویی در سطح L دارای m گره باشد در سطح L+1 حداکثر چند گره دارد ؟ 2m
مثال : یک درخت دودویی در سطح L حداکثر می تواند چند گره داشته باشد ؟ 2L=L ، 33=9
عمق ( depth ) :
عمق یک درخت دودویی بیشترین سطح برگ های درخت می باشد .
نکته : در یک درخت دودویی محض تعداد کل گره برابر است با :
تعداد گره ها = 1 + 2 * تعداد برگها
نمایش درخت دودویی :
برای نمایش درخت های دودویی از لیست پیوندی استفاده می شود .
تعاریف :
نمایش درخت دودویی :
برای نمایش درخت های دودویی از لیست پیوندی استفاده می شود .
تعاریف :
node ( p )
گره ای که p به آن اشاره می کند .info ( p )
قسمت نگهداری اطلاعات ( node ( p می باشد .left ( p )
به ریشه ی زیر درخت چپ ( پسر چپ ) اشاره می کند .right ( p )
به ریشه ی زیر درخت راست ( پسر راست ) اشاره می کند .نکته : اگر ( node ( p پسر چپ یا راست نداشته باشد در این صورت به ترتیب ( left ( p یا ( right ( p برابر با null است .
جلسه نهم
ادامه مباحث جلسه قبل :
مثال 1 : تابعی که یک درخت را گرفته و تعداد node های آن را محاسبه کند .
ادامه مباحث جلسه قبل :
مثال 1 : تابعی که یک درخت را گرفته و تعداد node های آن را محاسبه کند .
k = tree node count ( tree )
{
if ( tree == null )
return 0 ;
else
return 1 + tree node count ( left ( tree ) ) + tree node count ( right ( tree ) ) ;
}
{
if ( tree == null )
return 0 ;
else
return 1 + tree node count ( left ( tree ) ) + tree node count ( right ( tree ) ) ;
}
مثال 2 : تابعی که تعداد برگ های یک درخت را محاسبه کند .
k = tree leaf count ( tree )
{
if ( tree == null )
return 0 ;
else
{
if ( left ( tree ) == null && right ( tree ) == null )
return 1 ;
else
return tree leaf count ( leaf ( tree ) ) + tree leaf count ( right ( tree ) ) ;
}
}
{
if ( tree == null )
return 0 ;
else
{
if ( left ( tree ) == null && right ( tree ) == null )
return 1 ;
else
return tree leaf count ( leaf ( tree ) ) + tree leaf count ( right ( tree ) ) ;
}
}
مثال 3 : تابعی که یک درخت را گرفته و عمق درخت را برگرداند .
tree depth ( tree )
{
if ( tree == null )
return 0 ;
else
return 1 + Max ( tree depth ( left ( tree ) ) , tree depth ( right ( tree ) ) ) ;
}
{
if ( tree == null )
return 0 ;
else
return 1 + Max ( tree depth ( left ( tree ) ) , tree depth ( right ( tree ) ) ) ;
}
توابع قابل اجرا برای ساختن درخت دودویی :
p = maketree ( x )
این تابع یک درخت دودویی جدید که فقط دارای یک node است را ایجاد می کند .
p = maketree ( x )
{
p = get node ( ) ;
info ( p ) = x ;
left ( p ) = right ( p ) = null ;
return p ;
}
p = get node ( ) ;
info ( p ) = x ;
left ( p ) = right ( p ) = null ;
return p ;
}
این تابع به یک درخت دودویی شامل فقط یک ریشه با محتویات x اشاره می کند و p اشاره گری به آن ریشه است .
set left ( p , x )
{
q = maketree ( x ) ;
left ( p ) = q ;
}
q = maketree ( x ) ;
right ( p ) = q ;
}
{
q = maketree ( x ) ;
left ( p ) = q ;
}
با استفاده از این تابع می توان زیر درخت چپ درخت دودویی را با محتوای x ایجاد نمود .
{set right ( p , x )
q = maketree ( x ) ;
right ( p ) = q ;
}
با استفاده از این تابع می توان زیر درخت راست درخت دودویی را با محتوای x ایجاد نمود .
مثال 4 : تابعی که درخت را بگیرد و آن را برعکس کند .
مثال 4 : تابعی که درخت را بگیرد و آن را برعکس کند .
t2 = makemirror ( t1 )
{
if ( t1 == null )
t2 = null ;
else
{
t2 = maketree ( info ( t1 ) ) ,
left ( t2 ) = makemirror ( right ( t1 ) ) ,
right ( t2 ) = makemirror ( left ( t1 ) ) ;
return t2 ;
}
}
جلسه دهم
درخت جستوجوی دودویی( binary search tree ( BST
{
if ( t1 == null )
t2 = null ;
else
{
t2 = maketree ( info ( t1 ) ) ,
left ( t2 ) = makemirror ( right ( t1 ) ) ,
right ( t2 ) = makemirror ( left ( t1 ) ) ;
return t2 ;
}
}
homework 1 : برنامه ای بنویسید که تعدادی عدد را بخواند و تعداد تکرار هر عدد را بررسی کند .
( ترجیحاً با استفاده از درخت )
( ترجیحاً با استفاده از درخت )
جلسه دهم
درخت جستوجوی دودویی( binary search tree ( BST
در این درخت هر پدر از پسر چپ و تمام نوه های چپ بزرگتر و همچنین از پسر راست و تمام نوه های راست کوچکتر یا مساوی می باشد .
مثال : تابعی که گره ای با محتوای x را در درخت tree طوری اضافه کند که درخت BST باقی بماند .
insBST ( tree , x )
{
if ( x < info ( tree ) )
{
if ( left ( tree ) ! = null )
insBST ( left ( tree ) , x ) ;
else
set left ( tree , x ) ;
}
if ( x > info ( tree ) )
{
if ( right ( tree ) ! = null )
insBST ( right ( tree ) , x ) ;
else
set right ( tree , x ) ;
}
}
پیمایش درخت های دودویی :
ب ) هر گره دقیقا یک بار ملاقات شود .
روش های پیمایش درخت های دودویی :
1 - روش preorder
الف ) گره ریشه یا پدر را ملاقات کن .
ب ) زیردرخت چپ را به روش preorder ملاقات کن .
2 - روش inorder
الف) زیردرخت چپ را به روش inorder ملاقات کن .
3 - روش postorder
الف) زیردرخت چپ را به روش postorder ملاقات کن .
ب ) زیردرخت راست را به روشpostorder ملاقات کن .
پیاده سازی روش preorder
{
if ( x < info ( tree ) )
{
if ( left ( tree ) ! = null )
insBST ( left ( tree ) , x ) ;
else
set left ( tree , x ) ;
}
if ( x > info ( tree ) )
{
if ( right ( tree ) ! = null )
insBST ( right ( tree ) , x ) ;
else
set right ( tree , x ) ;
}
}
نمایش عبارت ها ( expression tree )
شامل عملگرهای دوتایی توسط درخت دودویی
شامل عملگرهای دوتایی توسط درخت دودویی
پیمایش درخت های دودویی :
منظور از پیمایش حرکت در سرتاسر درخت و ملاقات تک تک گره ها به طوری که :
الف ) همه گره ها ملاقات شوند .ب ) هر گره دقیقا یک بار ملاقات شود .
روش های پیمایش درخت های دودویی :
1 - روش preorder
الف ) گره ریشه یا پدر را ملاقات کن .
ب ) زیردرخت چپ را به روش preorder ملاقات کن .
ج ) زیردرخت راست را به روش preorder ملاقات کن .
2 - روش inorder
الف) زیردرخت چپ را به روش inorder ملاقات کن .
ب ) گره ریشه یا پدر را ملاقات کن .
ج ) زیردرخت راست را به روش inorder ملاقات کن .3 - روش postorder
الف) زیردرخت چپ را به روش postorder ملاقات کن .
ب ) زیردرخت راست را به روشpostorder ملاقات کن .
ج ) گره ریشه یا پدر را ملاقات کن .
پیاده سازی روش preorder
preorder ( tree )
{
if ( tree == null )
return ;
else
{
cout << info ( tree ) ;
preorder ( left ( tree ) ) ;
preorder ( right ( tree ) ) ;
return ;
}
}
{
if ( tree == null )
return ;
else
{
cout << info ( tree ) ;
preorder ( left ( tree ) ) ;
preorder ( right ( tree ) ) ;
return ;
}
}
پیاده سازی روش inorder
inorder ( tree )
{
if ( tree == null )
return ;
else
{
inordr ( left ( tree ) ) ;
cout << info ( tree ) ;
inorder ( right ( tree ) ) ;
return ;
}
}
{
if ( tree == null )
return ;
else
{
inordr ( left ( tree ) ) ;
cout << info ( tree ) ;
inorder ( right ( tree ) ) ;
return ;
}
}
پیاده سازی روش postorder
postorder ( tree )
{
if ( tree == null )
return ;
else
{
postorder ( left ( tree ) ) ;
postorder ( right ( tree ) ) ;
cout << info ( tree ) ;
return ;
}
}
الگوریتم هافمن
{
if ( tree == null )
return ;
else
{
postorder ( left ( tree ) ) ;
postorder ( right ( tree ) ) ;
cout << info ( tree ) ;
return ;
}
}
کاربرد های پیمایش درخت :
1- اگر درخت جستجوی دودویی یا BST به روش inorder پیمایش شود اطلاعات موجود در گره های درخت به صورت صعودی مرتب می شوند .
نکته : روش مرتب سازی فوق را روش مرتب سازی درخت دودویی می نامند .
2 - اگر یک درخت دودویی را با روش های preorder یا inorder یا postorder پیمایش کنیم به ترتیب نمایش عبارت ها به صورت prefix یا infix یا postfix به دست می آید .
الگوریتم هافمن
این روش بوسیلهٔ دیوید هافمن توسعه یافت. وی دانشجوی دورهٔ دکتری در رشتهٔ فلسفه
در دانشگاه MIT بود
و در سال ۱۹۵۲ مقالهٔ «روشی برای تولید کدی با کمترین تکرار زوائد» را منتشر کرد. و به عنوان بخشی از سایر روش های
فشرده سازی مانند LZW) )مورد استفاده قرار گرفت .
توضیح :
-1 چگالی هر کاراکتر را محاسبه میکنیم (تعداد دفعات حضور کاراکتر در متن مورد
نظر).
-2 دو کاراکتر با کمترین میزان تکرار
(چگالی) را انتخاب میکنیم.
-3 کاراکتر های مرحله 2 را با کاراکتر جدیدی که دارای چگالی برابر با مجموع چگالی دو کاراکتر فوق است جایگزین
میکنیم.
-4 تا زمانی که فقط یک کاراکتر باقی مانده
باشد، به مرحله 2 میرویم.
-5 از عملیات فوق یک درخت
حاصل می شود، بر روی این درخت هر مسیر به سمت چپ با 0 و هر مسیر به سمت
راست با 1 وزن دهی میشود.
-6 کد
هر کاراکتر با کنار هم گذاشتن وزن ها از ریشه تا آن کاراکتر به دست می آید.
1-عددی که بالای هر کاراکتر نوشته شده
است نشان دهنده تعداد دفعات تکرار آن کاراکتر در رشته مورد نظر است.
نکته: (هر حرکت به چپ 0 و هر حرکت به
راست 1 )
با دنبال کردن مسیر از راس تا
کاراکترها(ریشه تا برگ ها) کد های جدید به دست خواهند آمد؛ کدهای جایگزین به دست
آمده برای این مثال به شکل زیر است:
E: 00
M: 0100
W: 0101
C: 0110
H: 01110
U: 01111
N: 100
I: 1010
T: 1011
_: 110
S: 111
همانطور که مشاهده می کنید به حرف E که تعداد تکرار بیشتری داشته کد کوچکتر 00 اختصاص داده شده ، و از این پس در این کد نوشته ای که به روش هافمن فشرده سازی شده حرف E با کد 00 شناخته می شود نه با کد اسکی آن .
جلسه یازدهم
مقدمه ای بر کارایی الگوریتم :
برای حل یک مسأله ممکن است الگوریتم های مختلفی وجود داشته باشد که هر کدام دارای مزایا و معایب خاص خودشان هستند ، کارایی الگوریتم بر اساس دو معیار اندازه گیری می شود ، یکی از آنها بهره وری از فضا و دیگری کارایی زمان است ، در الگوریتم ها آنچه بسیار اهمیت دارد زمان اجرا است ، این زمان تحت تأثیر عوامل متعددی قرار دارد ، یکی از اصلی ترین عوامل تأثیرگذار در زمان پردازش الگوریتم ها اندازه ورودی است ، به عنوان مثال زمان لازم برای مرتب سازی عناصر یک آرایه به تعداد عناصر موجود در آن بستگی دارد بنابراین اگر زمان اجرای الگوریتم را T در نظر بگیریم ، کارایی آن الگوریتم به صورت تابع ( T ( n بیان می شود که n همان اندازه ورودی است ، نوع دستورالعمل ها و سرعت اجرای ماشین نیز در زمان اجرا مؤثر است .
این عوامل به کامپیوتری که مورد استفاده قرار می گیرد بستگی دارد ، نمی توان مقدار ( T ( n را بر اساس واحد های زمان مثل ثانیه بیان کنیم . لذا ( T ( n تعداد تقریبی از دستورالعمل هایی است که باید اجرا شوند ، ( T ( n را پیچیدگی زمانی الگوریتم گویند .
مثال : محاسبه پیچیدگی زمانی و مرتبه الگوریتم مرتب سازی انتخابی :
void select ( int x [ ] , const int n )
{
int min , item ;
for ( int i = 0 ; i < n - 1 ; i ++ )
{
min = i ;
for ( int j = i + 1 ; j < n ; j ++ )
{
if ( x [ j ] < x [ min ] )
min = j ;
}
item = x [ i ] ;
x [ i ] = x [ min ] ;
x [ min ] = item ;
}
}
آرایه :
مجموعه ای از داده های هم نوع می باشد که تحت یک نام معرفی شده و هر عنصر آن با یک اندیس قابل دسترسی می باشد ، فرض کنیم آرایه ای به نام A به صورت زیر ایجاد کنیم :
در این صورت تعداد عناصر آرایه برابر است با :
A [ m1 ] [ m2 ] ... [ mn ]
در این صورت تعداد عناصر آرایه برابر است با :
m1 * m2 * ... * mn
روش های ذخیره کردن آرایه :
1 - روش سطری :
1 - روش سطری :
در این روش سطرهای آرایه یکی یکی در حافظه ذخیره می شود ، در این صورت برای یافتن عنصر بعدی در آرایه اولین اندیس سمت راست یک واحد اضافه می شود ، در صورتی که این اندیس از مقدار نهایی خود گذشته باشد ، به مقدار اولیه باز می گردد و یک واحد به اندیس سمت چپ اضافه می شود .
2 - روش ستونی :
این روش مانند روش قبل است با این تفاوت که این بار ابتدا اندیس چپ و سپس اندیس راست عوض می شوند .
+ نوشته شده در جمعه ۱۳۹۱/۱۲/۱۸ ساعت 1:9 AM توسط نویسنده : محمّد راستگو
|
اطلاعات مورد نیاز دانشجویان رشته نرم افزار کامپیوتر