第四周做题总结_数据结构

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;
}