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

罗泽兵 · 发表于 5 天前

好，接下来我们来看一下线性表。它除了顺序结构之外，那么还有一种方式啊，是我们的链式表示和实现。线性表呢？链式存储结构的特点呢？是用一组任意的存储单元。存储线性表的数据元素。这组存储单元呢，可以是连续的，也可以呢，是不连续的。因此呢，为了表示每个数据元素a1与其直接。

后继元素a2这样一个逻辑关系了，那么我们对于数据a1来说，存了存取。本身的信息之外，还需存储一个指示，其直接后接a2。也就是说，即直接后继的存储位置。的这样一个信息。这两部分信息呢，组成了数据元素a1的存储映像，称为节点。所以说我们。数据元素呢？这个节点呢，

它就包含了两个域。其中呢，存储数据元素信息的域呢，我们称之为数据域。也就是说，在这个数据域里面呢，我们存放的呢，是数据元素的信息。而存储直接后继存储位置的域呢？我们称之为指针域。也就是说，我们指针域呢，存放的是它的直接后继的存储位置。指针域中存储的信息呢？称之为指针或者链。

n个结点链成一个链表。那么，称之为我们的线性表的链式存储结构。又由于这样一个链表的每一个节点呢，只包含一个指针域。所以呢，又称为线性链表。或者说单链表。根据链表节点所含指针的个数，指针指向以及呢？指针连接方式。可以将链表呢分为单链表。循环链表。双向链表，二叉链表，

十字链表临接表。连接多重表等。其中，单链表，循环链表和双向链表呢，用于实现线性表的链式存储结构。其他的，比如说其他的这些链表用于实现树或者图等非线性结构。我们呢，先来讨论一下。单链表我们首先来看一下单链表，它的这样一个。内容。以元素。数据元素的这样一个印象。

和指针指示后继元素存储位置。这两者结合了，就形成了一个节点。所以说结点呢，是表示数据元素或数据元素的印象。我们用一组地址任意的存储单元存放线性表中的数据元素，那么这就是我们的单链表。以节点的顺序呢序列表示，线性表称之为链表，那么我们来看一下。它的这样一个构成。比如说。节点a1。后面呢，它的后继呢是？

节点a2。它后面呢，又有它的直接后继。那么最后一个。节点呢？它就没有它的时间后继。我们以线性表中第一个元素的a1的存储地址作为线性表的地址。称作线性表的头指针。那也就是说我们。用一个指针呢指向。数据元素a1的存储地址。我们把这样一个第一个元素a1的存储地址呢，作为线性表的地址。那么，有时候为了操作方便呢，

在第一个节点之前。加一个头结点，以指向头结点的指针呢，作为链表的头指针，比如说。我们下一个头头节点，以指向头节点的指针作为链表的头指针。当线性表为空时头节点的指针域呢？为空。我们接下来看一下节点和单链表的C语言描述。type defy struct l load.element type data.struct l load信号next。这是我们的指针域。l node.

星号link list。这是呢，定义了我们一个结构体的这样一个类型，其中呢l node呢表示我们的这样一个。结构体的这样一个部分。link list呢那么表示了，是我们这样一个指针的，这样一个部分头，这样一个结构体的指针的部分。那么link list ll呢，就是单链表的头指针。那么我们再来看一下单链表的创建操作。create list选要的地址。n如何构造单链表呢？链表是一个动态的结构，

它不需要预先分配空间。因此呢，生成链表的过程呢，是一个节点，一个节点逐个插入的过程。生成单链表有多种方式，那么我们接下来讲一种采取逆序位输入元素值，那么这样一个算法。那么，我们来看一下这样一个逆序位输入n个数据元素的值，建立带头阶段的单链表的这样一个方式。首先，建立一个空表。接下来第二步输入数据元素an。建立节点并插入。

那么接下来呢？输入数据an- 1，那么再建立节点呢？进行插入。那么就插入到了我们的an之前。以此类推，直到输入a1为止，那么就插入到这些节点的这样一个。之前的这样一个开始的这样一个位置，那么用头接点呢？那么指向它的这样一个部分。那么我们看一下这些语句。void create list l link list.lint n.逆序输入n个数据元素，

建立带头结点的单列表。l=ulloa d。l指向next。等于null先建立一个带头结点的单链表，比如说l当中的这样一个。next.它的这样一个指针值呢？为空将先将它呢？赋予空值，建立一个带头节点的单列表，接下来for。I=ni大于零，减减I首先呢I的初值呢是n。I呢，它的这样一个循环表达式的这样一个判断条件呢，

