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

链表本章内容第一节链表概述第二节建立链表(扩展)第三节插入链表结点(扩展)第四节删除链表结点(扩展)第一节链表概述链表是一种动态数据结构，可以在程序中动态分配内存，而且不需要连续的内存空间，内存利用率高。由于不需要像数组一样移动其他的元素，在链表中插入或删除元素更方便快速。一、链表的概念链表中的元素称为结点，每个结点包含两部分内容：数据域和指针域。数据域存放结点要存储的数据，指针域存放指向下一个结点的指针，通过这些指针就可以将各个结点连接成为一个链表。链表有一个头指针变量，它的值是链表第一个结点的地址，用来指向链表的第一个结点。链表的最后一个结点称为尾结点，指针域中的值为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-1

structnode { intnum; charname[20]; node*next; }; node*head,*tail,*p; inti;

head=nullptr;//链表头指针变量head tail=nullptr;//链表尾指针变量tail for(i=0;i<3;i++) {

p=newnode;//建立新结点，p指向新结点

cout<<"输入学生信息："<<endl; cout<<"学号：";cin>>p->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)//输出链表的数据

{

cout<<p->num<<','<<p->name<<endl; 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也指向新结点。至此，包含三个结点的链表建立过程结束。二、遍历链表

p=head; while(p!=nullptr) { cout<<p->num<<','<<p->name<<endl; p=p->next; }链表的结点在内存中一般是不连续的，因此不能像数组一样进行随机访问，只能从第一个结点开始依次访问各结点。在链表中插入新的结点时，首先要确定结点插入到链表的位置，然后根据不同的位置进行相应的操作。插入结点的位置一般有以下几种情况：第三节插入结点（1）新结点插入到链表第一个结点前面，成为链表的第一个结点。（2）新结点插入到链表中间某个结点后面。（3）新结点插入到链表末尾，成为链表的尾结点。程序段12-2structnode{ intnum; floatscore; node*next;};node*createlist()//建立链表的函数{ node*head,*tail,*p; inti; head=nullptr; tail=nullptr; cout<<"输入三个学生的信息："<<endl; for(i=0;i<3;i++) { p=newnode; cout<<"学号：";cin>>p->num; cout<<"成绩：";cin>>p->score; p->next=nullptr; if(head==nullptr) head=p; else tail->next=p; tail=p; } returnhead;}程序段12-2node*insert(node*head,intinum,floatiscore)//插入结点的函数{ node*p,*pre,*inode; inode=newnode; inode->num=inum; inode->score=iscore; p=head; pre=head; while(p!=nullptr&&p->score<iscore)//查找插入位置

{ pre=p; p=p->next; } if(head==p)//插入到第一个结点前面

{ inode->next=head; head=inode; } elseif(p!=nullptr&&p->score>iscore)//插入到链表中间

{ pre->next=inode; inode->next=p; }

程序段12-2 elseif(p==nullptr)//插入到链表末尾

{ pre->next=inode; inode->next=nullptr; } returnhead;}intmain(){ node*head,*ph; intinum; floatiscore; head=createlist(); cout<<"输入要添加学生的学号和成绩："; cin>>inum>>iscore; ph=insert(head,inum,iscore); cout<<"所有学生的学号和成绩："<<endl; while(ph!=nullptr)//遍历链表，输出所有数据

{ cout<<ph->num<<','<<ph->score<<endl; ph=ph->next; } return0;}1、在链表头插入新结点if(head==p) { inode->next=head; head=inode; }如果要插入的新结点的成绩值比链表第一个结点的成绩小，那么上面的while语句就不会执行，p还是指向第一个结点，即p与head相等，要执行的是下面的语句：新结点要插入到链表第一个结点之前，因此将head的值赋给指向新结点的inode的next成员，使新结点的next指向链表第一个结点，然后将inode的值赋给head，使head指向新结点。2、在链表中间插入新结点elseif(p!=nullptr&&p->score>iscore) { pre->next=inode; inode->next=p; }如果要插入的新结点在链表中间的某个位置，要执行的是下面的语句：p指向的是要插入新结点的下一个结点，pre指向的是要插入结点的前一个结点。然后执行pre->next=inode;语句，使pre所指向结点的next指向新结点，再执行inode->next=p;语句，使新结点的next指向p所指的结点。3、在链表尾插入新结点elseif(p==nullptr) { pre->next=inode; inode->next=nullptr; }如果p指向的是nullptr，则要插入的新结点在链表末尾，执行的是下面的语句：pre指向的是链表的最后一个结点。然后执行pre->next=inode;语句，使pre所指向结点（即最后一个结点）的next指向新结点，再执行inode->next=nullptr;语句，使新结点的next值为nullptr。删除链表中的结点时，首先要确定删除结点的位置，然后根据不同的位置进行相应的操作。要删除结点的位置一般有以下几种情况：第四节删除结点（1）删除链表第一个结点。（2）删除链表中间某个结点。（3）删除链表的尾结点。程序段12-3structnode{ intnum; floatscore; node*next;};node*createlist(){ node*head,*tail,*p; inti; head=nullptr; tail=nullptr; cout<<"输入四个学生的信息："<<endl; for(i=0;i<4;i++) { p=newnode; cout<<"学号：";cin>>p->num; cout<<"成绩：";cin>>p->score; p->next=nullptr; if(head==nullptr) head=p; else tail->next=p; tail=p; } returnhead;}程序段12-3node*deletenode(node*head,intinum)//删除链表结点的函数{ node*p,*pre; p=head; pre=head; while(p!=nullptr&&p->num!=inum) { pre=p; p=p->next; } if(head==p)//删除链表的第一个结点

head=p->next; elseif(p!=nullptr&&p->num==inum)//删除链表中间的结点

pre->next=p->next; elseif(p==nullptr)//删除链表的最后一个结点

pre->next=nullptr; deletep; returnhead;}程序段12-3intmain(){node*head,*ph; intinum; floatiscore; head=createlist(); cout<<"输入要删除学生的学号："; cin>>inum; ph=deletenode(head,inum); cout<<"所有学生的学号和成绩："<<endl; while(ph!=nullptr) { cout<<ph->num<<','<<ph->score<<