Su embedded training - Day10

One 、 Bidirectional circular linked list

1.1 Concept

1.2 operation

1.2.1 Define a node structure

#ifndef _DOUBLELIST_H_
#define _DOUBLELIST_H_
#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
// Define the node structure 
typedef struct doublelist
{
    
    DataType data;
    struct doublelist *front;   // Save the address of the previous node 
    struct doublelist *next;   // Save the address of the next node 
}doublelist;

1.2.2 Create an empty two-way circular linked list

// Create an empty two-way circular linked list 
doublelist * DoubleListCreate()
{
    
    doublelist *head = (doublelist *)malloc(sizeof(doublelist));
    head->front = head;
    head->next = head;
    return head;
}

1.2.3 insert data

// insert data 
void DoubleListInsert(doublelist *head,DataType value)
{
    
    doublelist *tmp = (doublelist *)malloc(sizeof(doublelist));
    tmp->front = NULL;
    tmp->next = NULL;
    tmp->data = value;

    tmp->next = head->next;
    tmp->front = head;

    head->next->front = tmp;
    head->next = tmp;
}

1.2.4 Traversing the linked list

// Traverse the two-way circular linked list 
void DoubleListPrint(doublelist *head)
{
    
    doublelist *p = head;
    while(p->next != head)
    {
    
        p = p->next;
        printf("%d ",p->data);
    }
    putchar(10);
}

practice ： Delete data by header deletion

// Delete data by header deletion 
DataType DoubleListDelete(doublelist *head)
{
    
    if(head->next == head)
    {
    
        printf(" The two-way circular linked list is empty ！\n");
        return (DataType)-1;
    }
    doublelist *tmp = head->next;

    head->next = tmp->next;
    tmp->next->front = head;

    DataType value = tmp->data;
    free(tmp);
    tmp = NULL;
    return value;
}

Two 、 Stack （stack）

2.1 Concept

The nature of the stack ： Last in, first out
Stack operation ：
Push （ Pressing stack ）push
Out of the stack （ Single stack ）pop

2.2 Order of the stack seqstack

2.2.1 Define data types

#ifndef _SEQSTACK_H_
#define _SEQSTACK_H_

#include <stdio.h>
#include <stdlib.h>
#define N 32
typedef int DataType;
typedef struct seqstack
{
    
    DataType data[N];
    int pos;
}seqstack;

#endif

2.2.2 Defining structure

Create a stack

// Create an empty stack 
seqstack* SeqStackCreate()
{
    
    seqstack *s = (seqstack *)malloc(sizeof(seqstack));
    s->pos = -1;
    return s;
}

2.2.3 Determine whether the stack is full

// Determine whether the stack is full 
int SeqStackIsFull(seqstack *s)
{
    
    return s->pos == N -1 ? 1 : 0;
}
 Judge whether the stack is empty 
// Judge whether the stack is empty 
int SeqStackIsEmpty(seqstack *s)
{
    
    return s->pos == -1 ? 1: 0;
}

2.2.4 Push

// Push 
void SeqStackPush(seqstack *s,DataType value)
{
    
    if(SeqStackIsFull(s))
    {
    
        printf(" The stack is full ！\n");
        return;
    }
    s->pos++;
    s->data[s->pos] = value;
    return;
}

2.2.5 Out of the stack

// Out of the stack 
DataType SeqStackPop(seqstack *s)
{
    
    if(SeqStackIsEmpty(s))
    {
    
        printf(" The stack is empty. ！\n");
        return (DataType)-1;
    }
    DataType value = s->data[s->pos];
    s->pos--;
    return value;
}

2.3 Chain stack （ Chain stack ）

The overall code

mian.c

//main.c
#include "linkstack.h"
int main(int argc, char const *argv[])
{
    
    stack s;
    InitStack(&s);
    push(&s,100);
    push(&s,200);
    push(&s,300);
    push(&s,400);
    push(&s,500);
    push(&s,600);
    push(&s,700);

    while(!EmptyStack(&s))
    {
    
        printf(" Out of the stack :%d\n",pop(&s));
    }
    return 0;
}

linkstack.c

