文档章节

线性表

自由的角马
 自由的角马
发布于 2015/01/10 13:56
字数 2260
阅读 9
收藏 1

线性表概述

线性表是最基本、最简单、也是最常用的一种数据结构。在线性表中数据元素之间的关系是线性,数据元素可以看成是排列在一条线上或一个环上。

线性表分为静态线性表和动态线性表,常见的有顺序表(静态的)、单向链表(动态的)和双向链表 (动态的)。

线性表的操作主要包括:

1)计算表的长度n

(2)线性表是否为空

3)将元素添加到线性表的末尾

4)获取第i个元素,0≤i < n

5清除线性表

(6)返回列表中首次出现指定元素的索引,如果列表不包含此元素,则返回 -1。

(7)返回列表中最后一次出现指定元素的索引,如果列表不包含此元素,则返回 -1。

8)将新元素插入第i个位置,0≤i < n,使原来的第ii+1n–1个元素变为第i+1i+2n个元素。

(9)更改第i个元素

10 )删除第 i 个元素, 0≤i < n ,使原来的第 i+1 i+2 n–1 个元素变为第 i i+1 n–2 个元素

由此,对线性表抽象数据类型定义List接口如下:

List接口

package list;

public interface List {
	/**
	 * 将元素添加到线性表的末尾
	 */
	public void add(Object e);
	
	/**
	 * 清除线性表
	 */
	public void clear();
	/**
	 * 获取i位置的元素
	 * @param i
	 * @return
	 */
	public Object get(int i);
	/**
	 * 返回列表中首次出现指定元素的索引,如果列表不包含此元素,则返回 -1。
	 * @param e
	 * @return
	 */
	public int indexOf(Object e);
	/**
	 * 在i后面插入一个元素e
	 * @param i
	 * @param e
	 */
	public void insert(int i, Object e);
	/**
	 * 判断线性表是否为空
	 * @return
	 */
	public boolean isEmpty();
	/**
	 * 回列表中最后出现指定元素的索引,如果列表不包含此元素,则返回 -1。
	 * @param e
	 * @return
	 */
	public int lastIndexOf(Object e);
	/**
	 *  移除列表中指定位置的元素
	 * @param i
	 */
	public void remove(int i);
	/**
	 * 用指定元素替换列表中指定位置的元素(可选操作)。
	 * @param i
	 * @param e
	 */
	public void set(int i, Object e);
	/**
	 * 返回线性表的大小
	 * @return
	 */
	public int size();
}


线性表分为静态线性表和动态线性表,常见的有顺序表(静态的)、单向链表(动态的)和双向链表 (动态的)。

线性表的操作主要包括:

1)计算表的长度n

(2)线性表是否为空

3)将元素添加到线性表的末尾

4)获取第i个元素,0≤i < n

5清除线性表

(6)返回列表中首次出现指定元素的索引,如果列表不包含此元素,则返回 -1。

(7)返回列表中最后一次出现指定元素的索引,如果列表不包含此元素,则返回 -1。

8)将新元素插入第i个位置,0≤i < n,使原来的第ii+1n–1个元素变为第i+1i+2n个元素。

(9)更改第i个元素

10 )删除第 i 个元素, 0≤i < n ,使原来的第 i+1 i+2 n–1 个元素变为第 i i+1 n–2 个元素

由此,对线性表抽象数据类型定义List接口如下:

List接口

package list;

public interface List {
	/**
	 * 将元素添加到线性表的末尾
	 */
	public void add(Object e);
	
	/**
	 * 清除线性表
	 */
	public void clear();
	/**
	 * 获取i位置的元素
	 * @param i
	 * @return
	 */
	public Object get(int i);
	/**
	 * 返回列表中首次出现指定元素的索引,如果列表不包含此元素,则返回 -1。
	 * @param e
	 * @return
	 */
	public int indexOf(Object e);
	/**
	 * 在i后面插入一个元素e
	 * @param i
	 * @param e
	 */
	public void insert(int i, Object e);
	/**
	 * 判断线性表是否为空
	 * @return
	 */
	public boolean isEmpty();
	/**
	 * 回列表中最后出现指定元素的索引,如果列表不包含此元素,则返回 -1。
	 * @param e
	 * @return
	 */
	public int lastIndexOf(Object e);
	/**
	 *  移除列表中指定位置的元素
	 * @param i
	 */
	public void remove(int i);
	/**
	 * 用指定元素替换列表中指定位置的元素(可选操作)。
	 * @param i
	 * @param e
	 */
	public void set(int i, Object e);
	/**
	 * 返回线性表的大小
	 * @return
	 */
	public int size();
}


