`
hjj20040849
  • 浏览: 115204 次
  • 来自: 广州
社区版块
存档分类
最新评论

线性表的链式存储结构(java版)

阅读更多

在前面,我们已经讲了线性表的顺序存储结构(java版) ,我们也知道了他的代码实现,在了解之后,我们很容易就能够发现他有一个最大的缺点,就是插入和删除需要移动大量的元素,这显然是很耗费时间的,于是,为了解决这个问题,就出现了链式存储结构。

 

我学习的时候是看程杰的《大话数据结构》的,同时结合我们的经典教材清华出版社的《数据结构》,但是在学习过程中,我不小心把“插入到第i个位置之后”理解成了“插入到第i个位置”,所以我后面的程序跟书上的范例有些不一样,但是万变不离其宗,它运用的始终是我们的数据结构——线性表的链式存储结构。

 

由于理解错了课本的一些意思,所以代码显得更复杂了一点点,好吧,言归正传,继续讲我们代码是如何实现的。

 

第一步,定义一个接口,其实这个接口跟前面顺序存储结构的接口定义是一样的,后面我只是改了下名字和重新更换了包名而已,但这不影响我们的代码:

package com.stucture.list;

/**
 * 线性表顺序存储结构的接口
 * 指的是用一段地址连续的存储单元一次存储线性表的数据元素
 * @ClassName: ISqList 
 * @author 小学徒
 * @date 2013-2-27
 */
public interface IList<T> {
	
	/**
	 * 获得元素
	 * @param loc 需要获得的第loc个元素
	 * @return 
	 */
	public T getElem(int loc);
	

	/**
	 * 插入元素
	 * @param loc 元素的插入位置
	 * @param t 需要插入的元素
	 * @return  是否成功插入
	 */
	public boolean insertElem(int loc, T t);
	
	/**
	 * 删除元素
	 * @param i 需要删除元素的位置
	 * @return
	 */
	public T deleteElem(int i);
}

 

第二步,定义我们的节点类:

package com.stucture.list.linkList;

/**
 * 链表中的结点
 * @ClassName: Node 
 * @author 小学徒
 * @date 2013-2-27
 */
public class Node<T> {
	private T data;       //需要存储的数据信息
	private Node<T> next; //后继
	
	public T getData() {
		return data;
	}
	public void setData(T data) {
		this.data = data;
	}
	public Node<T> getNext() {
		return next;
	}
	public void setNext(Node<T> next) {
		this.next = next;
	}
	
	
}

 

第三步,定义我们的链表及其基本操作,代码如下:

package com.stucture.list.linkList;

import com.stucture.list.IList;

/**
 * 单链表
 * @ClassName: LinkList 
 * @author 小学徒
 * @date 2013-2-27
 */
public class LinkList<T> implements IList<T>{
	private Node<T> head;	//链表的结点
	private int length;	//链表的长度
	
	public LinkList(Node<T> head) {
		this.head = head;
	}
	//获取元素
	public T getElem(int loc) {
		int j = 1;	//计数器
		Node<T> n = head;	//指向第一个结点
		
		while(n != null) {	//n不为空时,循环继续寻找第loc个结点
			if(j == loc) {	//找到第一个元素时返回
				return n.getData();
			}
			n = n.getNext();
			j++;
			
		}
		return null;
	}

	//插入元素
	public boolean insertElem(int loc, T t) {
		if(length + 1 < loc) {
			System.out.println("非法插入");
			return false;
		}
		if(head == null && loc == 1) {	//当第一次插入的时候
			head = new Node<T>();	//第一次使用,必须创建对象
			head.setData(t);
			length++;
		} else if(head != null && loc == 1) {	//但不是第一次插入,但是插入的位置是第一个时
			Node<T> tempNode = new Node<T>();	//生成一个新的结点
			tempNode.setData(t);
			tempNode.setNext(head);	
			head = tempNode;	//把头换成新插入的结点
			length++;
		} else {	//当不是第一次插入并且插入的不是第一个时
			Node<T> n = this.head;
			int j = 1;	//计数器
			while(n != null && j < loc - 1) {
				n = n.getNext();
				j++;
			}
			Node<T> tempNode = new Node<T>();	//生成一个新的结点
			tempNode.setData(t);
			tempNode.setNext(n.getNext());	//将n的后继结点赋值给新的结点的后继
			n.setNext(tempNode);
			length++;
		}
		return true;
	}

	//删除元素
	public T deleteElem(int loc) {
		if(head == null || loc > length) {
			System.out.println("非法删除");
			return null;
		}
		T old;
		if(head != null && loc == 1) {
			old = head.getData();
			head = head.getNext();
			
		} else {
			Node<T> n = this.head;
			int j = 1;	//计数器
			while(n != null && j < loc - 1) {
				n = n.getNext();
				j++;
			}
			old = n.getNext().getData();
			n.setNext(n.getNext().getNext());
		}
		length--;
		return old;
	}

	
	public Node<T> getHead() {
		return head;
	}

	public void setHead(Node<T> head) {
		this.head = head;
	}

	public int getLength() {
		return length;
	}

	public void setLength(int length) {
		this.length = length;
	}
	
}

 

第四步,我们下面就写一个比较完善的代码测试,在下面的代码中,我是通过随机数来生成一些必要的数据来测试的,只要多运行几遍,还是能够测试比较完善的,不过封装的可能有点不太好,如果读者看了以后有什么更好的建议,还希望能够指出,当然因为该链式存储结构和顺序存储结构都是同一个接口的实现,所以测试方法是可以一样的,只是把实现类转换了而已。但是由于时间问题,我就没有去修改了,有兴趣的读者可以自行修改,有问题的可以在此留言共同讨论共同进步,我有空的时候也会更改并上传到博客的,下面继续代码:

package com.stucture.list.linkList;

import java.util.Random;

public class LinkListTest {
	final int MAX = 25;
	Random r = new Random();
	LinkList<Integer> linkList;
	
	public LinkListTest() {
		initSeqList();
	}
	
	//创建一个线性表顺序存储结构
	public void initSeqList() {
		linkList = new LinkList<Integer>(null);
		int length = Math.abs(r.nextInt(MAX));	//使用Random随机产生一个25左右的值,使用Math.abs()函数来取绝对值	
		System.out.println("产生的链表长度为 :" + length);
		
		for (int i = 1; i <= length; i++) {	//为生成的链表赋值,同时也测试了插入值的方法
			int j =r.nextInt(MAX);
			System.out.print(j + " ");
			
			if(!linkList.insertElem(i, j)) {
				System.exit(0);	
			}
		}
		System.out.println("\n原始链表是 :");
		display(linkList);
	}
	
	//测试删除方法
	public void deleteElem() {
		int i = r.nextInt(MAX);
		System.out.println("\n\n删除的位置是:" + i);
		Integer deleteNumber = linkList.deleteElem(i);
		
		if( deleteNumber == null) {
			System.exit(0);
		} else {
			System.out.println("删除的元素是 : " + deleteNumber);
			System.out.println("删除元素后链表是 :");
			display(linkList);
		}
	}
	
	//测试随机插入方法
	public void insertByRandom() {
		int i = r.nextInt(MAX);
		System.out.println("\n\n随机插入位置是 :" + i);
		int elem = r.nextInt(MAX);
		System.out.println("随机插入数据是 :" + elem);
		linkList.insertElem(i, elem);
		System.out.println("随机插入数据后链表是 :");
		display(linkList);
	}
	
	//数据展示
	public  void display(LinkList<Integer> linkList) {
		Node<Integer> node = linkList.getHead();
		while(node != null) {
			System.out.print(node.getData() + " ");
			node = node.getNext();
		}
		System.out.println("链表的长度为 :" + linkList.getLength());
	}
	
	//获取元素
	public void getElem() {
		int i = r.nextInt(MAX);
		System.out.println("\n获取位置为 :" + i);
		System.out.println("获取到的元素为 : " + linkList.getElem(i));
		
		
	}
	
	public static void main(String[] args) {
		LinkListTest s = new LinkListTest();
		s.insertByRandom();
		s.deleteElem();
		s.getElem();
	}
}

 

 运行结果同样我不一一把各种结果列出啦,读者可以自己运行多几遍来进行学习:

产生的链表长度为 :23
5 19 18 12 6 12 15 19 16 21 13 16 5 4 18 9 9 18 17 13 16 6 17 
原始链表是 :
5 19 18 12 6 12 15 19 16 21 13 16 5 4 18 9 9 18 17 13 16 6 17 链表的长度为 :23


随机插入位置是 :24
随机插入数据是 :0
随机插入数据后链表是 :
5 19 18 12 6 12 15 19 16 21 13 16 5 4 18 9 9 18 17 13 16 6 17 0 链表的长度为 :24


删除的位置是:11
删除的元素是 : 13
删除元素后链表是 :
5 19 18 12 6 12 15 19 16 21 16 5 4 18 9 9 18 17 13 16 6 17 0 链表的长度为 :23

获取位置为 :12
5 19 18 12 6 12 15 19 16 21 16 5 获取到的元素为 : 5

 

0
0
分享到:
评论

相关推荐

    链式线性表的java实现

    链式存储结构线性表的java实现,全代码注释,通俗易懂

    线性表的存储结构与顺序表的存储实现共4页.pdf.zip

    在实际应用中,线性表的存储结构通常有两种主要形式:顺序存储结构和链式存储结构。 顺序存储结构是将线性表中的元素按其逻辑顺序依次存放在一片连续的内存区域中,这种存储方式使得数据访问变得简单且高效。顺序表...

    基于链式存储结构的线性表实现.rar_Table_cameramjx_data structure

    在"Table_cameramjx_data structure"这个主题中,我们可能会看到如何使用C++或Java等编程语言实现这些链式存储结构,并讨论它们在实际问题中的应用,如数据缓存、队列、栈等。通过这个资源,学习者可以深入理解链式...

    线性表实现源码-java

    二、单向链式存储结构 1. 链表节点:在链式存储中,每个元素(节点)包含两部分:数据域和指针域。数据域存储实际元素,指针域指向下一个节点。Java中,可以定义一个Node类来表示链表节点,包含一个数据字段和一个...

    线性表的链式存储与实现

    总的来说,链式存储的线性表是一种灵活且高效的数据结构,尤其适用于频繁进行插入和删除操作的情况。通过理解和熟练掌握链式存储线性表的实现,可以为解决许多实际问题打下坚实的基础。在实际编程中,我们可以结合...

    java基础数据结构-线性表

    2. **链式存储结构**:通过节点之间的指针连接来表示线性表。每个节点包含数据域和指向下一个节点的指针。这种方式插入和删除操作较快,但访问速度较慢。 #### 三、线性表的基本操作 线性表的一些常见操作包括: -...

    JAVA线性表JAVA线性表JAVA线性表

    链式存储结构的特点是每个节点包含数据和指向下一个节点的引用,使得元素的位置可以不连续,从而避免了插入和删除时的元素移动。 **2.3.2 单链表** 单链表的遍历、插入和删除操作如下: - **遍历**:从头节点开始,...

    java线性表的存储结构及其代码实现

    Java 线性表是一种基本的数据结构,它的存储结构可以分为顺序存储结构和链式存储结构两种。在 Java 中,ArrayList 类就是线性表的数组实现。下面是 Java 线性表的存储结构和代码实现。 一、顺序存储结构 顺序存储...

    漫话数据结构-线性表的链式存储.pptx

    线性表的链式存储是相对于顺序存储的一种方式,尤其适用于动态变化的数据集合。 在链式存储中,线性表的数据元素并不必须存储在连续的内存位置,而是通过链接的方式将它们串联起来。具体来说,单链表是最基本的形式...

    自定义顺序存储结构线性表--java语言描述

    在编程领域,线性表是一种基础且重要的数据结构,它由有限个相同类型元素组成,元素之间存在一对一的关系。...此外,还可以考虑实现其他线性表结构,如链式存储结构,以对比和理解不同数据结构的优势和适用场景。

    线性表链式存储结构基本操作

    链式存储结构不依赖于内存中的连续空间,而是通过节点之间的链接来组织数据。 链表是一种动态数据结构,每个节点包含两部分:数据域和指针域。数据域用于存储元素,而指针域则指向下一个节点,最后一个节点的指针域...

    线性表,单链表,栈 java实现

    **单链表** 是线性表的一种链式存储结构,每个节点包含两部分:数据域和指针域。数据域用于存储数据,指针域指向下一个节点。单链表的优点在于插入和删除操作只需改变相邻节点的指针,时间复杂度为O(1)。但查找操作...

    数据结构链式线性表以及顺序线性表

    在数据结构领域,我们通常会根据存储方式的不同将其分为两种主要类型:顺序线性表和链式线性表。 **顺序线性表**是一种在内存中连续存储的数据结构,每个元素都有一个唯一的索引位置,索引从0开始。例如,如果一个...

    数据结构实验线性表实验报告(代码是java编写的)

    线性表是一种逻辑结构,其中的数据元素按照线性顺序排列,可以通过顺序存储或链式存储来实现。 1. **顺序表**:顺序表是用一组地址连续的存储单元依次存储线性表中的元素。在本次实验中,我们创建了一个数组 A[N] ...

    线性表JavaPPT学习教案.pptx

    线性表有两种常见的存储结构:顺序存储结构和链式存储结构。顺序存储结构使用一维数组实现,元素的逻辑顺序与物理顺序一致,这使得随机访问元素(get和set操作)非常高效,时间复杂度为O(1)。然而,插入和删除操作...

    数据结构线性表的操作

    线性表的两种常见存储方式是顺序存储和链式存储。顺序存储将元素存储在一块连续的内存空间中,通常使用数组实现,访问速度快,但插入和删除操作可能涉及到大量的元素移动。链式存储则通过指针连接元素,插入和删除...

    数据结构线性表课件郑州大学

    2.1.3 线性表的链式存储结构: 链式存储结构不依赖于元素在内存中的物理顺序,而是通过指针链接元素。单链表和双链表是两种常见的链式存储方式,其中单链表每个节点包含数据和指向下一个节点的引用,双链表还包含...

    线性表分析及Java实现.doc

    线性表的存储结构主要有两种:顺序存储结构和链式存储结构。顺序表使用数组来存储元素,优点是查询速度快,但插入和删除操作可能导致大量元素的移动。链表则通过节点之间的链接来表示元素顺序,插入和删除操作相对...

    附课后题答案-习题解答与实验指导 数据结构(java版).doc

    * 双链表是指每个节点有两个指针,一个指向下一个节点,一个指向上一个节点的链式存储结构。 * 双链表的基本操作包括插入、删除、查找和遍历等。 * 双链表的应用包括快速查找、插入和删除等。 习题 * 使用单链表...

    [详细完整版]数据结构类型.pdf

    链式存储结构,每个节点包含数据和指向下一个节点的指针,允许动态调整,插入和删除操作更灵活,但存储密度低且查找速度相对较慢。 索引存储结构,如数据库中的索引,建立额外的索引表来快速定位元素,适用于大规模...

Global site tag (gtag.js) - Google Analytics