第8章 结构

第8章 多种数据信息的整体包装——结构

在大千世界层出不穷的众多数据信息中，有时候只用一种数据类型的信息难以描述一种事物，难以处理一个问题。例如学生成绩表中最起码有2～3种数据类型的数据，姓名属于字符数组或字符串数据类型；学号可用字符数组、字符串或整型的数据类型；成绩可用浮点型、整型、双精度型中的任一种数据类型。只有这几种数据组合在一起才能描述清楚每个学生的成绩情况，这可是前面的景点中没有见到过的。前面学的数据类型都是单一的数据类型，C++把这些分散的景点巧妙地构造成了一个绚丽多彩的景点——结构，下面来欣赏C++是如何将多种数据信息包装成一个整体的。

8.1 打印学生成绩单的例题详解

【例 8-1】有 n 个学生，每个学生的数据包括学号、姓名、m 科的成绩，输入这 n 个学生的数据并打印，要求用自定义的方式定义 n 和 m，打印格式要对齐。

1. 用心分析人想通，机随人行写提纲

人的做法如图8-1所示。

2. 对号入座写文章，头脑运行改文章

（1） 定义结构数组

前面曾经把数组比喻为大套间，数组元素是大套间里的小房间，数组里放的是同一种类的东西（同一数据类型的数据），如电视机。而结构里放的是不同种类的东西（不同数据类型的数据），如电视机、冰箱、洗衣机等（即可以放 int、double、char 等不同数据类型的数据），若把相同的结构都放在一起，就形成了结构数组。例如，本例的学生成绩数据如图 8-2 所示，所有这些数据可以组成一个结构数组 stu，里面放了多个学生（NUM）的成绩数据，即有一个大套间 stu，大套间里有若干个小房间 stu[0]，…，stu[NUM-1]，每个小房间里面又

划分成若干个区域，区域1放学号、区域2放姓名、区域3放成绩，区域3中又分成几个小格，每个小格中放各科成绩。上述的每一个小房间就是一个结构，暂且给这个结构起个名字student，那么结构student就是数组stu中的每个元素的数据类型，则有定义语句如下：

student stu[NUM];//定义 student 这种结构数据类型的结构数组变量 stu

从中可以看出，定义结构数组的格式与定义数组的格式（如 int al[NUM];）一样，只不过 student 不是 C++已有的数据类型而已。按先定义后使用的原则，在定义 stu 之前必须先声明 student 这个结构数据类型。根据题意，学生数据中的学号一般用整型或字符数组，姓名用字符数组，成绩用整型或其他类型。由于多科成绩是同一种数据类型，所以不必要分开设置多个变量，而是用数组变量代替，该数组变量放在结构类型中。此例声明了一个结构 student 如下：

struct student //声明结构 student，关键字 struct 表示结构
{
    int id;//声明学号变量
    char name[10];//声明姓名变量
    int score[MAX];//声明成绩数组变量
};

注意：“{}”内的所有变量的声明与以前所述的定义变量的格式一样；在“}”后要加“；”，这是结构声明的一个关键。

准备好了存放数据的房间（结构数组），就可以存数据了。

（2） 输入数据

现在可以唱输入这部曲了，同例6-1一样，采用循环语句输入数组的数据。结构数组和数组的用法基本相同，区别在于结构数组还可以在每个小房间里分区域放东西，即可以使用结构分量。调用结构分量的格式为：

$$ 结构数组元素名 . 结构分量名 $$

即相当于：

结构变量名.结构分量名

因为结构数组中的每个元素都是变量，与以前所讲的数组中的每个元素都是变量的道理

是一样的。

例如，stu[i].id 是结构数组 stu 的第 i 个元素的学号，其中 stu[i] 是结构数组第 i 个元素的名，id 是结构中的分量。

由于输入多科的成绩是重复动作，所以也采用循环输入。

（3） 输出数据

输出显示数据也采用循环语句。

程序代码如下：

#include<iostream.h>
#include<iomanip.h>
#define MAX3 //宏定义课程数目 MAX 为 3
#define NUM2 //宏定义学生人数 NUM 为 2
struct student //声明结构 student
{
    int id;//声明学号变量
    char name[10]; //声明姓名变量
    int score[MAX]; //声明成绩数组变量
};

void main()
{
    student stu[NUM]; //定义 student 这种结构类型的结构数组变量 stu
    for(int i=0;i<NUM;i++) //输入数据到 stu 中
    {
        cout<<"学号：";
        cin>>stu[i].id;
        cout<<"姓名：";
        cin>>stu[i].name;
        cout<<"英语 计算机 中文成绩：";
        for(int j=0;j<MAX;j++)
            cin>>stu[i].score[j];
    }
    cout<<setiosflags(ios::left) //左对齐输出 stu 中的数据的字段名栏
    <<setw(10)<<"学号："
    <<setw(10)<<"姓名："
    <<setw(10)<<"英语"
    <<setw(10)<<"计算机"
    <<setw(10)<<"中文成绩"<<endl;
    for(i=0;i<NUM;i++) //左对齐输出 stu 中的数据
    {
        cout<<setw(10)<<stu[i].id
            <<setw(10)<<stu[i].name;
        for(int j=0;j<MAX;j++)
            cout<<setw(10)<<stu[i].score[j];
        cout<<endl;
    }
}

}

}

因为程序中多次用到课程数目 MAX 和学生人数 NUM，所以采用宏定义这两个常量值的方式，以增强程序的可读性和可维护性，使得在修改这两个常量值时不至于多处修改。

宏定义#define 是用宏名代替一个字符串，其格式如下：

#define 宏名 字符串

宏名同变量名的起名方法一样，不过其中的字母一般全部大写。

输出格式的调整一般要用到控制符，控制符是在头文件 iomanip.h 中定义的对象，所以要加上#include包含指令。此例采用了左对齐格式 setiosflags(ios::left)，且要设置填充字符宽度的控制符 setw(10)。经过多次运行及不断调整，setw 中的数字才定为 10，由此得到较为美观的显示界面。一般都需要通过这样的过程来调整界面，读者可以自行尝试。

3. C++帮助且裁判，人定胜机凯歌扬

上机实验记录如表8-1所示。

运行结果：

结果正确。

8.2 勤奋实践，总结评分