是I大于零。接下来呢I的变化情况呢？I自检减一。p=ul node。scan f.这样一个取这样一个符号p，然后呢，指向data输入。元素的值。接下来p指向next。那么等于l指向next l指向next了等于p。那么也就是说，把l指向的next呢？赋给了p。指向的那个时候把我们头节点。

指向的。从当当中的指针域呢，它的值呢？赋给了p的指针域，然后呢？再把p。这值了。附给这样一个。头节点当中的指针域。那么，这是我们的插入。节点的方式。那么，我们来看一下这个程序void create list l link link list符号lint n，那么我们是逆序呢？

输入n个数据元素，建立带头节点的单列表，首先呢l=6 l load。然后呢l这样一个。next了。等一闹，把它先。让它是我们的这样一个空先让它指针域呢为空。接下来呢I=ni大于零，减减I从I=n开始那么。每次建立一个呢。每次呢，创建一个节点，将它的插入，然后呢I就减一，

那么直到了I=1。那么最后呢，我们就能够输入n个数据元素，建立带头节点的单列表，那么这是我们。创建单链表的方式。接下来我们看一下单链表的基本操作。list认sl求线性表的长度locate element l查找元素。list insert l插入节点list delete l删除节点。我们来看一下线性表的操作list length l。在单链表中的这样一个实现，我们首先呢，求线性表的长度。那么，我们首先呢？

从开始的位置那么进行进行计算，那么比如说第一个，第二个。第三个，第四个。第五个。那么这样呢，第六个那么这样呢，我们这样来计算，我们这样一个数据元素的各节点的个数。单链表呢，是一种顺序存储的结构。以此呢，为存储结构的线性表长度可设置一个计数器。便利边，

便利。链表的节点边进行计数当遍历的指针呢，为空的时候呢？计数器的累计结果呢，就是我们线性表的长度，那么我们来看一下这个结果，看一下这个程序。int link link links.link list l.l为列表的头指针。那么这个函数呢？返回l所指向的列表的长度。p=lk=0，最先呢，让我们的这样一个。

指针p。那么等于我们的l。那么k=0。while p.k加加当p呢，不为空的时候呢k加加那么这个计数器呢？加一这个计数的这样一个部分呢？加一。p=p到next。把p到p当p当中的指针域next呢赋给p。k呢计算非空节点数，当我们的p当中的指针域next为空赋给p的时候呢，我们这个循环呢，那么就结束。运行结束，

我们的循环。最后呢？return k。返回我们k的值就是返回了l所指链表的这样一个长度。那么这样呢，我们就计算出了我们非空节点的个数，也就是说我们单链表的长度。接下来我们再看一下locate element lle。那么，在单列表中的实现。这个呢，我们就。是查找。一个元素。好吧，

我们看一下。从第一个开始，然后到第二个。然后到第三个。到第四个。到第五个到第六个依次呢，在我们的单链表中查找。是否有节点中的这样一个数据元素呢？它的值呢？与我们给与我们这样一个给定的。值相等给给定的这样一个数据的值相等，那么如果找到的话呢？那么就找到这样一个节点的这样一个位置。那么我们看一下这个这样一个结果。与求链表长度的算法类似，

在遍历单链表时边遍历边比较，给定值与节点的数据域值。查找结果呢，有两种可能，找到的时候呢，返回第一个和值域相等的数据结点指针。找不到的话就返回空指针，我们来看一下这个程序。l node星号located element l。link list l element type e.我们是在这样一个函数呢，是要在l所指的单链表中查找第一个值和e相等的数据元素。如果存在的话，就返回它在列表中的位置，那么也就是说，

指向该数据元素所在节点的指针。否则呢，返回now。返回一个空值，首先是p=l。把我们头指针，头指针l的值呢？赋给我们的p。然后呢？while p。并且呢，p指向的data。不等于。e，那么也就是说，

当我们的指针p不为空时，并且p当中的数据域。p当中p指向节点的数据域不等，当中的值了不等于e的时候呢，那么p呢等于p到next就把p当中的这样一个节点当中的数。指针域呢，它的值呢，赋给我们的p让p呢，指向下一个节点。那么，直到了我们的p为空。或者。这样一个。p指向的。数据域。

等于e那么这样呢，我们最后呢就返回p的值就返回了。该数据元素所在节点的指针，那么这就是我们查找。l所指的链表中第一个值和e相等的数据，那么这样一个方式。接下来我们再看一下。线性表的操作插入元素。list insert l.lps在单链表中的实现，比如说。我们要在我们的单面表中插入一个元素，在我们p指向的这样一个指针之前呢？插入一个数据元素。那么，

