swust oj(数据结构前40)

博主码风太丑，勿喷。
由于据说数据结构考试必须强行用学的这些数据结构，所以都老老实实写的。用数组模拟的代码有时间再写了

有的题数据输出格式改了，PE的题请在下面评论区留言。不懂的也可以在下面留言，可能会解答。
数据结构后40

---

[941] 有序顺序表的合并操作的实现

• 思路
• 题目描述
• 顺序表实现
• 数组模拟实现

每次比较两个序列的前两个，选小的放入c，详见代码。

传送门

描述

已知两非递减的顺序线性表，要求合并成一个新的非递减顺序线性表。(测试数据为整型)

输入

输入包含四行，第一行为自然数n，表示第一个非递减顺序线性表的长度;
第二行为n个自然数构成的非递减顺序线性表;
第三行为自然数m，表示第二个非递减顺序线性表的长度;
第四行为m个自然数构成的非递减顺序线性表。

输出

输出：用一行输出合并后的非递减顺序线性表，各数之间用一个空格隔开。

样例输入

2
1 3
3
2 3 6

样例输出

1 2 3 3 6

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll;
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7;

typedef struct {
    int date[100];
    int len;
} SqList;

void Create (SqList *&L) {
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>L->date[i];
    L->len=n;
}

void Merge(SqList *&La,SqList *&Lb,SqList *&Lc) { //把AB合成放在C里
    int ia=0,ib=0,ic=0;
    while(ia<La->len&&ib<Lb->len)
        Lc->date[ic++]= La->date[ia] <= Lb->date[ib]? La->date[ia++]:Lb->date[ib++]; //三目运算，就是找date[ia]和date[ib]小的放进C

    while(ia<La->len) Lc->date[ic++]=La->date[ia++]; //如果B数组放完了，就把A数组剩下的放进去。

    while(ib<Lb->len) Lc->date[ic++]=Lb->date[ib++]; //如果A数组放完了，就把B数组剩下的放进去。

    Lc->len=La->len+Lb->len;        //长度相加
}

void Put(SqList *&La) {
    for(int i=0; i<La->len; i++)
        cout<<La->date[i]<<" ";
}

int main() {
    SqList *La,*Lb,*Lc;
    La=(SqList *) malloc(sizeof(SqList));
    Lb=(SqList *) malloc(sizeof(SqList));
    Lc=(SqList *) malloc(sizeof(SqList));

    Create(La);
    Create(Lb);
    Merge(La,Lb,Lc);
    Put(Lc);
    return 0;
}

敬请期待…

---

[942] 逆置顺序表

• 思路
• 题目描述
• 顺序表实现
• 数组模拟实现

…

传送门

描述

建立长度为n的顺序表，然后将表中的数据元素逆置，即若表中原来的数据元素序列为（a0，a1，a2，…，an），则逆置后的数据元素序列为（an，an-1，an-2，…，a1，a0）。（数据类型为字符型）

输入

第一行为顺序表的长度n；
第二行为顺序表中的数据元素.

输出

输出为逆置后的顺序表.

样例输入

7
ABCDEFG

样例输出

G F E D C B A

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct 
{
    char date[100];
    int len;
} SqList;

void Create (SqList *&L)
{
    int n;
    cin>>n;
    getchar();
    for(int i=0;i<n;i++)
        scanf("%c",&L->date[i]);
    L->len=n;
}

void Put(SqList *&La)
{
    for(int i=La->len-1;i>=0;i--)
        cout<<La->date[i]<<" "; 
}

int main()
{
    SqList *La;
    La=(SqList *) malloc(sizeof(SqList));
    
    Create(La);
    Put(La);
    return 0;
}

敬请期待…

---

[943] 顺序表插入操作的实现

• 思路
• 题目描述
• 顺序表实现
• 数组模拟实现

插入到位置i就要把i及以后的元素都后移一个，再插入。

传送门

描述

建立长度为n的顺序表，在指定的数据元素item之前插入数据元素data。如果指定的数据元素item不存在，则将data插入到顺序表的尾端。（数据类型为整型）

输入

第一行为顺序表的长度n；
第二行为顺序表中的数据元素；
第三行为指定的数据元素item；
第四行为要插入的数据元素data；

输出

顺序表中的数据元素。

样例输入

10
10 20 30 40 50 60 70 80 90 100
50
55

样例输出

10 20 30 40 55 50 60 70 80 90 100

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct 
{
    int date[100];
    int len;
} SqList;

void Create (SqList *&L)
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>L->date[i];
    L->len=n;
}

void Put(SqList *&La)
{
    for(int i=0;i<La->len;i++)
        cout<<La->date[i]<<" "; 
}

void Insert(SqList *&La,int add,int x)
{
    int Flag=0;
    while(La->date[Flag]!=add&&Flag<La->len) Flag++;
    
    if(Flag==La->len)
    {
        La->date[Flag]=x;
    }
    else
    {
        int i=La->len-1;
         while(Flag<=i&&i>=0)
        {
            La->date[i+1]=La->date[i];
            i--;
        }
        La->date[i+1]=x;
    }        
    La->len++;
 } 

int main()
{
    SqList *La;
    La=(SqList *) malloc(sizeof(SqList));
    
    Create(La);
    
    int a,b;
    cin>>a>>b;
    Insert(La,a,b);
    Put(La);
    return 0;
}

敬请期待…

---

[952] 单链表的插入操作的实现

• 思路
• 题目描述
• 单链表实现
• 数组模拟实现

基操

传送门

描述

建立长度为n的单链表，在第i个结点之前插入数据元素data。

输入

第一行为自然数n，表示链式线性表的长度；
第二行为n个自然数表示链式线性表各元素值；
第三行为指定插入的位置i；第四行为待插入数据元素data。

输出

指定插入位置合法时候，输出插入元素后的链式线性表的所有元素，元素之间用一个空格隔开。输入不合法，输出”error!”。

样例输入

5
1 2 3 4 5
3
6

样例输出

1 2 6 3 4 5

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct node 
{
    int data;
    node *next;
} LinkNode;

void Create (LinkNode *&Head,int n)
{
    Head=(LinkNode *)malloc(sizeof(LinkNode));
    LinkNode *p1,*p2;
    p1=p2=Head;
    for(int i=0;i<n;i++)
    {
        p1=(LinkNode *)malloc(sizeof(LinkNode));
        cin>>p1->data;
        if(i==0) Head->next=p1;
        p2->next=p1;
        p2=p1;
    }
    p2->next=NULL;
}

void Put(LinkNode *Head)
{ 
    LinkNode *p1=Head->next;
    while(p1!=NULL)
    {
        cout<<p1->data<<" ";
        p1=p1->next;
    }
}

void Insert(LinkNode *&Head,int add,int x)
{
    LinkNode *p1=Head,*tem;
    
    for(int i=1;i<add;i++)
        p1=p1->next;
    
    tem=(LinkNode *)malloc(sizeof(LinkNode));
    tem->data=x;
    tem->next=p1->next;
    p1->next=tem;
}

int main()
{
    LinkNode *Head;
    
    int len;
    cin>>len;
    Create(Head,len);
    int a,b;
    cin>>a>>b;
    if(a<=0||a>len) cout<<"error!";
    else
    {
        Insert(Head,a,b);
        Put(Head);
    }
    return 0;
}

敬请期待…

---

[953] 单链表的删除操作的实现

• 思路
• 题目描述
• 单链表实现
• 数组模拟实现

基操

传送门

描述

建立长度为n的单链表，删除第i个结点之前的结点。

输入

第一行为自然数n，表示链式线性表的长度；
第二行为n个自然数表示链式线性表各元素值；
第三行为指定的删除参数i。

输出

指定删除位置合法时候，输出删除元素后的链式线性表的所有元素，元素之间用一个空格隔开。
输入不合法，输出”error!”。

样例输入

5
1 2 3 4 5
3
6

样例输出

1 3 4 5

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct node 
{
    int date;
    node *next;
} LinkNode;

void Create (LinkNode *&Head,int n)
{
    Head=(LinkNode *)malloc(sizeof(LinkNode));
    LinkNode *p1,*p2;
    p1=p2=Head;
    for(int i=0;i<n;i++)
    {
        p1=(LinkNode *)malloc(sizeof(LinkNode));
        cin>>p1->date;
        if(i==0) Head->next=p1;
        p2->next=p1;
        p2=p1;
    }
    p2->next=NULL;
}

void Put(LinkNode *Head)
{
    LinkNode *p1=Head->next;
    while(p1!=NULL)
    {
        cout<<p1->date<<" ";
        p1=p1->next;
    }
}

void Delete(LinkNode *&Head,int x)
{
    LinkNode *p1=Head,*tem;
    
    for(int i=0;i<x-2;i++)
        p1=p1->next;
    
    p1->next=p1->next->next;
}

int main()
{
    LinkNode *Head;
    
    int len;
    cin>>len;
    Create(Head,len);
    int x;
    cin>>x;
    if(x<=1||x>len) cout<<"error!";
    else
    {
        Delete(Head,x);
        Put(Head);
    }
    return 0;
}

敬请期待…

---

[954] 单链表的链接