8.2.1 习题

1. 编写一个程序，存储几个学生的姓名、电话和宿舍号的信息，查找时，输入姓名就可以显示该学生的这3项信息。

2．用结构变量管理班里任意10个学生的高数成绩，信息包括学号、姓名、高数成绩。功能包括从低分到高分的排序，打印高数成绩前三名学生的信息，删去某个转专业学生的信息。

3．某商店已有10种商品，商品信息包括商品名称、型号、数量、单价，这些商品信息已存储在计算机中，现在需要加入一种商品，请把该商品的信息添加进去。

1. 顾客要在第3题的商店中按单价查找商品，能帮帮他吗？

1. 在第3题中，某种商品的进货数量错了，如何修改？

1. 听别人说，有一本书很好，但不知道图书馆有没有，在计算机上查找一下吧，请编写程序实现。

图书数据结构为：索引号、书名称、作者、状态，状态下又分为借书数量和归还数量。

1. 编写一个程序——速记英语单词智力竞猜游戏。

利用随机函数显示某个英语单词，参加者先输入自己的竞赛序号，继而 $ \underset{\cdot}{输} $入 y（代表对）或 n（代表错），正确得 5 分，错误得 0 分，最后评选出智力优胜冠军、亚军和季军。

8．请编程设计一道快速心算的智力竞赛游戏：利用随机函数选取某数学题，如“ $ 18\times6+9=? $”，由参赛者抢答，即谁想到答案了就按下自己的参赛号码，接着输入答案并按〈Enter〉键，计算机据此加以评判，答案正确就得10分，游戏结束时评出冠军、亚军和季军，并显示其得分。邀请几位同学、朋友、家人玩一下，一定会很有趣，同时也会给智力的提高带来莫大的好处。

1. 在本章的第2题中，插入一位转学过来的同学，将其插入在第3序号处，如何做？

10\. 用链表方式管理 5 个学生的单科成绩、学号或姓名，请进行输入、删除和修改操作。

8.2.2 思考题

1. 本章习题第2题最好用什么结构变量来处理？

1. 在 1～7 中选择一个整数，该整数代表星期一到星期天中的一天，打印出该整数对应的星期几的英文名称和该天必做的一两件事情的英文名称。

8.2.3 总结评分，继续提高

浏览体验了例题、习题和思考题之后，说说自己的体会和收获，并认真总结，按表8-2给自己评判一下可以得多少分。

不论得分多少，大家都要总结经验，扬长避短，勤奋努力，不断提高。

最后浏览一下本章的第4节，可以先考考自己再浏览，以便使重点知识掌握得更牢固。

8.3 结构知识

结构——想象一个房间的结构，是由墙壁、窗户和门等组成的，而墙壁、窗户和门是由不同的材料制作的，即不同的材料可以构成一个房间。C++也一样，它也能将不同的数据信息搭建成一个结构，这样一种结构数据类型，将会为编写程序、解决问题带来极大的便利。

8.3.1 在什么情况下用到结构

当要将两种以上不同数据类型的数据结合在一起，成为新数据类型的数据时，就会用到结构。

8.3.2 关于结构

1. 什么是结构

结构——将两种以上不同数据类型的数据组合成一种新的数据类型。即结构也是一种数据类型，只不过它是含有多种数据类型的组合式数据类型。可以定义结构这种变量，从而对该变量进行各种处理运用。例如，可以将职工姓名、职工号、职工年龄等构成职工这种结构数据类型。也可以定义职工结构的结构变量，从而对结构变量进行输入、存储、输出等操作。

2. 如何声明结构数据类型和定义结构变量

读者可能会注意到，以前都是定义变量和常量，怎么现在多了一个名词——声明？

以前讲的定义，又叫起名字，即在存储器内开了一个房间，将变量和常量放在房间里，把数据保存起来。而声明是没有在存储器内开房间，如本章所介绍的结构这种数据类型、下一章将讲到的函数的原型、类、引用、外部变量等的说明都是声明。

（1） 定义结构变量

定义结构变量和定义普通变量的格式相同，结构变量也是变量，只是现在的数据类型是结构数据类型而已。使用时首先要自定义一种结构数据类型或选用 C++ 已定义的某种结构数据类型。

（2） 声明结构数据类型

声明结构数据类型和定义结构变量的格式可以合二为一，故放在一起讲述（注意：关键字 struct 是 C++规定的，表示结构）。

声明结构数据类型和定义结构变量有以下4种方式（注意：所有分量（变量）的声明同以前所述的定义变量的格式一样）。

1）方式一：只声明结构数据类型。

struct 结构名

{

第一种数据类型的声明（分量1）；

第二种数据类型的声明（分量2）；

・・・

第 n 种数据类型的声明（分量 n）；

【例8-2】请声明一个具有职工姓名、职工号、职工年龄的结构。

struct per //声明结构名为 per 的结构数据类型
{
    char name[10]; //声明姓名
    int num;//声明职工号
    int age;//声明年龄
};

这只是声明，还需要定义某个变量为这种结构数据类型，通过这个变量才能用上所声明的结构数据类型。

【例 8-3】

per work1; //定义一个 per 结构数据类型的结构变量 work1

如果与一个整型变量 x 的定义句比较，其对应关系如图 8-3 所示。

2）方式二：声明结构数据类型与定义结构变量合：为一。

struct 结构名

第一种数据类型的声明（分量1）；

第二种数据类型的声明（分量2）；

...

第 n 种数据类型的声明（分量 n）；

}结构变量名；

【例 8-4】用方式二定义一个 per 结构数据类型的结构变量 work1。

struct per //声明结构名为 per 的结构数据类型
{
    char name[10]; //声明姓名
    int num;//声明职工号
    int age;//声明年龄
} work1;//定义一个 per 结构数据类型的结构变量 work1

3）方式三：先声明结构数据类型，再定义结构变量并进行初始化。

struct 结构名

第一种数据类型的声明（分量1）；

第二种数据类型的声明（分量2）；

...

第 n 种数据类型的声明（分量 n）；

};

结构数据类型 结构变量名={结构变量的初始化数据}；

【例 8-5】用方式三定义一个 per 结构数据类型的结构变量 work1，并进行初始化。

方式一

per work1={"张三",10000,26};//定义一个per结构数据类型的结构变量 work1,

