PDA

View Full Version : سوال: درخواست بررسی سورس این برنامه



shahinshyd
جمعه 09 اردیبهشت 1390, 12:59 عصر
با سلام
ما اینجا دو تا برنامه داریم که مربوط به مبحث ساختمان داده هست

http://barnamenevis.org/attachment.php?attachmentid=69296&d=1304068684
1-برنامه ای که فرم پرانتزی یک درخت دودویی را به صورت رشته از ورودی خوانده وان را به فرم لیست پیوندی در حافظه پیاده سازی کرده و پیمایش های مختلف ان را چاپ میکند.


#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct Node{
int value;
Node*left;
Node*right;
};
int inorder(Node*node1,Node*node2){
int x=1;
if(node1->left&&node2->left)
x=x&inorder(node1->left,node2->left);
else
if(node1->left != node2->left)
x=0;
else
x=x&(node1->value==node2->value);
if(node1->right&&node2->right)
x=x&inorder(node1->right,node2->right);
else
if(node1->right != node2->right)
x=0;
return x;
}
int postorder(Node*node1,Node*node2){
int x=1;
if(node1->left&&node2->left)
x=x&&inorder(node1->left,node2->left);
else
if(node1->left != node2->left)
x=0;
if(node1->right&&node2->right)
x=x&&inorder(node1->right,node2->right);
else
if(node1->right != node2->right)
x=0;
x=x&&(node1->value==node2->value);
return x;
}
int preorder(Node*node1,Node*node2){
int x=1;
x=x&(node1->value==node2->value);
if(node1->left&&node2->left)
x=x&inorder(node1->left,node2->left);
else
if(node1->left != node2->left)
x=0;
if(node1->right&&node2->right)
x=x&inorder(node1->right,node2->right);
else
if(node1->right != node2->right)
x=0;
return x;
}
void Insert(int n,int x,Node*root){
Node*temp=root;
int right=0;
for(int h=1;h!=n && temp;){
for(int j=n;j/2>h;j/=2);
if(j==h*2){
if(temp->left)
temp=temp->left;
right=0;
}
if(j==h*2+1){
if(temp->right)
temp=temp->right;
right=1;
}
h=j;
}
Node*t=(Node*)malloc(sizeof(Node));
t->value=x;
t->left=NULL;
t->right=NULL;
if(right)
temp->right=t;
else
temp->left=t;
}

int main(){
clrscr();
int n,x;
Node*root1=NULL,*root2=NULL;
printf("First tree elements ... \n");
for(;;){
printf("Please Enter a Number for element Place : ");
scanf("%d",&n);
if(n==0)
break;
printf("Please Enter a Number : ");
scanf("%d",&x);
if(!root1){
Node*temp=(Node*)malloc(sizeof(Node));
temp->value=x;
temp->left=NULL;
temp->right=NULL;
root1=temp;
}else
Insert(n,x,root1);
}
printf("\nSecond tree elements ... \n");
for(;;){
printf("Please Enter a Number for element Place : ");
scanf("%d",&n);
if(n==0)
break;
printf("Please Enter a Number : ");
scanf("%d",&x);
if(!root2){
Node*temp=(Node*)malloc(sizeof(Node));
temp->value=x;
temp->left=NULL;
temp->right=NULL;
root2=temp;
}else
Insert(n,x,root2);
}

int issame=inorder(root1,root2)&&postorder(root1,root2)&&preorder(root1,root2);
if(issame)
printf("Binary trees are same");
else
printf("Binary trees are not same");
return 0;
}


2-این برنامه تابعی است که زیردرخت های چپ و راست یک درخت را جابه جا میکند(تا اخرین سطح بصورت بازگشتی ).این تابع دربرنامه میاد خروجی را برای یک درخت فرضی(با چاپ پیمایش های درخت اولیه ودرخت حاصل)ازمایش میکند.

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct Node{
int value;
Node*left;
Node*right;
};
void Insert(int n,int x,Node*root){
Node*temp=root;
int right=0;
for(int h=1;h!=n && temp;){
for(int j=n;j/2>h;j/=2);
if(j==h*2){
if(temp->left)
temp=temp->left;
right=0;
}
if(j==h*2+1){
if(temp->right)
temp=temp->right;
right=1;
}
h=j;
}
Node*t=(Node*)malloc(sizeof(Node));
t->value=x;
t->left=NULL;
t->right=NULL;
if(right)
temp->right=t;
else
temp->left=t;
}
void inorder(Node*node){
if(node->left)
inorder(node->left);
printf("%d,",node->value);
if(node->right)
inorder(node->right);
}
void postorder(Node*node){
if(node->left)
postorder(node->left);
if(node->right)
postorder(node->right);
printf("%d,",node->value);
}
void preorder(Node*node){
printf("%d,",node->value);
if(node->left)
preorder(node->left);
if(node->right)
preorder(node->right);
}
Node*Reverse(Node*root){
Node*temp=root;
if(temp){
Node*t=temp->left;
temp->left=Reverse(temp->right);
temp->right=Reverse(t);
}
return temp;
}
int main(){
clrscr();
int n,x;
Node*root=NULL;
for(;;){
printf("Please Enter a Number for element Place : ");
scanf("%d",&n);
if(n==0)
break;
printf("Please Enter a Number : ");
scanf("%d",&x);
if(!root){
Node*temp=(Node*)malloc(sizeof(Node));
temp->value=x;
temp->left=NULL;
temp->right=NULL;
root=temp;
}else
Insert(n,x,root);
}
printf("\b \ninlorder (LVR) : ");
inorder(root);
printf("\b \npostlorder (LRV) : ");
postorder(root);
printf("\b \nprelorder (VLR) : ");
preorder(root);
printf("\b \b");
root=Reverse(root);
printf("\b \ninlorder (LVR) : ");
inorder(root);
printf("\b \npostlorder (LRV) : ");
postorder(root);
printf("\b \nprelorder (VLR) : ");
preorder(root);
printf("\b \b");
return 0;
}



