반응형

스택

- 선형 자료구조의 일종이다.

- 들어간 것이 먼저 나오는 후입선출(LIFO : Last In First Out)형식의 자료구조이다.

  ※ 사용 예로 브라우저의 뒤로가기 기능을 들 수 있다.

 

  ※ 위의 그림 기준으로 입력의 순서는 A → D → C, 출력은 C → D → A 순으로 이루어진다.

 

그럼 본격적으로 코드를 작성하기 전 활용할 구조체는 다음과 같다.

typedef struct Stack
{
    int data;
    struct Stack* NEXT;
}Stack;

 

 

Push (입력)

Stack* Push(Stack* node, int data)
{
    Stack* newNode = (Stack*)malloc(sizeof(Stack));
    newNode->data = data;
    newNode->NEXT = node;
	
    return newNode;
}

  ※ 새로 할당한 노드의 자기참조 변수는 앞에 만들어진 노드(인수로 받은 노드)를 대입하면 된다.

 

 

Pop(출력)

Stack* Pop(Stack* node)
{
    if (node == NULL) return NULL;
	
    Stack* deleteNode = node;
    node = node->NEXT;
    free(deleteNode);
	
    return node;
}

  ※ 현재(Top)의 노드를 할당해제하고 인수로 받은 노드의 다음 노드를 반환한다.

 

위 과정을 그림으로 풀면 다음과 같다.

  ※ 제일 마지막에 Push된 데이터가 스택의 Top이 된다.

  ※ Push :  현재 Top(Stack3)을 인수로 넘겨주면 Push함수에서 노드를 동적할당하고 Stack->NEXT에 인수로 받은 Stack3을 대입해주고 반환해주면, Top은 새로 할당한 노드로 변경이 되고 기존 노드(Stack3)은 새로 할당한 노드의 참조 변수(NEXT)에 대입해주면 된다.

  ※ Pop : 현재 Top을 인수로 넘겨주면 되고, Pop함수에서 인수로 받은 Top 노드를 할당 해제 해주고, Top노드의 참조 변수(NEXT)를 반환해주면 된다.

 

 

풀 소스코드는 다음과 같다.

#include <stdio.h>
#define MAX 10

typedef struct Stack
{
    int data;
    struct Stack* NEXT;
}Stack;

Stack* Push(Stack* node, int data)
{
    Stack* newNode = (Stack*)malloc(sizeof(Stack));
    newNode->data = data;
    newNode->NEXT = node;
	
    return newNode;
}

Stack* Pop(Stack* node)
{
    if (node == NULL)
    {
        printf("데이터가 없습니다.\n");
        return NULL;
    }
	
    printf("%d ", node->n);
    Stack* deleteNode = node;
    node = node->NEXT;
    free(deleteNode);
	
    return node;
}

void main()
{
    Stack* top = NULL;
    for(int i = 0; i < MAX; i++)
        top = Push(top, data);
    
    //현재 상태 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9(top)
    
    for(int i = 0; i < MAX; i++)
    	top = Pop(top);
        
    //결과 : 9 8 7 6 5 4 3 2 1 0
}
반응형

'Stack > Data struct' 카테고리의 다른 글

C 트리 순회(Tree traversal) 구현  (0) 2021.09.10
C 이진탐색트리(Binary search tree) 구현  (0) 2021.09.09
C 트리(Tree) 설명  (0) 2021.09.09
C 큐(Queue) 구현  (0) 2021.09.09
C Linked List(연결리스트 구현)  (0) 2021.09.05
반응형

연결리스트

- 추상적 자료형인 리스트를 구현한 자료구조로 노드(데이터 덩어리)를 저장할 때 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 자료구조이다.

  ※ 그렇기때문에 구조체 멤머변수 중 자신과 동일한 구조체의 주소를 저장할 수 있는 변수를 만들어 참조해야한다. (이 때, 주소를 저장하는 멤버 변수를 자기참조 구조체라고 함.)

- 장점 : 배열과 다르게 데이터를 동적으로 추가, 삭제가 가능하다.

- 단점 : 배열처럼 정렬되어있지 않고, 흩어져있기 때문에 배열의 인덱스로 접근하는것 처럼 특정 노드에 빠른 접근은 불가능하다.

  ※ 일일이 탐색하는 과정을 거쳐서 데이터를 찾아야 한다.

 

