链表第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 表格的非顺序存储结构示意图