3-1作业

1.东东哥不会做加法运算。需要大家写个程序帮助东东哥进行运算。

要求：输入需要计算的两个整数，之后用链表来存放这两个整数（一个链表存放一个数据，链表

中的每个结点只包含一个数字）。并要求链表需要以逆序的方式存放这些数据。形式如下：

输入：103 286

链表存储为：3->0->1 6->8->2

运算：（3–>0->1） + (6 -> 8-> 2) 即是103 + 286 = 389

请编写相关程序给东东哥使用。

如果数字按照正常的顺序存储在相对应的链表中，那又该如何计算？

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

typedef struct LinkList{
    struct LinkList* next;
    int element;
}node;

node *head1;
node *head2;
node *head3;

void init_node();
void insert(int key,node* head);
void plus_node();
void delete_node(node* head);

int main()
{
    int m,n;
    printf("请输入两个整数:");
    scanf("%d%d",&m,&n);
    init_node();
    insert(m,head1);
    insert(n,head2);
    plus_node();
    printf("%d",print_node(head3));
    return 0;
}

void init_node()
{
    head1=(node*)malloc(sizeof(node));
    head2=(node*)malloc(sizeof(node));
    head3=(node*)malloc(sizeof(node));
    head1->element=0;
    head2->element=0;
    head3->element=0;
 	head1->next=NULL;
    head2->next=NULL;
    head3->next=NULL;
}

void insert(int key,node* head)
{
    node* temp;
    if(key==0)
    {
    	temp=(node*)malloc(sizeof(node));
        temp->element=0;
        temp->next=head->next;
        head->next=temp;
        return;
	}
    while(key>0)
    {
        temp=(node*)malloc(sizeof(node));
        temp->element=key%10;
        key/=10;
        temp->next=head->next;
        head->next=temp;
    }
}

void plus_node()
{
    node* temp1;
    node* temp2;
    int temp=0;
    while(1)
    {
        temp1=head1;
        temp2=head2;
        while(temp1->next!=NULL)
       		temp1=temp1->next;
        while(temp2->next!=NULL)
            temp2=temp2->next;
        if(temp1==head1 && temp2==head2 && temp==0)
        {
            break;
        }
        else
        {
			
            insert((temp1->element+temp2->element)%10+temp,head3);
            if(temp1->element+temp2->element>=10)
			{
				temp=(temp1->element+temp2->element)/10;
			}
			else
			{
				temp=0;
			}
            delete_node(head1);
            delete_node(head2);          
        }
	}
    
}

void delete_node(node* head)
{
    node*temp1=head,*temp2=head;
    while(temp1->next!=NULL)
    {
        temp2=temp1;
        temp1=temp1->next;
    }
    if(temp1!=head)
    {
        temp2->next=temp1->next;
    	free(temp1);
	}
}

int print_node(node *head)
{
    int aim=0;
    node *temp;
    while(head->next!=NULL)
    {
        aim*=10;
        aim+=head->next->element;
        temp=head->next;
        head->next=temp->next;
        free(temp);
    }
    return aim;
}

2.东东哥在出复合计算的数学题目，但是他只有七秒钟的记忆，前一秒写的东西后一秒就忘了。需

要大家写个程序帮助东东哥。帮忙判断一下他出的题目是否是合乎基本的运算法则的。

例子：

东东哥出的题目：((1+2)+3)判断：题目正确

