美文网首页
2.6 数据结构 --1.4 链表

2.6 数据结构 --1.4 链表

作者: 寒暄_HX | 来源:发表于2020-03-12 13:37 被阅读0次

数据结构子目录https://www.jianshu.com/p/a344fa483655

顺序表

顺序表按照存储的元素类型,可以分为两种,一种是单类型顺序表,一种是多类型顺序表。
Python中的列表和元组便是多类型顺序表,多类型顺序表的内存不是连续开辟的。
数组是单类型顺序表。

顺序表的弊端

需要先预知数据大小来开辟空间,如果需要扩充就需要对数据进行迁移。

链表

相比于顺序表,链表可以更加充分利用计算机的空间,实现灵活的内存动态管理,且进行扩容时不需要迁移。

什么是链表

链表中每一个元素都是一个对象,每一个对象称为一个节点,包含有数据域key与指向下一个节点的指针next,通过各个节点之间的相互连接,最终串联成一个链表。

节点定义

# Student类(节点类)         一个Student对象就是一个节点
class Student:
    def __init__(self,SchNum,name,score):
        self.SchNum = SchNum
        self.name = name
        self.score = score  #保存三个数据
        self.next = None  #下一个节点的指针

链表定义

# 链表类
class Link:

    # 构造函数
    def __init__(self):
        self.head = Student(None,None,None)            # 头节点为空
        self.tail = self.head
        self.size = 1
单向链表

建立链表--头插法

pcur是要插入到新链表中的节点
prev是pcur的next
步骤如下:

  • prev保存下一个要插入的节点
  • 把pcur插入到新链表中
  • 调整头节点的指向
  • 下一个要插入的节点为prev
# 链表类
class Link:

    # 构造函数
    def __init__(self):
        self.head = Student(None,None,None)            # 头节点为空
        self.tail = self.head
        self.size = 1
    #头插法
    def new_invert(self,head):
        dummy = self.head                       # 头节点当做新链表的尾节点
        pcur = head.next
        count = 0
        while(count < self.size - 1):
            prev = pcur.next                    # prev保存下一个要插入的节点
            pcur.next = dummy                   # 把pcur插入到新链表中
            dummy = pcur                        # 调整头节点的指向
            pcur = prev                         # 下一个要插入的节点为prev
            count = count + 1

        self.head = dummy

连接链表

直接将link1的尾节点的next指向link2的头节点就可以啦。

# 链表类
class Link:

    # 构造函数
    def __init__(self):
        self.head = Student(None,None,None)            # 头节点为空
        self.tail = self.head
        self.size = 1
    # 连接两个链表
    def connectLink(self,link):
        self.tail.next = link.head.next
        self.size = self.size + link.size - 1       # 链表大小相加

反转链表

prev指向头节点
pcur是当前需要反转的节点
dummy是头节点

步骤如下:

  • prev连接下一次需要反转的节点
  • 反转节点pcur
  • 将dummy向后移动一位
  • pcur指向下一次需要反转的节点
# 链表类
class Link:

    # 构造函数
    def __init__(self):
        self.head = Student(None,None,None)            # 头节点为空
        self.tail = self.head
        self.size = 1
    # 反转链表(就地反转)
    def jiudi_invert(self,head):
        dummy = Student(None,None,None)
        dummy.next = head                       # 创建新节点,新节点的下一个指向头(head)节点
        prev = dummy.next                       # prev也指向头(head)节点
        pcur = prev.next                        # pcur是当前需要反转的节点

        while(pcur != None):                    # 循环条件:直到尾节点结束
            prev.next = pcur.next               # prev连接下一次需要反转的节点
            pcur.next = dummy.next              # 反转
            dummy.next = pcur                   # 纠正头节点的位置(将头节点向后移动一位)
            pcur = prev.next                    # pcur指向下一次需要反转的节点

        self.head = dummy.next 

节点操作

增加节点

增加元素是将一个新的节点增加在链表的尾部,要增加一个节点,我们需要一下步骤:

  • 将链表尾节点的下一个节点指向新节点
  • 将新节点作为尾节点
  • 链表的长度+1
# 添加节点
    def add(self,SchNum,name,score):
        stu = Student(SchNum,name,score)        # 创建新节点
        self.tail.next = stu                    # 尾节点的下一个节点为新节点
        self.tail = stu                         # 尾节点为新节点
        self.size = self.size + 1

插入节点