//并给其赋初值，按 per 中安排的分量顺序给 work1 赋初始值

结构变量的初始化数据之间用逗号分隔。

4）方式四：声明结构数据类型，定义结构变量并进行初始化合三为一。

struct 结构名
{
    第一种数据类型的声明（分量1）；
    第二种数据类型的声明（分量2）；
    ...
    第n种数据类型的声明（分量n）；
}

结构变量名={结构变量的初始化数据}；

【例 8-6】用方式四定义一个 per 结构数据类型的结构变量 work1，并进行初始化。

方式二={"张三",10000,26};//定义一个per结构数据类型的结构变量 work1，//并给其赋初值，按per中安排的分量顺序给work1赋初始值

3. 如何使用结构变量

对于以前定义的变量，例如“int a;”，要使用这个变量可以通过名字 a，同理，可以通过结构变量名使用结构变量。要用到结构变量名下的分量时，要加以区分。在生活中，喊张三这个人名，相当于喊结构变量名，而张三的书包、张三的课本等结构分量如何使用呢？C++中用小数点符号表示中文这个“的”字，即 C++ 使用结构变量的格式为：

结构变量名. 结构分量名

例如：

张三.书包

张三.课本

8.3.3 如何运用结构

结构变量也必须先定义，然后才能使用。即先声明结构数据类型，然后定义该结构数据类型的结构变量。结构变量与以前所讲的变量的定义和使用方法基本相同（区别只在于取结构分量的操作中）。可以为结构变量赋值，并取出它的值来进行各种操作，如数学运算、赋

值、列成表格、输出显示、输出打印等，下面就一起来欣赏体验吧。

1. 定义结构变量及赋初始值

使用8.3.2节中介绍的方式一至方式四中的任意一种均可，如例8-2～例8-6所示。

1. 除初始化外，随时对结构变量赋值

【例8-8】

cin>>work1.name;
work1.num=10000;
work1.age=26;

注意：不能写为“work1.name="张三";”。

【例 8-9】

cout<<"请输入职工姓名、职工号和职工年龄";

cin>>work1.name>>work1.num>>work1.age;

【例 8-10】

不能这样写：

work1={"张三",10000,26};

否则会出现如下错误：

error C2059: syntax error : '{}

E:\C++\hc++\C++BOOK\八章\ex8-2.cpp(25) : error C2143: syntax error : missing '; before '{}

E:\C++\hc++\C++BOOK\八章\ex8-2.cpp(25) : error C2143: syntax error : missing '; before '{}

执行 cl.exe 时出错.

ex8-2.exe - 1 error(s), 0 warning(s)

这种情况只能用初始化的形式定义，即 “per work1={张三”,10000,26};”，也就是只有使用方式三或方式四才正确。

3. 将结构变量输出打印

【例 8-11】

cout<<work1.name<<"\t"<<work1.num<<"\t"<<work1.age;

运行结果：

张三 10000 26

结果正确。

注意：不能写成“cout<<work1;”。

4. 对结构变量的其他操作

还可以取结构分量进行比较、统计、修改、查询等操作。

下面举几个例子说明比较、查询操作。

（1）运用结构变量进行操作

【例 8-12】请编写一个程序，按职工号查找是否有张三这位职工。

int n1;
cout<<"请输入要查找的职工号:";
cin>>n1;
if(work1.num==n1)
{
    cout<<"有张三这位职工，其姓名和年龄为：";
    cout<<work1.name<<"\t"<<work1.age<<endl;
}
else
cout<<"没有张三这位职工\n";

运行结果：

请输入要查找的职工号：10000

有张三这位职工，其姓名和年龄为：张三 26

结果正确。

【例 8-13】请编写一个程序，按职工姓名查找是否有张三这位职工。

//ex8-12-2.cpp
#include<iostream>
using namespace std;

struct per //声明结构名为 per 的结构数据类型
{
    char name[20]; //声明姓名
    int num;//声明职工号
    int age;//声明年龄
} work1;//定义一个 per 结构数据类型的结构变量 work1

void main()
{
    cout<<"请输入在职职工的姓名"<<endl;//用“per work1={"张三",10000,26};”代替这行起的 //4 行内容也正确
    cin>>work1.name;
    work1.num=10000;
    work1.age=26;
    char name1[20];
    cout<<"请输入要查找的职工姓名：";
    cin>>name1;
    if(strcmp(work1.name,name1))
        cout<<"没有"<<name1<<"这位职工\n";
    else
    {
        cout<<"有"<<name1<<"这位职工，其职工号和年龄为：";
        cout<<work1.num<<"\t"<<work1.age<<endl;
    }
}

运行结果：

请输入在职职工的姓名

张三

请输入要查找的职工姓名：张三

有张三这位职工，其职工号和年龄为：1000026

结果正确。

用 C++ 标准函数中的字符串比较函数 “int strcmp(work1.name, name1);”，当相等时，返回值为 0，表明上述程序是正确的。

【例 8-14】请编写一个程序，按职工姓名查找是否有张三这位职工，职工姓名用字符串变量。

//ex8-12-1.cpp
#include<iostream>
#include<string>
using namespace std;

struct per //声明结构名为 per 的结构数据类型
{
    string name;//声明姓名为字符串变量
    int num;//声明职工号
    int age;//声明年龄
} work1;//定义一个 per 结构数据类型的结构变量 work1

void main()
{
    work1.name="张三"; //用“cin>>work1.name;”代替也正确
    work1.num=10000;
    work1.age=26;
    char name1[20];
    cout<<"请输入要查找的职工姓名�";
    cin>>name1;
    if(work1.name==name1)
    {
        cout<<"有"<<name1<<"这位职工，其职工号和年龄为：";
        cout<<work1.num<<"\t"<<work1.age<<endl;
    }
    else
        cout<<"没有"<<name1<<"这位职工\n";
}

因为用了字符串变量，所以可直接用 “if(work1.name==name1)” 比较。

运行结果：

请输入要查找的职工姓名：张三

有张三这位职工，其职工号和年龄为：1000026

结果正确。

（2） 运用结构指针变量进行操作

