补充：第七章结构与链表.ppt

面向对象程序设计（二）,吕俊白,结构与链表,主要内容： 结构数据类型的定义和数据对象声明 结构成员的访问 结构与指针 链表 重点： 结构类型、结构与指针的关系、用结构实现链表,一、结构,1.什么是结构 结构：由相同或不同数据类型的数据组成的集合体。 结构必须用结构类型来描述，结构类型是用户自定义的数据类型； 结构类型由一组相同或不同类型的数据对象组成，这些数据对象称为结构的成员或结构分量，每一个成员必须有确定的名字和类型。,2. 定义结构类型,结构类型的定义语法如下： struct 结构类型名 数据类型说明符1 成员名1; 数据类型说明符2 成员名2; 数据类型说明符n 成员名n; ; /分号是必需的,注意： struct为关键字，是声明结构类型的专用标识； 结构类型名，命名时要注意 “见名知义”； 成员可以是基本数据类型或非基本数据类型（如：数组、指针、或另一结构类型等）的数据对象，成员声明之间用分号分隔。,例如：学生数据聚合了：学号、姓名、性别、籍贯、出生年月等数据项目，用来描述学生的基本情况，其中出生年月这一项目又由年、月、日三个项目聚合而成。,定义一个描述学生数据的结构类型。 struct BIRTHDAY /描述出生年月 int year; int month; int day; ; struct STUDENT /描述学生的基本信息 int num; char name9; char sex; BIRTHDAY birthday; char NativePlace30; ;,注意：,(1) 若结构中又包含其他结构成员，则称为结构的嵌套。 (2) 结构成员不能是自身的结构变量。 例如： struct List char name20; List m; / 错！不应含有自身的结构变量 ;,3. 结构类型变量的定义,定义结构类型变量的语法如下： 结构类型名 结构变量名表; 注意： 结构类型名必须是已定义的； 例如： STUDENT stud1; 该语句定义了一个STUDENT类型的结构变量stud1；,说明：,(1) 声明一个结构并不分配内存，内存分配发生在定义结构变量时。 (2)结构变量占内存大小可用sizeof操作符求出：sizeof(类型名或变量名) (3)定义结构变量的同时可以直接设置初值。 （方法与初始化数组相似） 例如： STUDENT stud1=096011,“Frank“,M, 1990,6,23,“China“; STUDENT stud1=096011,“Frank“,M,1990,6,23,“China“;,4. 访问结构成员,一旦通过定义相应结构变量，分配了空间之后，就可以访问结构中的成员； 访问结构中的成员通过使用点操作符“.”来实现。 结构成员的引用形式为： 结构变量名 . 成员名 说明：左操作数为结构类型变量，右操作数为结构中的成员。,例如：定义一结构类型用于描述学生数据，后定义一结构变量并对其进行初始化，然后输出该生的信息。struct_visit.cpp,#include using namespace std; struct BIRTHDAY /描述出生年月 int year; int month; int day; ; struct STUDENT /描述学生的基本信息 int num; char name9; char sex; BIRTHDAY birthday; char NativePlace30; ;,例：（续）,int main() STUDENT stud1=096011,“Frank“,M,1990,6,23,“China“; coutstud1.numendl; endl; coutstud1.sexendl; coutstud1.birthday.yearendl; coutstud1.birthday.monthendl; coutstud1.birthday.dayendl; coutstud1.NativePlaceendl; return 1; 注意：引用嵌套结构的成员时，要使用多个点操作符，逐级表示到最低一级成员。,二、 结构与指针,在定义了结构类型之后，可以定义一个结构类型的变量；同样，定义了结构类型之后，也可以定义一个结构类型的指针变量。 例如：假设已定义结构类型Employee ，则 Employee *Empptr; Empptr就是一个结构类型的指针变量，它指向的对象是结构。 定义结构类型的指针变量与定义其它类型的指针变量其方法完全相同。,结构类型指针变量的赋值,指针变量的值是地址，在程序设计中，通常通过取地址操作,通过结构指针变量访问其所指的结构的成员,在C+中，结构指针通过箭头操作符“-”来访问其所指结构的成员。 例如：struct_pointer.cpp #include using namespace std; struct Person char name20; unsigned long id; float salary; ;,void main() Person pr1; Person *prPtr; prPtr= ,注意：,当用点操作符“.”时，它的左边应是一个结构变量； 当用箭头操作符“-”时，它的左边应是一个结构指针变量。 箭头操作符与点操作符是可以互换的： prPtr-name (*prPtr).name,等价,三、链表,1.为什么要引入链表 在实际应用中，我们常遇到类似这样的问题： 例如：商场里的客户购物，来一个客户就要建立一个客户记录（含客户编号、购买金额等信息，可用结构来表示），临下班时，要汇总营业额。 对于这类问题，我们事先并不知道究竟要处理多少个记录，因此，不能用结构数组来组织和存储数据。 为了描述这类数据引入了一种新的数据结构链表。,2.什么叫链表,一个链表由n个结点链接而成(n0)，每个结点是同类型的结构变量（如图8-1所示）。,每个结点包括两个域：存储数据元素信息的数据域和存放另一数据元素存储地址的指针域。 一个链表总是包含一个链首指针，用于指示链表中第一个结点的存储位置。链表通常以链首指针命名，通过它能实现对整个链表的存取。,数据域,指针域,3链表的种类,链表分为单向链表、循环链表和双向链表，下面分别简介： (1) 单向链表 若链表的每个结点只含一个指针域，则称之为单向链表。 单向链表的逻辑结构如图8-1所示。,单向链表中，最后一个结点无后继结点，其指针域值为空（NULL）。,(2) 循环链表 若修改单向链表，使最后一个结点的指针域指向第一个结点，则称为循环链表，其逻辑结构如图8-2所示。,(3) 双向链表 若表中每个结点都有两个指针域，分别指向其前趋结点和后继结点，这样的链表称之为双向链表，见图8-3。,带头结点的单向链表,在单链表的第一个结点前附设一个结点，称为头结点。 头结点的数据域可以不存贮任何信息，也可以存贮（如：表的长度等）附加信息，头结点的指针域存贮指向第一个结点的指针。 在含有头结点的情况下，通常，让链表的链首指针指向头结点，如图8-4。,增加表头结点的优点：增加表头结点后可以不必考虑空链表、表中只有一个结点和当前元素为表的第一结点这三种特殊情况。这样就可大大地减少源程序的复杂性。,4. 链表的描述,链表是由结点链接而成的，每个结点都包含数据域和指针域两部分（图8-5）。,链表结点可用如下结构类型来描述： struct Node ; Node *next; ;,注意：,(1) 结构成员不能是自身的结构变量，但可以用结构指针作为成员。 例如： sturct List char name20; List m; /Error! List *PN; /Right! ,(2)指针域（指针成员）的类型一定和包含该指针的结构同类型。 例如： struct Student long number; float score; Student * next; /指针域 ;,数据域,5.链表的基本操作,链表的基本操作包括：创建链表、遍历链表、删除链表结点、插入链表结点等。 下面以单向链表为例介绍上述各种操作。 (1)创建链表 例如：设学生成绩表包含学号、成绩两个数据项，表中学生人数是可变的，要求创建一链表用于存放该成绩表。,定义一结构类型用于描述链表中的结点： struct Student long number; float score; Student * next; ;,创建链表的方法：,设置一个链首指针Student *head，始终指向链表的第一个结点； 设置一个链尾指针Student *pEnd，指示结点插入位置，即新结点总是追加到链尾； 设置一个当前结点Student *ps，用new操作为其分配内存空间；,插入操作： 若当前插入的结点为链表的第一个结点： head=ps; 且令 PEnd=ps;,否则：pEnd-next=ps;且令PEnd=ps;,程序：,/* create_show_link * #include using namespace std; struct Student long number; float score; Student * next; ; Student * head; /链首指针,Student * Create() /创建链表函数 Student *ps; /当前要插入的结点 Student *pEnd; /链尾指针 ps=new Student; /为当前要插入的结点分配空间 cinps-numberps-score;/给结点赋值 head=NULL; /初始化链表，开始时链表为空 pEnd=ps; while (ps-number!=0) /以输入的学生学号为0作为结束条件 if(head=NULL) /当前插入的结点为链表的第一个结点 head=ps;,else pEnd-next=ps; pEnd=ps; ps=new Student; cinps-numberps-score; pEnd-next=NULL; /完成链表创建后，链尾结点的指针域赋值为NULL delete ps;/释放结点成员number为0的结点所占的堆内存 return (head); void main() head=Create(); ,(2)遍历链表,遍历链表是存取链表中数据的有效手段。 每个链表都有一个链首指针，指向链表的第一个结点，因此，可通过链首指针来遍历链表。 此外，在创建链表时我们令链尾结点的指针域为NULL，所以，在遍历链表的过程中，我们可以当前指针值为NULL，作为遍历的结束条件。,void ShowList(Student * head)/遍历链表 coutnumberscorenext; ,(3)删除链表结点,删除链表中的一个结点：将该结点从链表中分离出来，同时释放该结点所占的存储空间。 具体操作步骤如下： 1) 判断该链表是否为空，若为空给出相应的提示。,2)判断待删除结点（由p指向）是否为链表中的第一个结点，如果是则将p所指结点的指针域值传送给head，即：head指向待删除结点的下一结点。,3)若待删除结点（由p指向）不是链表中的第一个结点，将待删除结点的指针域值传送到其前一结点（由pGuard指向）的指针域中。,4)删除待删结点p（释放p指向的结点所占的存储空间）。,确定待删除结点时应注意： 1)查找之前必须先输入“查找关键字值”； 2)查找过程包含p和pGuard指针的移动以及关键字值与链表当前结点指定数据域值的比较。 问题：是否需要考虑被删除的结点在链尾的情况？,回答：不需要！因为已包含在删除链表的非链首结点的情况中了。,例如：从前面已建立的学生链表中删除学号为number的学生结点。,Student * Delete (Student *head,long number) /删除链表结点 Student *p; /p指向要删除的结点 if(!head) /原链表为空链表 cout“nList is null!n“; return(head); ,if (head-number=number) /要删除的结点为链表的第一个结点 p=head; head=head-next; delete p; coutnumber “the head of list have been deletedn“; return(head); ,for(Student * pGuard=head; pGuard-next; pGuard=pGuard-next) if (pGuard-next-number=number) /找到要删除的结点 p=pGuard-next;/p指向待删除结点 pGuard-next=p-next; delete p; coutnumber“have been deleted n“; return(head); coutnumber“not found!n“; /未找到要删除的结点 return (head); ,(4)插入链表结点,插入操作不能破坏链表中前后结点的链接关系。 插入链表结点的操作可分解为以下两个子操作： 查找结点插入位置 插入结点。 下面分几种情况讨论如何插入链表结点： 假设链表中的结点按某关键字值从