我们首先呢，肯就是要将。这个要插入的。节点，它的指针域呢？要指向p指向的这样一个节点。它的指针域呢？要是p的这样一个指针的值。并且呢p的前面的这样一个插入前。p的这样一个前面的这样一个节点呢，它的这样一个指针域呢。要是我们指向插入节点的。指针的值那么也是什么意思呢？也就是说。我们首先。

要把。我们这样一个要插入节点当中的指针域的值呢，把它。实现成我们的使用，实现成我们的这样一个p指针的值，然后把。p指向的指节点的前一个节点的这样一个指针域呢，让它指向我们插入节点，那么这样一个。实现我们的插入操作。那么我们看一下，那么这样一个内容在p指针所指的结点之前插入已经生成的结点s。未完成插入操作呢，指针的连接改动呢，需要先确定p指针原来前驱节点的位置信息。

因此呢，需要从头遍历列表，以定位前驱节点的指针q。我们来看一下这个语句void linked list insert l linked list l。宁可l漏的星p。l load性s。将指针。指向。l为头指针的列表中的某个节点。将s呢节点插入到p值节点之前，我们首先呢，ifp=l。那么就是说如果呢？我们是p指针呢？指向的是头结点，

那么就是说。插在我们的头结点之前，那么就是说将我们的s结点呢？插在链表的第一个结点之前，那么直接呢？将我们s到next呢？等于l就是将l呢？赋给。我们的。s.当中的这样一个指针域。然后呢？将s呢？等于l。让ll呢，

等于再加s呢，赋给l那就是说我们最先呢l是我们的头指针，如果我们要插入的这个结点呢？是在我们链表的第一个节点之前。那么这个时候。要需要插在我们链表的第一个节点之前，那么我们将l呢赋给我们的s呢当中的指针域。并且呢，将s呢？那么，指向l。当s呢，赋给l。那么，这是我们将s呢？

插在链表的第一个节点之前。如果我们的s呢？这个结点呢？不是插在链表的第一个结点之前，那么就q=l。把l呢赋给q。while q.当中的这样一个指针域不等于p。那么q=q到next就是当我们q的指针遇了。下一个结点。指向的下一个结点不是p所指向的结点的话的话，那么我们不是p指向的结点的话，那么我们就将q的这样一个指向的next。下一个节点的这样一个指针呢，就赋给我们的q，

那么我们依次下去，那么就能找到。p的前去节点q那么我们的q呢？我们是这里的判断条件呢，是q的。指向的这样一个指针，就下一个节点呢。下值q当中的指针域指向下一个节当中的值呢，不等于p，那么就说q的下一个节点呢？不是P图像的节点，那么我们就把q的指向的下一个节点的这样一个指针呢，赋给q那么我们这样呢，就就能够找到。当q到下一个结点呢，

是p指向的结点的话，那么我们就停止这个循环，那么就循环停止。那么这样呢，我们就能查找到p的前驱节点q。那么找到之后呢？我们q的指向的下一个next，那么等于s把s呢赋给。q指向的next。再把。s.指向的next了。付给p，付给付等于p，付给p=p，

就是把p呢，付给s指向的next。那么这样呢，我们就把s指向的这样一个这样一个指针赋给了。这样一个插入。在某个节点之前，插这样一个插入这样一个位置的这样一个节点的这样这样一个节点的。它之前的这样一个节点呢，它的指它的下一个指针指向的下一个节点的这样一个它的指针域呢，把它设置为s。然后呢，再把s。指向的下一个节点呢。这样一个指示域呢，设置为p。

这样呢，我们就能够在链表q的节点后呢？插入我们的s节点。那么，这就是我们插入节点的这样一个方式。在某个在某个节点之前呢？插入节点的方式。那么我们看一下这个部分。q指向next=ss箭头next=p，那么这里呢是？是把。q指向q箭头呢，就是我们插入节插入的某在某个节点前插入的这样一个。在这样一个在在这样一个节点前插入的，在这样一个插入的这样一个。

那么就是在这样一个插入的这样一个。要插入的，这在这之前的这样一个插入的这样一个节点。那么，这样一个位置呢？它之前的这样一个节点呢？它的指针域呢？把它设置为s那么s箭头next呢？我们要插入节点的这样一个指针域呢？把它设置为q。那么这样呢，我们就能够在链表的q中节点之后插入我们的s节点。

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