재귀 & 연결리스트1

with MK·2020년 10월 23일
0

자료구조

목록 보기
1/2
post-thumbnail

재귀

함수의 재귀적 호출의 이해

  • 재귀 함수가 호출되면 재귀 함수의 복사본이 만들어져서 복사본이 실행되는 구조로 재귀 함수 호출이 이루어진다.
  • 재귀 함수는 자료구조나 알고리즘의 어려운 문제를 단순화하는데 사용되는 중요한 무기이다. 수학적 수식을 그대로 코드로 옮길 수 있기 때문이다(피보나치 수열)

팩토리얼의 예

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);
}

연결리스트 1

추상 자료형(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;
}

0개의 댓글