顺序表

结构模型


图顺序存储结构内存结构示意图 


源代码

package list;

public class ArrayList implements List{
	/**
	 * 顺序表默认的初始大小
	 */
	public static final int defLen = 10;
	private int maxLen;
	private Object[] array;
	private int size;
	
	public ArrayList() {
		size = 0;
		maxLen = defLen;
		array = new Object[defLen];
	}
	
	@Override
	public void clear() {
		size = 0;
	}

	@Override
	public Object get(int i) {
		if(i>=0 && i<size)
			return array[i];
		else
			return null;
	}

	@Override
	public int indexOf(Object e) {
		int i =0; 
		while(i<size && !array[i].equals(e)) {
			i++;
		}
		if(i < size)
			return i;
		else
			return -1;
	}

	@Override
	public void insert(int i, Object e) {
		if(i >= size) {
			i = size;
			if((size) >= maxLen)//如果插入数的位置大于顺序表的最大容量,则扩大容量
				expand();
		}
		for(int j = size; j>i+1; j--) {
			array[j] = array[j-1];
		}
		array[i+1] = e;
		size ++;
	}

	@Override
	public boolean isEmpty() {
		if(size == 0)
			return true;
		else 
			return false;
	}

	@Override
	public int lastIndexOf(Object e) {
		int i = size-1;
		while(i>=0 && !array[i].equals(e)) {
			i--;
		}
		if(i>=0)
			return i;
		else
			return -1;
	}

	@Override
	public void remove(int i) {
		for(int j=i; j<size-1; j++) {
			array[j] = array[j+1];
		}
		size --;
	}

	@Override
	public void set(int i, Object e) {
		array[i] = e;
	}

	@Override
	public int size() {
		return size;
	}
	/**
	 * 当顺序表的大小不够时,扩充顺序表的大小
	 */
	private void expand() {
		maxLen = 2*maxLen;
		Object newArray[] = new Object[maxLen];
		for(int i=0; i<size; i++) {
			newArray[i] = array[i];
		}
		array = newArray;
	}

	@Override
	public void add(Object e) {
		if(size >=maxLen)
			expand();
		array[size] = e;
		size ++;
	}
}


单向循环链表

结构模型


带头结点的单链结构

  (a)空链;  (b)非空链 


源代码

package list;
/**
 * 链表的结点
 * @author luoweifu
 *
 */
class Node{
	Object data;	//数据元素
	Node next;		//后驱结点
	public Node() {
		this(null);
	}
	public Node(Object data) {
		this.data = data;
		this.next = null;
	}
}
/**
 * 带头结点的链式链表,下标从0开始; 
 * @author Administrator
 *
 */
public class LinkList implements List {
	Node head;	//头结点
	int size;	//链表的大小
	public LinkList() {
		head = new Node();
		size = 0;
	}
	public LinkList(Object[] datas) {
		int n = datas.length;
		head = new Node();
		Node p = head;
		for(int i=0; i<n; i++) {
			p.next = new Node(datas[i]);
			p = p.next;
		}
		size = n;
	}
	@Override
	public void add(Object e) {
		Node p;
		if(0 == size) {
			p = head;
		} else {
			p = index(size-1);
		}
		p.next = new Node(e);
		size ++;
	}

	@Override
	public void clear() {
		head.next = null;
		size = 0;
	}

	@Override
	public Object get(int i) {
		Node p = index(i);
		return p.data;
	}
	
	private Node index(int i) {
		Node p = null;
		if(i>=0 && i<size){
			p = head;
			for(int j=0; j<=i; j++) {
				p = p.next;
			}
		} 
		return p;
	}

	@Override
	public int indexOf(Object e) {
		Node p = head.next;
		int i = 0;
		while(!p.data.equals(e)) {
			p = p.next;
			i++;
		}
		if(i<size)
			return i;
		else 
			return -1;
	}

	@Override
	public void insert(int i, Object e) {
		Node p = index(i);
		Node p2 = new Node(e);
		p2.next = p.next;
		p.next = p2;
		size ++;
	}

