[数据结构与算法]实验：栈和队列

实验内容：

1、设单链表中存放着n个字符,设计算法,判断该字符串中是否有中心对称关系。例如：xyzzyx、 xyzyx都算是中心对称的字符串。
2、设计算法判断一个算术表达式的圆括号是否配对。(提示:对表达式进行扫描,遇‘(‘进栈,遇’)’退掉栈顶的’(‘,表达式被扫描完毕,栈为空)
3、假设以带头结点的循环链表表示队列,并只设个指针指向队尾,编写相应的置队空、入队和出队算法。

实验代码：?

#include<iostream>
//#include<queue>
#include<string.h>

using namespace std;

#define STACK_INIT_SIZE 100
#define OK 1 
#define ERROR 0
#define OVERFLOW -1

typedef int ElemType;
typedef int Status;
typedef char SElemType;

//struct of LNode
typedef struct LNode
{
    char data;      //data
    struct LNode *next; //pointer 
}LNode, *LinkList;

//struct of stack
typedef struct 
{
    SElemType *base;    //base pointer
    SElemType *top;     //top pointer
    int stacksize;      //max size of stack
}SqStack;

//struct of queue
typedef struct qnode 
{
    ElemType data;
    struct qnode *next;
}QueueNode;

typedef struct 
{
    QueueNode *front;
    QueueNode *rear;
}LinkQueue;

//init of stack
Status init_stack(SqStack *stack)
{
    //malloc space for stack
    stack->base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));  

    //failed to open up space
    if(!stack->base) exit(OVERFLOW);

    //init data    
    stack->top = stack->base;
    stack->stacksize = STACK_INIT_SIZE;
    return OK;
}

//insert e into sqstack
Status push_stack(SqStack *stack, SElemType elem) {
    //if stack is full
    if (stack->top-stack->base == stack->stacksize) {
        return ERROR;    
    }

    //add elem
    *stack->top++=elem;     
    return OK;
}

//get out of stack
Status pop_stack(SqStack *stack, SElemType elem) {
    //if stack is empty
    if (stack->top == stack->base) {
        return ERROR;
    }

    //complate elem and --s->top 
    if (elem == *(--stack->top)) {
        return OK;
    } else {
        return ERROR;
    }
}

//init queue
Status init_queue(QueueNode *&rear) {
    //malloc a space for rear
    rear = (QueueNode *)malloc(sizeof(QueueNode));  
    rear->next = rear;

    return OK;
}

//enter a node to queue
Status enter_queue(QueueNode *&rear, ElemType elem) {
    //malloc a space for new node
    QueueNode *node_insert;   
    node_insert = (QueueNode*)malloc(sizeof(QueueNode));  

    //insert the data
    node_insert->data = elem;
    node_insert->next = NULL;

    //change the positive of rear
    node_insert->next = rear->next;
    rear->next = node_insert;
    rear = node_insert;

    return OK;
}

//pop_stack of queue, get out the front of queue
Status delete_queue(QueueNode *&rear) {
    QueueNode *q;

    //if head node, return ERROR
    if (rear->next == rear) {
        return ERROR;

    //if only head node and one node in the queue
    } else if (rear->next->next == rear) {
        q = rear->next;
        q->next = q;
        free(rear);
        rear = q;
        return OK;
    
    //if more than two node
    } else {
        q = rear->next->next;
        rear->next->next = q->next;
        free(q);
        return OK;
    }
}

//whether empty
Status empty_queue(QueueNode *&rear) {
    QueueNode *queue_head;

    //while until empty
    while (1) {
        //if queue is empty
        if (rear->next == rear) {
            return ERROR;
        }

        //if two node
        if (rear->next->next == rear) {
            queue_head = rear->next;
            queue_head->next = queue_head;
            free(rear);
            rear = queue_head;
            
        //if more than two node
        } else {
            queue_head = rear->next->next;
            rear->next->next = queue_head->next;
            free(queue_head);
        }
    }
}

//display queue
Status display_queue(QueueNode *&rear) {
    //only the head node
    if (rear->next == rear) {
        return ERROR;
    }
    
    //queue_front is the first node without head node
    QueueNode *queue_front = rear->next->next;

    //if more than one value node
    while (queue_front != rear) {
        cout << queue_front->data << " ";
        queue_front = queue_front->next;
    }

    //if only one value node
    if (queue_front == rear) {
        cout << queue_front->data << " ";
    }
    cout << endl;
    
    return OK;
}

//func of creating a single linked in the first Question
LinkList create_single_linked(int n)
{
    int i;  //using for input data
    LinkList L_head;        //head of the link

    L_head = (LinkList)malloc(sizeof(LinkList));
    cout << "plese input a char:";
    cin >> L_head->data;
    L_head->next=NULL;

    LinkList temp=L_head;

    for(i=1;i<n;i++)
    {   //input data into link
        LinkList insert_linked=(LinkList)malloc(sizeof(LinkList));
        cout << "plese input a char:";
        cin >> insert_linked->data;
        insert_linked->next = NULL;
        //link together
        temp->next = insert_linked;
        temp = insert_linked;
    }

    return L_head;
}

