1029

第一道题，结构体对齐的规则。
第二大题，实现一个宏，计算结构体成员的相对偏移量。
第三道题，结构体和共用体的区别。
第四道题，编写程序完成，int变量的小端存储转换成大端存储。
第五道题，说一下用户存储空间都有哪几个区构成？回答一下，栈区和堆区的区别。
第六道题，代码实现打印N行杨辉三角。不得使用二维数组，可以使用一维数组。
第七道题，快排，堆排，归并排序，任选一道实现代码。
第八道题，谈谈顺序表和链表的区别，以及适用的场景。
第九道题，实现不带头节点单链表的逆置。

1

结构体对齐的规则。

我答的

~~所有成员地址相对结构体~~首地址的偏移量要可以被成员的基本数据类型大小整除。计算sizeof时，首地址默认为0，所以都满足相对首地址可整除。
各个成员依次从上到下都要相对于前一个成员的首地址偏移量被下一个成员基本数据类型大小整除。
最后，结构体的大小要可以被该结构体内最大的成员基本数据类型大小整除。

答案

结构体变量的首地址，必须是结构体变量中的“最大基本数据类型成员所占字节数”的整数倍。计算sizeof时，首地址默认为0，所以满足相对首地址可整除。
结构体变量中，相对于结构体首地址，每个成员的偏移量，都是成员本身基本数据类型所占字节数的整数倍。我们可以依次从上到下累计已计算的大小，再看下一某位置是否是其整数倍。
结构体变量的总大小，为结构体变量中 “最大基本数据类型成员所占字节数”的整数倍。

#pragma pack指定对齐值

预处理指令#pragma pack(n) 可以改变默认对齐数。n 取值是 1, 2, 4, 8 , 16。
vs 中默认值 = 8，gcc 中默认值 = 4；

#pragma pack(1)
struct node
{
    char cha;
    double dx;
    char chb;
};
//若( )内为1->size:10;
//		为2->	12;
//		为4->	16;
//		为8->	24;
//		为16->	24;
#pragma pack

加入指定对齐方式的终极总结

结构体变量的首地址，必须是MIN{“结构体最大基本数据类型成员所占字节数”, 指定对齐方式}的整数倍。
结构体中，相对于结构体首地址，每个成员的偏移量，都是MIN{该基本数据类型成员, 指定对齐方式}的整数倍。
结构体的总大小，为MIN{结构体最大基本数据类型成员所占字节数, 指定对齐方式}的整数倍。

2

实现一个宏，计算结构体成员的相对偏移量。

1	#define offset(type,member) (int)&( ( (type*)0 ) ->member)

3

结构体和共用体的区别。

然后让你判断大小端或者对数据转换

4

编写程序完成，int变量的小端存储转换成大端存储。

5

说一下用户存储空间都有哪几个区构成？回答一下，栈区和堆区的区别。

代码区、数据区、堆区、栈区

