'Computer Science/자료구조' 카테고리의 글 목록

Computer Science/자료구조

추상자료형이란?

2022. 10. 2. 17:54

추상 자료형 (Abstract Data Type)

간단히생각하면 클래스의 기능과도 같다.

단 자료구조 상에서 추상 자료형은 data handling 이라고말할 수 있다.

단순히 생각했을 때 데이터의 삽입과 추출과 같은 데이터를 가지고 연산하는 ‘기능이무엇인지를 나열 한 것’을 추상자료 형이라고 한다.

기본적으로 추가, 수정, 삭제. 조회, 삽입 등이 있다

추상자료 형이라고 해서 int, char 와 같은 자료형을 말하는것이 아니라 구조체 혹은 클래스와 같은 자료형의 정의에 기능 or 연산과 관련된 내용을 명시할 수 있다.

어렵게 생각하지 말고 해당 자료구조를 가지고 어떻게 다루어야 하는지 간단히 명시하자

추상자료형 학습 순서

자료구조의 ADT를 정의한다 (구조체 or 클래스 / 기능or 연산)
ADT를 근거로 해당 자료구조를 활용하는 main 함수를 정의한다.
ADT를 근거로 해당 자료구조를 구현한다.

질문: 추상자료형을 실무에서 어떻게 사용해야될까?

저작자표시

'Computer Science > 자료구조' 카테고리의 다른 글

C++ 기반 (0)	2022.10.02
리스트 구현 문제 (0)	2022.10.02
자료구조의 이해(1) (0)	2017.10.21

C++ 기반

2022. 10. 2. 17:53

// Main 함수

#include <stdio.h>
#include <stdlib.h>

#include "linkedArrayList.h"

int main(void)
{
// 메뉴 입력 번호 변수
int inputNumber;
CString str;
// List 생성 및 초기화
arrayList* list = new arrayList();
list->ListInit();

  while(1)
  {
   printf("\n메뉴: 0-종료 1-출력 2-추가 3-검색 4-삭제\n");
   printf("입력 : " );
   scanf("%d", &inputNumber);

   switch (inputNumber)
   {
   case 0:
    {
     printf("종료합니다");
    delete list;
     return 0;
    }
   case 1:
    {
     list->LPrint();
     break;
    }
   case 2:
    {
    char inputString[LIST_LEN] = "";

    printf("저장하려는 문자를 입력하세요\n");
    printf("입력: ");
    scanf("%s", inputString);

    str = inputString;

     list->LInsert(str);
     break;
    }
  case 3:
   {
    char inputString[LIST_LEN] = "";

    printf("검색할 문자열 입력: ");
    scanf("%s", inputString);
    str = inputString;

    list->LSearch(str);
    break;
   }
  case 4:
   {
    char inputString[LIST_LEN] = "";

    printf("삭제할 문자열 입력: ");
    scanf("%s", inputString);
    str = inputString;

    list->LRemove(str);
    break;
   }
   default:
    continue;
   }
  }

return 0;
}

// linkedList.h 파일

#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__

#include "atlstr.h"

#define TRUE 1
#define FALSE 0
#define LIST_LEN 100

typedef struct _STRING
{
CString str;
struct _STRING* next;
} STRING;

typedef STRING List;

class arrayList
{
public:
arrayList();
~arrayList();

void ListInit();
char* LPrint();
List* LNext(List* list);
  void LInsert(CString str);
char* LSearch(CString& searchString);
  int findSubString(CString& str, CString& findStr);
void LRemove(CString& searchString);
//List* nextFind(List* nextNode);

private:
List * head;
List * cur;
List * before;
int numOfData;

};

#endif

// linkedList.cpp 파일

#include <stdio.h>
#include "linkedArrayList.h"

arrayList::arrayList()
{
head = NULL;
cur = NULL;
before = NULL;
numOfData = 0;
}

arrayList::~arrayList()
{

}

void arrayList::ListInit()
{
head = new List();
head->next = NULL;
head->str = "";
cur = NULL;
before = head;
before->next = NULL;
}

char* arrayList::LPrint()
{
List* nextNode = head->next;

while(1)
{
  if(nextNode != NULL )
  {
   if( nextNode->next == NULL )
   {
    wprintf(_T("%s "), nextNode->str);
    return 0;
   }
   else
   {
    wprintf(_T("%s "), nextNode->str);
    nextNode = LNext(nextNode);
   }
  }
  else
   break;
}

return 0;
}