اگه امکان داره از اساتید میخوام یک توضیحی در مورد سورس های این دو برنامه بدهند

shahmohammadi
جمعه 09 اردیبهشت 1390, 21:55 عصر
به نظر شما در تابع main برنامه اول در اين قسمتش:
if(!root1){
Node*temp=(Node*)malloc(sizeof(Node));
temp->value=x;
temp->left=NULL;
temp->right=NULL;
root1=temp;
}
چه لزومي داشت كه از متغير كمكي استفاده كنيم. من كه فكر مي كنم مي تونستيم به صورت زير هم بنويسيم:


if(!root1){
root1->value=x;
root1->left=NULL;
root1->right=NULL;
}


با تشكر.

shahmohammadi
شنبه 10 اردیبهشت 1390, 00:33 صبح
در ضمن برنامه اول هم كارش اون چيزي نبود كه نوشتين.
در ابتدا مي آد و دو درخت باينري رو از طريق شماره مكان هاش (n) مقدار (x) مي ده. بعد با هم مقايسه مي كنه كه آيا برابر هستند يا نه. و در آخر نتيجه رو چاپ مي كنه.
منظور از شماره مكان رو هم حتما مي دونيد چيه؟:

69324

حالا اگه قبل از پدر به پسرش مقدار بديم پدر اون مقدار رو مي گيره و نيز اگه به يه عنصري دوباره مقدار بديم مقدار دوم رو نمي پذيره.

shahinshyd
شنبه 10 اردیبهشت 1390, 23:10 عصر
به نظر شما در تابع main برنامه اول در اين قسمتش:
if(!root1){
Node*temp=(Node*)malloc(sizeof(Node));
temp->value=x;
temp->left=NULL;
temp->right=NULL;
root1=temp;
}
چه لزومي داشت كه از متغير كمكي استفاده كنيم. من كه فكر مي كنم مي تونستيم به صورت زير هم بنويسيم:


if(!root1){
root1->value=x;
root1->left=NULL;
root1->right=NULL;
}


با تشكر.

سلام
با تشکر از نظری که دادی -اگه چیزی از این دو سورس فهمیدی چند خط در مورد بدنه این دو برنامه توضیح بده

shahmohammadi
شنبه 10 اردیبهشت 1390, 23:22 عصر
شما در مورد كدوم قسمت مشكل دارين.

shahmohammadi
شنبه 10 اردیبهشت 1390, 23:46 عصر
خوب حالا من توضيح كلي مي دم.
برنامه اول اومده براي اينكه تك تك عناصر دو تا درخت رو مقايسه كنه از سه تا پيمايش استفاده كرده. اگه از يكي هم استفاده ميكرد به نتيجه مي رسيد اما چون برنامه جنبه آموزشي داشته اومده از هر سه تا استفاده كرده.
نوع مقايسه اش هم به اين صورته كه مي آد يه ايكسي رو اول 1 مي كنه بعد هر دو درخت رو پيمايش مي كنه و اگه ديد در عنصري برابر نيستند اون ايكس رو 0 مي كنه. در آخر ايكس رو بررسي مي كنه و مي بينه كه آيا 0 شده يا 1.
حالا چون از هر سه روش پيمايش استفاده كرده خروجي هر سه پيمايش رو در دستور زير باهم and كرده:
int issame=inorder(root1,root2)&&postorder(root1,root2 )&&preorder(root1,root2);

اگه فقط از يه پيمايش استفاده مي كرد برنامه به صورت زير مي شد:
#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

typedef struct Node{

int value;

Node*left;

Node*right;

};

int inorder(Node*node1,Node*node2){

int x=1;

if(node1->left&&node2->left)

x=x&inorder(node1->left,node2->left);

else

if(node1->left != node2->left)

x=0;

else

x=x&(node1->value==node2->value);

if(node1->right&&node2->right)

x=x&inorder(node1->right,node2->right);

else

if(node1->right != node2->right)

x=0;

return x;

}


void Insert(int n,int x,Node*root){

Node*temp=root;

int right=0;

for(int h=1;h!=n && temp;){

for(int j=n;j/2>h;j/=2);

if(j==h*2){

if(temp->left)

temp=temp->left;

right=0;

}

if(j==h*2+1){

if(temp->right)

temp=temp->right;

right=1;

}

h=j;

}

Node*t=(Node*)malloc(sizeof(Node));

t->value=x;

t->left=NULL;

t->right=NULL;

if(right)

temp->right=t;

else

temp->left=t;

}



int main(){

clrscr();

int n,x;

Node*root1=NULL,*root2=NULL;

printf("First tree elements ... \n");

for(;;){

printf("Please Enter a Number for element Place : ");

scanf("%d",&n);

if(n==0)

break;

printf("Please Enter a Number : ");

scanf("%d",&x);

if(!root1){

Node*temp=(Node*)malloc(sizeof(Node));

temp->value=x;

temp->left=NULL;

temp->right=NULL;

root1=temp;

}else

Insert(n,x,root1);

}

printf("\nSecond tree elements ... \n");

for(;;){

printf("Please Enter a Number for element Place : ");

scanf("%d",&n);

if(n==0)

break;

printf("Please Enter a Number : ");

scanf("%d",&x);

if(!root2){

Node*temp=(Node*)malloc(sizeof(Node));

temp->value=x;

temp->left=NULL;

temp->right=NULL;

root2=temp;

}else

Insert(n,x,root2);

}



int issame=inorder(root1,root2);

if(issame)

printf("Binary trees are same");

else

printf("Binary trees are not same");

return 0;

}