	@Override
	public boolean isEmpty() {
		if(size ==0)
			return true;
		else
			return false;
	}

	@Override
	public int lastIndexOf(Object e) {
		int i = size-1;
		while(!get(i).equals(e)) {
			i--;
		}
		if(i>=0)
			return i;
		else 
			return -1;
	}

	@Override
	public void remove(int i) {
		if(i>=0 && i<size) {
			Node p = null;
			if(i == 0)
				p = head;
			else {
				p = index(i-1);
			}
			p.next = index(i).next;
		}
		size --;
	}

	@Override
	public void set(int i, Object e) {
		Node p = index(i);
		p.data = e;
	}

	@Override
	public int size() {
		return size; 
	}
	
}


双向循环链表

结构模型


带头结点的双循环链结构

 (a)空链;  (b)非空链 


源代码

package list;
/**
 * 链表的结点
 * @author luoweifu
 *
 */
class DlNode{
	Object data;
	DlNode prior, next;
	public DlNode() {
		this(null);
	}
	public DlNode(Object data) {
		this.data = data;	//数据元素
		this.prior = null;	//前驱结点
		this.next = null;	//后驱结点
	}
}
/**
 * 带头结点的双向循环链表,下标从0开始; 
 * @author Administrator
 *
 */
public class DoubleLinkList implements List {
	DlNode head;	//头结点
	int size;	//链表的大小
	public DoubleLinkList() {
		head = new DlNode();
		head.prior = head;
		head.next = head;
		size = 0;
	}
	public DoubleLinkList(Object[] datas) {
		int n = datas.length;
		head = new DlNode();
		DlNode p = head;
		DlNode p2 = null;
		for(int i=0; i<n; i++) {
			p2 = new DlNode(datas[i]);
			p.next = p2;
			p2.prior = p;
			p = p.next;
		}
		p2.next = head;
		head.prior = p2; 
		size = n;
	}
	@Override
	public void add(Object e) {
		DlNode p, p2;
		if(0 == size) {
			p = head;
		} else {
			p = index(size-1);
		}
		p2 = new DlNode(e);
		p.next = p2;
		p2.prior = p;
		p2.next = head;
		head.prior = p2;
		size ++;
	}

	@Override
	public void clear() {
		head.prior = head;
		head.next = head;
		size = 0;
	}

	@Override
	public Object get(int i) {
		DlNode p = index(i);
		return p.data;
	}
	
	private DlNode index(int i) {
		DlNode p = null;
		if(i>=0 && i<size){
			p = head;
			for(int j=0; j<=i; j++) {
				p = p.next;
			}
		} 
		return p;
	}

	@Override
	public int indexOf(Object e) {
		DlNode p = head.next;
		int i = 0;
		while(!p.data.equals(e)) {
			p = p.next;
			i++;
		}
		if(i<size)
			return i;
		else 
			return -1;
	}

	@Override
	public void insert(int i, Object e) {
		DlNode p = index(i);
		DlNode p2 = new DlNode(e);
		p2.next = p.next;
		p2.prior = p;
		p.next = p2;
		size ++;
	}

	@Override
	public boolean isEmpty() {
		if(size ==0)
			return true;
		else
			return false;
	}

	@Override
	public int lastIndexOf(Object e) {
		DlNode p = head.prior;
		int i = size-1;
		while(!p.data.equals(e)) {
			p = p.prior;
			i--;
		}
		if(i>=0)
			return i;
		else 
			return -1;
	}

	@Override
	public void remove(int i) {
		if(i>=0 && i<size) {
			DlNode p = null;
			if(i == 0)
				p = head;
			else {
				p = index(i-1);
			}
			DlNode p2 = index(i).next;
			p.next = p2.next;
			p2.next.prior = p;
		}
		size --;
	}

	@Override
	public void set(int i, Object e) {
		DlNode p = index(i);
		p.data = e;
	}

	@Override
	public int size() {
		return size; 
	}
	
}

测试线性表

package list;

public class Test {

