menu 李昊天的个人博客
程序设计:算法和数据结构 笔记2——数据结构
360 浏览 | 2019-07-09 | 分类:算法笔记 | 标签:算法,学习笔记

概述

栈(Stack)

规则

后入先出(Last In First Out,LIFO)

操作

  • push(X):在栈的顶部压入元素X
  • pop(): 从栈的顶部取出元素
  • isEmpty():检查栈是否为空
  • isFull(): 检查栈是否已满

一般情况下,栈还具有 “引用栈顶元素”和”检查栈中是否含有指定数据“的操作

队列(Queue)

规则

先入先出(First In First Out)

操作

  • enqueue(x):在队列的末端添加元素x
  • dequeue(): 从队列开头取出元素
  • isEmpty(): 检查队列是否为空
  • isFull():检查队列是否已满

一般情况下,队列还具有 “引用队列第一个元素”和”检查队列中是否含有指定数据“的操作

应用

逆波兰表示法(栈的应用)

逆波兰表示法是一种将操作符写在操作数后面的方法,又叫后缀表示法,相较于我们日常使用的中缀表示法**,它的优势在于不需要括号

例:$(1+2)\times (5+4) $ ==>>$1\space 2 + 5\space 4 + \times $

  1. 将 1 2 压入栈中
  2. 遇到运算符,从栈中取出两个操作数,按运算符运算,例中为+,将运算结果压入栈中,栈中数据变成了 3
  3. 将 5 4 压入栈中,栈中数据变为了 3 5 4
  4. 遇到操作符+ 取出两个操作数5 4 运算结果为9,压入栈中,栈中变为3 9
  5. 遇到操作符$\times$ 取出3 9 运算结果为27

一个并不完善的简单过程

#include<stdio.h>
#include<stdlib.h>
//本程序仅支持0-9的数字运算
int top,stack[1000];
void push(int x){
    stack[++top]=x;
}
int pop(){
    return stack[top--];
}
int main(){
    char s[1000];
    int i,a,b;
    i=0;
    top=0;
    scanf("%s",s);
    while(s[i]!='\0'){
        if(s[i]=='+'){
            a=pop();
            b=pop();
            push(a+b);
        }else if(s[i]=='-'){
            a=pop();
            b=pop();
            push(a-b);        
            
        }else if(s[i]=='*'){
            a=pop();
            b=pop();
            push(a*b);
        }else if(s[i]=='/'){//整除结果
            a=pop();
            b=pop();
            push(a/b);
        }else
        {
            push(s[i]-48);
        }
        i++;
    }
    printf("%d",pop());
    return 0;
}

运行结果:

队列

现有名称为namei且处理时间为timei的n个任务按照顺序排成一列,
CPU通过循环调度法逐一处理这些任务,每个任务最多处理q ms
(这个时间称为时间片)。如果q ms之后任务尚未处理完毕,那么该任务
将被移动至队伍最末尾,CPU随即开始处理下一个任务
    举个例子,假设q是100,然后有如下任务队列。
    A(150) -- B(80) -- C(200) -- D(200)
    首先A被处理100 ms,然后带着剩余的50 ms移动至队尾
    B(80) -- C(200) -- D(200) -- A(50)
    随后B被处理80 ms,在总计第180 ms时完成处理,从队列中消失
    C(200) -- D(200) -- A(50)
    接下来C被处理100 ms,然后带着剩余的100 ms移动至队尾。
    D(200) -- A(50) -- C(100) 
    之后同理,一直循环到处理完所有任务。
    请编写一个程序,模拟循环调度法。
输入
    输入形式如下
    n q
    name1 time1
    name2 time2
    ...
    namen timen
    第一行输入表示任务数的整数n与时间片的整数q,用一个空格隔开
    接下来n行输入各任务的信息。字符串namei与timei用一个空格隔开。
输出
    按照任务完成的先后顺序输出各任务名以及结束时间,任务名与对应结束时间用空格隔开,
    每一对任务名与结束时间占一行。
限制
    1 ≤n ≤100 000
    1 ≤q ≤1000
    1 ≤timei ≤50 000
    1 ≤字符串namei的长度 ≤10
    1 ≤timei的和 ≤1 000 000 
    
    输入示例                输出示例 
    5 100                    p2 180 
    p1 150                    p5 400
    p2 80                    p1 450
    p3 200                    p3 350
    p4 350                    p4 800
    p5 20 
#include<stdio.h>
#include<stdlib.h>
/*
    以数组实验队列
 */
#define MAX 100005
long tail ,head ; //头尾元素位置
typedef struct queue{
    char name[10];
    long time;

}q;
q Q[MAX];
int isEmpty(){
    if(tail==head) return 1;
    return 0;
}
int isFull(){
    if (tail+1==head) return 1;
    return 0;
}
void enqueue(q p){
    if(!isFull()){
        Q[tail]=p;
        tail=(tail+1)%MAX;
    }
}
q dequeue(){
    q p;
    if(!isEmpty()){
        p=Q[head];
        head=(head+1)%MAX;
        
    }
    return p;
}
int main(){
    tail=head=0;
    long elaps=0;
    int i=0;
    q u;
    long n,qtime;
    scanf("%ld %ld",&n,&qtime);
    while(i<n){
        scanf("%s %ld",u.name,&u.time);
        enqueue(u);
        i++;
    }
    while(!isEmpty()){
        u=dequeue();
        if (u.time-qtime<=0)
        {
            elaps+=u.time;
            printf("%s %ld\n",u.name,elaps);
            continue;
        }
        elaps+=qtime;
        u.time-=qtime;
        enqueue(u);
    }
}

运行结果:

STL(C++标准库)

C++库以提供“模板”为主,是指不必预先制定类型的函数或类。