如果我们想要将一个节点插入到链表中,我们需要哪些步骤呢?

  • 首先 ,推进到要插入的位置的前一个节点before处
  • before.next为新节点
  • 新节点.next为原链表before的下一个节点
  • 链表的长度+1
   # 插入节点(此节点作为第index个节点)
    def insert(self,SchNum,name,score,index):
        if(index > self.size):
            print('链表还没有这么长哟!请输入小一点的整数......')
        else:
            stu = self.head
            insert_stu = Student(SchNum,name,score)
            for i in range(index - 1):
                stu = stu.next                      # 推进到要插入的位置
            insert_stu.next = stu.next
            stu.next = insert_stu
            self.size = self.size + 1

删除节点

我们假设一个链表结构 before—>delete—>after。如果我们想要删除delete节点,那么我们只需要将before的下一个节点指向after就可以了,然后链表长度-1

  # 删除节点(索引为index)
    def delete(self,index):
        if (index > self.size):
            print('链表还没有这么长哟!请输入小一点的整数......')
        else:
            stu = self.head
            for i in range(index - 1):
                stu = stu.next
            temp = stu.next
            stu.next = temp.next
            self.size = self.size - 1

修改节点数据

# 改变指定节点的数据
    def change(self,SchNum,name,score,index):
        if (index > self.size):
            print('链表还没有这么长哟!请输入小一点的整数......')
        else:
            stu = self.head
            for i in range(index):                  # 推进到要改变节点的位置
                stu = stu.next
            stu.SchNum =SchNum
            stu.name = name
            stu.score =score

查询节点数据

 # 返回节点的数据
    def getData(self,index):
        if(index > self.size):                                  # 判断是否超过链表的长度
            print('链表还没有这么长哟!请输入小一点的整数......')
        else:
            stu = self.head
            for i in range(index):
                stu = stu.next
            return [stu.SchNum,stu.name,stu.score]

获取链表长度

    # 返回节点的长度
    def getSize(self):
        return self.size

总结

# Student类(节点类)         一个Student对象就是一个节点
class Student:
    def __init__(self,SchNum,name,score):
        self.SchNum = SchNum
        self.name = name
        self.score = score
        self.next = None

# 链表类
class Link:

    # 构造函数
    def __init__(self):
        self.head = Student(None,None,None)            # 头节点为空
        self.tail = self.head
        self.size = 1


    # 添加节点
    def add(self,SchNum,name,score):
        stu = Student(SchNum,name,score)        # 创建新节点
        self.tail.next = stu                    # 尾节点的下一个节点为新节点
        self.tail = stu                         # 尾节点为新节点
        self.size = self.size + 1


    # 插入节点(此节点作为第index个节点)
    def insert(self,SchNum,name,score,index):
        if(index > self.size):
            print('链表还没有这么长哟!请输入小一点的整数......')
        else:
            stu = self.head
            insert_stu = Student(SchNum,name,score)
            for i in range(index - 1):
                stu = stu.next                      # 推进到要插入的位置
            insert_stu.next = stu.next
            stu.next = insert_stu
            self.size = self.size + 1


    # 删除节点(索引为index)
    def delete(self,index):
        if (index > self.size):
            print('链表还没有这么长哟!请输入小一点的整数......')
        else:
            stu = self.head
            for i in range(index - 1):
                stu = stu.next
            temp = stu.next
            stu.next = temp.next
            self.size = self.size - 1


    # 改变指定节点的数据
    def change(self,SchNum,name,score,index):
        if (index > self.size):
            print('链表还没有这么长哟!请输入小一点的整数......')
        else:
            stu = self.head
            for i in range(index):                  # 推进到要改变节点的位置
                stu = stu.next
            stu.SchNum =SchNum
            stu.name = name
            stu.score =score


    # 返回节点的数据
    def getData(self,index):
        if(index > self.size):                                  # 判断是否超过链表的长度
            print('链表还没有这么长哟!请输入小一点的整数......')
        else:
            stu = self.head
            for i in range(index):
                stu = stu.next
            return [stu.SchNum,stu.name,stu.score]

    # 返回节点的长度
    def getSize(self):
        return self.size


    # 反转链表(就地反转)
    def jiudi_invert(self,head):
        dummy = Student(None,None,None)
        dummy.next = head                       # 创建新节点,新节点的下一个指向头(head)节点
        prev = dummy.next                       # prev也指向头(head)节点
        pcur = prev.next                        # pcur是当前需要反转的节点

        while(pcur != None):                    # 循环条件:直到尾节点结束
            prev.next = pcur.next               # prev连接下一次需要反转的节点
            pcur.next = dummy.next              # 反转
            dummy.next = pcur                   # 纠正头节点的位置(将头节点向后移动一位)
            pcur = prev.next                    # pcur指向下一次需要反转的节点

        self.head = dummy.next                  # 链表彻底反转完成,尾节点变为头节点

    # 反转链表(创建新链表,头节点插入法)
    def new_invert(self,head):
        dummy = self.head                       # 头节点当做新链表的尾节点
        pcur = head.next
        count = 0
        while(count < self.size - 1):
            prev = pcur.next                    # prev保存下一个要插入的节点
            pcur.next = dummy                   # 把pcur插入到新链表中
            dummy = pcur                        # 调整头节点的指向
            pcur = prev                         # 下一个要插入的节点为prev
            count = count + 1

        self.head = dummy


    # 连接两个链表
    def connectLink(self,link):
        self.tail.next = link.head.next
        self.size = self.size + link.size - 1       # 链表大小相加


