上次单链表中有个问题,就是remove 方法有误,在这里已经修正了,下面是双链表的实现。其实,双链表已比较简单,就是在存储节点中加上一个指向上个节点的引用(呵呵,这好像是java的术语) 具体代码如下:
# -*- coding: cp936 -*- #--------------------------------------------- # #author chile #version 1.0 #since #date #desc 双链表 # # # #--------------------------------------------- class DoubleLinkList: def __init__(self): self.root = DoubleLinkList.Entry() self.entry = self.root self.list = list() self.tally = 0 #新增的数据都是插入在尾部 def add(self,value): temp = self.Entry(pre = self.entry,value = value) self.entry.next = temp self.entry = temp self.tally += 1 #在头部添加 def addFirst(self,value): entry = self.root.next temp = self.Entry(pre = self.root , next = entry,value = value) self.root.next = temp self.tally += 1 def get(self,index): if index > self.tally or index < 0: return #其实应该抛出异常 mid = self.tally / 2 e = self.root.next if index < mid: for i in range(index): e = e.next else: for i in range(self.tally): if (i == index): break e = e.next return e.value def getLast(self): return self.entry.value def getFirst(self): return self.root.next.value def remove(self,value): e = self.root.next self.removeEntry(self.root,e, value) if self.isRemove: self.tally -= 1 def removeEntry(self,pre,current,value): self.isRemove = False if current == None: self.isRemove = False return if current.value == value: pre.next = current.next self.isRemove = True else: self.removeEntry(current,current.next, value) def removeFirst(self): root = self.root entry = root.next; root.next = entry.next entry.next.pre = root self.tally -= 1 def size(self): return self.tally def all(self): self.list = list() self.iterator(self.root.next) return self.list def iterator(self,entry): if entry != None: self.list.append(entry.value) self.iterator(entry.next) #内部类 用于存放节点的值,以及下个点的引用 class Entry: def __init__(self, pre = None , next = None , value = None): self.next = next #下一个节点 self.pre = pre #上一个节点 self.value = value #节点存储的值 link = DoubleLinkList() link.add(1) link.add(2) link.addFirst(3) link.add(5) link.add(4) link.add(7) link.remove(5) print link.all(), link.size() link.addFirst(5) print link.all(), link.size() link.removeFirst() print link.all(), link.size() print link.getFirst() , link.getLast() , link.get(3)
水平有限哈,写的比较简单。如果有什么问题,请指正。希望和有兴趣的共同交流。
相关推荐
http://msdn.microsoft.com/en-us/library/95z04bas(v=VS.71).aspx 双向链表
双向链表
双向链表的操作问题 Time Limit: 1000MS Memory Limit: 10000KB Submissions: 111 Accepted: 41 Description 建立一个长度为n的带头结点的双向链表,使得该链表中的数据元素递增有序排列。(必须使用双向链表完成...
数据结构的双链表算法:双链表基本运算插入前插入后,循环双链表的基本运算。用C++语言写的控制台程序。
定义、实现并测试一个双向链表结点类DNode。 链表结点类中包含私有数据成员为两个整数x,y以及左结点指针left及右结点指针right。 包含的函数成员包括: (a)对结点的数据成员赋值setDNodeValues(int,int,DNode* ...
详细的介绍了Linux内核中使用的最频繁的双向链表
双向链表类定义及测试文件 对应于数据机构与算法分析(c++版)第三版或第二版 Clifford A.Shaffer 重庆大学使用教材
创建空的双向链表; 逐字符读取键盘输入的合法字符串,并依次插入到双向链表中。具体的,对于当前读取的字符, 构造其对应的结点。 利用头插法(或尾插法)将该结点按照键盘输入的顺序插入到双向链表中。 3、...
一种支持类模版和函数模版的C++双向链表,实现了各种排序算法(排序原则可定制),包含学生信息的使用示例(VC 6.0、VS2008).
文档包括带表头单链表的实现,双链表的操作,双链表的冒泡排序,不带表头的单链表,双向链表、链表节点的排序
用模板类实现了一个简单的双向链表domo。
实现双向链表的增删改查功能,dos窗口输入输出,可运行,有注释
C 语言版 双向链表 #include #include typedef struct list { int date; struct list *llink; struct list *rlink; }st; st *creat () //创建双向链表 { st *head , *p , *q; head = q = p = NULL; int ...
java实现双链表模拟集合练习题
操作系统c++编程实现安全型双向链表,线程的创建,利用线程对链表进行增删改操作,并检验结果是否正确
原创手操,操作系统课设,线程安全的双向链表,VC6.0,无须配置,可运行
编写使用freelist 的带头、尾结点的双向链表类的定义,实现双向链表的基本操作。 2. 利用双向链表实现2个一元多项式的加法和乘法运算,运算结果得到的链表要求按照指数降序排列的多项式。 3. 最后提交完整的...
基于linkedList实现自己的双向链表反转。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。...
通过建立双向链表,来实现双向查找,增加和删除的功能
双向链表是一种比较常用的数据结构,在许多场合都有应用。但是,双向链表的节点操作,对于初学者来说或许显得比较繁琐。尤其是,当用链表描述不同的数据结构时,节点结构体的定义都是不同的,这就需要为每一种链表都...