[C++知识库]《C++程序设计原理与实践》习题答案 第十三章 第13章习题答案

13.1

#include<iostream>

using std::cout;

char* my_strdup(const char* s)
//将C风格字符串复制到其在自由空间上分配的内存中
{
	char* p = nullptr;
	const char* t = s;
	size_t len{ 0 };
	while (*t++ != '\0')
		++len;
	p = new char[len + 1];
	for (size_t i = 0; i < len; ++i)
		*(p + i) = *(s + i);
	*(p + len) = '\0';	//添加0结尾
	return p;
}

int main()
{
	char str[] = { "Hello, World!" };
	cout << str << '\n';
	char* str_cpy = my_strdup(str);
	cout << str_cpy << '\n';
	delete[] str_cpy;
	return 0;
}

13.2

#include<iostream>

void build_match(int* match, const char* pattern, int len)
{
	*match = -1;
	int i, j;
	for (j = 1; j < len; ++j)
	{
		i = *(match + j - 1);
		while (i >= 0 && *(pattern + i + 1) != *(pattern + j))
			i = *(match + i);
		if (*(pattern + i + 1) == *(pattern + j))
			*(match + j) = i + 1;
		else
			*(match + j) = -1;
	}
}

char* findx(const char* s, const char* x)
{
	int len_s{ 0 }, len_x{ 0 };
	for (const char* t = s; *t != '\0'; ++t)
		len_s++;
	for (const char* t = x; *t != '\0'; ++t)
		len_x++;
	if (len_s < len_x)
		return nullptr;

	int* match = new int[len_x];
	build_match(match, x, len_x);

	int i{ 0 }, j{ 0 };
	while (i < len_s && j < len_x)
	{
		if (*(s + i) == *(x + j))
		{
			++i;
			++j;
		}
		else if (j > 0)
			j = *(match + j - 1) + 1;
		else
			i++;
	}
	return (j == len_x) ? (const_cast<char*>(s) + i - len_x) : nullptr;
}

int main()
{
	char s[] = { "Hello, World!" };
	char x[] = "o,";
	char* t = findx(s, x);
	std::cout << s << std::endl;
	std::cout << t << std::endl;
}

13.3

#include<iostream>

using std::cout;

int strcmp(const char* s1, const char* s2)
{
	int res{ 0 };
	while (*s1 && *s2 && (*s1 == *s2))
	{
		++s1;
		++s2;
	}
	res = *s1 - *s2;
	return res;
}

int main()
{
	char s1[] = { "Hello, World!" };
	char s2[] = "Hello, world!";
	cout << s1 << std::endl;
	cout << s2 << std::endl;

	int res{ strcmp(s1,s2) };
	cout << "s1 ";
	if (res < 0)
		cout << "< ";
	else if (res > 0)
		cout << "> ";
	else
		cout << "== ";
	cout << "s2\n";
	return 0;
}

13.4

#include<iostream>

using std::cout;

//------------------------------------------------------------------------
char* my_strdup(const char* s, int len)
//将C风格字符串复制到其在自由空间上分配的内存中
{
	char* p = new char[len + 1];
	for (size_t i = 0; i < len; ++i)
		*(p + i) = *(s + i);
	*(p + len) = '\0';	//添加0结尾
	return p;
}
//------------------------------------------------------------------------

//------------------------------------------------------------------------
void build_match(int* match, const char* pattern, int len)
{
	*match = -1;
	int i, j;
	for (j = 1; j < len; ++j)
	{
		i = *(match + j - 1);
		while (i >= 0 && *(pattern + i + 1) != *(pattern + j))
			i = *(match + i);
		if (*(pattern + i + 1) == *(pattern + j))
			*(match + j) = i + 1;
		else
			*(match + j) = -1;
	}
}

char* findx(const char* s, int len_s, const char* x, int len_x)
{
	if (len_s < len_x || len_x < 0 || len_s < 0)
		return nullptr;

	int* match = new int[len_x];
	build_match(match, x, len_x);

	int i{ 0 }, j{ 0 };
	while (i < len_s && j < len_x)
	{
		if (*(s + i) == *(x + j))
		{
			++i;
			++j;
		}
		else if (j > 0)
			j = *(match + j - 1) + 1;
		else
			i++;
	}
	return (j == len_x) ? (const_cast<char*>(s) + i - len_x) : nullptr;
}
//------------------------------------------------------------------------

