内存字节对齐
1. 什么是内存字节对齐
计算机中内存空间都是按字节划分的，从理论上讲对任何类型的变量的访问可以从任何地址开始，但是在程序实际编译过程中，编译器会对数据类型在编译过程中进行优化对齐，编译器会将各种类型数据按照一定的规则在空间上排列，而不是顺序的排放，这就是内存字节对齐。
2. 为什么要内存字节对齐
不同硬件平台对存储空间的处理是不同的。一些平台对某些特定类型的数据只能从某些特定地址开始存取。比如某些架构的CPU在访问一个没有进行对齐的变量的时候会发生错误,那么在这种架构下编程必须保证字节对齐。其他平台可能没有这种情况，但是最常的情况是，如果不按照适合其平台要求对数据存放进行对齐，会在存取效率上带来损失。比如有些平台每次读都是从偶地址开始，如果一个int型（假设为32位系统）如果存放在偶地址开始的地方，那么一个读周期就可以读出这32bit，而如果存放在奇地址开始的地方，就需要2个读周期，并对两次读出的结果的高低字节进行拼凑才能得到该32bit数据，这样数据读取效率就会很差。
3. 如何实现内存字节对齐
3.1基本数据类型的自然边界对齐
各种数据类型的自然边界对齐值如下：

3.2对齐的规则
为结构体分配内存时，分配的内存大小至少是各个字段的长度和。通常，分配的结构体的长度会大于结构体各个字段的长度和，因为结构体需要对齐，即结构体各字段之间需要填充。
缺省情况下，编译器为结构体的每个成员按其自然边界对齐方式分配空间，按照每个成员被声明的顺序在内存中顺序存储，第一个成员的地址和整个结构体的地址相同。结构体整体的默认字节对齐值是结构体中的所有成员中对齐参数最大的一个的值，结构体长度的计算必须取所用过的所有对齐参数的整数倍。
结构体整体对齐方式取决于结构体中所有成员的自然边界对齐值的最大值和指定对齐值两者中最小的值。
3.3如何指定对齐方式
__attribute__ ((packed)); //取消结构在编译过程中的优化对齐。

__attribute__ ((aligned (n))); //让所作用的结构体、类的成员对齐在n字节自然边界上,如果结构中有成员的长度大于n，则按照机器字长来对齐。n=1,2,4,8,16…


GCC中荐使用这种方式实现字节对齐，关于#pragma pack不推荐使用，因此本文不作论述。
这里强调下取消编译过程中的对齐优化：
__attribute__ ((packed)); //取消结构在编译过程中的优化对齐。

无论是Linux中的GCC，还是windows中的vc编译器，都是非紧凑模式的编译器，默认有字节对齐的优化。前面我们讲过不同平台关于字节对齐的处理可能是不同的，因此在涉及到跨平台通信时，不同的字节对齐方式，可能引起数据解读的问题。
取消编译过程中的优化正是应用在这样的场合，它使得数据成员间紧凑排列，而不会去对齐优化。下面进行举例说明
4.例子
#include <stdio.h>
struct tst1
{
	char  a;
	short b;
	
	int   c;	
};
struct tst2
{
	char  a;
	short b;
	
	int   c;	
	
}__attribute((aligned(4)));

struct tst3
{
	char a;
	short b;
	
	int  c;
}__attribute((aligned(8)));

struct tst4
{
	char a;
	short b;
	
	int  c;
	
}__attribute((packed));
struct tst5
{
	char a;
	int  c;
	
	short b;
};__attribute((aligned(4)));
int main(void)
{
	printf("sizeof(struct tst1):%d\r\n", sizeof(struct tst1));
	printf("sizeof(struct tst2):%d\r\n", sizeof(struct tst2));
	printf("sizeof(struct tst3):%d\r\n", sizeof(struct tst3));
	printf("sizeof(struct tst4):%d\r\n", sizeof(struct tst4));
	printf("sizeof(struct tst5):%d\r\n", sizeof(struct tst5));
	return 0;
	
}

结果如下：
[fiona@fiona test]$ gcc attribute.c -o attribute
[fiona@fiona test]$ ./attribute 
sizeof(struct tst1):8
sizeof(struct tst2):8
sizeof(struct tst3):8
sizeof(struct tst4):7
sizeof(struct tst5):12



