함수의 재귀적 호출의 이해
팩토리얼의 예
int factorial(int n){
if(n == 0) return 1;
else return n * factorial(n – 1);
}
이진 탐색의 예
int Bsearch(int ar[], int first, int last, int target){
int mid;
if(first > last) return -1;
mid = (first + last) / 2;
if(ar[mid] == target) return mid;
else if(target < ar[mid]) return Bsearch(ar, first, mid – 1, target);
else return Bsearch(ar, mid + 1, last, target);
}
추상 자료형(Abstract Data Type)
리스트의 이해
연결리스트
ArrayList.h
#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__
#define LIST_LEN 100
typedef int LData;
typedef struct __ARRAYList{
LData arr[LIST_LEN];
int numOfData;
int curPosition;
} ArrayList;
typedef ArrayList List;
void ListInit(List * plist);
void LInsert(List * plist, LData data);
bool LFirst(List * plist, LData * pdata);
bool LNext(List * plist, LData * pdata);
LData LRemove(List * plist);
int LCount(List * plist);
#endif
ArrayList.c
#include <cstdio>
#include "ArrayList.h"
void ListInit(List * plist){
(plist->numOfData) = 0;
(plist->curPosition) = -1;
}
void LInsert(List * plist, LData data){
if(plist->numOfData > LIST_LEN){
puts("저장 불가");
return;
}
plist->arr[plist->numOfData] = data;
(plist->numOfData)++;
}
bool LFirst(List * plist, LData * pdata){
if(plist -> numOfData == 0)
return false;
(plist -> curPosition) = 0;
*pdata = plist -> arr[0];
return true;
}
bool LNext(List * plist, LData * pdata){
if(plist -> curPosition >= (plist -> numOfData) -1)
return false;
(plist -> curPosition)++;
*pdata = plist -> arr[plist -> curPosition];
return true;
}
LData LRemove(List * plist){
int rpos = plist -> curPosition;
int num = plist -> numOfData;
LData rdata = plist -> arr[rpos];
for(int i = rpos; i < num - 1; i++)
plist -> arr[i] = plist -> arr[i+1];
(plist -> numOfData)--;
(plist -> curPosition)--;
return rdata;
}
int LCount(List * plist){
return plist -> numOfData;
}
순차 리스트를 사용하는 예
#include <stdio.h>
#include "ArrayList.h"
int main(void)
{
/*** ArrayList의 생성 및 초기화 ***/
List list;
int data;
ListInit(&list);
/*** 5개의 데이터 저장 ***/
LInsert(&list, 11); LInsert(&list, 11);
LInsert(&list, 22); LInsert(&list, 22);
LInsert(&list, 33);
/*** 저장된 데이터의 전체 출력 ***/
printf("현재 데이터의 수: %d \n", LCount(&list));
if(LFirst(&list, &data)) // 첫 번째 데이터 조회
{
printf("%d ", data);
while(LNext(&list, &data)) // 두 번째 이후의 데이터 조회
printf("%d ", data);
}
printf("\n\n");
/*** 숫자 22을 탐색하여 모두 삭제 ***/
if(LFirst(&list, &data))
{
if(data == 22)
LRemove(&list);
while(LNext(&list, &data))
{
if(data == 22)
LRemove(&list);
}
}
/*** 삭제 후 저장된 데이터 전체 출력 ***/
printf("현재 데이터의 수: %d \n", LCount(&list));
if(LFirst(&list, &data))
{
printf("%d ", data);
while(LNext(&list, &data))
printf("%d ", data);
}
printf("\n\n");
return 0;
}