List* arrayList::LNext(List* list)
{
List* nextNode = list->next;

return nextNode;
}

void arrayList::LInsert(CString str)
{
List* newNode = new List;                       // 다음번 노드를 동적할당 하고

if( numOfData >= LIST_LEN)
{
  puts("저장할 용량을 초과했습니다");
  delete newNode;
  return;
}

newNode->next = head->next; // 새로 생긴 공간의 다음에 널을 만든다
newNode->str = str;
head->next = newNode;
cur = newNode;

numOfData++;
}

char* arrayList::LSearch(CString& str)
{
List* nextNode = head->next;
int pFind;

while(1)
{
  if(nextNode != NULL)
  {
   if( nextNode->next == NULL )
   {
    pFind = findSubString(nextNode->str, str);

    if( !pFind )
    {
     wprintf(_T("%s"), nextNode->str);
    }
    return 0;
   }
   else
   {
    pFind = findSubString(nextNode->str, str);

    if( !pFind )
    {
     wprintf(_T("%s"), nextNode->str);
    }
    nextNode = LNext(nextNode);
   }
  }
  else
   break;
}
return 0;
}

int arrayList::findSubString(CString& str, CString& searchStr)
{
int ret;
ret = str.Compare(searchStr);

return ret;
}

void arrayList::LRemove(CString& searchString)
{
List* nextNode = head->next;
int pFind;

while(1)
{
  if(nextNode != NULL)
  {
   pFind = findSubString(nextNode->str, searchString);

   if( !pFind )
   {
    cur = nextNode->next;
    delete nextNode;
    nextNode = NULL;
    before->next = cur;
    (numOfData)--;
    nextNode = LNext(before);
   }
   else
   {
    before = nextNode;
    nextNode = LNext(nextNode);

    if( nextNode == NULL)
     return;
   }
  }
  else
   break;

}

return;
}

// List* arrayList::nextFind(List* nextNode)
// {
// List* next = nextNode->next;
//
// if( next != NULL)
// return next;
//
// return 0;
// }

저작자표시

'Computer Science > 자료구조' 카테고리의 다른 글

추상자료형이란? (0)	2022.10.02
리스트 구현 문제 (0)	2022.10.02
자료구조의 이해(1) (0)	2017.10.21

리스트 구현 문제

2022. 10. 2. 17:52

Struct STRING
{
Char string[100];
STRING* pstring;
}

위와 같은 구조체 사용하세요

포인터 배열을 사용해서, 문자열에 대해 다음과 같은 메뉴를 처리합니다.

     메뉴 : 0. 종료 1. 출력 2. 추가 3. 검색 4. 삭제

   출력 : 지금까지 입력한 모든 문자열을 출력합니다.
   추가 : 새로운 문자열을 포인터 배열에 추가합니다.
   검색 : 검색할 문자열을 포함하고 있는 모든 문자열을 출력합니다.
   삭제 : 삭제할 문자열을 포함하고 있는 모든 문자열을 삭제합니다.

   이 문제는 입력할 문자열의 개수와 문자열의 길이가 정해져 있지않다는 점에서 어렵습니다.
   또한 검색과 삭제에서 완전히 똑같은 문자열이 아니라 부분 문자열을 처리하는 것도 어렵습니다.

   [입출력]
   메뉴 : 0. 종료 1. 출력 2. 추가 3. 검색 4. 삭제
   선택 : 2
   단어 : bonus
   메뉴 : 0. 종료 1. 출력 2. 추가 3. 검색 4. 삭제
   선택 : 2
   단어 : big_money
   메뉴 : 0. 종료 1. 출력 2. 추가 3. 검색 4. 삭제
   선택 : 2
   단어 : rainbow
   메뉴 : 0. 종료 1. 출력 2. 추가 3. 검색 4. 삭제
   선택 : 2
   단어 : handshaking
   메뉴 : 0. 종료 1. 출력 2. 추가 3. 검색 4. 삭제
   선택 : 2
   단어 : switch_on
   메뉴 : 0. 종료 1. 출력 2. 추가 3. 검색 4. 삭제
   선택 : 1
   bonus big_money rainbow handshaking switch_on
   메뉴 : 0. 종료 1. 출력 2. 추가 3. 검색 4. 삭제
   선택 : 3
   단어 : on
   bonus big_money switch_on
   메뉴 : 0. 종료 1. 출력 2. 추가 3. 검색 4. 삭제
   선택 : 4
   단어 : on
   메뉴 : 0. 종료 1. 출력 2. 추가 3. 검색 4. 삭제
   선택 : 1
   handshaking rainbow
   메뉴 : 0. 종료 1. 출력 2. 추가 3. 검색 4. 삭제
   선택 : 0