管理方式：栈由系统自动管理；堆由程序员控制，使用方便，但易产生内存泄露。
生长方向：栈向低地址扩展(即”向下生长”)，是连续的内存区域；堆向高地址扩展(即”向上生长”)，是不连续的内存区域。这是由于堆区管理系统用链表来存储空闲内存地址，自然不连续，而链表从低地址向高地址遍历。
空间大小：栈顶地址和栈的最大容量由系统预先规定(通常默认1M 或10M)；堆的大小则受限于计算机系统中有效的虚拟内存，32 位Linux 系统中堆内存可达2.9G 空间。
存储内容：
1. 栈在函数调用时，首先压入是函数实参，然后主调函数中下条指令(函数调用语句的下条可执行语句)的地址压入，最后是被调函数的局部变量。本次调用结束后，局部变量先出栈，指令地址出栈，最后栈平衡，程序由该点继续运行下条可执行语句。
2. 堆通常在头部用一个字节存放其大小，堆用于存储生存期与函数调用无关的数据，具体内容由程序员安排。
分配方式：
1. 栈可静态分配或动态分配。静态分配由编译器完成，如局部变量的分配。动态分配由alloc函数在栈上申请空间，用完后自动释放不需要调动free函数。
2. 堆只能动态分配且手工释放。
分配效率：
1. 栈由计算机底层提供支持：分配专门的寄存器存放栈地址，压栈出栈由专门的指令执行，因此效率较高。
2. 堆由函数库提供，机制复杂，效率比栈低得多。
分配后系统响应：
1. 只要栈剩余空间大于所申请空间，系统将为程序提供内存，否则报告异常提示栈溢出。
2. 操作系统为堆维护一个记录空闲内存地址的链表。当系统收到程序的内存分配申请时，会遍历该链表寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点空间分配给程序。若无足够大小的空间(可能由于内存碎片太多)，有可能调用系统功能去增加程序数据段的内存空间，以便有机会分到足够大小的内存，然后进行返回。大多数系统会在该内存空间首地址处记录本次分配的内存大小，供后续的释放函数(如free/delete)正确释放本内存空间。
3. 此外，由于找到的堆结点大小不一定正好等于申请的大小，系统会自动将多余的部分重新放入空闲链表中。
碎片问题：
1. 栈不会存在碎片问题，因为栈是先进后出的队列，内存块弹出栈之前，在其上面的后进的栈内容已弹出。
2. 而频繁申请释放操作会造成堆内存空间的不连续，从而造成大量碎片，使程序效率降低。
3. 可见，堆容易造成内存碎片；由于没有专门的系统支持，效率很低；由于可能引发用户态和内核态切换，内存申请的代价更为昂贵。所以栈在程序中应用最广泛，函数调用也利用栈来完成，调用过程中的参数、返回地址、栈基指针和局部变量等都采用栈的方式存放。所以，建议尽量使用栈，仅在分配大量或大块内存空间时使用堆。
4. 最后使用栈和堆时应避免越界发生，否则可能程序崩溃或破坏程序堆、栈结构，产生意想不到的后果。

6

代码实现打印N行杨辉三角。不得使用二维数组，可以使用一维数组。

int ar[100] = { 0,1 };	//初始化数组
int n, i, j;
int l, r;	//存放上一层左边的数和右边的数
n = 10;		//层数
for (i = 1; i <= n; i++)
{
    l = 0;
    for (j = 1; j <= i; j++)
    {
        r = ar[j];				//面试题空白处
        ar[j] = l + r;			//面试题空白处
        printf("%-4d", ar[j]);
        l = r;
    }
    printf("\n");
}

7

快排，堆排，归并排序，任选一道实现代码。

8

谈谈顺序表和链表的区别，以及适用的场景。

9

实现不带头节点单链表的逆置。

迭代器

可以理解为，指向容器内部数据的一个指针。本质是对象。

#include<vector>
int main()
{
    vector<int> v1;
    for(int i = 0;i<10;i++)
    {
        v1.push_back(i);
    }
    vector<int>::iterator it1 = v1.begin();
    for(;it1!=v1.end();it1++)
    {
        cout << 
    }
}

Mstring_iterator

//mstring_iterator.h
//begin end insert erase
#ifndef MSTRING_ITERATOR_H
#define MSTRING_ITERATOR_H
class Mstring;

class Mstring_iterator
{
public:
	Mstring_iterator(Mstring& mstr, int pos)
        :_mstr(mstr), _pos(_pos)
    {
        
    }
    Mstring_iterator(const Mstring_iterator& src)
        :_mstr(src._mstr), _pos(src._pos)
    {
        
    }
    Mstring_iterator& operator=(const Mstring_iterator& src)
    {
        if(&_mstr != &src._mstr)
        {
            return *this;
        }
        _pos = src._pos;
        return *this;
    }
    
    bool operator !=(const Mstring_iterator& src)
    {
        if(&_mstr != &src._mstr || _pos != src._pos)//不是一个字符串或没有指向同一位置
        {
            return true;
        }
        return false;
    }
    bool operator ==(const Mstring_iterator& src)
    {
        if(&_mstr == &src._mstr && _pos == src._pos)//不是一个字符串或没有指向同一位置
        {
            return true;
        }
        return false;
    }
    Mstring_iterator& operator++()
    {
        _pos++;
        return *this;
    }
    Mstring_iterator operator++(int)
    {
        int pos = _pos;
        _pos++;
        return Mstring_iterator(_mstr,pos);
    }

    Mstring_iterator& operator--()
    {
        _pos--;
        return *this;
    }
    Mstring_iterator operator--(int)
    {
        int pos = _pos;
        _pos--;
        return Mstring_iterator(_mstr,pos);
    }

