알고리즘 서론 제10 장 기본 데이터 구조 실현 (스 택, 대기 열, 링크), 방과 후 문제 답

창고.
스 택 은 후진 선 출 전략 을 실현 하고 스 택 에 들 어가 거나 스 택 에 나 가 는 것 은 모두 스 택 꼭대기 지침 을 통 해 조작 합 니 다.

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

#define SIZE 10
typedef struct{
    int array[SIZE];
    int top;
}T_stack;

bool Empty(T_stack * Stack){
    if(Stack->top == -1)
        return true;
    else
        return false;
}

void Push(T_stack * Stack ,int x){
    if(Stack->top == SIZE-1){
        printf("the stack is full
");
        return;
    }
    else{
        Stack->top = Stack->top +1;
        Stack->array[Stack->top] = x;
    }
}

int Pop(T_stack * Stack ){
    if(Empty(Stack)){
        printf("the stack is empty
");
        return;
    }
    else{
        Stack->top = Stack->top-1;
        return Stack->array[Stack->top +1];
    }
}

int main(void){
    int i,num;
    T_stack * Stack;
    Stack = malloc(sizeof(T_stack));
    Stack->top = -1;
    srand((unsigned)time(NULL));  
        for(i = 0;i< SIZE;i++){
        num = rand() % SIZE; //     
        Push(Stack,num);
    }
    for(i  = 0;i< SIZE;i++)
        printf("%d ",Stack->array[i]);
    printf("the last data is :%d
",Pop(Stack));
    return 0;
}

대열
대열 은 일종 의 선진 적 인 선발 전략 으로 줄 을 서 는 것 처럼 새로 온 사람 은 대열 의 끝 에서 가입 하고 팀 을 나 간 사람 은 팀 에서 나온다.

#include<stdio.h>
#include <time.h>
#include <stdlib.h>
#define SIZE 10
typedef struct {
    int array[SIZE];
    int head;
    int tail;
}Heap;

void Enqueue(Heap * he,int x){
    if(he->head == ((he->tail+1)% SIZE)){
        printf("the heap is full");
        return ;
    }
    else{
        he->array[he->tail] = x;
        he->tail = (he->tail+1) % SIZE;
    }
}

int Dequeue(Heap * he){
    int x;
    if(he->head == he->tail){
        printf("the heap is empty");
        return;
    }
    else{
        x = he->array[he->head];
        if(he->head == SIZE-1)
            he->head = 0;
        else
            he->head--;
    }
    return x;
}

int main(void){
    int i,num;
    Heap * he;
    he = malloc(sizeof(Heap));
    he->head = he->tail = 0;
    srand((unsigned)time(NULL));
    for(i = 0;i <SIZE;i++){
        num = rand() %10;
        Enqueue(he,num);
    }
    printf("the heap is:
");
    for(i = 0;i< SIZE;i++){
        printf("%d ",he->array[i]);
    }
    printf("*****************
");
    printf("the first data is:%d
",Dequeue(he));
    return 0;
}

수업 후 10.1 - 2 코드 구현

#include <stdio.h>
#include <stdbool.h>
#include <time.h>
#include <stdlib.h>
#define SIZE 10
typedef struct {
    int array[SIZE];
    int top1;
    int top2;
}T_stack;

bool Empty(T_stack * Stack,int zone);
void Push(T_stack * Stack,int zone,int x);
int Pop(T_stack * Stack,int zone);

bool Empty(T_stack * Stack,int zone){
    if(zone == 1){
        if(Stack->top1 == -1)
            return true;
        else
            return false;
    }
    if(zone == 2){
        if(Stack->top2 == SIZE)
            return true;
        else 
            return false;
    }
}

void Push(T_stack * Stack,int zone,int x){
    if(Stack->top1 == Stack->top2){
        printf("the stack is overflow
");
        return;
    }
    if(zone == 1){
        Stack->top1 = Stack->top1+1;
        Stack->array[Stack->top1] = x;
    }
    else if(zone == 2){
        Stack->top2 = Stack->top2-1;
        Stack->array[Stack->top2] = x;
    }
}

int  Pop(T_stack * Stack,int zone){
    if(zone == 1){
        if(Empty(Stack,zone)){
            printf("the stack is empty
");
            return ;
        }
        else{
            Stack->top1 = Stack->top1-1;
            return Stack->array[Stack->top1+1];
        }
    }
    else if(zone == 2){
        if(Empty(Stack,zone)){
            printf("the stack is empty
");
            return;
        }
        else{
            Stack->top2 = Stack->top2+1;
            return Stack->array[Stack->top2-1];
        }
    }
}
int main(void){
    int i,num;
    T_stack * T_s;
    T_s = malloc(sizeof(T_stack));
    T_s->top1 = -1;
    T_s->top2 = SIZE;
    srand((unsigned)time(NULL));
    for(i = 0;i< SIZE/2;i++){
        num = rand() % 10;
        Push(T_s,1,num);
    }
    for(i  = 0;i< SIZE/2;i++){
        num = rand() % 10;
        Push(T_s,2,num);
    }
    printf("the left stack first data: %d
",Pop(T_s,1));
    printf("the right stack first data: %d
",Pop(T_s,2));
    return 0;
}

수업 후 10.1 - 5 코드 구현

#include<stdio.h>
#include <stdlib.h>
#define SIZE 10
typedef struct{
    int array[SIZE];
    int head;
    int tail;
}Deque;

void enqueue_head(Deque * deq,int x){
    if(deq->head == deq->tail+1){
        printf("the deque is overflow");
        return ;
    }
    else{

        deq->array[deq->head] = x;
        if(deq->head == 0)
            deq->head = SIZE-1;
        else{
            deq->head = deq->head-1;
        }
    }
    printf("the head is: %d 
",deq->head);
}

void enqueue_tail(Deque * deq ,int x){
    if(deq->head == deq->tail +1){
        printf("the deque is overflow");
        return ;
    }
    else{
        deq->array[deq->tail] = x;
        deq->tail = (deq->tail+1 )% SIZE;
    }
}

int Dequeue_head(Deque * deq){
    int x;
    if(deq->head == deq->tail){
        printf("the deque is empty");
        return ;
    }
    else{
        if(deq->head == SIZE-1){
            x = deq->array[0];
            deq->head = 0;
        }
        else{
            x = deq->array[deq->head+1];
            deq->head++;
        }
    }
    return x;
}

int Dequeue_tail(Deque * deq){
    int x;
    if(deq->head == deq->tail){
        printf("the deque is empty");
        return;
    }
    else{
        if(deq->tail == 0){
            x = deq->array[SIZE-1];
            deq->tail = SIZE-1;
        }
        else{
            x = deq->array[deq->tail-1];
            deq->tail--;
        }
    return x;
    }
}

int main(void){
    int i;
    Deque * deq;
    deq = malloc(sizeof(Deque));
    deq->head =0;
    deq->tail = 1;
    enqueue_head(deq,1);
    enqueue_head(deq,2);
    enqueue_tail(deq,3);
    enqueue_tail(deq,4);
    printf("%d ",deq->array[0]);
    printf("%d ",deq->array[1]);
    printf("%d ",deq->array[2]);
    printf("%d ",deq->array[9]);
    printf("the head first is :%d
",Dequeue_head(deq));
    printf("the tail first is : %d 
",Dequeue_tail(deq));
    return 0;
}

체인 테이블
구조 체 를 구성 할 때 표현 방식 이 약간 다 르 고 단 방향 링크 에서 의 표현 이 더욱 뚜렷 하 다.1. 시계 머리 가 있 는 양 방향 링크

//         
#include<stdio.h>
#include <stdlib.h>
typedef struct T_list {
    int key;
    struct T_list * prev;
    struct T_list * next;
}T_list;

T_list * List_Search(T_list * L,int k){
    T_list * P;
    P =  L->next;
    while(P != NULL){
        if(P->key == k)
            return P;
        else
            P = P->next;
    }
    return P;
}

void List_insert(T_list * L,int x){
    T_list * node;
    node = (T_list *)malloc(sizeof(T_list));
    node->key = x;
    if(L->next == NULL){
        L->next = node;
        node->next = NULL;
        node->prev = L;
    }
    else{
        node->next = L->next;
        L->next->prev = node;
        node->prev = L;
        L->next = node;
    }
}

void List_delete(T_list * L,int x){
    T_list * P;
    P = List_Search(L,x);
    if(P != NULL){
        P->prev->next = P->next;
        P->next->prev = P->prev;
        free(P);
    }
    else
        printf("the data is noexist
");
}

void List_print(T_list * L ){
    T_list * P;
    P = L->next;
    while(P != NULL){
        printf("%d ",P->key);
        P = P->next;
    }
    printf("
");
}

int main(void){
    int i,num;
    T_list * head;
    T_list * temp;
    head = malloc(sizeof(T_list));
    head->next = NULL;
    for(i = 0;i< 5;i++){
        scanf("%d",&num);
        List_insert(head,num);
    }
    List_print(head);
    List_delete(head,3);
    List_print(head);
    return 0;
}

단 방향 링크

#include <stdio.h>
#include <stdlib.h>
struct T_list;
typedef struct T_list * List;
typedef List Position;
struct T_list{
    int key;
    Position next;
};

Position List_Search(List L,int k){
    List P;
    P = L->next;
    while(P != NULL && P->key != k)
        P = P->next;
    return P;
}

void List_insert(List L,int x){
    Position P;
    P = malloc(sizeof(struct T_list));
    P->key = x;
    P->next = L->next;
    L->next = P;
}

//   x       
void List_delete(List L,int x){
    Position P;
    P = L;
    while(P->next != NULL && P->next->key != x)
            P = P->next;
    if(P->next != NULL){
        Position de;
        de = P->next;
        P->next = de->next;
        free(de);
    }
    else
        printf("the list is empty
");
}
void List_print(List L){
    Position P;
    P = L->next;
    while(P != NULL){
        printf("%d ",P->key);
        P = P->next;
    }
    printf("
");
}
int main(void){
    int i,num;
    List head;
    head = malloc(sizeof(struct T_list));
    head->next = NULL;
    for(i = 0;i< 5;i++){
        scanf("%d",&num);
        List_insert(head,num);
    }
    List_print(head);
    List_delete(head,3);
    List_print(head);
    return 0;
}