Main.c 파일

#include <stdio.h>
#include <stdlib.h>

#include "linkedArrayList.h"
#include "stringData.h"

int main(void)
{
// 메뉴 입력 번호 변수
int inputNumber;
// List 생성 및 초기화
lList list;
List * pString;
char* nullString = 0;
ListInit(&list);

while(1)
{
  printf("\n메뉴: 0-종료 1-출력 2-추가 3-검색 4-삭제\n");
  printf("입력 : " );
  scanf("%d", &inputNumber);

  switch (inputNumber)
  {
  case 0:
   {
    printf("종료합니다");
    return 0;
   }
  case 1:
   {
    LPrint(list.head);
    break;
   }
  case 2:
   {
    pString = makeString();
    LInsert(&list, pString);
    break;
   }
  case 3:
   {
    printf("검색할 문자열 입력: ");
    scanf("%s", &nullString);

    LSearch(list.head, &nullString);
    nullString = 0;
    break;
   }
  case 4:
   {
    printf("삭제할 문자열 입력: ");
    scanf("%s", &nullString);

    LRemove(&list, &nullString);
    nullString = 0;
    break;
   }
  default:
   continue;
  }
}

return 0;
}

LinkedArrayList.h 파일

#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__

#include "stringData.h"

#define TRUE 1
#define FALSE 0

typedef struct _linkedList
{
List * head;
List * cur;
List * before;
int numOfData;
} linkedList;

typedef linkedList lList;

// 해당 문제의 ADT
void ListInit(lList * plist);
// 초기화할 리스트의 주소값을 인자로 전달
// 리스트 생성 후 제일 먼저 호출되어야 하는 함수이다
char* LPrint(List *plist);
// 저장된 문자열 모두를 출력한다
void LInsert(lList * plist); //, LData data);
// 리스트에 데이터를 저장한다. 매개변수 data에 전달된 값을 저장한다
char* LSearch(List * plist, char * searchString);
char* findSubString(char* str, char* findStr); //, char* searchStr)
// 리스트에서 특정 문자열을 찾아서 찾은 문자열을 반환한다
/*int LFirst(List * plist, LData * pdata);*/
// 첫번째 데이터가 pdata가 가리키는 메모리에 저장된다
// 데이터의 참조를 위한 초기화가 진행된다
// 참조 성공시 True 실패시 False를 반환
/*int LNext(List * plist, LData * pdata);*/
// 참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장된다
// 순차적인 참조를 위해서 반복 호출이 가능하다
// 참조를 새로 시작하려면 먼저 LFirst 함수를 호출한다
// 참조 성공 시 True 실패시 False를 반환
void LRemove(lList * plist, char * searchString);
List* nextFind(List* nextNode);
// LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제 한다
// 삭제된 데이터는 반환된다
// 마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다
/*int LCount(List * plist);*/
// 리스트에 저장되어 있는 데이터의 수를 반환한다

#endif

stringData.h 파일

#ifndef __NAME_CARD_H__
#define __NAME_CARD_H__

#define LIST_LEN 100

typedef struct _STRING
{
char stringData[LIST_LEN];
struct _STRING* next;
} STRING;

typedef STRING List;

List* makeString();

#endif

// LinkedArrayList.c 파일

#include <stdio.h>
#include "linkedArrayList.h"

void ListInit(lList *pList)
{
pList->head = (List *)malloc(sizeof(List));
pList->head->next = NULL;
memset(pList->head->stringData, 0, sizeof(pList->head->stringData));
//pList->head->stringData[LIST_LEN] = {0};
pList->cur = NULL;
pList->before = pList->head;
pList->before->next = NULL;
pList->numOfData = 0;
}

