文档章节

JAVA数据结构 线性表的链式存储及其实现

狂奔啦蜗牛
 狂奔啦蜗牛
发布于 2012/08/26 19:40
字数 814
阅读 313
收藏 0

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

2线性表的链式存储及其实现

虽然顺序表具有随机存取的特点是一种有用的存储结构但是也有缺陷:

(1)      若需要给顺序表增加存储空间首先必须开辟一个更大的存储空间然后把数据复制到现在这个表当中

(2)      因为顺序表的数据元素在存储结构上相邻素要删除元素就要移动平均一半的数据元素

所以顺序表适合静态的线性表,表一旦形成就很少进行插入操作,对于要进行平凡的插入或者删除操作的“动态的”线性表通常采用链式存储结构,与此同时链式存储结构也失去了可随机存取的优点,链式结构只能进行顺序存取。

统一接口如下:

/*
 * Kiss_My_Love
 * 2012/8/26
 * xaut.media082
 * */
package www.xaut.com.linkedlist;

public interface Ilist {
	public void clear();
	public boolean isEmpty();
	public int length();
	public Object get(int i);
	public void insert(int i,Object x);
	public void remove(int i);
	public int indexOf(Object x);
	public void display();
}

2.1单链表的表示

data

next

节点有数据和指针构成

2.1.1节点类的描述

/*
 * Kiss_My_Love
 * xaut
 * 2012/8/26
 * */
package www.xaut.com.linkedlist;

public class Node {
		private Object data;
		private Node next;
		
		public Node(){
			this.data=null;
			this.next=null;
		}
		public Node(Object data){
			this.data=data;
			this.next=null;
		}
		public Node(Object data,Node next){
			this.data=data;
			this.next=next;
		}
		
		public Object getData() {
			return data;
		}
		public void setData(Object data) {
			this.data = data;
		}
		public Node getNext() {
			return next;
		}
		public void setNext(Node next) {
			this.next = next;
		}
		
}


2.1.2单链表类的描述:

/*
 * Kiss_My_Love
 * xaut
 * 2012/8/26
 * */
package www.xaut.com.linkedlist;

import java.util.Scanner;

public class LinkedList implements Ilist {

	private Node head;
	public LinkedList(){//初始化头结点
		head=new Node();
	}
	public LinkedList(int n,boolean Order){//初始化头结点
		this();
		if(Order)
			create1(n);
		else 
			create2(n);
	}
	//尾插法建立单链表
	public void create1(int n){
		Scanner sc=new Scanner(System.in);
		for(int j=0;j<n;j++){
			insert(this.length(),sc.next());
		}
	} 
	//头插法建立单链表
    public void create2(int n){
    	Scanner sc=new Scanner(System.in);
    	for(int j=0;j<n;j++){
			insert(0,sc.next());
		}
	}
	public void clear() {
			head.setData(null);
			head.setNext(null);

	}

	@Override
	public boolean isEmpty() {
		return head.getNext()==null;
	}

	@Override
	public int length() {
		int length=0;
		Node p=head.getNext();
		while(p!=null){
			length++;
			p=p.getNext();
		}
		return length;
	}

