《数据结构》预备

在学习数据结构之前，需要预先准备学习的C语言知识是：自定义类型--结构体类型。

本节主要讲的内容有：

1.结构体类型的声明

2.结构体变量的创建和初始化

3.结构成员的访问操作符

4.结构体传参

5.结构体内存对齐

6.结构体实现位段(位域)

正文开始： 

---

一、结构体类型的声明

前面我们了解过整型int、浮点型double（float）、字符型char等常见的数据类型。之后又学习了数组，一个数组只能存储同一种数据类型的数据，随着我么们学习的不断深入，我们的需求越来越高，那么想要在一个数组内同时存储多种数据类型的变量，我们就可以通过本节来讲的结构体数据类型来解决这个问题。

这时候就会有一个问题，数组的定义不就是同一数据类型的数据的集合吗，我存储了多种类型的数据这不违背了我们的认知吗。其实并非如此，数组存储数据的本质还是存储同一种数据类型，只不过，这种数据类型囊括了多种数据类型的成员而已。简单来说，就好比：原本我们以为一个数组只能存储笔、橡皮等类型的物品，但现在我们想让一个数组能同时存下笔和橡皮，你会怎么办，那我们是不是可以买一个笔盒，里面装上橡皮和笔两种类型的物品就可以了，这样的话，这个数组存储的实质是笔盒这个类型的物品，它并不在乎笔盒里面装的是什么。

下面我们将结构体的声明代码放下来，再回过头理解一下，哪些代码相当于笔盒，哪些代码相当于笔和橡皮：

struct MyType
{
    int num;
    char ch;
};//分号不能丢
 
int main()
{
    struct MyType Arr[2]={{1,'A'}，{2,'B'}};
    //...
    return 0;
}

 很明显，MyType这个自己定义的数据类型就是笔盒，里面装有橡皮和笔类型的物品，也就对应着int和char类型的数据。Arr这个数组中存放的数据就是MyType类型的数据，每个MyType类型的数据中都包含了int和char类型的数据，这样就解决了我们上面提出的问题。

下面给出声明模板：

struct tag//tag叫做结构体标签，前面加上struct就是这个新的自定义类型。
{
    member-list;
}variable-list;//分号不可丢

第一种情况：只声明类型，不定义变量：

struct tag{member-list;};

第二种情况：声明类型并同时定义一个或多个变量：

struct tag{member-list;}tag1,tag2;

第三种情况：只定义变量，不指定结构体类型标签(也叫做，匿名结构体类型)

struct {member-list;}x,y;

下面我们定义一个学生类型的数据类型，包括姓名、年龄、性别、学号。

struct Student
{
    char name[20];//姓名
    int age;//年龄
    char sex[5];//性别
    char id[20];//学号
};//第一种：只声明类型，暂不定义变量
 
struct Stu
{
    char name[20];
    int age;
    char sex[5];
    char id[20];
}s1,s2;//第二种：声明类型并与此同时定义了s1，s2两位学生数据类型的变量
 
struct 
{
    char name[20];
    int age;
    char sex[5];
    char id[20];
}x,y;//第三种：匿名结构体。这种情况下，如果不定义变量的话，结构体的声明将无任何意义。
 
struct 
{
    char name[20];
    int age;
    char sex[5];
    char id[20];
}*p;

 这里有一个问题帮助大家理解第三种情况的声明：在上述声明的基础上，p=&x;这行代码合法吗？

答案是不合法，编译器会将下面两个声明当作完全不同的两个类型，所以是非法的。这里也就有了一个结论：匿名结构体类型，如果没有对结构体类型进行重命名的话，基本上只能使用一次。

除了匿名结构体外另一个特殊的结构体就是含自引用的结构体，顾名思义就是自己引用自己，也就是笔盒里面除了其它东西外还装了一个同类型的笔盒。代码如下：

struct DataType
{
    int len;
    struct DataType data;
};

但这样真的是对的吗？如果对的话，sizeof(struct DataType)是多少呢？仔细分析，其实是错误的，因为一个结构体再包含一个同类型的结构体变量，这样的结构体变量的大小就会使无穷大，是不合理的。正确的自引用方式是：

struct DataType
{
    member-list;
    struct DataType *data;
};

也就是说，一个笔盒不可能放得下同样的笔盒 ，但可以放下记录另一个笔盒位置的小纸条。也就是我们说的指针。

但是还需要注意一点，在结构体子引用的过程中，夹杂了typedef对匿名结构体类型的重命名，也容易引入问题，不要提前使用重命名。来看一段代码：

typedef struct
{
    member-list;
    Stu *s;
}Stu;//这个Stu可不是变量哦，是结构体类型的小名。

 这段代码指定是错误的，因为Stu是对前面的匿名结构体类型的重命名产生的，但是在匿名结构体内部提前使用Stu类型来创建成员变量，这样是不行的，非法的。

 解决方法：定义结构体不要使用匿名结构体了。

是不是神奇的很呐。好了，让我们接着看下面要了解的内容。

