链表的知识总结

Python128

链式结构内存不连续的，而是一个个串起来的，每个链接表的节点保存一个指向下一个节点的指针。

⭐ 链式结构包含：node（节点）还有value（值），由于内存不连续的，那么对于数据的插入，只需找到一个节点便可以插入数据，这也是链表优于列表的一个优点，反之，对于数据的删除，由于不是连续的，不能通过索引删除数据，只能一一遍历删除元素。

⭐ 接下来上代码 单链表的增删功能

# 定义一个结点的类
class Node():
    def __init__(self,value=None,next=None):
        self.next = next
        self.value = value

    def __str__(self):
        return "Node:{}".format(self.value)

# 定义一个连接点的类
class Linklist():

    def __init__(self):
        self.root = Node()
        self.size = 0
        self.next = None  # 增加新数据时，将信数据的地址与谁关联

    # 只要是追加 就要创造节点
    def append(self,value):
        node = Node(value)
        # 判断root节点下面是否有数据
        if not self.next: # 如果没有节点
            self.root.next = node  # 将新节点挂在root后面
        else:
            self.next.next = node  # 将新节点挂在最后一个节点上
        self.next = node # 重新赋值 一开始的是None
        self.size += 1

    def append_first(self,value):
        # 只要是追加 就要创造节点
        node = Node(value)
        # 判断root下面是否存在节点
        if not self.next:
            self.root.next = node
            self.next = node
        else:
            temp = self.root.next # 获取原来root后面的那个节点
            self.root.next = node #  将新节点挂在root后面
            node.next = temp # 新的节点的下一个节点是原来的root的节点

    # 迭代链表
    def __iter__(self):
        # 获得root节点下面的数据
        current = self.root.next
        # 判断current是否有之 由于一开始赋予value和next没有值 所以进行判断 否则报错
        if current:
            # 判断时候有下一个节点 有的话则返回下一个结点的值
            while current is not self.next: # self.next可以列结成最后一个节点
                yield current
                current = current.next
            yield current

    # 查找数据
    def find(self,value):
        for n in self.__iter__():
            if n.value == value:
                return n

    # 查找出现的次数
    def find_count(self,value):
        count = 0
        for n in self.__iter__():
            if n.value == value:
                count += 1
        return count

    # 移除数据(链表的移除，需要逐一遍历，找到当前元素的节点，再删除)
    def remove(self,value):
        prve = self.root
        for n in self.__iter__():
            # 判断节点的值与要删除的值是否相等
            if n.value == value:
                # 查看是不是最后一个节点
                if n == self.next:
                    # 更新倒数第二节点的关系
                    prve.next = None
                    # 更新最后一个节点为原倒数第二个节点
                    self.next = prve
                prve.next = None
                # 删除当前节点
                del n
                # 链表大小减少
                self.size -= 1
                return True
            prve = n

    def remove_all(self,value):
        prve =self.root
        for n in self.__iter__():
            if n.value == value:
                if n == self.next:
                    prve.next = None
                    self.next = prve
                prve.next = n.next
                # 删除当前节点
                del n
                # 链表大小减少
                self.size -= 1
                return True
            prve = n

if __name__ == "__main__":
    link = Linklist()
    link.append("孙悟空")
    link.append("猪八戒")
    link.append("孙悟空")
    link.append("猪八戒")
    link.append("猪八戒")
    link.append("唐僧")
    link.append_first("唐僧")
    link.append_first("唐僧")
    # for v in link:
    #     print(v)
    # print(link.find('孙悟空'))
    # print(link.find_count('唐僧'))

    print("**************删除之前的数据******************")
    for v in link:
        print(v)
    link.remove('唐僧')
    link.remove('唐僧')
    link.remove('唐僧')
    link.remove('唐僧')
    link.remove('孙悟空')
    link.remove('猪八戒')

    link.remove_all("猪八戒")
    link.remove_all("孙悟空")
    link.remove_all("唐僧")

    print("**************删除之后的数据******************")
    for v in link:
        print(v)

链表的知识总结

⭐ 接下来上代码 双链表的增删功能：

# 定义一个结点的类
class Node():
    def __init__(self,value=None,node=None,next=None):
        self.value = value
        self.node = node
        self.next = next
    def __str__(self):
        return "Node:{}".format(self.value)

# 定义一个连接点的类
class DoubleLinkedList():
    def __init__(self):
        self.root = Node()
        self.size = 0
        self.end = None

    def append(self,value):
        node = Node(value)
        # 判断root节点下面是否有数据
        if not self.end: # 如果没有元素
            self.root.next = node  # 将root 的下一个节点 设置为新的node节点
            node.prev = self.root  # 设置新节点的 上一个节点 为 root
        else:
            self.end.next = node  # 将原来最后节点的下一个节点 设置为新的node节点
            node.prev = self.end # 设置新节点的 上一个节点 为 原来的最后一个节点
        self.end = node # 更新最后 一个节点新加的node节点
        self.size += 1

    def append_first(self,value):
        node = Node(value) # 封装节点对象
        # 判断是否已经有数据
        if not self.end:# 如果没有元素
            self.end = node # 更新最后 一个节点新加的node节点
        else:
            # temp指向node，node指向root，root指向temp
            temp = self.root.next # 保存原来的第一个节点
            node.next = temp # 设置新节的下一个节为原来的 第一个节点
            temp.prev = node # 更新原来的第一个节点的上一个节点位置为 新的node节点
        node.prev = self.root # 设置新节点的 上一个节点 为 root
        self.root.next = node # 将root 的下一个节点 设置为新的node节点
        self.size += 1

    # 正序循环
    def __iter__(self):
        current = self.root.next
        if current:
            while current is not self.end:
                yield current.value
                current = current.next
            yield current.value

    # 倒叙循环
    def revers_iter(self):
        current  = self.end #获取最后一节点
        if current:
            while current is not self.root:
                yield current
                current = current.prev