• 题目链接
• 题目描述
• 单链表实现
• 数组模拟实现

传送门

描述

建立长度为n的单链表A和长度为m的单链表B。编程实现将B表链接在A表的尾端，形成一个单链表A。数据类型指定为字符型。

输入

第一行为A表的长度n；
第二行为A表中的数据元素;
第三行为B表的长度m；
第四行为B表中的数据元素。

输出

输出为链接好后的A表中的所有数据元素。

样例输入

4
A B C D 
6
1 2 3 4 5 6

样例输出

A B C D 1 2 3 4 5 6

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct node 
{
    char date;
    node *next;
} LinkNode;

void Create (LinkNode *&Head)
{
    int n;
    cin>>n;
    Head=(LinkNode *)malloc(sizeof(LinkNode));
    LinkNode *p1,*p2;
    p1=p2=Head;
    for(int i=0;i<n;i++)
    {
        p1=(LinkNode *)malloc(sizeof(LinkNode));
        getchar();
        scanf("%c",&p1->date);
        if(i==0) Head->next=p1;
        p2->next=p1;
        p2=p1;
    }
    p2->next=NULL;
}

void Put(LinkNode *Head)
{
    LinkNode *p1=Head->next;
    while(p1!=NULL)
    {
        cout<<p1->date<<" ";
        p1=p1->next;
    }
}

void Merge(LinkNode *&Head1,LinkNode *&Head2)
{
    LinkNode *p1=Head1;
    while(p1->next!=NULL)
        p1=p1->next;
    
    p1->next=Head2->next;
}

int main()
{
    LinkNode *Head1,*Head2;
    
    Create(Head1);
    Create(Head2);
    Merge(Head1,Head2);
    Put(Head1);
    return 0;
}

敬请期待…

---

[955] 单链表上查找算法的实现

• 思路
• 题目描述
• 单链表实现
• 数组模拟实现

遍历大法好

传送门

描述

建立一个长度为n的带头结点的单链表，在该表中寻找第i个结点，若找到，则输出ok，否则输出error。处理数据类型为整型。

输入

第一行为链表的长度n；
第二行为链表中的数据元素；
第三行为要找的结点i。

输出

找到就输出ok，没找到就输出error。

样例输入

10
1 2 3 4 5 6 7 8 9 10
5

样例输出

ok

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct node 
{
    int date;
    node *next;
} LinkNode;

void Create (LinkNode *&Head,int n)
{
    Head=(LinkNode *)malloc(sizeof(LinkNode));
    LinkNode *p1,*p2;
    p1=p2=Head;
    for(int i=0;i<n;i++)
    {
        p1=(LinkNode *)malloc(sizeof(LinkNode));
        cin>>p1->date;
        if(i==0) Head->next=p1;
        p2->next=p1;
        p2=p1;
    }
    p2->next=NULL;
}

int main()
{
    LinkNode *Head;
    
    int len;
    cin>>len;
    Create(Head,len);
    
    int n;
    cin>>n;
     
    n<1||n>len? cout<<"error":cout<<"ok";
    
    return 0;
}

敬请期待…

---

[956] 约瑟夫问题的实现

• 思路
• 题目描述
• 循环链表实现
• 数组模拟实现

用循环链表，每次数到k就删除这个节点

传送门

描述

n个人围成一个圈，每个人分别标注为1、2、…、n，要求从1号从1开始报数，报到k的人出圈，接着下一个人又从1开始报数，如此循环，直到只剩最后一个人时，该人即为胜利者。例如当n=10,k=4时，依次出列的人分别为4、8、2、7、3、10，9、1、6、5，则5号位置的人为胜利者。给定n个人，请你编程计算出最后胜利者标号数。（要求用单循环链表完成。）

输入

第一行为人数n;
第二行为报数k。

输出

输出最后胜利者的标号数。

样例输入

10
4

样例输出

5

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct node 
{
    int data;
    node *next;
} LinkNode;

void Create (LinkNode *&Head,int n)
{
    LinkNode *p1,*p2;

    p1=(LinkNode *)malloc(sizeof(LinkNode));
    Head=p1;p2=p1;
    p1->data=n;
    for(int i=1;i<n;i++)
    {
        p1=(LinkNode *)malloc(sizeof(LinkNode));
        p1->data=i;
        p2->next=p1;
        p2=p1;
    }
    p2->next=Head;
}

void Work(LinkNode *Head,int n,int k)
{
    LinkNode *p1=Head;
    while(n!=1)
    {
        for(int i=1;i<k;i++)
          p1=p1->next;
          //cout<<p1->next->data<<",";
        p1->next=p1->next->next;
        n--; 
    }
    cout<<p1->data;
}

int main()
{
    LinkNode *Head;
    
    int n,k;
    cin>>n>>k;
    Create(Head,n);
    Work(Head,n,k);
    return 0;
}

敬请期待…

---

[957] 逆置单链表

• 思路
• 题目描述
• 单链表实现
• 数组模拟实现

头插法重新建立单链表

描述

传送门

建立长度为n的单链表，然后将其数据元素逆置，即第1个元素变为最后一个元素，第2个元素变为倒数第2个元素，以此类推，最后一个元素变为第1个元素。（处理的数据类型为字符型。必须使用链表完成。）

输入

第一行为链表长度n；
第二行为链表中的n个数据元素的值。

输出

逆置后的原始的值。

样例输入

10
ABCDEFGHIJ

样例输出

J I H G F E D C B A

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct node 
{
    char data;
    node *next;
} LinkNode;

void Create (LinkNode *&Head,int n)
{
    LinkNode *p1,*p2;
    p1=(LinkNode *)malloc(sizeof(LinkNode));
    getchar();
    scanf("%c",&p1->data);
    Head=p2=p1;
    
    for(int i=0;i<n;i++)
    {
        p1=(LinkNode *)malloc(sizeof(LinkNode));
        scanf("%c",&p1->data);
        p2->next=p1;
        p2=p1;
    }
    p2->next=NULL;
}

void Put(LinkNode *Head)
{
    LinkNode *p1=Head;
    while(p1!=NULL)
    {
        cout<<p1->data<<" ";
        p1=p1->next;
    }
}

void Reverse(LinkNode *&Head,int n)
{
    LinkNode *p1=Head->next,*p2=p1->next;
    Head->next=NULL; 
    for(int i=1;i<n;i++)
    {
        p1->next=Head;
        Head=p1;
        p1=p2;
        p2=p2->next;
    }
}

int main()
{
    LinkNode *Head;
    
    int len;
    cin>>len;
    Create(Head,len);
    Reverse(Head,len);
    Put(Head);
    return 0;
}

敬请期待…

---

[960] 双向链表的操作问题

• 思路
• 题目描述
• 双向链表实现
• 数组模拟实现

每次读入新节点就遍历一遍，然后找到合适的位置插进去。

传送门

描述

建立一个长度为n的带头结点的双向链表，使得该链表中的数据元素递增有序排列。（必须使用双向链表完成，数据类型为整型。）

输入

第一行：双向表的长度；
第二行：链表中的数据元素。

输出

输出双向链表中的数据元素的值。

样例输入

10
2 4 6 3 5 8 10 21 12 9

样例输出

2 3 4 5 6 8 9 10 12 21

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct node 
{
    int data;
    node *pre;
    node *next;
} DLinkNode;

void Create (DLinkNode *&Head,int n)
{
    int x;
    DLinkNode *p1,*p2;
    p1=(DLinkNode *)malloc(sizeof(DLinkNode));
    Head=p2=p1;
    Head->pre=NULL;
    Head->next=NULL;
    
    while(n--)
    {
        cin>>x;p1=Head;
        while(p1->next!=NULL&&p1->next->data<=x)
            p1=p1->next;
        
        p2=(DLinkNode *)malloc(sizeof(DLinkNode));
        p2->data=x;
        p2->pre=p1;
        p2->next=p1->next;
        if(p1->next!=NULL)
            p1->next->pre=p2;
        p1->next=p2;
    }
}

void Put(DLinkNode *Head)
{
    DLinkNode *p1=Head->next;
    while(p1!=NULL)
    {
        cout<<p1->data<<" ";
        p1=p1->next;
    }
}

int main()
{
    DLinkNode *Head;
    
    int len;
    cin>>len;
    Create(Head,len);
    Put(Head);
    return 0;
}

敬请期待…

---

[961]进制转换问题

• 思路
• 题目描述
• 链栈实现
• 数组模拟实现

每次把x%2入栈，再x/=2;最后全部出栈。

传送门

描述

建立顺序栈或链栈，编写程序实现十进制数到二进制数的转换。

输入

输入只有一行，就是十进制整数。

输出

转换后的二进制数。

样例输入

10

样例输出

1010

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct linknode
{
    int data;
    linknode *next;
 } LinkStNode;
 
void Init(LinkStNode *&Top)
{
    Top=(LinkStNode *) malloc (sizeof(LinkStNode)); 
    Top->next=NULL;
}

void Push(LinkStNode *&Top,int x)        //入栈
{
    LinkStNode *tem;
    tem=(LinkStNode *) malloc (sizeof(LinkStNode));
    tem->data=x;
    tem->next=Top->next;
    Top->next=tem;
 } 
 
