الفريق العربي للبرمجةأرشيف المنتديات · 2000 – 2023
نسخة أرشيفية للقراءة فقط — التسجيل والمشاركة مغلقان، والمحتوى محفوظ كما كان.

مشكلة في التعامل مع Binary Tree

بدأه SIFE في 9 مايو 2009 · 3 رد · 448 مشاهدة · في الأسئلة المجابة
مشاركة: واتساب X فيسبوك تيليجرام
#1 صاحب الموضوع

السلام عليكــم ورحمـة الله وبركاتــه 

  1.  
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. struct tnode
  6. {
  7. 	int data;
  8. 	struct tnode *right,*left;
  9. };
  10.  
  11. typedef struct tnode *node;
  12.  
  13.  
  14. node creat_node(node N,int val);
  15. void preorder(node N);
  16. void postorder(node N);
  17. void inorder(node N);
  18.  
  19. int main()
  20. {
  21. 	node root = NULL;
  22. 	int x;
  23. 	while(x!=0)
  24. 	{
  25. 		scanf("%d",&x);
  26. 		root = creat_node(root, x);
  27. 	}
  28.  
  29. 	preorder(root);
  30. 	return 0;
  31. }
  32.  
  33. node creat_node(node N,int val)
  34. {
  35. 	node tmp1,tmp2;
  36.  
  37. /*
  38. التحقق من أول عقدة من أنها لاتحمل أي مؤشر لعقدة
  39.  
  40. أخرى حتى تكون بمثابة رأس الشجرة
  41. */
  42.  
  43. 	if(N==NULL)
  44. 	{
  45. 		N = (struct tnode*)malloc(sizeof(N));      
  46. 		N->data = val;
  47. 		N->left = N->right = NULL;
  48. 	}
  49.  
  50. 	else
  51. 	{
  52. 		tmp1 = N;
  53. 		while(tmp1!=NULL)
  54. 		{	
  55. 			tmp2 = tmp1 ;
  56.  
  57. /*
  58. جعل مؤشر لعقدة في جهة اليسار في حالة القيمة أصغر من القيمة الحالية
  59. */
  60.  
  61. 			if(tmp1->data > val)
  62. 				tmp1 = tmp1->left;
  63. 			else
  64. 				tmp1 = tmp1->right;
  65. 		}
  66.  
  67. /*
  68. إنشاء عقدة في جهة اليسار في حالة القيمة أصغر من القيمة الحالية
  69. */
  70.  
  71. 		if(tmp2->data > val)
  72. 		{
  73. 			tmp2->left = (struct tnode*)malloc(sizeof(N));
  74. 			tmp2 = tmp2->left;
  75. 			tmp2->data = val;
  76. 			tmp2->right = tmp2->left = NULL ;
  77. 		} 
  78.  
  79. 		else 
  80. 		{
  81. 			tmp2->right = (struct tnode*)malloc(sizeof(N));
  82. 			tmp2 = tmp2->right;
  83. 			tmp2->data = val;
  84. 			tmp2->right = tmp2->left = NULL; 
  85. 		}
  86. 	} 
  87.  
  88. 	return (N);
  89. }
  90.  
  91. void preorder(node N)
  92. {
  93. 	if(N!=NULL)
  94. 	{
  95. 		printf("%d ",N->data);
  96. 		preorder(N->left);
  97. 		preorder(N->right);
  98. 	}
  99. } 
  100.  
  101. /*
  102. void preorder(node N)
  103. void postorder(node N)
  104. void inorder(node N)
  105. */
  106.  

