第8章 数据封装—结构体 结构体的概述 结构体类型的定义 结构体类型的变量 结构体数组 结构体作为函数的参数 链表

结构体的概念 打印学生成绩单 ，格式如下： 如何在程序中表示这组学生信息？ 学号 姓名 语文成绩 数学成绩 英语成绩. 00001 张三 96 94 88 00003 李四 89 70 76 00004 王五 90 87 78 如何在程序中表示这组学生信息？

可选方案 用二维的数组来表示 每一列用一个一维数组来表示，这种方法称为并联数组。 该方案不可行，因为这些信息有不同的类型 要保证每位学生信息的正确性很难

为什么要使用记录 当我们考虑怎么逻辑地组织数据时，应该将一个人的所有信息项放在一起，即保持相关性。 学号 姓名 语文成绩 数学成绩 英语成绩. 00001 张三 96 94 88 00003 李四 89 70 76 00004 王五 90 87 78

我 们 希 望 的 结 构 记录 在C++中称为结构体 00001 学 生 张三 一 96 94 88 00003 李四 二 89 70 76 三 00004 王五 90 87 78 记录 在C++中称为结构体 我 们 希 望 的 结 构

结构体类型作用 结构体类型允许程序员把一些分量聚合成一个整体，用一个变量表示。 一个结构体的各个分量都有名字，把这些分量称为成员(member)。 由于结构体的成员可以是各种类型的，程序员能创建适合于问题的数据聚合。

结构体的使用 定义一个新的结构体类型 定义新类型的变量 访问结构体变量

第8章 数据封装—结构体 结构体的概述 结构体类型的定义 结构体类型的变量 结构体数组 结构体作为函数的参数 链表

结构体类型的定义 定义结构体类型中包括哪些分量 格式： struct 结构体类型名{ 字段声明； }； 如： struct studentT { char no[10]; char name[10]; int chinese; int math; int english; };

注意 字段名可与程序中的变量名相同 在不同的结构体中可以有相同的字段名 结构体成员的类型可以是任意类型，当然也可以是结构体类型

struct dateT { int month; int day; int year; }; struct studentT { ... dateT birthday; }; 

第8章 数据封装—结构体 结构体的概述 结构体类型的定义 结构体类型的变量 结构体数组 结构体作为函数的参数 链表

结构体类型的变量 结构体变量的定义 结构体类型的引用 指向结构体的指针 动态分配结构体的空间

结构体变量的定义 结构体变量的定义和普通的变量定义一样。如定义了结构体类型studentT，就可以定义结构体变量： studentT student1; 一旦定义了一个结构体类型的变量，系统在分配内存时就会分配一块连续的空间，依次存放它的每一个分量。这块空间总的名字就是结构体变量的名字。内部还有各自的名字 english math chinese name no student1

结构体变量的初始化 studentT student1= {“00001”，“张三” ，87，90，77}；

定义结构体类型的同时定义变量 struct 结构体类型名{ 字段声明； } 结构体变量； struct { 字段声明； } 结构体变量； 区别：前者可以继续用结构体类型名定义变量

结构体类型的变量 结构体变量的定义 结构体类型的引用 指向结构体的指针 动态分配结构体的空间

结构体变量的访问 对结构体类型变量的引用一般为引用他的成员 成员的表示： 结构变量名.成员名 如: student1.name 如结构中还有结构，则一级一级用”.”分开 ，如 如：student1.birthday.year

结构变量的赋值 结构体是一个统称。每个结构体类型在使用前都要先定义自己有哪些分量。系统事先无法知道如何处理他。 因此，结构体变量的赋值通常是通过对它的每一个成员的赋值而实现。如：输入student1的内容可用： cin >> student1.no >> student1.name >> student1.chinese >> student1.math >> student1.english >> student1.birthday.year >> student1.birthday.month >> student1.birthday.day; 同类型的结构变量之间可以相互赋值，如 Student1 = student2; 将student2的成员对应赋给student1的成员

结构变量的输出 结构体变量的输出通常是通过输出它的每一个成员而实现。如：输出student1的内容可用： cout << student1.no << student1.name << student1.chinese << student1.math << student1.english << student1.birthday.year << student1.birthday.month << student1.birthday.day;

结构体类型的变量 结构体变量的定义 结构体类型的引用 指向结构体的指针 动态分配结构体的空间

