【2】数据结构的单链表章

单链表的定义

• 结点（Node）的定义：数据域（data）和指针域（next）。其中，
  • data存储结点的值
  • next存储直接后继的地址
• 代码声明结点

class Node:"""定义节点类型"""def __init__(self, data):# 存储数据元素的数据域self.data = data# 存储指向后继结点位置的指针域self.next = None

• 结点示意图
  
• 定义：链表中的每一个结点只有一个指针域，将该类链表称为单链表。以单链表（A,B,C,D,E）为例。
• 单链表逻辑结构示意图
  
• 单链表物理结构示意图
  

单链表的初始化

• 初始化单链表

    def __init__(self):"""单链表的初始化"""# 声明头结点self.head = Node(None)

• 判断单链表是否为空表

    def isEmpty(self):"""判断单链表是否为空表:return: True or False"""# 如果头结点的next域为空，则返回True，否则返回falsereturn self.head.next == None

• 求单链表的长度

    def getLength(self):"""获取单链表的长度:return: 当前单链表中数据元素的个数"""# 设置length,用来计算长度，初始值为0length = 0# 声明cur指针，用于遍历单链表，初始值为第一个结点cur = self.head.next# 循环，直到cur==Nonewhile cur != None:# 单链表长度加1length += 1# cur指针指向当前结点的后继cur = cur.nextreturn length

• 打印单链表

    def display(self):"""展示单链表:return:"""#判断是否为空表if self.isEmpty():print("当前单链表为空表！")return# 遍历单链表，并展示数据元素print("单链表中的数据元素：", end="")cur = self.head.nextwhile cur!= None:print(cur.data, end=",")cur = cur.nextprint()

单链表的建立

头插法创建

• 将需加入的结点，不断加入到头结点的后面。

• 核心思想：

  • 将新结点的next指向头结点的后继结点
  • 将头结点的next指向新结点

• 头插法示意图
  

• 代码定义头插法函数

    def prepend(self, data):"""头插法:param data: 待插入的元素:return:"""# 创建新结点，在新结点中存储元素newNode = Node(data)# 修改指针指向，实现插入# 将新结点的next指向头结点的后继结点newNode.next = self.head.next# 将头结点的next指向新节点self.head.next = newNode

尾插法创建

• 将新结点不断地加入为当前链表的尾部。

• 核心思想：

  • 寻找尾结点
  • 将尾指针的next指向新结点

• 尾插法示意图
  

• 代码定义尾插法函数

    def append(self, data):"""尾插法:param data: 待插入的元素:return:"""# 创建尾指针，初始化指向头结点rear = self.head# 循环，寻找尾结点while rear.next != None:rear = rear.next# 创建新结点，在新节点中存储元素newNode =  Node(data)# 修改指针指向，实现插入# 将尾指针的next指向新结点rear.next = newNode

查找操作

按序号查找

• 从头结点开始扫描，直到第index个结点数，返回结点。
• 代码定义方法

    def getData(self, index):"""按序号查找:param index: 待查找的序号:return: 待查找位置对应的元素值"""# 判断index是否合法if index <= 0 or index > self.getLength():raise IndexError('index 非法')# 声明变量作为计数器，累计当前的结点数。初始为0i = 0# 声明指针cur,用于遍历cur = self.head# 循环扫描while cur != None and i != index:cur = cur.nexti += 1return cur

按内容查找

• 在表中查找与内容值key相同的结点，找到了返回下标，否则返回空序号-1。

• 代码定义方法

    def locate(self, key):"""按内容查找:param key: 待查找的内容:return: 查找内容的位置序号"""# 声明index为索引位置，初始-1index = -1cur = self.head.nexti = 0while cur != None:i += 1if cur.data == key:index = ibreakcur = cur.nextreturn index

插入操作

• 核心思想：

  • 遍历找到需插入的前一个结点，并用pre指针指向它
  • 将新结点的next指向pre指针所指向的结点的后续结点
  • 将pre指针所指向的结点的next指向新结点

• 插入示意图
  

• 代码定义方法

    def insert(self, index, data):"""在单链表中任意位置插入元素:param index: 待插入的位置:param data: 待插入的元素:return:"""# 判断index是否合法if index <= 0 or index > self.getLength():raise IndexError("index 非法")# 在单链表中找到插入的位置，即第index-1个结点，并由pre指针指示# 设置i,用于判断是否找到index-1的位置i = 1# 声明pre指针，初始化为指向头结点,用于指示第index-1个结点pre = self.head# 循环，直到pre空，或指向第index-1个结点while pre != None and i !=index:pre = pre.nexti += 1# 创建新节点，在新节点中存储数据元素newNode = Node(data)# 修改指针指向，以实现插入newNode.next = pre.nextpre.next = newNode