	/**
	 * 测试线性表
	 * @param args
	 */
	public static void main(String args[]) {
		List list = new ArrayList();
		//List list = new LinkList();
		//List list = new DoubleLinkList();
		for(int i=0; i<10; i++) {
			list.add(new Integer(i));
		}
		list.remove(9);
		System.out.print("size;" + list.size() + "\n");
		System.out.println("isEmpty:" + list.isEmpty());
		System.out.print("第7个位置的元素:" + list.get(7) + "\n");	
		for(int i=0; i<list.size(); i++) {
			System.out.print(list.get(i) + "    ");
		}
		
		list.add(21);
		list.add(22);
		list.insert(3, new Integer(5));
		System.out.print("size:" + list.size() + "\n");
		System.out.print("第一次出现5的索引:" + list.indexOf(5) + "\n");
		System.out.print("最后一次出现5的索引:" + list.lastIndexOf(5) + "\n");
		list.set(0, new Integer(30));
		for(int i=0; i<list.size(); i++) {
			System.out.print(list.get(i) + "    ");
		}
	}
}

结果

size;9
isEmpty:false
第7个位置的元素:7
0    1    2    3    4    5    6    7    8    size:12
第一次出现5的索引:4
最后一次出现5的索引:6
30    1    2    3    5    4    5    6    7    8    21    22    

本文转载自:http://blog.csdn.net/luoweifu/article/details/8505178

自由的角马
粉丝 1
博文 269
码字总数 0
作品 0
文山
私信 提问
数据结构------线性表 day 001

一:线性表的定义: 线性表是具有相同属性的数据元素的一个有限数列。 二:顺序线性表的具体操作: (1)定义线性表: 1 struct list{2 ElemTpye list; /存线性表的指针,其中ElemTpye为通用...

青柠萌萌哒
2018/09/18
0
0
数据结构与算法-C语言篇5-线性表之顺序存储结构

数据结构与算法-目录 1、线性表的定义:有零个或多个数据元素组成的有序数列。 线性表是一种常用的数据结构。在实际应用中,线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。...

香沙小熊
2018/01/06
0
0
《数据结构》笔记三:线性表之顺序存储结构

前言: 关于源码的几个说明: 编码工具:Xcode 语言:C语言 参考书:《大话数据结构》 为了方便不熟悉的小伙伴们,文中关于代码的部分给出了详细的步骤,只要按照步骤,都可以实现。 另:小编...

小曼blog
06/28
0
0
数据结构之_动态数组 顺序表的实现

数据结构之_动态数组 顺序表的实现 1.基本概念 线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。 线性表 (a1,a2,……,an)的顺序存储示意图如下: 2.线...

Mr.Right-w
07/15
0
0
数据结构——线性表概述

线性表:由零个或多个数据元素组成的有限序列 特征: 1、是一个序列,元素之间有先来后到 2、有且只有一个“首元素”,它没有直接前驱,只有一个直接后继 3、有且只有一个“末元素”、它没有...

翼动动空
2016/05/08
1K
0

没有更多内容

加载失败,请刷新页面

加载更多

CSS盒子模型

一、什么叫框模型 页面元素皆为框(盒子) 定义了元素框处理元素内容,内边距,外边距以及边框的计算方式 二、外边距 围绕在元素边框外的空白距离(元素与元素之间的距离) 语法:margin,定...

wytao1995
今天
4
0
Replugin借助“UI进程”来快速释放Dex

public static boolean preload(PluginInfo pi) { if (pi == null) { return false; } // 借助“UI进程”来快速释放Dex(见PluginFastInstallProviderProxy的说明) return PluginFastInsta......

Gemini-Lin
今天
4
0
Hibernate 5 的模块/包(modules/artifacts)

Hibernate 的功能被拆分成一系列的模块/包(modules/artifacts),其目的是为了对依赖进行独立(模块化)。 模块名称 说明 hibernate-core 这个是 Hibernate 的主要(main (core))模块。定义...

honeymoose
今天
4
0
精华帖

第一章 jQuery简介 jQuery是一个JavaScript库 jQuery具备简洁的语法和跨平台的兼容性 简化了JavaScript的操作。 在页面中引入jQuery jQuery是一个JavaScript脚本库,不需要特别的安装,只需要...

流川偑
今天
7
0
语音对话英语翻译在线翻译成中文哪个方法好用

想要进行将中文翻译成英文,或者将英文翻译成中文的操作,其实有一个非常简单的工具就能够帮助完成将语音进行翻译转换的软件。 在应用市场或者百度手机助手等各大应用渠道里面就能够找到一款...

401恶户
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部