//------------------------------------------------------------------------
int strcmp(const char* s1, int n1, const char* s2, int n2)
{
//这里默认 n1 和 n2 都 >= 0
	/*if (n1 < 0 || n2 < 0)
		throw exception;*/
	int res{ 0 };
	while (n1 > 0 && n2 > 0 && (*s1 == *s2))
	{
		--n1;
		--n2;
		++s1;
		++s2;
	}
	if (n1 == 0 && n2 == 0)
		res = 0;
	else if (n1 != 0 && n2 == 0)
		res = *s1 - 0;
	else if (n1 == 0 && n2 != 0)
		res = 0 - *s2;
	else
		res = *s1 - *s2;
	return res;
}
//------------------------------------------------------------------------

int main()
{
	char s[] = { 'H','e','l','l','o',',',' ','W', 'o','r','l','d','!' };
	cout << s << '\n';
	char* s_cpy = my_strdup(s, 13);
	cout << s_cpy << '\n';
	delete[] s_cpy;
	return 0;
}

13.5 and 13.6

#include"../../std_lib_facilities.h"

string cat_dot(const string& s1, const string& s2, const string& sep)
{
	return s1 + sep + s2;
}

int main()
{
	string s1{ "Hello" };
	string s2{ "World!" };
	string sep{ ", " };
	cout << cat_dot(s1, s2, sep) << endl;

	return 0;
}

13.7

#include<iostream>

char* cat_dot(const char* s1, const char* s2, const char* sep)
{
	int len_s1{ 0 }, len_s2{ 0 }, len_sep{ 0 };
	
	for (const char* t = s1; *t != '\0'; ++t)
		len_s1++;
	for (const char* t = s2; *t != '\0'; ++t)
		len_s2++;
	for (const char* t = sep; *t != '\0'; ++t)
		len_sep++;

	char* conc = new char[len_s1 + len_s2 + len_sep + 1];

	int i;
	for (i = 0; i < len_s1; ++i)
		conc[i] = s1[i];
	for (int j = 0; j < len_sep; ++i, ++j)
		conc[i] = sep[j];
	for (int j = 0; j < len_s2; ++i, ++j)
		conc[i] = s2[j];
	conc[i] = '\0';

	return conc;
}

int main()
{
	char s1[]{ "Hello" };
	char s2[]{ "World!" };
	char sep[]{ ", " };
	char* res = cat_dot(s1, s2, sep);
	std::cout << res << std::endl;
	delete[] res;
	return 0;
}

13.8

#include"../../std_lib_facilities.h"

//用string实现回文检测
void reverse(string& s)
{
	char temp;
	for (int i = 0, j = s.size() - 1; i < j; i++, j--)
	{
		temp = s[i];
		s[i] = s[j];
		s[j] = temp;
	}
}

bool is_plaindrome(const string& s)
{
	string p = s;
	reverse(p);		//不一定要用这种方法
	return p == s;
}



//用数组实现回文检测
bool is_plaindrome(char s[], int n)
{
	char* t = new char[n];
	bool flag{ true };
	//创建副本
	for (int i = 0, j = n - 1; i < n; i++, j--)
		t[i] = s[j];
	//比较
	for(int i = 0; i < n; i++)
		if (t[i] != s[i])
		{
			flag = false;
			break;
		}
	delete[] t;
	return flag;
}


//用指针实现回文
bool is_plaindrome(const char* first, const char* last)
{
	if (first >= last)
		return true;
	char* t = new char[last - first + 1];
	int i;
	const char* p;
	//创建副本
	for (i = 0, p = last; p >= first; p--, i++)
		t[i] = *p;
	//比较
	bool flag{ true };
	for(char* s = t; first <= last; s++, first++)
		if (*s != *first)
		{
			flag = false;
			break;
		}
	delete[] t;
	return flag;
}