结构数据类型的变量也是一种变量，是变量就有地址，所以可以定义结构类型的指针指向该结构变量，也就是定义结构指针变量，从而可以用指针来操作定义的结构变量。使用结构指针变量操作时，只需用“->”代替上面使用的点操作符“.”，即操作时用“结构指针变量名->结构分量名”，如“pl->name”，其中pl是结构指针变量名，name是结构per中的分量名。

就像使用指针一样，定义了指针，还要定义该指针指向的结构变量，还是用取地址符“&”把结构变量的地址送给结构指针变量，例如：

per *p1;//定义一个 per 结构数据类型的指针变量 p1

p1=&work1;//将指针 p1 指向结构变量 work1

【例 8-15】请定义一个 per 结构数据类型的结构变量 work1，并定义一个 per 结构数据类型的指针变量 p1，对职工信息进行输入与输出。

//ex8-15.cpp
#include<iostream>
using namespace std;

struct per //声明结构名为 per 的结构数据类型
{
    char name[20]; //声明姓名
    int num;//声明职工号
    int age;//声明年龄
} work1;//定义一个 per 结构数据类型的结构变量 work1

void main()
{
    per *p1;//定义一个 per 结构数据类型的指针变量 p1
    p1=&work1;//将指针 p1 指向结构变量 work1
    cout<<"请输入职工姓名、职工号和职工年龄\n";
    cin>>p1->name>>p1->num>>p1->age;
    cout<<p1->name<<"\t"<<p1->num<<"\t"<<p1->age<<endl;
}

运行结果：

请输入职工姓名、职工号和职工年龄

李英 20003

27

李英 20003 27

结果正确。

同理，用 “->” 代替上面使用的点操作符 “.” 后，可以相应地进行上述各种结构变量的操作。

5. 结构数据类型在数组中的应用

一个单位有 n 个职工，那么相同的职工结构数据类型在一个单位中就有 n 个，那是不是就定义 n 个这样的结构变量呢？如果定义 n 个结构变量，那就太麻烦了，程序也太长了，对这些变量也不好管理。前面不是看到过数组这个景点吗，它可以将相同的数据类型组合在一起。相同的结构数据类型也是相同的数据类型，只不过它里面不是单一的某种数据类型。不管它的内部，只看它的外部，就是某种结构的单一数据类型。一组相同的 int 可以组成一个数组 “int a[3];”，那么一组相同的 per 也可以组成一个数组，如 “per wa1[3];”。这种数组叫结构数组，相当于 “int a[3];” 叫整型数组。实际上，结构数组并不是什么另立山头的数组，它还是数组，只不过数组中的数据是结构这种数据类型，不再是整型而已。二者之间的区别可以通过图 8-2 和图 6-3 的异同来理解。结构数组的用法与前面叙述的数组的用法相同，只不过因为要区分使用的是 “per wa1[3];” 中的哪个分量，故用法为 “数组用法+结构用法”，即 “结构数组名[下标]。结构分量名”。因为结构数组也是一种变量，所以结构数组的用法只是比结构变量的用法多加一个下标，以指明结构数组变量中的某个元素。

例如，例 8-1 中的 “stu[i].name” 前面的 “stu[i]” 是数组用法，指明结构数组变量 stu 中的第 i 个元素，后面的 “.name” 是结构用法，指明是 name 这个结构分量。

结构数组的示意图可参见图8-2。

因为结构数组就是结构变量的一种特例，而结构指针可以指向结构变量，那么也可以定义一个指针指向结构数组，该指针称为结构数组指针。结构数组指针的用法同结构指针，只是要用结构数组指针变量名代替结构指针变量名而已。

【例 8-16】将例 8-1 改为用结构数组指针代替结构数组的程序。

//ex8-16-2.cpp
#include<iostream.h>
#include<iomanip.h>
#define MAX 3 //自定义 MAX 代表课程数目
#define NUM 3 //自定义 NUM 代表学生人数
struct student //声明结构 student
{
    int id;
    char name[10];
    int score[MAX];
};

void main()
{
    student stu[NUM]; //定义 student 这种结构类型的结构数组变量 stu
    student *ps=stu;//定义 student 这种结构类型的结构数组指针变量 ps，ps 指向结构数组 stu
    //的第一个元素的地址，因为数组名代表了数组第一个元素的地址
    for(int i=0;i<NUM;i++)//输入数据到 stu 中
    {
        cout<<"学号：";
        cin>>ps->id;//输入学号到结构数组指针 ps 所指的结构分量 id 中
        cout<<"姓名：";
    }
}

cin>>ps->name;
cout<<"英语 计算机 中文成绩：";
for(int j=0;j<MAX;j++)
    cin>>ps->score[j];

ps++;//输入完一个学生（单元）的数据，指针要往前移动一个单元

}

ps=stu;//输入完所有数据后，指针要指回该结构数组的第一个单元，

//以进行下述的操作

cout<<setiosflags(ios::left)//左对齐输出 stu 中的数据的字段名栏

<<setw(10)<<"学号:"

<<setw(10)<<"姓名:"

<<setw(10)<<"英语"

<<setw(10)<<"计算机"

<<setw(10)<<"中文成绩"<endl;
for(i=0;i<NUM;i++) //左对齐输出 stu 中的数据
{
    cout<<setw(10)<<ps->id
    <<setw(10)<<ps->name;
    for(int j=0;j<MAX;j++)
        cout<<setw(10)<<ps->score[j];
    cout<<endl;
    ps++;
}

运行结果：

姓名：___

英语 计算机 中文成绩：90

80

50

学号：2

姓名：w

英语 计算机 中文成绩：60

78

93

学号：3

姓名：王

英语 计算机 中文成绩：70

65

40

学号：___ 姓名：___ 英语 计算机 中文成绩：___

1 q 90 80 50

2 w 60 78 93

3 王 70 65 40

结果正确。

8.3.4 结构的特殊运用——链表

从图8-2中可以看到，当想增加职工人数或减少职工人数时，用结构数组是很不方便的。若想增加职工人数，在程序运行中是不能做到的（只能修改程序）。C++有个好主意，那就是将分立的结构用结构指针串联起来，形成链接起来的结构表——链表。此时就可以很好地解决上述问题。这就相当于自行车的链条一样，把链圈（结点）用链钩（指针）连接起来。

1. 什么情况下用到链表

在程序运行中对一组数据进行添加、删除、修改等操作时，可以采用链表。

