习题答案目录:https://www.cnblogs.com/Mered1th/p/10485695.html
第9章 顺序容器
练习9.1
a.list,需要按字典序插入,可能插入位置在中间
b.deque,需要在头部和尾部操作
c.vector
练习9.2
list<deque<int>> li;
练习9.4
bool findInt(vector<int> &vec, int x) {
for (auto i : vec) {
if (i == x) {
return true;
}
}
return false;
}
练习9.5
int findInt(vector<int> &vec, int x) {
for (auto i : vec) {
if (i == x) {
return x;
}
}
return -1;
}
练习9.6
改成 iter1!=iter2
练习9.7
vector<int>::size_type;
练习9.8
list<string>::const_iterator;
list<string>::iterator;
练习9.9
begin返回容器的iterator类型
cbegin返回容器的const_iterator类型
练习9.10
#include<string>
#include<vector>
#include<list>
#include<iostream>
using namespace std;
int main() {
list<int> li(5, 3);
vector<int> ivec(5, 5);
vector<double> dvec(li.begin(), li.end());
for (auto i : dvec) {
cout << i << " ";
}
cout << endl;
vector<double> dvec2(ivec.begin(), ivec.end());
for (auto i : dvec2) {
cout << i << " ";
}
cout << endl;
system("pause");
return 0;
}
练习9.14
list<const char *> oldli = { "a","an","the" };
vector<string> svec;
svec.assign(oldli.begin(), oldli.end());
练习9.15
bool isEquel(vector<int> &a, vector<int> &b) {
if (a == b) return true;
else return false;
}
练习9.16
bool isEquel(vector<int> &a, list<int> &b) {
vector<int> c(b.begin(), b.end());
if (a == c) return true;
else return false;
}
练习9.18
#include<iostream>
#include<string>
#include<deque>
using namespace std;
int main() {
string s;
deque<string> ans;
while (cin >> s) {
ans.push_back(s);
}
for (auto it = ans.begin();it != ans.end();++it) {
cout << *it << endl;
}
system("pause");
return 0;
}
练习9.19
将deque改为list即可。
#include<iostream>
#include<string>
#include<deque>
#include<list>
using namespace std;
int main() {
string s;
list<string> ans;
while (cin >> s) {
ans.push_back(s);
}
for (auto it = ans.begin();it != ans.end();++it) {
cout << *it << endl;
}
system("pause");
return 0;
}
练习9.20
#include<iostream>
#include<deque>
#include<list>
using namespace std;
int main() {
list<int> ori = { 1,2,3,4,5,6 };
deque<int> odd, even;
for (auto i : ori) {
if (i % 2) {
even.push_back(i);
}
else {
odd.push_back(i);
}
}
for (auto i : odd) {
cout << i << " ";
}
cout << endl;
for (auto i : even) {
cout << i << " ";
}
system("pause");
return 0;
}
练习9.22
#include<iostream>
#include<string>
#include<vector>
using namespace std;
void func(vector<int> &iv, int some_val) {
int extra = 0;
vector<int>::iterator iter = iv.begin();
while (iter != (iv.begin() + iv.size() / 2 + extra)) {
if (*iter == some_val) {
iter = iv.insert(iter, 2 * some_val);
++extra;
++iter;
}
++iter;
}
}
int main() {
vector<int> iv = { 1,2,3,4 };
func(iv, 2);
for (auto i : iv) {
cout << i << " ";
}
system("pause");
return 0;
}
练习9.24
#include<iostream>
#include<vector>
using namespace std;
int main() {
vector<int> vec;
int a = vec.at(0),
b = vec[0],
c = vec.front();
auto d = vec.begin();
cout << "a: " << a << endl;
cout << "b: " << b << endl;
cout << "c: " << c << endl;
cout << "d: " << *d << endl;
system("pause");
return 0;
}
练习9.25
如果elem1与elem2相等,则一个元素都不会删除。
如果elem2是尾后迭代器,则会从elem1元素删除到最后一个元素。
如果elem1与elem2都是尾后迭代器,则一个元素都不会删除。
练习9.26
#include<vector>
#include<iostream>
#include<list>
using namespace std;
int main() {
int ia[] = { 0,1,1,2,3,5,8,13,21,55,89 };
vector<int> vec(ia, end(ia));
list<int> li(ia, end(ia));
for (auto it = li.begin(); it != li.end();) {
if (*it % 2 == 1) {
it = li.erase(it);
}
else {
++it;
}
}
for (auto i : li) {
cout << i << " ";
}
cout << endl;
for (auto it = vec.begin();it != vec.end();) {
if (*it % 2 == 0) {
it = vec.erase(it);
}
else {
++it;
}
}
for (auto i : vec) {
cout << i << " ";
}
cout << endl;
system("pause");
return 0;
}
练习9.27
#include<iostream>
#include<forward_list>
using namespace std;
int main() {
forward_list<int> flst = { 0,1,2,3,4,5,6,7,8,9 };
auto prev = flst.before_begin();
auto curr = flst.begin();
while (curr != flst.end()) {
if (*curr % 2) {
curr = flst.erase_after(prev);
}
else {
prev = curr;
++curr;
}
}
for (auto i : flst) {
cout << i << " ";
}
system("pause");
return 0;
}
练习9.28
#include<forward_list>
#include<iostream>
#include<string>
using namespace std;
void func(forward_list<string> &flst, string a, string b) {
auto it = flst.begin();
auto prev = flst.before_begin();
bool flag = false;
while (it != flst.end()) {
if (*it == a) {
it = flst.insert_after(it, b);
flag = true;
break;
}
else {
prev = it;
++it;
}
}
if (!flag) flst.insert_after(prev, b);
}
int main() {
forward_list<string> flst = { "abc","bcd","eee" };
string a = "aaa", b = "fff";
func(flst, a, b);
for (auto i : flst) {
cout << i << " ";
}
cout << endl;
system("pause");
return 0;
}
练习9.29
vec.resize(100)会将90个值为0的元素添加到末尾。
vec.resize(10)会将末尾90个元素删去。
练习9.30
元素类型必须提供一个默认的构造函数。
练习9.31
list
#include<iostream>
#include<vector>
#include<list>
using namespace std;
int main() {
list<int> lst = { 0,1,2,3,4,5,6,7,8,9 };
auto iter = lst.begin();
while (iter != lst.end()) {
if (*iter % 2) {
iter = lst.insert(iter, *iter);
++iter;
++iter;
}
else {
iter = lst.erase(iter);
}
}
for (auto i : lst) {
cout << i << " ";
}
system("pause");
return 0;
}
forward_list
#include<iostream>
#include<vector>
#include<forward_list>
using namespace std;
int main() {
forward_list<int> lst = { 0,1,2,3,4,5,6,7,8,9 };
auto iter = lst.begin();
auto prev = lst.before_begin();
while (iter != lst.end()) {
if (*iter % 2) {
iter = lst.insert_after(iter, *iter);
prev = iter;
++iter;
}
else {
iter = lst.erase_after(prev);
}
}
for (auto i : lst) {
cout << i << " ";
}
system("pause");
return 0;
}
练习9.34
行为是奇数复制,但由于每次插入奇数后返回的是仍是同一个奇数,于是会进入无限循环,应在每次插入奇数后跳过当前数。
#include<vector>
#include<iostream>
using namespace std;
int main() {
vector<int> v = { 1,2,3,4,5 };
auto iter = v.begin();
while (iter != v.end()) {
if (*iter % 2) {
iter = v.insert(iter, *iter);
++iter;
}
++iter;
}
for (auto i : v) {
cout << i << " ";
}
system("pause");
return 0;
}
练习9.37
list所占的空间不是连续的,array是固定size
练习9.38
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main()
{
vector<string> v;
for (string buffer; cin >> buffer; v.push_back(buffer))
cout << v.size() << " " << v.capacity() << endl;
return 0;
}
练习9.39
为svec预留了1024的空间,将输入添加到svec中,最后将svec的size增大当前的一半。
练习9.41
vector<char> v = { 'a','b','c' };
string s(v.begin(), v.end());
练习9.42
string s;
s.reserve(100);
练习9.43
#include<iostream>
#include<string>
using namespace std;
void func(string &s, string &oldVal, string &newVal) {
auto iter = s.begin();
while (iter + oldVal.size() != s.end()) {
if (oldVal == string(iter, iter + oldVal.size())) {
iter = s.erase(iter, iter + oldVal.size());
iter = s.insert(iter, newVal.begin(), newVal.end());
iter += newVal.size();
}
else {
++iter;
}
}
}
int main() {
string s("though,you don't love me");
string oldVal("though");
string newVal("tho");
func(s, oldVal, newVal);
cout << s;
system("pause");
return 0;
}
练习9.44
#include<iostream>
#include<string>
using namespace std;
void func(string &s, string &oldVal, string &newVal) {
string::size_type i = 0;
auto s_len = s.size(), old_len = oldVal.size();
while (i + old_len <= s_len) {
if (oldVal == s.substr(i, i + old_len)) {
s.replace(i, i + old_len, newVal);
i += newVal.size();
}
else {
++i;
}
}
}
int main() {
string s("though,you don't love me");
string oldVal("though");
string newVal("tho");
func(s, oldVal, newVal);
cout << s << endl;
system("pause");
return 0;
}
练习9.45
#include<iostream>
#include<string>
using namespace std;
void func(string &name, string &pre, string &post) {
name.insert(0, pre);
name.append(post);
}
int main() {
string nm = "John", pre = "Mr.", post = " Jr.";
func(nm, pre, post);
cout << nm;
system("pause");
return 0;
}
练习9.46
void func(string &name, string &pre, string &post) {
name.insert(0, pre);
name.insert(name.size(), post);
}
练习9.47
#include<string>
#include<iostream>
using namespace std;
int main() {
string str("ab2c3d7R4E6");
string numbers{ "123456789" };
string alphabet{ "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" };
string::size_type pos = 0;
while ((pos = str.find_first_of(numbers, pos)) != string::npos) {
cout << str[pos] << " ";
++pos;
}
cout << endl;
pos = 0;
while ((pos = str.find_first_of(alphabet, pos)) != string::npos) {
cout << str[pos] << " ";
++pos;
}
cout << endl;
pos = 0;
while ((pos = str.find_first_not_of(alphabet, pos)) != string::npos) {
cout << str[pos] << " ";
++pos;
}
cout << endl;
pos = 0;
while ((pos = str.find_first_not_of(numbers, pos)) != string::npos) {
cout << str[pos] << " ";
++pos;
}
cout << endl;
system("pause");
return 0;
}
练习9.48
string::npos
练习9.49
#include<fstream>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main() {
string FileName;
cout << "请输入要打开的单词文件:" << endl;
cin >> FileName;
ifstream inFile(FileName);
if (!inFile) {
cout << "打开失败!" << endl;
return 0;
}
vector<string> ans;
string up("bdfhklt"), down("gjpqy"), s;
string::size_type pos = 0,poschar;
while (inFile >> s) {
if ((pos = s.find_first_of(up)) == string::npos) {
if ((pos = s.find_first_of(down)) == string::npos) {
ans.push_back(s);
}
}
}
for (auto i : ans) {
cout << i << endl;
}
system("pause");
return 0;
}
练习9.50
#include<string>
#include<iostream>
#include<vector>
using namespace std;
int main() {
vector<string> vec = { "2","3","4","50" };
int sum = 0;
for (auto i : vec) {
sum += stoi(i);
}
cout << sum << endl;
system("pause");
return 0;
}
练习9.51
#include<iostream>
#include<string>
using namespace std;
const string mm[12] = { "Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sept","Oct","Nov","Dec" };
int findmonth(const string &mon) {
int pos;
for (int i = 0;i < 12;++i) {
if ((pos = mon.find(mm[i])) != string::npos) {
return i + 1;
}
}
}
class Date {
public:
Date(const string &str) {
string data_str = str;
string::size_type index1 = 0;
string::size_type index2 = 0;
if (str.find(',') != string::npos) {
index1 = str.find(' ');
index2 = str.find(',',index1+1);
string mon = str.substr(0, index1 - 1);
month = findmonth(mon);
day = stoi(str.substr(index1 + 1, index2));
year = stoi(str.substr(index2 + 1));
}
else if (str.find('/') != string::npos) {
index1 = str.find_first_of('/');
index2 = str.find_first_of('/', index1 + 1);
year = stoi(str.substr(index2 + 1));
month = stoi(str.substr(index1 + 1, index2 - 1));
day = stoi(str.substr(0, index1));
}
else {
index1 = str.find_first_of(' ');
index2 = str.find_first_of(' ', index1 + 1);
string mon = str.substr(0, index1);
month = findmonth(mon);
day = stoi(str.substr(index1 + 1, index2 - 1));
year = stoi(str.substr(index2 + 1));
}
}
void getdate() {
cout << "Year:" << year << " " << "Month:" << month << " " << "Day:" << day << endl;
}
private:
unsigned year, month, day;
};
int main() {
string d1 = "January 1,1900", d2 = "1/1/1990", d3 = "Jan 1 1900";
Date a(d1), b(d2), c(d3);
a.getdate();
b.getdate();
c.getdate();
system("pause");
return 0;
}
练习9.52
题目意思表述的不太清楚,但大意是利用栈来求带括号表达式的值,下面只考虑加法的情况。
如果考虑加减乘除四则运算代码比较复杂,最好先转换成后缀表达式再求值。
#include<iostream>
#include<stack>
#include<string>
using namespace std;
bool isnum(char a) {
if (a >= '0'&&a <= '9') {
return true;
}
else return false;
}
int main() {
string expr("(1+2)+(3+4)+5");
stack<char> st;
int sum = 0;
int len = expr.size();
for (int i = 0;i < len;i++) {
if (expr[i] == '('|| isnum((expr[i]))) {
st.push(expr[i]);
}
else if (expr[i] == '+') {
continue;
}
else if (expr[i] == ')') {
while (st.top() != '(') {
sum += st.top() - '0';
st.pop();
}
st.pop();
}
}
while (!st.empty()) {
sum += st.top() - '0';
st.pop();
}
cout << sum << endl;
system("pause");
return 0;
}