void Pop(LinkStNode *&Top)        //这道题直接写全部出栈 
{
    LinkStNode *tem;
    while(Top->next!=NULL)
    {
        tem=Top->next;
        cout<<tem->data;
        Top=Top->next;
    }
}

int main()
{
    int x;
    cin>>x;
    
    if(!x) cout<<0;
    else
    {
        LinkStNode *Top;
        Init(Top);
        while(x)
        {
            Push(Top,x%2);
            x/=2;
        }
        Pop(Top);
    }
        
    return 0;
}

敬请期待…

---

[962]括号匹配问题

• 思路
• 题目描述
• 链栈实现
• 数组模拟实现

每次读入一个括号就比较是否可以和栈顶的匹配，可以就弹出栈顶元素，否则就把读入的压入栈。

传送门

描述

假设表达式中允许包含两种括号:圆括号和方括号。编写一个算法判断表达式中的括号是否正确配对。

输入

由括号构成的字符串，包含‘(’、‘)’、‘[’和‘]’。

输出

如果匹配输出YES，否则输出NO。

样例输入

[([][]())]

样例输出

YES

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct linknode
{
    char data;
    linknode *next;
 } LinkStNode;
 
void Init(LinkStNode *&Top)
{
    Top=(LinkStNode *) malloc (sizeof(LinkStNode)); 
    Top->next=NULL;
}

void Push(LinkStNode *&Top,char x)        //入栈
{
    LinkStNode *tem;
    tem=(LinkStNode *) malloc (sizeof(LinkStNode));
    tem->data=x;
    tem->next=Top->next;
    Top->next=tem;
 } 
 
void Pop(LinkStNode *&Top)        
{
    LinkStNode *tem;
    tem=Top->next;
    Top->next=Top->next->next;
    free(tem);
}

bool Empty(LinkStNode *&Top)
{
    return (Top->next==NULL);
}

char GetTop(LinkStNode *&Top)
{
    if(Top->next!=NULL) return Top->next->data;
    return '0';
}

int main()
{
    LinkStNode *Top;
    Init(Top);
    char x;
    while(scanf("%c",&x)&&x!='\n')
    {
        if(GetTop(Top)=='['&&x==']'||GetTop(Top)=='('&&x==')')
            Pop(Top);
        else
            Push(Top,x);
    }

    Empty(Top) ? cout<<"YES":cout<<"NO";
    return 0;
}

敬请期待…

---

[963] 小偷的背包

• 思路
• 题目描述
• 链栈dfs实现
• 动态规划实现

每个物品只有拿和不拿两种情况，用dfs（深度优先搜索）解决，时间复杂度
如果用动态规划就只要 O(NV);
01背包详解及优化

传送门

描述

设有一个背包可以放入的物品重量为S，现有n件物品，重量分别是w1，w2，w3，…，wn。问能否从这n件物品中选择若干件放入背包中，使得放入的重量之和正好为S。如果有满足条件的选择，则此背包有解，否则此背包问题无解。

输入

第一行为物品重量S（整数）；
第二行为物品数量n，
第三行为n件物品的重量的序列。

输出

有解就输出”yes!“，没有解就输出”no!“。

样例输入

20
5
1 3 5 7 9

样例输出

yes!

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

int Weight[200],Mark[200],Max,Flag=0,n;

typedef struct linknode
{
    int sum;
    linknode *next;
 } LinkStNode;
 
void Init(LinkStNode *&Top)
{
    Top=(LinkStNode *) malloc (sizeof(LinkStNode)); 
    Top->next=NULL;
    Top->sum=0;
}

int GetTop(LinkStNode *&Top)
{
    if(Top->next!=NULL) return Top->next->sum;
    return 0;
}

void Push(LinkStNode *&Top,int x)        //入栈
{
    LinkStNode *tem;
    tem=(LinkStNode *) malloc (sizeof(LinkStNode));
    tem->sum=x+GetTop(Top);
    tem->next=Top->next;
    Top->next=tem;
 } 
 
void Pop(LinkStNode *&Top)        
{
    LinkStNode *tem;
    tem=Top->next;
    Top->next=Top->next->next;
    free(tem);
}

bool Empty(LinkStNode *&Top)
{
    return (Top->next==NULL);
}

void dfs(LinkStNode *&Top)
{
    if(GetTop(Top)>Max||Flag) return;
    if(GetTop(Top)==Max) {Flag=1;return;}
    for(int i=0;i<n;i++)
    {
        if(!Mark[i])
        {
            Push(Top,Weight[i]);
            Mark[i]=1;
            dfs(Top);
            Mark[i]=0;
            Pop(Top); 
        }
    }
}

int main()
{
    LinkStNode *Top;
    CRL(Mark);
    Init(Top);
    cin>>Max>>n;
    for(int i=0;i<n;i++)
        cin>>Weight[i];
    dfs(Top);
        
    Flag? cout<<"yes!":cout<<"no!";
    
    return 0;
}

#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
using namespace std;
int dp[30005]={0},Time[105]={0},V,n;
int main()
{
    cin>>V>>n;
    for(int i=1;i<=n;i++)
    {
         cin>>Time[i];
    }
    
    for(int i=1;i<=n;i++)
      for(int j=V;j>0;j--)
       if(j>=Time[i])
        dp[j]=max(dp[j],dp[j-Time[i]]+Time[i]);
        
        if(dp[V]==V)
            cout<<"yes!";
        else
            cout<<"no!";
    return 0;
}

---

[964] 数细胞

• 思路
• 题目描述
• 队列实现
• 自己实现

DFS,经典四联通问题。

传送门

描述

一矩形阵列由数字0到9组成，数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。编程需要用到的队列及其相关函数已经实现，你只需要完成count函数以及主函数即可。

输入

第一行输入两个整数，分别代表矩阵的行和列 输入m * n的矩阵，由数字0到9组成。

输出

细胞个数。

样例输入

4 10
1 2 3 4 5 1 1 1 6 7 
1 0 3 4 5 6 1 5 1 0
2 0 4 5 6 6 1 6 7 1
0 0 6 0 6 6 1 0 8 9

样例输出

1

没看懂题目的代码

#include<bits/stdc++.h>
using namespace std;
int sum=0,mapp[100][100],m,n,book[100][100];
void bfs(int x,int y) {
    if(mapp[x][y]&&!book[x][y]) {
        book[x][y]=1;
        bfs(x-1,y);
        bfs(x+1,y);
        bfs(x,y-1);
        bfs(x,y+1);
    }
}
int main() {
    cin>>m>>n;
    for(int i=1; i<=m; i++)
        for(int j=1; j<=n; j++) 
            cin>>mapp[i][j];
        
    
    for(int i=1; i<=m; i++)
        for(int j=1; j<=n; j++)
            if(mapp[i][j]&&!book[i][j]) {
                bfs(i,j);
                sum++;
            }

    cout<<sum;
    return 0;
}

---

[965]循环队列

• 思路
• 题目描述
• 链栈实现
• 数组模拟实现

基操

传送门

描述

描述根据给定的空间构造顺序循环队列，规定队满处理方法为少用一个元素空间。例如，给定5个元素空间构造循环队列，则只能存放4个元素。试根据入队及出队操作判断队列最后的元素存放情况，并输出最后队列中的元素值，即完成给定入队及出列操作后一次性全部出队的元素值。要求采用顺序队列完成，少用一个存储空间的方法区分队列的空和满。
根据给定的空间构造顺序循环队列，规定队满处理方法为少用一个元素空间。例如，给定5个元素空间构造循环队列，则只能存放4个元素。试根据入队及出队操作判断队列最后的元素存放情况，并输出最后队列中的元素值，即完成给定入队及出列操作后一次性全部出队的元素值。要求采用顺序队列完成，少用一个存储空间的方法区分队列的空和满。

输入

输入的第一行为一个自然数n，表示要求构造的顺序循环队列空间数。 第二行为操作次k，接下来k行为出队入队操作，每行各代表一次操作。入队用in表示，出队用out表示，如果是入队，则in隔一空格后为一整数，表示入队元素值。

输出

输出完成所有入队出队操作后，一次性出队元素。用一个空格隔开。可以假定队在完成所有操作后不为空。

样例输入

4
7
in 1
in 2
in 5
in 6
out
out
in 8

样例输出

5 8

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
#define NewNode (SqQueue *)malloc (sizeof(SqQueue))
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7;

struct SqQueue{
    int data[500];
    int front,rear,MaxSize;
};

void Init(SqQueue *&q){
    q=NewNode;
    cin>>q->MaxSize;
    q->front=q->rear=0;
}

bool Empty(SqQueue *&q){
    return (q->front==q->rear);
}

bool Into(SqQueue *&q,int x){
    if((q->rear+1)%q->MaxSize==q->front)
        return false;
    
    q->rear=(q->rear+1)%q->MaxSize;
    q->data[q->rear]=x;
    return true;
}

bool deQueue(SqQueue *&q,int &tem){
    if(q->front==q->rear)
        return false;
    q->front=(q->front+1)%q->MaxSize;
    tem=q->data[q->front];
    return true;
}

