지극히 개인적인 공간

 

2장인가..3장인가.. 연습문제...

사칙연산하고 10개의 수를 입력받아 더해서 결과값을 출력

마지막은 = 을 입력하면 자동종료 추가...

1번 예제

if (argc < 2) // 명령이(입력개수) 2개가 초과하면

{

cout << "명령행 입력이 없습니다" << end1; return 2; // 입력이 없다 표기해주고

} // 오류가나면 2로 표기해준다

CString strArg = argv[1];

int iPos = strArg.FindOneOf("+-*/"); //int ipos에 사칙연산을 문자열형태로 삽입한다

{

cont <<"사칙 연산을 입력하세요 " << end1; return 3; // 사칙연산을 입력하라 출력

} // 오류가나면 3으로 표기해준다

CString strFrontEnd = strArg.Left(iPos); //문장 왼쪽에서 ipos만큼 출력해준다

CString strBackEnd = strArg.Mid(iPos + 1);// 문장 오른쪽에서 ipos만큼 출력해준다

CString strOperator = strArg.Mid(iPos , 1);//ipos번째부터 1개 출력해준다(사칙연산출력)

int iforntEnd = atoi(strFrontEnd); // 문자열을 정수로 표현한다

int iBackEnd = atoi(strBackEnd); // atoi함수를 사용

int iResult = 0; // iResult 0으로 선언

double iResult = 0.0; // iResult가 실수형값을 받기위해 double을 사용

if (strOperator == "+") iResault = iFrontEnd + iBackEnd;

//strOperator가 +면 값을 더해준다 아래도 -는 빼주고 *라면 곱해준다

else if(strOprtator == "-") iResault = iFrontEnd - iBackEnd;

else if(strOprtator == "*") iResault = iFrontEnd * iBackEnd;

else if(strOpertaor == "/") // 나눗셈일 경우에는

{

if (iBackEnd == 0) // 오른쪽에 숫자가 0이랑 같은경우에는

{

cont << "0으로 나눌 수 없습니다" << end1;

return 4; // 0으로 나눌수없다하고 오류가 나면 4를 표기해준다

}

ifResult = (double)iFrontEnd / ibackEnd; //0이 아닐경우에는 나눠준값을표기

}

cout << (LPCTSTR)strArg << "="; // =을 출력

cout << (strOperator != "/" ? iResult : lfResult);

// strOperator가 “/”가 아니면 iResult를 사용하고 “/”면 lfResult를사용해서소수점까지출력

cout << end1; // 공백

2번 예제

if(argc < 5) // 명령이(입력개수) 5개가 초과하면

{

cout << "명령행 입력이 4개 입니다" <<endl;

return 2; // 명령행 입력이 4개라고 출력 오류시 2표기

}

CString strXPos = argv[1]; // X좌표를 argv[1]에 저장

CString strYPos = argv[2]; // Y좌표를 argv[2]에 저장

CString strWidth = argv[3]; // 가로크기 argv[3]에 저장

CString strHeight = argv[4]; // 세로크기 argv[4]에 저장

int iXPos = atoi(strXPos); // atoi를 이용해서 문자열을 숫자로 바꿔준다

int iYpos = atoi(strYPos);

int iWidth = atoi(strWidth);

int iHeight = atoi(strHeight);

CRect rectTarget(iXPos, iYPos, iXPos+iWidth, iYPos+iHeight);

// 각 객체에 값을 설정 한다

rectTarget.NormalizeRect();

CPoint ptInput; // CPoint(점) 연산자를 입력

cout << "X 좌표와 Y 좌표를 입력하세요" <<endl;// 입력문구

cin >> ptInput.x >> ptInput.y; // X좌표와 Y좌표를 입력한다(scanf)

if(rectTarget.ptInRect(ptInput) == TRUE) cont << "내부" << endl;

else cout << "외부" << endl;

//CPoint를 사용해서 참이 나오면 내부를 출력하고 그 외에는 외부를출력해준다

3번 예제

cout << "더할 숫자 10개를 입력하세요" << endl; //문구 출력

CUIntArray uiArray;

UINT uiSum = 0; //합한값을 넣을수있게 생성하고 0으로 초기화

for (int i=0; i<10; i++) //for문을 사용해서 10개를 출력

{

cout << i+1 << "번째 : ";//1는 0이므로 1~10번째 출력

cin >> uiArray[i]; // 값을 입력

uisum += uiArray[i]; // 입력한값을 모두 더해서 uisum에 저장

}

for (int j=0; j<10; j++) //for문을 써서 10개를 출력

{

cout << uiArray[j]; // 값을 입력한 것을 출력해준다

cout << (j !=9 ? "+" : "=");

// (j가 9가 아니면) 10개의 입력한 숫자들은 더해주고 그이후 11번째는 합을표기

}

cout << uiSum << endl;

4번 예제

cout << "더할 숫자를 입력하세요 (종료 := 입력)" << endl; //문구 출력

CStringList strList;

UINT i=0; //i 생성 0으로 초기화

TCHAR szNumber[100]; //문자열 지정

while (TRUE) //참일경우

{

cout << ++i << "번째 : "; //i수만큼 i번째 출력

cin >> szNumber; // 숫자를 입력

CString strNumber = szNumber;

if (strNumber.Find("=") != -1)break; // =를 입력할 경우 중지한다

strList.Addtail(strNumber);

}

UINT uisum =0; // uisum을 0으로 초기화

POSITION pos = strList.GetHeadPosition();

while (pos) // 그외의경우

{

CString &strNumber = strList.GetNext(pos);

UINT uinumber = atoi(strNumber); // 문자열을 숫자로 바꿔서 입력

uiSum += uiNumber; //uiNumber에 있는 숫자들을 다 더해서 uisum에 저장

cout << uiNumber; // 숫자를 입력

cout << (pos != NULL ? "+" : "="); // 널(공백이 아니면 더해주고) 공백이면 합해준다

}

cout << uisum << endl; // 더한 값을 출력

 

 

밑변 과 높이? 구하는것 ....

 

헤드 파일 만들어서 제작

 

/* R04.h */

class Triangle

{

public:

Triangle( int w, int h ) : width( w ), height( h ) {}

int area() { return w * h / 2; }

 

private:

int width;

int height;

};

 

class Rectangle

{

public:

Rectangle( int w, int h ) : width( w ), height( h ) {}

int area() { return w * h; }

 

private:

int width;

int height;

};

 

/* R04.cpp */

#include <iostream.h>

#include "R04.h"

 

int main()

{

Triangle tri( 4, 3 );

Rectangle rect( 4, 3 );

 

cout << "밑변 4, 높이 3인 삼각형의 넓이는 " << tri.area() << " 입니다. " << endl;

cout << "밑변 4, 높이 3인 사각형의 넓이는 " << rect.area() << " 입니다. " << endl;

return 0;

}

 

 

 

음 주석다는것! MFC 프로그램 구조 ..

 

숙제 장수가 많은듯... ;;;

 

 

Simple.h

class CSimpleApp : public CWinApp //CWinApp 파생 클래스

{

public:

CSimpleApp();

virtual BOOL InitInstance(); //InitInstance()가상함수 초기화코드 삽입

afx_msg void OnAppAbout(); //afx_msg내부적 공백처리 OnAppAbout() 대화상자 화면에 표시(메시지 핸들러)

DECLARE_MESSAGE_MAP() //메시지 핸들러 사용시 필수적인 입력

};

