שלום, אני צריך למיין רשימה מקושרת (חד כיוונית )בעזרת מיון בועות בשפת C

אני די תקוע בפונ' ה swap

void swap(LNODE *cur,LNODE *next,LIST *lst)

אני לא מצליח לבצע את ההחלפה כאשר מצביע ה current הוא על ראש הרשימה..כל השאר עובד לי (עד עכשיו)..

כשה current נמצא בתוך הרשימה אני משתמש בצמת קודם (עם פונ' עזר, כי אין מצביע prev) כדי לבצע את הקישור בין המצביעים,

כשהוא בתחילתו אני די תקוע

אשמח אם תוכלו לכוון אותי טיפה

תודה

יעזור אם תעלה את שאר הקוד (ההגדרות המדוייקות של LNODE ו-LIST, והמימוש הנוכחי שלך ל-swap).

אחת הדרכים הפשוטות לפתרון של הבעיה היא הוספת איבר "עוגן" - איבר דמה היושב בראש הרשימה (לפני האיבר הראשון) ומכיל ערך פיקטיבי. ככה גם לאיבר הראשון יש איבר קודם, ואז אפשר לעבוד איתו כמו עם כל איבר אחר.

אגב, אם על מנת להחליף זוג איברים אתה צריך כל פעם לחפש את האיבר הקודם של cur, זה הופך את האלגוריתם לממש לא יעיל (במקום (O(n^2 הוא ייקח (O(n^3)). מומלץ כן לשמור את ה-prev איכשהו.

typedef struct listNode{
	int data;
	struct listNode* next;
}LNODE;

typedef struct list{
	LNODE* head;
	LNODE* tail;
}LIST;

המציאה של של האיבר הקודם באמת הופכת את זה לממש יעיל, בנוסף לעובדה שהמיון עצמו לא הכי יעיל שיש..

void swap(LNODE* cur,LNODE* next,LIST*lst)
{
	LNODE* prev;
	LNODE* tmp;


	if (cur == lst->head && next == lst->tail)
	{



	}

	if (cur==lst->head && next!=lst->tail)
	{


	}

	if (cur!=lst->head && next == lst->tail)
	{
		prev = prevNode(*lst,cur);
		cur->next = next->next;
		prev->next = next;
		next->next = cur;

	}

	else if (cur!=lst->head && next!=lst->tail)
	{

		prev = prevNode(*lst,cur);
		prev->next = next;
		cur->next = next->next;
		next->next = cur;
	}


}

בתנאי הקצה שקשורים לתחילת הרשמה השארתי ריק, כי כל מה שניסיתי לא עבד

קודם כל, אתה יודע שאתה יכול להימנע מכל הבלאגן אם תחליף את הערכים שברשימה (ה-data) במקום המצביעים, נכון?

אבל נניח שאנחנו בכל זאת רוצים לפתור בדרך הזו.

נתחיל מזה שהקוד בשני המקרים האחרונים זהה לחלוטין, ככה שאין כמעט צורך בהפרדה ביניהם (שים לב שבמקרה השני יש באג - אתה לא מעדכן את tail - אבל חוץ מזה אין הבדל ביניהם).

במקרה ש-cur הוא ראש הרשימה, זה אפילו יותר פשוט - אין לך prev, ככה שלא צריך לעדכן אותו. את מי כן צריך לעדכן? את ראש הרשימה (list->head), כי אותו הרי החלפת.

להחליף את ערכי הdata ממש מפשט את התרגיל,אמנם לא קיבלנו הנחיה שאסור אבל רוב התרגיל הוא על שינוי מצביעים כך שאני מניח שהמרצה מצפה שנחליף גם את המצביעים...

דוודא את העדכון של ה lst->head אני לא מצליח ליישם, בעיקרון זה אמור להיות

cur->next = next->next;

next->next = cur;

איך אני עושה שמצביע ה next יהיה ראש הרשימה..?

למה אתה לא מצליח ליישם את lst->head? כל מה שאתה צריך לעשות הוא

lst->head = x

ועכשיו אתה רק צריך לחשוב מה לשים במקום ה-x.

lst->head = next

נו, זה היה כל כך קשה?

		lst->head = next;
		cur->next = next->next;
		next->next = cur;

אבל זה לא עובד...

תגדיר "לא עובד".

כשאני מפעיל את הפונק' על רשימה שכוללת רק את ה lst->head ואת lst-> tail

זה נכנס ללולאה אינסופית רק עם הערך של ראש הרשימה..

אז תעלה את הקוד המלא. אתה מצפה שננחש מה הבעיה?

#include<stdio.h>
#include<malloc.h>

#define TRUE 1
#define FALSE 0

typedef struct listNode{
	int data;
	struct listNode* next;
}LNODE;

typedef struct list{
	LNODE* head;
	LNODE* tail;
}LIST;

void makeEmpty(LIST* lst);
int isEmpty(LIST lst);
LNODE* createNewListNode(int data,LNODE* next);
void insertNodeToStartList(LIST* lst,LNODE* head);
void exampleList(LIST* lst);
void printList(LIST lst);
void insertNodeToEndList(LIST* lst,LNODE* tail);
LNODE* prevNode(LIST lst,LNODE* cur);

void makeEmpty(LIST* lst)
{
	lst->head = NULL;
	lst->tail = NULL;
}

int isEmpty(LIST lst)
{
	return (lst.head == NULL);
}

LNODE* createNewListNode(int data,LNODE* next)
{
	LNODE* res;
	res = (LNODE*)malloc(sizeof(LNODE));
	res->data = data;
	res->next = next;
	return res;
}

void insertNodeToStartList(LIST* lst,LNODE* head)
{
	if (isEmpty(*lst) == TRUE)
	{
		head->next = NULL;
		lst->head = lst->tail = head;
	}
	else
	{
		head->next = lst->head;
		lst->head = head;
	}
}

void insertNodeToEndList(LIST *lst, LNODE* tail)
{
	if (isEmpty(*lst) == TRUE)
	{
		lst->head = lst->tail = tail;
	}
	else
	{
		lst->tail->next = tail;
		lst->tail = tail;
	}		
	tail->next = NULL;
}


void exampleList(LIST* lst)
{
	LNODE* node;
	if (isEmpty == FALSE)
		return ;
	else
	{
		node = createNewListNode(15,NULL);
		insertNodeToStartList(lst,node);

		node = createNewListNode(14,NULL);
		insertNodeToEndList(lst,node);
/*
		node = createNewListNode(10,NULL);
		insertNodeToEndList(lst,node);

		node = createNewListNode(12,NULL);
		insertNodeToEndList(lst,node);

		node = createNewListNode(11,NULL);
		insertNodeToEndList(lst,node);*/

	}

}

void printList(LIST lst)
{
	LNODE* cur;
	cur = lst.head;

	while (cur!=NULL)
	{
		printf("%d ",cur->data);
		cur = cur->next;
	}
}


LNODE* prevNode(LIST lst,LNODE* cur)
{
	LNODE* current;

	current = lst.head;
	while (current->next!=cur)
	{
		current = current->next;
	}
	return current;
}

void swap(LNODE* cur,LNODE* next,LIST* lst)
{
	LNODE* prev;

	if (cur == lst->head && next == lst->tail)
	{
		lst->head = next;
		cur->next = next->next;
		next->next = cur;
	}



	if (cur!=lst->head && next == lst->tail)
	{
		prev = prevNode(*lst,cur);
		cur->next = next->next;
		prev->next = next;
		next->next = cur;

	}

	else if (cur!=lst->head && next!=lst->tail)
	{

		prev = prevNode(*lst,cur);
		prev->next = next;
		cur->next = next->next;
		next->next = cur;
	}


}

/*void sortList(LIST* lst)
{
	LNODE* cur;
	LNODE* tmp;

	cur = tmp = lst->head ;

	while (cur->next!=NULL)
	{
		tmp = lst->head;
		while (tmp->next!=NULL)
			{
				if ( (tmp->data) > (tmp->next->data) )
					swap(tmp,tmp->next);
				tmp = tmp->next;
			}
		cur = cur->next;
	}

}*/

void main()
{
	LIST lst;
	makeEmpty(&lst);
	exampleList(&lst);

	swap(lst.head,lst.tail,&lst);

	printList(lst);
}

נתחיל מזה שלא התייחסת להערות שהיו לי לגבי swap, וחוץ מזה, ב-swap אתה לא מתייחס לכל המקרים.

אתה בטוח ששתי פונקציות ה-insertNode עובדות נכון? (כלומר, האם בלי ה-swap התכנית בכלל עובדת?)

אגב, לפי איך שזה נראה, ה-tail רק מסבך אותך. הצעה שלי - תיפטר ממנו. תוכל להחזיר אותו אחר כך כששאר הקוד יעבוד.

בלי הswap התכנית רצה, הפונ' printList מראה את הרשימה כמו שצריך

הפונ' insertNode ממומשות על פי ההכתבה של המרצה...

אממ איך ניתן להפטר מהזנב? לא יצא לי להתקל בפעולה כזאת עד עכשיו...