12.抽象数据类型_类 知识点梳理- 2023届浙教版（2019）高考信息技术专题复习（选修）

第十二章 类(抽象数据类型) 引：在前两章中我们介绍了链表、队列、栈三种数据结构。在学习和使用过程中会发现这几种数据结构有个共同的特点，就是需要“数组（列表）+指针（整数类型）”来表示一个数据结构。为了让这些数据结构在使用和操作时更具有整体性，我们引入类的概念。 一、链表类 对链表进行抽象处理时，我们发现链表的节点本身就是由两个以上元素（值域+指针域）组成的。所以对链表抽象之前需要先定义节点类，代码如下： class LinkNode:               #定义单向节点类     def __init__(self,data_,next_=None):   #注意函数默认值的使用         self.data = data_ #值域         self.next = next_ #指针域 __init__()函数是类的构造函数，在用类生成实例时会自动调用。构造函数内定义的是该类的属性值，由于单向链表节点只有值和指针两个元素，故只需要定义data和next两个属性。 在类中定义的函数我们一般称之为“方法”，故__init__()也称构造方法。在构造方法的参数列表中有三个参数，其中self是类方法对自己的调用，故在对自身值域赋值时是写的是self.data，剩下的两个是从外部获取值域和指针域值的变量。需要特别指出是，self参数不需要也不能赋值，在方法外部只能看到data_和next_这两个参数。 再定义链表类，代码如下： class LinkList:               #定义单链表类     def __init__(self):       #构造方法         self.head=None #链表头指针 这样其实我们就已经定义好了一个基础的链表类，我们现在可以使用类来生成链表实例 a = LinkList() #用链表类生成链表实例a a.head = LinkNode(2) #用节点类生成节点实例，并用链表a的头指针指向该节点 print(a.head.data) #输出链表头节点的值域的值 以上我们就生成了一个链表a和一个值域为2的节点，并让链表a的头指针直接指向了该节点。抽象数据类型除了可以定义属性，还可以定义操作方法。对链表常见的操作有插入、删除、求链表长度、格式化输出等......我们可以将这些操作方法也定义到链表类中。 class LinkList:               #定义单链表类     def __init__(self):       #构造方法         self.head=None     def __str__(self):        #格式化输出，执行print()时自动调用         s = ""         cur=self.head         while cur is not None:             s += f"{cur.data}->"   #format方法的另外一种写法             cur=cur.next         return s[:-2]       #删除多余的“->”     def len(self): #求链表长度         num = 0         cur = self.head         while cur is not None:             num += 1             cur = cur.next         return num     def perpend(self,data_):     #头插法         if self.head is None:             self.head=LinkNode(data_)         else:             self.head=LinkNode(data_,self.head)     def append(self,data_):      #尾插法         if self.head is None:             self.head = LinkNode(data_)         else:             cur = self.head             while cur.next is not None:                 cur = cur.next             cur.next = LinkNode(data_)     def insert(self