剑指Offer基础知识(一)数据结构

2018-02-07

本文主要记录阅读剑指Offer这本书所遇到的算法解释并作一些个人的拓展，其中的算法面试题请看剑指Offer面试题集

第二章

2.2.1 关于sizeof的小知识

sizeof 对于空类型(无成员变量和成员函数)的实例 = 1字节：由于声明空类型的实例必须在内存中占用一定空间否则无法使用，占用多少内存由编译器决定，在VS中每个空类型实例占用1字节。
sizeof 对于空类型+构造和析构函数的实例 = 1字节 ：调用函数只需知道函数地址即可，函数地址只与类型有关而与类型的实例无关，因此sizeof实例还是1字节。

sizeof 对于空类型+构造函数+虚析构函数(虚函数) = 1个指针大小：一个类型中有虚拟函数就会为该类型生成虚函数表，并为这个类型的每个实例中添加一个指向虚函数表的指针，指针大小与机器有关，32为指针为4字节，64位指针为8字节。

class B             //空类型
{
};
class C            //空类型+构造和析构函数
{
public:
	C(){};
	~C(){};
};
class D           //空类型+构造函数+虚析构函数(虚函数)
{
public:
	D(){};
	virtual  ~D(){};
};
int main()
{
	B b;
	C c;
	D d;
	cout << "空类型大小:" << sizeof(b)<<endl;
	cout << "空类型+构造和析构函数大小:" << sizeof(c) << endl;
	cout << "空类型+构造函数+虚析构函数(虚函数)大小:" << sizeof(d) << endl;
	system("pause");
	return 0;
}

总结：
空的类是会占用内存空间的，而且大小是1，原因是C++要求每个实例在内存中都有独一无二的地址。

类内部的成员变量：
*普通的变量：是要占用内存的，但是要注意对齐原则（这点和struct类型很相似）。
*static修饰的静态变量：不占用内容，原因是编译器将其放在全局变量区。
类内部的成员函数：
*普通函数：不占用内存。
*虚函数：要占用4个字节，用来指定虚函数的虚拟函数表的入口地址。所以一个类的虚函数所占用的地址是不变的，和虚函数的个数是没有关系的

2.2.1 关于复制函数的小知识

C++标准不允许复制构造函数传值参数，否则会造成递归重复调用，编译错误。

class E
{
private:
  int num;
public:
  //构造函数
  E(int x) :num(x)
  {
  	  cout << "constructor call" << endl;
  }
  //复制构造函数 传引用调用
  E(E& x)
  {
 	 num = x.num;
  	 cout << "copy constructor call" << endl;
  }
  //赋值运算符重载
  E& operator = (E& x)
  {
 	 num = x.num;
  	 cout << "assignment operator call" << endl;
  	 return *this;
  }
  //函数调用
  void showNum(E x)
  {
	
  } 

};
int main()
{
 	E a(1);       //1式
 	E b(2);       //2式
 	b = a;        //3式
  	E c = a;      //4式
 	c.showNum(a); //5式
 	system("pause");
 	return 0;
}

运行结果如图：

1/2式 => 若是实例创建并初始化时调用相应参数的构造函数
3式 => 若是实例已经创建初始化后再用=赋值，则调用=重载赋值函数
4式 => 若是实例用另一个同类实例初始化，则调用复制构造函数
5式 => 若是实例使用方法调用另一个实例，则首先调用复制构造函数将实参复制给形参后执行相关操作

因此就可以解释为什么C++不允许复制构造函数传值了，若是传值，则调用E c = a或者c.showNum(a)或者的时候，a作为参数传值给c的复制构造函数的参数E x，因为x没有被初始化，所以要调用x的复制构造函数将a复制给x，即x.E(a)，然而x的复制构造函数也是传值的，因此又要将a作为参数传值给c的复制构造函数的参数x的复制构造函数的参数E x，又因为这个x也没有被初始化，又要调用这个x的复制构造函数，造成了无限的递归。

因此复制构造函数的参数使用引用调用不是为了减少一次内存的复制，而是为了避免复制构造函数无限递归调用的情况出现。
下面这几种情况下会调用复制构造函数:
（1）显式或隐式地用同类型的一个对象来初始化另外一个对象。如上例中的E c=a;
（2）作为实参传递给一个函数。如上例中的c.showNum(a);
（3）在函数体内返回一个对象时，也会调用返回值类型的拷贝构造函数
（4）初始化序列容器中的元素时。比如vector svec(5)，string的缺省构造函数和拷贝构造函数都会被调用。
（5）用列表的方式初始化数组元素时。string a[] = {string(“hello”),string(“world”)};会调用string的拷贝构造函数。