//将字符读入缓冲区
istream& read_word(istream& is, char* buffer, int max)
//从is读取最多 max-1 个字符存入buffer
{
	is.width(max);	//下一个 >> 最多读取 max-1 个字符
	is >> buffer;	//读取空白符间隔的单词，在将最后一个读入字符存入buffer后添加一个0（即读入C风格字符串）
	return is;
}

//测试
int main()
{
	constexpr int max{ 128 };
	for (char s[max]; read_word(cin, s, max);)
	{
		cout << s << " is";
		if(!is_plaindrome(s))
		//if (!is_plaindrome(s, strlen(s)))
		//if(!is_plaindrome(s, s+strlen(s)-1))
			cout << " not";
		cout << " a plaindrome\n";
	}
	return 0;
}

13.9

#include"../../std_lib_facilities.h"

void stack_grow(int* addr[], int i);

int global_1;
int global_2;

int main()
{
	//测试静态存储的布局
	static int local_1;
	static int local_2;
	cout << "Static store:\n";
	cout << "&global_1 = " << &global_1 << endl;
	cout << "&global_2 = " << &global_2 << endl;
	cout << "&local_1 = " << &local_1 << endl;
	cout << "&local_2 = " << &local_2 << endl;
	cout << "Static store is ";
	if (!((&global_1 < &global_2) && (&local_1 < &local_2)))
		cout << "not ";
	cout << "from low to high\n";

	//测试栈的拓展方向
	int* addr[3];
	stack_grow(addr, 0);
	cout << "Stack store:\n";
	for (int i = 0; i < 3; i++)
		cout << "addr[" << i << "] = " << addr[i] << endl;
	cout << "Stack extends ";
	if (addr[0] < addr[1] && addr[1] < addr[2])
		cout << "from low to high\n";
	else if (addr[0] > addr[1] && addr[1] > addr[2])
		cout << "from high to low\n";
	else
		cout << "Randomly\n";

	//测试自由空间在内存中的布局
	double* d = new double[10];
	cout << "Free store:\n";
	for (int i = 0; i < 10; i++)
		cout << "&d[" << i << "] = " << d + i << endl;
	cout << "Element with high index is at ";
	if (d < &d[4] && &d[4] < &d[9])
		cout << "high ";
	else if (d > &d[4] && &d[4] > &d[9])
		cout << "low ";
	cout << "address\n";
	delete[] d;
	return 0;
}

void stack_grow(int* addr[], int i)
{
	//利用递归的方法测试栈生长方向
	if (i >= 3)
		return;
	addr[i] = &i;
	stack_grow(addr, i + 1);
}

13.10

#include"../../std_lib_facilities.h"

//将字符读入缓冲区，对长字符串的处理方法
//法1，当输入字符串过长，提示出错报告，这个方法只需要修改read_word函数，让该函数报错即可
istream& read_word_v1(istream& is, char* buffer, int max)
//从is读取最多 max-1 个字符存入buffer
{
	is.width(max);	//下一个 >> 最多读取 max-1 个字符
	is >> buffer;	//读取空白符间隔的单词，在将最后一个读入字符存入buffer后添加一个0（即读入C风格字符串）
	
	char ch;
	if ((strlen(buffer) == max - 1) && cin.get(ch))
	{
		cin.unget();
		error("read_word_v1: input string is too long");
	}
	return is;
}




//===============================================================================
//法2，可以处理任意长的字符串，这个方法需要同时修改主函数，实现比较复杂
void skip_space(istream& is);
char** expand_strs(char** strs, int& cnt_strs);
char* merge(char** strs, int sub_maxsz, int size);