---

 二、结构体变量的创建和初始化

知道结构体是怎么回事，怎么声明之后，那么我们就要创建结构体类型的变量了。其实我们帮助大家理解举例笔盒时就已经创建过结构体类型的变量了，为了让大家方便，不用往上翻了，直接看下文吧。

struct Stu
{
  char name[20];
  int age;  
};
 
int main()
{
    struct Stu s={ "张三", 18};//依次赋值
    printf("name: %s\n",s.name);
    printf("age: %d\n",s.age);
 
    struct Stu ss={ .age=20, .name="Marry"};//按照指定的顺序初始化
    printf("name: %s\n",ss.name);
    printf("age: %d\n",ss.age);
 
    return 0;
}

有时候会在声明该类型时就赋予结构体成员缺省值：

struct Stu
{
    char name[20];
    int age=18;
};
//这段代码意味着
//如果用该类型声明变量的话，不给变量成员age赋值
//那么该变量成员age会自动等于18.

---

三、结构成员的访问操作符

结构体成员的访问是通过“.”操作符访问的，在上面创建并初始化结构体类型数据时打印数据结果的时候我们就可以看到点操作符的使用方法。此外，如果是结构体指针类型，那么我们也是这么访问吗？好像不是这样的。

struct Stu
{
    int num;
    cahr ch;
};
 
int main()
{
    struct Stu data={1,'A'};
    struct Stu* sptr=&data;
    printf("直接访问%d--%c\n",data.num,data.ch);
    printf("间接访问%d--%c\n",sptr->num,sptr->ch);
    return 0;
}

呦，这是什么东东？"->"其实就是结构体指针访问成员的操作符。 它是由一个减号-和一个大于号>组合而成的运算符。

---

四、结构体传参

现在有一个问题：结构体类型的数据能够直接赋值吗，比如：

typedef struct Student
{
    char id[20];
    char name[20];
    char sex[6];
    int age;
}stu;
 
stu s1={"123","lbx","nan",19};
stu s2=s1; 

试着打印结果，运行结果显示可以直接使用等号=赋值。除了这种方法外，我们还可以写一个函数来赋值，要求这个函数声明行只能使用该结构体数据类型。

既然结构体类型是一种数据类型，那么自然也可以出现在函数的参数列表以及返回值当中。

例如：结构体成员太多，我们不可能一一传入或是一一传出，那么结构体类型的数据整体作为参数进行传输就显得方便了许多。

现在我们将上述代码重新用一个方法进行赋值：

typedef struct Student
{
    char id[20];
    char name[20];
    char sex[6];
    int age;
}stu;
 
stu GetStu(stu st)
{
    //法1：直接返回
    return st;
    //法2：间接返回
    stu s;
    s.id=st.id;
    s.name=st.name;
    s.sex=st.sex;
    s.age=st.age;
    return s;
}
 
stu s1={"123","lbx","nan",19};
stu s2=GetStu(s1);

其实这段代码主要是为了让大家知道结构体可以作为参数和返回值来进行传输，实际赋值没必要这么复杂。但是，假如有两个结构体里面的结构一致，我们可以直接赋值吗？

显然不可以。那么我们就可以运用上面的法2来进行赋值：

typedef struct Employee
{
	int num;
	char name[20];
	double salary;
}Emp;
typedef struct Teacher
{
	int num;
	char name[20];
	double salary;
}Tch;
 
Tch GetMsg(Emp e)
{
    Tch t={e.num,e.name,e.salary};
    return t;
}
Emp e={1,"123",3.1415};
Tch t=GetMsg(e);

同时还存在结构体指针，用法同普通指针一样，不作赘述。 而且，在传输结构体类型的数据时，一般都会选择传入结构体指针。原因是：

函数传参时，参数需要压栈，会有时间和空间上的系统开销。

如果传递一个结构体对象的时候，结构体过大，参数压栈的系统开销比较大，所以会导致性能下降。

结论，也可以说是推荐吧：结构体传参时，需要传结构体的地址。

---

五、结构体内存对齐

我们已经掌握了结构体的基本使用方法了。现在我们深入讨论一个问题：计算结构体的大小。

这也是一个特别热门的考点：结构体内存对齐

1).对齐规则

1.结构体的第一个成员对齐到和结构体变量起始位置偏移量为0的地址处。{即：结构体第一个成员的地址和结构体变量的地址一致}

2.其它成员变量要对齐到对齐数(编译器默认对齐数 与 该成员变量大小 的较小值)的整数倍的地址处。{VS中默认值为8，Linux中gcc没有默认对齐数，对齐数就是成员自身大小}

3.结构体总大小为最大对齐数(结构体中每个成员变量都有一个对齐数，所有对齐数中最大的)的整数倍。

4.如果嵌套了结构体的情况，嵌套的结构体成员对齐到自身的成员中最大对齐数的整数倍处，结构体的整体大小就是所有最大对齐数(含嵌套结构体中成员的对齐数)的整数倍。

Tips：//字节对齐

