数据结构与算法分析-C++描述第3章表、栈和队列

1.表

下标从0开始，到n-1结束的序列，叫做大小为n的表。
STL中的表：
vector-索引快( $O(1)$ )，在非末尾的地方插入和删除慢。
list-双向链表，插入和删除快，索引慢。
这两个查找都慢。

方法：
对所有容器都适用的方法：
size() 返回元素个数
clear() 删除所有元素
empty() 判断是否为空

适用于vector和list的方法：
push_back(x) 在表末插入元素x
pop_back() 删除表末对象
back() 返回表末对象
front() 返回表头对象

只适用于list，不适用于vector的方法：
push_front(x) 在表头插入元素x
pop_front() 删除表头对象

只适用于vector，不适用于list的方法：
vector重载了[ ]运算符但list没有
capacity() 返回vector最多能装多少元素
reserve(x) 设置vector最多能装x个元素，但这些元素还未初始化
resize(x) 设置vector最多能装x个元素，且这些元素已经被默认构造函数初始化了

两者都适用，但需要使用迭代器的方法：
insert(iterator,x) 在iterator的前面插入x，返回插入的地方，list快于vector
erase(iterator) 删掉iterator指向的对象，返回删掉的后面，list快于vector，删完了iterator就不存在了
erase(iterator1,iterator2) 删掉[iterator1,iterator2)之间的对象

2.vector的实现

#pragma once
template<typename Object>
class Vector {
private:
    int thesize;   //容量
    int thecapacity;  //最大容量
    Object *objects;  //指针
public:
    enum { SPARE_CAPACITY = 16 }; //容器的最大容量
    explicit Vector(int initsize = 0) //构造函数
        : thesize(initsize), thecapacity(initsize + SPARE_CAPACITY)
    {
        objects = new Object[thecapacity];
    }
    Vector(const Vector & rhs) : objects(NULL)//拷贝构造函数
    {
        operator = (rhs); //*this.operator = (rhs) 相当于*this = rhs
    }
    ~Vector() {
        delete[] objects;
    }//析构函数，要delete掉new出来的objects
    const Vector & operator = (const Vector & rhs) { //重载的赋值运算符
        if (this != &rhs) { //自赋值检测
            delete[] objects;
            thesize = rhs.size();
            thecapacity = rhs.thecapacity();
            objects = new Object[capacity()];
            for (int k = 0; k < size(); k++)
                objects[k] = rhs.objects[k]; //在赋值之前要重新更改容量
        }
        return *this;
    }
    void resize(int newsize) { //重新设置容量
        if (newsize > thecapacity)
            reserve(newsize * 2 + 1);
        thesize = newsize;
    }
    void reserve(int newcapacity) { //重新设置最大容量
        if (newcapacity > thesize) return;
        Object *oldarray = objects;
        objects = new Object[newcapacity];
        for (int k = 0; k < thesize; k++) {
            objects[k] = oldarray[k];
        }
        thecapacity = newcapacity;
        delete[] oldarray;
    }
    Object & operator[](int index) {//重载的[]运算符
        return objects[index];
    }
    bool empty() const {//判断Vector是否为空
        return size() == 0;
    }
    int size() const {//返回容量
        return thesize;
    }
    int capacity() const {//返回最大容量
        return thecapacity;
    }
    void push_back(const Object & x) {//添加末尾元素
        if (thesize == thecapacity) reserve(2 * thecapacity + 1);
        objects[thesize++] = x;
    }
    void pop_back() { //删除末尾元素
        thesize--;
    }
    const Object & back() const { //返回末尾元素
        return objects[thesize - 1];
    }
    //把指针命名成迭代器
    typedef Object* iterator;
    typedef const Object* const_iterator;

    iterator begin() {//begin()迭代器
        return &objects[0];
    }

    const_iterator begin() const {
        return &objects[0];
    }

    iterator end() {//end()迭代器
        return &objects[size()];
    }

    const_iterator end() const {
        return &objects[size()];
    }
};

3.链表的实现

这本书上的实现太复杂了，先用之前课件上的，以后有时间再补。
$(1)$ 单向链表

