结构体类型

结构体的基本介绍

结构的定义

• 结构体是一种构造数据类型，用于把不同类型的数据组合成一个整体；

  struct 结构名       // 结构名可省，但会导致重用不便
  {
      类型    成员1;  // 可定义多个成员
      类型    成员2;  // 成员也可以是其他结构体
  
  };  // 末尾的分号勿漏
  

• 结构体类型定义只描述结构的阻止形式，不分配内存；

• 结构体类型定义的作用域与变量的作用域类似，若将类型定义放在某个函数内，则只能在该函数内定义这种结构体类型的变量；

结构体变量的定义

1. 先定义结构体类型，再定义结构体变量；

   struct complex  // 定义复数的结构体类型
   {
       float re;   // 复数的实部
       float im;   // 复数的虚部
   };  // 注意分号别漏
   complex data;   // 先定义结构体类型，后定义结构体变量
   

   • 定义结构体类型相当于定义表头，定义结构体变量相当于向表中填入数据；

2. 定义结构类型的同时定义结构体变量：

   struct complex  // 定义复数的结构体类型
   {
       float re;   // 复数的实部
       float im;   // 复数的虚部
   }data1, data2;  // 定义结构体complex的同时定义结构体变量data1和data2;
   

3. 直接定义结构体变量(省略结构体名称)

   struct  // 定义无“结构名”的结构体，即所谓直接定义结构体变量
   {
       float re;   // 复数的实部
       float im;   // 复数的虚部
   }data1, data2;  // 定义结构体complex的同时定义结构体变量data1和data2;
   

4. 说明

   • 结构体类型与结构体变量概念不同：
     • 结构体类型不分配内存，而结构体变量分配内存；
     • 结构体类型不能赋值、存取和运算，而结构体变量可以；
   • 结构体类型可以嵌套定义，即一个结构体内可以包含其他结构体；
   • 结构体成员名与程序中的变量名可同名，因为访问结构体成员时需带上结构体变量名前缀，因此不会混淆；

结构体变量的引用

示例程序：

struct student
{
    int num;        // 学号
    char name[20];  // 姓名
    char sex;       // 性别
    int age;        // 年龄
    float score;    // 分数
    char addr[30];  // 家庭住址
}；
student stu1, stu2;

1. 引用方式：结构体变量名\textcolor{red}{.}成员名；

   stu1.num = 10;   // 赋值
   stu1.score += stu2.score  // 计算
   

2. 引用规则：结构体变量不能整体引用，只能引用变量成员：错误示范：

   if (stu1 == stu2)   // 不能直接使用结构体变量整体
   printf(“%d %s %c %d %f %s\n” stu1); // 无法直接引用结构体变量整体
   stu1={101,“Wan Li”,‘M’,19,87.5,“DaLian”};   // 整体进行赋值是不可以的！
   

3. 结构体嵌套时应逐级引用；

4. 结构体变量可以整体赋值给另一个结构体变量，可用于结构体的初始化；

结构体变量的初始化

注意到，结构体变量的定义有三种方式，在定义变量的同时都可以对结构体变量进行初始化：

struct student
{
    int num;        // 学号
    char name[20];  // 姓名
    char sex;       // 性别
    int age;        // 年龄
    float score;    // 分数
    char addr[30];  // 家庭住址
}；
student stu1 = {112,“Wang Lin”,‘M’,19, “200 Beijing Road”};     // 定义结构体变量的同时进行初始化。前面提到**几条狗提变量不能整体引用，即：
// stu1 = {112,“Wang Lin”,‘M’,19, “200 Beijing Road”}; 是错误的用法

结构体变量占用内存情况

sizeof(变量或类型说明符):

#include<stdio.h>
main()
{
    char str[20];
    struct date
    {   int  year,  month,  day;  } today;
    struct address
    {  char name[30], street[40], city[20], state[2];
         unsigned long  int  zip; } wang;
    printf("char:   %d\t", sizeof(char));
    printf("int:    %d\t", sizeof(int));
    printf("long:   %d\t", sizeof(long));
    printf("float:  %d\n", sizeof(float));
    printf("double: %d\t", sizeof(double));
    printf("str:    %d\t", sizeof(str));
    printf("date:   %d\t", sizeof(struct date));
    printf("wang:   %d\n", sizeof(wang));
}

