数据结构合集

这篇文章主要记录各种数据结构的基本操作以及一些相关题目。

队列

队尾插入，队头删除。

基本操作

顺序队列

队列的类型定义：

#define MAXLEN 1000
struct SeqQueue{
    int front, rear;
    int data[MAXLEN];
};

队列的初始化：

void init(SeqQueue &q){
    q.front = q.rear = 0;
}

判断队列是否为空：

bool isEmpty(SeqQueue q){
    return q.front == q.rear;
}

判断是否队满：

bool isFull(SeqQueue q){
    return q.rear == MAXLEN;
}

入队操作：

bool Push(SeqQueue &q, int t){
    if(isFull(q)) return false;
    q.data[q.rear++] = t;
    return true;
}

出队操作：

bool Pop(SeqQueue &q, int &dt){
    if(isEmpty(q)) return false;
    dt = q.data[q.front++];
    return true;
}

循环队列

#define MAXLEN 100
struct CycleQueue{
    int data[MAXLEN];
    int front, rear;
};
void init(CycleQueue &q){
    q.front = q.rear = 0;
}
bool isEmpty(CycleQueue q){
    return q.rear == q.front;
}
bool isFull(CycleQueue &q){
    return (q.rear + 1) % MAXLEN == q.front;
}
bool Push(CycleQueue &q, int t){
    if(isFull(q)) return false;
    q.data[q.rear++] = t;
    return true;
}
bool Pop(CycleQueue &q, int &dt){
    if(isEmpty(q)) return false;
    dt = q.data[q.front];
    q.front = (q.front + 1) % MAXLEN;
    return true;
}

HDU1276

方法一：（没用队列）

注意：这里是说不超过3，也就是可以小于3，所以不是只剩下3个时就停止报数，而是把那一趟报完，剩下几个就输出几个。

典型的如：输入4，输出1 3

#include <iostream>
using namespace std;

int n;
int d[5005];

void init(){
    for(int i = 1; i <= n; i++)
        d[i] = i;
}

int main(){
    int N;
    while(cin >> N){
        while(N--){
            cin >> n;
            init();
            int c = 0, cnt = n;
            while(cnt > 3){
                if(!c){
                    int f = 0;
                    for(int i = 1; i <= n; i++){
                        if(d[i]){
                            if(f){
                                d[i] = 0;
                                cnt--;
                            }
                            f ^= 1;
                        }
                    }
                    c ^= 1;
                }
                else{
                    int f = 2;
                    for(int i = 1; i <= n; i++){
                        if(d[i]){
                            if(f){
                                f--;
                            }
                            else{
                                d[i] = 0;
                                cnt--;
                                f = 2;
                            }
                        }
                    }
                    c ^= 1;
                }
            }
            int j = 0;
            for(int i = 1; i <= n; i++){
                if(d[i]){
                    j = i;
                    cout << d[i];
                    break;
                }
            }
            if(j){
                for(int i = j + 1; i <= n; i++){
                    if(d[i]){
                        cout << " " << d[i];
                    }
                }
            }
            cout << endl;
        }
    }
    return 0;
}

方法二：（队列）

利用两个队列来模拟整个报数方式，一个队列存放初始士兵，另一个存放一次报数后剩下的士兵，两个队列循环，直到最后队列中人数小于4人时，停止报数。

栈

顺序栈的基本操作

#define MAXLEN 100
struct Stack{
    int data[MAXLEN];
    int top;
};
bool isEmpty(Stack s){
    return s.top == 0;
}
bool isFull(Stack s){
    return s.top == MAXLEN;  //栈顶指针s.top指向的是栈顶元素位置的上一个
}
bool Push(Stack &s, int t){
    if(isFull(s)) return false;
    s.data[s.top++] = t;
    return true;
}
bool Pop(Stack &s, int &dt){  //或者干脆写个GetTop(int &dt)
    if(isEmpty(s)) return false;
    dt = s.data[s.top--];
    return true;
}

栈的应用

表达式求值

数制转换