Linked List를 위한 구조체

typedef struct Node
{
    int data
    struct Node* Next;
}Node;

 

위의 구조체를 바탕으로 우리가 구현할 연결리스트의 그림을 그려보자면 다음과 같이 표현할 수 있다.

추가

- 가장 마지막 노드를 찾아 그 뒤에 데이터를 추가한다.

1. 재귀함수를 통해 마지막 노드까지 찾아간다.

2. 새로운 데이터를 동적할당을 한 뒤, 마지막 노드에 연결해준다.

Node* AddData(Node* node, int data)
{
    if (node == NULL)
    {
    	Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = data;
        newNode->NEXT = NULL;

        return newNode;
    }

    node->NEXT = AddData(node->NEXT, data);
    return node;
}

 

 

탐색

- 이부분 역시 재귀함수로 데이터를 비교해서 같은 노드를 반환하면 된다.

Node* Search(Node* node, int data)
{
    if (node == NULL)
        return NULL;
	
    if (node->data == data)
        return node;

    return Search(node->NEXT, data);
}

 

 

삭제

1. 재귀함수로 데이터가 같은 노드를 찾는다.

2. 같은 노드를 찾으면 찾은 노드에 연결된 리스트를 임시 변수에 저장해둔다.

3. 찾은 노드의 동적할당을 해제한다.

4. 2번에 저장해둔 다음 리스트를 반환한다.

Node* Delete(Node* node, int data)
{
    if (node == NULL) return NULL;
	
    if (node->data == data)
    {
        Node* nextNode = node->NEXT;
        free(node);
		
        return nextNode;
    }
	
    node->NEXT = Delete(node->NEXT, data);
    return node;
}

 

 

여기까지만 구현해 두면, 어느 특정 위치에 데이터를 끼워넣든 삭제하든 나머지는 응용하기 나름이다.

마지막으로 풀 소스 코드를 올려본다.

#include <stdio.h>
#define MAX 10

typedef struct Node
{
    int data;
    struct Node* NEXT;
}Node;

Node* AddData(Node* node, int data)
{
    if (node == NULL)
    {
    	Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = data;
        newNode->NEXT = NULL;

        return newNode;
    }

    node->NEXT = AddData(node->NEXT, data);
    return node;
}

void ShowAllData(Node* node)
{
    if (node == NULL) return;

    printf("%d ", node->data);
    ShowAllData(node->NEXT);
}

Node* Search(Node* node, int data)
{
    if (node == NULL)
        return NULL;
	
    if (node->data == data)
        return node;

    return Search(node->NEXT, data);
}

Node* Delete(Node* node, int data)
{
    if (node == NULL) return NULL;
	
    if (node->data == data)
    {
        Node* nextNode = node->NEXT;
        free(node);
		
        return nextNode;
    }
	
    node->NEXT = Delete(node->NEXT, data);
    return node;
}

void main()
{
    Node* head = NULL;
    //데이터 추가
    for(int i = 0; i < MAX; i++)
        head = AddData(head, i);
    ShowAllData(head);
    
    //결과 : 0 1 2 3 4 5 6 7 8 9
    
    //탐샋
    Node* someNode = Search(head, 5);
    if(someNode != NULL)
        printf("%d\n", someNode->data);
        
    //결과 : 5
    
    //삭제
    head = Delete(head, 8);
    ShowAllData(head);
    //결과 : 0 1 2 3 4 5 6 7 9
}
반응형

'Stack > Data struct' 카테고리의 다른 글

C 트리 순회(Tree traversal) 구현  (0) 2021.09.10
C 이진탐색트리(Binary search tree) 구현  (0) 2021.09.09
C 트리(Tree) 설명  (0) 2021.09.09
C 큐(Queue) 구현  (0) 2021.09.09
C 스택(Stack) 구현  (0) 2021.09.05
반응형
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<Windows.h>
#define MAX 50
#define TRUE 1

typedef struct StudentInfo
{
    int Number;
    char Name[10];
    int Age;
    char Gender[10];
    int Grade;
}StudentInfo;

int SetStudent(StudentInfo* student, int count)
{
    student->Number = ++count;
    printf("====%d번 학생====", student->Number);
    printf("\n이름 입력 : ");
    scanf("%s", student->Name);
    printf("\n나이 입력 : ");
    scanf("%d", &student->Age);
    printf("\n성별 입력 : ");
    scanf("%s", student->Gender);
    printf("\n학년 입력<1~3> : ");
    scanf("%d", &student->Grade);

    return count;
}

