计算机程序设计基础课件：链表.pptx

链表

本章内容第一节链表概述第二节建立链表(扩展)第三节插入链表结点(扩展)第四节删除链表结点(扩展)

第一节链表概述链表是一种动态数据结构，可以在程序中动态分配内存，而且不需要连续的内存空间，内存利用率高。由于不需要像数组一样移动其他的元素，在链表中插入或删除元素更方便快速。

一、链表的概念链表中的元素称为结点，每个结点包含两部分内容：数据域和指针域。数据域存放结点要存储的数据，指针域存放指向下一个结点的指针，通过这些指针就可以将各个结点连接成为一个链表。链表有一个头指针变量，它的值是链表第一个结点的地址，用来指向链表的第一个结点。链表的最后一个结点称为尾结点，指针域中的值为nullptr。

链表的结点可以定义为以下的结构体类型：structnode{数据类型1成员名1;//数据域数据类型2成员名2;……node*next;//指针域};node是结构体类型名称，用来表示结点，成员next是结构体指针变量，指向node类型的结构体变量，也就是指向下一个结点。

二、链表常用运算符1、new运算符new运算符的格式为：new数据类型根据new后面数据类型的字节数来申请分配内存空间，然后返回该类型的指针。int*p=newint;申请分配存放整型数据的内存空间，分配成功后返回该内存空间的地址，即指针，并将指针赋值给变量p。

2、delete运算符delete运算符的格式为：delete指针变量释放使用new运算符分配的内存空间。deletep;释放指针变量p所指向的内存空间，p的值是前面使用new运算符分配的内存空间地址。delete运算符一般与new运算符配对使用。

一、建立链表第二节建立链表建立链表就是依次增加链表结点的过程，逐个为结点申请内存，存放结点数据，然后建立结点之间的链接关系。

程序段12-1structnode { intnum; charname[20]; node*next; }; node*head,*tail,*p; inti; head=nullptr;//链表头指针变量head tail=nullptr;//链表尾指针变量tail for(i=0;i3;i++) { p=newnode;//建立新结点，p指向新结点 cout输入学生信息：endl; cout学号：;cinp-num; cin.get(); cout姓名：;cin.get(p-name,20); p-next=nullptr; if(head==nullptr)//若链表为空，将头指针指向新结点 head=p; else//若链表不为空，将新结点链接到链表尾部 tail-next=p; tail=p;//将尾指针指向新结点 }

程序段12-1 p=head; cout三个学生信息：endl; while(p!=nullptr)//输出链表的数据 { coutp-num,p-nameendl; p=p-next; }

然后判断链表是否为空，即新结点是否为第一个结点，如果是第一个结点，执行head=p;和tail=p;语句，将head和tail都指向新结点。接着将输入的数据存放到新结点的相应成员中，再用p-next=nullptr;语句把新结点的next成员赋值为nullptr。建立第一个结点时，首先用new为结点申请内存空间，将分配到的内存空间地址赋值给结构体指针变量p，使p指向新结点。

接着输入数据到新结点的相应成员中,把新结点的next成员赋值为nullptr。建立第二个结点时，同样先为结点申请内存空间，将p指向新结点。然后判断链表是否为空，此时链表已经有结点不为空，所以执行tail-next=p;和tail=p;语句，tail的next成员即为第一个结点的next成员，tail-next=p;使第一个结点的next成员指向新结点，tail=p;使tail也指向新结点。

建立第三个结点的步骤与建立第二个结点的步骤相同，依然是p指向新结点，前一个结点的next成员指向新结点，tail也指向