结构体数组

结构体数组基本介绍

• 结构体是一种自定义的数据类型，它和其他基本数据类型int,float等没太大区别，除了结构体类型非常灵活也相对复杂。因此，结构体数组和整型数组等其他基本数组使用方法类似。

• 结构体变量的定义有三种方式，这三种方式中也可以定义结构体数组。最常用的方式是先定义结构体类型再定义结构变量(数组):

  struct student
  {
      int num;
      char name[20];
      char sex;
      int age;
  };
  struct student stu[3];  // 最常用的情况：先定义结构体类型，后定义结构体数组
  // 结构体数组的初始化：本质上是分别初始化数组中的每个结构体元素
  // struct stu[3] = {{...}, {...}, {...}};
  struct student stu[] = {   {100,“Wang Lin”,‘M’,20},
                              {101,“Li Gang", 'M',19}
                              {110,“Liu Yan”,‘F’,19}
                          };
  

• 结构体数组的引用：先通过数组访问符[]访问数组中的结构体类型元素，接着使用成员访问符.访问成员：stu[1].num = 20;；

结构体数组示例说明

示例程序：

struct s
{
    int x;
    int *y;
};
int data[5] = {10,20,30,40,50};
struct s array[5] = {100,&data[0],
                     200,&data[1],
                     300,&data[2],
                     400,&data[3],
                     500,&data[4]
                     };/* arrayy: 结构数 结构数组，初始化 初始化 */
main()
{
    int i=0;            /* 说明变量i并赋初值 */
    struct s s_var;     /* s_ver: 一般的结构变量 */
    s_var = array[0];   /* 整体赋给s_var */
    printf("%d\n", s_var.x);        // 取取s var s_var的成员 的成员xx的值:100
    printf("%d\n", *s_var.y);       //  取s_var的成员指针y所指的内容:10
    printf("%d\n", array[i].x);     // 取array[i]的x的值,i=0,故：100
    printf("%d\n", *array[i].y);    // 取array[i]的指针y所指的内容,i=0,故：10
    printf("%d\n", ++array[i].x);   //  取array[i]的x的值，x加1后输出:101
    printf("%d\n", ++*array[i]].y); // 取array[i]的y所指的内容加1输出:11
    printf("%d\n", array[++i].x);   // i先加1后取array[1]的成员x的值:200
    printf("%d\n", *++array[i].y);   // 将array[i]的指针y先加1后再取y所指的内容输出:30
    printf("%d\n", (*array[i].y)++); // 取array[i]的指针y的内容，输出y，y的内容再加1：31
    printf("%d\n", *(array[i].y++));    // 取array[i]的指针y的内容，输出 y，指针y再加 1：31
    printf("%d\n", *array[i].y++);  // 同 *(array[i].y++)，根据运算符的结合性，输出：40
    printf("%d\n", *array[i].y);    // 输出 y(注意上一行后指针y自增1了)，故结果：50
}

结构体指针

结构体指针基本知识

1. 结构与指针的关系
   • 将指针作为结构中的一个成员；
   • 其二是指向结构的指针（称为结构指针）
2. 结构指针说明的一般形式，如：struct date * pdate, today;。该语句声明了一个结构体类型的指针pdate和一个结构体变量today，注意today不是指针；
3. 通过指针访问结构中的成员：结构指针->成员名等价于(*结构指针).成员名。注意：
   • C语言中() [] . ->这四个运算符的优先级都是最高的15级，并从左到右进行接合。因此，使用(*结构指针).成员名的方式访问指针指向的结构体成员时，小括号()一定不能漏掉；

结构体指针程序分析

struct s
{
    int x;
    int *y; /* y:: 结构中的成员是指向整型的指针 结构中的成员是指向整型的指针 */
} *p;       /* p: 指向结构的指针 */
int data[5] = {10,20,30,40,50}; /* data: 整型数组 */
struct s array[5] = {100,&data[0],
                     200,&data[1],
                     300,&data[2],
                     400,&data[3],
                     500,&data[4]
                     };/* arrayy: 结构数 结构数组，初始化 初始化 */
