-
Experimental purpose
Master the abstract data types of stack and queue, and be able to correctly select them in corresponding application problems, Master the implementation methods of stack and queue (sequential and chained), the implementation algorithms of two storage structures and basic operations, pay attention to the judgment conditions of empty and full and their description methods, master the differences and solutions between the implementation of circular queue and other sequential structures, and be familiar with the implementation of the basic operations of various queues on circular queue
-
Experimental content
(1) Checking of bracket matching with stack
(2) Using stack to realize shape a+b@b+a #Test of centrosymmetric character sequences.
(3) Implement with queue, as shown in a+b@b+a #Test of centrosymmetric character sequences
Select the appropriate storage structure (sequential stack or chain stack) to represent the stack, give its definition, and realize the basic operations of the stack on the above storage structure: initialization, stack empty, stack in, stack out, stack top element, etc. select the appropriate storage structure (cyclic queue) refers to the queue, which solves the contradiction between the same judgment conditions of empty and full queue, realizes the basic operation of the storage structure based on cyclic queue, initialization, empty / full judgment, queue entry, queue exit, take the queue header element, calculate the queue length, etc., and analyzes the time complexity of the written algorithm
- Data structure definition
(describe the definition of data structure and data type used in your algorithm)
Stack:
ADT Stack {
Data object: D={ai| ai Î ElemSet, i=1,2,..., n, n ³ 0}
Data relationship: R1 = {< ai-1, ai > | ai-1, ai Î D, i=2,..., n}
& basic operations: InitStack, destroystack
ClearStack(&S), StackEmpty(S)
StackLength(&S), GetTop(S, &e)
Push(&S, e), Pop(&S, &e)
StackTraverse(s, visit())
} ADT Stack
Queue:
ADT Queue {
Data object: D={ai | ai Î ElemSet, i=1,2,..., N, n > = 0}
Data relationship: R1 = {< AI-1, AI > | AI-1, AI Î D, i=1,2,..., n}
Basic operations: initqueue (& Q), destroyqueue (& Q)
ClearQueue(&Q) , QueueEmpty(Q)
QueueLength(Q), Gethead(Q, &e)
EnQueue(&Q, e), DeQueue(&Q, &e)
QueueTraverse(Q, Visit())
}ADT Queue
- Algorithm idea and algorithm design
(first explain the idea of the algorithm in words, and then give the C-like language algorithm)
1,
The bracket problem can be used to solve the matching problem of "{" and "}" in C language. It can be observed that if a string is scanned from left to right, each right bracket will match the unmatched left bracket encountered recently. In the scanning project from left to right, the encountered left bracket is stored in the stack. Whenever a right bracket is encountered, It is matched with the left parenthesis at the top of the stack (if any), and the left parenthesis is deleted from the top of the stack.
2,
First put the characters before the @ symbol on the stack, and then compare them with the characters after @ one by one.
void match()
{ InitStack(S);
printf("input with #:");
c=getchar();
while (c!='@')
{ push(S,c);
c=getchar();
}
c=getchar();
while (c!='#'&&!StackEmpty(S))
{ x=Pop(S,x);
if (c==x) c=getchar();
else { printf("not match\n"); return; }
}
if (c=='#' && StackEmpty(S)) printf("match");
else printf("not match");
}Experimental code
(i.e. C language program)
1,
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
char * base;
char * top;
int stacksize;
}stack;
void initstack(stack*s)//Initialization function of stack
{
s->base = (char*)malloc(sizeof(char));
if (!s->base)//Check whether the memory allocation is successful
{
exit(0);
}
s->base = s->top;
s->stacksize = 10;
}
void push(stack*s, char x)//Stack function
{
if (s->top - s->base >= s->stacksize)//Check whether overflow occurs first
{
s->base = (char*)realloc(s->base, (s->stacksize + 10) * sizeof(char));//If it happens, add 10 memory spaces (dynamic expansion)
if (!s->base)//Check whether the memory allocation is successful
{
exit(0);
}
s->stacksize = s->stacksize + 10;
s->top = s->base + 10;
}
*s->top = x;
s->top++;
}
int main()
{
stack * s = (stack*)malloc(sizeof(stack));
initstack(s);
char c;
printf("Please enter a test case (e.g{[]()}#,#Flag input end): ");
c=getchar();
push(s,c);
while (c != '#')
{
c=getchar();
if (c == '{'||c == '('||c == '[')
{
push(s, c);
}
if (c == '}'||c == ')'||c == ']')
{
if (s->base == s->top)
{
push(s, c);
}
if (c == '}')
{
if (*--(s->top) == '{')//As explained here, * -- (s - > top) is obviously the top element of the stack, but this operation has implemented top--. The pop function is realized in a disguised form. Therefore, in fact, the elements in the stack are not deleted, but the top pointer is moved to continuously overwrite the elements.
{
//top -- has been implemented. No operation is required here
}
else
{
push(s, c);
}
}
if (c == ')')
{
if (*--(s->top) == '(')
{
}
else
{
push(s, c);
}
}
if (c == ']')
{
if (*--(s->top) == '[')
{
}
else
{
push(s, c);
}
}
}
}
if (s->base == s->top)
{
printf("Bracket matching succeeded");
}
else
{
printf("Bracket matching failed");
}
return 0;
}2,
#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OK 1
#define OVERFLOW 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int Status;
typedef char SElemType;
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
} SqStack;
Status InitStack(SqStack *S) {
//Construct an empty stack, which is indicated by a pointer
S->base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));//Continuous space allocation of stack
if (!S->base)
exit(OVERFLOW);//Storage allocation failed
S->top = S->base;//Empty stack, initialize stack top pointer
S->stacksize = STACK_INIT_SIZE;
return OK;
}
Status Push(SqStack *S, SElemType e) {
//Insert element e as the new top of the stack
if (S->top - S->base >= S->stacksize) {
//Stack full, additional storage space
S->base = (SElemType*)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType));
if (!S->base)
exit(OVERFLOW);
S->top = S->base + S->stacksize;
S->stacksize += STACKINCREMENT;
}
*S->top = e;
S->top++;
return OK;
}
Status Pop(SqStack *S) {
//If the stack is not empty, delete the top element of S, return its value with e, and return OK; otherwise, return ERROR;
if (S->top == S->base)
{
printf("Stack empty");
return ERROR;
}
return *--S->top;//--S->top; e=*S->top;
}
SElemType GetTop(SqStack *S) {
//If the stack is not empty, delete the top element of S and return OK; otherwise, return error
if (S->top = S->base)
{
// printf("stack empty");
return ERROR;
}
return *(S->top - 1);//Get stack top element
}
Status StackEmpty(SqStack *S) {
if (S->top == S->base)
{
//printf("stack empty");
return TRUE;
}
else
{
// printf("stack is not empty");
return FALSE;
}
}
Status Match(SqStack *S) {
char c, x;
c = getchar();
while (c != '@') {
Push(S, c);
c = getchar();
}
c = getchar();
while (c != '@' && !StackEmpty(S)) { //c is not equal to the centrosymmetric mark '@', and the S stack cannot be empty
x = Pop(S);
if (c == x)
c = getchar();
else {
printf("not match\n");
return ERROR;
}
}
if (c == '#'& & stackempty (s)) / / in order to solve the problem, the first half is indeed matched, but the part behind "@" exceeds the length of the front part
{
printf("match!\n");
return OK;
}
else
{
printf("not match\n");
return ERROR;
}
}
int main()
{
SqStack S;
InitStack(&S);
printf("Please enter the character sequence. The center of symmetry is'@'，with'#'end! \n");
Match(&S);
system("pause");
return 0;
}3,
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0
#define OVERFLOW 0
#define MAXQSIZE 100
typedef int Status;
typedef char QElemType;
typedef struct {
QElemType *base;
int front;//Points to the first element of the queue
int rear;//The next element that points to the last element of the queue
} SqQueue;
Status InitQueue(SqQueue *Q) {
//Construct an empty queue Q
Q->base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));//
if (!Q->base)
exit(OVERFLOW);//Storage allocation failed
Q->front = Q->rear = 0;//Initialize header pointer
return OK;
}
Status EnQueue(SqQueue *Q, QElemType e) {
//Insert element e as the new tail element of Q
if ((Q->rear + 1) % MAXQSIZE == Q->front)//Queue full
return ERROR;
Q->base[Q->rear] = e;//Save the queued data at the position indicated by the header pointer. In fact, it is not a real pointer, but to facilitate the saving of elements
Q->rear = (Q->rear + 1) % MAXQSIZE;//The tail pointer moves forward one bit
return OK;
}
Status DeQueue(SqQueue *Q, QElemType *e) {
//If the queue is not empty, delete the queue header element of Q, return its value with e, and return OK; otherwise, return ERROR
if (Q->front == Q->rear)//Queue full
return ERROR;
*e = Q->base[Q->front];//When out of the queue, the queue header element goes out first
Q->front = (Q->front + 1) % MAXQSIZE;//The head pointer moves forward one bit
return OK;
}
Status DeQueue_rear(SqQueue *Q, QElemType *e) {
//If the queue is not empty, delete the tail element of Q, return its value with e, and return OK; otherwise, return ERROR
if (Q->front == Q->rear)//Queue full
return ERROR;
Q->rear = (Q->rear - 1) % MAXQSIZE;//The end of queue pointer always points to the position of the next element of the last element. Therefore, when deleting the end of queue element, first move the pointer one bit forward
*e = Q->base[Q->rear];//Then take out the element
return OK;
}
Status QueueEmpty(SqQueue Q) {
if (Q.front == Q.rear)
return TRUE;
else
return FALSE;
}
int QueueLength(SqQueue Q) {
//Returns the number of elements in Q, that is, the length of the queue
return(Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}
Status Match(char*a) {
char c, b;
char*p; //Define character pointer variable p
p = a;//Assign the first address of the string array to p
SqQueue Q;//Define queue Q
InitQueue(&Q);//Initialize queue Q
while (*p != '@') {//p the element value currently referred to is not a token of a symmetric center character
EnQueue(&Q, *p);//Put the character indicated by p in the queue
p++;//The p pointer points to the next character
}
p++;//Skip the symmetry center sign @, and keep him out of the queue
while (*p != '#'{/ / p the character currently referred to is not the end of the queue
EnQueue(&Q, *p);//Continue to queue
p++;// p pointer backward
}
while (QueueLength(Q) != 0)
{//The condition of the loop is that the queue is not empty, and the characters are deleted from the tail and head of the queue for comparison
if (!DeQueue(&Q, &b))//Take out the team head element and check whether it can be taken successfully
return OVERFLOW;
if (!DeQueue_rear(&Q, &c))//Take out the tail element and check whether it can be taken successfully
return OVERFLOW;
//If the team leader is not zero, compare the team head element with the team tail element
if (b != c) //If a pair of characters at the beginning and end of the queue do not match, it proves that the string is not centrosymmetric
{
printf("Not a centrosymmetric character sequence!\n");
return FALSE;
}
}
if (Q.rear == Q.front)//When the two pointers to delete characters from the head and tail of the queue meet, it means that their previous characters have been successfully matched
printf("Is a centrosymmetric character sequence!");
return OK;
}
int main() {
char a[100];//Define character array
printf("Please enter the character sequence to verify,with#As an end sign! \n");
gets(a);//Receive string
Match(a);//The array name is used as an argument to pass the address of the first element of the array to the formal parameter
system("pause");
return 0;
}- Algorithm test results
(explain the test data and paste the experimental result diagram)
Experimental data: {([])} ({}])
- Analysis and summary
(1) algorithm complexity analysis, advantages and disadvantages analysis
(explain the complexity of the algorithm you write, and what are the advantages and disadvantages of the algorithm)
Input a string of characters into the stack one by one. After knowing the occurrence of the identifier @ and then out of the stack in turn, compare them with the characters after the identifier one by one. The basic statement is the process of stack in and out comparison, and its time complexity is O (n)
(2) experimental summary
(explain how you solved the problems encountered in the experiment and what you gained)
Through this experiment, I can skillfully master the abstract data types of stack and queue, and correctly select them in the corresponding application problems, Master the implementation methods of stack and queue (sequential and chained), the implementation algorithms of two storage structures and basic operations, pay attention to the judgment conditions of empty and full and their description methods, master the differences and solutions between the implementation of circular queue and other sequential structures, and be familiar with the implementation of the basic operations of various queues on circular queue.