Скажите пожалуйста этот код строит дерево? - C (СИ)
Формулировка задачи:
Что то я не пойму он стороит дерево или просто связанные списки
#include <stdio.h> #include <stdlib.h> #include <conio.h> struct ListElem { int data; struct ListElem* next; }; struct List { struct ListElem* head; struct ListElem* tail; int size; }; struct List* createList() { struct List* r = malloc(sizeof(struct List)); r->head = NULL; r->tail = NULL; r->size = 0; return r; } int strToInt(char str) { int chislo=0; chislo = str - 48; return chislo; } void addFirst(struct List* a,int x) { struct ListElem* e = malloc(sizeof(struct ListElem)); e->data = x; e->next = a->head; a->head = e; if(a->size == 0) a->tail = e; a->size++; } void addTail(struct List* l,int x) { struct ListElem* a = malloc(sizeof(struct ListElem)); a->data = x; a->next = NULL; if(l->size == 0) l->head = a; else l->tail->next = a; l->size++; l->tail = a; } int size(struct List* l) { return l->size; } int delFirst(struct List* l) { int ch = l->head; struct ListElem* phead = l->head; l->head = l->head->next; free(phead); l->size--; return ch; } int delTail(struct List* l) { int ch; struct ListElem* a = l->head; int i; if(l->size == 1) { ch = a->data; free(a); l->size = 0; } else { for(i=0;i<l->size-2;i++) a = a->next; l->tail = a; ch = a->next->data; free(a->next); l->size--; } return ch; } int getElem(struct List* l,int index) { struct ListElem* a = l->head; int i; for(i=0;i<index;i++) a = a->next; return a->data; } int strLen(char* c) { char* p = c; while(*p++); return (p-(c+1)); } int prioritet(char ch)//Возвращает приоритет операции { if((ch == '+')||(ch == '-')) return 1; if((ch == '*')||(ch =='/')) return 2; } int findPriorPredElem(struct List* a,int index)//Возвращает приоритет предыдущего элемента { struct ListElem* p; int i; p = a->head; for(i=0;i < index - 1;i++) p = p->next; return prioritet((char)p->data); } int arnost(char op) { if((op == '+')||(op == '-')||(op == '*')||(op == '/')) return 2; } int operResult(struct List* stack,char operation) { int i; double result = 0; int fop,sop; if(operation == '+') result = (delTail(stack)) + (delTail(stack)); if(operation == '*') result = (delTail(stack)) * (delTail(stack)); if(operation == '-') { sop = (delTail(stack)); fop = (delTail(stack)); result = fop - sop; } if(operation == '/') { sop = (delTail(stack)); fop = (delTail(stack)); result = fop / sop; } return result; } struct List* strToRPN(char* str) { struct List* quene; struct List* operation; int i; quene = createList(); operation = createList(); for(i=0;i<strLen(str);i++)//Цикл чтения входной строки { if((str[i]>=48)&&(str[i]<=57)) addFirst(quene,(int)str[i]); else { if((operation->size > 0)&&(prioritet(str[i]) < findPriorPredElem(operation,operation->size))) addFirst(quene,delTail(operation)); addTail(operation,(int)str[i]); } } while(operation->size > 0) addFirst(quene,delTail(operation)); //Проблема при перекидывании последнего плюса(проблема в delTail(исправлено)) return quene; } int RPNToResult(struct List* quene) { struct List* stack; int tmpResult; int i,arn,ret_getElem; stack = createList(); for(i=quene->size - 1;i >= 0;i--) { ret_getElem = getElem(quene,i); if((ret_getElem >= (int)'0')&&(ret_getElem <= (int)'9')) addTail(stack,strToInt(ret_getElem)); else { addTail(stack,operResult(stack,ret_getElem)); } } return delTail(stack); } int main() { struct List* ochred; int i; ochred = strToRPN("1+2+3+4*5+9"); for(i = ochred->size - 1;i >= 0;i--) printf("%c",getElem(ochred,i)); printf("\n"); printf("%d",RPNToResult(ochred)); getch(); return 0; }
Решение задачи: «Скажите пожалуйста этот код строит дерево?»
textual
Листинг программы
node * BuildTree(char s[],int & ps){ node * n=new node; n->op=s[ps++]; if(n->op=='+'||n->op=='-'||n->op=='*'||n->op=='/') { n->left=BuildTree(s,ps); n->right=BuildTree(s,ps); } else n->right=n->left=NULL; return n; }
Объяснение кода листинга программы
В данном коде строится дерево вычисления.
- В функции
BuildTree
создается новый узелnode
и инициализируется указательn
на этот узел. - В
n
записывается оператор, который является первым элементом в строкеs
и увеличиваетсяps
для перехода к следующему элементу. - Если оператор
n->op
равен+
,-
,*
или/
, то рекурсивно вызывается функцияBuildTree
для левого и правого поддеревьев. Результаты этих вызовов записываются вn->left
иn->right
соответственно. - Если оператор
n->op
не равен+
,-
,*
или/
, то оба поддерева (n->left
иn->right
) инициализируются какNULL
, что означает отсутствие поддеревьев для данного узла. - В конце функции возвращается
n
, который является вершиной построенного дерева. Таким образом, данный код строит дерево вычисления, где каждый узел представляет собой операцию, а его потомки - операнды этой операции.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д