23.05.12.

Today I learned

• 자료구조
• 응용수학

자료구조

Doubly LinkedList 구현하기

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct _list{
    struct _list* prev;
    int data;
    struct _list* next;
} list;
typedef list* listPointer;
void print_forward(listPointer list) {
  listPointer curr;
  FILE *outfile;
  outfile = fopen("hw2_result.txt", "a");
  if(list) {
    curr = list;
    while(1) {
     fprintf(outfile, "%d ", curr->data);
      printf("%d ", curr->data);
      curr = curr->next;
      if(curr == list) break;
  }
  }
  fprintf(outfile, "\n");
  printf("\n");
  fclose(outfile);
}
void print_reverse(listPointer list) {
  listPointer curr;
  FILE *outfile;
  outfile = fopen("hw2_result.txt", "a");
    if(list) {
    curr = list->prev;
    while(curr != list) {
     fprintf(outfile, "%d ", curr->data);
     printf("%d ", curr->data);
     curr = curr->prev;
    }
    fprintf(outfile, "%d ", curr->data);
    printf("%d ", curr->data);
  }
  fprintf(outfile, "\n");
  printf("\n");
  fclose(outfile);
}
int main(int argc,char* argv[]) {
    //파일 입력
    FILE *fp;
    fp = fopen(argv[1], "r");
    if(argc>2||argc==1){
        printf("usage: ./hw2 input_filename\n");
        return 0;
    }
    if (fp == NULL) {
        printf("The input file does not exist.\n");
        return 0;
        }
    //0인 상황을 위해 stack변수 생성
    int stack=0;
    listPointer head = NULL;
    listPointer curr;
    //커맨드
    char command[8];
    int num,i;
    while(1){
        if(fscanf(fp,"%s", command)==EOF) return 0;
        if(!strcmp(command,"INSERT")){
            fscanf(fp,"%d",&num);
            curr=head;
            i=0;
            while(1){
                i++;
                if(stack==0){//스택이 비어있는 경우 고려
                    stack++;
                    //Linked List 생성
                    listPointer node=(list*)malloc(sizeof(list));
                    node->prev=node;
                    node->next=node;
                    node->data=num;
                    head=node;
                    break;
                }
                else if(curr->data==num){//중복이 있으면 중지
                    break;
                }
                else if(stack==1){//스택이 1이라면, 연결시키고 작은 놈 헤드
                    stack++;
                    listPointer node=(list*)malloc(sizeof(list));
                    node->data=num;
                    node->prev=curr;
                    node->next=curr->next;
                    curr->next->prev=node;
                    curr->next=node;
                    if(curr->data>node->data) head=head->next;
                    break;
                }
                else if(curr->data>num){
                    stack++;
                    listPointer node=(list*)malloc(sizeof(list));
                    node->data=num;
                    node->next=curr;
                    node->prev=curr->prev;
                    curr->prev->next=node;
                    curr->prev=node;
                    if(i==1){//head보다 작다면
                        head=node;
                    }
                    break;
                }
                else if(i==(stack+1)){
                    stack++;
                    listPointer node=(list*)malloc(sizeof(list));
                    node->data=num;
                    node->next=curr;
                    node->prev=curr->prev;
                    curr->prev->next=node;
                    curr->prev=node;
                    break;
                }
                curr=curr->next;
            }
        }
        else if(!strcmp(command,"DELETE")){
            fscanf(fp,"%d",&num);
            curr=head;
            for(i=0;i<stack;i++){
                if(num==curr->data){
                    if(curr==head){//node가 하나뿐이라면
                        head=NULL;
                    }
                    else{
                        curr->prev->next = curr->next;
                        curr->next->prev = curr->prev;
                    }
                    break;
                }
                curr=curr->next;
            }
        }
        else if(!strcmp(command,"ASCEND")){
            print_forward(head);
        }
        else if(!strcmp(command,"DESCEND")){
            print_reverse(head);
        }
        else{
            return 0;
        }
    }
}

pseudo코드에서 바뀐 점들, 구상하면서 생각했던 것들

Doubly linkedlist에 첫번째 노드를 가리키는 headnode를 만들어 사용할 수 있으면 쉽게 구현할 수 있을거라 생각했다. 하지만 고정된 print_forward()를 참조했을 때 headnode도 linkedlist내에 들어가 있어야해서 어떻게 해야할지 고민이 되었다. 컴공실에서 짰을때 생각했던 것을 바탕으로, 없을 때는 head=NULL;로 만들었다가 노드가 들어오면 그 노드를 head로 정의하여 구현했다.
pseudo코드는 Doubly linkedlist의 특성을 고려하지 않고 짰던 거 같다. 순회한다는 특성을 이용해 조금더 간단하게 구현할 수 있는 것은 간단하게 구현했다.
마주했던 문제중 segmentation fault가 가장 당황스러웠다. 하지만 gdb를 통해 run시키고 에러나는 열을 찾았다.

//stack==1일때
curr->next->prev=node;

해당 코드에서 오류가 났다.

listPointer node=(list*)malloc(sizeof(list));
    node->prev=NULL;
    node->next=NULL;
    node->data=num;

때문이였다. stack이 1일때 headnode만 정의되어 있어 node->data만 num으로 갱신되고, 각 포인터들은 NULL을 가리키고 있었다. 이때 curr->next는 NULL을 가리키므로, NULL->prev가 되어 메모리 참조 오류가 발생했다.

---

char strs[4][64]; // 2차원배열
char* ptrs[4]; // 포인터배열
strcpy(strs[1], "ABC"); // O
strcpy(ptrs[1], "ABC"); // X, 초기화되지 않은 메모리에 문자열 할당
strs[2] = "DEF"; // X, 우항은 포인터 주소인데, 주소값을 값 넣는데에 넣으려는 시도자체가 틀림
ptrs[2] = "DEF"; // O

---

응용수학

Poisson Process

t초에 일어날 사건수 $N(t)$는 $P(\lambda t)$를 따른다.
$\lambda$는 단위시간당 일어날 사건 수이므로
하나의 사건이 발생하는데 걸리는 시간은 $1/\lambda$이다.

---

$Xi-1~Xi$의 시간의 평균은 $Expon(\lambda)$이다.

n개의 사건이 일어나는데 걸리는 시간은 $G(N,\lambda)$이다.