04.第04节课第2章线性表

罗泽兵 · 发表于 2024-4-15 09:13:41

最后呢，我们来看一下链线性表的操作list delete lpe在列表中的实现。比如说我们要删除掉。某个数据元素值为e的，为给定值的这样一个节点。那么，我们的这样一个。删除的方式，那么我们直接呢？就将这个结点之前的。这个节一个节点的。指针域让它指向要被删除结点之后的这样一个结点。那么这样呢，我们这样一个线性，我们这样一个链表呢？

那么，这样一个开始的部分呢？这样。连接的连接的这样一个部分呢，它被删除节点之前的这样一个节点呢，它就不再指向被删除的这样一个节点，那么之后呢，就指向了它。要被删除节点后面的这样一个节点，那么就。我们就不会再列单列表了，就不会再指向再有再指向我们这样一个要被删除的指令，要有。还有指定被删，还有指定元素的这样一个被删除的这样一个节点。

那么，我们来看一下这个内容，删除p指针所指的节点时未完成删除操作指针的链接改动呢？需要先确定p指针原来的前驱节点的位置。为此呢，需要从头遍历列表，以确定前驱节点的指针q，在删除p指针所指的节点之前，应将节点的数据移交给引用参量e。我们来看一下这些语句wide list delete linked list ll load星p。a里面的type e。p指向l为头指针的链接中的某个结点，从链表中呢删除该结点，并由e返回其元素。我们来看一下这个语，

看一下这个部分ifp=l那么如果呢？是删除链表的第一个节点。那么，就修改链表头指针。p箭头next附给l。那么这样呢，我们就把l呢设置为p呢当中的这样一个p指向的这样一个数据元素当中的这样一个指针域的这样一个部分。那么我们就是删除列表中的第一个节点，修改列表头指针，那么如果是另外的情况else q=l。把q呢设置为l设置为头指针的值y有q。箭头next不等于p。那么也就是说，当我们q的下一个。结点呢，

不是p指针所指向的结点之后。那么q指向的下一个节点呢？q指向节点的下一个节点呢，不是我们p指针指向的节点的话，那么我们就将q设置为q。箭头next就将q当中的指针域呢赋给q，让它指向下一个节点，那么这样呢，我们就能够找到。p的弦区间点q。那么接下来。q箭头next=p箭头next，那么这个时候呢？我们是将。p指向的这样一个指针域当中的值赋给q指向的指针域当中的值。

那么这样呢，我们就把要删除结点的前一个结点的指指针域呢？让它指向了。要删除结点的，后面的这样一个，它的下一个结点那么这样呢，我们要删除结点的前一个结点的指针指针域了。我们就指向了要删除节点的，它之后的这样一个指节点，我们就修改了q节点的指针域。那么最后呢，一=p箭头data那么delete delete p？那么这样呢，我们就删除掉了。该结点并由一呢返回了其元素，

那么这是我们在线在链表中删除某个节点的方式。接下来我们看一下。其他形式的链表。比如说静态链表。顺序表的。我们插入和删除了需要移动大量的元素，刚才我们讲过。我们如果呢？要删除。其中一个元素。那么，在这个元素之后的这些。元素呢，都要向前移动。比如说我们删除AI，

那么AI后面的元素呢，一直到an都要向前移动一个位置。那么所以呢，我们静态列表了，我们静态列表，我们顺序表了，删除了需要移动大量的元素。那么，顺序表的插入了也需要移动大量的元素，比如说我们要在AI。之前插入一个元素。那么，这个元素呢？插入到AI之前，那么从AI到an每个元素呢？

都要向后移动一个位置。那么也就是说，我们删除叉二的时候呢，我们的元素呢，都要向后进行移动，那么都要移动一个位置。所以说顺序表呢，它删除和插入需要大量的移动元素。好，我们再来看一下循环链表。那么，循环列表是什么呢？循环列表了最后一个节点的指针域。的指针又指回第一个节点的链表，那么这就是我们的循环链表。

循环链表是另一种形式的链式存储结构，它的特点呢？是表中。最后一个结点的指针域指向头结点，这样呢，整个链表形成一个环，由此从表中任意结点出发。均可找到表中其他节点。循环单列表呢？它的操作呢，和单列表基本一致，那么差别仅在于呢，当链表便利时。判别当前指针p。是否指向表尾节点的终止条件呢？