//func of printing single linked
Status print_single_linked(LinkList L_head) 
{
    LinkList temp=L_head;

    do{
        cout << temp->data;
        temp=temp->next;
    }while (temp!=NULL);
    
    return OK;
}

//Func of using "whether is symmetry"
Status use_whether_symmetry() {
    int n;          //the node to create
    int i;          //for push_stack and pull
    LinkList head;  //head of single linked
    SqStack stack;

    cout << "how many node to create:";
    cin >> n;

    //creating a single linked and print it
    head = create_single_linked(n);
    print_single_linked(head);  
    cout << endl;

    //push half of the data into stack, and then complate them
    LinkList temp=head;
    init_stack(&stack);
    int half=n/2;
    //push data       
    for(i=0;i<half;i++) {   
        push_stack(&stack,temp->data);
        temp=temp->next;
    }
    //judge Odd or even, if "odd" turn next
    if(n%2!=0) {
        temp=temp->next;
    }
    //pop data
    int empty;      //OK or ERROR
    do {
        //pop_stack the data
        empty = pop_stack(&stack, temp->data);
        temp = temp->next;
    } while (temp != NULL);
    
    //Judge whehter is void
    if (stack.top == stack.base && empty == OK) {
        cout << "Yes!!!\n";
    } else {
        cout << "No!!!\n";
    }

    //whether again
    char choose;
    cout << "again?(y/n):";
    cin >> choose;
    if (choose == 'y') {
        return OK;
    } else {
        return ERROR;
    }
}

//Judge 2
Status use_whether_pair() {
    cout << "please enter an expression:";
    char expression[20];
    cin >> expression; //input a string
    cout << expression;

    //inint stack
    SqStack stack;
    init_stack(&stack);
    int i;  //for ergodic
    char ok_no = ' ';

    //input expression into stack
    for (i = 0; i < strlen(expression); ++i) {
        if (expression[i] == '(') {
            push_stack(&stack, expression[i]);
        }
        if (expression[i] == ')') {
            //if the first insert ')' is false
            if (stack.top == stack.base) {
                ok_no = 'n';
                break;       
            }
            pop_stack(&stack, '(');
        }
    }

    //Judge whether matching
    if (stack.base == stack.top && ok_no != 'n') {
        cout << " is matching!!!\n";
    } else {
        cout << " is no matching!!!\n";
    }

    //whether again
    char choose;
    cout << "again?(y/n):";
    cin >> choose;
    if (choose == 'y') {
        return OK;
    } else {
        return ERROR;
    }
}
//Judge 3 
Status use_whether_queue() {
        QueueNode *p;
        init_queue(p);    

        while (1) {
        cout << "**********\n";
        cout << "1.push queue\n";
        cout << "2.pop queue\n";
        cout << "3.empty queue\n";
        cout << "4.display queue\n";
        cout << "5.back to menu\n";
        cout << "**********\n";
        int choose;
        cout << "please input your choose(1~5):";
        cin >> choose;

        int length; //how many node to insert
        
        //1.push_stack_queue
        if (choose == 1) {
            int data_insert;        
            cout << "please input the length:";
            cin >> length;
            //insert the node one by one
            for (int i = 0; i < length; ++i) {
                cout << "please input a int:";
                cin >> data_insert;
                enter_queue(p, data_insert);
            }

        //2.pop_stack_queue
        } else if (choose == 2) {
            delete_queue(p);
            cout << "pop_stack successful\n";

        //3.empty_queue
        } else if (choose == 3) {
            empty_queue(p);
            cout << "empty successful\n";

        //4.display_queue
        } else if (choose == 4 ) {
            display_queue(p);

        //5.back to menu
        } else {
            break;
        }
    }
    return OK;
}
//func of whether back to menu
Status whether_toMenu() {
    char choose_two;
    
    cout << "back to menu(y/n):";
    cin >> choose_two;

    if (choose_two == 'y') {
        return OK;
    } else {
        return ERROR;
    }

    return OK;
}

//main menu
Status menu() {
    int choose_one;
    char choose_two;

    do{
        cout << "\n*********************\n";
        cout << "1.Whether symmetry\n";
        cout << "2.Whether pair\n";
        cout << "3.Queue\n";
        cout << "4.Quit\n";
        cout << "**********************\n";
        cout << "plese input your choose(1~4):";
        cin >> choose_one;

        //1.Whether symmetry
        if (choose_one == 1) {   
            //Judge 1
            while (use_whether_symmetry() == 1);

            choose_two = whether_toMenu();
            if(choose_two == 1) {
                continue;
            } else {
                break;
            }
        }

        //2.Whether pair
        else if (choose_one == 2) {
            //Judge 2
            while (use_whether_pair() == 1);

            choose_two = whether_toMenu();
            if (choose_two == 1) {
                continue;
            } else {
                break;
            }
        }

        //3.Queue
        else if (choose_one == 3) {
            //Judge 3
            use_whether_queue();

            choose_two = whether_toMenu();
            if (choose_two == 1) {
                continue;
            } else {
                break;
            }
        }

        //4.Quit 
        else {
            break;
        }
    } while (choose_one != 4);    

    return OK;
}

int main() {
    menu();
    return 0;
}