指向记录的指针 直接定义指针变量 studentT *sp; 也可以在定义结构体类型的同时定义指向结构体的指针 struct 结构体类型名{ 字段声明； } *结构体指针；

通过指针操作记录 给结构体指针赋值，如： sp = &student1; 结构体指针的引用： 通常程序员习惯使用第二种方法 (*指针).成员 如：(*sp).name student1.成员 指针->成员 如：sp->name  ->是所有运算符中优先级最高的 通常程序员习惯使用第二种方法

结构体类型的变量 结构体变量的定义 结构体类型的引用 指向结构体的指针 动态分配结构体的空间

动态分配结构体的空间 指向结构体指针的另一种用法是存储动态申请到的内存的首地址。用法和申请普通的动态变量一样。如： studentT *sp; sp = new studentT;

第8章 数据封装—结构体 结构体的概述 结构体类型的定义 结构体类型的变量 结构体数组 结构体作为函数的参数 链表

结构体数组 用于描述个体的集合 定义格式： studentT studentArray[SIZE];

结构体数组的引用 引用数组的某一成员的成员 studentArray[3].name 数组成员之间相互赋值 studentArray[4] = studentArray[2] 结构数组的初始化 studentT studentArray[5] = { {“00001”, 张三“, 80, 90,98 }, {…}, {…}, {…}};

统计候选人得票。设有三个候选人，每次输入一个 得票的候选人名字，要求最后输出各人得票结果。 struct personT { int id; int count; } leader[3]= {0, 0, 1, 0, 2, 0};

int main() { int i, j, inputID; for (i=1; i<=10; ++i) {cin >> inputID; if (inputID < 0 || inputID > 2) { cout << “废票”；continue；} leader[inputID].count += 1; } cout << endl; for (i=0; i<3; ++i) cout << leader[i].id << “ “ << leader[i].count); return 0;

指针与结构体数组 与普通的指针一样，指向结构体的指针也能够用来指向一个结构体数组。此时，对指针加1就是加了该结构体的大小。

第8章 数据封装—结构体 结构体的概述 结构体类型的定义 结构体类型的变量 结构体数组 结构体作为函数的参数 链表

结构体作为参数传递 尽管结构体和数组一样也有许多分量组成，但结构体的传递和普通内置类型是一样的。它是将实际参数中的每个分量复制到形式参数的每个分量中。

结构体的传递 Void printPerson(PersonT p)

指向结构体的指针作为参数 因为结构体是值传递，当希望把函数内部对结构体的修改返回给主调函数时，可以用指针传递或引用传递 由于结构体一般占用的内存量都比较大，值传递既浪费空间又浪费时间。因此可用指针传递或引用传递 指针传递形式比较繁琐，所以C++通常用引用传递 引用传递的问题是函数中可以修改实际参数，要控制函数中不能修改实际参数，可以加const限定

指向结构体的指针作为参数 和普通的指针传递一样，函数中可以通过指针访问主调函数的记录 减少函数调用时的数据传递量 Void PrintPerson(personT &p); Void PrintPerson(const personT &p);

结构体传递的实例 设计一函数，打印学生信息

设计一：值传递 Void PrintStudent(studentT s) {cout << s.no << ‘\t’ << s.name << ‘\t’ << s.chinese << ‘\t’ << s.math << ‘\t’ << s.english << endl; } 缺点：浪费时间空间