istream& read_word_v2(istream& is, char** buffer)
{
	constexpr int sub_maxsz{ 128 };	//每个分串的最大长度
	int cnt_strs{ 10 };		//初始十个字串，之后可能会变多
	char** strs{ new char* [cnt_strs] };	//char*数组
	char* str{ nullptr };		//字符串
	int size{ 0 };		//长字符串的总长度
	char ch;

	//首先在自由空间建立第一个缓冲区，char*数组剩下的指向nullptr
	*strs = new char[sub_maxsz];
	for (int i = 1; i < cnt_strs; ++i)
		strs[i] = nullptr;

	//先跳过空白字符
	skip_space(is);

	//开始读入字符串
	int i = 0;	//子串内部字符索引
	int i_str = 0;	//子串索引
	while (is.get(ch) && !isspace(ch) && ch != '\0')
	{
		if (i < sub_maxsz)
			strs[i_str][i] = ch;
		else
		{
			++i_str;
			i = 0;
			if (i_str >= cnt_strs)
				strs = expand_strs(strs, cnt_strs);
			strs[i_str] = new char[sub_maxsz];
			strs[i_str][i] = ch;
		}
		++size;
		++i;
	}
	//合并为一个最终的字符串
	*buffer = merge(strs, sub_maxsz, size);

	//释放从自由空间分配的内存
	for (i = 0, i_str = 0; i < size; i += sub_maxsz, ++i_str)
		delete[] strs[i_str];
	delete[] strs;

	return is;
}

void skip_space(istream& is)
{
	char ch;
	while (is.get(ch) && isspace(ch))
		continue;
	is.unget();
}

char** expand_strs(char** strs, int& cnt_strs)
{
	constexpr int ex_sz = 10;	//每次拓展10个
	int new_cnt = cnt_strs + ex_sz;
	char** new_strs = new char* [new_cnt];

	for (int i = 0; i < cnt_strs; ++i)
		new_strs[i] = strs[i];
	for (int i = cnt_strs; i < new_cnt; ++i)
		new_strs[i] = nullptr;

	cnt_strs = new_cnt;
	delete[] strs;

	return new_strs;
}

char* merge(char** strs, int sub_maxsz, int size)
{
	char* m_str = new char[size + 1];
	
	for (int i = 0, j = 0, k = 0; i < size; ++i, ++j)
	{
		if (j == sub_maxsz)
		{
			j = 0;
			++k;
		}
		m_str[i] = strs[k][j];
	}
	m_str[size] = '\0';
	
	return m_str; 
}

bool is_plaindrome(char s[], int n)
{
	char* t = new char[n];
	bool flag{ true };
	//创建副本
	for (int i = 0, j = n - 1; i < n; i++, j--)
		t[i] = s[j];
	//比较
	for (int i = 0; i < n; i++)
		if (t[i] != s[i])
		{
			flag = false;
			break;
		}
	delete[] t;
	return flag;
}


int main()
{
	for (char* s; read_word_v2(cin, &s);)
	{
		cout << s << " is";
		if (!is_plaindrome(s, strlen(s)))
			cout << " not";
		cout << " a plaindrome\n";
	}
	return 0;
}

13.11 跳表 Skip List

目前实现了跳表的插入、删除、查询和打印。

SkipList.h

#include"../../std_lib_facilities.h"

typedef int ElementType;

typedef class Skip_list_node SLN;
typedef class Skip_list SL;

class Skip_list_node
{
	ElementType elem;
	int levels;			//总层数
	vector<SLN*>succs;	//该节点在它所在的每一层的后继节点

public:
	Skip_list_node(ElementType val, int ls);
	ElementType get_val()const { return elem; }
	int get_levels()const { return levels; }
	SLN* get_succ(int lev)const { return succs[lev]; }			//获得该节点在lev层的后继节点，lev从0开始
	void set_succ(SLN* succ, int lev) { succs[lev] = succ; }	//设置该节点在lev层的后继节点
};

class Skip_list
{
	static constexpr int Max_level{ 16 };
	static constexpr int Inf{ -65535 };

	SLN head;
	int rand_level();

public:
	Skip_list() :head{ Inf, Max_level } { srand(time(nullptr)); }
	const SLN& get_head()const { return head; }
	void insert(ElementType val);
	SLN* delte_with_sln(ElementType val);
	void delte_with_void(ElementType val);
	SLN* find(ElementType val);
};

//辅助函数
void print_all(const Skip_list& sl);

SkipList.cpp

#include"SkipList.h"

Skip_list_node::Skip_list_node(ElementType val, int ls)
	:elem{ val }, levels{ls}
{
	if (ls <= 0)
		error("No levels");
	for (int i = 0; i < ls; ++i)
		succs.push_back(nullptr);
}