المشكلة أن الترجمة تكون ناجحة و لكن البرنامج بعد أن أقوم بالإدخال فيه يغلق أوتوماتيكيا .

      
تم تعديل هذه المشاركة بواسطة SudaNix في 9 مايو 2009 في 12:27

      

      
''‏اللهم إني أسالك إيمانا دائما وأسألك قلبا خاشعا وأسألك علما ‏نافعا وأسألك يقينا صادقا وأسألك دينا قيما وأسألك العافية من كل ‏بلية''
'‏اللهم أغفر للمؤمنين و المؤمنات و المسلمين و المسلمات الأحياء ‏منهم و الأموات'
www.it-scoop.com

    

  

    
    

      
#2
        
        

      
وعليكــم السـلام ورحمة الله وبركاتـه..
لقد ترجمت الكود على gcc وعمل معي بدون مشاكل  :wink: .
ولم اشاهد اي خطأ يسبب Crash للبرنامج ، مثل استخدام Null pointer .
صحيح انه سيحدث Memory leak في حالة استخدامك لهذا الكود في برنامج اخر "بسبب عدم حذف العقد" ، لكن هذا لا يسبب crashing.
* ما هو المترجم او ال IDE الذي تعمل عليه ؟ ربما يكون من النوع الذي يغلق النتيجة فور وصول البرنامج الى جملة return 0 ؟
* تحقق من القيمة المعادة من malloc ، ربما قد لا توجد مساحة كافية لحجز عقدة جديدة ، وستكون القيمة المعادة هي صفر .
بالتوفيق.

      
      

      

    

  

    
    

      
#3
        
        

      
لقد فحصت البرنامج بال Valgrind وكشفت الخطا  :)
قم بتغيير مساحة الحجز لدوال malloc  من :
[color= #000000;]([color= #0000ff;]struct tnode[color= #000000;]*[color= #000000;])malloc[color= #000000;]([color= #0000ff;]sizeof[color= #000000;](N[color= #000000;])[color= #000000;]);
الى :
[color= #000000;]([color= #0000ff;]struct tnode[color= #000000;]*[color= #000000;])malloc[color= #000000;]([color= #0000ff;]sizeof[color= #000000;]([color= #0000ff;]struct tnode[color= #000000;])[color= #000000;]);
لان N عبارة عن مؤشر وحجمه ثابت "4 بايت في انظمة 32-بت" ، شوف الامثلة التالية:
printf[color= #000000;]([color= #A31515;]"%d[color= #A31515; font-weight: bold;]n",[color= #0000ff;]sizeof[color= #000000;](root[color= #000000;])[color= #000000;]);

	printf[color= #000000;]([color= #A31515;]"%d[color= #A31515; font-weight: bold;]n",[color= #0000ff;]sizeof[color= #000000;]([color= #0000ff;]struct tnode[color= #000000;])[color= #000000;]);

printf[color= #000000;]([color= #A31515;]"%d[color= #A31515; font-weight: bold;]n",[color= #0000ff;]sizeof[color= #000000;]([color= #0000ff;]struct tnode[color= #000000;]*[color= #000000;])[color= #000000;]);
1- المساحة المحجوزة  = 4 بايت . لان root مؤشر.
2- المساحة المحجوزة = 12 بايت ." حجم السجل = حجم محتوياته = 4+4+4 ".
3- المساحة  = 4 بايت.
تبقى بعض الاشياء البسيطة :
مثل تعيين قيمة ل x قبل الدخول في التكرار:


==5293== Conditional jump or move depends on uninitialised value(s)
==5293==    at 0x80484AB: main (main.c:21)


واصلاح مشاكل تسرب الذاكرة :


==5293== malloc/free: in use at exit: 48 bytes in 4 blocks.==5293== malloc/free: 4 allocs, 0 frees, 48 bytes allocated.




==5293== LEAK SUMMARY:
==5293==    definitely lost: 12 bytes in 1 blocks.
==5293==    indirectly lost: 36 bytes in 3 blocks.
==5293==      possibly lost: 0 bytes in 0 blocks.
==5293==    still reachable: 0 bytes in 0 blocks.
==5293==         suppressed: 0 bytes in 0 blocks.


ملاحظة على الهامش : valgrind هي أداة قوية على اللينوكس تساعد في اكتشاف اخطاء الذاكرة :
اقتباس
The Valgrind distribution currently includes six production-quality tools: a memory error detector, two thread error detectors, a cache and branch-prediction profiler, a call-graph generating cache profiler, and a heap profiler. It also includes one experimental tool, which detects out of bounds reads and writes of stack, global and heap arrays. It runs on the following platforms: X86/Linux, AMD64/Linux, PPC32/Linux, PPC64/Linux.
لاستخدامها :
ترجم البرنامج ب gcc مع تفعيل خاصية ال debug ، كالاتي :


gcc -g main.c


ثم شغل ال valgrind :


valgrind --leak-check=yes ./a.out


بالتوفيق.

      
      

      

    

  

    
    

      
#4
        
        

      
اقتباس
لقد ترجمت الكود على gcc وعمل معي بدون مشاكل wink.gif .
يبدو أن المشكلة كانت في النظام لأنه حاليا مفيرس لهذا أعطيت الشيفرة لصديقي و نجحت معه أيضا .
اقتباس
* ما هو المترجم او ال IDE الذي تعمل عليه ؟ ربما يكون من النوع الذي يغلق النتيجة فور وصول البرنامج الى جملة return 0 ؟
MinGw تحت الويندوز .
اقتباس
قم بتغيير مساحة الحجز لدوال malloc من :
كنت أعتقد أنه عند إعطاء مؤشر فإن الحجم سيحسب على المؤشر إليه و ليس المؤشر نفسه :D .
printf("%d\n",sizeof(root));
printf("%d\n",sizeof(struct tnode));
printf("%d\n",sizeof(struct tnode*));
شكرا لك على المعلومات القيمة .
بإذن الله سأرجع إلى لينكس في القريب إن شاء الله لأنه حاليا معطل و لم أجد له حلا .

      
      

      
''‏اللهم إني أسالك إيمانا دائما وأسألك قلبا خاشعا وأسألك علما ‏نافعا وأسألك يقينا صادقا وأسألك دينا قيما وأسألك العافية من كل ‏بلية''
'‏اللهم أغفر للمؤمنين و المؤمنات و المسلمين و المسلمات الأحياء ‏منهم و الأموات'
www.it-scoop.com

    

  

    
    
    
 مواضيع مشابهة