자료구조 구현하기!

힙(Heap)구현

void push(int n) {//1이 root
    heap[++hcou] = n;
    int child = hcou;
    int parent = child / 2;
    while (child > 1 && heap[child] > heap[parent]) {
        swap(heap[child], heap[parent]);
        child = parent;
        parent /= 2;
    }
}
 
int pop() {//1값 반환
    int res = heap[1];
    swap(heap[1], heap[hcou]);
    hcou--;
    int parent = 1;
    int child = parent * 2;
    if (child + 1 <= hcou) {//child 와 child+1값중 큰거 선택해야함
        child = (heap[child] > heap[child + 1]) ? child : child + 1;
    }
    while (child <= hcou && heap[child] > heap[parent]) {
        swap(heap[parent], heap[child]);
        parent = child;
        child *= 2;
        if (child + 1 <= hcou) {
            child = (heap[child] > heap[child + 1]) ? child : child + 1;
        }
    }
    return res;
}

머지 소트(Merge Sort)

bool cmp(lo a, lo b) {//a<b
    if (a.len == b.len)return a.oil > b.oil;
    return a.len < b.len;
}
void merge(int start, int mid, int end) {
    int i = start;
    int j = mid + 1;
    int k = start;
    while (i <= mid && j <= end) {
        if (cmp(arr[i], arr[j])) {
            tem[k] = arr[i];
            i++;
        }
        else {
            tem[k] = arr[j];
            j++;
        }
        k++;
    }
    if (i > mid) {
        for (int t = j; t <= end; t++) {
            tem[k] = arr[t];
            k++;
        }
    }
    else {
        for (int t = i; t <= mid; t++) {
            tem[k] = arr[t];
            k++;
        }
    }
    for (int i = start; i <= end; i++) {
        arr[i] = tem[i];
    }
}
void mergesort(int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2;
        mergesort(start, mid);
        mergesort(mid + 1, end);
        merge(start, mid, end);
    }
}

해시 테이블 (Hash table)

• collision 이 최대한 적게 생기는게 중요!
• 해시 함수
  • 롤링 해시

  • int makekey(char* a) {
        //mod = 4096;
        int key = 5381;
        int c = 0;
        while (a[c]) {
            key = (key << 5) + key + a[c];
            key %= mod;
            c++;
        }
        return key;
    }

• bool same(char* a, char* b) {
      int c = 0;
      while (a[c] || b[c]) {
          if (a[c] != b[c])
              return 0;
          c++;
      }
      return 1;
  }
   
  struct NODE {
      char arr[25];
      int num;
      NODE* pre;
      NODE* next;
  }nodes[100004];
  int cou = 0;
  NODE* makenode() {
      return &nodes[cou++];
  }
  struct list {
      NODE head;
      NODE tail;
      int size =0;
      void init() {
          size = 0;
          head.next = &tail;
          tail.pre = &head;
      }
      void add_node(char* brr,int n) {
          NODE* temnode = makenode();
          NODE* nextnode = &tail;
          NODE* prenode = tail.pre;
          prenode->next = nextnode->pre = temnode;
          temnode->next = nextnode;
          temnode->pre = prenode;
          temnode->num = n;
          int c = 0;
          while (brr[c]) {
              temnode->arr[c] = brr[c];
              c++;
          }
          temnode->arr[c] = 0;
          size++;
      }
      int search(char* a) {
          NODE* temnode = head.next;
          
          int c = 0;
          while (!same(a, temnode->arr)) {
              temnode = temnode->next;
          }
          return temnode->num;
      }
  }hrr[MOD];
  char tem[25];
   
  int makekey(char * a) {//4096
      int key = 5381;
      int c = 0;
      while (a[c]) {
          key = (key << 5) + key + a[c];
          key %= MOD;
          c++;
      }
      return key;
  }
  void copy(string s ,char * b) {
      int cou = 0;
      while (s[cou]) {
          b[cou] = s[cou];
          cou++;
      }
      b[cou] = 0;
  }
  int size(char* a) {
      int cou = 0;
      while (a[cou])
          cou++;
      return cou;
  }
   
  int findnum(char* a) {
      int tem = 0;
      int c = 0;
      while (a[c]) {
          tem *= 10;
          tem += a[c] - '0';
          c++;
      }
      return tem;
  }

•