	@Override
	public Object get(int i) {
		Node p=head.getNext();
		//i的合法性
		if(i<0||p==null){
			try {
				throw new Exception("第"+i+"个数据元素不从在");
			} catch (Exception e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
	
		for(int j=0;j<i&&p!=null;j++){
			p=p.getNext();
		}
		return p.getData();
	}

	@Override
	//在第i个数据元素之前插入
	public void insert(int i, Object x) {
		Node q=new Node (x);
		int j=-1;
		//判断I的合法性
		Node p=head;
		if(j>i-1||p==null){
			try {
				throw new Exception("插入位置不合法");
			} catch (Exception e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		for(;j<i-1;j++){
			p=p.getNext();
		}
		q.setNext(p.getNext());
		p.setNext(q);
	}
        //删除掉第i个数据元素 
	public void remove(int i) {
		Node p=head;
		for(int j=-1;j<i-1&&p!=null;j++){
			p=p.getNext();
		}
		p.setNext(p.getNext().getNext());
	}

	@Override
	public int indexOf(Object x) {
		Node p=head.getNext();
		int j=0;
		while(p!=null&&!p.getData().equals(x)){
			p=p.getNext();
			++j;
		}
		if(p!=null){
			return j;
		}else
			return -1;
	
	}

	@Override
	public void display() {
		Node p=head.getNext();
		while(p!=null){
			System.out.print(p.getData()+"  ");
			p=p.getNext();
		}
		System.out.println();

	}

}


         由于单链表 只需要一个头指针就能唯一标识它所以单链表的成员变量只需设置一个头指针即可

测试类

/*
 * Kiss_My_Love
 * xaut
 * 2012/8/26
 * */
package www.xaut.com.linkedlist;

public class TestLinkedList {


	public static void main(String[] args) {
		int n=10;
		LinkedList L=new LinkedList();
		for(int i=0;i<n;i++){
			L.insert(i, i);
		}
		L.display();
		System.out.println(L.length());
		System.out.println(L.get(5));
		L.remove(5);
		L.display();
		System.out.println(L.indexOf(9));

	}

}


© 著作权归作者所有

狂奔啦蜗牛
粉丝 8
博文 17
码字总数 15025
作品 0
西安
程序员
私信 提问
加载中

评论(1)

Winnie007
Winnie007
6
数据结构(java版)学习笔记(一)——线性表

一、线性表的定义 线性表是n(n>=0)个具有相同特性的数据元素的有限序列。 线性表是最简单、最常用的一种数据结构 线性表属于线性结构的一种 如果一个数据元素序列满足: (1)除第一个和最...

Stars-one
2018/07/29
0
0
第一阶段:Java内功秘籍-线性表

前言 为什么要学习数据结构与算法,如果你学会了做安卓,javaweb,前端等,都是你的武功秘籍,但是如果你的内功不够好,再厉害的功夫也是白费。 数据结构和算法:什么是数据结构,什么是数据...

达叔小生
2018/08/06
0
0
Java 描述数据结构之链表的增删改查

链表是一种常见的基础数据结构,它是一种线性表,但在内存中它并不是顺序存储的,它是以链式进行存储的,每一个节点里存放的是下一个节点的“指针”。在Java中的数据分为引用数据类型和基础数...

码农UP2U
11/06
0
0
java数组、集合和数据结构知识*

一、数据结构知识。数据结构分为逻辑结构和物理结构,下面是百度百科的数据结构知识。 数据的逻辑结构:指反映数据元素之间的逻辑关系的数据结构,其中的逻辑关系是指数据元素之间的前后件关...

cjun1990
2015/06/27
72
0
JAVA数据结构的个人见解之绪论

JAVA数据结构的个人见解之绪论 概念 一般来说用计算机解决问题总是围绕以下三个主要步骤: (1) 抽象出所求解问题中需要处理的数据对象的逻辑模型。(逻辑结构) (2) 根据所求解问题需要完...

狂奔啦蜗牛
2012/08/23
182
0

没有更多内容

加载失败,请刷新页面

加载更多

阿里云视频云正式支持AV1编码格式 为视频编码服务降本提效

今天我们要说的 AV1 可不是我们平时说的 .AVI 文件格式,它是由AOM(Alliance for Open Media,开放媒体联盟)制定的一个开源、免版权费的视频编码格式,可以解决H.265昂贵的专利费用和复杂的...

一肥仔
24分钟前
8
0
软件缺陷静态分析 CodeSonar 5.2 新版发布

对于使用C和C++构建安全关键软件的开发团队而言,CodeSonar一直是首选的静态分析解决方案。在近期发行的版本中,CodeSonar通过使用开放标准来扩展其语言覆盖范围,并增加了对Java、C#、Obj...

旋极科技
24分钟前
5
0
数据迁移

1. insert into values 或 insert into select批量插入时,都满足事务的原子性与一致性,但要注意insert into select的加锁问题。 2. replace into与insert into on duplicate key update都可...

qiang123
31分钟前
6
0
Linux装Windows系统后还不会激活?3招教你搞定

     相信大家已经发现荣耀MagicBook科技尝鲜版有多“香”了,不但可以轻松的将Linux系统装回Windows系统,还足足省下了300大洋!但是装回系统就万事大吉了吗?NoNoNo,我们还需要去激活...

梅丽莎好
34分钟前
6
0
Tomcat8源码分析-请求处理过程

上一篇:Tomcat8源码分析-启动流程-start方法 此篇主要讲Tomcat8从接收请求到处理请求的时序图画出来,并用文字描述一下主要流程 时序图 说明 文字描述流程之前先提示如下两点: 1.Acceptor...

特拉仔
36分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部