不同在单链表中呢？判别条件呢？是p。不等于null或者说p。它的这样一个指针，指针指向的指针域当中的指针呢，不等于no，而循环单链表的判断条件呢是？是p不等于头结点，或者说p指向的。指针域当中的指针呢，不等于我们的头指针。那么，我们来看一下这个部分。在循环链表中呢，

头指针呢，也可以改变到指向尾节点这样呢。用一个头指针就能够控制手尾两端，那么可以委委屈操作呢，带来便利。接下来我们看一下双向链表。双向链表types defy struct。do load.element type data struct.导llo de。星号prior。struct download.信号next。download downlink list.那么，

这个定义的。结构体了，而就定义了一个。高漏的这样一个结构体的这样一个结构体类型，以及呢，我们的高link list这样一个。指针的这样一个类型，指向节头节点指针的这样一个类指，指向我们的这样一个结构体指针的指结构体的这样一个指针的类型。我们来看一下双向循环链表。我们的空表呢？我们的双向循环链表呢？那么我们的双向循环链表呢？那么可以进行一个指向的这样一个方式。也就是说。

我们刚才讨论的链式存储结构的节点中呢，只有一个指示，其后接的指针域。由此呢，从某个节点出发，只能顺时顺指针向后查询其他节点。如果要巡查节点的直接前驱，必须从表头指针出发。也就是说，在单链表中呢，查找直接后继节点的时间呢，为o1而查找直接前驱的直接时间呢，为on。那么，我们的双向循环链，

双向循环链表呢？比如说我们的在双向循环列表中呢，有两个指针域，一个呢指向其直接后继。另一个呢，指向其直接前驱。我们双向链表的操作特点呢，是查询和单链表相同，插入和删除时呢，需要同时修改两个方向上的指针。由于前驱指针的设置啊，如果需要前驱的便利位置信息的话，可以直接使用，避免了便利操作时间消耗。好了，

我们来看一下插入的这样一个方方式。好吧，我们插入p。插入s。这样一个e的，这样一个。数据了这样一个e的，这样s指向的这样一个节点。那么，我们插入的话。那么首先呢？这里呢？要让s。箭头next=p到next，那么也就是说我们这里的插入操作呢？

是将s的next值。是让它设置为p。箭头list。也就是说，我们将插入结点前一个。要插入的这样一个。部分的这样一个位置的这样一个节点的这样一个部分节点的，这这个这个位置呢，它前面的这样一个节点呢，它的指针域呢，所指向的下一个节点呢？说它的指针域呢，赋给我们要插入节点的，这样一个指针域，这个那后继。

后继指针的这样一个指针域后继指针。然后呢，将p箭头next。等于s，比如说p。这样一个next呢，它的下一它的这样一个指针域呢，指向我们插入的这个节点。那么，接下来s。箭头next箭头prior，也就是说s。的s指针所指向的这样一个指针域。得了后继指针域。所指向的这样一个节点，

它的这样一个前驱指针呢？将它设置为s，也就是说什么呢？也就是说将我们s。这个节点它的。所指向的。指针域中指向的的指针的指针，比如说s。的指针域中指向的下一个结点，它的前驱指针呢？要指向被插入的这样一个s结点。那么最后呢，将我们的s箭头prior=p，也就是说将我们的。s.

指向节点的前驱指针呢？设置为。它的这样一个前驱节点。指向前驱节点的指，指向它的前驱节点的指针，比如说加s了指向的这样一个。节点，它的前序指针呢？那么设置为p，那么这是我们插入的这样一个部分。那么我们再来看一下删除。删除了。比如说我们要删除这样一个部分。我们将。p箭头next。

设置为p。箭头next箭头next。也就是说，我们要将。p指针。所指向的结点的指针域呢，要让它指向它后继结点。指向的。下一个节点，也就是说什么呢？我们要让p指针。所指向的节点，它的指针域。指向它后继结点的后继结点。那么，

这是这是什么样的含义呢？那么说，比如说我们p呢，指向一个结点，那么我们要让它的指指针域呢？把它设置为它后继结点当中的指针域，让它指向了再下一个结点。那么另外呢，还要将p指向的。后继节点呢，它的前驱指针呢，把它设置为p。那么，这就是我们。删除了这样一个部分，

那么大家呢？要注意这样一个指针呢？它设置了这样一个顺序，它赋值的这样一个顺序，那么首先呢，是将p。指向这样一个。箭头的这样一个next的下一个指针域，这指针域呢？将它设置为它指向的下一个节点的下一个节点。然后呢，再将它指向的这样一个节点呢，它的前驱指针呢，把它设置为p，那么这是这样一个设置的顺序，