链表弥补了数组的不足，便用数组不能在程序运行中增加或减少数组元素的个数，也不方便进行删除数组元素等操作。链表还弥补了堆只能用于地址连续的数组这一不足（堆的知识将在第16章中介绍）。

2. 链表知识

（1） 什么是链表

链表是将一些数据通过指针链接起来的数据结构表，有许多种，本书以线性链表（以下简称链表）为例，进行讲述。

链表是由一组相同数据类型的数据（链圈）链接在一起形成的结构表，数据（链圈）之间是用这种数据类型的指针（链钩）进行链接的。

链表可以是首尾封闭的环链（即链尾指针指向链首），也可以是有头有尾的开口链表，下面以开口链表为例进行讲述，其构造如图8-4所示。

从图8-4中可看出，构成一个链表必不可少的组成部分包括：

1）若干个链圈（结点），其中含有链表结构数据的内容（简称链圈数据）和该链表结构的指针（简称链钩）。

2 ）两个指针（链首指针和链尾指针）。

链首和链尾这两个指针的数据类型与链钩指针的数据类型是一样的，都是该链表结构的数据类型；链首指针指向第一个链圈，它是辨认链表的唯一标志，末尾链圈（结点）的链钩就是链尾指针，其值为 NULL，表示空地址，链表到此结束；链钩起到将若干个链圈（结点）连接起来的作用，这样就形成了一个链表。

（2） 链表的声明和定义

链表是一种变量，变量要先定义，然后才能使用。

请读者将图8-4与图8-2比较一下，看得出来，二者基本相像，都是有若干个大房间，大房间里有小房间，只不过链表的各个大房间（链圈）之间的地址不一定连续，而结构数组

的各个大房间的地址却是连续的，即链表结构与结构的差别是：链表结构中多了一个必不可少的结构分量——链钩指针，在声明和定义链表时需注意这个差别，其他与声明和定义结构是一样的。

链表的定义分为如下两步。

1）声明链表结构数据类型。

先来看一个例子。

【例 8-17】例 8-2 中声明了职工结构数据类型 per，若要将其声明成链表结构，应如何声明（为简化分析，去掉姓名这个分量）？

struct plist//声明链表结构名为 plist 的结构，即一个链圈的结构，用于链表中 {
int num;//链圈的内容之一：职工号
int age;//链圈的内容之二：年龄

plist *p;//链圈的内容之三：声明链钩（链钩指针）

};

声明链表这种结构数据类型的格式为：

声明结构数据类型的方式——具体见8.3.2节的第2点

声明中，增加了一个必不可少的分量：

方式一声明的结构名*链钩指针名：

如例 8-17 中增加的分量 “plist *p;”。

可以看出，链表结构只是结构的一种特例，无非是结构分量中多了一个链钩指针。

声明了链表结构后，就可以定义链表了。

2 ）链表的定义

链表怎样定义呢？看看图8-4中链表的构造有什么，就定义什么。链表有两个指针和若干个链圈。因为链圈（结点）在存储器中的位置不一定连续，所以链钩将链圈链接起来是靠地址，而指针是存储地址的，对地址的操作用指针比较方便，所以一般把链表变量定义为指针这种类型的变量，定义链表指针变量的格式为：

链表结构名 *链表指针变量名：

【例 8-18】

plist *p11;//定义 p11 为链表指针，该链表结构为 plist

定义一个链表至少要定义多少个链表指针变量呢？至少三个以上，其中两个是链首指针和链尾指针，还有一个是链钩指针，这三个指针对于创建链表就够了，而对于删除或添加等操作，还需要一些中间辅助指针，中间辅助指针视程序的需要而定，例如查找指针等。定义好链表后，就可以进行创建链表等操作了。

（3） 如何组成及运用链表

定义了所需的几个链表指针变量后，就可按图 8-4 所示的链表的构造组成一个链表

了。因为这几个链表指针变量是指针，而且是结构指针，所以具体构成链表的操作就是按照前面讲过的运用指针的方法和运用结构指针变量的方法来进行的，并没有什么特殊的东西。即组成链表的方法是：运用指针和结构指针的操作将一个个链圈用链钩链接成一个链表，然后就可以利用链表对数据进行添加、删除、修改等操作了。有如下一些运用指针和结构指针的操作。

1）某链圈的指针名。代表该链圈本身，如 head、inp 等，即 head 指针名、inp 指针名就是代表 head 链圈和 inn 链圈。

2）某链圈的指针名->链圈数据。代表该链圈的数据，如例 8-19 中的“pp->num”，即 pp 链圈的数据 num。

3）某链圈指针名->链钩。代表该链圈的下一个链圈，如例8-20中有：

pd=pf->p;//将 pf 链圈的链钩 p 指向的链圈（即 pf 的下一个链圈）送给 pd 链圈

4）指针之间的相互赋值，例如：

head=inp;//将指针 head 指向指针 inp

组成及运用链表的具体例子请见下方的“3. 链表的运用”。

3. 链表的运用

可以对链表进行很多种操作，例如创建链表，添加、删除、修改链表数据等。

（1）创建链表、为链表赋值和显示链表

要画出（建立）链表，需要先知道什么是链表，链表是怎样形成的。一提到链表，就想到自行车的链条，链表的样子就是自行车链条的样子。可以把创建链表想象成装配自行车链条，装配链条的过程如图8-5所示。创建链表结束时的示意图如图8-4所示。

【例 8-19】创建一个含有职工号和职工年龄的链表（按职工号从小到大的顺序连接），并输入和输出这些数据，职工人数自定，请编写程序实现。

//ex8-19-1.cpp
#include<iostream.h>
//创建链表

struct plist//声明结构名为 plist 的结构，即一个链圈的结构，用于链表中 {
    int num;//链圈的内容之一：职工号
    int age;//链圈的内容之二：年龄
    plist *p;//链圈的内容之三：声明链钩（链钩指针）
};