STL为用户提供了多种名为辅容器(Container)的类,用于管理数据集合。在创建动态数组、表、栈、队列等结构时,只需要定义对应的容器。然后就可以通过调用成员函数或方法使用。

stack

函数名功能复杂度
size()返回栈的元素数O(1)
top()返回栈顶元素O(1)
pop()从栈中取出并删除元素O(1)
push(x)向栈中添加元素xO(1)
empty()当栈为空时返回trueO(1)
#include<iostream>
#include<stack>
using namespace std;
int main()
{
    stack<int> S;
    S.push(1);
    S.push(2);
    S.push(3);
    cout<<"栈的大小:"<<S.size()<<endl;
    cout<<"栈顶元素:"<<S.top()<<endl;
    S.pop();
    cout<<"栈的大小:"<<S.size()<<endl;
    cout<<"栈顶元素:"<<S.top()<<endl;


}

运行结果:

通过栈模板实现逆波兰表示

#include<iostream>
#include<stack>
using namespace std;
int main()
{
    int i=0,a,b;
    string s;
    stack<int> stk;
    cin>>s;
    while (s[i]!='\0')
    {

        switch(s[i]){
            case '+':
                a=stk.top();stk.pop();
                b=stk.top();stk.pop();
                stk.push(a+b);
                break;
            case '-':
                a=stk.top();stk.pop();
                b=stk.top();stk.pop();
                stk.push(a-b);
                break;
            case '*':
                a=stk.top();stk.pop();
                b=stk.top();stk.pop();
                stk.push(a*b);
                break;
            default:
                stk.push(s[i]-48);
        }
        i++;
    }
    cout<<stk.top()<<endl;
    return 0;
}

运行结果:

queue

函数名功能复杂度
size()返回队列中的元素数目O(1)
front()返回队头的元素O(1)
pop()从队列中取出并删除元素O(1)
push(x)在队列中添加元素xO(1)
empty()当队列为空时返回trueO(1)
#include<iostream>
#include<queue>
#include<string>
using namespace std;
int main()
{
   queue<string> que;
   que.push("red");
   que.push("yellow");
   que.push("yellow");
   que.push("blue");

   cout<<que.front()<<"\tnow size:"<<que.size()<<endl;
   que.pop();

   cout<<que.front()<<"\tnow size:"<<que.size()<<endl;
   que.pop();
   
   cout<<que.front()<<"\tnow size:"<<que.size()<<endl;
   que.pop();

   cout<<que.front()<<"\tnow size:"<<que.size()<<endl;
   que.pop();

   return 0;

}

运行结果:

用标准库模板实现上面的队列

#include<iostream>
#include<queue>
#include<string>
using namespace std;
int main()
{
    queue<pair<string,int>> que;
    string name;
    int n,q,t;
    int elaps=0;
    cin>>n>>q;
    while(n--){
        cin>>name>>t;
        que.push(make_pair(name,t));
    }
    pair<string,int> u;
    while(!que.empty())
    {
        u=que.front();
        que.pop();
        if(u.second-q<=0){
            elaps+=u.second;
            cout<<u.first<<' '<<elaps<<endl;
            continue;
        }
        u.second-=q;
        elaps+=q;
        que.push(u);
    }

   return 0;

}

运行结果:

pair是保存对数值的结构体模板,声明时需要在<>中指令两个数据结构。make_pair用于生成一对数值,第一个元素通过first访问,第二个通过second访问

vector

可以在添加元素是增加长度的数组成为动态数组或可变长数组。相对地,必须事先指定长度的是静态数组

STL中的vector(向量)实现了动态数组

函数名功能复杂度
size()返回向量的元素数目O(1)
push_back(x)在向量的末尾添加xO(1)
pop_back()删除向量的最后一个元素O(1)
begin()返回指向向量开头的迭代器O(1)
end()返回指向向量结尾的迭代器O(1)
insert(p,x)在向量中迭代器p指向的位置插入xO(n)
erase(p)删除向量中迭代器p指向的元素O(n)
clear()删除向量中所有元素O(n)
#include<iostream>
#include<vector>
#include<string>
using namespace std;
void output(vector<double> v){
    
    for (int i = 0; i < v.size(); i++)
    {
        cout<<v[i]<<" ";
    }
    cout<<endl;
}
int main()
{
    vector<double> vec;
    vec.push_back(0.1);
    vec.push_back(0.2);
    vec.push_back(0.3);
    vec[2]=0.4;
    output(vec);
    
    vec.insert(vec.begin()+2,0.8);
    output(vec);

    vec.erase(vec.begin()+1);
    output(vec);

    return 0;

}

输出结果:

list

list是一个双向列表

函数名功能复杂度
size()返回向量的元素数目O(1)
push_back(x)在向量的末尾添加xO(1)
push_front(x)在向量的开头添加xO(1)
pop_back()删除向量的最后一个元素O(1)
pop_front()删除向量的开头元素O(1)
begin()返回指向向量开头的迭代器O(1)
end()返回指向向量结尾的迭代器O(1)
insert(p,x)在向量中迭代器p指向的位置插入xO(1)
erase(p)删除向量中迭代器p指向的元素O(1)
clear()删除向量中所有元素O(n)
#include<iostream>
#include<list>
#include<string>
using namespace std;

int main()
{
    list<char> li;
    li.push_back('b');  //[b]
    li.push_front('a'); //[ab]
    li.push_back('c');  //[abc]
    cout<<li.front();   //a
    cout<<li.back();    //c
    li.pop_front();     //[bc]
    li.push_back('d');  //[bcd]
    cout<<li.front();   //b
    cout<<li.back();    //d
    return 0;

}

运行结果:

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

发表评论

email
web

全部评论 (暂无评论)

info 还没有任何评论,你来说两句呐!