배열과 연결리스트 연결리스트 배열 메모리 할당이 연속적이어서 인덱스 사용시 검색이 빠르다.

Presentation on theme: "배열과 연결리스트 연결리스트 배열 메모리 할당이 연속적이어서 인덱스 사용시 검색이 빠르다."— Presentation transcript:

1 배열과 연결리스트 연결리스트 배열 메모리 할당이 연속적이어서 인덱스 사용시 검색이 빠르다.
메모리 관리 면에서 공간의 낭비가 심하다. 자료의 삽입 및 삭제가 어렵다. 연결리스트 메모리 할당이 비연속적이며, 크기가 동적이므로 낭비가 없다. 보통 element 와 element 를 가로 질러서 조건에 맞을 때까지 순차 검색하므로 검색이 느리다. 자료의 삽입및 삭제가 쉽다

2 레코드 정의 성적관리 레코드 (배열) typedef struct _student { int studentId; char name[30]; int korean; int english; int math; } student; student list[MAX_STUDENT];

3 레코드 정의 성적관리 레코드 (연결리스트) typedef struct _student { int studentId; char name[30]; int korean; int english; int math; struct _student *next; } student; student *head = null;

4 레코드 정의 사용 예제 student *newStudent = (student *) malloc (sizeof (student)); newStudent->id = …… /* 데이터 저장 */ if (head != null) { /* 레코드가 존재하는 경우 추가 */ newStudent->next = null; head = newStudent; } else { /* 레코드가 없는 경우 추가 */ }

5 Factorial 예제 int f, x; int factorial(int a); int main() { puts("Enter an interger value"); scanf("%d", &x ); if(x < 1) return 1; f=factorial(x); printf("%d factorial is %d\n", x, f); return 0; }

6 Factorial 예제 int factorial(int a) { if(a == 1) return 1; else { a *= factorial(a - 1); return a; /* return value */ }

7 Stack 예제 #define STACK_SIZE 10 char stackbuf[STACK_SIZE]; int top = -1; int push(char data) { if(top == STACK_SIZE - 1) { printf("stack overflow \n"); return -1; /* nothing */ } else { top++; /* change top */ stackbuf[top] = data; /* insert data */ }

8 Stack 예제 char pop() { if(top == -1) { printf("stack empty \n"); return -1; /* nothing */ } else { top--; /* change top */ return stackbuf[top + 1]; /* return value */ }

9 Stack 예제 void printStack() { int i; if(top == -1) { printf("stack empty \n"); return; } for(i=top; i>=0; i--) printf("%c ", stackbuf[i]); printf("\n");

10 Array Circular Queue 예제
#define Q_SIZE 10 char queuebuf[Q_SIZE]; int front = 0; int rear = 0; int enqueue(char data) { if((rear + 1) % Q_SIZE == front) { printf("queue overflow \n"); return -1; /* nothing */ } else { queuebuf[rear] = data; /* insert data */ rear = (rear + 1) % Q_SIZE; /* change rear */ }

11 Array Circular Queue 예제
char dequeue() { if(front == rear) { printf("queue empty \n"); return -1; /* nothing */ } else { front = (front+1) % Q_SIZE; /* change front */ return queuebuf[front]; /* return value */ }

12 Array Circular Queue 예제
void printQueue() { int i, next; if(front == rear) { printf(“queue empty \n"); return; } for(i=front; i!=rear; i=(i+1) % Q_SIZE) printf("%c ", queuebuf[i]); printf("\n");

13 Linked list Queue 예제 typedef struct _node { char value; struct _node *next; } node; node *front = null; node *rear = null;

14 Linked list Queue 예제 int enqueue(char data) { node *newNode = (node *)malloc(sizeof(node)); newNode->value = data; newNode->next = null; if(front == null) { front = newNode; rear = newNode; } else { rear->next = newNode; } return 0;

15 Linked list Queue 예제 char dequeue() { node *old = front; char data; if(front == null) { printf("queue empty \n"); return -1; } else { data = old->value; front = front->next; if(front == null) rear = null; } free(old); return data;

16 Linked list Queue 예제 void printQueue() { node *p = front; if(p == null) { printf(“queue empty \n"); return; } while(p != null) { printf("%c ", p->value); p = p->next; printf("\n");