东东哥出的题目：((1+2+3)判断：错误

东东哥出的题目：(1+2+3)+(5+6）判断：题目正确

东东哥出的题目：(1+2+3)+5+6) 判断：错误

#include<stdio.h>
#include<stdlib.h>
#define SIZE 6
int* stack;
int size;
int top;
void init_stack();
void insert_stack();
void delete_stack();
int isEmpty();

int main()
{
    char str[20];
    init_stack();
    scanf("%s",str);
    int i=0;
    while(str[i]!='\0')
    {
        if(str[i]=='(')
        {
            insert_stack();
        }
        else if(str[i]==')')
        {
            delete_stack();
        }
        else
        {
        	
		}
		i++;
	}
    if(isEmpty())
    {
        printf("yes");
    }
    else
        printf("no");
    return 0;
}
void init_stack()
{
    top=-1;
    stack=(int*)malloc(sizeof(int)*SIZE);
    size=SIZE;
}

void insert_stack()
{
    if(top!=size-1)
    	top++;
    else
        return;
}

void delete_stack()
{
    if(top!=-1)
    	top--;
    else
    {
    	printf("no");
    	exit(0);	
	}
    
        return;
        
}

int isEmpty()
{
    if(top==-1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

3. 东东哥听到图灵机跟他说咱们学到队列了。他不信，想让大家实现一个队列。但是他事儿又比较

多，想让大家用栈结构来实现队列。请大家设计一个算法，使用栈来实现队列的操作。

同时他觉得大家都能用栈实现队列了，那用队列实现栈操作应该也是轻而易举的。所以请再书写

一个算法，用队列实现栈。

用栈实现队列

#include<stdio.h>
#include<stdlib.h>
#define SIZE 6
int *stack1;
int *stack2;
int size;
int top1;
int top2;

void init_stack();
void insert(int *stack,int key);
void delete_stack();
void delete();
void isFull();
void isEmpty();

int main()
{
    init_stack();
    insert(stack1,1);
    delete_stack();
    delete();
    return 0;
}

void init_stack()
{
    stack1=(int *)malloc(sizeof(int)*SIZE);
    stack2=(int *)malloc(sizeof(int)*SIZE);
    top1=top2=0;
    size=0;
}

void insert(int *stack,int key)
{
    if(isFull())
    {
        
    }
    else
    {
        stack1[++top1]=key;
        size++;
    }
}

void delete()
{
    if(isEmpty())
    {
        while(top!=-1)
	}
}

void delete_stack()
{
    if(isEmpty())
    {
        
    }
    else
    {
        stack2[++top2]=stack1[top1--];
        size--;
    }
}

void isFull()
{
    if(top==size-1)
    {
        return 1;
	}
    else
        return 0;
}

void isEmpty()
{
    if(top==-1)
    {
        return 1;
    }
    else
        return 0;
}

用队列实现栈

#include<stdio.h>
#include<stdlib.h>
#define SIZE 6

int *queue1;
int *queue2;
int head1;
int end1;
int head2;
int end2;
int size;

void init_queue()
{
    queue1=(int*)malloc(sizeof(int)*SIZE);
    queue2=(int*)malloc(sizeof(int)*SIZE);
    size=0;
    head1=head2=end1=end2=1;
    
}

void insert(int key)
{
    if(isFull())
    {
        
    }
    else
    {
        queue1[head1]=key;
    }
    
}

void delete()
{
    
}

东东哥做了一个员工食堂，但是他比较抠门，只提供了两种食品，分别是烤乳猪和烤兔，烤乳猪

和烤兔分别用数字0和数字1表示。前面也说了，他事儿比较多，又不允许员工自由选择。（食物提供的

数量和员工数量一致）

此时员工在排队，东东哥定下了一个食堂取餐规则：

如果队列最前面的员工喜欢栈顶的食物，那么就会拿走他，并且离开队列。

如果这个员工不喜欢栈顶的食物，那么就放弃食物回到队伍的最后方。

如果队列里的员工都不喜欢栈顶的食物，那么今天的食堂就关门了。爱干啥干啥去‘

输入两组数据，比如:食物 1 1 0 0 （第一个元素是栈顶元素）员工 0 1 0 1 （员工的0和1

代表跟他们喜欢哪种食物）请计算出来没有吃到午餐的员工的数量。比如上述数据返回0 代表全

都能吃到午餐。

#include<stdio.h>
#include<stdlib.h>
#define SIZE 20
#define SIZE 20
int* stack;//栈顶指针
int top;//栈顶下标
int end;//栈底下标
int maxSize1;

int *queue;
int front;
int end;
int maxSize;

void initstack();
void push(int key);
void pull();
void Initqueue();
void insert_queue(int key);
void delete_queue();
int isFull();
int isEmpty();

int main()
{
    int temp=0;
    initstack();
    Initqueue();
    push(1);
    push(0);
    push(0);
    push(0);
    push(1);
    push(0);
    push(1);
    push(0);
    push(0);
    push(0);
    push(1);
    push(0);
    insert_queue(1);
    insert_queue(1);
    insert_queue(1);
    insert_queue(1);
    insert_queue(1);
    insert_queue(1);
    insert_queue(1);
    insert_queue(1);
    
    while(1)
    {
        if(isEmpty())
        {
            temp=0;
            break;
        }
        else
        {
            if(stack[top]==queue[head])
            {
                pull();
                delete_queue();
                temp=0;
            }
            else
            {
                delete_queue();
                insert_queue(end-1);
                temp++;
                if(temp==maxSize)
                {
                    break;
                }
            }
        }
        
    }
    if(temp==0)
    {
        printf("ok");
    }
    else
    {
        printf("close");
    }
}
    
void initstack()
{
    stack=(int*)malloc(sizeof(int)*SIZE);
    end=-1;
    top=-1;
    maxSize1=SIZE;
}

//压栈（入栈）
void push(int key)
{
    //判断栈满
    if(top==maxSize1)
    {
        return;
	}
    else
    {
        top++;
        stack[top]=key;
    }
}

//出栈
void pull()
{
    if(top==-1)
    {
        return;
	}
    else
    {
        top--;
    }
}

void Initqueue()
{
    queue=(int *)malloc(sizeof(int)*SIZE);
    maxSize=SIZE;
    front=end=0;
}

void insert_queue(int key)
{
    if(isFull())
    {
        return;
	}
    else
    {
        end=(end+1)%maxSize;
        queue[end]=key;
    }
}

void delete_queue()
{
    if(isEmpty())
    {
        return;
	}
    else
    {
        front=(front+1)%maxSize;
        
    }
    
}

int isFull()
{
    if((end+1)%maxSize==front)
    {
        return 1;
	}
    else
        return 0;
}

int isEmpty()
{
    if(end==front)
    {
        return 1;
	}
    else
        return 0;
}

前面说到，东东哥事儿比较多，他看到员工排队，觉得排队排的不好，他想要改变员工的站位。

他让第一个和第二个员工交换位置，第三个和第四个员工交换位置，依次类推。

要求：用单链表实现操作，并且不能改变结点的值。只允许移动结点。

比如 1-> 2 -> 3 -> 4 改变完以后 2 -> 1 -> 4 -> 3

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

typedef struct Linklist{
    struct Linklist * next;
    struct Linklist * front;
    int element;
}Node;

Node* head;
Node* end;

void init_Node();
void insert(int key);
void change();

int main()
{
    init_Node();
    insert(1);
    insert(2);
    insert(3);
    insert(4);
    change();
}

void init_Node()
{
    head=(Node*)malloc(sizeof(Node));
    end=(Node*)malloc(sizeof(Node));
    head->next=end;
    end->front=next;
    head->front=NULL;
    end->front=NULL;
    head->element=0;
}

void insert(int key)
{
    Node* temp;
    temp=(Node*)malloc(sizeof(Node));
    temp->element=key;
    temp->next=head->next;
    temp->front=head;
    head->next=temp;
    temp->next->front=temp;
    head->element++;
}

void change()
{
    Node* temp=head->next;
    for(int i=0;i<element/2;i++)
    {
        temp->next->front=temp->front;
        temp->front->next=temp->next;
        temp->next=temp->next->next;
        temp->front=temp->next->front;
        temp->front->next=temp;
        temp=temp->next
    }
    
}

发布于 2024-11-10