删除操作

• 核心思想：

  • 循环，找到需要删除的位置，用指针pre指向要删除的前一个结点
  • 将pre的next指向被删除结点的后继结点

• 删除方法示意图
  

• 代码定义方法

    def delete(self, index):"""在单链表中任意位置删除元素:param index: 待删除的位置:return: 被删除的结点"""# 判断是否合法if index <= 0 or index > self.getLength():raise IndexError("index 非法")# 判断是否为空if self.isEmpty():raise IndexError("单链表为空，不允许删除")i = 1# 用于遍历单链表，初始化为头结点pre = self.head# 循环，当pre为空或pre为第index-1个结点结束while pre != None and i != index:pre = pre.nexti += 1# 获取被删除的结点delNode = pre.next# 修改指针指向，实现删除pre.next = delNode.nextreturn delNode

合并操作

• 核心思想：

  • 通过更改结点的next域来重建新结点之间的线性关系；
  • 利用尾插法创建listC单链表，以保证新表有序；

• 合并方法示意图
  

• 代码定义方法

    def merge(self, listB):"""合并操作:param listB: 待合并的单链表B:return: 合并后的单链表listC"""# 声明nodeA和B指针分别指向listA和B当前待合并的结点，分别初始化为listA和B的第一个结点nodeA = self.head.nextnodeB = listB.head.next# 创建listC,沿用listA的头结点listC = LinkedList()listC.head = self.head# 定义tailC作为listC的尾指针，用于合并数据元素，初始化listC的头结点tailC = listC.head# 循环，将较小的结点插入listC中while nodeA != None and nodeB != None:if nodeA.data <= nodeB.data:tailC.next = nodeAtailC = nodeAnodeA =nodeA.nextelse:tailC.next = nodeBtailC = nodeBnodeB = nodeB.next# 如果listA未合并结束，则将listA中剩余的结点链接到listC的表尾if nodeA != None:tailC.next = nodeA# 如果listB未合并结束，则将listB中剩余的结点连接到listC的表尾if nodeB != None:tailC.next = nodeBreturn listC

单链表总代码与调试

• 链式存储结构的优缺点
  • 优点：不用考虑单链表的存储空间大小，只要内存足够大，就可以无限延伸；插入或删除方便，只要改变指针域的指向，不用移动大量的结点，效率较顺序表高很多。
  • 缺点：逻辑地址与物理地址不一定有直接的映射关系，随机存取单链表中的任一元素的效率较顺序表低。

