《面向对象程序设计》课程教学资源（PPT课件）第15章 链表

链表第15章链表概述15.1链表类15.215.3顺序表

第15章 链表 0  15.1 链表概述  15.2 链表类  15.3 顺序表

15.1链表概述表15-1学生成绩表性别学号姓名分数女86周敏99011001女92苏伊诗99011002男7699011003王苏朋男60苏俊明99011004男95贾林990110051

15.1 链表概述 1 表15-1 学生成绩表 学号 姓名 性别 分数 99011001 周敏 女 86 99011002 苏伊诗 女 92 99011003 王苏朋 男 76 99011004 苏俊明 男 60 99011005 贾林 男 95

15.1链表概述存储方法顺序存储(1)将表格中每一行数据定义成结构体，整个表格定义成存储在内存一块结构体数组表格中的数据是连续的、连续区域中。(2)链表存储，数据可以不连续地存储在内存中

15.1 链表概述 2  存储方法  （1）顺序存储 将表格中每一行数据定义成结构体，整个表格定义成 结构体数组表格中的数据是连续的、存储在内存一块 连续区域中。  （2）链表存储，数据可以不连续地存储在内存中

女86周敏下一行数据首地址9901100192女苏伊诗下一行数据首地址99011002男76下一行数据首地址王苏朋99011003男60苏俊明99011004下一行数据首地址男贾林95空地址99011005图15.1学生成绩表存储结构存储方法：（链式结构)链表，不连续存储3

3 存储方法：(链式结构)链表，不连续存储

链表中每一行数据的存储结构简化形式（结点）：数据指针链表特点：·表格中有多少行数据就存储多少个结点；每个结点存放可以不连续，且无顺序要求；结点的逻辑顺序通过指针连接起来；链表中插入或删除结点只会影响相邻的结点

4 链表中每一行数据的存储结构简化形式（结 点）： 链表特点：  表格中有多少行数据就存储多少个结点；  每个结点存放可以不连续，且无顺序要求；  结点的逻辑顺序通过指针连接起来；  链表中插入或删除结点只会影响相邻的结点。 数据 指针

15.2链表类要定义链表，首先将每个结点定义成一个类：templateclassNODEIpublic://数据域datatype data;//指针域NODE *next;1;注：next为类的成员，指向本类别的对象5

15.2 链表类 5 要定义链表，首先将每个结点定义成一个类： template class NODE { public: datatype data; //数据域 NODE *next; //指针域 }; 注：next为类的成员，指向本类别的对象

注：虚拟的数据类型datatype可以是：整型结构体等浮点数、字符串类例如:struct student声明结点类对象：lNODE jie1;long num;NODE jie2;char name[9];NODEjie3;char sex;注：struct可删float score;1;6

6 注： 虚拟的数据类型datatype可以是：整型、 浮点数、字符串类、结构体等 例如： struct student { long num; char name[9]; char sex; float score; }; 声明结点类对象： NODE jie1; NODE jie2; NODE jie3; 注： struct 可删

将表格定义为如下链表类：templateclass LIST private:NODE*head;//链表头指针public:LIST() (head=NULL;)//构造函数~LIST();//构造函数int length();/求表长boolinsert data(datatype data,inti);//插入元素函数,data为插入值，i为插入位置voidprintlistO;//打印输出链表中的所有元素

7 将表格定义为如下链表类： template class LIST { private: NODE *head; //链表头指针 public: LIST() {head=NULL;} //构造函数 ~LIST(); //构造函数 int length(); //求表长 bool insert_data(datatype data,int i); //插入元素函 数, data为插入值，i为插入位置 void print_list(); //打印输出链表中的所有元素 };

构造/析构函数构造函数public:LISTO(head=NULL;)~LIST()NODE *p;//析构函数while(head)1将链表中所有元素占用空间释放(p=head;head=head->next;delete p;

8 public: LIST(){head=NULL;} //构造函数 ~LIST() { NODE *p; //析构函数 while(head) //将链表中所有元素占用空间释放 { p=head; head=head->next; delete p; } }; 构造/析构函数

一、结点的插入操作head为链表头指针，指向第一个结点，而构造函数将头指针置为空NULL;当声明一个链表类对象时，链表为空表，无结点。headaNULLOan图15-2表格的非顺序存诸结构示意图

9  head为链表头指针，指向第一个结点，而构造函 数将头指针置为空NULL;  当声明一个链表类对象时，链表为空表，无结点。 一、结点的插入操作 head 1 a 2 a an NULL 图15-2 表格的非顺序存储结构示意图