#include<iostream>
using namespace std;
struct Node {
    int data;
    Node *next;
};
Node* creat() {//创建链表并返回头节点
    Node *head, *tail, *pnew;
    //*tail：尾结点，tail->next:尾指针
    //头节点是第0个结点
    head = new Node;
    head->next = NULL;  //堵住最后
    tail = head;  //尾结点和头结点重合
    while (1) {
        pnew = new Node;
        cin >> pnew->data;
        if (pnew->data == -1) {
            delete pnew;
            break;
        }
        tail->next = pnew;  //让尾指针指向新节点
        tail = pnew;  //让新节点变成尾结点
        pnew->next = NULL;  //堵住最后
        //上述三行加起来实现了把一个新节点挂在原来尾结点的后面
    }
    return head;
}
void insert(Node *head, Node *pnew, int ith) {//把某个节点插入到第ith个结点的后面
    Node *p = head; 
    for (int i = 0; i < ith && p!=NULL ; i++) p = p->next;   //跑完以后p就到了第ith个结点处了
    if (p == NULL)
    {
        cout << "Error!" << endl;
        return;
    }
    pnew->next = p->next;   //将p的后继节点（第ith+1个结点）设为pnew的后继节点
    p->next = pnew;
    //将pnew设为p的后继节点
    //注意此处的顺序不能颠倒，否则后面的链表就都丢了
}

void del(Node *head, int ith) {  //删除第ith个结点
    if (ith == 0) { //不能删头节点
        cout << "Error!" << endl;
        return;
    }
    Node *p = head, *q;
    for (int i = 1; i < ith && p->next != NULL; i++) p = p->next;
    //注意此处是要让i=ith-1，来删掉p后面的那个结点，故判断应为p->next!=NULL
    if (p->next == NULL) {
        cout << "Error!" << endl;
        return;
    }
    q = p->next; //让q指向要删的结点
    p->next = q->next;  //将要删的结点的后置结点设为p的后置结点
    delete q;
}

void show(Node *head) { //输出整个链表
    Node *p;
    for (p = head->next; p != NULL; p = p->next) {  //遍历链表，注意不要从头节点开始
        cout << p->data << ' ';
    }
    cout << endl;
}

void clear(Node* head) {  //销毁整个链表
    Node *p = new Node;
    while (head->next != NULL) {
        p = head;
        head = p->next;
        delete p;
    }
}


int main() {
    Node *head = creat();
    show(head);
    //这里有个坑，如果要添加新结点的话必须用下面这种new的方法,从堆里分配*p的空间
    //不能把一个Node结构的地址传给insert函数，否则del的时候会delete一个栈空间，从而报错
    Node *p = new Node;
    p->data = 1;
    p->next = NULL;
    insert(head, p, 2);
    show(head);
    del(head, 3);
    show(head);
    clear(head);
    return 0;
}

$(2)双向链表$
在单向链表上稍作修改，又添加了逆序输出的函数。

#include<iostream>
using namespace std;
struct Node {
    int data;
    Node *next;
    Node *previous;
};
Node* creat() {//创建链表并返回头节点
    Node *head, *tail, *pnew;
    //*tail：尾结点，tail->next:尾指针
    //头节点是第0个结点
    head = new Node;
    head->next = NULL;  //堵住最后
    head->previous = NULL;
    tail = head;  //尾结点和头结点重合
    while (1) {
        pnew = new Node;
        cin >> pnew->data;
        if (pnew->data == -1) {
            delete pnew;
            break;
        }
        pnew->previous = tail;
        tail->next = pnew;  //让尾指针指向新节点
        tail = pnew;  //让新节点变成尾结点
        pnew->next = NULL;  //堵住最后
        //上述三行加起来实现了把一个新节点挂在原来尾结点的后面
    }
    return head;
}
void insert(Node *head, Node *pnew, int ith) {//把某个节点插入到第ith个结点的后面
    Node *p = head;
    for (int i = 0; i < ith && p != NULL; i++) p = p->next;   //跑完以后p就到了第ith个结点处了
    if (p == NULL)
    {
        cout << "Error!" << endl;
        return;
    }
    pnew->previous = p;
    pnew->next = p->next;
    p->next->previous = pnew;
    p->next = pnew;
    //注意此处的顺序不能颠倒，否则后面的链表就都丢了
}