void main()
{
    plist *head;//定义链表首部记号（链首指针），简称链首
    plist *pn;//定义待加入链圈的指针
    plist *pe;//定义链表尾部记号（链尾指针），简称链尾

pn=new plist;//先拿一个待加入链圈，即用 new 升一个链圈的房间（动态空间）

cout<<"循环输入待加入的职工号和年龄；若要结束输入，输入职工号为0"
&lt;&lt;"和任一年龄，并按 Enter 键"<<endl;
cin>>pn->num>>pn->age;//给这个链圈加内容

head=NULL;//开始没有链条，则令链表首部记号为空

while(pn->num!=0)//当待加入链圈的职工号不等于0时，循环加入链圈
{
    if(head==NULL)//如果链首为空
        head=pn;//待加入的链圈就送给链首
    else
        pe->p=pn;//否则，链尾的链钩钩住这个待加入的链圈
    pe=pn;//这个待加入的链圈就送给链尾（即把待加入的链圈作为链尾）
    pn=new plist;//再拿下一个待加入链圈
    cin>>pn->num>>pn->age;
}

pe->p=NULL;//链尾的链钩指向空，代表这条链到此为止

delete pn;//释放待加入链圈的房间

*创建链表函数的程序解释（行数从 void main()算起）：

第3～8行如图8-6所示；第一次运行第9～12、15行如图8-7所示；第一次循环结束时如图8-8所示；第二次运行第13～15行如图8-9所示；创建链表结束时的示意图如图8-4所示*/

plist *pp;//定义显示使用的链表指针

pp=head;//pp 指向链首

cout<<"职工号"  "<<"年龄"<<endl;
while(pp)//当显示链表指针 pp 为 1，即 pp!=NULL（即 pp 没指到链尾）时，循环输出链圈
//内容
{
    cout<<pp->num<<"  "<<pp->age<<endl;
    pp=pp->p;//pp 指针移向下一个链圈
}

运行结果：

循环输入待加入的职工号和年龄；若要结束输入，输入职工号为0和任一年龄，并按Enter键1000020

10001

39

0

40

职工号年龄

10000 20

10001 39

结果正确。

结果正确。

（2） 输出显示链表的数据

输出显示链表数据（见例 8-19）的过程是；将显示链表指针 pp 指向链首指针，再利用 pp 指针的移动指引，一直将链圈内容（链表的数据）从链首到链尾全部输出显示。

（3） 对链表数据进行查询、比较等操作

对链表数据进行查询、比较等操作时，取出数据的基本动作与输出显示链表数据时一样，只不过取出来不是用于输出显示，而是用于查询、比较等操作而已，所以设计思路和流程图基本一致。在例 8-19～例 8-21 中，有多处查询、比较操作，如 “while(pn->num!=0)”、“if(head->num==num)” 等。

（4） 在链表中删除数据

把在链表中删除数据当做从自行车链条上拆下链圈来处理，人的做法如图 8-10 所示，其中有 3 种情况。（注：在图 8-11～图 8-13、图 8-15～图 8-17 中，“→”表示断开原来的链钩连接，虚线表示修改（删除或添加）后的链钩连接。）

【例 8-20】在创建的含有职工号和职工年龄的链表（按职工号从小到大的顺序连接）中，删除某个职工号的职工数据，请编写程序实现。

//ex8-20-1.cpp
#include<iostream.h>

//创建链表

struct plist//声明结构名为 plist 的结构，即一个链圈的结构，用于链表中
{
    int num;//链圈的内容之一：职工号
    int age;//链圈的内容之二：年龄
    plist *p;//链圈的内容之三：声明链钩（链钩指针）
};

void main()
{
    plist *head;//定义链表首部记号（链首指针），简称链首
    plist *pn;//定义待加入链圈的指针
    plist *pe;//定义链表尾部记号（链尾指针），简称链尾
    pn=new plist;//先拿一个待加入的链圈，即用 new 开一个链圈的房间（动态空间）
    cout<<"循环输入待加入的职工号和年龄；若要结束输入，输入职工号为 0"
    <<"和任一年龄，并按 Enter 键"<endl;
    cin>>pn->num>>pn->age;//给这个链圈加内容
    head=NULL;//开始没有链条，则令链表首部记号为空
    while(pn->num!=0)//当待加入链圈的职工号不等于 0 时，循环加入链圈
    {
        if(head==NULL)//如果链首为空
            head=pn;//这个待加入的链圈就送给链首
        else

pe->p=pn;//否则，用链尾的链钩钩住这个待加入的链圈

pe=pn;//将这个待加入的链圈送给链尾（即把待加入链圈作为链尾）

pn=new plist;//再用一个待加入链圈

cin>>pn->num>>pn->age;

}

pe->p=NULL;//链尾的链钩指向空，代表这条链到此为止

delete pn;//释放待加入链圈的房间

/*创建链表函数的程序解释（行数从“void main()”算起）:

第3～8行如图8-6所示；第一次运行第9～12、15行如图8-7所示；第二次运行13～15行如图8-9所示；第一次循环结束时如图8-8所示*/

//显示链表

plist *pp;//定义显示使用的链表指针

pp=head;//pp 指向链首

cout&lt;&lt;"职工号"  "<<"年龄"<<endl;
while(pp)//当显示链表指针 pp 为 1，即 pp!=NULL（链尾）时，循环输出链圈内容
{
    cout&lt;&lt;pp->num&lt;&lt;"  "<<pp->age<<endl;
    pp=pp->p;//pp 指针移向下一个链圈
}

删除链圈

int num;//职工号
int b=0;//删除标记初始化为 0
cout<<"请输入要删除的职工号";
cin>>num;

plist *pd;//定义要拆链圈的指针

plist *pf;//定义查找链圈的指针

//处理下述 3 种情况
if(!head)//如果是空链表
{
    cout<<"这是空链表\n";
}
else
{
    if(head->num==num)//如果要删除的职工号在链首
    {
        pd=head;//将链首的链圈送给要拆链圈
        head=head->p;//链首钩住要拆链圈后面的链圈
        //（则要拆链圈就脱钩了，如图 8-11 的虚线所示）
        delete pd;//删除要拆链圈
        cout&lt;&lt;"删除了职工号为"<<num<<"的数据"<<endl;
        b=1;//删除标记置 1
    }
    else
    {
        pf=head;
        while(pf->p)//要删除的职工号在指定位置，从链首的下一个链圈起，逐个查找
        //找到要拆的链圈或找到链尾（pf->p=NULL，如图 8-13 所示）时，结束循环
    {
        if(pf->p->num==num)//如果查找指针的链钩钩住的链圈（pf->p)

//的职工号（->num）等于要找的职工号
{
    pd=pf->p;//下一个链圈就是要拆链圈，将它送给要拆链圈
    pf->p=pd->p;//将要拆链圈前面的链圈（即查找指针指向的链圈）的//链钩钩住要拆链圈后面的链圈（则要拆链圈就脱钩了，即拆下了这个要拆链圈，如图8-12或图8-13（这是删除链尾链圈的情况）的//虚线所示）
    delete pd;//删除要拆链圈
    cout<<"删除了职工号为"<<num<<"的数据"<<endl;
    b=1;//删除标记置1
    break;//跳出 while 循环
}

pf=pf->p;
}

if(b==0)//如果没有删除
    cout<<"没有此职工。\n"<<endl;//当从头到尾都找不到时，应给予提示
}

//又显示链表

pp=head;//pp 指向链首

cout<<"职工号 "<<"年龄"<<endl;
while(pp)
{
    cout<<pp->num<<" "<<pp->age<<endl;
    pp=pp->p;
}

运行结果：

循环输入待加入的职工号和年龄；若要结束输入，输入职工号为0和任一年龄，并按Enter键100

20

101

39

0

0

职工号 年龄

100 20

101 39

请输入要删除的职工号100

删除了职工号为100的数据

职工号 年龄

101 39

结果正确

结果正确。

（5） 在链表中插入数据

把在链表中插入数据当做往自行车链条上安装链圈来处理，人的做法如图 8-14 所示，其中有4种情况。

第4种情况是要插入到链尾时，即下述语句中的前一种情况：

if((pi->p==NULL))||(pi->p->num>inp->num))//如果查找指针的链钩已到了链尾（NULL）或钩住//的链圈的职工号大于要添加的职工号

这种情况的处理请读者自行尝试。

【例 8-21】在创建的含有职工号和职工年龄的链表（按职工号从小到大的顺序连接）中，插入某个职工号的职工数据，请编写程序实现。

//ex8-21-1.cpp
#include<iostream.h>

//创建链表

struct plist//声明结构名为 plist 的结构，即一个链圈的结构，用于链表中
int num;//链圈的内容之一：职工号
int age;//链圈的内容之二：年龄

plist *p;//链圈的内容之三：声明链钩（链钩指针）

};
void main()
{
}

plist *head;//定义链表首部记号（链首指针），简称链首

plist *pn;//定义待加入链圈的指针

plist *pe;//定义链表尾部记号（链尾指针），简称链尾

pn=new plist;//先拿一个待加入链圈，即用 new 开一个链圈的房间（动态空间）

cout<<"循环输入待加入的职工号和年龄；若要结束输入，输入职工号为0"
<<"和任一年龄，并按 Enter 键"<<endl;
cin>>pn->num>>pn->age;//给这个链圈加内容

head=NULL;//开始没有链条，则令链表首部记号为空

while(pn->num!=0)//当待加入的链圈的职工号不等于0时，循环加入链圈
{
    if(head==NULL)//如果链首为空
        head=pn;//这个待加入的链圈就送给链首
        else
        pe->p=pn;//否则，链尾的链钩钩住这个待加入的链圈
    pe=pn;//这个待加入的链圈就送给链尾（即把待加入链圈作为链尾）
    pn=new plist;//又拿下一个待加入链圈
    cin>>pn->num>>pn->age;
}

pe->p=NULL;//链尾的链钩指向空，代表这条链到此为止

delete pn;//释放待加入链圈的房间

/*创建链表子函数的程序解释（行数从 void main()算起）：

第3～8行如图8-6所示；第一次运行第9～12、15行如图8-7所示；第二次运行第

图8-9所示；第一次循环结束时如图8-8所示*/

//显示链表

plist *pp;//定义显示使用的链表指针

pp=head;//pp 指向链首

cout<<"职工号"
"<<"年龄"<<endl;
while(pp)//当显示链表指针 pp 为 1，即 pp!=NULL（链尾）时，循环输出链圈内容
{
    cout<<pp->num<<"
        "<<pp->age<<endl;
    pp=pp->p;//pp 指针移向下一个链圈
}

//插入链圈

{
    cout<<pp->num<<"  "<<pp->age<<endl;
    pp=pp->p;//pp指针移向下一个链圈
}

入链圈

plist *pi;//定义查找指针

plist *inp;//定义待插入链圈的指针 inp

inp=new plist;//新开--间待插入链圈的房间

cout<<"请输入要插入的职工号和年龄";
cin>>inp->num>>inp->age;
while(1)
{
    if(head==NULL)//如果是空链表
    {
        cout<<"原来是空链表\n";
        head=inp;//链首指针（一只手）指向（拉着）待插入链圈，如图8-15中的虚线1
        //所示
        inp->p=NULL;//待插入链圈的链钩（另一只手）指向（拉着）NULL，代表这
        //条链到此为止，如图8-15中的虚线2所示，手拉手加入到链表中
        cout<<"现已插入数据\n";
        break;//跳出 while 循环
    }
    if(head->num>inp->num)//如果要插入的职工号在链首
    {
        inp->p=head;//待插入链圈的链钩（一只手）钩住链首链圈，如图8-16中的虚线1
        //所示
        head=inp;//链首指针（另一只手）钩住待插入链圈，如图8-16中的虚线2所示，
        //手拉手加入到链表中
        break;//跳出 while 循环
    }
    for(pi=head;pi;pi=pi->p)//从链首的下一个链圈起，逐个查找，找到插入位置或找到链尾
        //（pi->p=NULL）时，结束循环
        if((pi->p==NULL))((pi->p->num>inp->num))//如果查找指针的链钩
        //已到了链尾（NULL）或钩住的链圈的职工号大于要添加的职工号
        {
            inp->p=pi->p;//待插入指针的链钩（一只手）钩住待插入链圈之后的链圈，
            //如图8-17中的虚线1所示
            pi->p=inp;//待插入链圈之前的链钩（另一只手）钩住待插入链圈，
            //如图8-17中的虚线2所示，手拉手就加入到了链表中
            break;//跳出 for 循环
        }
        break;//跳出 while 循环
}

//显示插入后的链表

pp=head;//pp 指向链首

cout<<"职工号"   "<<"年龄"<<endl;
while(pp)
{
    cout<<pp->num<<"   "<<pp->age<<endl;
    pp=pp->p;
}

运行结果：

循环输入待加入的职工号和年龄；若要结束输入，输入职工号为0和任一年龄，并按Enter键

10000

29

10001

40

0

34

职工号 年龄

10000 29

10001 40

请输入要插入的职工号和年龄 10008

35

职工号 年龄

10000 29

10001 40

10008 35

结果正确。

8.3.5 控制输出格式法

用户会不会有这样的困惑：程序输出结果的形式都是由cout等语句摆布的，有时不整齐、不美观，总之不尽人意，那人就无能为力了吗？记住：人定胜机。人设计了在C++中用控制输出格式法来重新布置输出阵地，让我们来看个究竟吧。

1. 在什么情况下用控制输出格式法

当对输出格式有具体要求时，可以使用控制输出格式法。

2. 关于控制输出格式法

方法有两种，下面介绍其中的一种——使用控制符控制。

控制输出格式法的控制符如表8-3所示。

（续）

使用控制输出格式法时，要将控制符加在cout语句中，其语法格式如下：

cout<<输入输出流控制符 1[<<...<<输入输出流控制符 n]<<要输出的信息;

即先写控制符，再写要按此控制符输出的信息。

控制符是在头文件 iomanip.h 中定义的，使用控制符时，要包括此头文件，即要写上“#include”。

【例 8-22】编写控制显示圆周率 $ \mathrm{pi}=3.14159 $ 的程序，要求其小数点后输出 4 位有效数字。

解法一：

const float pi=3.14159;
cout<<setprecision(5)<<"pi="<<pi<<endl;
//因为控制显示小数点后输出4位有效数字，而整数部分是1位有效数字，则共5位有效
//数字，所以setprecision(5)的括号中为5

运行结果：

pi=3.1416

结果正确。

解法二：

const double pi=3.14159;
cout<<setiosflags(ios::fixed)<<setprecision(4)<<"pi="<<pi<<endl;
//设置实数输出精度为4位，当前面加上setiosflags(ios::fixed)时，4为小数位数

运行结果：

pi=3.1416

结果正确。

【例 8-23】有两个式子：y1=3700.0 和 y2=140000.0-100.0，试将 y1 以科学记数法（指数形式）输出，y2 以科学记数法（E 的形式）输出，并且 y1 先以前面带“+”的形式输出，再以前面没有“+”的形式输出，试编程实现。

程序代码如下：

double y1, y2;
y1=3700.0;
y2=140000.0-100.0;
cout<<setiosflags(ios::scientific)<<setiosflags(ios::showpos)<<"y1="<<y1<<endl;
//科学记数法（指数形式）显示，前面带“+”
cout<<resetiosflags(ios::showpos); //终止前面带“+”的形式
cout<<setiosflags(ios::scientific)<<"y1="<<y1<<endl;
cout<<setiosflags(ios::scientific)<<setiosflags(ios::uppercase)<<"y2="<<y2<<endl;
//科学记数法（E的形式）

运行结果：

y1=+3.700000e+003

y1=3.700000e+003

y2=1.399000E+005

结果正确。

【例 8-24】有一个整数 100，分别以十进制、十六进制和八进制将其显示。

int x;
x=100;
cout<<dec<<x<<endl;
cout<<hex<<x<<endl;
cout<<oct<<x<<endl;

运行结果：

100

64

144

结果正确。

3. 如何运用控制输出格式法

首先按输出要求合理地选择控制输出格式法的控制符，然后按以上所述的语法格式正确书写程序，再运行调试，观看显示状态，最后不断加以调整和修改，直到合乎要求为止。可参考例8-1的输出格式。

8.4 结构的亮点

1. 在什么情况下用结构的亮点

当要将两种以上不同数据类型的数据结合在一起，成为新数据类型的数据时，就会用

到结构。

2. 结构具体知识的亮点

1）结构就是将两种以上不同数据类型的数据组合成一种新的数据类型。

2）定义结构变量和定义普通变量的格式相同。声明结构数据类型和定义结构变量的方式有4种，既有声明和定义分开的，也有合二为一的，还有合三为一的（即声明、定义和初始化一起完成），可视需要选用。

3）C++使用结构变量的格式为：

结构变量名. 结构分量名

3. 运用结构的亮点

1）结构变量也必须先定义，然后才能使用，要正确书写和定义结构变量。可以给结构变量赋值，它的值可用于各种操作，如数学运算、赋值、列成表格、输出显示、输出打印等。

2）使用结构指针变量操作时，只需用“->”代替结构变量中使用的点操作符“.”，即操作时用“结构指针变量名->结构分量名”。

3）结构数组的用法是“数组用法+结构用法”，即“结构数组名[下标].结构分量名”。因为结构数组也是一种变量，所以结构数组的用法只是比结构变量的用法多加一个下标，以指明结构数组变量中的某个元素。

4）定义一个指针指向结构数组，该指针称为结构数组指针，其用法同结构指针，只是用结构数组指针变量名代替结构指针变量名而已。

5）结构的特殊运用——链表。什么时候进行这种特殊的运用？在程序运行中对一组数据进行添加、删除、修改等操作时，可以采用链表。

链表是由一组相同数据类型的数据（链圈）链接在一起形成的结构表，数据（链圈）之间是用这种数据类型的指针（链钩）进行链接的。定义链表前，首先要声明链表这种结构数据类型，其格式与声明结构的格式基本相同，只不过多了一个结构分量（链钩指针）。

链表可以是首尾封闭的环链（即链尾指针指向链首），也可以是有头有尾的开口链表。

构成一个链表必不可少的组成部分包括：若干个链圈（结点），其中含有链表结构数据的内容（简称链圈数据）和该链表结构的指针（简称链钩）；两个指针（链首指针和链尾指针）。

在链表的运用中，关键要注意：链钩钩住什么，与什么脱开。

可以对链表进行很多种操作，例如创建链表，添加、删除、修改链表数据等。

把创建链表当做装配自行车链条；把在链表中删除数据当做从自行车链条上拆下链圈；把在链表中插入数据当做往自行车链条上安装链圈；把在链表中修改数据当做在自行车链条上修理链圈等。

6）当对输出格式有具体要求时，可以使用控制输出格式法。