int main(){
    SqQueue * q;
    Init(q);
    int n,tem,x;char a[10];
    cin>>n;
    while(n--){
        scanf("%s",a);
        if(a[0]=='i'){
            cin>>x;
            Into(q,x);
        }
        else 
        deQueue(q,tem);
    }
    
    while(deQueue(q,tem))
        cout<<tem<<" "; 
    return 0;
}

敬请期待…

---

[966] 打印杨辉三角形

• 思路
• 题目描述
• 循环队列实现
• 数组模拟实现

每次都从队首去两个，然后把和入队，然后输出，详见代码。

传送门

描述

杨辉三角形具有如下特征：
1、每行数字左右对称，由1开始逐渐变大，然后变小，回到1。
2、第n行的数字个数为n个。
3、第n行数字和为2^(n－1)。
4、每个数字等于上一行的左右两个数字之和。可用此性质写出整个帕斯卡三角形。
5、将第2n+1行第1个数，跟第2n+2行第3个数、第2n+3行第5个数……连成一线，这些数的和是第2n个斐波那契数。将第2n行第2个数，跟第2n+1行第4个数、第2n+2行第6个数……这些数之和是第2n-1个斐波那契数。
6、第n行的第1个数为1，第二个数为1×(n-1)，第三个数为1×(n-1)×（n-2）/2，第四个数为1×(n-1)×（n-2）/2×（n-3）/3…依此类推。例如7阶杨辉三角形如下： 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 要求：利用循环队列，编程实现打印杨辉三角形。（n在0-12之间取值）

输入

输入要打印的杨辉三角形的阶n。

输出

打印出n阶杨辉三角形。

样例输入

7

样例输出

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
#define NewNode (SqQueue *)malloc (sizeof(SqQueue))
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7;

struct SqQueue
{
    int data[500];
    int front,rear,MaxSize;
};

void Init(SqQueue *&q)
{
    q=NewNode;
    q->front=q->rear=0;
    q->MaxSize=500;
}

bool Empty(SqQueue *&q)
{
    return (q->front==q->rear);
}

int GetSum(SqQueue *&q)
{
    return (q->data[q->front+1]+q->data[q->front+2]);
 } 

bool Into(SqQueue *&q,int x)
{
    if((q->rear+1)%q->MaxSize==q->front)
        return false;
    
    q->rear=(q->rear+1)%q->MaxSize;
    q->data[q->rear]=x;
    return true;
}

bool deQueue(SqQueue *&q,int &tem)
{
    if(q->front==q->rear)
        return false;
    q->front=(q->front+1)%q->MaxSize;
    tem=q->data[q->front];
    return true;
}

int main()
{
    SqQueue * q;
    Init(q);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i-2;j++)
        {
            int sum=GetSum(q);
            if(!Into(q,sum)) break;
            int e;
            if(!deQueue(q,e)) break;
        }
        if(Into(q,1))
        {
            for(int j=1;j<=i;j++)
                cout<<q->data[q->front+j]<<" ";
            cout<<endl;
        }
    }
    return 0;
}

敬请期待…

---

[971] 统计利用先序遍历创建的二叉树的深度

• 思路
• 题目描述
• 二叉树实现
• 只用一个变量实现

递归查找，从一个节点开始向下最深的深度就是deep(i)=1+max(deep(左儿子),deep(右儿子))。

描述

传送门

利用先序递归遍历算法创建二叉树并计算该二叉树的深度。先序递归遍历建立二叉树的方法为：按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符”#”时表示该结点不需要创建，否则创建该结点。最后再统计创建完成的二叉树的深度（使用二叉树的后序遍历算法）。需要注意输入数据序列中的”#”字符和非”#”字符的序列及个数关系，这会最终决定创建的二叉树的形态。

输入

输入为先序遍历二叉树结点序列。

输出

对应的二叉树的深度。

样例输入

A##
ABC####
AB##C## 
ABCD###E#F##G## 
A##B##

样例输出

1
3
2
4
1

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define NewNode (TreeNode *) malloc (sizeof(TreeNode))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct node
{
    char data;
    node *Lchild,*Rchild;
} TreeNode;

TreeNode *Built()
{
    TreeNode *T;
    char ch;
    cin>>ch;
    if(ch=='#')
        T=NULL;
    else
    {
        T=NewNode;
        T->data=ch;
        T->Lchild=Built();
        T->Rchild=Built();
    }
    return T;
}

int Deep(TreeNode *&Tem)
{
    if(Tem==NULL) return 0;
    return 1+max(Deep(Tem->Lchild),Deep(Tem->Rchild));
}

int main()
{
    TreeNode *Root;
    Root=Built();
    cout<<Deep(Root);
    return 0;
}

#include<bits/stdc++.h>
using namespace std; 

char x;
int slove()
{
    if(scanf("%c",&x)&&x=='#') return 0;
    return 1+max(slove(),slove());
 } 

int main()
{
    cout<<slove();
    return 0;
}

---

[972] 统计利用先序遍历创建的二叉树的宽度

• 思路
• 题目描述
• 二叉树实现
• 简单写法

跟上题差不多

传送门

描述

利用先序递归遍历算法创建二叉树并计算该二叉树的宽度。先序递归遍历建立二叉树的方法为：按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符”#”时表示该结点不需要创建，否则创建该结点。最后再统计创建完成的二叉树的宽度（是指二叉树每层节点数的最大值）。需要注意输入数据序列中”#”字符和非”#”字符的序列及个数关系，这会最终决定创建的二叉树的形态。

输入

输入为接受键盘输入的由大写英文字符和”#”字符构成的一个字符串（用于创建对应的二叉树）。

输出

输出该用例对应的二叉树的宽度。

样例输入

A##
ABC####
AB##C##
ABCD###EF##G###
A##B##

样例输出

1
1
2
3
1

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define NewNode (TreeNode *) malloc (sizeof(TreeNode))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

int Count[100]={0},Max=0;

typedef struct node
{
    char data;
    node *Lchild,*Rchild;
} TreeNode;

TreeNode *Built()
{
    TreeNode *T;
    char ch;
    cin>>ch;
    if(ch=='#')
        T=NULL;
    else
    {
        T=NewNode;
        T->data=ch;
        T->Lchild=Built();
        T->Rchild=Built();
    }
    return T;
}

void Num(TreeNode *&T,int i)
{
    if(T!=NULL)
    {
        Count[i]++;//第i层结点数+1
        Max=max(Max,Count[i]);
        Num(T->Lchild,i+1);//T的左孩子，层数+1
        Num(T->Rchild,i+1);//T的右孩子，层数+1
    }
}

int main()
{
    TreeNode *Root;
    Root=Built();
    Num(Root,1);
    cout<<Max;
    return 0;
}

#include<bits/stdc++.h>
using namespace std; 

char x;int Book[100]={0},Max=0;
void slove(int n)
{
    if(scanf("%c",&x)&&x=='#') return ;
    Book[n]++;
    Max=max(Book[n],Max);
    slove(n+1);    
    slove(n+1);
 } 

int main()
{
    slove(1);
    cout<<Max;
    return 0;
}

---

[973] 统计利用先序遍历创建的二叉树叶结点的个数

• 思路
• 题目描述
• 二叉树实现
• 数组模拟实现

这题没看懂样例，但是用[971]的代码直接过了

描述

传送门

输入

利用先序递归遍历算法创建二叉树并计算该二叉树叶结点的个数。先序递归遍历建立二叉树的方法为：按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符”#”时表示该结点不需要创建，否则创建该结点。最后再统计创建完成的二叉树叶结点的个数。需要注意输入数据序列中的”#”字符和非”#”字符的序列及个数关系，这会最终决定创建的二叉树的形态。

输出

接受键盘输入的由大写英文字符和”#”字符构成的一个字符串（用于创建对应的二叉树）。

样例输入

#
A##
ABC####
AB##C##
ABCD###EF##G###
A##B##
#A

样例输出

0
1
1
2
3
1
0

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define NewNode (TreeNode *) malloc (sizeof(TreeNode))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

int Count[100]={0},Max=0;

typedef struct node
{
    char data;
    node *Lchild,*Rchild;
} TreeNode;

TreeNode *Built()
{
    TreeNode *T;
    char ch;
    cin>>ch;
    if(ch=='#')
        T=NULL;
    else
    {
        T=NewNode;
        T->data=ch;
        T->Lchild=Built();
        T->Rchild=Built();
    }
    return T;
}

void Num(TreeNode *&T,int i)
{
    if(T!=NULL)
    {
        Count[i]++;//第i层结点数+1
        Max=max(Max,Count[i]);
        Num(T->Lchild,i+1);//T的左孩子，层数+1
        Num(T->Rchild,i+1);//T的右孩子，层数+1
    }
}

int main()
{
    TreeNode *Root;
    Root=Built();
    Num(Root,1);
    cout<<Max;
    return 0;
}

敬请期待…

---

[975] 统计利用先序遍历创建的二叉树的度为2的结点个数

• 思路
• 题目描述
• 二叉树实现
• 简单写法

左右儿子都！=NULL,ans++;