Simple.cpp

BEGIN_MESSAGE_MAP(CSimpleApp, CWinApp) //메시지 핸들러와 연결해준다

ON_COMMAND(ID_APP_ABOUT, OnAppAbout)//OnAppAbout()와 연결

END_MESSAGE_MAP()

CSimpleApp::CSimpleApp()

{

}

CSimpleApp theApp;//전역 응용 프로그램 객체를 선언

BOOL CSimpleApp::InitInstance()

{

SetRegistryKey(_T("Local AppWizard-Generated Applications"));//프로그램과 관련된정보를 특정 레지스트리 위치에저장

CMainFrame* pFrame = new CMainFrame;//프레임 윈도우 객체를 동적으로 생성

m_pMainWnd = pFrame; // 객체의 주소값을 m_pMainWnd에 저장

pFrame->LoadFrame(IDR_MAINFRAME, //IDR_MAINFRAME메뉴, 아이콘 정보제공

WS_OVERLAPPEDWINDOW | FWS_ADDTOTITLE, NULL,

NULL);

pFrame->ShowWindow(SW_SHOW);//ShowWindow() 생성된프레임을 화면에출력

pFrame->UpdateWindow();//UpdateWindow() 함수가WM_PAINT 메시지를 처리

return TRUE; //초기화가 되면 TRUN을 리턴해준다

}

// 대화상자 관련 클래스 선언 및 정의 부분 - 생략

// ...

void CSimpleApp::OnAppAbout()//화면에 대화상자를 표기해준다

{

CAboutDlg aboutDlg;

aboutDlg.DoModal();

}

MainFrm.h

class CMainFrame : public CFrameWnd//새로운 클래스 파생

{

public:

CMainFrame();

protected:

DECLARE_DYNAMIC(CMainFrame)// 객체에 대해 실행시간클래스 정보기능사용

public:

virtual BOOL PreCreateWindow(CREATESTRUCT& cs);//가상함수를 재정의한다

virtual BOOL OnCmdMsg(UINT nID, int nCode, void* pExtra, AFX_CMDHANDLERINFO* pHandlerInfo);

virtual ~CMainFrame();

CChildView m_wndView;//뷰객체 선언

protected:

afx_msg int OnCreate(LPCREATESTRUCT lpCreateStruct);//메시지 핸들러

afx_msg void OnSetFocus(CWnd *pOldWnd); // 메시지 핸들러(대화상자 화면표시)

DECLARE_MESSAGE_MAP()

};

MainFrm.cpp

IMPLEMENT_DYNAMIC(CMainFrame, CFrameWnd)//실행시간 클래스 정보기능

//(클래스 이름, 베이스 클래스 이름)

BEGIN_MESSAGE_MAP(CMainFrame, CFrameWnd)

ON_WM_CREATE()// WM_CREATE, OnCreate() 함수를 연결해준다

ON_WM_SETFOCUS()//WM_SETFOCUS, OnSetFocus() 함수를 연결

END_MESSAGE_MAP()

CMainFrame::CMainFrame()

{

}

CMainFrame::~CMainFrame()

{

}

int CMainFrame::OnCreate(LPCREATESTRUCT lpCreateStruct)

//프레임 윈도우가 CMainFrame::OnCreate에 생성되면 WM_CREATE 메시지를 받고 메시지맵에 의해 ONcreate() 함수가 자동으로 호출

{

if (CFrameWnd::OnCreate(lpCreateStruct) == -1)// 0부터 시작하므로 -1로시작

return -1; // -1경우에는 리턴 해준다

if (!m_wndView.Create(NULL, NULL, AFX_WS_DEFAULT_VIEW,//자식 윈도우생성

CRect(0, 0, 0, 0), this, AFX_IDW_PANE_FIRST, NULL))//뷰를 생성

{

TRACE0("Failed to create view window \n");// 아닐 경우 윈도우 뷰를 만드는데 실패했다고 뜨고 리턴을 해준다

return -1;

}

return 0;

}

BOOL CMainFrame::PreCreateWindow(CREATESTRUCT& cs)//가상함수 생성

{

if( !CFrameWnd::PreCreateWindow(cs) )

return FALSE; //CFrameWnd::PreCreateWindow(cs) 경우 리턴

cs.dwExStyle &= ~WS_EX_CLIENTEDGE;

cs.lpszClass = AfxRegisterWndClass(0);

return TRUE;

}

void CMainFrame::OnSetFocus(CWnd* pOldWnd) //뷰객체의 SetFocus()를 호출하여

뷰가 키보드 포커스를 가지게 한다

{

m_wndView.SetFocus();

}

