# Fourth and second work

Which course does this assignment belong to? data structure
where is this job requirement https://edu.cnblogs.com/campus/qdu/DS2020/homework/11296
The goal of this assignment 1. Master the structural characteristics of the stack and its push and pop operations. 2. Master the structural characteristics of the queue and the operations of entering and leaving the queue, and master the characteristics and operations of the circular queue.
student ID 2018204147

## stacks and queues

#### 1. The purpose of the experiment

1. Master the structural characteristics of the stack and its push and pop operations.

2. Master the structural characteristics of the queue and the operations of entering and leaving the queue, and master the characteristics and operations of the circular queue.

#### 2. Pre-experiment

Explain the following concepts:

1. Sequential stack: Sequential stack is the sequential implementation of stack. The sequential stack refers to the stack that uses the sequential storage structure. The sequential stack uses a storage space (array) with consecutive addresses to store the data elements in the stack in turn. Fixed, the stack bottom position can be set at the beginning of the array space. The position of the top of the stack changes with the push and pop operations, so an integer variable Top is needed to record the position of the current stack top element in the array.

2. Chain stack: The chain stack is a chain implementation of the stack. Chained stack is a data storage structure, which can be implemented in the form of a singly linked list. The advantage of using a chained stack is that it can overcome the low space utilization of sequential stacks implemented with arrays, but it needs to be used for each stack element. Allocate additional pointer space for storing pointer fields.

3. Circular queue: The circular queue is to wrap the last position of the queue storage space to the first position to form a logical annular space for the queue to be used for circular use. In the circular queue structure, when the last position of the storage space has been used and the queue operation is to be entered, only the first position of the storage space needs to be free, and the element can be added to the first position, that is, the The first position is the tail of the line. Circular queues can be simpler to prevent false overflows, but the queue size is fixed

4. Chain queue: The chain storage structure of the queue is a linear linked list to represent a queue, each element in the queue corresponds to a link point in the linked list, such a queue is referred to as a linked queue. Specifically, the pointer of the first link point of the linear linked list is defined as the head pointer front, the pointer rear is established at the last link point of the linked list as the tail pointer, and the deletion operation can only be performed at the head of the link. The insertion operation is performed at the tail, and this linear linked list constitutes a linked queue. Another difference from the sequential storage structure queue is that the head pointer and the tail pointer both point to the link point where the actual head element and the tail element are located.

#### 3. Experiment content and requirements

##### 1. Read the program below and complete the function Push and Pop.
```#include<malloc.h>
#define ERROR 0
#define OK 1
#define STACK_INT_SIZE 10 /*Initial allocation of storage space*/
#define STACKINCREMENT 5 /*Storage space allocation increment*/
typedef  int ElemType; /*define the type of the element*/
typedef struct{
ElemType *base;
ElemType *top;
int stacksize;     /*Currently allocated storage space*/
}SqStack;

int InitStack(SqStack *S);   /*construct empty stack*/
int push(SqStack *S,ElemType e); /*push onto the stack*/
int Pop(SqStack *S,ElemType *e);  /*pop*/
int CreateStack(SqStack *S);     /*create stack*/
void PrintStack(SqStack *S);   /*Pop the stack and output the elements on the stack*/

int InitStack(SqStack *S){
S->base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemType));
if(!S->base) return ERROR;
S->top=S->base;
S->stacksize=STACK_INT_SIZE;
return OK;
}/*InitStack*/

int Push(SqStack *S,ElemType e){
if(S->top-S->base>=S->stacksize){

S->base=(ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S->base) return ERROR;
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*S->top++ = e;
return OK;
}/*Push*/

int Pop(SqStack *S,ElemType *e){
if(S->top==S->base) return ERROR;
S->top=--S->top;
*e=*S->top;
return OK;

}/*Pop*/

int CreateStack(SqStack *S){
int e;
if(InitStack(S))
printf("Init Success!\n");
else{
printf("Init Fail!\n");
return ERROR;
}
printf("input data:(Terminated by inputing a character)\n");
while(scanf("%d",&e))
Push(S,e);
return OK;
}/*CreateStack*/

void PrintStack(SqStack *S){
ElemType e;
while(Pop(S,&e))
printf("%3d",e);
}/*Pop_and_Print*/

int main(){
SqStack ss;
printf("\n1-createStack\n");
CreateStack(&ss);
printf("\n2-Pop&Print\n");
PrintStack(&ss);
return 0;
}
```

