Skip to content

Instantly share code, notes, and snippets.

@hanjae-jea

hanjae-jea/01_fibRecur.cpp

Last active November 7, 2019 12:30
Show Gist options
  • Save hanjae-jea/db8e3becfc87662f25cf6e1c390203d2 to your computer and use it in GitHub Desktop.
Save hanjae-jea/db8e3becfc87662f25cf6e1c390203d2 to your computer and use it in GitHub Desktop.
Download ZIP
KUPT Data structure
Raw
01_fibRecur.cpp
#include <stdio.h>
long long fib(int n, long long fib1, long long fib2)
{
if (n == 1) return fib1;
else return fib(n - 1, fib2, fib1 + fib2);
}
int main()
{
while (1)
{
int n;
scanf("%d", &n);
printf(": %lld", fib(n, 0, 1));
}
return 0;
}
Raw
01_linkedlist.cpp
#include <stdio.h>
typedef struct node{
int data;
struct node *next;
} node;
int main()
{
node a, b, c;
a.data = 2;
a.next = &b;
b.data = 5;
b.next = &c;
c.data = 3;
c.next = NULL;
node head;
head.next = &a;
printf("연결 리스트 출력\n");
node *p = head.next;
while( p != NULL ){
printf("%d -> ", p->data);
p = p->next;
}
printf("X\n");
node d;
d.data = 4;
d.next = a.next;
a.next = &d;
p = head.next;
while( p != NULL ){
printf("%d -> ", p->data);
p = p->next;
}
printf("X\n");
return 0;
}
Raw
01_recursion.cpp
#include <stdio.h>
int strLength(char* s) {
if (*s == NULL)
return 0;
else
return strLength(s + 1) + 1;
}
int palindrome(char* s) {
if (strLength(s) <= 1){
return 1; // string is palindrome
}
if (s[0] == s[strLength(s) - 1]) {
s[strLength(s) - 1] = NULL;
return palindrome(s + 1);
}
else return 0; // string is not palindrome
}
int main() {
char arr[100];
int i;
for (i = 0; i < 3; i++)
{
scanf("%s", arr);
if (palindrome(arr)) printf("string is palindrome\n");
else printf("No palindrome ㅜㅜ\n");
}
return 0;
}
Raw
02_brace.cpp
#include <stdio.h>
#include <stack>
using namespace std;
stack<char> st;
int main()
{
char s[100];
while (true) {
gets_s(s, 100);
if (s[0] == '.') break;
int c = 0;
int yesorno = 1;
while (s[c] != NULL) {
if (s[c] == '(' || s[c] == '{' || s[c] == '[')
st.push(s[c]);
else if (s[c] == ')') {
if (!st.empty() && st.top() == '(') {
st.pop();
}
else {
yesorno = 0;
break;
}
}
else if (s[c] == '}') {
if (!st.empty() && st.top() == '{') {
st.pop();
}
else {
yesorno = 0;
break;
}
}
else if (s[c] == ']') {
if (!st.empty() && st.top() == '[') {
st.pop();
}
else {
yesorno = 0;
break;
}
}
c++;
}
// stack에 자료가 남아있으면
if (!st.empty()) {
yesorno = 0;
while (!st.empty()) st.pop(); // 스택을 비워라
}
if (yesorno == 1) printf("yes\n");
else printf("no\n");
}
return 0;
}
Raw
02_calc.cpp
#include <stdio.h>
#include <stack>
using namespace std;
stack<char> oper;
stack<double> ep;
int main()
{
char s[100];
scanf("%s", s);
char postfix[100]; int p = 0;
int c = 0;
while (s[c] != NULL) {
if ('0' <= s[c] && s[c] <= '9') { // 1. 숫자는 그냥 집어넣는다
postfix[p++] = s[c++];
continue;
}
if (s[c] == '+' || s[c] == '-') { // 2. 덧셈 뺄셈은 연산자 우선순위가 높은거나, 같은걸 만나면 꺼낸다.
while (!oper.empty() && oper.top() != '(') { // 괄호 제외하고 +,-,*,/ 전부 다 꺼낸다.
postfix[p++] = oper.top();
oper.pop();
}
oper.push(s[c]); // 자기 자신 스택에 넣는다.
}
else if (s[c] == '*' || s[c] == '/') { // 3. 곱셈 나눗셈은 연산자 우선순위 높은거나 같은걸 만나면 꺼낸다.
while (!oper.empty() && (oper.top() == '*' || oper.top() == '/')) { // 곱하기 나누기보다 높은 건 없으니까. 곱하기 나누기 만나면 꺼낸다
postfix[p++] = oper.top();
oper.pop();
}
oper.push(s[c]);
}
else if (s[c] == '(') {
oper.push(s[c]); // 여는 소괄호는 그냥 스택에 넣는다.
}
else if (s[c] == ')') { // 닫는 소괄호는 여는 소괄호 만날때까지 다 꺼낸다
while (!oper.empty() && oper.top() != '(') {
postfix[p++] = oper.top();
oper.pop();
}
if (oper.top() == '(') oper.pop(); // 남은 여는 소괄호는 삭제.
}
c++;
}
while (!oper.empty()) { // 다 끝나면 스택 비운다.
postfix[p++] = oper.top();
oper.pop();
}
postfix[p] = NULL; // 끝.
p = 0;
while (postfix[p] != NULL) {
if ('0' <= postfix[p] && postfix[p] <= '9') {
ep.push(postfix[p++] - '0');
continue;
}
if (ep.empty()) { // b 를 꺼내려고 했는데, 스택에 자료가 없으면
printf("INVALID_FORMULA"); return 0;
}
double b = ep.top(); ep.pop(); // 두 개 꺼내서 연산해서 다시 넣는다.
if (ep.empty()) { // a를 꺼내려고 했는데, 스택에 자료가 없으면
printf("INVALID_FORMULA"); return 0;
}
double a = ep.top(); ep.pop();
if (postfix[p] == '+') {
ep.push(a + b);
}
else if (postfix[p] == '-') {
ep.push(a - b);
}
else if (postfix[p] == '*') {
ep.push(a * b);
}
else if (postfix[p] == '/') {
if (b == 0) {
printf("DIVIDED_BY_ZERO");
return 0; // 프로그램 종료
}
ep.push(a / b);
}
else {
printf("INVALID_FORMULA");
return 0;
}
p++;
}
printf("%g", ep.top());
return 0;
}
Raw
1107_BST.c
//
// binarySearchTreeADT.cpp
// simple_c
//
// Created by 제한재 on 2019/11/07.
// Copyright © 2019 제한재. All rights reserved.
//
#include <stdbool.h>
#include <stdlib.h>
#include "binarySearchTreeADT.h"
bool _bstInsert(TREE_NODE* node, TREE_NODE* newNode)
{
if( node->data < newNode->data ){
if( node->right == NULL ){
node->right = newNode;
return true;
}
return _bstInsert(node->right, newNode);
}
else if( node->data > newNode->data ){
if( node->left == NULL ){
node->left = newNode;
return true;
}
return _bstInsert(node->left, newNode);
}
else return false;
}
TREE_NODE* __bstInsert(TREE_NODE* node, TREE_NODE* newNode){
if( node == NULL ) return newNode;
if( node->data < newNode->data ){
node->right = __bstInsert(node->right, newNode);
}
else{
node->left = __bstInsert(node->left, newNode);
}
return node;
}
bool bstInsert(BST_TREE* tree, int data)
{
if( tree == NULL ) return false;
TREE_NODE* newNode = (TREE_NODE*)malloc(sizeof(TREE_NODE));
if( newNode == NULL ) return false;
newNode->data = data;
newNode->left = newNode->right = NULL;
if( tree->root == NULL ){
tree->root = newNode;
return true;
}
/*
TREE_NODE* node = tree->root;
while( node ){
if( node->data < newNode->data ){ // to right
if( node->right == NULL ){
node->right = newNode;
return true;
}
else{
node = node->right;
}
}
else if( node->data > newNode->data ){ // to left
if( node->left == NULL ){
node->left = newNode;
return true;
}
node = node->left;
}
else {
// if has duplicate value, then do not insert
return false;
}
}
return false;*/
return _bstInsert(tree->root, newNode);
}
TREE_NODE* _bstSearch(TREE_NODE* node, int key)
{
if( node == NULL ) return NULL;
if( node->data == key ) return node;
else if( node->data < key ) return _bstSearch(node->right, key);
else return _bstSearch(node->left, key);
}
TREE_NODE* bstSearch(BST_TREE* tree, int key)
{
TREE_NODE* node = tree->root;
while( node ){
if( node->data == key ) return node;
else if( node->data < key ) node = node->right;
else node = node->left;
}
return NULL;
return _bstSearch(tree->root, key);
}
TREE_NODE* _getMaximumChild(TREE_NODE* node)
{
if( node->right == NULL ) return node;
TREE_NODE* X = _getMaximumChild(node->right);
if( node->right == X ){
node->right = X->left;
}
return X;
}
TREE_NODE* __bstDelete(TREE_NODE* root, int key) // node subtree에서 key 값을 지우고 난 root
{
if( root == NULL ) return NULL;
if( root->data < key ){
root->right = __bstDelete(root->right, key);
return root;
}
else if( root->data > key ){
root->left = __bstDelete(root->left, key);
return root;
}
else{ // data == key
if( root->left == NULL && root->right == NULL ){
return NULL;
}
else if( root->left == NULL ){
return root->right;
}
else if( root->right == NULL ){
return root->left;
}
else{
TREE_NODE *X = _getMaximumChild(root->left);
root->data = X->data;
root->left = __bstDelete(root->left, X->data);
return root;
}
}
}
TREE_NODE* _bstDelete(TREE_NODE *node, int key)
{
if( node == NULL ) return NULL;
if( node->data < key ){
node->right = _bstDelete(node->right, key);
return node;
} else if( node->data > key ){
node->left = _bstDelete(node->left, key);
return node;
}else { // node 자기 자신이 삭제의 대상이 되는 경우.
TREE_NODE *X = _getMaximumChild(node->left);
if( X == node->left ) {
X->left = node->left->left;
X->right = node->right;
}
else{
X->left = node->left;
X->right = node->right;
}
return X;
}
}
bool bstDelete(BST_TREE *tree, int key)
{
TREE_NODE* node = tree->root, *pre = NULL;
return _bstDelete(tree->root, key);
while( node )
{
if( node->data < key ){
pre = node;
node = node->right;
} else if( node->data > key ){
pre = node;
node = node->left;
}
else{
// delete!
if( node->left == NULL ){
// node->right 올려보내기
if( pre->left == node ){
pre->left = node->right;
} else{
pre->right = node->right;
}
}
else if( node->right == NULL ){
// node->left 올려보내기
if(pre->right==node){
pre->right=node->left;
}else{
pre->left=node->left;
}
}
else{ // node->data == key
TREE_NODE* X = node->left;
TREE_NODE* T;
while( true ){
if( X->right->right == NULL ){
T = X->right;
X->right = T->left;
break;
}
X = X->right;
}
if( pre->right == node ){
pre->right = T;
} else{
pre->left = T;
}
T->left = node->left;
T->right = node->right;
free(node);
}
}
}
}
Raw
function_pointer.c
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
struct node{
void *data;
struct node* link;
};
struct student{
int id;
char name[20];
};
typedef struct linkedList{
struct node* first;
int (*cmp)(void* , void*); // 함수 포인터 변수
void (*print)(void*);
} LIST;
bool insertItem(LIST* list, void* data)
{
struct node* newNode = (struct node*)malloc(sizeof(struct node));
newNode->data = data;
newNode->link = NULL;
if( list->first == NULL ){
list->first = newNode;
return true;
}
struct node* t = list->first;
if( (*list->cmp)(newNode->data, t->data) < 0 ){
newNode->link = t;
list->first = newNode;
return true;
}
while( t->link != NULL ){
if( (*list->cmp)(t->data, newNode->data) < 0 &&
(*list->cmp)(newNode->data, t->link->data) < 0 ){
// t < newNode < t->link
break;
}
t = t->link;
}
newNode->link = t->link;
t->link = newNode;
return true;
}
void printList(LIST* list)
{
struct node* t = list->first;
while( t != NULL ){
(*list->print)(t->data);
t = t->link;
}
printf("\n");
}
int cmpInt(void *i1, void *i2)
{
int a = *(int*)i1, b = *(int*)i2;
if( a < b ) return -1;
else if( a == b ) return 0;
else return 1;
// return a - b;
}
int cmpStudent(void *s1, void *s2)
{
return ((struct student*)s1)->id - ((struct student*)s2) -> id;
}
void printInt(void *i)
{
printf("%d ", *(int*)i);
}
void printStudnet(void *s)
{
printf("(번호:%d, 이름:%s) ", ((struct student*)s)->id, ((struct student*)s)->name);
}
void printName(void *s)
{
printf("%s ", ((struct student*)s)->name);
}
int main()
{
LIST* intList = (LIST*)malloc(sizeof(LIST));
intList->first = NULL;
intList->cmp = cmpInt;
intList->print = printInt;
printList(intList);
int x = 3;
insertItem(intList, &x);
int y = 2;
insertItem(intList, &y);
// printList(intList);
LIST* studentList = (LIST*)malloc(sizeof(LIST));
studentList->first = NULL;
studentList->cmp = cmpStudent;
studentList->print = printName;
struct student hanjae = {1141, "한재"};
insertItem(studentList, &hanjae);
struct student suruen = {1122, "수련"};
insertItem(studentList, &suruen);
printList(studentList);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment