עבור לתוכן

בניית רשימה מקושרת דו כיוונית c++

Featured Replies

פורסם

שלום, אני בונה רשימה מקושרת דו כיוונית בשפת c++ , 

על ידי יצירת אובייקט שקרוי List שהוא אמור להצביע לתחילת הרשימה וסוף הרשימה,

ויצירת node שאמור להצביע לזה שלפניו וזה שאחריו.

הבעיה, בפונקציה  של Insert (הכנסה לתחילת הרשימה), עשיתי (רוצה לעשות בכל אופן..)שהוא יקבל את הList , ויבנה node חדש , במקרה הראשון אם הlist מצביע לnull, אז שיצביע עליו,

ואם לא מצביע לnull, אז שהאיבר החדש, יצביע למה שהצביע הlist, והlist יצביע עליו.מאוד פשוט.

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

ניסיתי לשלוח את הכתובת אבל זה אומר שאני שולח מצביע , ואז המצביעים שיש בתוך הlist אינלי גישה אליהם או משו.(שם עיקר האי הבנה שלי)

להלן הקוד:

#include <list> 
#include <iostream>
#include<stdio.h>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node* prev;
};
struct List {
    Node* head;
    Node* tail;
};

void Insert(List h, int new_data) {

    struct Node newNode;

    newNode.data = new_data;


    if (h.head == NULL) {
        newNode.next = NULL;
        newNode.prev = NULL;
        
        h.head = &newNode;
        h.tail = &newNode;
    }
    else {
        h.head->prev = &newNode;
        newNode.next = h.head;
        newNode.prev = NULL;
        h.head = &newNode;
    }
}

void displayList(struct List& h)
{
    //cout << h.head->data;

}

void main()
{
    struct List list;
    list.head = NULL;
    list.tail = NULL;
    Insert(list, 23);
    Insert(list, 234);

    displayList(list);
}
בקוד הזה הוא יוצר כל פעם list חדש.

ואם אני משנה בפונקציית הinsert ל

void Insert(List* h, int new_data) {

    struct Node newNode;

    newNode.data = new_data;


    if (h.head == NULL) {
        newNode.next = NULL;
        newNode.prev = NULL;
        
        h.head = &newNode;
        h.tail = &newNode;
    }
    else {
        h.head->prev = &newNode;
        newNode.next = h.head;
        newNode.prev = NULL;
        h.head = &newNode;
    }
}

זה יוצר בעיה בכל h.head וh.tail.

עזרה?

 

פורסם

 

יש תיבת CODE (סימון <> בסרגל הכלים. תלמד להשתמש בה (ראה דוגמה למטה של איך הקוד אמור להיראות).

 

#include <iostream>

int main (void)
{
	return 0;
}
פורסם
  • מחבר
#include <list> 
#include <iostream>
#include<stdio.h>
using namespace std;



struct Node {
	int data;
	Node* next;
	Node* prev;
};
struct List {
	Node* head;
	Node* tail;
};

void Insert(List* h, int new_data) {

	struct Node newNode;

	newNode.data = new_data;


	if (h.head == NULL) {
		newNode.next = NULL;
		newNode.prev = NULL;
		
		h.head = &newNode;
		h.tail = &newNode;
	}
	else {
		h.head->prev = &newNode;
		newNode.next = h.head;
		newNode.prev = NULL;
		h.head = &newNode;
	}
}

void displayList(struct List& h)
{

}

void main()
{
	struct List list;
	list.head = NULL;
	list.tail = NULL;
	Insert(list, 23);
	Insert(list, 234);

	displayList(list);
}

זה הקוד הכתוב

פורסם

יש כמה בעיות. אחת היא זו שבפונקציה Insert אתה מקצה אובייקט מקומי על המחסנית ואז שומר את הכתובת שלו ברשימה חיצונית. זה לא טוב, כי האובייקט המקומי "מת" בסוף הפונקציה והזיכרון שלו משוחרר, כלומר המצביע מצביע לזבל. אתה צריך להקצות ע"י new (בגישת ++C) או malloc (בגישת C).

 

למה אתה צריך לעשות include ל<list>?

 

שים לב שאתה מגדיר שהפונקציה Insert מקבלת *List אבל אתה מעביר לה struct List. אתה בטוח שזה התקמפל בכלל?

פורסם
  • מחבר

בלי ה*list כן, פשוט זה נשאר מאחד הניסויים שעשיתי..

הבעיה שהעלת בפונקציית Insert  היא הבעיה האמיתי שלי,כל פעם הוא מצביע לnull כי נוצר אובייקט זמני חדש.

כיצד אפשר לעשות שיקבל את האובייקט האמיתי, ולא העתק שלו?

פורסם

אם אתה רוצה שיהיה סיכוי שמישהו יעזור לך להבין את הבעיה, אני מציע שתעלה את הקוד האמיתי שאתה מריץ, ולא משהו שנשאר מאחר הניסויים שעשית... :nixweiss:

פורסם
  • מחבר
#include <iostream>
#include<stdio.h>
using namespace std;



struct Node {
	int data;
	Node* next;
	Node* prev;
};
struct List {
	Node* head;
	Node* tail;
};

void Insert(List h, int new_data) {

	struct Node newNode;

	newNode.data = new_data;


	if (h.head == NULL) {
		newNode.next = NULL;
		newNode.prev = NULL;
		
		h.head = &newNode;
        //its will be point to the last node in list
		h.tail = &newNode;
	}
	else {
    //"the first node will point(prev) to new node"
		h.head->prev = &newNode;
        //the new node will point(next) to the first node
		newNode.next = h.head;
		newNode.prev = NULL;
        //the head will point to the new node,and its will be first now
		h.head = &newNode;
	}
}

void displayList(struct List h)
{
	//cout << h.head->data;

}

void main()
{
	struct List list;
	list.head = NULL;
	list.tail = NULL;
	Insert(list, 23);
	Insert(list, 234);

	displayList(list);
}

אוקי..

אז זה הקוד, והוא מתקפל.

הבעיה היא כמו שאמרת, שכל insert יוצר לי העתק.

 

פורסם

מסיבה זו אתה צריך שהפונקציה Insert תקבל *List ולהעביר לה את list&.

 

זה לא יפתור את בעיית ההקצאה המקומית בתוך Insert שהערתי לך לגביה בתשובה הקודמת.

 

ניכר שיש לך עדיין חוסר הבנה מסוים על ההבדל בין אובייקט למצביע לאותו אובייקט, ולהבדל בין אופרטור הנקודה לאופרטור החץ.

פורסם
  • מחבר

יש איזה שהוא אתר או משו שמסביר את העניין בהרחבה?

פורסם

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

ארכיון

דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.

דיונים חדשים