传送门

描述

利用先序递归遍历算法创建二叉树并计算该二叉树度为2结点的个数。先序递归遍历建立二叉树的方法为：按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符”#”时表示该结点不需要创建，否则创建该结点。最后再统计创建完成的二叉树度为2的结点个数。需要注意输入数据序列中的”#”字符和非”#”字符的序列及个数关系，这会最终决定创建的二叉树的形态。

输入

接受键盘输入的由大写英文字符和”#”字符构成的一个字符串（用于创建对应的二叉树）。

输出

输出该用例对应的二叉树度为2的结点个数。

样例输入

#
A##
ABC####
AB##C##
ABCD###EF##G##H##
A##B##
#A

样例输出

0
0
0
1
3
0
0

#include<iostream>
#include<malloc.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define NewNode (TreeNode *) malloc (sizeof(TreeNode))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll;
const int mod =1e9+7;

typedef struct node {
    char data;
    node *Lchild,*Rchild;
} TreeNode;

TreeNode *Built() {
    TreeNode *T;
    char ch;
    cin>>ch;
    if(ch=='#')
        T=NULL;
    else {
        T=NewNode;
        T->data=ch;
        T->Lchild=Built();
        T->Rchild=Built();
    }
    return T;
}

int Count(TreeNode *&Tem) {
    if(Tem==NULL) return 0;
    if((Tem->Lchild!=NULL)&&(Tem->Rchild!=NULL))    //如果当前节点的左右儿子都不为空，说明他度数为2，ans++
        return 1+Count(Tem->Lchild)+Count(Tem->Rchild); //1就是ans+1
    return (Count(Tem->Lchild)+Count(Tem->Rchild)); //否则就不+1

}

int main() {
    TreeNode *Root;
    Root=Built();
    cout<<Count(Root);
    return 0;
}

#include<bits/stdc++.h>
using namespace std; 

char x;int ans=0;
bool slove()
{
    if(scanf("%c",&x)&&(x=='#'||x=='\n')) 
        return false;
    int a=slove();
    int b=slove();
    if(a&&b) 
        ans++;    
    return true;
 } 

int main()
{
    slove();
    cout<<ans;
    return 0;
}

---

[976] 统计利用先序遍历创建的二叉树的度为1的结点个数

• 思路
• 题目描述
• 二叉树实现
• 数组模拟实现

(左儿子==NULL)^(右儿子==NULL)，ans++

传送门

描述

利用先序递归遍历算法创建二叉树并计算该二叉树度为1结点的个数。先序递归遍历建立二叉树的方法为：按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符”#”时表示该结点不需要创建，否则创建该结点。最后再统计创建完成的二叉树度为1的结点个数。需要注意输入数据序列中的”#”字符和非”#”字符的序列及个数关系，这会最终决定创建的二叉树的形态。

输入

输入为接受键盘输入的由大写英文字符和”#”字符构成的一个字符串（用于创建对应的二叉树）。

输出

每个用例用一行输出该用例对应的二叉树度为1的结点个数。

样例输入

#
A##
ABC####
AB##C##
ABCD###EF##G###
A##B##
#A

样例输出

0
0
2
0
2
0
0

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define NewNode (TreeNode *) malloc (sizeof(TreeNode))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct node
{
    char data;
    node *Lchild,*Rchild;
} TreeNode;

TreeNode *Built()
{
    TreeNode *T;
    char ch;
    cin>>ch;
    if(ch=='#')
        T=NULL;
    else
    {
        T=NewNode;
        T->data=ch;
        T->Lchild=Built();
        T->Rchild=Built();
    }
    return T;
}

int Count(TreeNode *&Tem)
{
    if(Tem==NULL) return 0;
    if((Tem->Lchild==NULL)^(Tem->Rchild==NULL)) return 1+Count(Tem->Lchild)+Count(Tem->Rchild);
    return (Count(Tem->Lchild)+Count(Tem->Rchild));
    
}

int main()
{
    TreeNode *Root;
    Root=Built();
    cout<<Count(Root);
    return 0;
}

敬请期待…

---

[977] 统计利用先序遍历创建的二叉树中的空链域个数

• 思路
• 题目描述
• 二叉树实现
• 数组模拟实现

跟前面几道差不多

传送门

描述

利用先序递归遍历算法创建二叉树并计算该二叉树中的空链域个数。先序递归遍历建立二叉树的方法为：按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符”#”时表示该结点不需要创建，否则创建该结点。最后再统计创建完成的二叉树中的空链域个数。需要注意输入数据序列中的”#”字符和非”#”字符的序列及个数关系，这会最终决定创建的二叉树的形态。

输入

输入为接受键盘输入的由大写英文字符和”#”字符构成的一个字符串（用于创建对应的二叉树）。

输出

输出该用例对应的二叉树中的空链域个数。

样例输入

A##
ABC####
AB##C##
ABCD###EF##G###
A##B##
#A

样例输出

2
4
4
8
2
1

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define NewNode (TreeNode *) malloc (sizeof(TreeNode))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct node
{
    char data;
    node *Lchild,*Rchild;
} TreeNode;

TreeNode *Built()
{
    TreeNode *T;
    char ch;
    cin>>ch;
    if(ch=='#')
        T=NULL;
    else
    {
        T=NewNode;
        T->data=ch;
        T->Lchild=Built();
        T->Rchild=Built();
    }
    return T;
}

int Count(TreeNode *&Tem)
{
    if(Tem==NULL) return 1;
    return (Count(Tem->Lchild)+Count(Tem->Rchild));
    
}

int main()
{
    TreeNode *Root;
    Root=Built();
    cout<<Count(Root);
    return 0;
}

敬请期待…

---

[978] 输出利用先序遍历创建的二叉树的中序遍历序列

• 思路
• 题目描述
• 二叉树实现
• 数组模拟实现

修改一下递归顺序。

传送门

描述

利用先序递归遍历算法创建二叉树并输出该二叉树的中序遍历序列。先序递归遍历建立二叉树的方法为：按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符”#”时表示该结点不需要创建，否则创建该结点。最后再输出创建完成的二叉树的中序遍历序列。需要注意输入数据序列中的”#”字符和非”#”字符的序列及个数关系，这会最终决定创建的二叉树的形态。

输入

输入为接受键盘输入的由大写英文字符和”#”字符构成的一个字符串（用于创建对应的二叉树）。

输出

对应的二叉树的中序遍历序列。

样例输入

A##
ABC####
AB##C##
ABCD###EF##G###
A##B##

样例输出

A
CBA
BAC
DCBFEGA
A

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define NewNode (TreeNode *) malloc (sizeof(TreeNode))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct node
{
    char data;
    node *Lchild,* Rchild;
} TreeNode;

TreeNode *Built()
{
    TreeNode *T;
    char ch;
    cin>>ch;
    if(ch=='#')
        T=NULL;
    else
    {
        T=NewNode;
        T->data=ch;
        T->Lchild=Built();
        T->Rchild=Built();
    }
    return T;
}

void Put(TreeNode *&Tem)
{
    if(Tem==NULL) return;
    Put(Tem->Lchild);
    cout<<Tem->data;
    Put(Tem->Rchild);
 } 

int main()
{
    TreeNode *Root;
    Root=Built();
    Put(Root);
    return 0;
}

敬请期待…

---

[979] 输出利用先序遍历创建的二叉树的后序遍历序列

• 思路
• 题目描述
• 二叉树实现
• 数组模拟实现

修改一下递归顺序。

传送门

描述

利用先序递归遍历算法创建二叉树并输出该二叉树的后序遍历序列。先序递归遍历建立二叉树的方法为：按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符”#”时表示该结点不需要创建，否则创建该结点。最后再输出创建完成的二叉树的后序遍历序列。需要注意输入数据序列中的”#”字符和非”#”字符的序列及个数关系，这会最终决定创建的二叉树的形态。

输入

输入为接受键盘输入的由大写英文字符和”#”字符构成的一个字符串（用于创建对应的二叉树）。

输出

对应的二叉树的后序遍历序列。

样例输入

A##
ABC####
AB##C##
ABCD###EF##G###
A##B##

样例输出

A
CBA
BCA
DCFGEBA
A

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define NewNode (TreeNode *) malloc (sizeof(TreeNode))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct node
{
    char data;
    node *Lchild,*Rchild;
} TreeNode;

TreeNode *Built()
{
    TreeNode *T;
    char ch;
    cin>>ch;
    if(ch=='#')
        T=NULL;
    else
    {
        T=NewNode;
        T->data=ch;
        T->Lchild=Built();
        T->Rchild=Built();
    }
    return T;
}

void Put(TreeNode *&Tem)
{
    if(Tem==NULL) return;
    Put(Tem->Lchild);
    Put(Tem->Rchild);
    cout<<Tem->data;
 } 

int main()
{
    TreeNode *Root;
    Root=Built();
    Put(Root);
    return 0;
}

敬请期待…

---

[1027]舞伴问题

• 思路
• 题目描述
• 队列实现
• 数组模拟实现

每次分别取两个队列的队首元素，然后放到队尾。

传送门

描述

假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。要求编写程序实现舞伴问题。

