링크드리스트, 스택, 큐

선 구현 후 설명

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <windows.h>
struct node {
    char ch;
    node *prev;
    node *next;
};
node *makelist();
void putlist(node **head, node **tail, node *current);
void print(node *head);
int search(node *head);
void kill(node **head, node **tail);
node *findnode(node *head, node **prev);
void save(node *head);
void load(node **head, node **tail);
 
int main(void)
{
    int mode = 0;
    int amount = 0;
    node *head, *tail, *current;
    head = tail = current = NULL;
    
    while (1)
    {
        puts("[1]입력");
        puts("[2]검색");
        puts("[3]삭제");
        puts("[4]출력");
        puts("[5]저장");
        puts("[6]불러오기");
        puts("[0]종료\n");
        scanf("%d", &mode);
        if(mode == 1)
        {
            puts("입력할 자료의개수");
            scanf("%d", &amount);
            getchar();
            for (int i = 0; i < amount; i++)
            {
                current = makelist();
                putlist(&head, &tail, current);
            }
            puts("완료되었습니다.\n");
        }
        else if(mode == 2)
        {
            int d = search(head);
            if (d == 1)
            {
                puts("찾지 못했습니다.");
                Sleep(2000);
                system("cls");
            }
            else if (d == 0)
            {
                puts("있습니다.\n");
                Sleep(2000);
                system("cls");
            }
            else
            {
                fprintf(stderr, "error!\n");
            }
        }
        else if(mode == 3)
        {
            kill(&head, &tail);
        }
        else if(mode == 4)
        {
            print(head);
        }
        else if(mode == 5)
        {
            save(head);
        }
        else if(mode == 6)
        {
            if (head != NULL)
                head = tail = NULL;
            load(&head, &tail);
        }
        else if(mode == 0)
        {
            system("cls");
            puts("종료합니다.");
            exit(1);
        }
        else
        {
            puts("잘못되었습니다.");
        }
    }
}
node *makelist()
{
    node *temp;
    temp = (node*)malloc(sizeof(node));
    scanf("%c", &(temp->ch));
    getchar();
    temp->next = NULL;
    temp->prev = NULL;
    return temp;
}
void putlist(node **head, node **tail, node *current)
{
    if (*head == NULL)
    {
        *head = *tail = current;
    }
    else
    {
        (*tail)->next = current;
        current->prev = *tail;
        *tail = current;
    }
}
void print(node *head)
{
    while (head)
    {
        printf("%c", head->ch);
        head = head->next;
    }
    printf("\n");
}
int search(node *head)
{
    char sch;
    getchar();
    scanf("%c", &sch);
    while (head)
    {
        if (head->ch == sch)
        {
            return 0;
        }
        else
            head = head->next;
    }
    return 1;
}
void kill(node **head, node **tail)
{
    node *prev, *find;
    node *temp;
    find = findnode(*head, &prev);
    if (find == NULL)
    {
        puts("삭제할 자료가 없습니다.");
    }
    else if (find == *head)
    {
        temp = *head;
        *head = (*head)->next;
        (*head)->prev = NULL;
        free(temp);
    }
    else if (find == *tail)
    {
        temp = *tail;
        *tail = (*tail)->prev;
        (*tail)->next = NULL;
        free(temp);
    }
    else
    {
        temp = find;
        prev->next = find->next;
        prev->next->prev = prev;
        free(find);
    }
}
node *findnode(node *head, node **prev)
{
    char kch;
    getchar();
    scanf("%c", &kch);
    while (head)
    {
        if (head->ch == kch)
            return head;
        else
        {
            head = head->next;
            *prev = head->prev;
        }
    }
    return NULL;
}
void save(node *head)
{
    char fname[50];
    puts("파일이름 입력");
    scanf("%s", fname);
    FILE *fp;
    fp = fopen(fname, "wb");
    while (head)
    {
        fwrite(head, sizeof(node), 1, fp);
        head = head->next;
    }
    puts("완료되었습니다.");
    fclose(fp);
}
void load(node **head, node **tail)
{
    char fname[50];
    node *current;
    FILE *fp;
    int n = 1;
    puts("파일이름 입력");
    scanf("%s", fname);
    fp = fopen(fname, "rb");
    if (fp == NULL)
    {
        fprintf(stderr, "error!\n");
    }
    else
    {
        while (1)
        {
            current = (node*)malloc(sizeof(node));
            n = fread(current, sizeof(node), 1, fp);
            if (n != 1)
                break;
            putlist(head, tail, current);
        }
        fclose(fp);
    }
    
}