char* LPrint(List *plist)
{
List* nextNode = plist->next;
if(nextNode)
{
  if( nextNode->next == NULL )
  {
   printf("%s ", nextNode->stringData);
   return 0;
  }
  else
  {
   LPrint(nextNode);
   printf("%s ", nextNode->stringData);
  }
}

return 0;
}

void LInsert(lList * plist, List* pStringData)
{
List* newNode = (List *)malloc(sizeof(List)); // 다음번 노드를 동적할당 하고
strcpy(newNode->stringData, pStringData->stringData);

if( plist->numOfData >= LIST_LEN)
{
  puts("저장할 용량을 초과했습니다");
  free(newNode);
  return;
}

newNode->next = plist->head->next; // 새로 생긴 공간의 다음에 널을 만든다
plist->head->next = newNode;
plist->cur = pStringData;

plist->numOfData++;
}

char* LSearch(List * plist, char * searchString)
{
List* nextNode = plist->next;
char *pFind;

if(nextNode)
{
  if( nextNode->next == NULL )
  {
   pFind = findSubString(nextNode->stringData, searchString);

   if( !pFind )
   {
    printf("%s", nextNode->stringData);
   }

   return 0;
  }
  else
  {
   LSearch(nextNode, searchString);

pFind = findSubString(nextNode->stringData, searchString);

   if( !pFind )
   {
    printf("%s", nextNode->stringData);
   }
  }
}

return 0;
}

char* findSubString(char* str, char* searchStr)
{
if( strstr(str, searchStr) != NULL )
return 0;
else
return -1;
}
void LRemove(lList * plist, char * searchString)
{
List* nextNode = plist->head;
char *pFind;

while(1)
{
//if( nextNode->stringData == NULL)
// return;

pFind = findSubString(nextNode->stringData, searchString);

  if( !pFind )
  {
   plist->cur = nextNode->next;
   free(nextNode);
   nextNode->stringData[0] = 0;
   plist->before->next = plist->cur;
   (plist->numOfData)--;
   nextNode = nextFind(plist->before);
  }
  else
  {
   plist->before = nextNode;
   nextNode = nextFind(nextNode);

   if( nextNode == NULL)
    return;
  }
}

return;
}

List* nextFind(List* nextNode)
{
List* next = nextNode->next;

if( next != NULL)
return next;

return 0;
}

// stringData.c 파일

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "stringData.h"

List * makeString()
{
char inputString[LIST_LEN] = "";
List * newString = (List *)malloc(sizeof(List));

printf("저장하려는 문자를 입력하세요\n");
printf("입력: ");
scanf("%s", inputString);

strcpy(newString->stringData, inputString);
return newString;
}

저작자표시

'Computer Science > 자료구조' 카테고리의 다른 글

추상자료형이란? (0)	2022.10.02
C++ 기반 (0)	2022.10.02
자료구조의 이해(1) (0)	2017.10.21

자료구조의 이해(1)

2017. 10. 21. 21:01

참고문서 - 윤성우의 열혈 자료구조

1차 작성 - 2016/03/04 (이글루스에서 옮김)

자료구조는 데이터를 표현하고 저장하는 방법에 대한 설명이다.

프로그램의 정의는 “데이터를 표현하고, 그렇게 표현된 데이터를 처리하는 것”

위에서 말하는 “데이터의 표현” 이란데이터의 저장을 포함하는 것이다.

선형 구조 – 데이터를 선의 형태로 나란히 혹은 일렬로 저장하는 방식

비선형 구조 – 데이터가 나란히 저장되지 않는 방식

알고리즘 – 표현 및 저장된 데이터를 대상으로 하는 ‘문제의 해결 방법’

Ex) 자료구조 측면의 배열 선언

Intarr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

Ex) 알고리즘 측면의 배열에 저장된 합 구하기

For(idx=0 ; idx < 10; idx++ )

Sum += arr[idx];

문장에서의 예문

“여기상자가 제법 많이 쌓여 있지요? 이 상자들 중 어딘가에 넣어 둔 머그컵을 찾으셔야 합니다.”

위의문장에서 ‘쌓여있는 상자’는 자료구조이다.