BOOL CMainFrame::OnCmdMsg(UINT nID, int nCode, void* pExtra,//명령 라우팅 AFX_CMDHANDLERINFO* pHandlerInfo)

{// 명령 핸들러가 어디서든지 생성되도 처리된다

if (m_wndView.OnCmdMsg(nID, nCode, pExtra, pHandlerInfo))

return TRUE;

return CFrameWnd::OnCmdMsg(nID, nCode, pExtra, pHandlerInfo);

}

ChildView.h

class CChildView : public CWnd//CWnd 일반적 윈도우 기능을 정의

{

public:

CChildView();

protected:

virtual BOOL PreCreateWindow(CREATESTRUCT& cs);// 윈도우 특성의 바꾸는함수

public:

virtual ~CChildView();

protected:

afx_msg void OnPaint();//화면에 대화상자 표시

DECLARE_MESSAGE_MAP()

};

ChildView.cpp

CChildView::CChildView()

{

}

CChildView::~CChildView()

{

}

BEGIN_MESSAGE_MAP(CChildView,CWnd )

ON_WM_PAINT()//WM_PAINT, Onpaint()함수와 연결

END_MESSAGE_MAP()

BOOL CChildView::PreCreateWindow(CREATESTRUCT& cs)

{ //윈도우 생성전에 특성을 변경

if (!CWnd::PreCreateWindow(cs))//가상함수를 먼저 호출

return FALSE; //cs의 일부멤버를 초기화

cs.dwExStyle |= WS_EX_CLIENTEDGE;//WS_EX_CLIENTEDGE 확장 스타일 지정

cs.style &= ~WS_BORDER;//WS_BORDER 일반 스타일 지정

cs.lpszClass = AfxRegisterWndClass ( //윈도우 클래스 이름을 저장 CS_HREDRAW|CS_VREDRAW|CS_DBLCLKS, ::LoadCursor(NULL, IDC_ARROW), HBRUSH(COLOR_WINDOW+1), NULL);

return TRUE;

}

void CChildView::OnPaint() //WM_Paint를 처리

{

CPaintDC dc(this);//생성자 ::BeginPaint() 소멸자 ::EndPaint() 생성

dc.TextOut(100, 100, CString("안녕하세요."));// 100, 100이란 영역에글을호출

}

 

정말 긴연산... 다들 비슷한거 내서 한개는 특별하게

 

후위연산 + 토큰 +기본 옵션 까지 ~! 주석달기...

 

쫌길다.. 25페이지... ㅋㅋ

 

 

// 사칙연산

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define BOOL int

#define TRUE 1

#define FALSE 0

#define STACKSIZE 20 // 입력할 문자를 20개 까지 받는다

#define BUFFER 256

// 아스키 코드를 사용해서 사칙연산 및 괄호를 입력 받는다

#define ASCII_ADD 43 // + 를 지정

#define ASCII_SUB 45 // - 를 지정

#define ASCII_MUL 42 // * 를 지정

#define ASCII_DIV 47 // / 를 지정

#define ASCII_MOD 37 // % 를 지정

#define ASCII_BRACKET_START 40 // ( 를 지정

#define ASCII_BRACKET_STOP 41 // ) 를 지정

// push, pop, del을 지정 한다

#define FLAG_NONE 0

#define FLAG_PUSH 1

#define FLAG_POP 2

#define FLAG_DEL 3

// 각 리턴을 지정해준다

#define RETURN_NONE 0

#define RETURN_NUM 1

#define RETURN_OPER 2

#define RETURN_START 3

#define RETURN_STOP 4

typedef struct _NODE

{

char nData;

_NODE *pPrev;

_NODE *pNext;

} NODE, *PNODE;

typedef struct _LINKEDLIST

{

NODE *pTop;

NODE *pBottom;

int nSize;

} LINKEDLIST, *PLINKEDLIST;

// 함수의 원형을 나열한다

PLINKEDLIST Create();

BOOL Input(PLINKEDLIST pLinkedList, char *szInfix, char* szPostfix);

BOOL PushLinkedList(PLINKEDLIST pLinkedList, char *cOperator);

char PopLinkedList(PLINKEDLIST pLinkedList);

BOOL PrintLinkedList(char *pToken, char *pValue, PLINKEDLIST pLinkedList, char *szResult, int nFlag);

int Process(char *szPostfix);

BOOL PushArray(int *pStack, int nValue, int *nTop);

int PopArray(int *pStack, int *nTop);

BOOL PrintArray(int *pStack, char *pToken, int nValue, int nTop, int nFlag);

char* AddResult(char *pResult, char *pToken, int nSize);

char* NextTokenIn(char *pCurrent, char *pToken, int *nFlag);

char* NextTokenPost(char *pCurrent, char *pToken, int *nFlag);

BOOL ParseInfix(char *pCurrent);

BOOL GetKey(char *szTemp);

// 프로그램 시작점

int main()

{

PLINKEDLIST pLL;

char szInfix[BUFFER];

char szPostfix[BUFFER];

int nResult;

// 행렬리스트 링크드 리스트를 생성한다

pLL = Create();

// 화면 출력

printf("===============================================================================\n");

printf(" 스택 구현 프로그램\n");

printf("===============================================================================\n\n");

// 수식 입력 함수 호출

Input(pLL, szInfix, szPostfix);

printf("===============================================================================\n");

printf(" 후위 계산 과정 출력\n");

printf("===============================================================================\n\n");

// 수식 계산 함수 호출

nResult = Process(szPostfix);

printf("===============================================================================\n");

printf(" 결과값 출력\n");

printf("===============================================================================\n\n");

// 결과 출력

printf("INFIX : %s\n", szInfix);

printf("POSTFIX : %s\n", szPostfix);

printf("RESULT : %d\n", nResult);

printf("\n===============================================================================");

// 링크드리스트 헤더노드 메모리 소거

free(pLL);

getchar();

return 0;

}

// 새로운 링크리스트를 만드는 부분

PLINKEDLIST Create()

{

// 노드의 시작을 가리키는 포인터를 생성한다

PLINKEDLIST pLinkedList;

// 말록 함수를 이용해서 LINKEDLIST의 사이즈만큼 pLinkedList로 삽입한다

pLinkedList = (PLINKEDLIST)malloc(sizeof(LINKEDLIST));

// 노드의 TOP, BOTTOM을 NULL(공백)로 지정한다

pLinkedList->pTop = NULL;

pLinkedList->pBottom = NULL;

//스택의 크기를 0으로 초기화 한다

pLinkedList->nSize = 0;

return pLinkedList;

}

//값을 삽입 해주는 부분

BOOL Input(PLINKEDLIST pLinkedList, char *szInfix, char* szPostfix)

{

char szTemp[BUFFER];

char szResult[BUFFER];

char szToken[BUFFER];

char *pCurrent;

char *pResult;

char cTemp;

int nFlag;

if(pLinkedList == NULL) //pLinkedList가 공백이면

{

// 초기화 되지 않았다고 알림이 나온뒤

printf("Input(): LinkedList가 초기화 될수없다\n");

// 리턴해준다

return FALSE;

}

//배열을 NULL로 초기화 한다(다른것과 겹쳐서 오류가 나지않기위해서)

//memset=포인터가 가리키는 주소에서부터 바이트수만큼의 길이를 값으로 초기화 시킨다

memset(szResult, '\0', sizeof(szResult));

printf("[?] 수식을 입력. ");

printf("예) 1+2*(3+4)/5%6+(7*8)\n");

while(TRUE)

{

printf(">> ");

// 값 입력

GetKey(szTemp);

// 입력된 수식이 올바른 형식인지 원하는 모양인지 확인한다(파싱)

if(ParseInfix(szTemp) == TRUE)

{

break;

}

else

{

printf("[!] 잘못된 수식이 입력\n");

}

}

// 순환을 돌 토큰 지정 하는 부분

pCurrent = szTemp;

pResult = szResult;

// 중위입력값 보관하는 부분

strcpy(szInfix, szTemp);

while(*pCurrent != NULL)// 널이 아닐경우

{

memset(szToken, '\0', sizeof(szToken));

// Infix형 수식의 토큰을 나눈다

pCurrent = NextTokenIn(pCurrent, szToken, &nFlag);

if(nFlag == RETURN_NONE)

{

continue;

}

// 숫자일때

else if(nFlag == RETURN_NUM)

{

pResult = AddResult(pResult, szToken, strlen(szToken));

PrintLinkedList(szToken, szToken, pLinkedList, szResult, FLAG_NONE);

}

else if(nFlag == RETURN_OPER)

{

if(szToken[0] == ASCII_ADD || szToken[0] == ASCII_SUB)

{

// 스택의 최상위가 NULL이 아닐때

if(pLinkedList->pTop != NULL)

{

while(TRUE)

{

// 스택이 비어있을때 멈춘다

if(pLinkedList->pTop == NULL)

{

break;

}

// 스택위 최상위에 같은 우선순위 (*, /, %, +, -) 연산자가 있을경우 스택에서 꺼내주는 부분

if(pLinkedList->pTop->nData == ASCII_MUL || pLinkedList->pTop->nData == ASCII_DIV || pLinkedList->pTop->nData == ASCII_MOD

|| pLinkedList->pTop->nData == ASCII_ADD || pLinkedList->pTop->nData == ASCII_SUB)

{

// 스택 POP

cTemp = PopLinkedList(pLinkedList);

pResult = AddResult(pResult, &cTemp, 1);

PrintLinkedList(szToken, &cTemp, pLinkedList, szResult, FLAG_POP);

}

else

{

break;

}

}

}

PushLinkedList(pLinkedList, szToken);

PrintLinkedList(szToken, szToken, pLinkedList, szResult, FLAG_PUSH);

}

else if(szToken[0] == ASCII_MUL || szToken[0] == ASCII_DIV || szToken[0] == ASCII_MOD)

{

// 스택의 최상위가 NULL이 아닐때

if(pLinkedList->pTop != NULL)

{

while(TRUE)

{

// 스택이 비어있을때

if(pLinkedList->pTop == NULL)

{

break;

}

// 스택의 최상위에 같은 우선순위의 (*, /, %) 연산자가 있을경우 스택에서 꺼낸다

if(pLinkedList->pTop->nData == ASCII_MUL || pLinkedList->pTop->nData == ASCII_DIV || pLinkedList->pTop->nData == ASCII_MOD)

{

// 스택 POP

cTemp = PopLinkedList(pLinkedList);

pResult = AddResult(pResult, &cTemp, 1);

PrintLinkedList(szToken, &cTemp, pLinkedList, szResult, FLAG_POP);

}

else

{

break;

}

}

}

// 스택에 넣는다

PushLinkedList(pLinkedList, szToken);

PrintLinkedList(szToken, szToken, pLinkedList, szResult, FLAG_PUSH);

}

}

// 괄호 시작일때

else if(nFlag == RETURN_START)

{

// 스택에 넣는다

PushLinkedList(pLinkedList, szToken);

PrintLinkedList(szToken, szToken, pLinkedList, szResult, FLAG_PUSH);

}

// 괄호가 닫힐때

else if(nFlag == RETURN_STOP)

{

// TOP이 NULL이 아니면서 열린 괄호가 나올때까지 스택의 값들을 꺼낸다

while(pLinkedList->pTop != NULL && pLinkedList->pTop->nData != ASCII_BRACKET_START)

{

// 스택 POP

cTemp = PopLinkedList(pLinkedList);

pResult = AddResult(pResult, &cTemp, 1);

PrintLinkedList(szToken, &cTemp, pLinkedList, szResult, FLAG_POP);

}

// 열린괄호를 삭제한다

cTemp = PopLinkedList(pLinkedList);

PrintLinkedList(szToken, &cTemp, pLinkedList, szResult, FLAG_DEL);

}

// 그 이외의 값이 입력되었을때

else

{

// 잘못된 값이라 출력하고 리턴해준다

printf("[!] 잘못된 값이 입력되었다");

return FALSE;

}

}

// 모든 토큰을 돌았을때

strcpy(szToken, "end");

// 스택안에 들어있는 데이터를 모두 꺼낸다

while(pLinkedList->nSize > 0)

{

// 스택 POP

cTemp = PopLinkedList(pLinkedList);

pResult = AddResult(pResult, &cTemp, 1);

PrintLinkedList(szToken, &cTemp, pLinkedList, szResult, FLAG_POP);

}

// 후위 변환 완료후 결과값 복사

strcpy(szPostfix, szResult);

return TRUE;

}

// Push LinkedList Stack 부분

BOOL PushLinkedList(PLINKEDLIST pLinkedList, char *cOperator)

{

PNODE pNewNode;

// 스택이 풀인지 체크 한다

if(pLinkedList->nSize == STACKSIZE)

{

printf("[!] 링크드리스트 스택이 가득차 있다");

return FALSE;

}

// 링크드 리스트가 정상적으로 생성되있지 않을경우

if(pLinkedList == NULL)

{

printf("PushLinkedList(): LinkedList가 초기화 될수없다\n");

return FALSE;

}

// 포인터 구조체에 값을 입력하기 위해 메모리 영역을 할당한다

pNewNode = (PNODE)malloc(sizeof(NODE));

// 위의 과정을 거쳐 메모리에 영역을 할당하는데 실패하였을 경우

if(pNewNode == NULL)

{

printf("PushLinkedList(): LinkedList 노드를 생성 할 수가없다\n");

return FALSE;

}

// 입력된 연산자를 스택에 입력한다

pNewNode->nData = (char)*cOperator;

// 이전 노드의 포인터를 NULL로 한다

pNewNode->pPrev = NULL;

// 처음으로 입력되는 스택일경우

if(pLinkedList->pTop == NULL)

{

pNewNode->pNext = NULL;

pLinkedList->pTop = pNewNode;

pLinkedList->pBottom = pNewNode;

}

// 두번째 이상으로 입력되는 스택일경우

else

{

pLinkedList->pTop->pPrev = pNewNode;

pNewNode->pNext = pLinkedList->pTop;

pLinkedList->pTop = pNewNode;

}

// 스택의 사이즈를 하나더 증가시킨다

pLinkedList->nSize++;

return TRUE;

}

// Pop LinkedList Stack 부분

char PopLinkedList(PLINKEDLIST pLinkedList)

{

char cTemp;

PNODE pCurrent;

// 스택이 비어있는지 검사한다

if(pLinkedList->nSize == 0)

{

printf("[!] 링크드리스트 스택이 비어 있다");

return FALSE;

}

// 링크드 리스트가 정상적으로 생성되어있지 않을경우

if(pLinkedList == NULL)

{

printf("PopLinkedList(): LinkedList가 초기화 될수 없다\n");

return FALSE;

}

// 메모리에서 삭제하기 위한 링크를 남겨둔다

pCurrent = pLinkedList->pTop;

// 링크드 리스트 스택 사이즈를 1줄인다

pLinkedList->nSize--;

// 스택이 비었을때

if(pLinkedList->nSize == 0)

{

pLinkedList->pTop = NULL;

pLinkedList->pBottom = NULL;

}

// 스택이 비어있지 않을때 Top을 조정한다

else

{

pLinkedList->pTop = pLinkedList->pTop->pNext;

pLinkedList->pTop->pPrev = NULL;

}

// 삭제될 최상의 스택의 값을 받는다.

cTemp = pCurrent->nData;

// 메모리 소거

free(pCurrent);

// 값 리턴

return cTemp;

}

// Print LinkedList Stack부분

BOOL PrintLinkedList(char *pToken, char *pValue, PLINKEDLIST pLinkedList, char *szResult, int nFlag)

{

PNODE pCurrent;

char *pResult;

char szTemp[BUFFER];

int nReturn;

//pLinkedList가 공백일때

if(pLinkedList == NULL)

{

printf("PrintLinkedList(): LinkedList가 초기화 될수없다\n");

return FALSE;

}

// 현재 토큰 값 출력

printf("TOKEN : %s\n", pToken);

// 플래그 출력, PUSH인지 POP인지 DELETE인지 구별한다

switch(nFlag)

{

case FLAG_NONE :

// 스택을 거치지 않을때

printf("COPY(-)\n");

break;

case FLAG_PUSH :

// PUSH일때

printf("PUSH(%s)\n", pToken);

break;

case FLAG_POP :

// POP일때

printf("POP(%c)\n", pValue[0]);

break;

case FLAG_DEL :

// DELETE일때

printf("DELETE(%c)\n", pValue[0]);

break;

}

// 스택안에 들어있는 값 출력

printf("STACK : ");

pCurrent = pLinkedList->pBottom;

while(pCurrent != NULL)

{

// 링크드 리스트를 돌며 값을 출력한다

printf("%c ", pCurrent->nData);

pCurrent = pCurrent->pPrev;

}

// 결과 출력

printf("\nOUTPUT : ");

pResult = szResult;

// 토큰을 돌며 출력한다

while(*pResult != '\0')

{

memset(szTemp, '\0', sizeof(szTemp));

// 토큰을 돌며 출력한다

pResult = NextTokenPost(pResult, szTemp, &nReturn);

// 숫자나 연산자만 출력한다

if(nReturn == RETURN_NUM || nReturn == RETURN_OPER)

{

printf("%s ", szTemp);

}

}

getchar();

printf("\n");

return TRUE;

}

int Process(char *szPostfix)

{

char *pCurrent;

char szTemp[BUFFER];

int aStack[STACKSIZE];

int nReturn;

int nTop;

int nTemp[2];

// 스택의 탑위치를 가리키는 nTop초기화(0부터 시작하므로-1으로 초기화)

nTop = -1;

// 후위변경된 수식의 시작을 포인터 지정

pCurrent = szPostfix;

// 토큰을 돌며 출력한다

while(*pCurrent != '\0')

{

memset(szTemp, '\0', sizeof(szTemp));

// 토큰을 돌며 출력한다

pCurrent = NextTokenPost(pCurrent, szTemp, &nReturn);

// 숫자는 무조건 push한다

if(nReturn == RETURN_NUM)

{

PushArray(aStack, atoi(szTemp), &nTop);

PrintArray(aStack, szTemp, atoi(szTemp), nTop, FLAG_PUSH);

}

// 연산자가 나오면 이전의 스택 값 두개를 연산하여 결과를 다시 push한다

else if(nReturn == RETURN_OPER)

{

nTemp[1] = PopArray(aStack, &nTop);

PrintArray(aStack, szTemp, nTemp[1], nTop, FLAG_POP);

nTemp[0] = PopArray(aStack, &nTop);

PrintArray(aStack, szTemp, nTemp[0], nTop, FLAG_POP);

switch(szTemp[0])

{

case '+' :

// 덧셈 연산자 일때

PushArray(aStack, (int)(nTemp[0] + nTemp[1]), &nTop);

break;

case '-' :

// 뺄셈 연산자 일때

PushArray(aStack, (int)(nTemp[0] - nTemp[1]), &nTop);

break;

case '*' :

// 곱셈 연산자 일때

PushArray(aStack, (int)(nTemp[0] * nTemp[1]), &nTop);

break;

case '/' :

// 나눗셈 연산자 일때

PushArray(aStack, (int)(nTemp[0] / nTemp[1]), &nTop);

break;

case '%' :

// 나머지 연산자 일때

PushArray(aStack, (int)(nTemp[0] % nTemp[1]), &nTop);

break;

}

PrintArray(aStack, szTemp, aStack[nTop], nTop, FLAG_PUSH);

}

}

// 최종 결과 값 리턴

return aStack[0];

}

// Push Stack

BOOL PushArray(int *pStack, int nValue, int *nTop)

{

// 스택사이즈만큼 가득차 있을경우

if(*nTop == STACKSIZE)

{

printf("[!] 배열 스택이 가득차 있다\n");

return FALSE;

}

// TOP 위치 상승

(*nTop)++;

// 푸쉬할 값 입력

*(pStack + *nTop) = nValue;

return TRUE;

}

// Pop Stack

int PopArray(int *pStack, int *nTop)

{

int nTemp;

// 스택이 비어있을 경우

if(*nTop == -1)

{

printf("[!] 배열 스택이 비어 있다\n");

return FALSE;

}

// 팝을 하기 위한 값 복사

nTemp = *(pStack + *nTop);

// TOP위치 감소

(*nTop)--;

return nTemp;

}

// Print Stack

BOOL PrintArray(int *pStack, char *pToken, int nValue, int nTop, int nFlag)

{

int nCount;

printf("TOKEN : %s\n", pToken); //pToken 값을 출력

if(nFlag == FLAG_PUSH)//FLAG_PUSH와 같으면

{

printf("PUSH(%d)\n", nValue);//nValue(push) 값을 출력

}

else if(nFlag == FLAG_POP)//또는 FLAG_POP와 같을때

{

printf("POP(%d)\n", nValue);//nValue(pop)를 출력

}

printf("STACK : ");

for(nCount = 0 ; nCount <= nTop ; nCount++)//nCount를 nTop보다 같으나 클때까지 출력

{

printf("%d ", *(pStack + nCount));

}

// 사용자가 엔터를 입력할때까지 기다린다

getchar();

printf("\n");

return TRUE;

}

// Add Character Array

char* AddResult(char *pResult, char *pToken, int nSize)

{

int nCount;

// 토큰을 결과 배열에 입력한다

for(nCount = 0; nCount < nSize ; nCount++)

{

*pResult = *pToken;

// 결과 배열 포인터를 증가시킨다

pResult++;

pToken++;

}

// 널문자 삽입

*pResult = '\0';

return pResult;

}

// Next Token Pointer

char* NextTokenIn(char *pCurrent, char *pToken, int *nFlag)

{

// 숫자인지 오퍼레이터인지 검사하는 플래그 초기화

*nFlag = 0;

// 숫자일때

if(*pCurrent < 58 && *pCurrent > 47)

{

// 이전 토큰의 값이 -이면서 그 이전토큰의 값이 숫자가 아닐때

if(*(pCurrent - 1) == ASCII_SUB && (*(pCurrent - 2) > 57 || *(pCurrent - 2) < 48))

{

*pToken = ASCII_SUB;

pToken++;

}

else

{

*pToken = ASCII_ADD;

pToken++;

}

// 이어 나오는 토큰이 숫자일경우 계속 출력한다

while(*pCurrent < 58 && *pCurrent > 47)

{

*pToken = *pCurrent;

pToken++;

pCurrent++;

}

// 숫자일경우

*nFlag = RETURN_NUM;

}

else if(*pCurrent == ASCII_BRACKET_START || *pCurrent == ASCII_BRACKET_STOP)

{

if(*pCurrent == ASCII_BRACKET_START)

{

*nFlag = RETURN_START;

}

else

{

*nFlag = RETURN_STOP;

}

*pToken = *pCurrent;

pToken++;

pCurrent++;

}

else

{

// 앞의 토큰이 숫자일 경우

if(*(pCurrent - 1) < 58 && *(pCurrent - 1) > 47 || *(pCurrent - 1) == ASCII_BRACKET_STOP)

{

*pToken = *pCurrent;

pToken++;

// 연산식일 경우

*nFlag = RETURN_OPER;

}

pCurrent++;

}

return pCurrent;

}

// Next Token Pointer

char* NextTokenPost(char *pCurrent, char *pToken, int *nFlag)

{

// 숫자인지 오퍼레이터인지 검사하는 플래그 초기화

*nFlag = RETURN_NONE;

// 숫자일때

if(*pCurrent < 58 && *pCurrent > 47)

{

// 이전 토큰의 값이 -일때

if(*(pCurrent - 1) == ASCII_SUB)

{

*pToken = ASCII_SUB;

pToken++;

}

// 이어 나오는 토큰이 숫자일경우 계속 출력한다

while(*pCurrent < 58 && *pCurrent > 47)

{

*pToken = *pCurrent;

pToken++;

pCurrent++;

}

// 숫자일경우

*nFlag = RETURN_NUM;

}

// 연산식일때

else

{

// 뒤의 토큰이 숫자일 경우

if(*(pCurrent + 1) > 57 || *(pCurrent + 1) < 48)

{

*pToken = *pCurrent;

pToken++;

*nFlag = RETURN_OPER;

}

pCurrent++;

}

return pCurrent;

}

// Get Key 키입력 처리

BOOL GetKey(char *szTemp)

{

int nCount;

// fgets로 값을 입력받는다. BUFFER이상 길이의 값이 입력될 경우 짤린다

fgets(szTemp, BUFFER, stdin);

// 반복문, 값이 입력되지 않은 부분에 널문자를 채운다

for(nCount = 0 ; nCount < BUFFER ; nCount++)

{

if(szTemp[nCount] < 0 || szTemp[nCount] == '\n')

{

// 아스키코드 0번 이하이거나 엔터문자일경우 널문자로 교체

szTemp[nCount] = '\0';

}

}

return TRUE;

}

// Parserinfix

BOOL ParseInfix(char *pCurrent)

{

int nCountNum;

int nCountOper;

int nCountBracket_Start;

int nCountBracket_Stop;

// 각각의 정보를 기록하는 카운터를 초기화 한다

nCountNum = 0;

nCountOper = 0;

nCountBracket_Start = 0;

nCountBracket_Stop = 0;

while(*pCurrent != '\0')

{

// 현재 토큰이 숫자일때

if(*pCurrent < 58 && *pCurrent > 47)

{

// 이전 토큰이 숫자가 아닐때

if(*(pCurrent - 1) > 57 || *(pCurrent - 1) < 48)

{

nCountNum++;

}

}

// 현재 토큰이 연산자일때

else

{

// 여는 괄호일때, 이전 토큰이 숫자이면 안된다

if(*pCurrent == ASCII_BRACKET_START && (*(pCurrent - 1) > 57 || *(pCurrent - 1) < 48))

{

// 닫는 괄호가 여는 괄호보다 많을수 없음

nCountBracket_Start++;

}

// 닫는 괄호일때

else if(*pCurrent == ASCII_BRACKET_STOP)

{

if(nCountBracket_Stop > nCountBracket_Start)

{

return FALSE;

}

nCountBracket_Stop++;

}

// 연산자 일때

else if(*pCurrent == ASCII_ADD || *pCurrent == ASCII_SUB || *pCurrent == ASCII_MUL || *pCurrent == ASCII_DIV || *pCurrent == ASCII_MOD)

{

// 이전 토큰이 숫자일때 연산자임

if(*(pCurrent - 1) < 58 && *(pCurrent - 1) > 47 || *(pCurrent - 1) == ASCII_BRACKET_STOP)

{

nCountOper++;

}

// 이전 토큰이 시작하는 괄호일때

else if(*(pCurrent - 1) == ASCII_BRACKET_START)

{

// 현재 토큰이 *, /, %이라면 잘못된 수식

if(*pCurrent == ASCII_MUL || *pCurrent == ASCII_DIV || *pCurrent == ASCII_MOD)

{

return FALSE;

}

}

}

else

{

// 위에 있지 않는 문자가 입력되었을 경우

return FALSE;

}

}

pCurrent++;

}

// 여는 괄호와 닫는 괄호의 수가 다를 경우 잘못된 형식

if(nCountBracket_Start != nCountBracket_Stop)

{

return FALSE;

}

// 숫자와 연산자+1의 수가 다를 경우 잘못된 형식

if(nCountNum != (nCountOper + 1))

{

return FALSE;

}

return TRUE;

}

 

 

 

요건좀 짧다 일부러 빠져나오는 구녕은 없게 만들었다 1로 둘러 쳤음

 

스택을 이용한 미로찾기!! 것도 C언어로...

 

XX캠퍼스인지 XXX 리포터 사이트라든지 엄청 나쁜거 같다.. 지식은 공유하는것이여~~

 

요런거가지고 대학생 돈 울궈먹는 사람 나쁘다 -..- 사는 사람도참.. @#$#@$?

 

주석까지 다달고 코딩까지 ..... D대학 다니시는 H님 잘참조 했습니다~~~

 

 

//미로찾기

//////////////////////////////////////////////////////////////////////////////////////////////////////////

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

#define MAX_STACK_SIZE 200

#define MAX 20

#define FALSE 0

#define TRUE 1

//구조체 선언

typedef struct{

short int row;

short int col;

short int dir;

}element;

element stack[MAX_STACK_SIZE],position;

//탐색 경로

typedef struct{

short int vert;

short int horiz;

}offsets;

offsets move[8];

//함수 정의

void path(int (*maze)[MAX], int row, int col); //미로 탐색

void clear_kb(void); //메모리 초기화

element del(int *top); //탑 삭제

void add(int *top,element item); //스택 추가

main()

{

int i, j, row, col, maze[MAX][MAX]; //변수 선언

char func;

do

{

srand((unsigned)time(NULL)); //랜덤값 변화

//랜덤으로 미로를 무작위로 생성

printf("당신이 원하는 미로의 크기를 입력.(row,col):");

scanf("%d %d",&row, &col);

for(i=0; i<row; i++)

{

for(j=0;j<col; j++)

{

maze[i][j]=rand()%2;

} //미로를 랜덤으로 발생

}

for(i=0;i<col;i++) //벽은 모두 1로 채운다

{

maze[0][i]=1;

maze[row-1][i]=1;

}

for(i=0;i<row;i++)

{

maze[i][col-1]=1;

maze[i][0]=1;

}

maze[1][1]=0; //입구와 출구를 0으로 설정

maze[row-2][col-2]=0;

//미로 출력

printf("선택한 크기의 미로 생성.\n");

for(i=0; i<row; i++)

{

printf("\n");

for(j=0;j<col;j++)

{

printf("%2d",maze[i][j]);

}

}

printf("\n\n");

clear_kb(); //stdin상의 메모리를 초기화

printf("미로를 다시 생성 하시겠습니까?(y/n):");

scanf("%c",&func);

//y나n 이외의 값은 에러출력후 종료

if(!(func=='y'||func=='n'))

{

fprintf(stderr,"You must enter a \'x\' or \'y\'");

exit(1);

}

}while(func=='y'||func=='Y');

//미로 탐색

path(maze,row,col);

return 0;

}

//미로 탐색 알고리즘

void path(int (*maze)[MAX], int r, int c)

{

int i, j, top, row, col, next_row, next_col, dir, mark[MAX][MAX], found=FALSE;

//mark값을 초기화

for(i=0;i<MAX;i++)

{

for(j=0;j<MAX;j++)

{

mark[i][j]=0;

}

}

//move값 초기화

move[0].vert=-1;

move[0].horiz=0;

move[1].vert=-1;

move[1].horiz=1;

move[2].vert=0;

move[2].horiz=1;

move[3].vert=1;

move[3].horiz=1;

move[4].vert=1;

move[4].horiz=0;

move[5].vert=1;

move[5].horiz=-1;

move[6].vert=0;

move[6].horiz=-1;

move[7].vert=-1;

move[7].horiz=-1;

//초기화 끝

mark[1][1]=1; //시작점을 1로 설정

top=0;

stack[0].row=1;

stack[0].col=1;

stack[0].dir=1;

while(top>-1&&!found)

{

position=del(&top);

row=position.row;

col=position.col;

dir=position.dir;

while(dir<8&&!found)

{

//dir을 북쪽에서 시계방향으로 돌리면서 탐색

next_row=row+move[dir-1].vert;

next_col=col+move[dir-1].horiz;

//만약 마지막 출구를 착았을때 found=1로 설정

if(next_row==r-2 && next_col==c-2)

found=TRUE;

else if(!maze[next_row][next_col]&&!mark[next_row][next_col])

{

mark[next_row][next_col]=1;

//그렇지 않은경우 경로 이동

position.row=row;

position.col=col;

position.dir=++dir;

add(&top,position);

row=next_row;

col=next_col;

dir=0;

}

else ++dir;

//dir 을 증가시켜 북쪽부터 시계방향으로 출구 검색

}

}

//출력 부분

if(found) //found가 1(TRUE)일때

{

printf("The path is:\n");

printf("row col\n");

for(i=0;i<=top;i++)

printf("%2d%5d\n",stack[i].row,stack[i].col);

printf("%2d%5d\n",row,col);

printf("%2d%5d\n",r-2,c-2);

}

else

printf("The maze does not have a path\n");

}

// 스택 추가

void add(int *top,element item)

{

if(*top>=MAX_STACK_SIZE-1)

{

fprintf(stderr,"stack Is_Full.\n");

return;

}

stack[++*top]=item;

}

//스택 삭제

element del(int *top)

{

if(*top==-1)

{

printf("stack is empty.\n");

return stack[MAX_STACK_SIZE];

}

return stack[(*top)--];

}

void clear_kb(void)

{

char junk[80];

gets(junk);

}

 

예제 7-4 이중 연결 리스트를 이용한 덱 프로그램

#include <stdio.h>

#include <malloc.h>

typedef char element;

typedef struct DQNode{

element data;

struct DQNode *llink; //다음 노드를 가르킬 포인터

struct DQNode *rlink;

} DQNode; // 자료형 정의

typedef struct{ //연결큐 데이터 타입

DQNode *front, *rear;

} DQueType; // 자료형 정의

DQueType *createDQue()//공백 이중연결 덱을 생성

{

DQueType *DQ;

DQ = (DQueType *)malloc(sizeof(DQueType));//메모리 할당

DQ->front=NULL;

DQ->rear=NULL;

return DQ;

}

int isEmpty(DQueType *DQ) //덱이 공백인지 아닌지 검사

{

if (DQ->front == NULL) {

printf("\n Linked Queue is empty! \n");

return 1; //front 널이면 종료

}

else return 0;

}

void insertFront(DQueType *DQ, element item)//연결덱에 첫번째 원소를 삽입

{

DQNode *newNode=(DQNode *)malloc(sizeof(DQNode));

newNode->data = item;

if(DQ->front == NULL) {// front가 널이면 r,llink를 널로 잡아준다

DQ->front = newNode;

DQ->rear = newNode;

newNode->rlink = NULL;

newNode->llink = NULL;

}

else {

DQ->front->llink = newNode;

newNode->rlink = DQ->front;

newNode->llink = NULL;

DQ->front = newNode;

}

}

void insertRear(DQueType *DQ, element item) //연결덱에 마지막 원소를 삽입

{

DQNode *newNode=(DQNode *)malloc(sizeof(DQNode));

newNode->data = item;

if(DQ->front == NULL) {

DQ->front = newNode;

DQ->rear = newNode;

newNode->rlink = NULL;

newNode->llink = NULL;

}

else {

DQ->rear->rlink = newNode;

newNode->rlink = NULL;

newNode->llink = DQ->rear;

DQ->rear = newNode;

}

}

element deleteFront(DQueType *DQ) //연결덱에서 첫번째 원소를 삭제

{

DQNode *old = DQ->front;

element item;

if (isEmpty(DQ)) return 0;

else {

item = old->data;

if(DQ->front->rlink == NULL) {

DQ->front = NULL;

DQ->rear = NULL;

}

else {

DQ->front = DQ->front->rlink;

DQ->front->llink = NULL;

}

free(old);

return item;

}

}

element deleteRear(DQueType *DQ) //연결덱에서 마지막 원소를 삭제

{

DQNode *old = DQ->rear;

element item;

if (isEmpty(DQ)) return 0;

else {

item = old->data;

if(DQ->rear->llink == NULL) {

DQ->front = NULL;

DQ->rear = NULL;

}

else {

DQ->rear = DQ->rear->llink;

DQ->rear->rlink = NULL;

}

free(old);

return item;

}

}

void removeFront(DQueType *DQ) //연결덱에서 첫번째 원소를 삭제

{

DQNode *old = DQ->front;

if (isEmpty(DQ)) return;

else if(DQ->front->rlink == NULL) {

DQ->front = NULL;

DQ->rear = NULL;

}

else {

DQ->front = DQ->front->rlink;

DQ->front->llink = NULL;

}

free(old);

}

void removeRear(DQueType *DQ) //연결덱에서 마지막 원소를 삭제

{

DQNode *old = DQ->front;

if (isEmpty(DQ)) return;

else if(DQ->rear->llink == NULL) {

DQ->front = NULL;

DQ->rear = NULL;

}

else {

DQ->rear = DQ->rear->llink;

DQ->rear->rlink = NULL;

}

free(old);

}

element peekFront(DQueType *DQ) //연결덱에서 첫번째 원소를 검색해서변환

{

element item;

if (isEmpty(DQ)) return 0;

else {

item = DQ->front->data;

return item;

}

}

element peekRear(DQueType *DQ) //연결덱에서 마지막 원소를 검색해서변환

{

element item;

if (isEmpty(DQ)) return 0;

else {

item = DQ->rear->data;

return item;

}

}

void printDQ(DQueType *DQ) // 기본 출력 문구 및 출력 위치 선정

{

DQNode *temp = DQ->front;

printf("\n DeQue : [");

while(temp) {

printf("%3c", temp->data);

temp = temp->rlink;

}

printf(" ]");

}

int main(void)

{

DQueType *DQ1 = createDQue();

element data;

insertFront(DQ1, 'A'); printDQ(DQ1); // A

insertFront(DQ1, 'B'); printDQ(DQ1); // BA

insertRear(DQ1, 'C'); printDQ(DQ1); // BAC

deleteFront(DQ1); printDQ(DQ1); // AC

deleteRear(DQ1); printDQ(DQ1); // A

insertRear(DQ1, 'D'); printDQ(DQ1); // AD

insertFront(DQ1, 'E'); printDQ(DQ1); // EAD

insertFront(DQ1, 'F'); printDQ(DQ1); // FEAD

data = peekFront(DQ1); printf("\n peek Front item : %c", data); //F

data = peekRear(DQ1); printf("\n peek Rear item : %c", data); //D

getchar();

return 0;

}

/* remove는 delete와 마찬가지로 원소 하나를 삭제하는 기능을 한다.

둘의 차이는 remove는 삭제 연산만 하고,

delete는 삭제연산한 후에 삭제한 원소의 데이터를 리턴한다 그러므로

삭제한 원소의 데이터가 필요한 경우에는 delete 연산을 사용하고,

삭제한 원소의 데이터가 필요없으면 remove 연산으로 처리해주면 된다.

*/

 

 

 

C로 배우는 쉬운 자료구조 출처 나름 연습문제 풀이

 

자료구조 연습문제

1. 일상생활에서 발견할 수 있는 큐의 예를 설명하여라.

>> 영화예매시, 화장실, 병원 접수 창구 등

2. 큐와 스택의 구조를 비교하여 설명하여라.

>> 스택은 후입선출형 자료구조로 캔에서 물건을 꺼낼때 나중에 들어간 데이터가 제일

먼저 빠져나오고, 큐는 선입선출형 자료구조로 입력은 뒤에서 받고 출력은 앞으로 빠진다.

3. 1차원 배열의 선형 큐에서 잘못된 포화 상태 문제를 해결하는 방법을 설명하여라.

>> rear가 배열의 끝에 도달하면 다시 배열의 처음으로 포인터를 이동시키는 환형큐를

사용해서 앞에 비워지게 되는 front자리를 채워준다.

4[가->나->다->라] 순서로 큐에 원소를 삽입한 후에 모두 삭제하면 어떤 순서로 삭제되는지 설명하여라.

>> 삽입과 마찬가지로 가->나->다->라 순으로 삭제된다 [삽입->가->나->다->라->출력]부분 이기 때문에 나올때도 [라]부터 빠지고 [가]가 제일 나중에 빠져나간다.

5. 원형큐의 삭제 알고리즘을 순서대로 나열하여라.

① item <- Q(front);

② front <- (front+1)mod n;

③ if(front = rear) then Q Empty();

>> 3번 -> 2번 -> 1번 순 으로 진행 된다.

6. 크기가 5인 선형 큐에서 다음의 연산을 수행한다. 큐가 포화 상태가 되어 더 이상 작업을 할수 없게 되는 시점을 설명하여라.

예) A삽입 -> B삽입 -> 삭제 -> C삽입 -> 삭제 -> 삭제 -> D삽입 -> E삽입 -> 삭제 -> F삽입 -> 삭제

>>Ｆ삽입에서 작업을 할수없게된다 이유는 5개인 선형큐이기 때문에 ABCDE가 다들어가고 그다음 삭제가 되도 빈공간에 들어갈수가 없기 때문에 F는 못들어가게된다.

7. 공백 덱에 대하여 다음의 연산이 모두 수행된 후에 덱에 남아있는 원소를 순서대로 나타내어라.

예)insertFront(DQ,A)->insertFront(DQ,B)->insertRear(DQ,C)->deleteRear(DQ)-> insertFront(DQ,D)->deleteRear(DQ)->getRear(DQ)->insertrear(DQ,E)->deleteFront(DQ)

