算法笔记—数据结构专题

栈和队列

栈

#include<stack>
stack<int> s;
s.push(value);  //入栈
s.pop();   //弹栈
s.top();   //获得栈顶元素
s.empty();  //是否为空
s.size();  //元素个数

需要注意的是STL中没有清空栈的操作，如果需要清空栈

while(!s.empty())
{
    s.pop();
}

队列

queue<typename> q;
q.front();//访问队首元素
q.back();//访问队尾元素

q.push(value);  //入队尾
q.pop();// 队首出队
q.empty();   //检查队是否为空
q.size();  //返回队中元素个数

例题

首先，复习一下中缀表达式和后缀表达式的部分

中缀表达式转后缀表达式

栈是用来存放操作符的，而数组(或者设置一个队列)用来存放后缀表达式
如果是左括号，压入操作符栈，如果是右括号，把栈中的元素不断的弹出，直到碰到左括号

题目就变成了两步：

1. 中缀表达式转后缀表达式
2. 计算后缀表达式
   
   
   书上的代码没有加上有括号的情况，这里我把带括号的情况加上了

#include<iostream>
#include<cstdio>
#include<string>
#include<stack>
#include<queue>
#include<map>
using namespace std;

//由于数字不一定是个位，所以采用节点的方式进行存储
struct node{
    double num; //操作数
    char op;    //操作符
    bool flag;  //true表示操作数，false表示操作符
};

string str;     //中缀表达式
stack<node> s;  //操作符栈
queue<node> q;  //后缀表达式序列
map<char,int> op;  //使用map,op[char] = int; 给操作符定义优先级

//中缀表达式转后缀表达式函数
void change()
{
    double num;
    node temp;
    for(int i=0;i<str.length();) //i的值的更迭在for循环中实现了，这里不要再写
    {
        if(str[i]>='0' && str[i]<='0')
        {//这个数字不一定是个位数，可能有多位的
            temp.flag = true;
            temp.num = str[i]-'0';
            i++;
            while(i<str.length()&&str[i]>='0'&&str[i]<='9')
            {
                temp.num = temp.num*10 + (str[i]-'0');
                i++;
            }
            q.push(temp);
        }
        else if(str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/'){
            temp.flag = false;
            //只要操作符栈的栈顶元素比该操作符优先级高
            //就把操作符栈顶元素弹出到后缀表达式中去
            if(s.top().op!='(')
            {
            while(!s.empty() && op[str[i]] <= op[s.top().op])
            {
                q.push(s.top());
                s.pop();
            }//只有当当前的运算符优先级大于栈顶运算符优先级才压栈，等于的情况有可能出错，例子在上面的图中
            temp.op = str[i];
            s.push(temp);
            i++;
            }
            else{
                temp.op = str[i];
                s.push(temp);
                i++;
            }
        }
        else if(str[i]=='(')
        {
            temp.flag = false;
            temp.op = '(';
            s.push(temp);
            i++;
        }     
        else if(str[i]==')')
        {
            while(s.top().op!='(')
            {
                q.push(s.top());
                s.pop();
            }
            s.pop();
        }  
    }
    while(!s.empty())
    {
        q.push(s.top());
        s.pop();
    }
}

//计算后缀表达式
double Cal()
{
    double temp1,temp2;
    node cur,temp;
    while(!q.empty())
    {
        cur = q.front(); //记录队首元素
        q.pop();
        if(cur.flag == true) s.push(cur);
        else
        {
            temp2 = s.top().num;
            s.pop();
            temp1 = s.top().num;
            s.pop();
            temp.flag = true;
            if(cur.op=='+') temp.num = temp1+temp2;
            else if(cur.op=='-') temp.num = temp1 - temp2;
            else if(cur.op=='*') temp.num = temp1*temp2;
            else if(cur.op == '/') temp.num = temp1/temp2;
            s.push(temp);
        }
    }
    return s.top().num;
}

int main()
{
    op['+'] = op['-'] = 1;
    op['*'] = op['/'] = 2;
    // '0'表示字符，"0"才表示字符串(string类型)
    while(getline(cin,str),str!="0")
    {
        for(string::iterator it=str.end();it!=str.begin();it--)
        {//把空格都去掉
            if(*it == ' ') str.erase(it);
        }
        change();
        printf("%.2f\n",Cal());
        return 0;
    }
}

链表

struct node{
    typename data;
    node *next;
};

node *p = new node;
node *p1 = new node[100];

delete(p);

链表的操作

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

//创建链表
node* creat(int Array[])
{
    node *p,*pre,*head; //p指向当前节点，pre指向前一个节点，head指向头结点
    head = new node;
    head->next = NULL;
    pre = head;
    for(int i=0;i<5;i++)
    {
        p = new node;
        p->data = Array[i];
        p->next = NULL;
        pre->next = p;
        pre = p;
    }
    return head;
}

//查找元素
node* search(node *head,int x)
{
    node* cur = new node;
//这里头结点没给他赋值
    cur = head->next;
    while(cur!=NULL)
    {
        if(cur->data == x) break;
        cur = cur->next;
    }
    if(cur==NULL) printf("no such num\n");
    else return cur;
}

//插入元素
void insert(node *head,int x,int pos)  //在位置pos后插入
{
    node *cur = new node;
    cur = head;
    node *new_node = new node;
    new_node->data = x;
    int count = 0;
    while(count!=pos)
    {
        count++;
        cur = cur->next;
    }
    new_node->next = cur->next;
    cur->next = new_node;
}

//删除节点
void delete(node *head,int x)
{
    node *cur = new node;
    cur = head;
    while(cur->next->data!=x)
    {
        cur = cur->next;
    }
    cur->next = cur->next->next;

}

PAT A Sharing

To store English words, one method is to use linked lists and store a word letter by letter. To save some space, we may let the words share the same sublist if they share the same suffix. For example, loading and being are stored as showed in Figure 1.

输入

Each input file contains one test case. For each case, the first line contains two addresses of nodes and a positive N (≤10^5​​ ), where the two addresses are the addresses of the first nodes of the two words, and N is the total number of nodes. The address of a node is a 5-digit positive integer, and NULL is represented by −1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is the letter contained by this node which is an English letter chosen from { a-z, A-Z }, and Next is the position of the next node

输出

For each case, simply output the 5-digit starting position of the common suffix. If the two words have no common suffix, output -1 instead.

输入实例

11111 22222 9
67890 i 00002
00010 a 12345
00003 g -1
12345 D 67890
00002 n 00003
22222 B 23456
11111 L 00001
23456 e 67890
00001 o 00010

输出实例

67890

实现

#include<cstdio>
#include<cstring>
struct Node{
    char letter;
    int next;
    bool flag;
}node[100010];

int main()
{
    for(int i=0;i<100010;i++)
    {
        node[i].flag = false;
    }
    int add1,add2,N;
    scanf("%d%d%d",&add1,&add2,&N);
    for(int i=0;i<N;i++)
    {
        int pos,the_next;
        char the_letter;
        scanf("%d %c %d",&pos,&the_letter,&the_next);
        node[pos].next = the_next;
        node[pos].letter = the_letter;
    }
    int cur1 = add1,cur2 = add2;
    while(cur1 != -1)
    {
        node[cur1].flag = true;
        cur1 = node[cur1].next;
    }
    while(cur2 != -1)
    {
        if(node[cur2].flag == true) break;
        cur2 = node[cur2].next;
    }
    if(cur2!=-1) printf("%05d\n",cur2);
    else printf("-1\n");

    return 0;


}

本文地址：https://blog.csdn.net/weixin_44972129/article/details/110140582