نحوه پیاده سازی heap sort با لینک لیست ها

دوستان می خواستم کمکم کنید
یه توضیحی در مورد heap sort و پیاده سازی اون توسط لینک لیست ها بدید ممنون میشم
خواهشن هر چه زود تر به راهنمایی بکنید شدیدا گیرشم:11:

ببینید برنامه ی زیر کاربردی براتون داره:

کد:

---

#include <stdio.h>

typedef struct node_tag node;
struct node_tag
{
node *pA, *pB;
int data;
};

/* too lazy to use rand() in a loop */
node Q[16] =
{
{ NULL, &Q[ 1], 37 },
{ &Q[ 0], &Q[ 2], 42 },
{ &Q[ 1], &Q[ 3], 55 },
{ &Q[ 2], &Q[ 4], 11 },
{ &Q[ 3], &Q[ 5], 12 },
{ &Q[ 4], &Q[ 6], 71 },
{ &Q[ 5], &Q[ 7], 34 },
{ &Q[ 6], &Q[ 8], 35 },
{ &Q[ 7], &Q[ 9], 16 },
{ &Q[ 8], &Q[10], 61 },
{ &Q[ 9], &Q[11], 36 },
{ &Q[10], &Q[12], 49 },
{ &Q[11], &Q[13], 48 },
{ &Q[12], &Q[14], 10 },
{ &Q[13], &Q[15], 32 },
{ &Q[14], NULL, 80 },
};
node *pHead = &Q[0];

void PrintNodes(void)
{
const node *p;

p = pHead;
do
{
if (p->pA == NULL)
printf(" ");
else
printf(" [%2d] -> ", p->pA->data);
printf("%2d", p->data);
if (p->pB == NULL)
printf("\n");
else
printf(" -> [%2d]\n", p->pB->data);
p = p->pB;
} while (p);
}

node *HeapSort(node *pList);
int main(void)
{
printf("Before:\n");
PrintNodes();

pHead = HeapSort(pHead);

printf("After:\n");
PrintNodes();

return 0;
}

node *HeapInsert(node *pHead, node *pNew)
{
if (pHead == NULL)
{
pNew->pA = pNew->pB = NULL;
return pNew;
}

if (pNew->data > pHead->data)
{
/* switch A/B to try to maintain balance */
pNew->pB = pHead->pA;
pNew->pA = HeapInsert(pHead->pB, pHead);
return pNew;
}
else
{
pHead->pA = HeapInsert(pHead->pA, pNew);
return pHead;
}
}

node *HeapRemove(node *pHead)
{
if (pHead == NULL)
return NULL;

if (pHead->pA == NULL)
return pHead->pB;
if (pHead->pB == NULL)
return pHead->pA;

if (pHead->pA->data > pHead->pB->data)
{
pHead->pA->pA = HeapRemove(pHead->pA);
pHead->pA->pB = pHead->pB;
return pHead->pA;
}
else
{
pHead->pB->pB = HeapRemove(pHead->pB);
pHead->pB->pA = pHead->pA;
return pHead->pB;
}
}

node *HeapSort(node *pList)
{
node *pIter = pList, *pNext, *pPrev;
node *pHead = NULL;
/* build heap */
while (pIter)
{
/* take one out of the list */
pNext = pIter->pB;
/* put it into the heap */
pHead = HeapInsert(pHead, pIter);
pIter = pNext;
}

/* tear down heap */
pPrev = NULL;
while (pHead)
{
/* take one out of the heap */
pIter = pHead;
pHead = HeapRemove(pHead);
/* put it into the list */
pIter->pA = pPrev;
if (pPrev == NULL)
pList = pIter;
else
pPrev->pB = pIter;
pPrev = pIter;
}
if (pIter)
pIter->pB = NULL;
return pList;
}

---

salam age barnamasho khasti ye mail bezar barat send konam

نقل قول:

---

نوشته شده توسط soda_india [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

salam age barnamasho khasti ye mail bezar barat send konam

---

دستت درد نکنه شدیدا بهش احتیاج دارم اگه بفرستی ممنون میشم تا آخر شب باید برنامه رو بفرستم
البته مشکل اصلی من نحوه ساختن خود heap هست با لینک لیست که مثلا داده ها رو وارد که می کنی با چه الگوریتمی این داده هارو بریزم تو heap
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

salam man baraton ferestadam moshkeli bod begid mamnon misham

دوست عزیز بسیار ممنون برنامتونو دریافت کردم و خوندم مفید بود مرسی
البته یه چیزی من میخواستم که درخت heap با لینک لیست ها باشه اما تو برنامه شما از آرایه استفاده شده که تو آرایه به سادگی میشه درخت رو ساخت
به این شکل که با آرایه ها درخت رو پیاده سازی کنیم رو مشکلی نداشتم همونطور که گفتم مشکل من این بود که چه طور یه درخت کامل با لینک لیست ها بسازم که بعد اینکه حدودا یه روز full time رو این تکلیف کار کردم با یه ایده نسبتا جالب تونستم این کار رو بکنم و یه درخت کامل رو با لینک لیست ها پیاده سازی کردم که در ادامه heap رو هم با لینک لیست ها ساختم و کارم را افتاد
بازم از دوست عزیز soda_india تشکر میکنم زحمت کشیدید
دوستان اگه خواستید نحوه پیاده سازی یه درخت کامل رو اون طور که من فهمیدم توضیح بدم چون تو خیلی جاها گشتم بیشتر جاها با آرایه پیاده سازی کرده بودن و با لینک لیست جایی ندیدم شاید هم درست search نکردم در ضمن شاید الگوریتم های خیلی بهتری شماها بلد باشید که ما هم یاد بگیریم خیلی خوشحال میشم

mishe in barnamaro baraye manam mail konid? mamnon misham!!!

---------- Post added at 07:25 PM ---------- Previous post was at 07:24 PM ----------

mishe in barnamaro baraye manam mail konid? manam bhsh niaz daram baraye pro sakkhteman dadam mamnon misham

---------- Post added at 07:26 PM ---------- Previous post was at 07:25 PM ----------

inam emailam hastesh:
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]