operation result: Algorithm analysis: input element sequence 1 2 3 4 5, why is the output sequence 5 4 3 2 1? What are the characteristics of the stack?
Since the stack can only perform insertion and output operations at the end of the list, the first element inserted into the stack will be stored at the bottom of the stack and can be output at the end, then the input elements are pushed into the stack in the order of 1 2 3 4 5, and 5 4 3 2 1 pop the stack in order.
This reflects the last-in, first-out nature of the stack.

##### 2. In the program in question 1, write a decimal-to-binary number system conversion algorithm function (requires the use of a stack to implement), and verify its correctness.

Code:

```int conversion(SqStack *S,int a){
while(a){
int e;
e=a%2;
Push(S,e);
a=a/2;
}
}
```
```int main(){
SqStack ss;
int a;
printf("please input the number:",a);
scanf("%d",&a);
InitStack(&ss);
conversion(&ss,a);
PrintStack(&ss);
return 0;
}
```

verify: ##### 3. Read and run the program, and analyze the program function.
```#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define M 20
#define  elemtype  char
typedef struct
{
elemtype stack[M];
int top;
}stacknode;
void init(stacknode *st);
void push(stacknode *st,elemtype x);
void pop(stacknode *st);
void init(stacknode *st)
{
st->top=0;
}

void push(stacknode *st,elemtype x)
{
if(st->top==M)
printf("the stack is overflow!\n");
else
{
st->top=st->top+1;
st->stack[st->top]=x;
}
}

void pop(stacknode *st)
{
if(st->top>0)  st->top--;
else  printf("Stack is Empty!\n");
}

int main()
{
char s[M];
int i;
stacknode *sp;
printf("create a empty stack!\n");
sp=(stacknode*)malloc(sizeof(stacknode));
init(sp);
printf("input a expression:\n");
gets(s);
for(i=0;i<strlen(s);i++)
{
if(s[i]=='(')
push(sp,s[i]);
if(s[i]==')')
pop(sp);
}
if(sp->top==0)
printf("'('match')'!\n");
else
printf("'('not match')'!\n");
return 0;
}
```

