专栏首页python3python实现单链表

python实现单链表

#encoding:utf-8

import sys

class Lnode():
    def __init__(self,elem,next=None):
        self.elem = elem    #节点的值
        self.next = next    #指向下一个节点
    def getelem(self):
        return self.elem
    def getnext(self):
        return self.next

class linklist(object):
    def __init__(self):
        L = Lnode(None,None)
        self.head = L       #定义头节点
        self.length = 0     #链表元素个数
    # 链表是否为空
    def isempty(self):
        if self.head.next is None:
            return True
        else:
            return False
    def getlength(self):
        return self.length

    #尾部添加
    def append(self,elem):
        newNode = Lnode(elem)
        if self.head.next is None:
            self.head.next = newNode
        else:
            p = self.head
            while p.next is not None:
                p = p.next
            p.next = newNode
        self.length += 1

    #头部添加
    def headpush(self,elem):
        newNode = Lnode(elem)
        if self.isempty():
            self.head.next = newNode
        else:
            newNode.next = self.head.next
            self.head.next = newNode
        self.length += 1


    #在指定元素的位置后面插入
    def insertafter(self,elem,newelem):
        newNode = Lnode(newelem)
        if self.find(elem) == -1:
            print "%s in the link list" %elem
            return -1
        else:
            #如果在链表中找到元素elem
            p = self.find(elem)
            if p.next is None:
                p.next = newNode
            else:
                newNode.next = p.next
                p.next = newNode
            self.length += 1

    # 在指定元素的位置前面插入
    def insertbefor(self,elem,newelem):
        newNode = Lnode(newelem)
        if self.find(elem) == -1:
            print "%s in not the link list" % elem
            return -1
        else:
            p = self.head
            q = self.find(elem)
            while p is not None:
                if p.next == q:
                    break
                p = p.next
            newNode.next = q
            p.next = newNode
            self.length += 1


    #遍历链表
    def for_each(self):
        if self.head.next is None:
            print "empty"
            return
        else:
            p = self.head
            while p.next is not None:
                p = p.next
                sys.stdout.write("%s " %(p.elem))
            print
            return

    #查找元素,返回指向该元素的节点
    def find(self,elem):
        #找到元素返回节点,未找到返回-1
        if self.isempty():
            print "sorry,is empty"
            return -1
        else:
            p = self.head
            while p is not None:
                if p.elem == elem:
                    return p
                else:
                    p = p.next
            return -1
    #修改指定元素
    def modify(self,elem,newelem):
        if self.find(elem) != -1:
            #如果找到
            p = self.find(elem)
            p.elem = newelem
            return 0
        else:
            print "%s is not in the linklist" %elem
            return -1
    #删除指定元素
    def delnode(self,elem):
        if self.find(elem) != -1:
            #如果找到
            p = self.find(elem)
            q = self.head
            while q.next != p:
                q = q.next
            q.next = p.next
            p.next = None

        else:
            print "%s is not in the linklist" %elem
            return -1

def main():

    #创建链表
    ll = linklist()
    print ll.isempty()
    #尾部添加元素
    ll.append(3)
    ll.append(4)
    ll.append(5)
    ll.for_each()
    print ll.getlength()

    #首部添加元素
    ll.headpush(2)
    ll.for_each()
    print ll.getlength()

    #查找元素
    print ll.find(3).elem
    ll.insertafter(3,3.3)
    ll.for_each()
    print ll.getlength()

    #测试后插法
    ll.insertafter(1,1.1)

    #测试前插法
    ll.insertbefor(5,3.9)
    ll.for_each()
    print ll.getlength()

    #修改指定元素
    ll.modify(3.9,44)
    ll.for_each()

    ll.modify(3.8,88)

    #删除指定元素
    ll.delnode(3.3)
    ll.for_each()
    ll.delnode(2)
    ll.delnode(2)
    ll.delnode(3)
    ll.delnode(4)
    ll.delnode(44)
    ll.delnode(5)


    ll.for_each()




if __name__ == '__main__':
    main()

运行结果

True

3 4 5 

3

2 3 4 5 

4

3

2 3 3.3 4 5 

5

1 in the link list

2 3 3.3 4 3.9 5 

6

2 3 3.3 4 44 5 

3.8 is not in the linklist

2 3 4 44 5 

2 is not in the linklist

empty

Process finished with exit code 0

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 链表的创建与基本操作(Python版)

    py3study
  • 局部敏感哈希(原始LSH)python实

    最近短期计划是学习一下Python,最好的学习方式当然是实践了,今天用Python实现了下lsh算法,代码比较简陋。。。(2016.1.17)

    py3study
  • Python3结合Sciter编写桌面

    但由于是同一个进程,如果你做了很耗时的操作,比如下载一张图片之类的IO操作......

    py3study
  • 局部敏感哈希(原始LSH)python实

    最近短期计划是学习一下Python,最好的学习方式当然是实践了,今天用Python实现了下lsh算法,代码比较简陋。。。(2016.1.17)

    py3study
  • 用Python实现OpenCV特征提取与图像检索 | Demo

    “拍立淘”“一键识花”“街景匹配”……不知道大家在使用这些神奇的功能的时候,有没有好奇过它们背后的技术原理?其实这些技术都离不开最基本的图像检索技术。本篇文章我...

    AI科技大本营
  • 绘图-简单手绘板的实现

    自定义一个UIBezierPath的子类 LGPaintpath,下面是它的初始化方法

    進无尽
  • 朴素贝叶斯算法及其Python实现

    中文名比较好听,叫朴素贝叶斯,英文叫Naive Bayes,Naive是什么意思大家都知道,朴素贝叶斯的朴素就体现在它假设所有的属性(即特征)之间相互独立,这一...

    带萝卜
  • TensorFlow 学前班

    本文我参加Udacity的深度学习基石课程的学习的第3周总结,主题是在学习 TensorFlow 之前,先自己做一个miniflow,通过本周的学习,对于Te...

    zhuanxu
  • OpenCV特征提取与图像检索实现(附代码)

    翻译 | AI科技大本营 参与 | 张蔚敏 审校 | reason_W “拍立淘”“一键识花”“街景匹配”……不知道大家在使用这些神奇的功能的时候,有没有好奇过...

    AI科技大本营
  • 为什么要指令重排序?

    我们知道java在运行的时候有两个地方可能用到重排序,一个是编译器编译的的时候,一个是处理器运行的时候。

    MageekChiu

扫码关注云+社区

领取腾讯云代金券