>>A->AB->CAB->AB->ABD->BD->(값을리턴)->EBD->EB

8. 원형 큐에서 포화 상태와 공백 상태의 조건을 설명하여라.

>>공백상태는 front와 rear가 같을때 이고, ((rear+1)mod n) 상태는 rear위치가 front위치가 되어서 포화상태가 된다.

9. 리스트이 양쪽에서 정보를 삽입하거나 삭제할 수 있는 선형 리스트는 무엇인가?

>> 리스트에서 나열한 원소들간에 순서를 가지고 있는 리스트를 선형 리스트 라고 한다.

10. 운영체제의 작업 스케줄링 드엥 응용되는 것으로 가장 적합한 자료구조는?

예) 가. 스택 나. 큐 다. 연결 리스트 라. 트리

>> 나. 큐

 

 

 

그냥 기본으로 나와있는거 주석까지 밑에거 끌어다가 붙인거다..

 

 

ex4_1.h

#include <avr/io.h>

#include <avr/interrupt.h>

#include <stdlib.h>

#define CPU_CLOCK 16000000

#define BAUD_RATE 19200

#define BAUD_RATE_L (CPU_CLOCK / (161 * BAUD_RATE)) -1

#define BAUD_RATE_H ((CPU_CLOCK / (161 * BAUD_RATE)) -1) >> 8

