Page 55 - 高中 信息技术 选择性必修1 数据与数据结构

第二章 数据的存储方式  2.3 数据的链式存储与组织

2.3.3 链表的基本操作

对于链表，通常有创建空链表、插入结点、删除结点、取得结点这几种操作。通过对

链表的操作，可以实现以链表为存储结构的数据的各种组织和管理功能。
链表的结点可以动态增加或删除，结点的存储空间也是动态申请和释放的，在C++语
言中，可以使用new关键字动态申请内存，使用delete关键字释放之前动态申请的空间。动
态申请内存的基本形式如下所示：
指针变量=new 类型说明符;

释放之前动态申请的空间的基本形式如下所示：
delete 指针变量;
申请和删除链表结点的代码如下所示：
LinkNode *p; //链表结点指针
p=new LinkNode; //申请一个链表结点空间
delete p; //释放结点所占用的空间

p=NULL; //释放空间后将变量置为空指针
这里需要注意的是，使用delete释放的内存空间必须是使用new关键字申请的内存空
间，否则将可能引起内存访问错误。
单向链表创建空链表、插入结点、删除结点和取结点元素的基本操作可用如表2-10所

示的程序代码实现。 广东教育出版社

表2-10 单向链表的基本操作实现代码

功能 程序段
//初始化空链表，空链表仅包含一个头结点
void CreateEmptyList(LinkList &L)
{
LinkNode * p;
创建一个空链表。
p=new LinkNode; //新建头结点
p->next=NULL; //下一结点为空
L=p; //头指针指向该头结点
}
//在链表中的第i(i>0)个位置插入元素e
//成功返回true，失败返回false
bool ListInsert(LinkList &L,int i,string e)
{
LinkNode * p, * q;
在链表第i（i>0）个位置 int j;
插入新的结点。
//查找第i-1个结点
p=L;
j=0;
while(p&&j<i-1)
{
47 47

21X2204.indd 47 2019/9/26 13:53:08