Java基础复习笔记04数据结构-线性表

smx5555 贡献于2013-04-12

作者 liuyan  创建于2011-04-13 10:51:00   修改者liuyan  修改于2011-04-14 12:48:00字数8950

文档摘要: 线性表线性表是数据结构的一种逻辑结构,其实所有的逻辑数据结构都可以用2类物理实现方式去实现,一个是物理存储连续的顺序结构,另一个就是物理存储不连续的链式结构。线性表是指有n个元素组成的有序序列,这n个元素具有相同的结构。
关键词:

Java基础复习笔记04数据结构-线性表 刘岩 Email:suhuanzheng7784877@163.com 1. 线性表 线性表是数据结构的一种逻辑结构,其实所有的逻辑数据结构都可以用2类物理实现方式去实现,一个是物理存储连续的顺序结构,另一个就是物理存储不连续的链式结构。线性表是指有n个元素组成的有序序列,这n个元素具有相同的结构。 2. 线性表的操作 线性表的主要操作是增加元素、删除索引处元素、在索引处添加元素、查找索引处元素、替换索引处元素、清空所有元素。而对于顺序结构和链表结构这两种不同实现方式,底层的算法也会有比较大的差异。 3. 使用场景 其实线性表的使用场景非常多,从宏观来说,比如我们从数据库查询多条记录出来需要封装一个集合List对象来承载着众多的业务Bean元素,之后传给MVC的控制C层。之后C层在以某种展现形式传给视图V层。那么装载着众多业务记录信息的容器就是线性表。从微观上来讲,比如实现数据结构的栈结构、或者是对象池的底层、有序排序的数据域等等比较复杂的结构,底层都是离不开线性表的支持。 4. 线性表的顺序实现——顺序表 顺序的存储结构实质上就是利用数组进行元素的存储,笔者简单地实现了一个顺序链表。线性表的顺序实现就是利用对象数组。 看如下代码 package dateStructer.list; /** / 18 * 自实现的arrayList * @author liuyan * * @param */ public class MyArrayList implements List { //默认的数组长度 private final int DefSize = 16; //临时变量数组 private Object[] objects; //记录实实在在的元素个数 private int elementSize; public MyArrayList() { objects = new Object[DefSize]; } /** * 增加元素,实际上就是往最后一位出入数据 */ @Override public boolean add(E e) { add(elementSize, e); return true; } /** * 按位索引插入元素 */ @Override public void add(int index, E element) { if (index == elementSize) { objects[index] = element; elementSize++; return; } for (int i = elementSize - 1; i >= 0; i--) { if (i == index) { / 18 int movedSize = elementSize - i - 1; System.arraycopy(objects, index + 1, objects, index, movedSize); objects[index] = element; elementSize++; } } } /** * 清除所有元素 */ @Override public void clear() { for (int i = 0; i < elementSize; i++) { objects[i] = 0; } elementSize = 0; } /** * 判断集合是否包含了某个元素 */ @Override public boolean contains(Object o) { for (Object object : objects) { if (object != null && object.equals(o)) { return true; } } return false; } /** * 获得某位置索引的元素 */ @Override public E get(int index) { for (int i = 0; i < elementSize; i++) { / 18 if (i == index) { return (E) objects[index]; } } return null; } /** * 实现元素定位 */ @Override public int indexOf(Object o) { for (int i = 0; i < elementSize; i++) { if (o.equals(objects[i])) { return i; } } return -1; } /** * 是否是空集合 */ @Override public boolean isEmpty() { if (elementSize == 0) { return true; } return false; } @Override public int lastIndexOf(Object o) { if (objects == null || objects.length == 0) { return -1; } for (int i = elementSize - 1; i >= 0; i--) { if (objects[i] == o) { return i; } / 18 } return -1; } /** * 删除某个元素 */ @Override public boolean remove(Object o) { for (int i = 0; i < elementSize; i++) { if (o.equals(objects[i])) { objects[i] = null; int movedSize = elementSize - i - 1; System.arraycopy(objects, i + 1, objects, i, movedSize); elementSize--; return true; } } return false; } /** * 删除某个索引下的元素 */ @Override public E remove(int index) { for (int i = 0; i < elementSize; i++) { if (objects[i].equals(objects[index])) { objects[i] = null; int movedSize = elementSize - i - 1; System.arraycopy(objects, i + 1, objects, i, movedSize); elementSize--; return (E) objects[index]; } / 18 } return null; } /** * 对已有位置设置新的元素值 */ @Override public E set(int index, E element) { for (int i = 0; i < elementSize; i++) { if (i == index) { objects[index] = null; objects[index] = element; return element; } } return null; } @Override public int size() { // TODO Auto-generated method stub return elementSize; } @Override public String toString() { StringBuffer str = new StringBuffer("["); for (int i = 0; i < elementSize; i++) { str.append("[" + objects[i].toString() + "],"); } if (elementSize > 0) { return str.substring(0, str.lastIndexOf(",")) + "]"; } / 18 return str.append("]").toString(); } 实际上实现Java标准的List接口还需要实现其他一些方法,只不过因为篇幅原因,在此只能实现一些核心方法,而且说实在的,根本谈不上健壮性,更不可能投入使用,线程安全也存在问题,这只是演示一下用数组实现顺序线性表的核心算法罢了。所以说学习数据结构实际上是考验算法功底。一个数据结构的事先是否最优,完全是底层算法的实现是否最优。顺序线性表最大的特点就是物理上存储空间连续,内存资源使用比较节省、但是进行增加、删除元素的时候就得让别的元素挪挪地方了,用时间换取了空间的连续性,显得有点牵一发而动全身。如果是查找某个元素操作的时候就是需要遍历整体集合。 简单测试代码如下: public static void main(String[] args) { MyArrayList list = new MyArrayList(); list.add("1"); list.add("2"); list.add("3"); System.out.println(list); list.remove("3"); System.out.println(list); list.add("3"); System.out.println(list); System.out.println(list.contains("2")); System.out.println(list.isEmpty()); list.clear(); System.out.println(list); System.out.println(list.isEmpty()); } 执行结果 [[1],[2],[3]] [[1],[2]] [[1],[2],[3]] true false [] true 5. 线性表的非顺序实现——链式表 相对于数组的顺序存储,还可以定义一个比较特殊的链表结构,每个链表节点在内存中不一定是一块连续的区域,链表节点记录了与自身节点相关的下一个节点的位置信息。 如果链表节点仅仅记录了与其下一个Next节点的位置信息,而没有记录上一个Prev节点的信息,那么这叫做单向链表结构。 如果此节点不仅仅记录了下一个节点的信息,还记录了上一个节点的信息,那么这个情况叫做双向链表结构。我们就用双向链表实现Java标准的List接口。(实际上Java提出了一堆标准,实际上就是接口,而sun自己为自己定义的标准接口还提供了实现类,咱们一般用的就是基于sun提出标准的sun自己的实现类) / 18 。 如下代码 /** * 自己实现的linkedList * @author liuyan * @param */ public class MyLinkedList implements List { /** * 双向链表结构 */ public class LinkNode { // 真正的数据域 private E date; // 记录上一个节点 private LinkNode prevLinkNode; // 记录下一个节点 private LinkNode nextLinkNode; public LinkNode() { / 18 } public LinkNode(E date, LinkNode prevLinkNode, LinkNode nextLinkNode) { this.date = date; this.prevLinkNode = prevLinkNode; this.nextLinkNode = nextLinkNode; } } // 结点个数 private int nodeSize; // 头结点 private LinkNode headNode; // 尾巴节点 private LinkNode tailNode; public MyLinkedList() { headNode = null; tailNode = null; } /** * 采用尾端元素增加法,增加新元素 */ @Override public boolean add(E element) { if (nodeSize == 0) { headNode = new LinkNode(element, null, tailNode); } else { if (tailNode == null) { tailNode = new LinkNode(element, headNode, null); headNode.nextLinkNode = tailNode; nodeSize++; return true; } LinkNode linkNode = tailNode; tailNode = new LinkNode(element, linkNode, null); linkNode.nextLinkNode = tailNode; / 18 } nodeSize++; return true; } /** * 根据索引号查找节点 * * @param index * @return */ public LinkNode findLinkNodeByIndex(int index) { LinkNode linkNodeNowTemp = headNode; for (int i = 0; i < nodeSize; i++) { if (i == index) { return linkNodeNowTemp; } linkNodeNowTemp = linkNodeNowTemp.nextLinkNode; } return null; } /** * 按索引位置添加元素 */ @Override public void add(int index, E element) { if (nodeSize == 0) { add(element); } // 按照元素先建立新的node LinkNode linkNodeNew = new LinkNode(element, null, null); // 找到索引处的节点 LinkNode linkNodeNowTemp = findLinkNodeByIndex(index); // 找出索引处节点的上一个node / 18 LinkNode linkNodePrev = linkNodeNowTemp.prevLinkNode; // 上一个节点的下一个节点指向新node linkNodePrev.nextLinkNode = linkNodeNew; // 新节点的上一个节点指向原位置节点上一个节点 linkNodeNew.prevLinkNode = linkNodePrev; // 新节点的下一个节点指向原位置节点 linkNodeNew.nextLinkNode = linkNodeNowTemp; // 原节点的上一个节点指向新节点 linkNodeNowTemp.prevLinkNode = linkNodeNew; nodeSize ++; } /** * 清除所有Node元素资源 */ @Override public void clear() { LinkNode linkNodeNowTemp = headNode; for (int i = 0; i < nodeSize; i++) { if (linkNodeNowTemp != tailNode && linkNodeNowTemp != headNode) { linkNodeNowTemp = linkNodeNowTemp.nextLinkNode; linkNodeNowTemp.prevLinkNode.nextLinkNode = null; linkNodeNowTemp.prevLinkNode.prevLinkNode = null; linkNodeNowTemp.prevLinkNode.date = null; linkNodeNowTemp.prevLinkNode = null; } else if (linkNodeNowTemp == tailNode) { linkNodeNowTemp.prevLinkNode = null; } else if (linkNodeNowTemp == headNode) { linkNodeNowTemp.nextLinkNode = null; } } headNode = null; tailNode = null; nodeSize = 0; / 18 } /** * 是否包含此元素 */ @Override public boolean contains(Object object) { LinkNode linkNodeNowTemp = headNode; for (int i = 0; i < nodeSize; i++) { if (object == linkNodeNowTemp.date) { return true; } linkNodeNowTemp = linkNodeNowTemp.nextLinkNode; } return false; } @Override public E get(int index) { LinkNode linkNode = findLinkNodeByIndex(index); if (linkNode != null) { return linkNode.date; } return null; } @Override public boolean isEmpty() { return nodeSize == 0; } /** * 删除元素 */ @Override / 18 public boolean remove(Object o) { LinkNode linkNodeNowTemp = headNode; for (int i = 0; i < nodeSize; i++) { if (linkNodeNowTemp.date == o) { if (linkNodeNowTemp != tailNode && linkNodeNowTemp != headNode) { LinkNode linkNewPrev = linkNodeNowTemp.prevLinkNode; LinkNode linkNewNext = linkNodeNowTemp.nextLinkNode; linkNewPrev.nextLinkNode = linkNewNext; linkNewNext.prevLinkNode = linkNewPrev; linkNodeNowTemp.nextLinkNode = null; linkNodeNowTemp.prevLinkNode = null; linkNodeNowTemp.date = null; linkNodeNowTemp = null; nodeSize--; return true; } else if (linkNodeNowTemp == tailNode) { tailNode = linkNodeNowTemp.prevLinkNode; linkNodeNowTemp.prevLinkNode = null; linkNodeNowTemp.date = null; linkNodeNowTemp = null; nodeSize--; return true; } else if (linkNodeNowTemp == headNode) { headNode = linkNodeNowTemp.nextLinkNode; linkNodeNowTemp.nextLinkNode = null; linkNodeNowTemp.date = null; linkNodeNowTemp = null; nodeSize--; return true; } } linkNodeNowTemp = linkNodeNowTemp.nextLinkNode; / 18 } return false; } /** * 删除位置标记下的元素 */ @Override public E remove(int index) { LinkNode linkNodeNowTemp = headNode; for (int i = 0; i < nodeSize; i++) { if (index == i) { LinkNode linkNewPrev = linkNodeNowTemp.prevLinkNode; LinkNode linkNewNext = linkNodeNowTemp.nextLinkNode; linkNewPrev.nextLinkNode = linkNewNext; linkNewNext.prevLinkNode = linkNewPrev; linkNodeNowTemp.nextLinkNode = null; linkNodeNowTemp.prevLinkNode = null; linkNodeNowTemp.date = null; linkNodeNowTemp = null; break; } linkNodeNowTemp = linkNodeNowTemp.nextLinkNode; } return null; } @Override public int size() { // TODO Auto-generated method stub return nodeSize; } @Override public String toString() { StringBuffer str = new StringBuffer("["); / 18 LinkNode linkNode = null; for (int i = 0; i < nodeSize; i++) { linkNode = findLinkNodeByIndex(i); str.append("[" + linkNode.date + "],"); } if (nodeSize > 0) { return str.substring(0, str.lastIndexOf(",")) + "]"; } return str.append("]").toString(); } } 和顺序实现一样,实现了核心方法,下面是测试代码 public static void main(String[] args) { MyLinkedList list = new MyLinkedList(); list.add("1"); list.add("2"); list.add("3"); list.add(2,"22"); System.out.println(list); list.remove("3"); System.out.println(list); list.add("4"); System.out.println(list); System.out.println(list.contains("2")); System.out.println(list.isEmpty()); list.clear(); System.out.println(list); System.out.println(list.isEmpty()); } 执行后结果 [[1],[2],[22],[3]] [[1],[2],[22]] [[1],[2],[22],[4]] true false [] true 6. 总结 这次总结了线性表的数据结构,并且用数组和双向链表节点实现了类似ArrayList和LinkedList的功能。主要是实现了核心的方法。为了节省资源,一般 / 18 使用ArrayList存储,但是添加、删除元素的时候就比较费时间,还得移动剩余元素的物理位置,使之物理连续。而双向链表的实现也不是什么省油的灯,占用资源比数组大很多,但是作为经常修改的元素集合,双向链表还是比顺序链表有性能上的优势的。 / 18

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 3 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档