从tst1和tst2来看，此结构体的自然对齐是4字节，与成员中最大对齐int一致


从tst2和tst3来看，印证前面的结论结构体整体对齐方式取决于结构体中所有成员的自然边界对齐值的最大值和指定对齐值两者中最小的值。


从tst2和tst4来看，packed参数起了作用，取消了编译过程中的对齐，使结构体紧凑排列


从tst2和tst来看，如果相邻成员放在一起能更接近但不大于对齐方式指定的字节位，编译器是会把它们放在一起看作整体，再作填充，以满足对齐方式，所以据此编排结构体成员可以节省一些空间


5.参考

https://blog.51cto.com/9291927/1790295

系统中的堆、栈和数据结构堆、栈不是一个概念。可以说系统中的堆、栈是真实的内存物理区，数据结构中的堆、栈是抽象的数据存储结构。
栈：实际上就是满足后进先出的性质，是一种数据项按序排列的数据结构，只能在一端(称为栈顶(top))对数据项进行插入和删除。
栈区（stack）— 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
栈的优势是，存取速度比堆要快，仅次于直接位于CPU中的寄存器。但缺点是，存在栈中的数据大小与生存期必须是确定的，缺乏灵活性。
代码：
Stack的基本使用
初始化
Stack stack=new Stack
判断是否为空
stack.empty()
取栈顶值（不出栈）
stack.peek()
进栈
stack.push(Object);
出栈
stack.pop();
实例：
public class Test01 {
 public static void main(String[] args) {
 Stack stack=new Stack();
 //1.empty()栈是否为空
 System.out.println(stack.empty());
 //2.peek()栈顶值    3.进栈push()
 stack.push(new Integer(1));
 stack.push("b");
 System.out.println(stack.peek());
 //4.pop()出栈
 stack.pop();
 System.out.println(stack.peek());
 }
}
以上就是java什么是栈的详细内容，希望对你有所帮助。

指针

    A 什么是指针：

      在计算机中访问数据需要的一个东西叫做 地址：内存区的每个字节都有的一个编号。（区分：地址   &   地址对应的内容）

      在内存中一般是通过变量名来对内存单元进行存取操作。但其实，程序编译后已经将变量名转换为变量的地址，对变量名的存取都是通过地址进行的。

      直接存取（直接访问）：按变量地址存取变量值的方式（变量名也算是变量地址的一种形式，属于直接访问）

      间接存取（间接访问）：将变量 i 的地址存放在另一个变量中。可以定义一种特殊的变量，它是用来专门存放地址的。

i_pointer=&i;

      & 是取地址运算符，&i 是  i 的地址。地址指向该变量单元（通过地址就能找到该变量单元）。

      因此，形象地称：地址为指针（通过它能访问以他为地址的内存单元）。一个变量的地址称为该变量的指针。对应，一个变量的指针就是变量的地址

    一个专门用来存放地址（即指针）的变量，指针变量。

   B 引用指针变量：

     & 取地址运算符；

     * 指针运算符（间接访问运算符）

     &a 为变量a的地址，*p 指针变量p所指向的存储单元。

      例子1：

#include <iostream>
using namespace std;
int main()
{
	int a=100,b=233;
	int *p1,*p2;
	p1=&a;
	p2=&b;
	cout<<a<<' '<<b<<endl;
	cout<<*p1<<' '<<*p2<<endl;
	return 0;
}

      在程序的第6行最然定义了两个指针变量 p1 和 p2 ，但是它们并未指向任一个整形变量，而是只提供两个基类型为整型的指针变量。（用 int* 定义）

      & 和 * 的优先级别相同，按从右而左方向结合。故：& * p1和 & a 相同，都是和“ a 变量的地址” 等价；* & a 与 a 等价。

      例子2：

      输入a和b两个整数，按先大后小的顺序输出 a 和 b （用指针变量处理，不交换整形变量的值，而是交换变量指针的值, a 和 b 的内容并未交换。）