void ShowStudent(StudentInfo* student)
{
    printf("====%s학생<%d번>====\n", student->Name, student->Number);
    printf("나이 : %d, 성별 : %s, 학년 : %d\n", student->Age, student->Gender, student->Grade);
    printf("==========\n");
}

void ShowStudentByGrade(StudentInfo* studentArr[], int grade)
{
    printf("========%d 학년 \n", grade);
    for (int i = 0; studentArr[i] != NULL; i++)
    	if (studentArr[i]->Grade == grade)
        	ShowStudent(studentArr[i]);

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

void SearchStudentByGrade(StudentInfo* studentArr[])
{
    int grade = 0;
    printf("학년 입력 : ");
    scanf("%d", &grade);

    system("cls");
    if (grade > 0 && grade <= 3)
    	ShowStudentByGrade(studentArr, grade);
}

void SearchStudentByName(StudentInfo* studentArr[])
{
    char name[10] = { 0 };
    printf("이름 입력 : ");
    scanf("%s", name);

    system("cls");
    for (int i = 0; studentArr[i] != NULL; i++)
    	if (strcmp(studentArr[i]->Name, name) == 0)
    		ShowStudent(studentArr[i]);
}

void Save(StudentInfo* studentArr[])
{
    FILE* file = fopen("Students.txt", "w");

    for (int i = 0; studentArr[i] != NULL && i < MAX; i++)
    	fprintf(file, "%s %d %s %d\n", studentArr[i]->Name, studentArr[i]->Age,
    	studentArr[i]->Gender, studentArr[i]->Grade);

    fclose(file);
}

//포인터로 반환해도 좋지만, return으로 반환을 우선으로 생각한다.
int Load(StudentInfo* studentArr[], int count)
{
    if (count + 1 >= MAX)
    {
    	printf("학생목록을 더이상 불러올 수 없습니다.");
    	system("pause");
    	return;
    }

    FILE* file = fopen("Students.txt", "r");
    if (file == NULL)
    {
    	printf("해당 파일이 존재하지 않습니다.");
    }
    else
    {
    	for (; count < MAX; count++)
        {
            studentArr[count] = (StudentInfo*)malloc(sizeof(StudentInfo));
            studentArr[count]->Number = count + 1;
            int eof = fscanf(file, "%s%d%s%d", studentArr[count]->Name, &studentArr[count]->Age,
            studentArr[count]->Gender, &studentArr[count]->Grade);
            if (eof == EOF)
            {
                free(studentArr[count]);
                studentArr[count] = NULL;
                break;
            }
        }

        fclose(file);

        return count;
    }
}

void main()
{
    StudentInfo* studentArr[MAX] = { 0 };
    int count = 0;
    while (TRUE)
    {
    	system("cls");
        int label = 0;

        printf("====학생관리프로그램====(total : %d)\n", count);
        printf("  1. 학생 등록\n");
        printf("  2. 학생 목록<번호순>\n");
        printf("  3. 학생 목록<학년순>\n");
        printf("  4. 학년 검색\n");
        printf("  5. 학생 검색\n");
        printf("  6. 마지막 학생 삭제\n");
        printf("  7. 학생 전체 삭제\n");
        printf("  8. 학색 목록 저장하기\n");
        printf("  9. 학색 목록 불러오기\n");
        printf("  10. 종료\n");
        printf("입력 : ");
        scanf("%d", &label);

        system("cls");
        switch (label)
        {
        case 1:
            if (count + 1 >= MAX)
            {
            	printf("정원(50명) 초과");
                system("pause");
                break;
            }

            studentArr[count] = (StudentInfo*)malloc(sizeof(StudentInfo));
            count = SetStudent(studentArr[count], count);
            break;
        case 2:
            for (int i = 0; i < count; i++)
                ShowStudent(studentArr[i]);

            system("pause");
            break;
        case 3:
            for (int i = 0; i < 3; i++)
                ShowStudentByGrade(studentArr, i + 1);

            system("pause");
            break;
        case 4:
            SearchStudentByGrade(studentArr);
            system("pause");
            break;
        case 5:
            SearchStudentByName(studentArr);
            system("pause");
            break;
        case 6:
            if (count > 0)
            {
            	count--;
                free(studentArr[count]);
                studentArr[count] = NULL;
            }
            break;
        case 7:
            count = 0;
            for (int i = 0; studentArr[i] != NULL; i++)
            {
            	free(studentArr[i]);
                studentArr[i] = NULL;
            }
            break;
        case 8:
            if (count > 0)
                Save(studentArr);
            break;
        case 9:
            count = Load(studentArr, count);
            break;
        case 10:
            return;
        }
    }
}

  ※ SetSudent함수 : Grade 값이 범위 안(1학년~3학년) 사이에 들지 않는 오입력이 일어날 수 있으므로 필요하면 while문으로 범위 안에 들어올 때까지 계속 값을 요구하는 코드를 넣을수도 있다.

  ※ SetStudent함수, Load 함수 : count 인수를 포인터로 받을수도 있지만 이런 경우엔 포인터로 인수를 받기보단 return 값을 먼저 생각해서 작성한다.

  ※case 10 (종료 Label) : 프로그램이 종료되면 동적 할당이 자동으로 반환되지만, 해제 후 return해도 무방하다.

반응형

'Stack > C' 카테고리의 다른 글

C 파일 입출력  (0) 2021.08.24
C 구조체, 구조체 포인터  (0) 2021.08.22
C 동적할당  (0) 2021.08.22
C 포인터, 배열  (0) 2021.08.22
반응형

파일 입출력

- 프로그램 내의 정보를 외부 파일에 저장하거나 외부 파일의 정보를 프로그램으로 불러오는 방식.

  ※ 스트림 : 구현한 프로그램과 참조할 데이터가 저장되어 있는 파일 사이에 놓는 다리.

- 필요 헤더 : <stdio.h>

 

fopen 함수

- FILE* fopen(char* filename, char* mode)

- mode 값에 따라 파일 입출력 옵션이 정해진다

  ※ w(덮어쓰기) : 파일이 없을 경우 새로 만듦, 내용이 있을 경우 전부 지우고 다시 작성됨.

  ※ a(추가) : 파일이 없을 경우 새로 만듦, 내용이 있을 경우 마지막 내용 뒤 추가.

  ※ r(읽기) : 파일이 없을 경우 NULL을 반환한다.

- 성공 시 해당 FILE 구조체 변수의 주소 값, 실패시 NULL 반환

  ※ 구조체의 주소 값을 반환하기 때문에 FILE 포인터로 변수를 선언함.

  ※ 해당 함수를 호출하면 FILE 구조체 생성 후, 구조체 변수에 파일에 대한 정보가 담긴다.

 

fclose 함수

- int fclose(FILE* stream)

- fopen으로 인해 형성된 스트림을 해제하는 함수

  ※ 운영 체제가 할당한 자원(주로 메모리)을 반환한다.

  ※ 스트림 중간에 존재하는, 버퍼링 되어있던 데이터의 출력.

- 성공 시 0, 실패 시 EOF를 반환

  ※ EOF : end of file, -1의 값을 가지고 있는 상수이다.

 

fprintf 함수

- int fprintf(FILE* stream, char* format)

- 파일의 내용 출력

  ※ 출력의 대상이 콘솔이 아닌 파일이다.

 

구구단 예시

#include<stdio.h>

void main()
{
    FILE* file = fopen("GoGoDan.txt", "w");
    for(int i = 1; i <= 9; i++)
        for(int j = 1; j <= 9; j++)
            fprintf(file, "%d x %d = %d\n", i, j, i * j);
    
    fclose(file);
    
    //결과 : 1단 ~ 9단까지 구구단
}

 

fscanf 함수

- int fscanf(FILE* stream, char* format)

  ※ 파일의 끝에 도달하면 EOF를 반환한다.

- 띄어쓰기 또는 엔터 단위로 정보를 가져온다.

- 파일의 내용 입력

  ※ 입력의 대상이 콘솔이 아닌 파일이다.

 

fgets 함수

- char* fgets(char* buffer, int count, FILE* stream)

- 엔터 단위로 정보를 가져온다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

typedef struct temp
{
    char arr[10];
    int a;
}Temp;

void main()
{
    Temp tmp = { "A", 10 };
    FILE* file = fopen("Tmp.txt", "w");
    char buf[256];
    fprintf(file, "%s\n", tmp.arr);
    fprintf(file, "%d", tmp.a);
    fclose(file);
    
    file = fopen("Tmp.txt", "r");
    if (file == NULL)
    {
        printf("해당 파일이 존재하지 않습니다.\n");
    }
    else
    {
        while (!feof(file))
        {
            fgets(buf, sizeof(buf), file);
            printf("%s", buf);
        }
        
        fclose(file);
    }
    
    // 결과 : A
    //        10
}

 

fread 함수

- char* fread(char* buffer, size_t size, size_t count, FILE* stream)

  ※ count는 바이트 수이다. 보통 1로 둔다.

- 성공지 전달인자 count, 실패 또는 파일의 끝 도달 시 count보다 작은 값 반환

- fgets 함수와는 달리 비어있는 부분은 NULL로 채워주지 않는다.

  ※ 그렇기 때문에 buffer 배열을 선언시에 초기화 후 사용한다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

typedef struct temp
{
    char arr[10];
    int a;
}Temp;

void main()
{
    Temp tmp = { "A", 10 };
    FILE* file = fopen("Tmp.txt", "w");
    char buf[256] = {0};
    fprintf(file, "%s %d\n", tmp.arr, tmp.a);
    fclose(file);
    
    file = fopen("Tmp.txt", "r");
    if (file == NULL)
    {
        printf("해당 파일이 존재하지 않습니다.\n");
    }
    else
    {
        fread(buf, sizeof(buf), 1, file);
        printf("%s", buf);
        
        fclose(file);
    }
    
    // 결과 : A 10
}

  ※ buffer 선언부를 보면 초기화 한것을 확인할 수 있다.

반응형

'Stack > C' 카테고리의 다른 글

C 중간 활용 : 학생 관리 시스템 만들기  (0) 2021.08.24
C 구조체, 구조체 포인터  (0) 2021.08.22
C 동적할당  (0) 2021.08.22
C 포인터, 배열  (0) 2021.08.22
반응형

구조체

- 하나 이상의 변수(포인터와 배열 포함)를 묶어서 새로운 사용자정의 자료형

- 실존하는 정보를 데이터화 하는 추상화 작업

  ※ class와의 차이점은 접근지시자를 사용하지 않을시 struct는 public, class는 private으로 설정된다.

//type 1
struct example
{
    int a;
    char arr[10];
};

void main()
{
    struct example exam = { 10, "test" };
    printf("%d, %s", exam.a, exam.arr);
    
    //결과 10, test
}

 

typedef 선언

- typedef는 기존의 자료형의 이름에 새 이름(별명)을 부여하는 것을 목적으로 선언된다.

  ※ typedef int INT : int의 또 다른 이름 INT를 부여.

//type 2
struct example
{
    int a;
    char arr[10];
};

typedef struct example Example;

//type 3
typedef struct example
{
    int a;
    char arr[10];
}Example;

void main()
{
    Example exam = { 10, "test" };
    printf("%d, %s", exam.a, exam.arr);
    
    //결과 10, test
}

  ※ type 2와 같이 구조체 선언 후 typedef로 지정하는 법과 type 3과 같이 선언과 동시에 지정하는 방법이 있다.

 

구조체 변수와 포인터

- 기존 포인터와 선언 형식 및 접근의 방법이 다르지 않다.

typedef struct example
{
    int a;
    char arr[10];
}Example;

void main()
{
    Example exam = { 10, "test" };
    Example* exptr = &exam;
	
    printf("%d, %s", (*exptr).a, (*exptr).arr);
    
    //결과 10, test
}

  ※ 접근을 위해 포인터 변수를 대상으로 *연산을 하는것은 동일하다. 다만 구조체 포인터이기 때문에 변수에 접근하기위해 .연산을 추가해야한다.

  ※ *연산과 .연산을 하나의 ->연산으로 대체가 가능하다.

typedef struct example
{
    int a;
    char arr[10];
}Example;

void main()
{
    Example exam = { 10, "test" };
    Example* exptr = &exam;
	
    printf("%d, %s", exptr->a, exptr->arr);
    
    //결과 10, test
}

 

반응형

'Stack > C' 카테고리의 다른 글

C 중간 활용 : 학생 관리 시스템 만들기  (0) 2021.08.24
C 파일 입출력  (0) 2021.08.24
C 동적할당  (0) 2021.08.22
C 포인터, 배열  (0) 2021.08.22

+ Recent posts