    char& operator*();//由于[]重载在本文件不可见，则在这里实现不可编译，我们可以在mstring.cpp进行类外实现。
private:
    Mstring& _mstr;
    int _pos;
}

Mstring

//mstring.h
#ifndef MSTRING_H
#define MSTRING_H
#include<iostream>
#include"mstring_iterator.h"
#include<mutex>
using namespace std;

#define MSTRING_MORE_SIZE sizeof(int)
#define DEFEALT_LEN (10+MSTRING_MORE_SIZE)

class Mstring
{
public:
	typedef Mstring_iterator iterator;
	Mstring(const char* str = NULL);
	Mstring(const Mstring& src);
	Mstring& operator=(const Mstring& src);
	~Mstring();

	void push_back(char c);
	void pop_back();
	char back()const;
	char front()const;
	bool empty()const;
	int size()const;

	Mstring operator+(const Mstring& str)const;
	char& operator[](int pos);
	char operator[](int pos)const;

	iterator begin();
	iterator end();
	void insert(iterator it, char val);
	void erase(iterator it);

	friend ostream& operator<<(ostream& out, const Mstring& src);
	friend istream& operator>>(istream& in, Mstring& src);
private:
	bool full()const;
	void expand();
	void init_num();
	int& get_num();
	int get_num()const;
	const char* get_str_begin()const;
	char* get_str_begin();
	void write_copy();
	int down_num();//引用计数-1
	int up_num();//引用计数+1

	char* _str;//能否直接使用浅拷贝------怎么加引用计数
	int _len;//当前空间总长度
	int _val_len;//已经占用的长度，实际数据数量
	//static mutex* _lock;
};

#endif

mstring.cpp

#include"mstring.h"

mutex* Mstring::_lock = new mutex();

Mstring::Mstring(const char* str)
{
	if (NULL == str)
	{
		_len = DEFEALT_LEN;
		_val_len = 0;
		_str = new char[_len];
		memset(_str, 0, _len);
		init_num();
		return;
	}

	_val_len = strlen(str);

	//加上引用计数占的空间
	_len = _val_len + 1 + MSTRING_MORE_SIZE;
	_str = new char[_len];
	memset(_str, 0, _len);

	for (int i = 0; i < _val_len; i++)
	{
		get_str_begin()[i] = str[i];
	}
	init_num();
}

Mstring::Mstring(const Mstring& src)
{
	_val_len = src._val_len;
	_len = src._len;
	_str = src._str;
	//让引用计数+1
	up_num();
}

Mstring& Mstring::operator=(const Mstring& src)
{
	if (&src == this)
	{
		return *this;
	}
	_val_len = src._val_len;
	_len = src._len;
	_str = src._str;
	up_num();

	return *this;
}

Mstring::~Mstring()
{
	//将引用计数-1
	down_num();

	//查看当前是否还有人引用
	if (0 == get_num())
	{
		delete[]_str;
	}
}

void Mstring::push_back(char c)
{
	//判断是否一个人独有
	if (get_num() > 1)
	{
		//写时拷贝，给分配独有的空间
		write_copy();
	}

	if (full())
	{
		expand();
	}

	get_str_begin()[_val_len] = c;
	_val_len++;
}

void Mstring::pop_back()
{
	if (get_num() > 1)
	{
		write_copy();
	}

	if (empty())
	{
		return;
	}

	_val_len--;
}

char Mstring::back()const
{
	if (empty())
	{
		return 0;
	}

	return get_str_begin()[_val_len - 1];
}

char Mstring::front()const
{
	if (empty())
	{
		return 0;
	}

	return get_str_begin()[0];
}

bool Mstring::empty()const
{
	return _val_len == 0;
}

Mstring Mstring::operator+(const Mstring& str)const
{
	char* p;
	int len = _val_len + str._val_len + 1;
	p = new char[len];
	memset(p, 0, len);

	//进行数据拷贝-----将两个字符串的数据拼接起来
	int i = 0;
	for (; i < _val_len; i++)
	{
		p[i] = get_str_begin()[i];
	}

	for (int j = 0; j < str._val_len; j++, i++)
	{
		p[i] = str.get_str_begin()[j];
	}

	return p;
}

char& Mstring::operator[](int pos)
{
	if (get_num() > 1)
	{
		write_copy();
	}
	return  get_str_begin()[pos];
}