输入

输入一共5行，
第一行是男生人数m；
第二行依次是男生的姓名；
第三行是女士的人数n；
第四行依次是女士的姓名；
第五行是跳舞的轮数。

输出

配对的男士和女士的姓名。

样例输入

5
A B C D E
3
F G H
2

样例输出

B G

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct qnode
{
    char data;
    struct qnode *next;
}QNode;

typedef struct
{
    QNode * front;
    QNode * rear;
}Head;

void Init(Head *&q)
{
    q=(Head *) malloc (sizeof(Head));
    q->front=q->rear=NULL;
}

bool Empty(Head *&q)
{
    return (q->rear==NULL);
}

void In(Head *&q,char &x)
{
    QNode *p;
    p=(QNode *) malloc(sizeof(QNode));
    p->data=x;
    p->next=NULL;
    if(q->rear==NULL)
        q->front=q->rear=p;
    else
    {
        q->rear->next=p;
        q->rear=p;
    }
}

bool Out(Head *&q,char &x)
{
    QNode *T;
    if(q->rear==NULL)
        return false;
    t=q->front;
    if(q->front==q->rear)
        q->front=q->rear=NULL;
    else
        q->front=q->front->next;
    x=t->data;
    free(t);
    return true;
}

int main()
{
    Head *q1;
    Head *q2;
    Init(q1);
    Init(q2);
    int n;char x,a,b;;
    cin>>n;
    while(n--)
    {
        cin>>x;
        In(q1,x);
    }
    
    cin>>n;
    while(n--)
    {
        cin>>x;
        In(q2,x);
    }
    
    cin>>n;
    while(n--)
    {
        Out(q1,a);
        Out(q2,b);
        In(q1,a);
        In(q2,b);
    }
    
    cout<<a<<" "<<b;
    return 0;
}

敬请期待…

---

[1028]特定字符序列的判断

• 思路
• 题目描述
• 链栈实现
• 数组模拟实现

去掉’@’就和括号匹配问题一样了。

传送门

描述

编写一程序，识别依次读入的一个以“#”为结束符的字符序列是否为形如“序列1@序列2”模式的字符序列。期中序列1和序列2中都不含字符“@”，且序列2是序列1的逆序列。例如“a+b@b+a”是满足条件的序列字符，而“1+3@3-1”则不是。

输入

一个以“#”结束的字符序列。

输出

是满足条件的字符序列输出“yes!”；否则输出“no!”。

样例输入

a+b@b+a#

样例输出

yes!

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct linknode
{
    char data;
    linknode *next;
 } LinkStNode;
 
void Init(LinkStNode *&Top)
{
    Top=(LinkStNode *) malloc (sizeof(LinkStNode)); 
    Top->next=NULL;
}

void Push(LinkStNode *&Top,char x)        //入栈
{
    LinkStNode *tem;
    tem=(LinkStNode *) malloc (sizeof(LinkStNode));
    tem->data=x;
    tem->next=Top->next;
    Top->next=tem;
 } 
 
void Pop(LinkStNode *&Top)        
{
    LinkStNode *tem;
    tem=Top->next;
    Top->next=Top->next->next;
    free(tem);
}

bool Empty(LinkStNode *&Top)
{
    return (Top->next==NULL);
}

char GetTop(LinkStNode *&Top)
{
    if(Top->next!=NULL) return Top->next->data;
    return '0';
}

int main()
{
    LinkStNode *Top;
    Init(Top);
    char x;
    while(scanf("%c",&x)&&x!='\n')
    {
        if(GetTop(Top)=='['&&x==']'||GetTop(Top)=='('&&x==')'||GetTop(Top)=='{'&&x=='}')
            Pop(Top);
        else
            Push(Top,x);
    }

    Empty(Top) ? cout<<"YES":cout<<"NO";
    return 0;
}

敬请期待…

---

[1035] 定位顺序表中的最大和最小值

• 思路
• 题目描述
• 顺序表实现
• 数组模拟实现

…

传送门

描述

建立长度为n的顺序表，在表中找出最大值和最小值元素所在的位置。

输入

第一行为顺序表的长度n；
第二行为顺序表中的数据元素；

输出

第一行为最大值的位置；
第二行为最小值的位置。

样例输入

7
1 2 3 4 5 6 7

样例输出

Lmax=6
Lmin=0

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct 
{
    int data[100];
    int len;
} SqList;

void Create (SqList *&L)
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>L->data[i];
    L->len=n;
}

void Find(SqList *&L,int &Min,int &Max)
{
    for(int i=0;i<L->len;i++)
    {
        if(L->data[Min]>L->data[i]) Min=i;
        if(L->data[Max]<L->data[i]) Max=i;
    }
}

int main()
{
    SqList *La;
    int Min,Max;
    La=(SqList *) malloc(sizeof(SqList));
    
    Create(La);
    Find(La,Min,Max);
    cout<<"Lmax="<<Max<<"\n";
    cout<<"Lmin="<<Min;
    return 0;
}

敬请期待…

---

[1036] 寻找整数序列的主元素

• 思路
• 题目描述
• 顺序表实现
• 数组模拟实现

算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。 然后重新计数， 确认 Num 是否是主元素。算法可分为以下两步：

• 选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数 Num 保存到 c 中，记录 Num 的出现次数为 1；若遇到的下一个整数仍等于 Num，则计数加 1，否则计数减 1； 当计数减到 0 时，将遇到的下一个整数保存到 c 中，计数重新记为 1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。
• 判断 c 中元素是否是真正的主元素：再次扫描该数组，统计 c 中元素出现的次数，若大于 n/2，则为主元素；否则，序列中不存在主元素。

传送门

描述

已知一个整数序列$A=（a_0，a_1，…a_n）$，如果其中有一个元素的出现次数超过n/2，就称该元素为A的主元素，否则就称整数序列没有主元素。例如A=（0，5，5，3，5，7，5，5），则5为主元素。A=（0，5，5，3，5，1，5，7），则A中没有主元素。要求编写程序实现寻找给定整数序列的主元素，如果找到，则输出主元素。如果没有找到，则输出-1。

输入

第一行为整数序列的个数n
第二行为一个整数序列。

输出

如果找到主元素，输出主元素的值，否则输出-1。

样例输入

8
0 5 5 3 5 7 5 5

样例输出

5

把数组模拟的改成顺序表就行了。

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

int a[200];

int main()
{
    int n,ans,Count=0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(!Count)
        {
            ans=a[i];
            Count++;
        }
        else
        if(a[i]==ans)
            Count++;
        else
            Count--;
    }
    
    Count=0;
    
    for(int i=0;i<n;i++)
        if(a[i]==ans)
        Count++;
        
    Count>n/2 ? cout<<ans:cout<<-1; 
    return 0;
} 

---

[1037]集合的并运算的实现

• 思路
• 题目描述
• 顺序表实现
• 数组模拟实现

遍历大法好

传送门

描述

假设有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即线性表中的数据元素即为集合中的成员。编程实现集合A和集合B的并运算。

输入

第一行为集合A的数据元素个数n 第二行输入n个集合A的数据元素 第三行为集合B的数据元素的个数； 第四行输入m个集合B的数据元素。

输出

第一行为A和B的并集.

样例输入

8
0 5 6 3 8 7 9 10
7
1 3 4 7 8 9 5

样例输出

0 5 6 3 8 7 9 10 1 4 

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct 
{
    int date[100];
    int len;
} SqList;

void Create (SqList *&L)
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>L->date[i];
    L->len=n;
}

void Merge(SqList *&La,SqList *&Lb)
{
    for(int i=0;i<Lb->len;i++)
    {
        int j=0;
        for(;j<La->len;j++)
            if(La->date[j]==Lb->date[i]) break;
        
        if(j==La->len) 
        {
            La->date[j]=Lb->date[i];
            La->len++;
        }
    }
}

void Put(SqList *&La)
{
    for(int i=0;i<La->len;i++)
        cout<<La->date[i]<<" "; 
}

int main()
{
    SqList *La,*Lb;
    La=(SqList *) malloc(sizeof(SqList));
    Lb=(SqList *) malloc(sizeof(SqList));
    
    Create(La);
    Create(Lb);
    Merge(La,Lb);
    Put(La);
    return 0;
}

敬请期待…

---

[1038]顺序表中重复数据的删除

• 思路
• 题目描述
• 顺序表实现
• 数组模拟实现

遍历，找到就删。
注意不要每一次都从头找。

传送门

描述

将存储在顺序表中的长度为n的线性表中指定的数据全部删除。

输入

第一行为顺序表的长度n； 第二行为顺序表中的数据元素； 第三行为指定要删除的元素值。

输出

如果表不空，输出删除指定值后的线性表；如果删除后表空，则输出-1。

样例输入

8
11 22 33 44 44 55 44 66
44

样例输出

11 22 33 55 66

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct 
{
    int date[100];
    int len;
} SqList;

void Create (SqList *&L)
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>L->date[i];
    L->len=n;
}

void Put(SqList *&La)
{
    for(int i=0;i<La->len;i++)
        cout<<La->date[i]<<" "; 
}