Input: 2+((c-d)6-(f-7)a)/6
operation result: Input: a-((c-d)*6-(s/3-x)/2
operation result: The basic function of the program: check whether the use of polynomial brackets is legal, and whether it can find the corresponding ")" for each "("

Which course does this assignment belong to? data structure
where is this job requirement https://edu.cnblogs.com/campus/qdu/DS2020/homework/11213
The goal of this assignment Review the concepts of functions, arrays, pointers, structures and unions in C language, and be familiar with the general methods of programming in C language
student ID 2018204147

## Preliminary experiment ---- C language function array pointer structure knowledge

#### 1. The purpose of the experiment

1. Review the concepts of functions, arrays, pointers, structures and unions in C language.

2. Familiar with the general method of programming using C language.

#### 2. Pre-experiment

Explain the following concepts in c language

1. Function: A function is a group of execution code segments with certain related functions. Input data or operation to the function can get the corresponding result. Functions can simplify the code, provide a means of programming, facilitate the reading and writing of the code, and also facilitate us to maintain and modify the code.

2. Array: An array is a collection of data, each of which is called an array element, and the total number of data is called an array length.

3. Pointer: The pointer is the address number of the memory unit, which should be distinguished from the content of the memory unit. In the C language, a variable is allowed to store the pointer, and this variable is called a pointer variable.

4. Structure: A structure is a self-defined data type that can contain multiple basic data types such as integers, floating-point types, etc. By defining a structure, we do not need to define multiple types of variables. They can all be put into a struct.

5. Union: When programming some algorithms in C language, it is necessary to store several different types of variables in the same memory unit. That is, using the overlay technique, several variables overwrite each other. This structure in which several different variables occupy a piece of memory together is called a "union" type structure in the C language, abbreviated as a union, or a union.

#### 3. Experiment content and requirements

##### 1. Debug program: output all prime numbers within 100 (implemented with functions)

code show as below:

```int isprime(int n){
int m;
for(m=2;m*m<=n;m++)
if(n%m==0) return 0;
return 1;
}
int main(){           /*print all prime numbers up to 100*/
int i; printf("\n");
for(i=2;i<100;i++)
if(isprime(i)==1) printf("%4d",i);
return 0;
}
```

operation result: ##### 2. Debugger: Arrange the elements in a one-dimensional array in reverse order

code show as below:

```#include<stdio.h>
#define N 10
int main(){
int a[N]={0,1,2,3,4,5,6,7,8,9},i,temp;
printf("\nthe original Array is:\n ");
for(i=0;i<N;i++)
printf("%4d",a[i]);
for(i=0;i<N/2;i++){
temp=a[i];
a[i]=a[N-i-1];
a[N-i-1]=temp;
}
printf("\nthe changed Array is:\n");
for(i=0;i<N;i++)
printf("%4d",a[i]);
return 0;
}
```

Output result: ##### 3. Debugging program: In a two-dimensional array, if the element at a certain position is the largest in the row and the smallest in the column, the element is a saddle point of the two-dimensional array. It is required to input a two-dimensional array from the keyboard, and when the saddle point exists, find the saddle point.

code show as below:

```#include<stdio.h>
#define M 3
#define N 4
int main(){
int a[M][N],i,j,k;
printf("\n Please enter the data of the two-dimensional array:\n");
for(i=0;i<M;i++)
for(j=0;j<N;j++)
scanf("%d",&a[i][j]);
for(i=0;i<M;i++){        /*output matrix*/
for(j=0;j<N;j++)
printf("%4d",a[i][j]);
printf("\n");
}
for(i=0;i<M;i++){
k=0;
for(j=1;j<N;j++)    /*Find the maximum value of row i*/
if(a[i][j]>a[i][k])
k=j;
for(j=0;j<M;j++)   /*Determine whether the maximum value of the i-th row is the minimum value of the column*/
if(a[j][k]<a[i][k])
break;
if(j==M)               /*Find saddle point at row i*/
printf("%d,%d,%d\n",a[i][k],i,k);
}
return 0;
}
```

The input and output results are as follows: ##### 4. Debugger: use pointer to output elements of two-dimensional array

Code:

```#include<stdio.h>
int main(){
int a={1,3,5,7,9,11,13,15,17,19,21,23};
int *p;
for(p=a;p<a+12;p++){
if((p-a)%4==0) printf("\n");
printf("%4d",*p);
}
return 0;
}
```

Output result: ##### 5. Debugging program: There is a common table for teachers and students. The teacher's data includes four items: name, age, occupation, and teaching and research office. output

code show as below:

```#include <stdio.h>
#define N 10
struct student{
char name;/*Name*/
int age;    /*age*/
char job;   /*Occupation or profession, use s or t for student or teacher*/
union {
int class1;        /*class*/
char office;  /*Teaching and Research Office*/
}depa;
}stu[N];
int main(){
int i; int n;
printf("\n Please enter the number of people(<10):\n");
scanf("%d",&n);
for(i=0;i<n;i++){  /*Enter the information of n people*/
printf("\n Please enter the%d Personnel Information:(name  age  job  class1/office)\n",i+1);
scanf("%s,%d,%c",stu[i].name, &stu[i].age, &stu[i].job);
if(stu[i].job='s')
scanf("%d",&stu[i].depa.class1);
else
scanf("%s",stu[i].depa.office);
}
printf("name    age    job    class1/office");
for(i=0;i<n;i++){ /*output*/
if(stu[i].job=='s')
printf("%s %3d %3c %d\n",stu[i].name, stu[i].age, stu[i].job, stu[i].depa.class1);
else
printf("%s %3d %3c %s\n",stu[i].name, stu[i].age, stu[i].job, stu[i].depa.office);
}
}
```

Input and output results: #### Fourth, the experimental summary

Through this experiment, I reviewed the concepts of functions, arrays, pointers, structures, and unions in c language. By debugging and running the code of the example, I became familiar with the application of c language structures such as arrays and pointers, and became familiar with the process of program running. . However, the application of pointers is not familiar enough, and there are also great deficiencies in the programming related to pointers. In the next study, you should be more proficient in the writing and use of c language code, and learn and consolidate the unfamiliar and unskilled knowledge.

Posted by arie_parie on Thu, 12 May 2022 09:24:08 +0300