char Mstring::operator[](int pos)const
{
	return  get_str_begin()[pos];
}

bool Mstring::full()const
{
	return _val_len == _len - 1 - MSTRING_MORE_SIZE;
}

void Mstring::expand()
{
	if (get_num() > 1)
	{
		write_copy();
	}

	_len = _len << 1;

	char* p = new char[_len];
	memset(p, 0, _len);

	for(int i = 0;i<_val_len+MSTRING_MORE_SIZE;i++)
	{
		p[i] = _str[i];
	}

	if (down_num() == 0)
	{
		delete[]_str;
	}

	_str = p;
}

int Mstring::size()const
{
	return _val_len;
}

//初始化引用计数
void Mstring::init_num()
{
	get_num() = 1;
}

//获取引用计数
int& Mstring::get_num()
{
	return *((int*)_str);
}

//引用计数-1
int Mstring::down_num()
{
	_lock->lock();
	int num = --get_num();
	_lock->unlock();
	return num;
}

//引用计数+1
int Mstring::up_num()
{
	//get_lock()->lock();
	_lock->lock();
	/*
	while(1)
	{
		if(_lock->a == 0)
		{
			_lock->a = 1;
			break;
		}
		sleep(10);
	}
	
	*/
	int num = ++get_num();
	_lock->unlock();
	/*
	_lock->a = 0;
	*/

	return num;
}


//获取引用计数
int Mstring::get_num()const
{
	return *((int*)_str);
}

//获取字符串的开头指针
char* Mstring::get_str_begin()
{
	return _str + MSTRING_MORE_SIZE;
}

//获取字符串的开头指针
const char* Mstring::get_str_begin()const
{
	return _str + MSTRING_MORE_SIZE;
}

//写时拷贝
void Mstring::write_copy()
{
	char* p = new char[_len];

	//将所有的数据全部拷贝过来
	for (int i = 0; i < _len; i++)
	{
		p[i] = _str[i];
	}

	//改变原来指向的内存的引用计数
	if (0 == down_num())
	{
		delete[]_str;
	}

	//将当前引用计数改为1
	_str = p;
	init_num();
}

ostream& operator<<(ostream& out, const Mstring& src)
{
	for (int i = 0; i < src.size(); i++)
	{
		out << src.get_str_begin()[i];
	}
	out << "     :::::num:::" << src.get_num();
	out << endl;
	return out;
}

istream& operator>>(istream& in, Mstring& src)
{
	if (src.get_num() > 1)
	{
		src.write_copy();
	}

	char tmp[1024];
	in >> tmp;
	
	src = tmp;
	return in;
}

////////////////////////////////迭代器

iterator Mstring::begin()
{
    return iterator(*this, 0);
}

iterator Mstring::end()
{
    return iterator(*this, _val_len);
}
iterator Mstring::insert(iterator it, char val) 
{
    //判断是否独有
    if (get_num() > 1)
    {
        write_copy();
    }

    //扩容
    if (full())
    {
        expand();
    }

    iterator it1 = end();
    iterator it2 = it1 - 1;

    for (; it1 != it; it1--, it2--)
    {
        *it1 = *it2;
    }
    *it = val;
    _val_len++;

    return it;
}
iterator Mstring::erase(iterator it)
{
    //判断是否独有
    if (get_num() > 1)
    {
        write_copy();
    }

    //判空
    if (empty())
    {
        return it;
    }

    iterator it1 = it;
    iterator it2 = it + 1;
    for (; it2 != end(); it1++, it2++)
    {
        *it1 = *it2;
    }

    _val_len--;
    return it;
}


char& Mstring_iterator::operator*()
{
	return _mstr[_pos];
}

test

int main()
{
    Mstring s1 = "123456";
    Mstring::iterator it = s1.begin();
    for(; it != s1.end(); it++)
    {
        cout << *it << " ";
        
    }
    cout << endl;
}

vector

通过迭代器进行增删改查。

顺序迭代器

//正向迭代打印
template<class T>
void print(T & obj)
{
	typename T::iterator it = obj.begin();
	for (; it != obj.end();it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}
//反向迭代打印
template<class T>
void r_print(T& obj)
{
	typename T::reverse_iterator it = obj.rbegin();
	for (;it != obj.rend();it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

2021年10月面试