2.3 数组和指针区别

输出 “20,4,4”
20：data1是一个数组，包含五个整数，每个整数占4字节，一共20字节
4：data2是一个指针指向data1数组的第一个数字，指针大小为4字节
4：在C/C++中数组作为参数传递时自动退化为同类型的指针，因此为4字节

2.3.2字符串小知识

C/C++中每个字符串以’/0’作为结尾，这样可以方便地找到字符串的结尾，但有额外字符开销，易越界。
C/C++将常量字符串放到一个单独的内存区域节省内存，当几个指针赋值给相同的常量字符串时，他们实际上会指向相同的内存地址，但是用常量内存初始化数组却会创建新空间。

2.3.3 链表小知识

链表是由指针把若干个节点连接成链状结构，链表的创建、插入节点、删除节点等操作只需要20行代码就可以实现，比较适合面试。
链表是一种动态结构，创建时无需知道链表的长度，每添加一次节点再分配新内存，然后调整指针的指向。
单向链表的节点定义如下

struct ListNode
{
 	int Value;
 	ListNode* Next;
}

往链表末尾添加一个节点的函数如下
要点：1.头指针的传参 2.插入的节点是第一个节点的情况(空链表/头指针为空)

void addToTail(ListNode** pHead, int value)  //由于头指针可能改变，因此要以传指针的形式传参，否则出了函数头指针依然是空指针
{
 	ListNode* pNew = new ListNode();
 	pNew->Value = value;
 	pNew->Next = NULL;	//注意新节点的Next初始化为NULL

 	if(*pHead == NULL)  //若是往一个空链表插入节点，则头指针指向新节点
 	{
 		*pHead = pNew;
 	}
 	else  	//否则找到头指针指向第一个节点，开始遍历找到最后一个节点，将节点的Next指向新节点
 	{
 		ListNode* pNode = *pHead;

 		while(pNode->Next != NULL)
 			pNode = pNode->Next;

 		pNode->Next = pNew;
 	}
}

在链表中找到第一个含有某值的节点并删除该节点的函数如下
要点：

void removeNode(ListNode** pHead, int value)
{
 	if(pHead == NULL || *pHead == NULL)  //空链表直接返回
 		return;

 	ListNode* pToBeDelete = NULL;  //找到需要删除的节点
 	if((*pHead)->Value == value)  //当第一个节点是需要删除的节点，则需要改变头指针的指向
 	{
 		pToBeDelete = *pHead;
 		*pHead = (*pHead)->Next;
 	}
 	else 						//否则开始遍历节点
 	{
 		ListNode* pNode = *pHead;
 		while(pNode->Next != NULL && pNode->Next->Value != value)  //遍历到最后一个节点或者找到需要删除的节点的前一个节点则停止遍历
 		  pNode = pNode->Next;
 		
 		if(pNode->Next != NULL && pNode->Next->Value ==value)  //找到需要删除的节点的前一个节点
 		{
 		  pToBeDelete = pNode->Next;
 		  pNode->Next = pNode->Next->Next;  //这里包含了当需要删除的节点是最后一个节点的情况，若是最后一个节点则它的前一个节点会指向NULL
 		}
 	}

 	if(pToBeDelete != NULL)
 	{
 		delete pToBeDelete;
 		pToBeDelete = NULL;
 	}
}

2.3.4 树小知识

树是一种数据结构:

除了根节点外每个节点只有一个父节点，根节点没有父节点
除了叶节点外每个节点有一个或多个子节点，叶节点没有子节点
父节点与子节点之间用指针连接

二叉树：树的特殊结构，每个节点最多有两个子节点
遍历方式：

前序：根-左-右
中序：左-根-右
后序：左-右-根
宽度优先：按照层的顺序从顶到底遍历，同一层的节点按从左到右遍历
二叉搜索树：左节点小于等于根节点，右节点大于等于根节点的二叉树
堆：最大堆中根节点的值最大，最小堆中根节点的值最小
红黑树：把树中的节点定义为红、黑两种颜色，并通过规则确保从根节点到叶节点的最长路径的长度不超过最短路径的两倍，C++中STL中set、multiset、map、multimap等数据结构都是基于红黑树实现的

2.3.5 栈和队列小知识

栈：先进先出，即最后入栈(push)的元素会第一个被弹出(pop)
队列：先进先出，即第一个进入队列的元素会第一个出来

Fright For Better Day

ItEassy