*상* 스토어

*상*

개인인증

팔로워0 팔로우

소개

등록된 소개글이 없습니다.

전문분야 등록된 전문분야가 없습니다.

판매자 정보

학교정보

입력된 정보가 없습니다.

직장정보

입력된 정보가 없습니다.

자격증

입력된 정보가 없습니다.

판매지수

판매중 자료수

5개
전체 판매량

108개
최근 3개월 판매량

0개
자료후기 점수

평균A
자료문의 응답률

-

전체자료 5개

최적 이진탐색트리

{{알 고 리 즘1. 최적이진탐색트리(Optimal Binary Search Tree)1) 소스코드(컴파일러 : MinGW32 - gcc compiler){#include#include#define MAX 11struct node* makeNode();//노드생성 함수void inputData();//데이터 입력void optimalSearch();//최적 root값 탐색node* tree(int i, int j);//트리 구축void inOrder(struct node* T);//트리 출력void preOrder(struct node* T);//트리의 Level과 방향 출력struct node{char data[10];//데이터값float p;//확률struct node* left;struct node* right;};struct node* root=NULL;//루트의 초기화node* key[MAX];//각 키에 노드의 주소값을 가지고 있는다.int num;//입력받을 데이터의 수float A[MAX][MAX];//검색시간을 가지고 있을 배열int R[MAX][MAX];//최소검색을 가지고 있는 키값을 갖는 배열int level=0;//노드의 Level을 나타냄int tmp=0;int tmp2=0;//0이면 부모노드의 left, 1이면 부모노드의 right에 위치{int main(){//main함수int i, j;inputData();//데이터 입력함수 호출for(i=1;ip;if(maxp);max=temp;}}}}{void optimalSearch(){//평균탐색시간이 최소가 되는 노드를 찾는 함수int i, j, k, diagonal;for(i=1;ip;R[i][i]=i;R[i][i-1]=0;}A[num+1][num]=0;R[num+1][num]=0;for(diagonal=1;diagonalright=tree(k+1, j);return p;}}{void inOrder(struct node* T){//트리를 출력하는 함수if(T!=NULL){inOrder(T->left);printf("%s ", T->data);inOrder(T->right);}}void preOrder(struct node* T){//트리의 Level과 방향을 나타내어 주는 함수if(T!=NULL){printf("%s -> ", T->data);printf("%d Level", level);if(level==0) printf("(root)");else if(level!=0 && tmp2==0) printf("/left");else if(level!=0 && tmp2==1) printf("/right");printf("n");level++;tmp2=0;preOrder(T->left);level++;tmp2=1;preOrder(T->right);}else{tmp++;level--;if(tmp==2){level--;tmp=0;}}}2) 결과화면(정상화면){{{{{{{{{{{{{{{3) 결과화면(예외의 처리-1){{4) 결과화면(예외의 처리-2){{

프로그램소스| 2005.06.02| 7페이지| 1,000원| 조회(2,673)

알고리즘, 탐색트리, 최적이진탐색트리, Optimal Binary Searc, 최적이진검색트리

미리보기

닫기
쉬트라센 알고리즘 평가A+최고예요

#include <stdio.h>#include <time.h>#define max 16//2의 거듭제곱(본 프로그램에서 계산 가능한 배열의 최대크기)void ArraySet(int n, int (*a)[max], int (*b)[max], int (*c)[max]);void ArrayMulti(int n, int (*a)[max], int (*b)[max], int (*c)[max]);void Strassen(int n, int (*a)[max], int (*b)[max], int (*c)[max]);void ArrayPrint(int n, int (*tmp)[max]);int main(){int a[max][max];int b[max][max];int c[max][max];int n;printf("2의 거듭제곱을 입력하세요 = ");scanf("%d",&n);ArraySet(n, a, b, c);printf("A 배열n");ArrayPrint(n, a);printf("nB 배열n");ArrayPrint(n, b);ArrayMulti(n, a, b, c);//표준 알고리즘 호출printf("n////표준 알고리즘 완료////n");printf("C 배열(결과)n");ArrayPrint(n, c);//배열 출력Strassen(n, a, b, c);//쉬트라센 알고리즘 호출printf("n////쉬트라센 알고리즘 완료////n");printf("C 배열(결과)n");ArrayPrint(n, c);//배열 출력return 0;}

프로그램소스| 2005.05.17| 8페이지| 1,000원| 조회(1,923)

알고리즘, 쉬트라센, 쉬트라쎈, strass, 스트라센

미리보기

닫기
자료구조 정렬방법별 시간 분석

⊙ 6가지 정렬방법으로 정렬을 하고 시간을 계산하여 평균적인 효율성 판단(선택, 삽입, 버블, 합병, 퀵정렬, 이진탐색트리)1) 코딩 리스트{코딩 리스트#include#include#include#define MAX 20int data[MAX];int random[MAX];int tmp[MAX]; // 합병정렬에서 사용double result[6];clock_t start, end;void ArrayReset(); // 배열 초기화void swap(int*, int*); // 값 바꾸는 함수void print_sorted();void SelectionSort(); // 선택정렬int Small(int);void InsertionSort(); // 삽입정렬void BubbleSort(); // 버블정렬void MergeSort(int, int); // 합병정렬void Merge(int, int, int);void QuickSort(int, int); // 퀵정렬void firstNode(int); // 이진탐색트리struct node* makeNode(int);void searchNode(struct node*,int);void inOrder(struct node*);struct node{int value;struct node *Alink;struct node *Blink;};struct node *Root=NULL;int main(){// 랜덤으로 수를 넣어주는 부분/////////int i, j, k, x, count;srand((unsigned)time(NULL));for(j=0;j 삽입정렬0 7 17 27 31 33 34 48 49 50 61 64 66 69 75 76 86 92 95 100-> 버블정렬0 7 17 27 31 33 34 48 49 50 61 64 66 69 75 76 86 92 95 100-> 합병정렬0 7 17 27 31 33 34 48 49 50 61 64 66 69 75 76 86 92 95 100-> 퀵정렬0 7 17 27 31 3 7 17 27 31 33 34 48 49 50 61 64 66 69 75 76 86 92 95 1000.000 0.000 0.000 0.000 0.000 0.000 Press any key to continue{결 과 - DATA 40개/// 정렬할 데이터99 30 5 74 19 52 87 50 55 58 72 59 93 35 97 100 13 46 37 98 49 64 6 2 26 18 83 17 32 51 62 57 8 56 71 38 3 75 60 66-> 선택정렬2 3 5 6 8 13 17 18 19 26 30 32 35 37 38 46 49 50 51 52 55 56 57 58 59 60 62 64 66 71 72 74 75 83 87 93 97 98 99 100-> 삽입정렬2 3 5 6 8 13 17 18 19 26 30 32 35 37 38 46 49 50 51 52 55 56 57 58 59 60 62 64 66 71 72 74 75 83 87 93 97 98 99 100-> 버블정렬2 3 5 6 8 13 17 18 19 26 30 32 35 37 38 46 49 50 51 52 55 56 57 58 59 60 62 64 66 71 72 74 75 83 87 93 97 98 99 100-> 합병정렬2 3 5 6 8 13 17 18 19 26 30 32 35 37 38 46 49 50 51 52 55 56 57 58 59 60 62 64 66 71 72 74 75 83 87 93 97 98 99 100-> 퀵정렬2 3 5 6 8 13 17 18 19 26 30 32 35 37 38 46 49 50 51 52 55 56 57 58 59 60 62 64 66 71 72 74 75 83 87 93 97 98 99 100-> 이진탐색트리2 3 5 6 8 13 17 18 19 26 30 32 35 37 38 46 49 50 51 52 55 56 57 58 59 60 62 64 66 71 72 74 75 83 87 93 97 98 99 1000.000 0.결 과 - DATA 60개/// 정렬할 데이터71 70 66 28 33 37 39 56 98 77 19 95 100 35 73 76 3 68 74 90 5 20 52 86 51 43 6379 10 17 47 72 38 27 14 25 58 60 8 2 92 32 24 75 1 62 18 61 40 59 49 96 91 78 655 15 34 88 12-> 선택정렬1 2 3 5 6 8 10 12 14 15 17 18 19 20 24 25 27 28 32 33 34 35 37 38 39 40 43 47 4951 52 55 56 58 59 60 61 62 63 66 68 70 71 72 73 74 75 76 77 78 79 86 88 90 91 92 95 96 98 100-> 삽입정렬1 2 3 5 6 8 10 12 14 15 17 18 19 20 24 25 27 28 32 33 34 35 37 38 39 40 43 47 4951 52 55 56 58 59 60 61 62 63 66 68 70 71 72 73 74 75 76 77 78 79 86 88 90 91 92 95 96 98 100-> 버블정렬1 2 3 5 6 8 10 12 14 15 17 18 19 20 24 25 27 28 32 33 34 35 37 38 39 40 43 47 4951 52 55 56 58 59 60 61 62 63 66 68 70 71 72 73 74 75 76 77 78 79 86 88 90 91 92 95 96 98 100-> 합병정렬1 2 3 5 6 8 10 12 14 15 17 18 19 20 24 25 27 28 32 33 34 35 37 38 39 40 43 47 4951 52 55 56 58 59 60 61 62 63 66 68 70 71 72 73 74 75 76 77 78 79 86 88 90 91 92 95 96 98 100-> 퀵정렬1 2 3 5 6 8 10 12 14 15 17 18 19 20 24 25 27 28 32 33 34 35 37 38 39 40 43 4775 76 77 78 79 86 88 90 91 92 95 96 98 100-> 이진탐색트리1 2 3 5 6 8 10 12 14 15 17 18 19 20 24 25 27 28 32 33 34 35 37 38 39 40 43 47 4951 52 55 56 58 59 60 61 62 63 66 68 70 71 72 73 74 75 76 77 78 79 86 88 90 91 92 95 96 98 1000.000 0.000 0.000 0.000 0.000 0.000 Press any key to continue⊙ 데이터 개수별 5번의 시간 계산1만개0.340 0.230 1.302 0.000 0.010 0.0100.350 0.230 1.282 0.010 0.010 0.0200.390 0.250 1.472 0.000 0.000 0.0200.340 0.230 1.282 0.010 0.000 0.0100.350 0.210 1.282 0.010 0.000 0.0201만2천개0.470 0.301 1.793 0.000 0.010 0.0200.470 0.301 1.773 0.010 0.000 0.0100.470 0.301 1.753 0.000 0.000 0.0200.470 0.301 1.753 0.010 0.010 0.0200.460 0.301 1.773 0.000 0.010 0.0201만5천개0.771 0.491 2.915 0.000 0.000 0.0200.771 0.501 3.045 0.010 0.000 0.0200.801 0.491 2.915 0.010 0.000 0.0300.781 0.491 2.904 0.000 0.010 0.0200.791 0.491 2.915 0.010 0.000 0.0301만7천개0.932 0.611 3.585 0.010 0.010 0.0300.952 0.601 3.545 0.010 0.000 0.0200.932 0.611 3.575 0.010 0.010 0.0300.942 0.601 3.545 0.000 0.000 0.0200.942 0.601 3 0.0301.352 0.861 5.137 0.010 0.010 0.0301.352 0.881 5.208 0.010 0.010 0.0301.362 0.881 5.188 0.010 0.010 0.0301.372 0.891 5.228 0.010 0.010 0.0302만2천개1.632 1.072 6.339 0.000 0.010 0.0401.632 1.062 6.299 0.010 0.010 0.0311.622 1.062 6.279 0.010 0.010 0.0311.632 1.062 6.299 0.010 0.010 0.0301.632 1.072 6.289 0.010 0.010 0.0302만5천개2.093 1.382 8.201 0.010 0.010 0.0402.093 1.382 8.212 0.010 0.010 0.0312.093 1.362 8.141 0.010 0.010 0.0402.093 1.372 8.191 0.010 0.010 0.0402.083 1.372 8.191 0.010 0.010 0.0402만7천개2.333 1.542 9.163 0.010 0.000 0.0402.333 1.532 9.174 0.010 0.010 0.0402.323 1.542 9.153 0.010 0.010 0.0402.373 1.522 9.143 0.010 0.010 0.0402.333 1.532 9.164 0.010 0.010 0.0403만개3.004 1.993 11.897 0.010 0.010 0.0503.415 2.283 11.927 0.010 0.010 0.0503.005 2.033 11.887 0.010 0.010 0.0503.004 1.993 11.877 0.010 0.010 0.0403.125 1.993 11.857 0.010 0.010 0.0503만2천개3.264 2.143 12.939 0.010 0.010 0.0503.285 2.133 12.858 0.010 0.010 0.0503.265 2.163 12.938 0.010 0.020 0.0503.264 2.173 12.989

프로그램소스| 2005.05.17| 14페이지| 1,000원| 조회(991)

자료구조, 합병정렬, 버블정렬, 퀵정렬, 이진탐색트리

미리보기

닫기
산술식을 트리로 구성하고 infix, prefix, postfix 방식으로 접근 평가D별로예요

⊙ 산술식을 트리로 구성하고 infix, prefix, postfix 방식으로 접근1) 해결방법: 우선 한 개의 다항식을 입력받아 배열에 넣고 앞에서부터 순차적으로 검색하며 배열에 push함과 동시에 트리를 구성한다.이 때 사용되는 배열은 연산자 배열과 피연산자 배열로 연산자 배열에는 char형의 값이 들어가며 피연산자 배열에는 그때 그때 생성된 피연산자 노드의 주소값이 들어간다. 이때의 자료형은 정의된 구조체의 포인터 형이다.다항식을 배열에 push 할 때의 판단 기준은 피연산자는 조건없이 순차적으로 push 되며, 연산자의 경우는 연산자의 우선순위를 따져 이전에 넣은 연산자의 우선순위가 지금 넣으려는 연산자의 우선순위보다 높거나 같으면 이전에 넣은 연산자의 계산을 선행하는 동시에 배열에서 제거(pop)해 준 후 새로운 연산자를 push 한다. 이때 이전에 넣은 연산자의 계산을 선행한다는 것은 해당 연산자에 대한 한 개의 루트와 두 개의 차일드를 가지는 트리를 구성하여 결과를 나타낸다고 생각하고 피연산자의 배열에 push 한다. 이 때 연산자 우선순위를 판단하는 과정은 각 연산자에 레벨을 부여하는 방법을 사용하였다. 그리고 괄호연산의 경우는 괄호 안에서의 계산 과정도 밖에서의 과정과 같으나 연산자 우선순위에 관계없이 괄호 안의 연산자에 대한 트리 생성을 선행해 줌으로서 해결해 주었다.그리고 다항식의 배열로의 적용이 끝났다 하더라도 트리 생성이 끝난 것이 아니다. 단지 연산자 우선순위에 따라 먼저 해주어야 하는 계산은 먼저 해주어 결국에는 우선순위가 낮은 연산자부터 높은 연산자로 배열되도록 하는 과정이었고, 다항식의 배열에 대입이 끝난 후에는 가장 오른쪽에 있는 연산자부터 트리를 생성해 주면 된다. 이때 새로 생성된 트리는 계속 위로 붙어 누적되므로 트리를 가리키던 헤더 값도 계속 변하게 된다.infix, prefix, postfix로의 접근은 재귀함수를 사용하여 노드의 주소값을 찾아 들어가며 leaf노드의 링크값은 모두 NULL인것 을 참고하여 종료조건을 만X]; // 연산자 스택 배열struct node* ope2[MAX]; // 피연산자 스택 배열(노드의 주소값을 가짐)////////////////////////////////////////////////////////////////////////////////////////스택에 필요한 함수들void pushOpe1(char a);void popOpe1();int full1();int empty1();int top1=0;void pushOpe2(struct node* a);struct node* popOpe2();int full2();int empty2();int top2=0;//////////////////////////////////////////////////////////////////////////////////////void changeTree(); // 산술식을 트리로 만들어 주는 함수struct node* makeNode(char); // 하나의 노드를 만들어 주소값을 반환void makeOneTree(char); // 한개의 루트 아래 두개의 subtree를 가지는 트리 생성void inOrder(struct node*); // infix 출력void preOrder(struct node*); // prefix 출력void postOrder(struct node*); // postfix 출력int isp(char a); // 연산자에 대한 level값 반환int main(){printf("산술식 입력 = ");gets(poly);changeTree();printf("changeTree is OKn");printf("inOrder = ");inOrder(tree);printf("npreOrder = ");preOrder(tree);printf("npostOrder = ");postOrder(tree);printf("n");return 0;}{코딩 리스트void changeTree(){int i;char data;for(i=0;i=isp(c(sizeof(struct node)); // 추가할 노드 생성newnode->value=a;newnode->alink=NULL;newnode->blink=NULL;return newnode; // 생성된 노드의 주소값 반환}{코딩 리스트void makeOneTree(char a){struct node* onenode;onenode=makeNode(a);tree=onenode;onenode->blink=popOpe2();onenode->alink=popOpe2();pushOpe2(onenode);}void inOrder(struct node* T){if(T!=NULL){inOrder(T->alink);printf("%c", T->value);inOrder(T->blink);}}void preOrder(struct node* T){if(T!=NULL){printf("%c", T->value);preOrder(T->alink);preOrder(T->blink);}}void postOrder(struct node* T){if(T!=NULL){postOrder(T->alink);postOrder(T->blink);printf("%c", T->value);}}int isp(char a){if(a=='(') return 0;else if(a=='+' || a=='-') return 1;else if(a=='*' || a=='/') return 2;else return 3;}//////////////////////////////////////////////////////////////////////////////////////// 배열을 이용한 스택 1void pushOpe1(char a){if(!full1()){ope1[top1]=a;top1++;}else printf("Ope1 is FULLn");}{코딩 리스트void popOpe1(){if(!empty1()){top1--;}else printf("Ope1 is EMPTYn");}int full1(){if(top택 2void pushOpe2(struct node* a){if(!full2()){ope2[top2]=a;top2++;}else printf("Ope2 is FULLn");}struct node* popOpe2(){struct node* tmp;if(!empty2()){top2--;tmp=ope2[top2];}else printf("Ope2 is EMPTYn");return tmp;}int full2(){if(top2==MAX) return 1;else return 0;}int empty2(){if(top2==0) return 1;else return 0;}//////////////////////////////////////////////////////////////////////////////////////{MakeFileall : polytreepolytree : polytree.ogcc -o polytree polytree.opolytree.o : polytree.cgcc -c polytree.cclean :-del polytree.exe3) 결 과{결 과D:sourceds>polytree산술식 입력 = a+b*(c-d)/echangeTree is OKinOrder = a+b*c-d/epreOrder = +a/*b-cdepostOrder = abcd-*e/+D:sourceds>D:sourceds>polytree산술식 입력 = a*(b+c/d)-echangeTree is OKinOrder = a*b+c/d-epreOrder = -*a+b/cdepostOrder = abcd/+*e-D:sourceds>D:sourceds>polytree산술식 입력 = (a+b)*(c-d)/(e+f)changeTree is OKinOrder = a+b*c-d/e+fpreOrder = /*+ab-cd+efpostOrder = ab+cd-*ef+/D:sourceds>D:sourceds>polytree산술식 입력 = a*b+(c*(d-e))/fchange졌는지.. 어디서 잘못되었는지 정확히 확인할 수 있는 방법이 없어 원인을 찾는데 조금 애를 먹었으나 프로그램 실행과정을 추적하여 이유를 찾아 보니 연산자 우선순위에 의해 미리 만들어진 트리를 다시 피연산자에 넣어주는 과정에서 차일드 노드들의 정보가 떨어져 나가게 되었다는걸 알았다. 그래서 생각한 방법이 우선 모든 피연산자는 다항식에서 스캔할 때부터 노드화를 시켜주고 배열에는 생성한 노드의 주소값이 들어가게 되는 것이다. 이렇게 되면 생성된 트리를 피연산자 스택에 넣어줄 때에도 root의 주소값만 넣어주면 됨으로 이용에 문제가 없게 되었다.그리고 추가로 개선한 부분은 본래 ( ) 연산에 대한 부분에서 문제에서는 항상 괄호 안에 두 개의 피연산자와 한 개의 연산자만을 넣어 계산을 했었다. 그래서 아무생각없이 ) 를 만나면 그 전에 입력된 연산자에 대한 트리를 생성하고 배열을 두 번 pop하면 ( 까지 삭제되어 문제가 없다고 생각하였다. 하지만 실제 식에서는 괄호 안에 한 개의 연산자만 있으란 법이 없고 또 이중, 삼중 괄호가 없으란 법이 없다. 이를 해결하기 위한 방법이 끝을 인식하게 하는 법이다. 우선 괄호 안의 식이 아무리 길어져도 계산의 방법은 괄호가 없는 산술식이랑 같다. 결과적으로 연산자 우선순위를 참조한 배열에 입력 후에는 오른쪽에 있는 연산자부터 트리화 시켜주는 것이다. 이때 트리화 시켜주며 연산자 배열의 참조가 ( 가 오게되면 트리화 시켜주는것을 중단하고 배열에서 ( 를 pop 해주면 된다.본 프로그램을 짜면서 느낀점은 프로그램을 짜기 전에 전체적으로 프로그램을 어떻게 짜야 할지 미리 생각을 하고 조금 더 넓고 깨어있는 생각을 해야 한다는 것이다. 우선 항상 프로그램을 짜기 시작할때는 내가 짜는 프로그램을 어떤 방식으로 짜야할지 진지하게 생각해보기보다는 대충.. 이렇게 하면 될까? 하는 생각으로 시작하고.. 안되면 계속 여기저기 수정하다 보니 내가 짠 프로그램이지만 대체 이부분이 왜 이렇게 되고 왜 이렇게 수정한건지 알수가 없게 되었다. 결국 다 지각한다.