设计二：指针传递或引用传递 Void PrintStudent(studentT *s) { cout << s->no << ‘\t’ << s->name << ‘\t’ << s->chinese << ‘\t’ << s->math << ‘\t’ << s->english << endl; } Void PrintStudent(studentT &s) { cout << s.no << ‘\t’ << s.name << ‘\t’ << s.chinese << ‘\t’ << s.math << ‘\t’ << s.english << endl; 缺点：不安全

设计三：C++的常规做法 Void PrintStudent(const studentT &s) {cout << s.no << ‘\t’ << s.name << ‘\t’ << s.chinese << ‘\t’ << s.math << ‘\t’ << s.english << endl; } 特点：节约内存，提高函数调用速度，可靠

返回结构体类型的函数 一个函数返回一个结构体。如： personT GetPersonData(void) {personT person; ……. Return(person);} 返回的是一个结构体的复制。 在主调函数中必须有这样的程序段： Main() { personT p1,p2; p1=GetPersonData();}

返回结构体引用的函数 函数返回一个结构体的引用。如： personT &GetPersonData(void) {personT *person = new personT; ……. Return(*person);} 本质上返回的是结构体的地址。 在主调函数中可以有这样的程序段： Main() { personT & p1=GetPersonData(); … } 函数中返回的结构体不能是局部变量

第8章 数据封装—结构体 结构体的概述 结构体类型的定义 结构体类型的变量 结构体数组 结构体作为函数的参数 链表

单链表 链表的概念 链表的存储 链表的操作 循环链表

单链表 只指出后继关系的链表 nil head 头结点

双链表 同时存储前趋和后继 head 循环链表 head

单链表 链表的概念 链表的存储 链表的操作 循环链表

单链表的存储 struct linkRec { datatype data; linkRec *next; } 存储链表就是存储链表中的一个节点的地址，因此需要定义一个节点类型 struct linkRec { datatype data; linkRec *next; }

单链表 链表的概念 链表的存储 链表的操作 循环链表

单链表操作—插入 在结点p后插入一个结点 tmp head p  申请空间 输入数据放入申请到的空间 链入p后

tmp = new LinkRec; // 创建一个新节点 tmp->data = x; // 把x放入新节点的数据成员中 tmp->next = p->next; // 把新节点和p的下一成员相连 p->next = tmp; //把p和新节点连接起来

单链表操作—删除 把结点p后的结点删除  delPtr=p->next; p->next=delPtr->next; head p delPtr  delPtr=p->next; p->next=delPtr->next; delete delPtr;

单链表操作--建立 定义头指针：linkRec *head; 建立头结点 申请空间 设为头结点 head

单链表操作--建立（续） 逐个从键盘输入数据，存入链表 置链表结束标志 接受输入 申请空间 输入数据放入申请到的空间 链入链表尾 a b c head a b c d ^

head = new linkRec; rear = head; Cin >> in_data; while(输入未结束) { p= new linkRec; p->data = in_data; rear->next = p; rear=p; cin >> in_data; } rear->next = NULL;

单链表操作—输出 p = head->next; while ( p != NULL) b c d ^ p = head->next; while ( p != NULL) { cout << p->data; p = p->next; }

创建并访问一个带头结点的、存储整型数据的单链表，数据从键盘输入，0为输入结束标志。 #include <iostream> using namespace std;   struct linkRec { int data; linkRec *next; };

int main() { int x; //存放输入的值 linkRec *head, *p, *rear; head = rear = new linkRec;   while (true) { //创建链表的其他结点 cin >> x; if (x == 0) break; p = new linkRec; p->data = x; rear->next = p; rear = p; } rear->next = NULL; //设置rear为表尾，其后没有结点了 //读链表 cout << "链表的内容为：\n"; p = head->next; while (p != NULL) { cout << p->data << '\t'; p = p->next; } cout << endl; return 0;

单链表 链表的概念 链表的存储 链表的操作 循环链表

循环链表的应用—约瑟夫环 例：n个人围成一圈，从第一个人开始报数1、2、3。凡报到 3者退出圈子。找出最后留在圈子中的人的序号。 解。用循环链表 1 2 4 3 head 当n = 5时，其删除的节点的顺序为2，0，4，1，最后剩下的节点为3。

struct node { int data; node *next; }; int main() { node *head, *p, *q; // head为链表头 int n, i; //输入n cout << "\ninput n:"; cin >> n; //建立链表 head = p = new node; p->data = 0; //p指向表尾 for (i=1; i<n; ++i) { q = new node; //q为当前正在创建的节点 q->data =i; p->next = q; p = q; //将q链入表尾 } p->next = head; // 头尾相连

// 删除过程 q=head; while (q->next != q) //只要表非空 { for (i = 0; i<2; ++i) //报数， { p = q; q = p->next;} p->next = q->next; //绕过节点q cout << q->data << '\t'; //显示被删者的编号 delete q; //回收被删者的空间 q=p->next; //让q指向报1的节点 } // 打印结果 cout << "\n最后剩下： " << q->data << endl; return 0;

链表总结 实现较复杂 插入、删除效率高，但查找第i个元素效率低 无表满的问题 适合于动态表

总结 本章介绍了结构体 作用： 处理更复杂的数据 使用： 定义类型 定义变量 链表