ex4_1.c

#include"EXT2_ex4_1.h"

// 1byte 전송 함수

void uart_send_byte(unsigned char byte)

{

// 전송 버퍼가 빌 때까지 기다린다.

while(!(UCSR1A & (1 <<UDRE1)));

//UCSR1A 레지스터의 UDRE1 비트가 1인지 검사한다

UDR1 = byte;//전송버퍼가 비었을때 UDR1 레지스터에

//1바이트의 데이터를 써준다

}

//return 문자 전송 함수

void uart_send_return(void) //터미널상 개행문자를 표시함수

{

uart_send_byte('\n');

uart_send_byte('\r');

}

//문자열 전송 함수

void uart_send_string(unsigned char *str, unsigned char len)

//문자열을 전송하기 위한 함수

{

int i;

for(i=0; i<len; i++)

{

if(!(*(str + i)))

{

break;//널문자를 만나게되면 전송중단

}

uart_send_byte(*(str+i));//1바이트씩 전송

}

}

//딜레이 루틴

void m_delay(unsigned int m)

//ms 단위의 시간지연을 만들기 위해 만들어진함수

{

unsigned int i,j;

cli();

for(i=0;i<m;i++)

for(j=0;j<2650;j++); //16MHz : 1msec

sei();

}

//가변저항의 출력값을 내기 위한 구분(UART 상에 출력)