bool Find(SqList *&L,int x,int &li)
{
    for(int i=li;i<L->len;i++)
        if(L->date[i]==x)
        {
            li=i;
            return true;
        }
    return false;
}

void Delete(SqList *&L,int x)
{
    for(int i=x;i<L->len;i++)
        L->date[i]=L->date[i+1];
    
    L->len--;
}

int main()
{
    SqList *La;
    La=(SqList *) malloc(sizeof(SqList));
    
    Create(La);
    int x,li=0;
    cin>>x;
    while(Find(La,x,li))
    {
        Delete(La,li); 
    }
    if(La->len==0) cout<<-1;
    else
    Put(La);

    return 0;
}

敬请期待…

---

[1039] 单链表中信息的分类

• 思路
• 题目描述
• 顺序表实现
• 数组模拟实现

…

传送门

描述

已知L为设有头结点的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符或数字字符或其他字符。编写程序构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符，最后输出链表中的信息。

输入

链表中的数据元素

输出

第一行为数字链表中的信息； 第二行为英文字母字符链表中的信息； 第三行为其它字符链表中的信息。

样例输入

abc123@$12

样例输出

12312
abc
@$

是我菜了，没看懂要求，所以直接用数组做的。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<stack>
#include<map>
using namespace std;
int main()
{
    char str[1005];
    cin >> str;
    int k, l, m;
    k = l = m = 0;
    char str1[500], str2[500], str3[500];
    for (int i = 0; i < strlen(str); i++)
    {
        if (str[i] >= '0'&&str[i] <= '9')
        {
            str1[k++] = str[i];
        }
        else if ((str[i] >= 'a'&&str[i] <= 'z')|| ( str[i] >= 'A'&&str[i]<='Z') )
        {
            str2[l++] = str[i];
        }
        else
        {
            str3[m++] = str[i];
        }
    }
    str1[k] = str2[l] = str3[m] = '\0';
    cout << str1 << endl << str2 << endl << str3 << endl;
    return 0;
}

---

[1040] 一元多项式加法运算的实现

• 思路
• 题目描述
• 链表实现
• 数组模拟实现

插入排序
测试数据没有答案为0的情况，我就没考虑这种情况。

传送门

描述

编程实现一元多项式的加法运算。（要求用链表实现）

输入

第一个一元多项式A； 第二个一元多项式B。 以（0，0）作为输入结束。

输出

多项式A和多项式B的和。

样例输入

5,3 7,8 9,15 0,0
2,0 6,3 -7,8 0,0

样例输出

2x^0+11x^3+9x^15

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct node 
{
    int xishu;
    int cifang;
    node *next;
} LinkNode;

void Init(LinkNode *&Head)
{
    Head=(LinkNode *)malloc(sizeof(LinkNode));
    Head->next=NULL;
}

void Create (LinkNode *&Head)
{
    LinkNode *p1,*p2;
    p1=Head;
    
    int c,x;
    while(scanf("%d,%d",&c,&x)&&(c||x))
    {
        p1=Head;
        while(p1->next!=NULL&&p1->next->cifang<x)
            p1=p1->next;
        
        if(p1->next==NULL||p1->next->cifang>x)
        {
            p2=(LinkNode *)malloc(sizeof(LinkNode));
            p2->cifang=x;
            p2->xishu=c;
            p2->next=p1->next;
            p1->next=p2;
        }
        else 
            p1->next->xishu+=c;
    }
}

void Put(LinkNode *Head)
{
    LinkNode *p1=Head->next;
    
    while(p1!=NULL)
    {
        if(p1->xishu==0)
        {
            p1=p1->next;
            continue;
         } 
        if(p1!=Head->next)
            cout<<"+";
        cout<<p1->xishu<<"x^"<<p1->cifang;
        p1=p1->next;
    }
}

int main()
{
    LinkNode *Head;
    Init(Head);
    Create(Head);
    Create(Head);
    Put(Head);
    return 0;
}

敬请期待…

---

[1042] 中缀表达式转换为后缀表达式

• 思路
• 题目描述
• 链栈实现
• 数组模拟实现

读入不是’+’,’-‘,’*’,’-‘，就入栈再出栈，否则入栈，当遇到’)’时，将栈里从栈顶到’(‘的元素全部出栈，最后全部出栈，所得到的出栈顺序就是后缀表达式。

传送门

描述

中缀表达式是一个通用的算术或逻辑公式表示方法，操作符是以中缀形式处于操作数的中间（例：3 + 4），中缀表达式是人们常用的算术表示方法。后缀表达式不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：(2 + 1) 3 ， 即2 1 + 3 。利用栈结构，将中缀表达式转换为后缀表达式。(测试数据元素为单个字符)

输入

中缀表达式

输出

后缀表达式

样例输入

A+(B-C/D)*E

样例输出

ABCD/-E*+

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct linknode
{
    char data;
    linknode *next;
 } LinkStNode;
 
void Init(LinkStNode *&Top)
{
    Top=(LinkStNode *) malloc (sizeof(LinkStNode)); 
    Top->next=NULL;
}

void Push(LinkStNode *&Top,int x)        //入栈
{
    LinkStNode *tem;
    tem=(LinkStNode *) malloc (sizeof(LinkStNode));
    tem->data=x;
    tem->next=Top->next;
    Top->next=tem;
 } 
 
bool Empty(LinkStNode *&Top)
{
    return (Top->next==NULL);
}

bool Pop(LinkStNode *&Top,char &x)        
{
    if(Empty(Top)) return false;
    LinkStNode *tem;
    tem=Top->next;
    x=tem->data;
    Top->next=Top->next->next;
    free(tem);
    return true;
}


int GetTop(LinkStNode *&Top)
{
    if(Top->next!=NULL) return Top->next->data;
    return 0;
}

int main()
{
    LinkStNode *Top;
    Init(Top);
    char x,tem;
    while(scanf("%c",&x)&&x!='\n')
    {
        if(x=='+'||x=='-'||x=='*'||x=='/'||x=='(') 
            Push(Top,x);
        else
        if(x==')')
        while(Pop(Top,tem)&&tem!='(')
            cout<<tem;
        else        
        {
            Push(Top,x);
            Pop(Top,tem);
            cout<<tem;
        }
    }
    
    while(Pop(Top,tem))
        cout<<tem;
    return 0;
}

敬请期待…

---

[1043] 利用栈完成后缀表达式的计算

• 思路
• 题目描述
• 链栈实现
• 数组模拟实现

是数字就入栈，否则弹出栈顶两个进行运算，再将运算结果压入栈。

传送门

描述

后缀表达式不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：(2 + 1) * 3 ， 即2 1 + 3 *。利用栈结构，将后缀表达式的结果计算出来。

输入

后缀表达式。以#号作为表达式结束标志。为了简单，处理的数据为0-9的整数。

输出

计算结果。

样例输入

3 6 6 2 / - 3 * +#

样例输出

12

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct linknode
{
    int data;
    linknode *next;
 } LinkStNode;
 
void Init(LinkStNode *&Top)
{
    Top=(LinkStNode *) malloc (sizeof(LinkStNode)); 
    Top->next=NULL;
}

void Push(LinkStNode *&Top,int x)        //入栈
{
    LinkStNode *tem;
    tem=(LinkStNode *) malloc (sizeof(LinkStNode));
    tem->data=x;
    tem->next=Top->next;
    Top->next=tem;
 } 
 
int Pop(LinkStNode *&Top)        
{
    int x;
    LinkStNode *tem;
    tem=Top->next;
    x=tem->data;
    Top->next=Top->next->next;
    free(tem);
    return x;
}

bool Empty(LinkStNode *&Top)
{
    return (Top->next==NULL);
}

int GetTop(LinkStNode *&Top)
{
    if(Top->next!=NULL) return Top->next->data;
    return 0;
}

int main()
{
    LinkStNode *Top;
    Init(Top);
    char x,Flag=' ';
    while(scanf("%c",&x)&&Flag!='#')
    {
        if(x>'0'&&x<'9') 
            Push(Top,x-'0');
        else
        {
            int b=Pop(Top),a=Pop(Top);
            switch(x)
            {
                case '+' : Push(Top,a+b);break;
                case '-' : Push(Top,a-b);break;
                case '*' : Push(Top,a*b);break;
                case '/' : Push(Top,a/b);break;
            }
        }
        scanf("%c",&Flag);
    }

    cout<<GetTop(Top);
    return 0;
}

敬请期待…

---

[1044] 顺序栈基本操作的实现

• 思路
• 题目描述
• 链栈实现
• 数组模拟实现

…我直接写的链栈，改改就好了

传送门

描述

编程实现顺序栈的初始化、入栈、出栈、取栈顶元素和计算栈中元素个数等基本操作。

输入

第一行为入栈元素的个数； 第二行依次为入栈的元素； 出栈操作的次数n.

输出

输出n次出栈后的栈顶元素值。如果是空栈，输出-1.

样例输入

4
1 2 3 4
2

样例输出

2

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
#define MaxSize 200
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct 
{
    int data[MaxSize];
    int Top;
 } SqStack;
 
void Init(SqStack *&S)
{
    S=(SqStack *) malloc (sizeof(SqStack)); 
    S->Top=-1;
}

bool Push(SqStack *&S,int x)        //入栈
{
    if(S->Top==MaxSize-1)
        return false;
    S->Top++;
    S->data[S->Top]=x;
    return true;
 } 
 
bool Empty(SqStack *&S)
{
    return (S->Top==-1);
}

bool Pop(SqStack *&S,int &x)        
{
    if(S->Top==-1)
        return false;
    x=S->data[S->Top];
    S->Top--;
    return true;
}


bool GetTop(SqStack *&S,int &x)
{
    if(S->Top==-1) 
        return false;
    x=S->data[S->Top];
    return true;
}

int main()
{
    SqStack *S;
    Init(S);
    int tem,n;
    cin>>n;
    while(n--)
    {
        cin>>tem;
        Push(S,tem);
    }
    cin>>n;
    while(n--)
        Pop(S,tem);
    
    if(Empty(S))
        cout<<-1;
    else
    {
        GetTop(S,tem);
        cout<<tem; 
    }
    return 0;
}

敬请期待…

---

[1045] 集合的交运算的实现

• 思路
• 题目描述
• 顺序表实现
• 数组模拟实现

…

传送门

描述

假设有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即线性表中的数据元素即为集合中的成员。编程实现集合A和集合B的交运算。

输入

第一行为集合A的数据元素个数n;
第二行输入n个集合A的数据元素 ;
第三行为集合B的数据元素的个数；
第四行输入m个集合B的数据元素

输出

A和B的交集

样例输入

8
0 5 6 3 8 7 9 10
7
1 3 4 7 8 9 5

样例输出

5 3 8 7 9

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct 
{
    int date[100];
    int len;
} SqList;

void Create (SqList *&L)
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>L->date[i];
    L->len=n;
}