“노란색으로포장되어 있는 상자들이 머그컵이 저장되어 있는 상자입니다”

상자가차곡차곡 위에서부터 쌓여 있다고 가정했을 때 상자의 포장지 색이 노란색인 상자만 선별하는 방법을 알고리즘이라고 할 수 있다.

작가가 하고픈 말

“자료구조에 따라서 알고리즘은 달라집니다.”

“알고리즘은 자료구조에 의존적입니다.”

즉, 프로그래머로서 문제해결을 하는 것은

자료구조를 파악하고 데이터를 어떻게 정리(or 정렬)할지를 선정하는 것이 선행되어야 하며 그 자료구조(정렬된 데이터)를 이용하여 원하는 데이터를 가져오는 방법을 만들어 내는 것

이런 알고리즘을 만들기 위해서는 현재 내가 다루는 데이터의 구조를 알아야 한다

라고 결론을 내려본다.

---------------------------------------------------------------------------------------------------------------------------------------------------------

위의 내용이 작년 수준에서 정리한 내용이다.

제대로 코딩을 시작한지 2014년 11월 부터이니 현재로서 만 3년이 되었다.. 나 그럼 이제 4년차? 시간가는게 두렵다 ㅠㅠ

(사실 첫회사가 있었으나.. 개발자라고 할 경력을 3개월 밖에 인정 못 받은 수준이니...)

어쨌든 만 3년이 되는 지금 다시 자료구조를 생각해보니 학부생이었다면 2년정도 걸린다 했을 때 2학년 때 되어서 이해 되지 않았을가 싶다 (한번에는 잘 몰랐을 듯...)

자료구조가 중요한 이유만 생각해 보자 아니 자료구조라는 것을 왜 만들었을까? 관리 효율을 위해서??

선형이 되었든 비선형이 되었든 자료구조의 하나의 특징은 연결성이다 하나의 데이터는 다른 데이터와 연결되어 있다

Table 형대의 자료구조도 생각해보자 (데이터베이스에서는 Entity 혹은 관계형 데이터 모델이라고 나와있다)

윤성우 자료구조에는 저런 Table 형태는 없다 정확히 선형이나 비선형으로 표현되는 것이 아니다 굳이 만들자면 리스트<리스트> 나 맵<맵> 이런 방식의 중첩구조로 나타낼 수는 있다

어쨌든 이렇게 저렇게 막 끄집어내서 도달하려는 결론은 "데이터들" 을 어떻게 다룰 것인가를 고민하게 된다.

정보(information)가 데이터로 바뀌고 우리가 다루는 것은 데이터가 아니라 데이터들이다.

쓸데없이 철학적으로 복잡하게 생각하는 것 같지만 현실세계의 많은 것들이 발전단계에서 결국 수적 양적 증가에 대해 어떻게 대처하는가에서 발전해왔다

제품의 대량생산의 가능으로 산업혁명과 다양한 물류 유통 마케팅 산업이 가능해졌고 단순했던 정보가 대량의 데이터로 변하면서 정보혁명과 데이터 분석 빅데이터 등 결국 대량의 많은 것들을 어떻게 Processing(처리) 하느냐에 대한 선구자들의 고민이 있었을 것이다 (너무 멀리 갔다)

간단히 말하면 뭐든 많아지면 처리하기 힘들어진다 이 말이다 그리고 그 많은 것을 처리하는 것이 그 시대에 필요한 기술이 된다

하고 싶은 말은 다시 앞으로 온다 많아진 데이터들을 실제 컴퓨터가 인식할 수 있는 단위로 다루기 위해 공통의 규격(프로토콜같은 필요로)으로 정리해 둔 것이다

즉, 한 두개의 데이터가 아닌 많아진 데이터들을 효과적으로 또는 정해진 형식(Type)에 따라 저장해 두기 위해서 자료구조를 만들었을 가능성이 크다

우리는 많아진 데이터들을 처리하기 위해 자료구조를 사용한다로 정리한다 즉 자료구조도 도구와 수단으로서 존재한다

'Computer Science > 자료구조' 카테고리의 다른 글

추상자료형이란? (0)	2022.10.02
C++ 기반 (0)	2022.10.02
리스트 구현 문제 (0)	2022.10.02

PREV 1 NEXT

어제보다 더 나은 개발자 되기