void vr_out(void)

{

chat buf[4];

int result;

ADCSR |= 0x40; // ACD Start Conversion ADCSR을 1로 전환

while((ADCSR & 0x10) == 0); //ADC의 변환이 종료될때까지 대기

result = ADCL; // 결과값을 ADCL을 먼저 읽어들이고

result = ADCH; // ADCL을 읽은후 ADCH를 읽어들인다

itoa(result, buf, 10); // 아스키코드로 출력하기위해itoa함수사용

// 문자출력

uart_send_string(buf, sizeof(buf));//반환된 문자열을 UART으로출력

}

//ADC초기화

void adc_init(void)

{

DDRF &= 0x00; // F포트 입력 설정

// ADMUX = (01 1 00000), AVCC를 레퍼런스로 사용, 좌정렬 1, 채널 0

// 레퍼런스(REFS1, REFS0) 좌정렬(ADLAR)1로설정, 채널(ADC0,61번핀)

ADMUX = (0<<REFS1) | (1<<REFS0) | (1<<ADLAR);

// ADCSR = (1000 0 111), ADC enable(ADEN=1), 128분주비 설정

ASCSR = (1<<ADEN) | (1<<ADPS2) | (1<<ADPS1) | (1<<ADPS0);

}

//시리얼 통신(UART) 초기화

void uart_init(void)

{

//baud rate 설정

UBRR1L = (unsigned char)BAUD_RATE_L;

UBRR1H = (unsigned char)BAUD_RATE_H;

//no parity, 1 stop bit, 8bit 설정

UCSR1C = (0<<UPM1) | (0<<UPM0) | (0<<USBS)

|(1<<USCZ1) | (1<<UCSZ0);

//Tx, Rx Enable, 8bit 설정

UCSR1B = (1<<TXEN) | (1<<RXEN) | (0<<USCZ2);

}

int main(void)

{

adc_init(); //ADC 초기화

uart_init(); //LED 포트 초기화

while(1){

m_delay(1000);//딜레이지정

vt_out();

uart_send_return();

m_delay(1000);

}

return 1;

}