//linkstack.c
#include "linkstack.h"
// Initialization stack information 
void InitStack(stack *s)
{
    
    s->length = 0;
    s->top = NULL;
}
// Push 
void push(stack *s,DataType value)
{
    
    if(NULL == s)
    {
    
        printf(" Stack space allocation failed , initialization failed ！\n");
        return ;
    }
    Node *tmp = (Node *)malloc(sizeof(Node));
    tmp->next = NULL;
    tmp->data = value;

    tmp->next = s->top;
    s->top = tmp;
    s->length++;
}
// Get stack top element 
DataType GetTop(stack *s)
{
    
    if(NULL == s)
    {
    
        return (DataType)-1;
    }
    if(s->top == NULL)
    {
    
        return (DataType)-1;
    }
    return s->top->data;
}
// Out of the stack 
DataType pop(stack *s)
{
    
    if(NULL == s)
    {
    
        return (DataType)-1;
    }
    if(s->top == NULL)
    {
    
        return (DataType)-1;
    } 
    Node *tmp = s->top;
    s->top = tmp->next;
    DataType value = tmp->data;
    free(tmp);
    tmp = NULL;
    s->length--;
    return value;
}
// Judge whether the stack is empty 
int EmptyStack(stack *s)
{
    
    return s->top == NULL ? 1 : 0;
}
// Empty stack 
int ClearStack(stack *s)
{
    
    if(NULL == s)
    {
    
        return (DataType)-1;
    }
    if(s->top == NULL)
    {
    
        return (DataType)-1;
    }
    Node *tmp = s->top;
    while(tmp)
    {
    
        s->top = tmp->next;
        free(tmp);
        tmp = s->top;
        s->length--;
    }     
    return 1;
}

practice Four arithmetic unit

// Determine the priority of symbols 
int Priority(char ch)
{
    
    switch (ch)
    {
    
    case '(':
        return 3;
    case '*':
    case '/':
        return 2;
    case '+':
    case '-':
        return 1;
    default:
        return 0;
    }
}
// Four hybrid calculators 
void calculator()
{
    
    stack s_sum, s_opt;
    InitStack(&s_sum);
    InitStack(&s_opt);
    char opt[128] = {
    0};
    printf(" Please enter the expression ：\n");
    scanf("%s",opt);
    int i = 0,tmp = 0,num1,num2;
    while(opt[i] != '\0' || EmptyStack(&s_opt) != 1)
    {
    
        if(opt[i] >= '0' && opt[i] <= '9')   // Operands 
        {
    
            tmp = tmp *10 + opt[i] - '0';
            i++;
            if(opt[i] < '0' || opt[i] > '9')
            {
    
                push(&s_sum,tmp);
                tmp = 0;
            }
        }
        else   // The operator 
        {
    
            if(EmptyStack(&s_opt) == 1 || Priority(opt[i]) > Priority(GetTop(&s_opt))||
            (GetTop(&s_opt) == '(' && opt[i] != ')'))
            {
    
                push(&s_opt,opt[i]);
                i++;
                continue;
            }
            if(GetTop(&s_opt) == '(' && opt[i] == ')')
            {
    
                pop(&s_opt);
                i++;
                continue;
            }
            if(Priority(opt[i]) <= Priority(GetTop(&s_opt)) ||opt[i] == ')' && GetTop(&s_opt)!= '('||
            opt[i] == '\0' && EmptyStack(&s_opt) != 1)
            {
    
                switch (pop(&s_opt))
                {
    
                case '+':
                    num1 = pop(&s_sum);
                    num2 = pop(&s_sum);
                    push(&s_sum,num1 + num2);
                    break;
                case '-':
                    num1 = pop(&s_sum);
                    num2 = pop(&s_sum);
                    push(&s_sum,num2 - num1);
                    break;
                case '*':
                    num1 = pop(&s_sum);
                    num2 = pop(&s_sum);
                    push(&s_sum,num1 * num2);
                    break;
                case '/':
                    num1 = pop(&s_sum);
                    num2 = pop(&s_sum);
                    push(&s_sum,num2 / num1);
                    break;               
                default:
                    break;
                }
            }
        }
    }
    printf("%d\n",GetTop(&s_sum));
}