프로그램소스| 2005.05.17| 7페이지| 1,000원| 조회(1,537)

postfix, infix, prefix, 후위형, 전위형

미리보기

닫기
크루스컬, 프라임 알고리즘 평가B괜찮아요

⊙ Prim's algorithm으로 찾은 Minimum Spanning Tree1) 해결방법- 기본 원리: 모든 노드를 한번씩 거치되 가장 짧은 가중치를 갖는 노드를 거친다. 단 싸이클을 이루지 말아야 한다.- 알고리즘 탐색 방법: 우선 가중치가 가장 작은 엣지를 찾은 후 Prim's 알고리즘에 의하여 지금까지 검색된 모든 노드가 가지고 있는 인접노드 중 가중치가 가장 작은 노드를 찾아 엣지를 연결한다. 이때 새로운 노드 접근시 인접한 노드를 찾아가므로 모든 노드는 단 한번씩만 검색이 되는데 노드에 접근을 할때마다 접근상태를 표시해 주면 검색의 완료를 "모든노드의 접근이 끝났을 때" 로 해줄 수 있다.- 싸이클 검사 방법: 모든 노드의 검색은 한번만 이루어 지므로 새로운 인접노드가 내가 이미 검색한 노드이면 싸이클을 이룬다.2) 코딩 리스트 및 makefile의 내용{코딩 리스트#include#define node 20#define edge 24void SpanningTree();void prim();void print_Min_edge(int a, int b);void Print_Edge(int a);int E[node][node];int freeE[node];int alink, blink, min_eg=1000, sum=0;int main(){int i, j;for(i=0;i

프로그램소스| 2005.05.17| 11페이지| 1,000원| 조회(1,197)

알고리즘, kruskal, prim, algorithm

미리보기

닫기