分类目录归档:白皮书

ACM-数据结构

点击量:19

{% blockquote 本文出自 http://svtter.com svtter.com %}
本文可以随意转载,但是转载请保留本信息.

Uvaoj的判题效率不是很高。。所以直接开下一章节。题目慢慢刷,先过一遍书,不然书都看不完了TAT。。

6.1 栈和队列

卡片游戏,回顾了下队列和STL

#include <stdio.h>
#include <queue>
#include <iostream>
using namespace std;
const int maxn = 100;
int q[maxn];
void ace()
{
    void ace2(int);
    int n;
    scanf("%d", &n);
    //init
    for(int i = 0; i < n; i++) q[i] = i+1;
    int front , rear;
    front = 0, rear = n;
    // 队列不为空
    while(front != rear)
    {
        printf("%d ", q[front++]);
        q[rear++] = q[front++];
    }
    printf("\n");
    ace2(n);
}
// STL 
void ace2(int n)
{
    queue <int> q;
    for(int i = 1; i <= n; i++) q.push(i);
    while(!q.empty())
    {
        printf("%d ", q.front());
        q.pop();
        q.push(q.front());
        q.pop();
    }
    printf("\n");
}
int main(int argc, const char *argv[])
{
    ace();
    return 0;
}

6.1.2栈的STL

#include <stdio.h>
#include <iostream>
#include <stack>
using namespace std;
const int maxn = 200;
int s[maxn];
void ace()
{
    int n;
    int a[maxn];
    int temp, top;
    int p, set;
    while(~scanf("%d", &n))
    {
        top = -1, p = 0, set = 1;
        for(int i = 0; i < n; i++) a[i] = i+1;
        for(int i = 0; i < n; i++)
        {
            scanf("%d", &temp);
            // 如果无法完成序列,只吸收输入值
            if(!set) continue;
            if(temp == a[p]) p++;
            else if(top != -1 && temp == s[top]) top--;
            else while(temp != a[p])
                {
                    s[++top] = a[p];
                    p++;
                    if(p == n)
                    {
                        set = 0;
                        break;
                    }
                }
        }
        if(set) printf("Yes");
        else printf("No");
        printf("\n");
    }
}
void ace2()
{
    int n;
    int a[maxn];
    int temp, p, set;
    while(~scanf("%d", &n))
    {
        stack <int> s;
        p = 0, set = 1;
        for(int i = 0; i < n; i++) a[i] = i+1;
        for(int i = 0; i < n; i++)
        {
            scanf("%d", &temp);
            // 如果无法完成序列,只吸收输入值
            if(!set) continue;
            if(temp == a[p]) p++;
            else if(!s.empty() && temp == s.top()) s.pop();
            else while(temp != a[p])
                {
                    s.push(a[p]);
                    p++;
                    if(p == n)
                    {
                        set = 0;
                        break;
                    }
                }
        }
        if(set) printf("Yes");
        else printf("No");
        printf("\n");
    }
}
int main()
{
    ace2();
    return 0;
}

6.2 链表和随机数发生器

链表的相关部分就不在赘述了。主要是随机数发生器。
很多人喜欢用rand()%N得到一个随即整数,但是n大于RAND_MAX的时候,就不好用了。
于是使用(double)rand()/RAND_MAX,然后在扩大n-1倍以后四舍五入,再+1

例如这样

// 获取1~m的随即整数
int random(int m)
{
    double a = (double)rand() / RAND_MAX;
    return (int) (a * (m-1) + 0.5);
}

6.3 二叉树