# 4.单链表的实现
class Node:"""定义节点类型"""def __init__(self, data):# 存储数据元素的数据域self.data = data# 存储指向后继结点位置的指针域self.next = Noneclass LinkedList:"""单链表的定义"""def __init__(self):"""单链表的初始化"""# 声明头结点self.head = Node(None)def isEmpty(self):"""判断单链表是否为空表:return: True or False"""# 如果头结点的next域为空，则返回True，否则返回falsereturn self.head.next == Nonedef getLength(self):"""获取单链表的长度:return: 当前单链表中数据元素的个数"""# 设置length,用来计算长度，初始值为0length = 0# 声明cur指针，用于遍历单链表，初始值为第一个结点cur = self.head.next# 循环，直到cur==Nonewhile cur != None:# 单链表长度加1length += 1# cur指针指向当前结点的后继cur = cur.nextreturn lengthdef display(self):"""展示单链表:return:"""#判断是否为空表if self.isEmpty():print("当前单链表为空表！")return# 遍历单链表，并展示数据元素print("单链表中的数据元素：", end="")cur = self.head.nextwhile cur!= None:print(cur.data, end=",")cur = cur.nextprint()def prepend(self, data):"""头插法:param data: 待插入的元素:return:"""# 创建新结点，在新结点中存储元素newNode = Node(data)# 修改指针指向，实现插入# 将新结点的next指向头结点的后继结点newNode.next = self.head.next# 将头结点的next指向新节点self.head.next = newNodedef append(self, data):"""尾插法:param data: 待插入的元素:return:"""# 创建尾指针，初始化指向头结点rear = self.head# 循环，寻找尾结点while rear.next != None:rear = rear.next# 创建新结点，在新节点中存储元素newNode =  Node(data)# 修改指针指向，实现插入# 将尾指针的next指向新结点rear.next = newNodedef getData(self, index):"""按序号查找:param index: 待查找的序号:return: 待查找位置对应的元素值"""# 判断index是否合法if index <= 0 or index > self.getLength():raise IndexError('index 非法')# 声明变量作为计数器，累计当前的结点数。初始为0i = 0# 声明指针cur,用于遍历cur = self.head# 循环扫描while cur != None and i != index:cur = cur.nexti += 1return curdef locate(self, key):"""按内容查找:param key: 待查找的内容:return: 查找内容的位置序号"""# 声明index为索引位置，初始-1index = -1cur = self.head.nexti = 0while cur != None:i += 1if cur.data == key:index = ibreakcur = cur.nextreturn indexdef insert(self, index, data):"""在单链表中任意位置插入元素:param index: 待插入的位置:param data: 待插入的元素:return:"""# 判断index是否合法if index <= 0 or index > self.getLength():raise IndexError("index 非法")# 在单链表中找到插入的位置，即第index-1个结点，并由pre指针指示# 设置i,用于判断是否找到index-1的位置i = 1# 声明pre指针，初始化为指向头结点,用于指示第index-1个结点pre = self.head# 循环，直到pre空，或指向第index-1个结点while pre != None and i !=index:pre = pre.nexti += 1# 创建新节点，在新节点中存储数据元素newNode = Node(data)# 修改指针指向，以实现插入newNode.next = pre.nextpre.next = newNodedef delete(self, index):"""在单链表中任意位置删除元素:param index: 待删除的位置:return: 被删除的结点"""# 判断是否合法if index <= 0 or index > self.getLength():raise IndexError("index 非法")# 判断是否为空if self.isEmpty():raise IndexError("单链表为空，不允许删除")i = 1# 用于遍历单链表，初始化为头结点pre = self.head# 循环，当pre为空或pre为第index-1个结点结束while pre != None and i != index:pre = pre.nexti += 1# 获取被删除的结点delNode = pre.next# 修改指针指向，实现删除pre.next = delNode.nextreturn delNodedef merge(self, listB):"""合并操作:param listB: 待合并的单链表B:return: 合并后的单链表listC"""# 声明nodeA和B指针分别指向listA和B当前待合并的结点，分别初始化为listA和B的第一个结点nodeA = self.head.nextnodeB = listB.head.next# 创建listC,沿用listA的头结点listC = LinkedList()listC.head = self.head# 定义tailC作为listC的尾指针，用于合并数据元素，初始化listC的头结点tailC = listC.head# 循环，将较小的结点插入listC中while nodeA != None and nodeB != None:if nodeA.data <= nodeB.data:tailC.next = nodeAtailC = nodeAnodeA =nodeA.nextelse:tailC.next = nodeBtailC = nodeBnodeB = nodeB.next# 如果listA未合并结束，则将listA中剩余的结点链接到listC的表尾if nodeA != None:tailC.next = nodeA# 如果listB未合并结束，则将listB中剩余的结点连接到listC的表尾if nodeB != None:tailC.next = nodeBreturn listCif __name__ == '__main__':# print('PyCharm')# 1.初始化单链表list = LinkedList()list.display()# 2-0.创建单链表，采用头插入操作创建for i in range(10):list.prepend(ord("A") + i)print("头插法操作结果：", end='')list.display()# 2-1.创建单链表，采用尾插法进行操作list = LinkedList()for i in range(10):list.append(chr(ord("A") + i))print('尾插法操作结果:', end='')list.display()# 3.获取单链表的长度length = list.getLength()print('当前单链表中的长度为：%d' % length)# 4.在表中任意位置插入元素list.insert(2, "T")list.display()#  5-0.按序号查找node = list.getData(2)print('按序号查找的结果：%s' % node.data)# 5-1.按内容查找index = list.locate("B")if index == -1:print("未找到你要的内容位置")else:print("按内容查找的结果：%d" % index)# 6.在单链表中任意位置删除元素node = list.delete(2)print("被删除的数据元素为: %s" % node.data)list.display()# 7.合并操作# 原始元素dataA = (8, 21, 25, 49, 62)dataB = (16, 37, 54, 72, 82, 90)# 创建listAlistA = LinkedList()for i in range(len(dataA)):listA.append(dataA[i])listA.display()# 创建listBlistB = LinkedList()for i in range(len(dataB)):listB.append(dataB[i])listB.display()# 合并成listClistC = listA.merge(listB)listC.display()