- 浏览: 8983 次
- 性别:
- 来自: 四川
最新评论
在使用链表实现线性表是,既可以选择单链表,也可以选择双向链表,实际中的选择要依据需要实现的基本操作来决定。
在使用单链表实现线性表的时候,为了使程序更加简洁和方便,我们在单链表的最前面添加一个哑元节点,也称为头节点。在头节点中不存储任何实质的数据对象,其next指向线性表中0号元素所在的节点。头节点的引入也使线性表运算中的边界条件更容易一些。带头节点的单链表实现线性表结构图:
通过图可以暗处,对于任何基于序号的插入,删除,以及任何基于数据元素所在的节点的前后插入,删除,在带头节点的单链表中均可转换为在某个特定的节点之后完成节点的插入,删除,而不用考虑操作在连表中的头,中,尾等不同情况。
线性表的单链表实现。
在SLinkedList类中有3个成员变量,其中size表明线性表中数据元素个数,head是带头节点的单链表的首节点引用,strategy为连表中数据元素比较策略。
算法getSize(),isEmpty()时间复杂度为1,因为通过size即可判断。
类中的两个私有方法getPreNode(Object e), getPreNode(int i), 功能是找到数据元素e或线性表中i号数据元素所在的节点的前驱结点。在带头节点的单链表中插入,删除操作均在某个节点之后完成,因此线性表中的一些基于数据元素或序号的插入,删除操作依赖于对应元素所在节点的前驱结点引用。这两个方法平均运行时间n/2.
算法replace(int i, Object e),get(int i)的平均时间复杂度为n/2。由于连表中每个节点在内存中的地址不是连续的,所以链表不具有随机存取特性,这样要对线性表中i号元素进行获取或替换的操作,不可能与使用数组实现线性表那样在常数时间内完成,而是必须从链表的头节点开始沿着链表定位i号元素所在的节点,然后才进行相应的操作,比使用数组实现要慢得多。
算法contains(Object e), indexOf(e)主要是在线性表忠查找某个数据元素,算法平均时间与使用数组一样,都只能从线性表0号元素开始,依次向后查找,因此算法时间为n/2.
算法insert(int i, Object e), remove(int i)在实现的过程中首先需要在连表中定位i号元素所在的节点的前驱结点,然后才能进行插入,删除操作,由于定位方法getPreNode(Object e),getPreNode(int i)的平均时间为n/2,而真正的结点的插入与删除只需要常数时间,因此算法的运行时间为n/2,与数组实现的运行时间相同。
算法inertBefore(Object obj, Object e),insertAfter(Object obj, Object e),remove(Object e)在现实的过程中insertBefore, remove,需要找到对应元素的前驱结点,insertAfter需要找到对应的元素本身,这个定位过程品军时间为n/2,而剩下的插入与删除操作只需要常数时间,因此整个算法平均时间要比数组的n小,所以要由于使用数组。
在使用单链表实现线性表的时候,为了使程序更加简洁和方便,我们在单链表的最前面添加一个哑元节点,也称为头节点。在头节点中不存储任何实质的数据对象,其next指向线性表中0号元素所在的节点。头节点的引入也使线性表运算中的边界条件更容易一些。带头节点的单链表实现线性表结构图:
通过图可以暗处,对于任何基于序号的插入,删除,以及任何基于数据元素所在的节点的前后插入,删除,在带头节点的单链表中均可转换为在某个特定的节点之后完成节点的插入,删除,而不用考虑操作在连表中的头,中,尾等不同情况。
线性表的单链表实现。
package taxus.list; public class ListSLinked implements List { private Strategy strategy; private int size; private SLNode head;//单链表首节点引用 public ListSLinked(){ this(new DefaultStrategy()); } public ListSLinked(Strategy strategy){ this.strategy = strategy; head = new SLNode(); size = 0; } private SLNode getPreNode(Object e){ SLNode p = head; while (p.getNext() != null) { if (strategy.equal(p.getNext().getData(), e)) { return p; } else { p = p.getNext(); } } return null; } private SLNode getPreNode(int i){ SLNode p = head; for (; i > 0; i--) { p = p.getNext(); } return p; } private SLNode getNode(int i){ SLNode p = head.getNext(); for (; i > 0; i--) { p = p.getNext(); } return p; } public int getSize() { return size; } public boolean isEmpty() { return size == 0; } public boolean contains(Object e) { SLNode p = head.getNext(); while (p != null) { if (strategy.equal(p.getData(), e)) { return true; } else { p = p.getNext(); } } return false; } public int indexOf(Object e) { SLNode p = head.getNext(); int index = 0; while (p != null) { if (strategy.equal(p.getData(), e)) { return index; } else { p = p.getNext(); index++; } } return -1; } public void insert(int i, Object e) throws OutOfBoundaryException { if (i < 0 || i > size) { throw new OutOfBoundaryException("指定的插入序号越界,Size:" + size + " Index:" + i); } SLNode p = getPreNode(i); SLNode q = new SLNode(e, p.getNext()); p.setNext(q); size++; return; } public boolean insertBefore(Object obj, Object e) { SLNode p = getPreNode(obj); if (p != null) { SLNode q = new SLNode(e, p.getNext()); p.setNext(q); size++; return true; } return false; } public boolean insertAfter(Object obj, Object e) { SLNode p = head.getNext(); while (p != null) { if (strategy.equal(p.getData(), obj)) { SLNode q = new SLNode(e, p.getNext()); p.setNext(q); size++; return true; } else { p = p.getNext(); } } return false; } public Object remove(int i) throws OutOfBoundaryException { if (i < 0 || i >= size) { throw new OutOfBoundaryException("指定的删除序号越界,Size:" + size + " Index:" + i); } SLNode p = getPreNode(i); Object obj = p.getNext().getData(); p.setNext(p.getNext().getNext()); size--; return obj; } public boolean remove(Object e) { SLNode p = getPreNode(e); if (p != null) { p.setNext(p.getNext().getNext()); size--; return true; } return false; } public Object replace(int i, Object e) throws OutOfBoundaryException { if (i < 0 || i >= size){ throw new OutOfBoundaryException("指定的删除序号越界"); } SLNode p = getNode(i); Object obj = p.getData(); p.setData(e); return obj; } public Object get(int i) throws OutOfBoundaryException { if (i < 0 || i >= size) { throw new OutOfBoundaryException("指定的序号越界"); } SLNode p = getNode(i); return p.getData(); } }
在SLinkedList类中有3个成员变量,其中size表明线性表中数据元素个数,head是带头节点的单链表的首节点引用,strategy为连表中数据元素比较策略。
算法getSize(),isEmpty()时间复杂度为1,因为通过size即可判断。
类中的两个私有方法getPreNode(Object e), getPreNode(int i), 功能是找到数据元素e或线性表中i号数据元素所在的节点的前驱结点。在带头节点的单链表中插入,删除操作均在某个节点之后完成,因此线性表中的一些基于数据元素或序号的插入,删除操作依赖于对应元素所在节点的前驱结点引用。这两个方法平均运行时间n/2.
算法replace(int i, Object e),get(int i)的平均时间复杂度为n/2。由于连表中每个节点在内存中的地址不是连续的,所以链表不具有随机存取特性,这样要对线性表中i号元素进行获取或替换的操作,不可能与使用数组实现线性表那样在常数时间内完成,而是必须从链表的头节点开始沿着链表定位i号元素所在的节点,然后才进行相应的操作,比使用数组实现要慢得多。
算法contains(Object e), indexOf(e)主要是在线性表忠查找某个数据元素,算法平均时间与使用数组一样,都只能从线性表0号元素开始,依次向后查找,因此算法时间为n/2.
算法insert(int i, Object e), remove(int i)在实现的过程中首先需要在连表中定位i号元素所在的节点的前驱结点,然后才能进行插入,删除操作,由于定位方法getPreNode(Object e),getPreNode(int i)的平均时间为n/2,而真正的结点的插入与删除只需要常数时间,因此算法的运行时间为n/2,与数组实现的运行时间相同。
算法inertBefore(Object obj, Object e),insertAfter(Object obj, Object e),remove(Object e)在现实的过程中insertBefore, remove,需要找到对应元素的前驱结点,insertAfter需要找到对应的元素本身,这个定位过程品军时间为n/2,而剩下的插入与删除操作只需要常数时间,因此整个算法平均时间要比数组的n小,所以要由于使用数组。
发表评论
-
数据结构学习---队列
2014-03-18 22:24 750像栈一样,队列(queue)也是表,然而,使用队列时插入在 ... -
数据结构学习---栈
2014-03-18 22:05 738栈是限制插入和删除只能在一个位置上进行的表,该位置是表的末 ... -
数据结构学习---基于双向链表实现的链接表
2014-03-13 21:54 1613经过前面的学习,我 ... -
数据结构学习---线性表的数组实现与单链表实现比较
2014-03-02 00:18 8421. 基于时间的比较 线性表的操作主要有查询,插入,删除 ... -
数据结构学习---线性表的链式存储实现(双向链表)
2014-03-01 22:55 1294单链表的优点是结构 ... -
数据结构学习---线性表的链式存储实现(单链表)
2014-02-26 11:48 1468之前实现了线性表的数组实现方式,了解了其特性,查询很快,不 ... -
数据结构学习---线性表的数组实现LIstArray
2014-02-25 22:39 547线性表的数组实现,其内部存放数据的实际上就是一个可变容量的 ... -
数据结构学习---线性表
2014-02-25 22:15 718本人第一次发帖,只 ...
相关推荐
数据结构---线性表之单链表,包括单链表的创建、插入、删除等,C语言编写
数据结构c++ 线性表 单链表 【4】Chapter3 线性表1-顺序表及单链表
实验名称: 实验一线性表——题目1 学生姓名: 李文超 班 级: 2015661131 班内序号: 15 学 号: 2015522147 日 期: 2016年11月13日 数据结构实验报告--单链表全文共12页,当前为第2页。数据结构实验报告--单链表...
数据结构,单链表的12种操作的实现。更多详细内容请见http://blog.csdn.net/zhongkelee
链表实现线性表的基本功能,继而更进一步地去活学活用的用好这个基本数据结构,最后更好的编程续写出更完美的程序片段
(1)掌握线性表的顺序存储结构; (2)验证单链表及其基本操作的实现; (3)进一步理解算法与程序的关系,能够将单链表算法转换为对应的程序。 1.2 实验要求: (1)用头插法(或尾插法)建立带头结点的单链表; ...
数据结构-线性表-单链表的查找、插入、删除.doc
本程序的主要目的在于帮助同学熟练掌握线性表的基本操作在链式存储结构上的...通过本实验, 对链表基本操作及其组合应用的演练,加深对链表存储方法及其基本操作的理解,为以后进 一步学习更复杂的数据结构打下基础。
2008年5月8日 ... 写出将la 和lb两链表归并成一个结点按元素值非递减有序排列的单链表(其头指针为lc... 设Listhead为一单链表的头指针,单链表的每个结点由一个整数域DATA和指针域NEXT组成,整数在单链表中是无序的。
数据结构C语言版-线性表的单链表存储结构表示和实现优质资料.doc
数据结构C语言版-线性表的单链表存储结构表示和实现.doc
数据结构-第2章 线性表.ppt
鲁东大学软件工程22级数据结构实验报告代码(云班课-雷鹏) 实验一 线性表的建立与应用 要求:建立一个有n个结点的单链表,进行查询、修改、删除和插入操作
LinkList.h与LinkList.c。使用c语言实现单链表数据结构。注释详细。
数据结构C语言版,单链表操作的菜单式实验,包括单链表的初始化、创建、求表长、插入删除元素、销毁和清空单链表等操作,具体操作根据屏幕提示进行。
数据结构C语言代码--线性表
单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储...
数据结构 线性表的单链表存储结构PPT学习教案.pptx
关于线性表的Java实现代码 有顺序表,带头结点的单链表的实现代码,顺序表里包含插入,删除,求数据元素个数,取数据元素,判断非空否,以及顺序表中删除第一个出现的数据元素x,以及把顺序表中所有等于x的数据元素...