void Merge(SqList *&La,SqList *&Lb)
{
    for(int i=0;i<La->len;i++)
    {
        int j=0;
        for(;j<Lb->len;j++)
            if(La->date[i]==Lb->date[j])
            {
                cout<<La->date[i]<<" ";
                break;
            }
    }
}

int main()
{
    SqList *La,*Lb;
    La=(SqList *) malloc(sizeof(SqList));
    Lb=(SqList *) malloc(sizeof(SqList));
    
    Create(La);
    Create(Lb);
    Merge(La,Lb);
    return 0;
}

敬请期待…

---

[1046] 链栈基本操作的实现

• 思路
• 题目描述
• 链栈实现
• 数组模拟实现

…

传送门

描述

编程实现链栈的初始化、入栈、出栈和计算栈中元素个数等基本操作。（测试数据为整数。）

输入

第一行为入栈元素的个数;
第二行为入栈元素；
出栈操作的次数n.

输出

n次出栈后的栈顶元素。如果是空栈，输出-1.

样例输入

4
1 2 3 4
2

样例输出

2

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct linknode
{
    int data;
    linknode *next;
 } LinkStNode;
 
void Init(LinkStNode *&Top)
{
    Top=(LinkStNode *) malloc (sizeof(LinkStNode)); 
    Top->next=NULL;
}

void Push(LinkStNode *&Top,int x)        //入栈
{
    LinkStNode *tem;
    tem=(LinkStNode *) malloc (sizeof(LinkStNode));
    tem->data=x;
    tem->next=Top->next;
    Top->next=tem;
 } 

bool Empty(LinkStNode *&Top)
{
    return (Top->next==NULL);
} 

int Pop(LinkStNode *&Top)        
{
    if(Empty(Top)) return 0;
    int x;
    LinkStNode *tem;
    tem=Top->next;
    x=tem->data;
    Top->next=Top->next->next;
    free(tem);
    return x;
}


int GetTop(LinkStNode *&Top)
{
    if(Top->next!=NULL) return Top->next->data;
    return 0;
}

int main()
{
    LinkStNode *Top;
    Init(Top);
    
    int n,x;
    cin>>n;
    while(n--)
    {
        cin>>x;
        Push(Top,x);
    }
    cin>>n;
    while(n--)
    {
        Pop(Top);
    }
    Empty(Top)? cout<<-1: cout<<GetTop(Top);
    return 0;
}

敬请期待…

---

[1101] 顺序表中数据的循环移动

• 思路
• 题目描述
• 顺序表实现
• 数组模拟实现

Lb->date[i]=La->date[(i+k)%La->len];

传送门

描述

设有长度为n（n>1）的顺序表R，将R中保存的序列循环左移P（0 < P < n）个位置，即将R中的数据由（x0,x1,…,xn-1）变换为(xp,xp+1,…,xn-1,x0,x1,…,xp-1)。如果p值不合法，输出“error！”。

输入

第一行为数据元素个数n；
第二行为n个整数；
第三行为要左移的位数p

输出

移动后的序列。

样例输入

10
1 2 3 4 5 6 7 8 9 10
5

样例输出

6 7 8 9 10 1 2 3 4 5

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct 
{
    int date[100];
    int len;
} SqList;

void Create (SqList *&L)
{
    int n;
    cin>>n;
    L=(SqList *) malloc(sizeof(SqList));
    for(int i=0;i<n;i++)
        cin>>L->date[i];
    L->len=n;
}

void Put(SqList *&La)
{
    for(int i=0;i<La->len;i++)
        cout<<La->date[i]<<" "; 
}

void Move(SqList *&La,SqList *&Lb,int k)
{
    for(int i=0;i<La->len;i++)
        Lb->date[i]=La->date[(i+k)%La->len];
    Lb->len=La->len;
}

int main()
{
    int k;
    SqList *La;
    SqList *Lb=(SqList *) malloc(sizeof(SqList));
    Create(La);
    cin>>k;
    if(k<=0||k>=La->len)
        cout<<"error!";
    else
    {
        Move(La,Lb,k);
        Put(Lb);    
    }
    return 0;
}

敬请期待…

---

[1102] 顺序表上数据的划分问题的实现

• 思路
• 题目描述
• 顺序表实现
• 数组模拟实现

这道题要正着找大的，逆着找小的。

传送门

描述

建立一个顺序表L，然后以第一个为分界，将所有小于等于它的元素移到该元素的前面，将所有大于它的元素移到该元素的后面。

输入

顺序表长度n；
顺序表中的数据元素。

输出

移动后的数据元素。

样例输入

10
32 5 22 43 23 56 54 57 11 25

样例输出

25 11 23 22 5 32 43 56 54 57

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct 
{
    int date[100];
    int len;
} SqList;

void Create (SqList *&L)
{
    int n;
    cin>>n;
    L=(SqList *) malloc(sizeof(SqList));
    for(int i=0;i<n;i++)
        cin>>L->date[i];
    L->len=n;
}

void Put(SqList *&La)
{
    for(int i=0;i<La->len;i++)
        cout<<La->date[i]<<" "; 
}

void Move(SqList *&La,SqList *&Lb)
{
    int tem=La->date[0];
    Lb->len=0;
    for(int i=La->len-1;i>=0;i--)
        if(La->date[i]<tem)
        {
            Lb->date[Lb->len]=La->date[i];
            Lb->len++;
        }
    
    Lb->date[Lb->len]=tem;
        Lb->len++;
    
    for(int i=0;i<La->len;i++)
        if(La->date[i]>tem)
        {
            Lb->date[Lb->len]=La->date[i];
            Lb->len++;
        }
}

int main()
{
    int k;
    SqList *La;
    SqList *Lb=(SqList *) malloc(sizeof(SqList));
    Create(La);
    Move(La,Lb);
    Put(Lb);
    return 0;
}

敬请期待…

---

[1103] 删除顺序表中指定区间的数据

• 思路
• 题目描述
• 线性表实现
• 数组模拟实现

…

传送门

描述

建立顺序表L，将指定区间的数据从顺序表中删除。假设指定区间是合法数据，无序做合法性判断。测试数据为整型。

输入

第一行是表长n；
第二行是表中数据元素。

输出

删除以后的顺序表中的数据元素。

样例输入

10
22 32 11 23 43 59 17 65 45 57
10 20

样例输出

22 32 23 43 59 65 45 57

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll; 
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7; 

typedef struct 
{
    int date[100];
    int len;
} SqList;

void Create (SqList *&L)
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>L->date[i];
    L->len=n;
}

void Put(SqList *&La)
{
    for(int i=0;i<La->len;i++)
        cout<<La->date[i]<<" "; 
}

bool Find(SqList *&L,int l,int r,int &li)
{
    for(int i=0;i<L->len;i++)
        if(L->date[i]>=l&&L->date[i]<=r)
        {
            li=i;
            return true;
        }
    return false;
}

void Delete(SqList *&L,int x)
{
    for(int i=x;i<L->len;i++)
        L->date[i]=L->date[i+1];
    
    L->len--;
}

int main()
{
    SqList *La;
    La=(SqList *) malloc(sizeof(SqList));
    
    Create(La);
    int l,r,li;
    cin>>l>>r;
    while(Find(La,l,r,li))
    {
        Delete(La,li); 
    }
    if(La->len==0) cout<<-1;
    else
    Put(La);

    return 0;
}

敬请期待…