main()
{
    p = array;  /* 指针p指向结构数组的首地址 */
    printf("%d\n", p->x);   // 取结构指针p指向的结构的成员x的值，输出 100
    printf("%d\n", (*p).x); // 取结构指针p的内容所指的成员x的值，输出 100；访问方式不同
    printf("%d\n", *p->y);  // 取结构指针p的指针成员y所指的内容，输出 10
    printf("%d\n", *(*p).y);// 取指针p的内容的指针成员y的内容，输出 10
    printf("%d\n", ++p->x); // p所指的 x 加1,x 先加1后再输出101,p不加1
    printf("%d\n", (++p)->x);// p指向下一个变量的成员 x
}

### 指针运算与++运算规律小结

由运算符的优先级和结合性决定++操作的对象； 由++的前缀/后缀形式，决定操作的时机。

```c++
++p->x;     // -> 优先级高：先获取p指向的成员x的值，再执行 ++
++ * pp->yy; // 先获取p指向的成员y，接着去除y指针指向的内容，最后执行 ++，即y指向的内容自增 1
* ++ p->y;      // 先获取p指向的成员y，接着指针y自增 1，最后获取自增 1 后的指针指向的值
*(++p)->y;  // 注意：()和->的优先级都为最高的15级，结合性从左至右，因此先执行 ++p，即结构指针自增 1，接着获取自增 1 后的结构体指针指向的成员y，最后获取指针y指向的值

结构与函数

结构与函数的关系

包括以下三种关系：

1. 向函数中传递结构的成员；
2. 在函数之间传递整个结构；
3. 向函数传递结构的地址（指针）

向函数中传递结构的成员

在函数中传递结构成员的方法与传递简单变量的方法相同：

• 在函数之间传递成员的值
• 在函数之间传递成员的地址

printf("%d", man.birthday.year); 传递结构成员的值
scanf("%d", &man.birthday.year); 传递结构成员的地址

#include<stdio.h>
#define STNUM   5  

struct   xscj
{
    char xh[5];
    float cj[2];
    float av;
};

float ave(float x,float y)
{  
    float a;
    a=(x+y)/2.0;
    return a;
}

// 定义函数：以结构类型的变量作为形参
void f1(struct xscj tj)
{
    tj.av=(tj.cj[0]+tj.cj[1])/2.0;
    printf("%s,%5.1f,%5.1f,%5.1f\n", tj.xh,tj.cj[0],tj.cj[1],tj.av);
}

main()
{
  struct xscj xs[4]={{"01",70,80},  {"02",78,67},{"03",56,78},  {"04",90,80}};
  int i;
  for (i=0;i<4;i++)
  {
    xs[i].av = ave(xs[i].cj[0],xs[i].cj[1]);    // 结构体成员作为函数的实参
    // f1(xs[i]);  // 结构体变量作为函数的实参
    printf("%s,%5.1f,%5.1f,%5.1f\n",xs[i].xh, xs[i].cj[0],xs[i].cj[1],xs[i].av);
  }
}

联合

联合和结构的定义和使用非常相似。举个通俗的例子，假设有多种物品需要存放，物品的类型和大小有一定差异，那么结构就是为所有物品开辟一块空间用来存放它们，而联合则仅开辟一块足够放下需存放物品中最大物品的空间。可见，联合用来保存多种数据中的一个，而结构用来保存所有的数据；

联合与结构的异同

1. 联合与结构都是由多个成员分量组成的一个整体；
2. 联合与结构在定义、说明和使用(成员引用、指针)上十分相似。
3. 结构：多个成员分量分别占用不同的存储空间构成一个整体；成员分量之间是相互独立的，所进行的各种操作互不影响。
4. 联合：多个成员分量共同占用同一存储空间；成员分量之间是相互联系的，所进行的操作相互依赖

union <联合类型名>
{
    数据类型 成员名1；
    数据类型 成员名2；
    ...
    数据类型 成员名n；
};

示例程序

main()
{
    union       /* 定义联合并说明联合变量mix */
    {
    long i;     /* 定义long型成员 */
    int k;      /* 定义int型成员 */
    char ch;;   /*定义定义char char型成员 型成员 */
    char s[4];  /* 定义char型数组成员 */
    }mix;

mix.i == 0x12345678; /* 通过联合中的long型成员i为联合赋初值 */

printf("mix.i=%lx\n", mix.i);
printf("mix.k=%x\n", mix.k);
printf("mix.ch=%x\n", mix.i);
printf("mix.s[0]=%x\t mix.s[1]=%x\n", mix.s[0], mix.s[1]);
printf("mix.s[2]=%x\t mix.s[3]=%x\n", mix.s[2], mix.s[3]);
}

联合类型数据的特点

1. 同一个内存段可以用来存放几种不同类型的成员，但在每一瞬时只能存放其中一种，而不是同时存放几种。也就是说，每一瞬时只有一个成员起作用，其他的成员不起作用，即不是同时都存在和起作用。

2. 联合变量中起作用的成员是最后一次存放的成员，在存入一个新的成员后原有的成员就失去作用。如有以下赋值语句：mix.i=1； mix.ch='a';在完成以上2个赋值运算以后，只有mix.ch是有效的，mix.i已经无意义了,此时用printf(“%d”,mix.i)是错误的;

3. 联合变量的地址和它的各成员的地址都是同一地址。例如： &mix.i, &mix.k, mix.ch, mix.s都是同一地址值；

4. 以下做法均是错误的：

   union example
   {
       int i；
       char ch；
       float f；
   };
   

   • union example a={1，'a'，1．5};(不能初始化);
   • a=1; (不能对联合变量赋值 不能对联合变量赋值);
   • m=a; (不能引用联合变量名以得到一个值)

5. 不能把联合变量作为函数参数，也不能使函数返回联合变量(因为数据类型是可变的)，但可以使用指向联合变量的指针(因为指针的类型是不变的)

6. 联合类型可以出现在结构体类型定义中，也可以定义联合数组。反之，结构体也可以出现在联合类型定义中，数组也可以作为联合的成员。

typedef自定义类型

typedef用于自定义新的数据类型，它和宏定义类似，作用于字符串替换相近，但也有微小的差别；

用typedef自定义数据类型的步骤

1. 先按定义变量的方法写出定义体（如：int i）;
2. 将变量名换成新类型名(例如：将i换成COUNT);
3. 在最前面加typedef(例如：typypedef int COUNT);
4. 然后可以用新类型名去定义变量;

示例：

1. 先按定义数组变量形式书写：int n[100];
2. 将变量名n换成自己指定的类型名：int NUM[100];；
3. 在前面加上typedef，得到typedef int NUM[100];；
4. 用来定义变量NUM n;，此时它等价于int n[100];；

说明

• 用typedef可以声明各种类型名，但不能用来定义变量。
• 用typedef只是对已经存在的类型增加一个类型名，而没有创造新的类型。
• 当不同源文件中用到同一类型数据时，常用typedef声明一些数据类型，把它们单独放在一个文件中，然后在需要用到它们的文件中用#include命令把它们包含进来。
• 使用typedef有利于程序序的通用与移植。
• typedef与#define有相似之处，例如：typedef int COUNT;和#define COUNT int的作用都是用COUNT代表int。但事实上，它们二者是不同的:
  • #define是在预编译时处理的，它只能作简单的字符串替换;
  • typedef是在编译时处理的。实际上它并不是作简单的字符串替换，而是采用如同定义变量的方法那样那样来声明一个类型。

枚举

结构和联合等数据结构让我们可以非常自由地设计数据类型，与它们相反的是，枚举意在限制数据类型的定义。在定义只有7天星期类型、只有15个学院的学院类型等情境下尤为有用。

枚举类型的定义

枚举类型：如果一个变量只有几种可能的值，可以定义为枚举类型。所谓“枚举”是指将变量的值一一列举出来出来，变量的值只限于列举出来的值的范围内 变量的值只限于列举出来的值的范围内。

格式：enum 类型名 {数据表列};，例如：enum weekday {sun，mon，tue，wed，thu，fri fri，，sat sat};

枚举类型说明

1. 在C编译中，对枚举元素按常量处理，故称枚举常量。它们不是变量，不能对它们赋值。例如:sun=0;mon=1;是错误的。
2. 枚举元素作为常量，它们是有值的，C语言编译按定义时的顺序使它们的值为0，1，2,...。也可以改变枚举元素的值，在定义时由程序员指定，如:enum weekday{sun=7,mon=1,tue,wed,thu,fri, sat}workday, weekend;定义sun为7，mon=1，以后顺序加1，sat为为6;
3. 枚举值可以用来做判断比较。如if(workday == mon)...和if(workday＞sun)...。枚举值的比较规则是按其在定义时的顺序号比较。如果定义时未人为指定，则第一个枚举元素的值认作0。故mon大于sun，sat＞fri;
4. 一个整数不能直接赋给一个枚举变量。如：workday=2;是不对的，它们属于不同的类型。应先进行强制类型转换才能赋值。如：workday=(enum weekday)2；

链表

解决数据动态存储的问题。

链式存储

• 用一组地址任意的存储单元存放数据集合中的数据元素
• 以元素(数据元素) + 指针指针(指示后继元素存储位置)结点
• 以“结点的序列”表示 —— 称作链表

链表的组成

• 链表: 由结点组成
• 头指针: 指向链表的开始，每个链表都必须有。
• 头结点：链表的第一个节点不存数据，可没有。
• 数据结点 数据结点：保存数据和指针 保存数据和指针（指向其他结点）
• 尾结点：没有指针的节点，置为“\0”(NULL)

链表基础

malloc和free函数

1. 动态存储分配函数malloc：void * malloc(int size). 使用示例：

   struct student * ps;
   ps=(struct student *)malloc(sizeof(struct student));
   

   • 由于malloc函数默认返回void类型指针，因此需使用强制类型转换来转换指针类型：struct student *;
   • malloc需要知道需分配的内存的大小,sizeof(struct student)可获取结构变量所占用的内存大小；

2. 释放内存函数：void free(void *p)。每个malloc分配的内存都需要和一个free函数配对以实现内存的分配和释放。

链表完整示例

//#include <stdio.h>   // 包含标准输入输出函数库
//#include <stdlib.h>  // 包含标准函数库：malloc函数和free函数

struct  node
{  
    char name[20],address[20],phone[15];    // 步骤 1：定义节点 = 数据域 + 指针域
    struct node  * link;        /* 步骤 2：指针域，定义node型结构指针 */
};                              /* 定义结构 */
typedef node NODE;              /* 定义结点类型：节点名大写，提高可读性 */

main()
{
    NODE * head ;       // 步骤 2：说明头指针 head
    NODE * p;
    p =(NODE *)malloc(sizeof(NODE));  /* 步骤 3：开辟新存储区，申请表头节点 */
    p->link = NULL;         /* 将表头节点的link置为NULL*/
    head = p;               /* 将处理好的节点地址赋给头指针，完成头指针的创建 */
    int create(NODE * head , int n);    /* 使用create前需要先声明该函数 */
    create(head, 2);

    p =(NODE *)malloc(sizeof(NODE));
    gets(p->name);
    int insert_node(NODE * head , NODE * p , int i);
    insert_node(head, p, 1);

    int output(NODE * head);
    output(head);

    int delete_node(NODE * head , int i);
    delete_node(head,2);

    output(head);

    getchar();
}

// 创建节点：创建的新节点都在头节点后插入，形参n为希望插入的节点个数
int create(NODE * head , int n)
{
    NODE * p;   // 声明节点指针备用
    for(;  n>0 ;  n--)
    {
        p =(NODE *)malloc(sizeof(NODE));    // 开辟新存储区，申请新节点
        gets(p->name);          // 为节点的数据域赋值
        p->link = head->link;   // 将新节点p指针域指向节点插入前头结点的下一个节点
        head->link = p;         // 将新节点p插入到指针之后
    }
    return 0;           // 插入结束则返回 0，私以为返回值意义不大
}

// 输出节点
int output(NODE * head)
{
    NODE * p;       // 声明节点指针备用
    p = head->link;        /* p 指向第一个数据节点，头指针是没有数据的 */
    while(p!=NULL)
    {   puts( p->name);   /* 输出 p 所指向节点的数据 */
        p = p->link ;     /* p 指向下一个数据节点 */
    }
    return 0;
}

// 在第 i 个节点后插入新节点 p
int insert_node(NODE * head , NODE * p , int i)
{
    NODE * q;
    int n=0;
    // 条件 n < i 控制循环在 i = n 时退出循环
    for(q = head;  n<i && q->link!=NULL; ++n)
        q = q->link;        /* ① 定位 */
    p->link = q->link;      /* ② 链接后面指针 */
    q->link = p;            /* ③ 链接前面指针 */
    return 0;
}

// 删除第 i 个节点
int delete_node(NODE * head , int i)
{
    NODE * q, * p;
    int n;
    for(n=0, q = head;  n<i-1 && q->link!=NULL; ++n)
        q = q->link;                 /* ① 定位 */
    if(i>0 && q->link != NULL)  
    {
        p = q->link;                /* p 指向被删除节点 */
        q->link = p->link;          /* ② 摘链 */
        free(p);                    /* ③ 释放 p节点 */
    }
}

// 获取链表的长度
int length(NODE * head)
{
    int len;    // 定义整型变量用于计数节点
    NODE *p;    // 说明节点指针备用
    for(len = 0, p = head->link; p != NULL; ++len)
        p = p->link;
    return(len);
}

链表引用——约瑟夫问题

15个基督教徒和 个基督教徒和1515个异教徒在海上遇险 个异教徒在海上遇险，必须将 半的人 必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一个圆圈，从第一个人开始依次报数，每数到第 9 个人就将他扔入大海，如此循环进行直到仅余 15 人为止。问怎样排法，才能使每次投入大海的都是异教徒?

/*约瑟夫问题*/
// #include <stdio.h>   /* 包含标准输入输出函数库 */
// #include <stdlib.h>  /* 包含标准函数库：malloc函数和free函数 */

// 创建链表的步骤
struct node {       // 步骤 1：定义节点 = 数据域 + 指针域
        int no;             // 数据域：人员的编号
        struct node * next; // 指针域：指向下一个节点(人员)
    };

main()
{
    int i, k;  
    struct node *head, *p, *q;  // 步骤 2：说明头指针 head

    // 步骤 3：按照结构大小分配一块内存并将内存地址赋值给头指针
    head =(struct node *)malloc(sizeof(struct node));
    head->no   = -1;        // 为头指针数据域赋值(一般不赋值)，但赋一个特殊值可标志表头指针
    head->next = head;      // 为头指针的指针域赋值(一般为NULL)。此处头指针的指针域设置头指针本身，可实现循环链表

    // 按照顺序创建链表：新节点总是在表头后插入，因此编号1的节点在最后插入，而编号30的节点第一个插入
    for(i=30; i>0; i--)                       /* 步骤 3:生成循环链表 */
    {
        p =(struct node *)malloc(sizeof(struct node)); // 继续分配一块内存区域
        p->next = head->next;  // 新节点在表头节点后插入，新插入的节点后面的节点恰为插入前表头节点后的节点
        p->no   = i;    // 为新节点数据域赋值：人员编号
        head->next = p;     // 新插入的节点总是在表头节点之后
    }

    // 输出整个链表
    printf("\nThe original circle is :");
    while(p->next != head)              /* 循环链跳过表头结点 */
        p = p->next;
    // 循环结束时，p指向最后一个节点，即 p 指向第 30 个节点
    p->next = head->next;                 /* 删除头结点，使得第30个节点的下一个节点指向第 1 个节点 */

    // 约瑟夫问题求解的核心代码从此处开始

    // 游戏规则是当只剩15个人时终止，由于总共30人，因此需要把把15个人扔到海里。故循环需执行 15次
    for(i=0; i<15; i++)
    {
        // 每一次都需要找到被扔到海里的那个人：从当前第一个人开始数，每数到第9个人被人出去
        for(k=1 ; k<9 ; k++)    // 先略过前8个不被扔到海里的人
            p = p->next;
        q = p->next;                    /* p 的下一个结点为第9个，恰是要出列的结点 */
        p->next = q->next;              /* 删除节点：循环链表跳过要出列的结点 */
        printf("%3d", q->no);           /* 输出 q 结点的编号 */
        free(q);                        /* 释放 q 结点 */
    }
}