void del(Node *head, int ith) {  //删除第ith个结点
    if (ith == 0) { //不能删头节点
        cout << "Error!" << endl;
        return;
    }
    Node *p = head, *q;
    for (int i = 1; i < ith && p->next != NULL; i++) p = p->next;
    //注意此处是要让i=ith-1，来删掉p后面的那个结点，故判断应为p->next!=NULL
    if (p->next == NULL) {
        cout << "Error!" << endl;
        return;
    }
    q = p->next; //让q指向要删的结点
    p->next = q->next;  //将要删的结点的后置结点设为p的后置结点
    q->next->previous = p;
    delete q;
}

void show(Node *head) { //输出整个链表
    Node *p;
    for (p = head->next; p != NULL; p = p->next) {  //遍历链表，注意不要从头节点开始
        cout << p->data << ' ';
    }
    cout << endl;
}

void revshow(Node *tail) {
    Node *p;
    for (p = tail; p->previous != NULL; p = p->previous) {
        cout << p->data << ' ';
    }
    cout << endl;
}


void clear(Node* head) {  //销毁整个链表
    Node *p = new Node;
    while (head->next != NULL) {
        p = head;
        head = p->next;
        delete p;
    }
}


int main() {
    Node *head = creat();
    show(head);
    //这里有个坑，如果要添加新结点的话必须用下面这种new的方法,从堆里分配*p的空间
    //不能把一个Node结构的地址传给insert函数，否则del的时候会delete一个栈空间，从而报错
    Node *tail;
    for (tail = head; tail->next != NULL; tail = tail->next);
    revshow(tail);
    Node *p = new Node;
    p->data = 1;
    p->next = NULL;
    insert(head, p, 2);
    revshow(tail);
    del(head, 3);
    revshow(tail);
    clear(head);
    return 0;
}

$(3)$ 循环链表
就是让链表的尾指针指向头节点。

4.栈

插入和删除操作只能在表末进行的表，这里把表末叫做栈顶。
push（进栈），pop（出栈），后进先出。
栈可以由stack，vector或list实现。
应用：
$(1)$ 判断括号有没有匹配：
‘(’后面一定紧跟着‘)’,[],{}也同理
栈可以用来保存后面的状态。

#include<iostream>
#include<stack>
#include<string>
#include<map>
using namespace std;
map<char, char> judge;
stack<char> test;
int main() {
    judge[')'] = '(';
    judge[']'] = '[';
    judge['}'] = '{';
    string input;
    cin >> input;
    int len = input.size();
    for (int i = 0; i < len; i++) {
        if (judge.find(input[i]) == judge.end())
            test.push(input[i]);
        else if (test.empty()) {
            cout << "No";
            return 0;
        }
        else if (test.top() != judge[input[i]]){
            cout << "No";
            return 0;
        }
        else test.pop();
    }
    if (test.empty()) cout << "Yes";
    else cout << "No";
    return 0;
}

$(2)$ 后缀表达式求值（整数）
碰到运算符就让栈顶的两个元素出栈做运算。

#include<iostream>
#include<stack>
#include<string>
#include<cctype>
using namespace std;
string input;
stack<int> cal;
int rnum;
int lnum;
int main() {
    getline(cin, input);
    int len = input.size();
    for (int i = 0; i < len; i += 2) {
        switch (input[i]) {
        case '+':
            rnum = cal.top();
            cal.pop();
            lnum = cal.top();
            cal.pop();
            cal.push(lnum + rnum);
            break;
        case'-':
            rnum = cal.top();
            cal.pop();
            lnum = cal.top();
            cal.pop();
            cal.push(lnum - rnum);
            break;
        case'*':
            rnum = cal.top();
            cal.pop();
            lnum = cal.top();
            cal.pop();
            cal.push(lnum * rnum);
            break;
        case'/':
            rnum = cal.top();
            cal.pop();
            lnum = cal.top();
            cal.pop();
            cal.push(lnum / rnum);
            break;
        default:
            cal.push(input[i] - '0');
        }
    }
    cout << cal.top();
    return 0;
}

$(3)$ 前缀表达式求值（浮点数）
http://bailian.openjudge.cn/practice/2694/
先翻转成后缀表达式，注意减和除的顺序。