#include <iostream>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	int *p1,*p2;
	p1=&a;
	p2=&b;
	if(a<b)
	{
		int *p=p1;
		p1=p2;
		p2=p;
	}
	cout<<*p1<<' '<<*p2<<endl;
	return 0;
}

     C 用指针作函数参数

       函数的参数也可以是指针类型，它的作用是：将一个变量的地址传送给被调用函数的形参。

       例子3：

        输入a和b两个整数，按先大后小的顺序输出 a 和 b （要求用函数处理，并且用指针变量作为函数参数。）

#include <iostream>
using namespace std;
int main()
{
	void pai(int *p1,int *p2);
	int a,b;
	cin>>a>>b;
	int *p1,*p2;
	p1=&a;
	p2=&b;
	if(a<b)
	{
		pai(p1,p2);
	}
	cout<<a<<' '<<b<<endl;
	return 0;
}
void pai(int *p1,int *p2)
{
	int t;//形参指针p1和p2是无法通过void函数改变的 
	t=*p1;//所以这里通过地址（虚）访问并改变参变量（实）的值，虚实结合 
	*p1=*p2;
	*p2=t;
}

       注：1. 本次选择了交换整形变量的值而非指针变量。p1依旧指向 a ，而p2也依旧指向 b 。

              2. 由于虚实结合的方式是采取单向的“值传递”的方式，只能从实参向形参传递数据，形参质的改变无法传递给实参。

              而通过把指针作为形参，实现了：通过调用函数使变量的值发生变化，在主调函数中使用这些改变了的值。

              3. 和任意其他数据类型一样，不能通过改变形参指针变量的值而使实参指针变量的值改变。

              4. 总结2、3两条，调用函数时不会改变实参指针变量的值，但可以改变指针变量所指向变量的值。

              5. 函数的调用可以（而且只可以）得到一个返回值（即函数值），而使用指针变量作函数参数，就可以通过指针变量改变主调函       数中变量的值。相当于通过函数调用从被调用的函数中得到多个值，如果不用指针变量是难以做到的。

       例子4：

       输入a和b和c三个整数，按先大后小的顺序输出 a 和 b 和 c（要求用函数处理，并且用指针变量作为函数参数。）

#include <iostream>
using namespace std;
int main()
{
	void pai(int *p1,int *p2);
	int a,b,c;
	cin>>a>>b>>c;
	int *p1,*p2,*p3;
	p1=&a;
	p2=&b;
	p3=&c;
	if(a<b) pai(p1,p2);
	if(b<c) pai(p2,p3);
	if(a<b) pai(p1,p2);
	cout<<a<<' '<<b<<' '<<c<<endl;
	cout<<*p1<<' '<<*p2<<' '<<*p3<<endl;
	return 0;
}
void pai(int *p1,int *p2)
{
	int t;//形参指针p1和p2是无法通过void函数改变的 
	t=*p1;//所以这里通过地址（虚）访问并改变参变量（实）的值，虚实结合 
	*p1=*p2;
	*p2=t;
}

     D 数组与指针

       指针既然可以指向变量，也就当然可以指向数组元素。所谓数组元素的指针就是数组元素的地址。

       

p=&a[0];
p=a;//在c++中这两个语句等价

       注：在第二行代码中数组名 a 并不代表整个数组。第二行代码的作用是：把 a 数组的首元素的地址赋给指针变量 p ，而绝非把 a 数组各个元素的值赋给p。

       可以通过指针引用数组元素：

*p=1;//对p当前所指向的数组元素赋予数值1

       ps：1. 若果指针变量p指向数组中的一个元素，则 p+i 指向同一数组中的下一个元素。（p+i 所代表的地址实际上是 p+i*d，d是一个          数组元素所占用的字节数）

               2. 数组名（如 a ）代表是的数组首元素的地址，a+i 也是地址。和 p+i 同理。指针法（能使目标程序质量高，即占内存少，运行       速度快。）

               3. a[3] 数组名后的方括号“[ ]”，实际上是变址运算符。下标法

       例子1：

       下标法表示数组。

#include <iostream>
using namespace std;
int main()
{
	int a[10];
	for(int i=0;i<10;i++)
	{
		a[i]=i+1;
	}
	for(int i=0;i<10;i++)
	{
		cout<<a[i]<<' ';
	}
	return 0;
}

       例子2：

       指针法表示数组。