if __name__ == "__main__":
    link = DoubleLinkedList()
    link.append('孙悟空')
    link.append('猪八戒')
    link.append_first('唐三藏')

    for v in link:
        print(v)

    print('-'*30)

    for v in link.revers_iter():
        print(v)

链表的知识总结

Original: https://www.cnblogs.com/lxxduang/p/16562327.html
Author: 小小程序员-lian
Title: 链表的知识总结

相关阅读

Title: drf -- 版本管理类

为了方便版本管理，drf为我们提供了5个版本管理类

  • QueryParameterVersioning （将版本信息以URL参数的形式传递）
  • URLPathVersioning （将版本信息以URL路径形式传递）
  • AcceptHeaderVersioning （将版本信息以请求头的形式传递）
  • HostNameVersioning (将版本信息以域名的方式传递，几乎不用)
  • NamespaceVersioning （将版本信息以别名定义，通过分发到同一视图，可以实现，几乎不用）

1. QueryParameterVersioning

源码分析：

class QueryParameterVersioning(BaseVersioning): #如果要配置版本的参数，可以通过他的父类去查看需要配置的参数名
"""
    GET /something/?version=0.1 HTTP/1.1
    Host: example.com
    Accept: application/json
"""
    invalid_version_message = _('Invalid version in query parameter.')

    def determine_version(self, request, *args, **kwargs):
        version = request.query_params.get(self.version_param, self.default_version)
        if not self.is_allowed_version(version):
            raise exceptions.NotFound(self.invalid_version_message)
        return version

#版本管理的父类，配置的参数看该类的参数
class BaseVersioning:
    default_version = api_settings.DEFAULT_VERSION  # 如果不传入版本号，默认的版本号
    allowed_versions = api_settings.ALLOWED_VERSIONS # 仅支持的所有版本，列表的形式，如果版本号不在里面，会报错，可不配置
    version_param = api_settings.VERSION_PARAM # 版本的参数名

    def determine_version(self, request, *args, **kwargs):
        msg = '{cls}.determine_version() must be implemented.'
        raise NotImplementedError(msg.format(
            cls=self.__class__.__name__
        ))

配置文件中settings.py的配置

REST_FRAMEWORK = {
    'VERSION_PARAM':'v', #版本号的参数名，可以任意配置，不配置默认参数名为version
    'DEFAULT_VERSION':"V1",#默认的版本号，可以不配置
    "ALLOWED_VERSIONS":["v1","v2","v3"] #可以配置仅支持的版本，如果版本不在这里，会抛出异常

    #配置该类后，就不用再视图函数中声明了，不过视图函数的优先级高于配置文件
    'DEFAULT_VERSION_CLASS':"from rest_framework.versioning.QueryParameterVersioning"
}

视图函数Viwes.py代码示例：

from rest_framework.views import APIView
from rest_framework.response import Response
from rest_framework.versioning import QueryParameterVersioning

class StudentViewSet(APIView):

    versioning_class = QueryParameterVersioning

    def get(self,request,*args,**kwargs):
        print(request.version)
        return Response('ok')

路由文件urls.py的代码示例：

from django.urls import path

from student.views import StudentViewSet
urlpatterns = [
    path('info/',StudentViewSet.as_view())
]

2. URLPathVersioning

  • 用法基本与上面的类一样，只不过urls.py的写法不同
from django.urls import path

from student.views import StudentViewSet
urlpatterns = [
    # 这样的URL方式，与正则re_path方法相似，只是写法不同，url中的参数，还是会传递到 **kwargs中，
    #可以通过request.query_params获取
    # <str:version>&#x7684;&#x4E2D;&#x7684;&#x53C2;&#x6570;version&#x5FC5;&#x73B0;&#x4E0E;&#x914D;&#x7F6E;&#x6587;&#x4EF6;&#x4E00;&#x81F4;
    path('info/<str:version>/',StudentViewSet.as_view())
]
</str:version></str:version>
  • 与 URLPathVersioning 类不同，URL中不用携带
  • 配置文件中依然可以配置
  • 不过在发送请求时，需要将版本参数和版本信息以请求头的信息携带发送

示例图片：

链表的知识总结

视图函数views.py代码示例

from rest_framework.views import APIView
from rest_framework.response import Response
from rest_framework.versioning import AcceptHeaderVersioning

class StudentViewSet(APIView):

    versioning_class = AcceptHeaderVersioning

    def get(self,request,*args,**kwargs):
        print(request.version)
        return Response('ok')

Original: https://www.cnblogs.com/zhiqianggege/p/16230036.html
Author: 志强爱璇璇
Title: drf -- 版本管理类