def main():
    link = Link()               # 创建链表

    newlink = Link()            # 创建newlink,用作链表连接
    for i in range(5):
        newlink.add(i,'我是新链表!!!',i)

    print('添加节点 => 1 , 插入节点 => 2 , 删除节点 => 3 , 改变节点数据 => 4 , 遍历链表 => 5 , 获取链表长度 => 6')
    print('反转链表(就地反转) => 7 , 连接两个链表 => 8 , 反转链表(头节点插入法) => 9 , 退出 => 0')
    select = -1

    while select != 0:
        select = int(input('请选择:'))

        if(select == 1):                                    # 添加
            print('请输入相应数据')
            SchNum = int(input('学号:'))
            name = input('姓名:')
            score = input('成绩:')
            link.add(SchNum,name,score)
        elif(select == 2):                                  # 插入
            print('请输入相应数据')
            SchNum = int(input('学号:'))
            name = input('姓名:')
            score = input('成绩:')
            index = int(input('要插入的位置(整数):'))
            link.insert(SchNum,name,score,index)
        elif(select == 3):                                  # 删除
            index = int(input('要删除节点的索引:'))
            link.delete(index)
        elif(select == 4):                                  # 改变数据
            print('请输入相应数据')
            SchNum = int(input('学号:'))
            name = input('姓名:')
            score = input('成绩:')
            index = int(input('要改变的位置(整数):'))
            link.change(SchNum,name,score,index)
        elif(select == 5):                                  # 遍历
            print('学号------姓名--------成绩')
            for i in range(link.size):
                data = link.getData(i)
                print(str(data[0]) + '   ' + str(data[1]) + '   ' + str(data[2]))
        elif(select == 6):                                  # 获取长度
            print('链表的长度为:'+str(link.getSize()))
        elif(select == 7):
            link.jiudi_invert(link.head)
        elif(select == 8):
            link.connectLink(newlink)
        elif(select == 9):
            link.new_invert(link.head)


if __name__ == '__main__':
    main()

参考

相关文章

  • 2.6 数据结构 --1.4 链表

    数据结构子目录https://www.jianshu.com/p/a344fa483655 顺序表 顺序表按照存储...

  • redis 学习整理

    本文是《redis设计与实现》的学习整理。 1 基础数据结构 1.1 字符串 1.2 链表 1.3 哈希表 1.4...

  • 算法与数据结构知识汇总(二、链表)

    1、概念 2、链表的数据结构 单向链表的数据结构如下图: 上图数据结构为单向链表,简称单链表,该数据结构由若干个节...

  • iOS 数据结构之链表

    iOS 数据结构之链表 iOS 数据结构之链表

  • 2019-03-23 集合-lis

    1.常见的数据结构自定义容器类: 基于 1.1数组 1.2链表 1.3队列 1.4堆栈 1.5树 2.Array...

  • 数据结构 | 其二 链表

    冰河winner - 数据结构之链表 2.1 单向链表 数据结构(一) 单链表的实现-JAVA 2.2 双端链表 ...

  • 数据结构之线性表

    其他文章:数据结构之栈和队列 文章目录1.1 概念1.2 顺序表1.3 链表1.4 两种存储方式的比较1.5 两种...

  • Go语言数据结构和算法-LinkedList(链表)

    Go语言数据结构和算法-LinkedList(链表) 节点和链表数据结构 Prepend(item) 在链表头新增...

  • 集合-LinkedList解析

    一、概要 Java中底层数据结构是链表、双端链表,Android中数据结构是双向循环链表 非线程安全数据结构,允许...

  • 常见数据结构和算法

    常见数据结构 线性数据结构(按顺序具有数据元素的数据结构):数组,堆栈,链表(单链表 双链表),队列非线性数据结...

网友评论

      本文标题:2.6 数据结构 --1.4 链表

      本文链接:https://www.haomeiwen.com/subject/ldjyjhtx.html