数据结构Python语言描述 线性表

数据结构

Python语言描述第2章线性表2目录2.1线性表简介2.2顺序表2.3链表2.4本章小结2.5上机实验32.1线性表简介4线性表是由若干个具有相同特性的数据元素组成的有限序列。若该线性表中不包含任何元素，则称为空表，此时其长度为零。当线性表不为空时，表中元素的个数即为其长度。2.1线性表简介5可以用以下形式来表示线性表。{a[1],a[2],…,a[i],…,a[n]}其中a[i]表示线性表中的任意一个元素，n表示元素的个数。表中a[1]为第一个元素，a[2]为第二个元素，依次类推，a[n]为表中的最后一个元素。由于元素a[1]领先于a[2]，因此我们称a[1]是a[2]的直接先驱元素，a[2]是a[1]的直接后继元素。我们把线性表中的第一个元素a[1]称为表头，最后一个元素a[n]称为表尾，在线性表中，有且仅有一个表头元素和一个表尾元素。通常表头元素没有直接先驱元素，表尾元素没有直接后继元素。2.1线性表简介6一种典型的线性表的逻辑结构。2.1线性表简介7线性表中的元素之间也可以存在某种关系。如数字1～20里所有奇数的排列，可用如下线性表的形式来表示。{1,3,5,7,9,11,13,15,17,19}此时，表内元素的值是按照递增顺序来排列的，通常我们称这种类型的线性表为有序线性表（简称有序表），即该表中元素按某种顺序进行排列。从严格意义上来讲，仅当线性表中所有元素以递增或递减的顺序排列（允许表中存在相同的元素），我们才称其为有序表；否则，我们均称其为无序表，元素之间既无递增也无递减关系，示例如下。{1,13,5,74,9,11,13,15,17,195}2.1线性表简介8线性表有以下特性。（1）线性表中的元素个数一定是有限的。（2）线性表中的所有元素具有相同的性质。（3）线性表中除表头元素以外，其他所有元素都有唯一的（直接）先驱元素。（4）线性表中除表尾元素以外，其他所有元素都有唯一的（直接）后继元素。线性表的抽象数据类型的定义参见教材p20表2-1。2.2顺序表2.2.1顺序表的概念2.2.2顺序表的操作2.2.3顺序表的应用92.2.1顺序表的概念10顺序表是指采用顺序存储的方式来存储数据元素的线性表。在顺序表中，我们通常将结点依次存放在一组地址连续的存储空间中，由于待存储空间连续且每个数据元素占用的空间相同，因此可以综合上述信息并通过计算得出每个元素的存储位置。2.2.2顺序表的操作11创建文件ex020202.py。在该文件中我们定义了一个用于顺序表基本操作的SequenceList类。序号名称注释1__init__(self)初始化线性表（构造函数）2CreateSequenceList(self)创建顺序表3DestorySequenceList(self)销毁顺序表4IsEmpty(self)判断顺序表是否为空5GetElement(self)获取表中指定位置的元素值6FindElement(self)在表中查找某一指定元素7GetExtremum(self)获取表中最大值或最小值8InsertElement(self)在表中指定位置插入某一元素9AppendElement(self)在表末尾插入某一元素10SortSequenceList(self)对表进行排序11DeleteElement(self)删除表中某一元素12VisitElement(self)访问表中某一元素13TraverseElement(self)遍历表中所有元素12顺序表基本操作122.2.2顺序表的操作13我们将具体实现__init__(self)CreateSequenceList(self)FindElement(self)InsertElement(self)DeleteElement(self)TraverseElement(self)这6个方法。读者可根据自己的需要，自行实现其余方法。2.2.2顺序表的操作14我们首先调用SequenceList类的构造函数__init__(self)初始化一个空的顺序表，其算法思路如下。（1）创建一个顺序表。（2）对该顺序表进行初始化。该算法思路对应的算法步骤如下。（1）创建一个顺序表self.SeqList。（2）将顺序表self.SeqList置空。14151#####################################2#初始化顺序表函数3#####################################4def__init__(self):5self.SeqList=[]算法2-1初始化顺序表函数2.2.2顺序表的操作16CreateSequenceList(self)的算法思路如下。（1）输入数据元素并存入顺序表中。（2）结束数据元素的输入。（3）成功创建顺序表。该算法思路对应的算法步骤如下。（1）调用input()方法接收用户的输入。（2）若用户的输入不为“#”，则调用append()方法将其添加至线性表中并转（3）。（3）重复步骤（1）。（4）若用户的输入为“#”，则结束当前输入并完成线性表的创建。16171#####################################2#创建顺序表函数3#####################################4defCreateSequenceList(self):5print("*************************************************")6print("*请输入数据后按回车键确认，若想结束请输入“#”。*")7print("*************************************************")8Element=input("请输入元素：")9whileElement!='#':10self.SeqList.append(int(Element))11Element=input("请输入元素：")算法2-2创建顺序表函数2.2.2顺序表的操作18通过执行上述代码，我们创建了一个新的顺序表SeqList，表内数据元素为{‘1001’,‘365’,‘30’,‘11’,‘23’,‘24’,‘3’,‘9’,‘35’}在之后的基本操作中，我们都会基于该顺序表进行。182.2.2顺序表的操作19FindElement(self,SeqList)的算法思路如下。（1）输入待查找的元素值。（2）若需查找的元素值存在于顺序表中，则输出其值及所在位置。（3）若需查找的元素不在顺序表中，则输出相应提示。该算法思路对应的算法步骤如下。（1）调用input()方法接收用户输入的待查找的元素值key，并将其转化为int型。（2）判断用户输入的元素值key是否存在于顺序表SeqList中，若结果为真则转（3），否则转（4）。（3）输出该元素值及其所在位置。（4）输出查找失败的提示。19201#####################################2#查找元素值函数3#####################################4defFindElement(self):5key=int(input('请输入想要查找的元素值：'))6ifkeyinself.SeqList:7ipos=self.SeqList.index(key)8print("查找成功！值为",self.SeqList[ipos],"的元素，位于当前顺序表的第",ipos+1,"个位置。")9else:10print("查找失败！当前顺序表中不存在值为",key,"的元素")算法2-3查找元素值函数2.2.2顺序表的操作21InsertElement(self,SeqList)的算法思路如下。（1）输入待插入元素的目标位置。（2）输入待插入的元素值。（3）输出成功插入元素后的顺序表。该算法思路对应的算法步骤如下。（1）调用input()方法接收用户需要插入元素的目标位置iPos。（2）调用input()方法接收用户需要插入元素的值Element。（3）调用insert()方法将值为Element的元素插入指定位置iPos处。（4）调用print()方法将插入元素Element后的顺序表输出。21221#####################################2#指定位置插入元素函数3#####################################4defInsertElement(self):5iPos=int(input('请输入待插入元素的位置：'))6Element=int(input('请输入待插入的元素值：'))7self.SeqList.insert(iPos,Element)8print("插入元素后，当前顺序表为：\n",self.SeqList)算法2-4指定位置插入元素函数23假定我们在之前创建的顺序表SeqList中，将元素‘66’插入至表中第4个位置（其下标位置为3），通过执行上述代码，原本含有9个元素的顺序表SeqList{‘1001’,‘365’,‘30’,‘11’,‘23’,‘24’,‘3’,‘9’,‘35’}变为含有10个元素的顺序表SeqList{‘1001’,‘365’,‘30’,‘66’,‘11’,‘23’,‘24’,‘3’,‘9’,‘35’}2.2.2顺序表的操作24252.2.2顺序表的操作26DeleteElement(self,SeqList)的算法思路如下。（1）输入待删除元素的下标位置。（2）删除指定元素。（3）输出删除元素后的顺序表。该算法思路对应的算法步骤如下。（1）调用input()方法接收用户需要删除元素的目标位置dPos。（2）调用remove()方法将下标位置为dPos的元素删除。（3）调用print()方法输出删除元素后的顺序表。26271#####################################2#指定位置删除元素函数3#####################################4defDeleteElement(self):5dPos=int(input('请输入待删除元素的位置：'))6print("正在删除元素",self.SeqList[dPos],"...")7self.SeqList.remove(self.SeqList[dPos])8print("删除后顺序表为：\n",self.SeqList)算法2-5指定位置删除元素函数28假定我们在之前创建的顺序表SeqList中删除下标位置为3的元素‘66’，在执行删除操作后，原顺序表SeqList中元素‘11’及其之后的5个元素均向前移动了一个位置。29我们还可以通过将元素‘30’及其之前的两个元素向后移动一个位置，实现删除元素‘66’这一操作。2.2.2顺序表的操作30TraverseElement(self)的算法思路如下。（1）得到顺序表的长度。（2）逐一输出该顺序表中的元素值。该算法思路对应的算法步骤如下。（1）调用len()函数得到当前顺序表SeqList的长度SeqListLen。（2）使用变量i来指示当前元素的下标位置。（3）从变量i=0开始到i=SeqListLen-1为止，执行（4）。（4）调用print()方法输出下标位置为i的元素值。（5）结束输出。30311#####################################2#遍历顺序表元素函数3#####################################4defTraverseElement(self):5SeqListLen=len(self.SeqList)6print("******遍历顺序表中元素******")7foriinrange(0,SeqListLen):8print("第",i+1,"个元素的值为",self.SeqList[i])算法2-6遍历顺序表元素函数32【例2-1】表2-3为软件学院15级软件工程1班部分学生2017—2018年度英语期末考试成绩，该表包括序号、姓名和分数3个字段。请结合顺序表的操作将分数存入顺序表中，并求出最高分与最低分。2.2.3顺序表的应用序号姓名分数1赵小一562钱小二293孙小三694李小四955周小五926吴小六627郑小七708王小八509冯小九8010陈小十7733分析：本例实质就是获取表中成绩的最大值与最小值。根据题目要求，需结合顺序表的操作来求解，因此我们必须先创建一个顺序表，然后将上述成绩逐一输入至顺序表中，最后求出该顺序表的最大值与最小值并将两者的值输出。基于上述分析，我们可将算法思路归纳如下。（1）创建一个顺序表，将表2-3中学生的分数依次输入至顺序表中。2.2.3顺序表的应用34（2）通过对顺序表执行相关操作，求出最大值和最小值。（3）输出最大值和最小值，即为最高分和最低分。该算法思路对应的算法步骤如下。（1）调用SequenceList类的成员函数CreateSequenceList(self)将表2-3中的分数依次输入至顺序表L中（具体代码实现可参考算法2-1与算法2-2）。（2）调用SequenceList类的成员函数GetExtremum(self)获取顺序表中的最大值和最小值。（3）输出最大值和最小值。2.2.3顺序表的应用351#####################################2#算法2-7求顺序表最值函数3#####################################4defGetExtremum(self):5whileTrue:6print("*********************")7print("*1:查询最大值")8print("*2:查询最小值")9print("*3:查询最大值和最小值")10print("*0:退出程序")11print("*********************")12i=int(input("请输入:"))13ifi==1:14print("顺序表中最大值为：",max(self.SeqList))15elifi==2:16print("顺序表中最小值为：",min(self.SeqList))17elifi==3:18print("顺序表中最大值为：",max(self.SeqList))19print("顺序表中最小值为：",min(self.SeqList))20elifi==0:21break36算法2-8创建顺序表并计算最值1L=SequenceList()2L.CreateSequenceList()3L.GetExtremum()此时，我们可以看到软件学院15级软件工程1班部分学生2017—2018年度英语期末考试成绩中，最高分为95分，最低分为29分。2.3链表2.3.1链表的基本概念2.3.2单链表2.3.3循环单链表2.3.4双链表2.3.5循环双链表2.3.6链表的应用37382.3.1链表的基本概念链表是指采用链式结构来存储数据元素的线性表，它与顺序表最大的区别在于两者的存储结构不同。顺序表需要由系统提前分配一组连续的存储空间，并采用顺序存储的方式来存储数据元素；而链表是在每个结点创建时主动向系统申请相应的存储空间，并通过指针来链接各个包含数据元素的结点。即链表中元素的逻辑顺序是由指针的链接次序决定的，与存储空间的物理位置无关，因此在使用时仅能被顺序存取；而顺序表中元素的逻辑顺序与其物理位置直接相关，因此可实现随机存取。除此之外，与顺序表相比，链表还有以下特点。（1）链表实现了存储空间的动态管理。（2）链表在执行插入与删除操作时，不必移动其余元素，只需修改指针即可。392.3.1链表的基本概念我们使用存储密度这一指标来衡量数据存储时其对应存储空间的使用效率。它是指结点中数据元素本身所占的存储量和整个结点所占用的存储量之比，即:存储密度=结点中数据元素所占的存储量/结点所占的存储量因此我们可以知道顺序表的存储密度为1，而链表的存储密度小于1。所以在理想情况下，顺序表的存储密度会大于链表，其相应的存储空间利用率也就更高。402.3.1链表的基本概念链表是由一系列结点通过指针链接而形成的，每个结点可分为数据域和指针域两个部分，数据域可用于存储数据元素，指针域可用于存储下一结点的地址。每个数据元素a[i]与其直接后继元素a[i+1]的逻辑顺序是通过使用结点的指针来指明的，其中，数据元素a[i]所在的结点为数据元素a[i+1]所在的结点的直接先驱结点，反之，数据元素a[i+1]所在的结点为数据元素a[i]所在的结点的直接后继结点。412.3.1链表的基本概念假定一个线性表A为{‘Ren’,‘Zhi’,‘Chu’,‘Xing’,‘Ben’,‘Shan’}当我们将此线性表中的元素用链式结构来存储时，其对应链式存储结构如图所示。42我们该如何通过指针，对上述元素按表中顺序进行存储呢？首先假定一个头指针H，它被用来指向链表中第一个结点，接着在第一个结点的指针域中存入第二个结点所在的存储地址，依次类推，直至最后一个元素。由于最后一个元素没有直接后继，因此其指针域中的值为None。2.3.1链表的基本概念43链表可分为单向链表、双向链表及循环链表。（1）在单向链表中，每个结点只包含一个指针域，它用来指向其直接后继结点，通常我们将这种单向链表简称为单链表。2.3.1链表的基本概念44（2）在双向链表中，每个结点包含两个指针域，其中一个用于指向先驱结点，可称之为先驱指针；另一个用于指向后继结点，可称之为后继指针。通常我们将这样的双向链表简称为双链表。2.3.1链表的基本概念45（3）循环链表的特点之一就是从表中任一结点出发，均可找到表中其他结点。接下来我们介绍两种最为常用的循环链表——循环单链表和循环双链表。2.3.1链表的基本概念46通过上一节的学习我们知道，单链表可由头指针唯一确定。它用于指向表中第一个结点，若其为空，则表示该单链表的长度为0；否则我们需通过循环的方式来访问结点的指针域，从而计算出单链表的长度。通过使用头指针，我们还可对单链表执行其他操作。有时我们会在单链表的第一个结点前增加一个结点，其数据域默认为空，也可用于存储单链表长度之类的数据；而指针域则被用于存储第一个结点的地址。我们把这种类型的结点称为头结点，并把含有这种头结点的单链表称为带头结点的单链表；反之则称为不带头结点的单链表。和不带头结点的单链表相比，带头结点的单链表不仅统一了第一个结点及其后继结点的处理过程，还统一了空表和非空表的处理过程。因此在后续内容的介绍中，若无特别声明，我们所说的单链表均指带头结点的单链表。2.3.2单链表47我们可按如下步骤来实现带头结点的单链表的基本操作。第1步，创建文件ex020302.py。在该文件中我们首先定义一个Node类，该类包含创建结点并对结点进行初始化的操作。第2步，定义一个SingleLinkedList类，用于创建一个单链表，并对其执行相关操作(参见教材p38)。我们将具体实现Node类中的__init__()方法，以及SingleLinkedList类中的__init__(self)、CreateSingleLinkedList(self)、InsertElementInTail(self)、InsertElementInHead(self)、FindElement(self)、DeleteElement(self)和TraverseElement(self)这几个方法。其余方法读者可根据自己的需要来实现。2.3.2单链表48调用Node类的成员函数__init__(self,data)初始化一个结点，其算法思路如下。（1）创建一个数据域，用于存储每个结点的值。（2）创建一个指针域，用于存储下一个结点的地址。（3）还可以根据实际需要创建其他域，用于存储结点的各种信息。该算法思路对应的算法步骤如下。（1）创建数据域并将其初始化为data。（2）创建指针域并将其初始化为空。2.3.2单链表491#####################################2#初始化结点函数3#####################################4def__init__(self,data):5self.data=data6self.next=None算法2-9初始化结点函数50SingleLinkedList类的成员函数__init__(self)用于初始化头结点，其算法思路如下。（1）创建单链表的头结点。（2）将其初始化为空。该算法思路对应的算法步骤如下。（1）创建一个结点并将其初始化为空。（2）令单链表的头结点为上述结点。2.3.2单链表511#####################################2#初始化头结点函数3#####################################4def__init__(self):5self.head=Node(None)算法2-10初始化头结点函数52SingleLinkedList类的成员函数CreateSingleLinkedList(self)用于创建一个单链表，其算法思路如下。（1）获取头结点。（2）由用户输入每个结点的值，并依次创建这些结点。（3）每创建一个结点，就将其链入单链表的尾部。（4）若用户输入“#”号，转（5）；否则转（2）。（5）完成单链表的创建。2.3.2单链表53该算法思路对应的算法步骤如下。（1）使用变量cNode指向头结点。（2）调用input()方法接收用户的输入。（3）判断用户的输入是否为“#”，若结果为真，则转（7）；否则转（4）。（4）将用户输入的值作为参数去创建并初始化一个新结点。（5）在cNode的next域中存入新结点的地址。（6）将cNode指向cNode的后继结点，并转（2）。（7）结束当前输入，完成单链表的创建。2.3.2单链表541#####################################2#创建单链表函数3#####################################4defCreateSingleLinkedList(self):5print("*************************************************")6print("*请输入数据后按回车键确认，若想结束请输入“#”。*")7print("*************************************************")8cNode=self.head9Element=input("请输入当前结点的值：")10whileElement!="#":11nNode=Node(int(Element))12cNode.next=nNode13cNode=cNode.next14Element=input("请输入当前结点的值：")算法2-11创建单链表函数55通过执行上述代码，我们可以创建一个新的单链表。2.3.2单链表56SingleLinkedList类的成员函数InsertElementInTail(self)，向已有单链表的尾端插入结点，其算法思路如下。（1）输入待插入结点的值。（2）创建数据域为该值的结点。（3）在当前单链表的尾端插入该结点。2.3.2单链表57该算法思路对应的算法步骤如下。（1）调用input()方法接收用户输入，并将其存入变量Element中。（2）判断Element是否为“#”，若结果为真，则转（8）；否则转（3）。（3）使用变量cNode指向单链表的头结点。（4）将Element转化为整型数，然后将其作为参数去创建并初始化一个新结点。（5）判断cNode的next是否为空，若为空则转（7），否则转（6）。（6）将cNode指向其后继结点，转（5）。（7）将nNode的地址存入cNode的指针域中，完成该结点在单链表尾端的插入。（8）结束本程序。2.3.2单链表581#####################################2#尾端插入元素函数3#####################################4defInsertElementInTail(self):5Element=(input("请输入待插入结点的值："))6ifElement=="#":7return8cNode=self.head9nNode=Node(int(Element))10whilecNode.next!=None:11cNode=cNode.next12cNode.next=nNode算法2-12尾端插入元素函数59假定我们在之前创建的单链表SLList中，将值为18的结点插入至表中最后一个位置，通过执行上述代码，原本含有5个结点的单链表SLList，变为含有6个结点的单链表SLList。2.3.2单链表一般情况下，我们将这种直接在链表尾端插入结点的方法称为尾插法。60SingleLinkedList类的成员函数InsertElementInHead(self)，向已有单链表的首端插入结点，其算法思路如下。（1）输入待插入结点的值。（2）创建数据域为该值的结点。（3）在当前单链表的首端插入该结点。2.3.2单链表61该算法思路对应的算法步骤如下。（1）调用input()方法接收用户输入，并将其存入变量Element中。（2）判断Element是否为“#”，若结果为真，则转（7）；否则转（3）。（3）使用变量cNode指向当前单链表的头结点。（4）将Element转化为整型数，然后将其作为参数去创建并初始化一个新结点。（5）将新结点的next指向cNode的后继结点，转（6）。（6）将nNode的地址存入结点cNode的指针域中，完成该结点在单链表首端的插入。（7）结束本程序。2.3.2单链表621#####################################2#首端插入元素函数3#####################################4defInsertElementInHead(self):5Element=input("请输入待插入结点的值：")6ifElement=="#":7return8cNode=self.head9nNode=Node(int(Element))10nNode.next=cNode.next11cNode.next=nNode算法2-13首端插入元素函数63假定我们在之前创建的单链表SLList中，将值为88的结点插入至表中第一个位置，通过执行上述代码，原本含有6个结点的单链表SLList，变为含有7个结点的单链表SLList。2.3.2单链表一般情况下，我们将这样直接在链表首端插入结点的方法称为头插法。64SingleLinkedList类的成员函数FindElement(self)(self)，在单链表中查找含有某一指定元素的结点，其算法思路如下。（1）输入待查找的元素值。（2）若在单链表中存在包含目标元素的结点，则输出第一个被找到的结点的值及其所在位置。（3）若在单链表中不存在包含目标元素的结点，则输出相应提示。2.3.2单链表65该算法思路对应的算法步骤如下。（1）使用变量Pos指示当前下标位置。（2）使用变量cNode指向单链表SLList的头结点。（3）调用input()方法接收用户的输入，存入变量key中，并将其转化为整型数。（4）判断当前链表是否为空，若为空则转（5），否则转（6）。（5）调用print()方法输出当前单链表为空的提示并返回。（6）当cNode的next不为空且cNode所指结点的值不等于key时，执行（7），否则执行（8）。（7）将cNode指向当前结点的后继结点并将Pos加1，转（6）。（8）判断当前cNode所指结点的值是否等于key，若为真，则转（9）；否则转（10）。（9）调用print()方法输出值key及其所在位置。（10）调用print()方法输出查找失败的提示。2.3.2单链表661#####################################2#查找指定元素并返回其位置函数3#####################################4defFindElement(self):5Pos=06cNode=self.head7key=int(input('请输入想要查找的元素值：'))8ifself.IsEmpty():9print("当前单链表为空！")10return11whilecNode.next!=NoneandcNode.data!=key:12cNode=cNode.next13Pos=Pos+114ifcNode.data==key:15print("查找成功，值为",key,"的结点位于该单链表的第",Pos,"个位置。")16else:17print("查找失败！当前单链表中不存在值为",key,"的元素")算法2-14查找指定元素并返回其位置函数671#####################################2#判断单链表是否为空函数3#####################################4defIsEmpty(self):5ifself.GetLength()==0:6returnTrue7else:8returnFalse算法2-15判断单链表是否为空函数681#####################################2#获取单链表长度函数3#####################################4defGetLength(self):5cNode=self.head6length=07whilecNode.next!=None:8length=length+19cNode=cNode.next10returnlength算法2-16获取单链表长度函数69SingleLinkedList类的成员函数DeleteElement(self)，可将已有单链表中包含指定元素的结点删除，其算法思路如下。（1）输入待删除结点的值。（2）在单链表中，查找与该值相等的结点。（3）若查找成功，则执行删除操作。（4）若查找失败，则输出相应提示。2.3.2单链表70该算法思路对应的算法步骤如下。（1）调用input()方法接收用户待删除结点的值dElement。（2）使用变量cNode、pNode指向单链表SLList的头结点。（3）判断当前链表是否为空，若为空则转（4），否则转（5）。（4）调用print()方法输出当前单链表为空的提示并返回。（5）当cNode所指结点的指针域不为空且cNode所指结点的值不等于dElement时，执行（6），否则执行（7）。（6）令pNode等于cNode，再将cNode指向其后继结点并转（5）。（7）判断cNode所指结点的值是否等于dElement，若为真，则转（8）；否则转（9）。（8）将pNode的next指向cNode所指结点的后继结点，然后删除cNode所指结点，再调用print()方法输出相应提示。（9）调用print()方法输出删除失败的提示。2.3.2单链表711#####################################2#删除元素函数3#####################################4defDeleteElement(self):5dElement=int(input('请输入待删除结点的值：'))6cNode=self.head7pNode=self.head8ifself.IsEmpty():9print("当前单链表为空！")10return11whilecNode.next!=NoneandcNode.data!=dElement:12pNode=cNode13cNode=cNode.next14ifcNode.data==dElement:15pNode.next=cNode.next16delcNode17print("成功删除含有元素",dElement,"的结点")18else:19print("删除失败！当前单链表中不存在含有元素",dElement,"的结点")算法2-17删除元素函数72假定我们在之前创建的单链表SLList中删除值为57的结点，通过执行算法2-17使得原本含有7个结点的单链表，变为含有6个结点的单链表。为了将值为57的结点成功删除，我们首先需要将值为57的结点的先驱结点内的指针指向值为57的结点的后继结点，进而再对值为57的结点执行删除操作，具体过程如图所示。73SingleLinkedList类的成员函数TraverseElement(self)，用于遍历单链表中的元素，其算法思路如下。（1）若头结点的指针域为空，则输出相应提示。（2）若头结点的指针域不为空，则调用VisitElement(self,tNode)方法将当前单链表中的元素逐一输出。2.3.2单链表74该算法思路对应的算法步骤如下。（1）使用变量cNode指向单链表SLList的头结点。（2）判断当前链表是否为空，若为空，则转（3），否则转（4）。（3）调用print()方法输出当前单链表为空的提示并返回。（4）当cNode不为空时，执行（5），否则执行（6）。（5）将cNode指向其后继结点，并调用VisitElement()方法输出cNode所指结点的值，转（4）。（6）退出程序。2.3.2单链表751#####################################2#遍历单链表函数3#####################################4defTraverseElement(self):5cNode=self.head6ifcNode.next==None:7print("当前单链表为空！")8return9print("您当前的单链表为：")10whilecNode!=None:11cNode=cNode.next12self.VisitElement(cNode)算法2-18遍历单链表函数761#####################################2#输出单链表某一元素函数3#####################################4defVisitElement(self,tNode):5iftNode!=None:6print(tNode.data,"->",end="")7else:8print("None")算法2-19输出单链表某一元素函数77循环单链表是在单链表的基础上，将其自身的第一个结点的地址存入表中最后一个结点的指针域中。与单链表相比，两者的基本操作大致类似，所以在本节中，我们将重点介绍循环单链表的创建、插入及删除操作。2.3.3循环单链表78创建文件ex020303.py。在该文件中我们首先定义一个Node类，该类包含创建结点并对结点进行初始化的操作。我们在实现这一方法时，调用了与单链表Node类中的__init__()方法相同的源代码。定义一个CircularSingleLinkedList类，用于创建一个循环单链表，并对其执行相关操作（参见教材p47表2-8）。2.3.3循环单链表79在实现CircularSingleLinkedList类的__init__(self)时，我们调用了与单链表SingleLinkedList类的__init__(self)方法类似的源代码。接下来，我们将具体实现CircularSingleLinkedList类中的CreateCircularSingleLinkedList(self)、InsertElementInTail(self)、InsertElementInHead(self)和DeleteElement(self)这4个方法，其余方法读者可根据自己的需要来实现。2.3.3循环单链表80SingleLinkedList类的成员函数CreateCircularSingleLinkedList(self)可创建一个新的循环单链表，其算法思路如下。（1）获取头结点。（2）由用户输入每个结点值，并依次创建这些结点。（3）每创建一个结点，将其链入循环单链表的尾部，并将头结点的地址存入其指针域中。（4）若用户输入“#”号，则结束输入，完成循环单链表的创建。2.3.3循环单链表81该算法思路对应的算法步骤如下。（1）调用input()方法接收用户输入的值data。（2）使用变量cNode指向头结点。（3）判断用户的输入是否为“#”，若结果为真，则转（6）；否则转（4）。（4）将data转化为整型数，然后将其作为参数去创建并初始化一个新结点nNode。（5）在cNode的next域中存入nNode的地址，并将头结点的地址存入nNode的next域中，最后将cNode指向其后继结点，并继续接受用户的输入后转（3）。（6）结束当前输入，完成循环单链表的创建。2.3.3循环单链表821####################################2#创建循环单链表函数3####################################4defCreateCircularSingleLinkedList(self):5print("*************************************************")6print("*请输入数据后按回车键确认，若想结束请输入“#”。*")7print("*************************************************")8data=input("请输入结点的值：")9cNode=self.head10whiledata!="#":11nNode=Node(int(data))12cNode.next=nNode13nNode.next=self.head14cNode=cNode.next15data=input("请输入结点的值：")算法2-20创建循环单链表函数83SingleLinkedList类的成员函数InsertElementInTail(self)，可向已有循环单链表的尾端插入结点，其算法思路如下。（1）输入待插入结点的值。（2）创建数据域为该值的结点。（3）在当前循环单链表的尾端插入该结点。2.3.3循环单链表84该算法思路对应的算法步骤如下。（1）调用input()方法接收用户输入，并将其存入变量Element中。（2）判断Element是否为“#”，若结果为真，则转（8）；否则转（3）。（3）使用cNode指向循环单链表的头结点。（4）将Element转化为整型数，然后将其作为参数去创建并初始化一个新结点。（5）判断cNode的next是否为头结点，若为真则转（7），否则转（6）。（6）将cNode指向其后继结点，转（5）。（7）将cNode的next指向新结点nNode，并将nNode的next指向头结点，完成该结点在循环单链表尾端的插入。（8）结束本程序并返回。2.3.3循环单链表851#####################################2#尾端插入函数3#####################################4defInsertElementInTail(self):5Element=input("请输入待插入结点的值：")6ifElement=="#":7return8cNode=self.head9nNode=Node(int(Element))10whilecNode.next!=self.head:11cNode=cNode.next12cNode.next=nNode13nNode.next=self.head算法2-21尾端插入函数86假定我们在之前创建的循环单链表CSLList中，将值为6的结点插入至表中最后一个位置。通过执行上述代码，将原本含有两个结点的循环单链表CSLList，变为含有3个结点的循环单链表CSLList。87SingleLinkedList类的成员函数InsertElementInHead(self)，在循环单链表的首端插入新结点，其算法思路如下。（1）输入待插入结点的值。（2）创建数据域为该值的结点。（3）在当前循环单链表的首端插入该结点。2.3.3循环单链表88该算法思路对应的算法步骤如下。（1）调用input()方法接收用户输入，并将其存入变量Element中。（2）判断Element是否为“#”，若结果为真，则转（7）；否则转（3）。（3）使用变量cNode指向循环单链表的头结点。（4）将Element转化为整型数，然后将其作为参数去创建并初始化一个新结点。（5）将nNode的next指向cNode的后继结点。（6）将cNode的next指向新结点nNode，完成循环单链表首端的插入。（7）结束本程序并返回。2.3.3循环单链表891#####################################2#首端插入函数3#####################################4defInsertElementInHead(self):5Element=input("请输入待插入结点的值：")6ifElement=="#":7return8cNode=self.head9nNode=Node(int(Element))10nNode.next=cNode.next11cNode.next=nNode算法2-22首端插入函数90SingleLinkedList类的成员函数DeleteElement(self)，可将循环单链表中与指定元素值相等的结点删除，其算法思路如下。（1）输入待删除结点的值。（2）在单链表中查找是否存在某一结点的值与待删除结点的值相等。（3）若查找成功，则执行删除操作。（4）若查找失败，则输出相应提示。2.3.3循环单链表91该算法思路对应的算法步骤如下。（1）调用input()方法由用户输入待删除结点的值，并使用变量dElement存储。（2）使用变量cNode、pNode指向循环单链表的头结点（3）判断当前链表是否为空，若为空则转（4），否则转（5）。（4）调用print()方法输出当前循环单链表为空的提示并返回。（5）当cNode的next不为头结点且cNode所指结点的值不等于dElement时，执行（6），否则执行（7）。（6）令pNode等于cNode，再将cNode指向其后继结点并转（5）。（7）判断cNode所指结点的值是否等于dElement，若为真，则转（8）；否则转（9）。（8）将pNode的next指向cNode的后继结点，然后删除cNode所指结点，再调用print()方法输出相应提示。（9）调用print()方法输出删除失败的提示。921#####################################2#删除元素函数3#####################################4defDeleteElement(self):5dElement=int(input('请输入待删除结点的值：'))6cNode=self.head7pNode=self.head8ifself.IsEmpty():9print("当前循环单链表为空！")10return11whilecNode.next!=self.headandcNode.data!=dElement:12pNode=cNode13cNode=cNode.next14ifcNode.data==dElement:15pNode.next=cNode.next16delcNode17print("成功删除含有元素",dElement,"的结点")18else:19print("删除失败！双链表中不存在含有元素",dElement,"的结点\n")算法2-23删除元素函数93通常在单链表中，每个结点都只有一个指向其直接后继结点的指针，我们只能通过这一指针访问到该结点的直接后继结点。若我们需要访问某一结点cNode的直接先驱结点，只能从头结点开始，借助于每一个结点的指针域依次访问其后继结点，直到某一结点的后继结点为cNode时，才找到了cNode的直接先驱结点。倘若我们为上述结点增加一个指针域，用来记录其直接先驱结点，则可大大提高处理此类问题的效率。我们将这种同时包含两个指针域的结点构成的链表称为双链表，对于每一个结点而言，它的一个指针域可用于存储该结点直接先驱结点的地址，我们将其称为先驱指针域，而另一个指针域用于存储该结点直接后继结点的地址，我们将其称为后继指针域。2.3.4双链表94在本节中，我们将具体介绍如何实现带头结点的双链表的基本操作，请读者按以下步骤执行。第1步，创建文件ex020304.py。在该文件中我们首先定义一个DoubleLinkedNode类，该类包含创建结点并对结点进行初始化的操作。第2步，定义一个DoubleLinkedList类，用于创建一个双链表，并对其执行相关操作（参见教材pp52~53表2-10）。2.3.4双链表95接下来，我们将具体实现DoubleLinkedNode类中的__init__()方法，以及DoubleLinkedList类中的__init__(self)、CreateDoubleLinkedList(self)、InsertElementInTail(self)、InsertElementInHead(self)、DeleteElement(self)和TraverseElement(self)这6个方法。其余方法读者可根据自己的需要来实现。2.3.4双链表96我们调用DoubleLinkedNode类的成员函数__init__（self,data）初始化一个结点，其算法思路如下。（1）创建一个数据域，用于存储每个结点的值。（2）创建一个后继指针域，用于存储下一个结点的地址。（3）创建一个先驱指针域，用于存储前一个结点的地址。（4）根据实际需要创建其他域，用于存储结点的各种信息。2.3.4双链表97该算法思路对应的算法步骤如下。（1）创建数据域并将其初始化为data。（2）创建后继指针域并将其初始化为空。（3）创建先驱指针域并将其初始化为空。2.3.4双链表981#######################2#初始化结点函数3#######################4def__init__(self,data):5self.data=data6self.next=None7self.prev=None算法2-24初始化结点函数99我们调用DoubleLinkedList类的成员函数__init__(self)来初始化头结点，其算法思路如下。（1）创建单链表的头结点。（2）将其初始化为空。该算法思路对应的算法步骤如下。（1）创建一个结点并将其初始化为空。（2）令双链表的头结点为上述结点。2.3.4双链表1001###################################2#初始化头结点函数3###################################4def__init__(self):5self.head=DoubleLinkedNode(None)算法2-25初始化头结点函数101我们调用DoubleLinkedList类的成员函数CreateDoubleLinkedList(self)创建一个双链表，其算法思路如下。（1）获取头结点。（2）由用户输入每个结点值，并依次创建这些结点。（3）每创建一个结点，将其链入双链表的尾部。（4）若用户输入“#”号，转（5）；否则转（2）。（5）完成双链表的创建。2.3.4双链表102该算法思路对应的算法步骤如下。（1）调用input()方法接收用户输入的值data。（2）使用变量cNode指向头结点。（3）判断用户的输入是否为“#”，若结果为真，则转（6）；否则转（4）。（4）将data转化为整型数，然后将其作为参数去创建并初始化一个新结点nNode。（5）在cNode的next中存入nNode，再将cNode存入nNode的prev中，最后将cNode指向其直接后继结点，并继续接受用户输入后转（3）。（6）结束当前输入，完成双链表的创建。2.3.4双链表1031###################################2#创建双链表函数3###################################4defCreateDoubleLinkedList(self):5print("*************************************************")6print("*请输入数据后按回车键确认，若想结束请输入“#”。*")7print("*************************************************")8data=input("请输入元素：")9cNode=self.head10whiledata!='#':11nNode=DoubleLinkedNode(int(data))12cNode.next=nNode13nNode.prev=cNode14cNode=cNode.next15data=input("请输入元素：")算法2-26创建双链表函数104通过执行上述代码，我们可以创建一个新的双链表。如图所示为某一次输入所产生的双链表DLList，若无特殊说明，我们在之后讲解的内容都会基于该双链表进行操作。105我们调用DoubleLinkedList类的成员函数InsertElementInTail(self)，向已有双链表的尾端插入结点，其算法思路如下。（1）输入待插入结点的值。（2）创建数据域为该值的结点。（3）在当前双链表的尾端插入该结点。2.3.4双链表106该算法思路对应的算法步骤如下。（1）调用input()方法接收用户输入，并将其存入变量Element中。（2）判断Element是否为“#”，若结果为真，则转（8）；否则转（3）。（3）将Element转化为整型数，然后将其作为参数去创建并初始化一个新结点。（4）使用cNode指向当前双链表的头结点。（5）判断cNode所指结点的后继指针域是否为空，若为空则转（7），否则转（6