#include<iostream>
#include<stack>
#include<string>
#include<sstream>
#include<algorithm>
#include<iomanip>
using namespace std;
stack<double> cal;
string in;
string input[100000];
double rnum;
double lnum;
double temp;
int main() {
    getline(cin, in);
    stringstream ss;
    ss << in;
    int num = 0;
    while (ss >> input[num++]);
    reverse(input, input + num);
    for (int i = 1; i < num; i++) {
        switch (input[i][0]) {
        case '+':
            rnum = cal.top();
            cal.pop();
            lnum = cal.top();
            cal.pop();
            cal.push(rnum + lnum);
            break;
        case'-':
            rnum = cal.top();
            cal.pop();
            lnum = cal.top();
            cal.pop();
            cal.push(rnum - lnum);
            break;
        case'*':
            rnum = cal.top();
            cal.pop();
            lnum = cal.top();
            cal.pop();
            cal.push(rnum * lnum);
            break;
        case'/':
            rnum = cal.top();
            cal.pop();
            lnum = cal.top();
            cal.pop();
            cal.push(rnum / lnum);
            break;
        default:
            stringstream stemp;
            stemp << input[i];
            stemp >> temp;
            cal.push(temp);
            break;
        }
    }
    cout << fixed << setprecision(6) << cal.top();
    return 0;
}

$(4)$ 中缀表达式转后缀表达式
比较 $a+b*c$ 和 $(a+b)*c$ ，前者的后缀表达式为a b c * +，后者为a b + c *，显然输出字母的顺序跟运算的优先级有关， $（> * > +$ ,低级运算符碰上高级运算符，不能马上输出；反之可以，因为高级肯定算完了。把中缀表达式读入：

如果遇到数字，立即输出；如果遇到运算符和左括号，从栈中输出并弹出元素直到栈顶元素的优先级比遇到的运算符低，把遇到的运算符压入栈中；如果遇到右括号，则将栈内元素输出并弹出，直到栈顶为左括号，把左括号弹出但不输出。最后，将栈里的所有元素全部弹出。

#include<iostream>
#include<stack>
#include<string>
#include<cctype>
#include<map>
using namespace std;
string input;
map<char, int> prior;
stack<int> cal;
int main() {
    prior['('] = 3;
    prior['*'] = prior['/'] = 2;
    prior['+'] = prior['-'] = 1;
    getline(cin, input);
    int len = input.size();
    for (int i = 0; i < len; i++) {
        if (isspace(input[i])) continue;
        if (isalnum(input[i])) cout << input[i] << ' ';
        else{
            if (input[i] == ')') {
                while (cal.top() != '(') {
                    cout << char(cal.top()) << ' ';
                    cal.pop();
                }
                cal.pop();
            }
            else {
                while (!cal.empty() && prior[input[i]] <= prior[cal.top()]) {
                    if (cal.top() == '(') break;//左括号里面的运算符输出到左括号为止
                    cout << char(cal.top()) << ' ';
                    cal.pop();
                }
                cal.push(input[i]);
            }
        }
    }
    while (!cal.empty()) {
        cout << char(cal.top()) << ' ';
        cal.pop();
    }
    return 0;
}

$(5)$ 中缀表达式求值：结合 $(4)$ 和 $(2)$ 即可

5.队列

先进先出的容器。
入队：在队尾插入一个元素，出队：在队头删除一个元素。
双端队列：队头和队尾都可以修改元素。
STL deque的方法：
比vector多了front(),pop_front(),push_front(x)。
重载了[]运算符。
应用：广度优先搜索
框架：

BFS()
{
    初始化队列
    while(队列不为空)
    {
        取队首结点扩展，并将扩展出的结点放入队尾
        队首结点出队
                必要时要记住每个结点的父结点(搞个结构体当队列的)
    }
}

例题：洛谷P1443

最后编辑于：2019.09.26 12:58:50

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 216,193评论 6赞 498
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,306评论 3赞 392
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 162,130评论 0赞 353
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,110评论 1赞 292
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,118评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,085评论 1赞 295
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,007评论 3赞 417
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,844评论 0赞 273
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,283评论 1赞 310
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,508评论 2赞 332
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,667评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,395评论 5赞 343
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,985评论 3赞 325
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,630评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,797评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,653评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,553评论 2赞 352

数据结构与算法分析-C++描述 第3章 表、栈和队列

1.表

2.vector的实现

3.链表的实现

4.栈

5.队列

推荐阅读更多精彩内容

数据结构与算法分析-C++描述第3章表、栈和队列