#include <iostream>
using namespace std;
int main()
{
	int a[10];
	for(int i=0;i<10;i++)
	{
		*(a+i)=i+1;
	}
	for(int i=0;i<10;i++)
	{
		cout<<*(a+i)<<' ';
	}
	return 0;
}

       例子3：

       指针变量法表示数组。

#include <iostream>
using namespace std;
int main()
{
	int a[10];
	int *p=a;
	for(int i=0;i<10;i++)
	{
		*(p+i)=i+1;
	}
	for(int i=0;i<10;i++)
	{
		cout<<*(p+i)<<' ';
	}
	return 0;
}

       注：1. 例子1、2 对每个a[ i ]（或“*(a+i)”）都要计算地址，然后再访问元素。而例子3 是用指针变量直接指向元素，不必每次都重新计算地址。例子3 的效率和执行速度都是三个中最高的（但没有下标法直接）。

              2. 注意数组越界问题！

       用指针变量作为函数形参接受数组地址：

       数组名代表数组首元素地址。用数组名做函数参数传递的是数组首元素所对应的地址。因此，用指针变量作函数形参，同样可以接受从实参传来的数组首元素地址（此时，实参是数组名）。

       例子4：

       将10个整数按由小到大的顺序排列。

#include <iostream>
using namespace std;
int main()
{
	void pai(int *p,int n);
	int a[10];
	int *p=a;
	for(int i=0;i<10;i++)
	{
		cin>>*(p+i);
	}
	pai(a,10);
	for(p=a;p<(a+10);p++)
	{
		cout<<*p<<' ';
	}
	return 0;
}
void pai(int *p,int n)
{
	for(int i=0;i<n-1;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			if(*(p+i)>*(p+j))
			{
				int t=*(p+i);
				*(p+i)=*(p+j);
				*(p+j)=t;
			}
		}
	}
}

      注：1. c++编译系统将形参数组名一律按照指针变量来处理。

             2. 实际上在函数调用时并不存在一个占用存储空间的形参数组！

             3. 实参数组名（如 a ）代表一个固定的地址，或者是说是指针形常量，因此要改变 a 的值是不可能的！

             4. 而形参数组名是一个指针变量，并非一个固定的地址。因而它可以可以改变的。比如在函数开始时，就接受了实参数组首元素地址，在函数执行过程中，它也可以被赋值。

      E 字符串和指针

       在c++中有三种方法可以访问一个字符串。

       例子1：

       用字符数组来存放一个字符串。

#include <iostream>
using namespace std;
int main()
{
	char str[]="I love HNU!";
	cout <<str;
	return 0;
}

       例子2：

       定义一个字符串变量并初始化，然后输出其中的字符串。

#include <iostream>
#include <string>
using namespace std;
int main()
{
	string str="I love HNU!";
	cout <<str;
	return 0;
}

       例子3：

       定义一个字符串指针变量并初始化，然后输出它指向的字符。

#include <iostream>
using namespace std;
int main()
{
	char *str="I love HNU!";//注意这里要用char型！ 
	cout<<str<<endl;
	cout<<*str;//这样的话就只会输出字符串首元素，即‘I’ 
	return 0;
}

       注：1. 第五行，在对字符指针变量初始化时，实际上是把字符串中的第一个字符的地址赋给 str。

               2.在输出时（第六行），系统先输出 str 所指向的第一个字符数据，然后使 str 自动加一，使之指向下一个字符，然后在输出一       个字符。。。如此，直至遇到字符串的结束标志为止。

               3. 在内存中字符串的最后被自动加了一个 ‘\0’ ，因此能在输出时确定字符串的终止位置。

               4. 利用字符串指针来进行两个字符串（字符数组形式）的赋值，是相当痛苦的，要一位一位的赋值。（推荐直接用string型）

     E 函数与指针

       指针变量也可以指向一个函数。一个函数在编译时被分配给一个入口地址。这个函数的入口地址就是函数的指针。可以用一个指针变量指向函数，然后通过该指针变量调用此函数。函数名代表函数的入口地址。

       例子1：

       求 a 和 b 中的大者。（用一个指向 max 的指针变量来调用该函数）

