第四周做题总结_数据结构_栈与应用

id:144 A. 前驱后继–双向链表（线性结构）

题目描述

在双向链表中，A有一个指针指向了后继节点B，同时，B又有一个指向前驱节点A的指针。这样不仅能从链表头节点的位置遍历整个链表所有节点，也能从链表尾节点开始遍历所有节点。

对于给定的一列数据，按照给定的顺序建立双向链表，按照关键字找到相应节点，输出此节点的前驱节点关键字及后继节点关键字。

输入

第一行两个正整数n（代表节点个数），m（代表要找的关键字的个数）。

接下来输入n个整数为关键字key（数据保证关键字在数列中没有重复）。

接下来有m个要查找的关键字，每个占一行。

输出

对给定的每个关键字，输出此关键字前驱节点关键字和后继节点关键字。如果给定的关键字没有前驱或者后继，则不输出。给定关键字为每个输出占一行。

输入样例

10 3
1 2 3 4 5 6 7 8 9 0
3
1
0

输出样例

2 4
2
9

题解

• 定义两个类，一个是链表结点类，一个是带头结点的单链表定义，在链表结点类定义中，有数据和指向下一个结点的指针这两个成员，然后有一个构造函数，在带头结点的链表类中，有头节点的指针，链表的长度这两个成员，还有构造和析构，将数据插入链表和输出的函数
• 我们在类的输出函数中实现题目的要求，首先定义三个指针，一个指针指向链表的头节点，代表前驱指针，一个指针指向链表头节点的下一个指针，代表当前节点，另一个指针先初始化为指向头结点的下一个结点的指针，方便后面作为中间变量作为比较，也是为了在循环过程中不改变指针的指向，一个循环，条件是当前指针不为空，也就是当链表遍历完后退出循环，在循环中，定义一个变量判断当前循环的前驱指针指向的数字是否输出，接着一个判断，如果当前指针指向的位置的数字与输入进来的需要查找的参数一样，而且前驱指针不指向头节点，则输出前驱指针指向的位置的数字，然后将判断变量值改变，表示前驱数字已输出，接着判断当前节点的后一个节点是否为空，也就是后继节点是否为空，如果不为空，则将一个指针指向后继指针，如果前驱指针已输出，则后继指针输出时前面要添加一个空格分开，否则不用输出，然后更新前驱指针指向当前节点，当前指针更新为指向下一个结点的指针

代码实现

#include <iostream>
using namespace std;
#define ok 0
#define error -1

//链表结点类定义
class ListNode
{
public:
    int data;
    ListNode* next;
    ListNode() { next = NULL; }
};

//带头结点的单链表定义
class LinkList
{
public:
    ListNode* head;
    int len;
    //操作定义
    LinkList();
    ~LinkList();
    int LL_insert(int i, int item); //把数值item插入第i个位置
    void LL_display(int k); //输出单链表的内容
};

LinkList::LinkList()
{
    head = new ListNode();
    len = 0;
}

LinkList::~LinkList()
{
    ListNode* p, * q;
    p = head;
    while (p != NULL)
    {
        q = p;
        p = p->next;
        delete q;
    }
    len = 0;
    head = NULL;
}

int LinkList::LL_insert(int i, int item) //把数值item插入第i个位置
{
    if (i < 1 || i > len + 1)
    {
        return error;
    }
    ListNode* p = head;
    int j = 0;
    while (p && (j < i - 1))
    {
        p = p->next;
        j++;
    }
    if (!p || (j > i - 1))
    {
        return error;
    }
    ListNode* s = new ListNode();
    s->data = item;
    s->next = p->next;
    p->next = s;
    len++;
    return ok;
}

void LinkList::LL_display(int k)
{
    ListNode* preP = head;
    ListNode* p = head->next;
    ListNode* s = p;

    while (p)
    {
        int f = 0;
        //找到
        if (p->data == k)
        {
            if (preP != head)
            {
                cout << preP->data;
                f = 1;
            }
            if (p->next != NULL)
            {
                s = p->next;
                if (f == 1)
                {
                    cout << " ";
                }
                cout << s->data << endl;
            }
            else
            {
                cout << endl;
            }
            break;
        }
        preP = p;
        p = p->next;
    }
}

int main()
{
    int n, m, i, key, data;
    cin >> n >> m;
    LinkList list;

    for (i = 0; i < n; i++)
    {
        cin >> data;
        list.LL_insert(i + 1, data);
    }

    for (i = 0; i < m; i++)
    {
        cin >> key;
        list.LL_display(key);
    }

    return 0;
}

id:37 B. DS堆栈–逆序输出

题目描述

C++中已经自带堆栈对象stack，无需编写堆栈操作的具体实现代码。

本题目主要帮助大家熟悉stack对象的使用，然后实现字符串的逆序输出

输入一个字符串，按字符按输入顺序压入堆栈，然后根据堆栈后进先出的特点，做逆序输出

stack类使用的参考代码

• 包含头文件：#include <stack>
• 创建一个堆栈对象s（注意stack是模板类）：stack <char> s; //堆栈的数据类型是字符型
• 把一个字符ct压入堆栈：s.push(ct);
• 把栈顶元素弹出：s.pop();
• 获取栈顶元素，放入变量c2：c2 = s.top();
• 判断堆栈是否空：s.empty()，如果为空则函数返回true，如果不空则返回false

输入

第一行输入t，表示有t个测试实例
第二起，每一行输入一个字符串，注意字符串不要包含空格

字符串的输入可以考虑一下代码：

#include <string>

int main()

{ string str;

  Int len;

  cin>>str; //把输入的字符串保存在变量str中

  len = str.length()  //获取输入字符串的长度

}

输出

每行逆序输出每一个字符串

输入样例

2
abcdef
aabbcc

输出样例

fedcba
ccbbaa

题解

代码实现

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main()
{
    int t, i, len, j;
    char ch;

    string str;
    stack<char> s; //堆栈的数据类型是字符型
    cin >> t;
    ch = getchar();

    for (i = 0; i < t; i++)
    {
        getline(cin, str);
        len = str.length();
        for (j = 0; j < len; j++)
        {
            s.push(str[j]);
        }
        while (!s.empty())
        {
            cout << s.top();
            s.pop();
        }
        cout << endl;
    }

    return 0;
}