لیست های پیوندی
تعریف لیست پیوندی Link List
A
. . .
0
Z
B
تعریف : مجموعه ای از گره ها که هرگره حداقل شامل یک فیلد داده ویک فیلد اشاره گر است.
اشاره گر هر گره از نوع خود گره است.
هر گره به وسیله ی اشاره گر خود به گره بعدی اشاره می کند.
نقایص کار با آرایه ها به صورت ترتیبی
بازگشت ناپذیر بودن حافظه بعد از گرفتن آن
لازم بودن پیش بینی بیشترین حافظه مورد نیاز
پر هزینه بودن اضافه کردن عنصر
پر هزینه بودن حذف کردن عنصر
پر هزینه بودن اضافه کردن عنصر
می خواهیم C را به آن اضافه کنیم به طوری که ترتیب آن الفبایی بماند.
0 1 2 3 4 5
Shift
پر هزینه بودن اضافه کردن عنصر-ادامه
0 1 2 3 4 5
سوال:مرتبه الگوریتم بالا چیست؟
O(n)
پر هزینه بودن حذف کردن عنصر
اگر بخواهیم B را از آرایه ی قبلی حذف کنیم باید تمام عناصر بعد از آن را یکی به عقب بیاوریم
0 1 2 3 4 5
مرتبه این الگوریتم نیز (n)O است.
shift
راه حل مشکلات ناشی از کار با آرایه به صورت ترتیبی
استفاده ازلیست پیوندی
مزایا:
مجبور نیستیم داده ها را در فواصل مشخصی ازهم قرار دهیم.
می توان حافظه ی بدون استفاده را به کامپیوتربرگرداند.
– عملیات لیست پیوندی
– ایجاد لیست
– درج گره در لیست
– حذف گره از لیست
– جستجو در لیست
– مرتب سازی لیست
– معکوس کردن لیست
– و …
ساختمان داده مورد نیاز
جهت پیاده سازی لینک لیست:
استفاده از آرایه
استفاده از اشاره گر Pointer
پیاده سازی لیست پیوندی به وسیله ی آرایه
برای ایجاد این لیست باید از دو آرایه استفاده کرد.
آرایه ی اول برای داده ها : این آرایه از نوع داده ی مورد نظر انتخاب می شود (مثلا یک structure)
آرایه ی دوم برای اتصال ها : این آرایه که از نوع int است.متناظر با داده هاست.که نشان دهنده ی آدرس داده بعدی است.
پیاده سازی لیست پیوندی به وسیله ی آرایه-ادامه
0
درج در لیست پیوندی
درج در لیست پیوندی-ادامه
درج در لیست پیوندی-ادامه
درج در لیست پیوندی-ادامه
درج در لیست پیوندی-ادامه
مراحل درج در لیست پیوندی
1)قرار دادن داده ی لینک در آرایه ی داده ها
2)اشاره دادن عضو جدید به عضو بعد از خودش
3)اشاره دادن عضو قبل از عضو جدید به عضو جدید
نکته : همیشه ابتدا عضوجدید را در لیست قرار می دهیم سپس عضوهایی را که باید به عضو جدید اشاره کنند به آن اشاره می دهیم.
پیاده سازی با اشاره گر
تعریف یک نود
لازم است این مسئله مشخص شود که فیلدهای ما چه نوع داده ای هستند.(به عنوان مثال می توان یک کاراکتر)
class CharNode
{
private :
char data;
CharNode *link;
};
روش های طراحی لیست
طرح اول:
متغیر first را از نوع به عنوان متغیر سراسری در نظر می گیریم.
Node *first;
اشاره گر link و کاراکتر data اعضای private هستند.
خطای زمان اجرا
طرح دوم:
data , link را به صورت public در بیاوریم. (نقض اصل محصور سازی)
از توابع set و get برای هر کدام استفاده نماییم.(نقض اصل مخفی سازی)
روش های طراحی لیست
اصل مخفی سازی داده ها
دسترسی ساده تر به اطلاعات
یک کلاس دیگر تعریف می شود که حاوی کل لیست باشد (first).
طراحی لیست به وسیله ی کلاس مدیر
class List
{
public :
//list manipulation operations
private:
Node * first;
};
class Node
{
friend class List;
private :
char data;
Node * link;
};
طراحی لیست به وسیله ی کلاس مدیر-ادامه
رابطه ی بین کلاس مدیر (List) و کلاس گره (Node)
دستکاری اشاره گرها در C++
تعریف یک اشاره گر:
Node * pointer;
گرفتن حافظه برای اشاره گر:
pointer = new Node;
آزاد کردن حافظه :
delete pointer;
مثال – ایجاد لیست با دو گره
void List::Create2()
{ first = new Node (‘B’);
first link = new Node (‘C’);
}
Node :: Node (char element =0)
{ data = element;
link = 0 ; //null pointer
}
مثال – درج گره در ابتدای لیست
void List :: InsertFirst ()
{ Node *t = new Node(‘A’);
t link = first;
first = t;
}
یک کلاس لیست پیوندی با قابلیت استفاده مجدد
بهتر نیست که یک بار یک لیست را طراحی کنیم و چندین بار از آن استفاده کنیم؟
برای این که بتوانیم از یک لیست پیوندی برای چند بار استفاده کنیم باید از کلاس های الگو(template) استفاده کنیم.
template <class Type> class List; //forward declaration
template <class Type>
class ListNode
{
friend class List<Type>;
private :
Type date;
ListNode *link;
};
template <class Type>
class List
{
public :
List(){first = 0;}
private:
ListNode <Type> *first;
};
تعریف لیست های با قابلیت استفاده ی مجدد
عملکردها روی لیست پیوندی
1) نمایش لیست پیوندی
2) اضافه کردن عنصری در لیست
3) حذف کردن عنصر
و …
first
temp
ِA
ِB
C
ِD
Output : A
نمایش لیست پیوندی(پیمایش)
نمایش لیست پیوندی(پیمایش)-ادامه
نمایش لیست پیوندی(پیمایش)-ادامه
نمایش لیست پیوندی(پیمایش)-ادامه
نمایش لیست پیوندی)پیمایش(-ادامه
void ListNode :: Print()
{
if( !first ) return; //no node
Node *temp = first;
while(temp) //traverse list
{
cout << temp data;
temp = temp link; //next node
}
}
اضافه کردن عنصر جدید
البته برای کاربردهای مختلف اضافه کردن فرق می کند.
ما در اینجا اضافه کردن عنصر جدید بعد از یک عنصر مشخص را نشان می دهیم.
مراحل کار:
1) نصب عنصر جدید
2) تنظیم اشاره گرهای مربوط به عنصر جدید
first
curNode
0
0
newNode
اضافه کردن عنصر جدید
first
curNode
0
newNode
اضافه کردن عنصر جدید-ادامه
C
B
A
D
E
newNode link = curNode link ;
first
curNode
0
newNode
اضافه کردن عنصر جدید-ادامه
A
B
D
E
C
curNode link = newNode ;
first
curNode
0
newNode
اضافه کردن عنصر جدید-ادامه
A
B
C
D
E
اضافه کردن عنصر جدید-ادامه
template <class Type>
void ListNode<Type> :: Insert (Node*curNode ,Node *newNode)
{
newNode –> link = curNode –> link ; //assign newNode
curNode –> link = newNode ; //assign curNode
}
اضافه کردن به ابتدای لیست
بدین دلیل این حالت خاص را بررسی می کنیم که بعد از اضافه کردن عنصر باید اشاره گر first به ابتدای لیست اشاره کند.
مراحل کار
1) نصب عنصر جدید
2) اشاره دادن اشاره گر first به عنصر جدید
اضافه کردن به ابتدای لیست
first
0
newNode
اضافه کردن به ابتدای لیست-ادامه
A
B
C
D
E
newNode link = first;
اضافه کردن به ابتدای لیست-ادامه
first = newNode;
اضافه کردن به ابتدای لیست-ادامه
اضافه کردن به ابتدای لیست-ادامه
template <class Type>
void ListNode<Type> :: InsertFirst(Node *newNode)
{
if( !first ) //no node
{
first = newNode;
newNode –> link = NULL;
return;
}
newNode –> link = first; //assign newNode
first = newNode;
}
حذف عنصر از لیست پیوندی
مراحل کار:
1) تنظیم اشاره گرها
2) حذف کردن گره (آزاد کردن حافظه)
first
curNode
0
ِA
ِB
C
ِD
ِE
حذف عنصر از ابتدای لیست پیوندی
first
curNode
0
ِA
ِB
C
ِD
ِE
حذف عنصر از لیست پیوندی-ادامه
first = first link;
حذف عنصر از ابتدای لیست پیوندی-ادامه
delete cur;
first
curNode
0
ِA
ِB
C
ِD
ِE
حذف عنصر از لیست پیوندی-ادامه
temp
Node *temp = first;
first
curNode
0
ِA
ِB
C
ِD
ِE
حذف عنصر از لیست پیوندی-ادامه
temp
while( temp link != cur)
temp = temp link;
first
curNode
0
ِA
ِB
C
ِD
ِE
حذف عنصر از لیست پیوندی-ادامه
temp
while( temp link != cur)
temp = temp link;
حذف عنصر از لیست پیوندی-ادامه
temp link = cur link;
حذف عنصر از لیست پیوندی-ادامه
delete cur;
template <class Type>
void ListNode<Type> :: Delete( Node *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;
}
حذف عنصر از لیست پیوندی-ادامه
سوالات
عناصر یک لیست را برعکس نمایید.
سوال 3 از تمرینات بخش 4-3
دو زنجیر (لیست پیوندی) را بهم متصل کنید و یک زنجیر تولید کنید.
عنصری را به انتهای لیست اضافه کنید.
لیست های حلقوی
به وسیله ی اتصال آخرین گره به اولین گره می توان لیست حلقوی را تولید کرد.
در این گونه لیست ها به راحتی می توان از آخر لیست به اول لیست پرش کرد.
نمونه ای از لیست حلقوی
عملکردهای لیست حلقوی
بیشتر کارهایی را که روی لیست معمولی انجام می دادیم می توانیم روی لیست حلقوی انجام دهیم.
باید بعد از تغییرات لیست ، حلقوی بماند.
نمایش لیست حلقوی
void ListNode :: Print()
{
if( !first ) return; //no node
Node *temp = first;
while(temp link != first)//traverse list
{
cout << temp data;
temp = temp link; //next node
}
}
اضافه کردن عنصر جدید
تابعی که برای اضافه کردن عنصر جدید بعد از یک عنصر خاص برای لیست ساده گفته شد این جا نیز کاربرد دارد.
اما برای اضافه کردن عنصر به ابتدای لیست باید تابعی جدید نوشته شود.
یک اشاره گر جدید last به عنصر آخراشاره کند.
لیست را برای پیدا کردن آخرین عنصر پیمایش کرد.
اضافه کردن به ابتدای لیست حلقوی
void InsertFirst(Node * newNode)
{
if( !last ) //no node
{
last = first = newNode;
first link = first;
}
else
{
newNode link = first;
last link = newNode;
first = newNode;
}
}
اضافه کردن به ابتدای لیست حلقوی-ادامه
void InsertFirst(Node * newNode)
{
if( !first ) //no node
{
first = newNode;
first link = first;
}
else
{
newNode link = first;
Node *temp = first;
while(temp link != first) temp = temp link;
temp link = newNode;
first = newNode;
}
}
پشته های پیوندی
با استفاده از لیست پیوندی این استراتژی را پیاده سازی کنیم.
همین طور که می دانید در پشته ورود و خروج داده ها از یک طرف انجام می شود.
تعریف کلاس پشته
class Stack
{
public :
Stack() {top = 0;};
void Push( int );
int Pop();
private:
StackNode *top;
};
class StackNode
{
friend class stack;
private:
int data;
StackNode * link;
StackNode(int d = 0,StackNode *li = 0):data(d),link(li){};
};
درج در پشته
void Push(int newElement)
{
top = new StackNode(newElement , top);
}
top
B
A
E
D
C
0
temp
حذف از پشته
temp = top;
top
B
A
E
D
C
0
temp
top
B
A
E
D
C
0
temp
حذف از پشته-ادامه
top = temp link;
حذف از پشته-ادامه
delete temp;
int Stack :: Pop()
{
if( !top ){cout << “empty stack”; return -1;}
StackNode *temp = top;
int retVal = temp data;
top = top link;
delete temp;
return retVal;
}
حذف از پشته-ادامه
صف های پیوندی
همان طور که می دانید در استراتژی صف ورود اطلاعات از یک طرف و خروج اطلاعات از طرف دیگر است.
به این دلیل به دو اشاره گر به نام های rear و front نیاز داریم.
تعریف کلاس صف پیوندی
class QueueNode
{
friend class Queue;
private :
int data;
QueueNode * link;
QueueNode(int d = 0,QueueNode *li = 0): data(d) , link(li){};
};
class Queue
{
public :
Queue() {front = rear = 0;}
void AddQ( int );
int DelQ();
private:
QueueNode *rear , *front;
};
اضافه کردن عنصر جدید به صف پیوندی- درج در انتها
void Queue :: AddQ( int newElement)
{
if( !front ) front = rear = new QueueNode( newElement , 0);
else rear = rear link = new QueueNode( newElement, 0);
}
حذف از یک صف پیوندی – حذف از ابتدا
int Queue :: DelQ()
{
if( !front ){cout << “empty queue.”; return;}
QueueNode *temp = front;
int retVal = front data;
front = front link;
delete temp;
return retVal;
}
پروژه برنامه نویسی
سوال 10 [پروژه برنامه نویسی] تمرینات بخش 4-8
نکته: قسمت 4-8 بایستی به طور کامل خوانده شود.(ماتریس خلوت)
لیست های پیوندی دوگانه
مشکل اساسی لیست های یک طرفه عدم دسترسی به گره قبلی
لیست های دوگانه با اضافه کردن یک اشاره گر به گره ی قبلی این مشکل را حل کرده است.
لیست دوطرفه ی ساده
لیست دوطرفه ی حلقوی
انواع لیست های پیوندی دوگانه
تعریف کلاس لیست دوطرفه
class DblListNode
{
friend class DblList;
private:
int data;
DblListNode * next, *pre;
};
class DblList
{
public :
//operations
private:
DblListNode *first;
};
اضافه کردن عنصر به لیست دوطرفه ساده
newEle next = cur next;
اضافه کردن عنصر به لیست دوطرفه ساده-ادامه
cur next = newEle;
اضافه کردن عنصر به لیست دوطرفه ساده-ادامه
cur next = newEle;
اضافه کردن عنصر به لیست دوطرفه ساده-ادامه
(newEle next) pre = newEle;
اضافه کردن عنصر به لیست دوطرفه ساده-ادامه
اضافه کردن عنصر به لیست دوطرفه ساده-ادامه
سوال
اگر بخواهیم عنصر newEle را به ابتدای لیست اضافه کنیم؟
اگر بخواهیم عنصر newEle را به انتهای لیست اضافه کنیم؟
اگر لیست خالی باشد؟
اضافه کردن عنصر به لِست دوطرفه ساده
void DblList :: Insert(DblListNode *cur,DblListNode *newEle)
{
newEle next = cur next;
newEle pre = cur;
cur next = newEle;
if(newEle next)
(newEle next) pre = newEle;
}
حذف از لیست دوطرفه ساده
first
cur
( cur next ) pre = cur pre;
حذف از لیست دوطرفه ساده -ادامه
( cur pre ) next = cur next;
حذف از لیست دوطرفه ساده-ادامه
( cur pre ) next = cur next;
حذف از لیست دوطرفه ساده -ادامه
حذف از لُیست دوطرفه ساده -ادامه
سوال
اگر بخواهیم عنصر ابتدای لیست را حذف کنیم؟
اگر بخواهیم عنصر ابتدای لیست را حذف کنیم؟
اگر لیست خالی باشد؟
حذف از لیست دوطرفه ساده
void DblList :: Delete( Node * cur)
{
if( cur next)
{
( cur next ) pre = cur pre;
( cur pre ) next = cur next;
delete cur;
return;
}
( cur –> pre ) –> next = 0;
delete cur;
}
حذف از ابتدای لیست دوطرفه ساده
void DblList :: Delete(DblListNode *cur)
{
if( cur == first )
{
Node *temp = first ;
if( !first –> next )
{
delete first;
return;
}
first = first –> next;
first –> pre = 0;
delete temp;
return;
}
}
مباحث بعدی
لیست دو طرفه حلقوی
لیستهای تعمیم یافته ص 216
سوالات
الگوریتم درج عنصر در انتهای لیست دو طرفه ی حلقوی؟
الگوریتم معکوس کردن لیست دو طرفه ی ساده؟
الگوریتم معکوس کردن لیست دو طرفه ی حلقوی؟