링크드리스트란, 구조체, 즉 노드에 있는 포인터가 앞이나, 뒤의 구조체를 가르키면서, 메모리에선 연결되있지 않지만 논리적으로 연결되어있는 구조를 뜻한다.

대개 이런식으로 되어있다.

헤드를 뒤로밀면 스택이 될 수있고,

테일을 뒤로밀면 큐가 된다.

자료탐색을 위해 순회를해야한다.

#include <stdio.h>
 
int pop(int * top, int stack[]);
int push(int data, int * top, int stack[]);
 
int main(void)
{
    int stack[100]={};
    int cnt=-1;
    int *top;
    int buf;
    int i =0;
    int n;
    top = &cnt;
    puts("자료의 개수를 입력하여 주십시오.(최대 100)");
    scanf("%d", &n);
    for(i=0;i<n;i++)
    {
        buf = i;
        printf("%d\n", buf);
        push(buf, top, stack);
    }
    for(i=0;i<n;i++)
    {
        printf("%d\n", pop(top, stack));
    }
    top = &cnt;
    return 0;
}
 
int pop(int * top, int stack[])
{
    if(*top<0)
    {
        fprintf(stderr, "Stack has no data!!\n");
        return -1;
    }
    else
    {
        return stack[(*top)--];
    }
}
int push(int data, int * top, int stack[])
{
    if(*top<99)
    {
        *top = *top+1;
        stack[*top] = data;
        return 0;
    }
    else
    {
        fprintf(stderr, "Stack is FULL!!!!\n");
        return -1;
    }
}

스택은 FILO 으로, 먼저들어간게 뒤에 쌓여서 늦게 나오는 구조이다.

소프트웨어로 이를 구현하면, 스택의 꼭대기를 가르키는 top이 있고, 자료를 넣을때마다 1씩 상승한다. 자료를 POP하면 top 이 -1 되고 그값을 반환한다.

큐는 FIFO 으로, 먼저들어간게 먼저 나오는 구조이다.

보통 큐는 한쪽으로 가면, 다시 역으로 확장하기 힘들기때문에, 큐사이즈로 나눈 나머지로 원형큐를 구현한다.

 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
#define SIZE 40
 
int arr[SIZE];
int count;
 
void put(int *rear, int front, int data);
int deque(int rear, int *front);
 
int main(void)
{
    int rear = 0, front = 0, i;
    int data;
    int mode = 0;
    while (1)
    {
        puts("[1] INPUT");
        puts("[2] DELETE");
        puts("[3] print all");
        puts("[4]exit");
        scanf("%d%*c", &mode);
        if (mode == 1)
        {
            puts("Input Data");
            scanf("%d%*c", &data);
            put(&rear, front, data);
        }
        else if (mode == 2)
        {
            printf("%d \n", deque(rear, &front));
        }
        else if (mode == 3)
        {
            for (i = 0; i < count; i++)
            {
                if (arr[i] == -99999)
                {
                    puts("Your Que is empty");
                    break;
                }
                else
                    printf("%d\n", arr[i]);
            }
        }
        else if (mode == 4)
        {
            exit(1);
        }
        else
            continue;
        system("cls");
    }
}
void put(int *rear, int front, int data)
{
    *rear = (*rear + 1) % SIZE;
    if (*rear == front)
    {
        puts("Hey! Que is FULL!!!");
        return;
    }
    else
    {
        count++;
        arr[*rear - 1] = data;
    }
}
int deque(int rear, int *front)
{
    int ret;
    if (*front == rear)
    {
        puts("Hey!! Que is empty");
        return 0;
    }
    else
    {
        count--;
        *front = (*front + 1) % SIZE;
        ret = arr[*front - 1];
        arr[*front - 1] = -99999;
        return ret;
    }
}