Java、Python中没有指针,怎么实现链表、图等数据结构?
程序员文章站
2023-12-22 17:38:10
...
回复内容:
我只说一下 Java :虽然没有指针,但每个变量,如果不是基本数据类型(int float 等),那么就是一个引用(reference)。引用类似指针,只是不能进行指针运算,比如 p + 1 指向下一个元素之类的。
各种语言的链表实现:
Singly-linked list/Element definition
Singly-linked list/Element insertion 实现基本的数据结构时指针唯一的作用就是指向,不涉及指针运算(pointer arithmetic)(这也不叫 const pointer),所以 Java / Python 的引用已经足够做到这一点了。就算实现 B-tree 什么的,配个数组也够了。
随手写个 Python 的链表节点,Java 的下面有人贴例子了,都是一样的道理。
需要
class Node(object):
def __init__(self, value, nextnode=None):
self.value = value
self._nextnode = nextnode
def append(self, n):
if not isinstance(n, Node):
n = Node(n)
self._nextnode, n = n, self._nextnode
self._nextnode._nextnode = n
Python里直接用dict套dict就可以表示图,graph[u][v]=w,表示从u到v的有向边,边权(或者其他需要标记的信息)为w。如果是无向图,可以限定u如果u到v有多条边,那就是dict套dict套set,graph[u][v]={w0,w1..}
如果要求存留边之间的或者节点之间的顺序关系,就把dict/set改为ordereddict。
以上做法相当于hash表示的邻接表,适合稀疏图。稠密图可以考虑用NumPy存储邻接矩阵以减小额外开销。
想看成熟的Python库怎样设计处理图的API的话,看Overview — NetworkX。 方法有很多:
- 用内置数据结构(list, dict, tuple等)的嵌套/组合,它们隐式地包含了指向/嵌套关系,如上面回答中的graph[u][v]={w0,w1..}
- 类的成员变量、嵌套类可能包含了指向/嵌套关系;
- 引用表示指向关系,只不过引用不能像指针一样运算,比如 p + 1 指向下一个元素,所以可能限制颇多。
- ...
class TreeNode:
# 类的结构已经包含了指向关系
def __init__(self, x):
self.val = x
self.left = None
self.right = None
l1 = TreeNode(0)
l2 = TreeNode(1)
l3 = TreeNode(2)
# 引用表示指向关系
l1.left = l2
l1.right = l3
这个可以怒答一发,因为刚用java实现了一下链表,这里针对java和链表,python不发表意见首先,楼上的大大们都说了,引用差不多是受限的指针,完全可以实现指针的功能
先上节点的代码
private class Node {
public Node next;
public T data;
public Node(T d,Node n) {data = d; next = n;}
}
java的引用就不说了,python里所有的变量其实都是对象的引用(连基本类型都是如此),而这个引用,说白了就是个指向实例的指针。所以并不是没有指针,而是全都是指针只不过你看不出来而已。
做链表当然可以,对于python而言就一个类里两个属性,next仍旧是next,指向下个节点的实例就可以了。 Python和Java的“引用”就是不能运算的指针。
其实我更喜欢go语言的理念,没有任何“引用”,所以就避免了混淆的“传引用”概念。所有的值传递都是传值,指针就是指针,但是不能运算。 其实Java, python完全可以看成在语言层用语法糖隐藏了指针。
Java中,假设class A有 属性 int a, B(class B) b,那A实例化(b在A实例化新开辟而不是通过外部赋值),内存开辟一段包含一个int a和 一个b 的reference地址,b实例化和A一样,然后把地址抛给A中b的reference。其实这个和C/C++中的A中有个B* b差不多。所以链表、图等数据结构在C/C++中的实现转义到Java中也就是改改语法糖的表示。
Python中,链表、树等数据结构大致对应Python自带list、tuple、dict。Python这种动态语言用C实现,拿Python的list来讲,用一个struct PyListObject 实现,看看源码指针随处都是。
C/C++这样的语言比较接近早期抽象计算机数据的思维方式,指针其实就是我们抽象数据并且这个数据是聚合但是实际内存离散的胶合层产物。后来出的语言通过其他的方式来抽象数据表示,将指针这个概念隐藏了,显得友好了,但是其实他还在那。 基本上没有指针会有更灵活的方式进行,回收机制直接丢弃可以自动释放内存,写起来也简单,一码胜千言,贴张python的简单链表实现:
# -*- coding: utf-8 -*-
class Node(object):
def __init__(self, datum, next):
self.__datum = datum
self.__next = next
@property
def datum(self):
return self.__datum
@property
def next(self):
return self.__next
@next.setter
def next(self, next):
self.__next = next
class LinkedList(object):
def __init__(self):
self.__head = None
self.__tail = None
@property
def head(self):
return self.__head
@property
def tail(self):
return self.__tail
def purge(self):
self.__head = None
self.__tail = None
def is_empty(self):
return self.__head is None
def append(self, item):
#Generates the node.
datum = Node(item, None)
#For the first node in a linked list, it will change the head.
if self.__head is None:
self.__head = datum
else:
self.__tail.next = datum
self.__tail = datum
def remove(self, item):
pointer = self.__head
prepointer = None
#Finds the item
while pointer and pointer.datum != item:
prepointer = pointer
pointer = pointer.next
#Raise the error when not finding the item.
if pointer is None: raise KeyError
#When the linked list has one node, it will sets the head.
if pointer == self.__head:
self.__head = pointer.next
else:
prepointer.next = pointer.next
if pointer == self.__tail:
self.__tail = prepointer
其实完全不用指针也可以实现这种结构。参见:cons
声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。
相关文章
相关视频
专题推荐
-
独孤九贱-php全栈开发教程
全栈 170W+
主讲:Peter-Zhu 轻松幽默、简短易学,非常适合PHP学习入门
-
玉女心经-web前端开发教程
入门 80W+
主讲:灭绝师太 由浅入深、明快简洁,非常适合前端学习入门
-
天龙八部-实战开发教程
实战 120W+
主讲:西门大官人 思路清晰、严谨规范,适合有一定web编程基础学习
网友评论
文明上网理性发言,请遵守 新闻评论服务协议
我要评论