#include <iostream>
using namespace std;
int main()
{
	int max(int a,int b);//函数声明 
	int (*p)(int a,int b);//定义指向函数的指针变量p 
	int a,b;
	cin>>a>>b;
	p=max; //使p指向函数max 
	int m=p(a,b);
	cout<<m;
	return 0;
}
int max(int a,int b)
{
	if(a>b)
	{
		return a;
	}
	else 
	{
		return b;
	}
}

       注：语句 int (*p)(int a,int b); 中，依次的意义为，第一个int：指针变量所指向的函数的类型；（*p）：p 是指向函数的指针变量；（int，int）：p所指向的函数中的形参的函数类型。

              在定义指向函数的指针p时，（*p）两侧的括号不能省略，表示 p 先与 * 结合，在与右面的括号结合。如果省略的话，该语句的含义就变成了：定义一个返回值是指向 int 型的指针的函数！

              在定义完对应函数的指针变量后，还要进行一部操作：使指针 p 指向函数max。来使函数的入口地址赋给指针变量p。

     F 返回指针的函数

       简称为指针函数。在定义时，注意和定义指向函数的指针作区分。

int *p(int x,int y,int z);

     G 指针数组和指向指针的指针

       指针数组：一个数组其元素都为指针类型。指针数组的每一个值都相当于一个指针变量，它们的值都是地址。

       例子1：

       将若干字符串按字母序排序输出。

#include <iostream>
#include <string.h>
using namespace std;
int main()
{
	void sort (char *name[],int n);
	char *name[]={"bnji","fnhij","c++","phbj","co0"};
	int n=5;
	sort(name,n);
	for(int i=0;i<n;i++)
	{
		cout<<name[i]<<endl;
	}
	return 0;
}
void sort (char *name[],int n)
{
	for(int i=0;i<n-1;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			if(strcmp(name[i],name[j])>0)
			{
				char *t=name[i];
				name[i]=name[j];
				name[j]=t;
			}
		}
	}
}

       注：排序函数sort的形参是指针数组明，实参是指针数组name的首元素地址。排序改变的是数组的不同元素所指向的字符串（即指针数组的值——地址）。

       指向指针（数据）的指针。就比如刚才的指针数据name，数组名name就是指针数组首元素的地址。所以name以及（name+ i ）

       例子2：

       指向字符型数据的指针变量。

#include <iostream>
using namespace std;
int main()
{
	char **p;//定义指向指针的指针变量p 
	char *a[]={"aa","bb","cc","dd","ee"};//定义指针数组 
	p=a+2;
	cout<<*p<<endl;//输出name[2]指向的字符串（通过其首字母地址） 
	cout<<**p; //输出name[2]指向的字符串的首字母 
	return 0;
}

     H 感谢您的阅读！

第二章主要说的是线性表，那么什么是线性表呢？

线性表是一种线性结构，在头结点无直接前驱有一个直接后继，尾节点无直接后继有一个直接前驱。

1.线性表的顺序存储结构

简单的说就是把线性表的结点按照它的逻辑结构顺序，依次的存放到计算机内存中一组连续的存储单元中。用顺序存储来实现的线性表为顺序表。这里要注意，如果是存储，则是指按顺序的，如果是存取，则是可以随机的，可以利用元素下标进行。

线性表的基本运算在顺序表上的实现

（1）插入：插入新的结点，之后的结点后移，平均时间复杂度为O(n)

（2）删除：删除结点，之后的结点前移，平均复杂度为O(n)

（3）定位：查找出线性表等于某个结点序号的最小值，当找不到这个结点时，返回结果0

2.线性表的链接存储

线性表的链接存储结构为链式，常见的有：单链表、循环列表和双向循环链表

（1）单链表：每个结点的存储地址是存放在其直接前驱结点next域中，而开始结点无直接前驱，故应设头指针head指向开始结点。同时，由于最后一个结点无直接后继，故结点的指针域为空，即NULL。

（2）循环列表：是一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。在单链表中，将终端结点的指针域NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，

（3）双向循环列表：在单链表的每个节点中再设置一个指向其直接前驱结点的指针域prior，这样每个结点有两个指针。prior与next类型相同，它指向直接前驱结点。都结点的prior指向最后一个结点，最后一个结点next指向头结点。简单来说，设指针X指向某一结点，那么：X→prior→next=X=X→next→prior