1.找成员当中最大的类型进行对齐 结果一定是它的整数倍

2.分配空间时 要按照成员变量定义的顺序进行 不能自由组合分配空间

3.空间分配时，要做到整数倍地址对齐

2).为什么存在内存对齐

大部分的参考资料上是这样说的：

1.平台原因（可移植性方面）：不是所有的硬件平台都能访问任意地址上的任意数据的；某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常。

2.性能原因：数据结构，尤其是栈，应该尽可能地在自然边界上对齐。原因在于，为了访问未对齐的内存，处理器需要作两次访问；而对齐的内存访问仅需要一次访问。假设一个处理器总是从内存中取8个字节，则地址必须是8的倍数。如果我们能保证所有的double类型的数据的地址都对齐成8的倍数，那么就可以用一个内存操作来读写值了。否则，我们需要执行两次内存访问，因为对象可能被分放在两个8字节内存块中。

总的来说：结构体的内存对齐是拿空间来换取时间的做法。

那在设计结构体的时候，我们就需要满足对齐，又节省空间，具体做法就是：让占空间小的成员尽量集中在一起。

struct s1{
    char c1;
    int i;
    char c2;
};
 
struct s2{
    char c1;
    char c2;
    int i;
};

s1和s2类型的成员一模一样，但是s1和s2占用的空间大小有了一些区别。//后者占用空间更小。

3).修改默认对齐数

没有默认对齐数的对齐都是缺省对齐。#pragma这个预处理指令，可以改变编译器的默认对齐数。使用方法如下：{这就给了我们一个启示：结构体在对齐方式不合适时，我们可以自己更改默认对齐数。}

#pragma pack(1)//设置默认对齐数为1
 
struct S{
    char c1;
    int i;
    char c2;
}；
#pragma pack()//取消设置的对齐数，还原为默认
 
int main()
{
    printf("%d\n",sizeof(struct S));    
    return 0;
}

---

六、结构体实现位段(位域)

结构体讲完就得讲讲结构体实现位段(位域)的能力。

1).什么是位段

位段的声明和结构体是类似的，有两个不同：

1.位段的成员必须是int、unsigned int、 signed int，在C99中位段成员也可以选择其它类型。

2.位段的成员后边有一个冒号和一个数字。

比如：

struct A{
    int _a:2;
    int _b:5;
    int _c:10;
    int _d:30;
};

A就是一个位段类型。那位段A所占内存的大小是多少呢？printf("%d\n",sizeof(struct A));

2).位段的内存分配

1.位段的成员可以是int、unsigned int、signed int、或者是char等类型

2.位段的空间上是按照需要以4个字节int或者1个字节char的方式来开辟的

3.位段涉及很多不确定因素，位段是不跨平台的，注意可移植性的程序应该避免使用位段。

//⼀个例⼦
struct S
{
 char a:3;
 char b:4;
 char c:5;
 char d:4;
};
struct S s = {0};
s.a = 10;
s.b = 12;
s.c = 3;
s.d = 4;
//空间是如何开辟的？

3).位段的对齐方式

Tips://位域

成员：之后的数字表示的是 所占的bit是多大

1.分析相邻的两个成员是否是同种类型，如果是同种类型可以考虑放置在同一单位下

2.如果相邻的成员超出一个单位 那么就放在两个单位里面，放置的时候不允许跨单位存储。

4).位段的跨平台问题

1.int位段被当成有符号数还是无符号数是不确定的。

2.位段中最大位的数目不能确定。（16位机器最大16，32位机器最大32，写成27的话在16位机器会出问题）

3.位段中的成员在内存中从左向右向左分配，标准未定义。

4.当一个结构包含两个位段，第二个位段成员比较大 ，无法容纳于第一个位段剩余的位时，是舍弃剩余的位还是利用，这是不确定的。

总结：跟结构相比，位段可以达到同样的效果，并且可以很好的节省空间，但是有跨平台的问题存在。

5).位段的应用

下图是网络协议中，IP数据报的格式，我们可以看到其中很多属性只需要几个bit位就能描述，这里使用位段就能够实现想要的效果，也节省了空间，这样网络运输的数据报大小也会较小一些，对网络的畅通是有帮助的。

6).位段使用的注意事项

位段的⼏个成员共有同⼀个字节，这样有些成员的起始位置并不是某个字节的起始位置，那么这些位置处是没有地址的。内存中每个字节分配⼀个地址，⼀个字节内部的bit位是没有地址的。
所以不能对位段的成员使⽤& 操作符，这样就不能使⽤scanf直接给位段的成员输⼊值，只能是先输⼊放在⼀个变量中，然后赋值给位段的成员。

struct A{
 int _a : 2;
 int _b : 5;
 int _c : 10;
 int _d : 30;
};
int main()
{
 struct A sa = {0};
 scanf("%d", &sa._b);//这是错误的
 
 //正确的⽰范
 int b = 0;
 scanf("%d", &b);
 sa._b = b;
 return 0;
}

---

感谢大家！