那么大家注意这样一个顺序。好同学们，那么我们今天呢？那么就讲过了我们。链表线。线性表的链式表示以及实现。那么这里呢？我们再给大家回顾一下我们讲过的这些内容。比如说我们的单链表。以及呢？嗯。我们单链表的基本操作。比如说我们的插入。删除，查找。

还有计算它的长度。以及。我们的循环链表和双向链表。我们来看一下。线性表链式存储结构的特点呢？是用一组任意的存储单元存储线性表的数据元素。这组存储单元呢，可以是连续的，也可以呢，是不连续的。那么因此呢，为了表示某个每个数据元素AI与其直接后继元素AI+1之间的逻辑关系呢？对数据元素AI来说，除了存储器本身的信息之外，还需存储一个指示器，

直接后继节点的这样一个信息，比如说直接后继的存储位置。这两部分信息呢，组成了数据元素AI的存储映像，称为节点。它包括两个域，其中存储数据元素信息的域呢，称为数据域。存储直接后继存储位置的这样一个预指针呢，我们称之为。指针域。指针域中存储的信息呢？称为指针或者链。n个结点呢，连成一个链表，

那么就是我们线性表的链式存储结构。那么对此呢，每个链表中每个结点只包含一个指针域，因此呢，称为单链表或者链表。我们我们这里要注意。我们要掌握。单面表。它的这样一个。定义。以及它的这样一个存储结构。我们来看一下单链表呢，是由表头指针唯一确定的，因此呢，单链表和。

可以用表头指针呢来命名。如果表头指针名是l，那么我们可以简称该链表呢？为表l。那么我们再来看一下，我们给大家讲一下头节点和头指针，那么这样一个部分。头节点呢，是设置在。表中存储第一个数据元素。之前的复设的一个节点。其指针域呢？指向表中存储的第一个数据元素的这样一个结点头。结点的数据域呢？可以不存储任何信息，

也可存储与数据元素类型相同的其他附加信息。头指针呢，是指向链表中第一个结点的指针，如果链表了设有头结点。则头指针呢？指向所指结点呢？为线性表的头结点，如果链表了，不设头结点。则头指针呢？所指结点呢？为该单链表的首第一个结点。这是我们的单链表的这样一个部分。那么，我们给大家讲一下我们的。

线性表，它的顺序存储以及呢，链式存储的特点。线性表的顺序存储呢，是用一组地址连续的存储单元来存放，我们的数据元素。它的特点呢，是容易查找。便于访问。但是它的缺点呢是。插入。和删除的时候呢，需要移动大量的元素。而我们。线性表的链式存储呢？

它的特点呢？是插入和删除比较方便，比较容易实现，只需要呢，对我们的指针呢？进行这样一个。指向的链接，那么改变呢？就可就可以进行这样一个部分就可以，而它的缺点呢？是查找。那么很很不方便，不能够。进行很容易的访问，这是我们的。

线性表，它的顺序存储和链式存储，它们各自的特点。接下来我们再看一下。单面表它的这样一个基本操作。单链表的基本操作呢？由我们的。求它的长度。以及呢？查找某个。数据元素的位置和插入，以及呢，删除那么大家要了解我们求它的长度的方法。查查找某个数据元素所在位置的方法，以及呢，

插入和删除的方法。那么，对我们的指针呢，进行连接修改的这样一个。方式。那么最后呢？我们给大家讲一下关于我们的。循环链表以及我们的双向链表。循环链表呢，是另一种形式的存储结构，它的特点呢，是表中最后一个结点的指针域呢，指向头结点。每个链表呢，形成一个环，

因此呢，从表中任意节点出发，均可找到表中的其他节点。这是我们的循环列表。那么我们再看一下双向链表。双向链表呢？的节点当中呢，有两个指针域，一个呢是向其直接后继。另一个呢，指向其直接前驱，那么大家要注意，在我们单循双向链表进行插入和删除的时候呢？对我们前驱指针以及呢，后继这样一个指针，

那么这样一个指针域呢，那么修改的。连接的这样一个操作部分，那么大家要注意那么大家了，这样一个操作的这样一个方式。那么，这就是我们今天呢？所讲过的这样一些内容好，大家下来之后呢？那么大家呢？再进行一个了解和熟悉。好，我们今天的课呢，就讲到这里好，谢谢大家。

		自动登录	找回密码
密码			立即注册