int Skip_list::rand_level()
{
	int levels{ 1 };
	while (randint(0, 1) && levels < Max_level)
		++levels;
	return levels;
}

void Skip_list::insert(ElementType val)
{
	int levels = rand_level();
	SLN* new_node = new Skip_list_node{ val, levels };
	
	//从头节点开始，逐层寻找合适的节点位置
	SLN* p = &head;
	for (int i = levels - 1; i >= 0; --i)
	{
		while (p->get_succ(i) && (p->get_succ(i))->get_val() <= val)
			p = p->get_succ(i);
		//找到合适的节点位置后，设置后继
		if (p->get_val() != val)	//如果不相等，则插入
		{
			new_node->set_succ(p->get_succ(i), i);
			p->set_succ(new_node, i);
		}
		else
			delete new_node;	//如果重复，则释放
	}
}

SLN* Skip_list::delte_with_sln(ElementType val)
{
	SLN* update[Max_level];		//被删除节点每一层的前驱节点
	SLN* p = &head;
	for (int i = Max_level - 1; i >= 0; --i)
	{
		while (p->get_succ(i) && p->get_succ(i)->get_val() < val)
			p = p->get_succ(i);
		update[i] = p;
	}
	if (p->get_succ(0) == nullptr || p->get_succ(0)->get_val() != val)
	{
		cerr << "delete_with_sln: element not found\n";
		return nullptr;
	}
	else
	{
		SLN* del_node = p->get_succ(0);
		for (int i = 0; i < del_node->get_levels(); ++i)
			update[i]->set_succ(del_node->get_succ(i), i);
		return del_node;
	}
}

void Skip_list::delte_with_void(ElementType val)
{
	SLN* update[Max_level];		//被删除节点每一层的前驱节点
	SLN* p = &head;
	for (int i = Max_level - 1; i >= 0; --i)
	{
		while (p->get_succ(i) && p->get_succ(i)->get_val() < val)
			p = p->get_succ(i);
		update[i] = p;
	}
	if (p->get_succ(0) == nullptr || p->get_succ(0)->get_val() != val)
		cerr << "delete_with_void: element not found\n";
	else
	{
		SLN* del_node = p->get_succ(0);
		for (int i = 0; i < del_node->get_levels(); ++i)
			update[i]->set_succ(del_node->get_succ(i), i);
		delete del_node;
	}
}

SLN* Skip_list::find(ElementType val)
{
	SLN* p = &head;
	for (int i = Max_level - 1; i >= 0; --i)
	{
		while (p->get_succ(i) && p->get_succ(i)->get_val() <= val)
			p = p->get_succ(i);
		if (p->get_val() == val)
			return p;
	}
	return nullptr;
}

//辅助函数
void print_all(const Skip_list& sl)
{
	const SLN& head = sl.get_head();
	int cnt{ 1 };
	for (SLN* p = head.get_succ(0); p; p = p->get_succ(0))
	{
		cout << p->get_val();
		if (cnt % 10)
			cout << ' ';
		else
			cout << '\n';
		++cnt;
	}
	cout << '\n';
}

mian.cpp 测试

#include"SkipList.h"

int main()
{
	Skip_list sl;
	int n;

	cout << "Enter some integers to build skip list, ctrl+z to end.\n";
	while (cin >> n)
		sl.insert(n);

	print_all(sl);

	cin.clear();
	cout << "Enter an integer and I will tell you if it is in the skip list, ctrl+z to end.\n";
	while (cin >> n)
	{
		cout << n << " is";
		if (!sl.find(n))
			cout << " not";
		cout << " in the skip list\n";
	}

	cin.clear();
	cout << "Enter an integer and I will delete it from the skip list, ctrl+z to end.\n";
	while (cin >> n)
	{
		sl.delte_with_void(n);
	}

	cin.clear();
	cout << "Enter an integer and I will tell you if it is in the skip list, ctrl+z to end.\n";
	while (cin >> n)
	{
		cout << n << " is";
		if (!sl.find(n))
			cout << " not";
		cout << " in the skip list\n";
	}

	print_all(sl);
	
	return 0;
}

13.12 未实现