数据结构总结

刚开始对数组队列和链表不是很清楚，这两天又上了几节课总算大概了解了点。数组队列和链表各有优点，具体怎么用就是胡哥说的看情况。
链表修改比较方便，但是获取内容时没有数组方便，需要从头节点开始一个个往下指向。
1.链表增加时不需要重新定义，而只需要新建一个节点node，然后让原先的尾节点指向node，再把node赋给尾节点，当然新建之前要先判断一下头节点是否为空。代码实现如下

	/**
	 * 添加节点的方法
	 * 
	 * @param node要被添加的节点对象
	 */

	public void add(Node node) {
		// 判断root是否为null，如果是，则表示此时第一个添加节点
		if (root == null) {
			root = node;// 将新节点给根节点
			tail = node;// 将新节点给尾节点
		} else {// 将新节点添加到尾节点之后
			tail.setNext(node);
			tail = node;
		}
		size++;// 计数器加1
	}

 
2.删除时只要指定删除位置的上一个节点直接指向指定删除位置的下一个节点就欧了，代码实现如下

/**
	 * 移除指定索引位置的数据
	 * 
	 * @param index指定的索引位置
	 * @return 返回移除的数据
	 */
	public Object remove(int index) {
		Node node = root;// 循环的节点
		Node removeNode;// 要移除的节点
		if (index == 0) {// 如果要移除的是第一个节点
			root = node.getNext();// 将root的下一个节点设置为root
			removeNode = node;// 把原来的root赋给要移除的节点
		} else {// 如果要移除的是不是第一个节点
			// 找到要移除节点的前一个节点对象
			for (int i = 0; i < index - 1; i++) {
				node = node.getNext();
			}
			// 判断要移除的节点是否是最后一个
			if (index == size - 1) {
				// 将node的下一个节点赋给要移除的节点
				removeNode = node.getNext();
				// 将node的下一个节点引用设置为null
				node.setNext(null);
			} else {// 要移除的节点是在链表的中间
				// 将node的下一个节点赋给要移除的节点
				removeNode = node.getNext();
				// 将removeNode下一个节点的引用赋给nextNode
				Node nextNode = removeNode.getNext();
				// 将nextNode赋给node,保持链表不会中断
				node.setNext(nextNode);
			}
		}
		size--;
		// 返回要移除节点的数据域对象
		return removeNode.getObj();
	}

 
3.根据指定索引获取相关信息较数组则会麻烦一点。链表不像数组一样有具体的编号，链表取出需要从头节点开始一个一个循环指下去，假如需要获取index位置的数据，先判断一下索引是否越界，一般默认头节点索引为0，则需要从头节点开始循环index次，即for(int i=0；i<index;i++){node = node.getNext();}，代码如下

/**
	 * 获取指定索引位置节点的数据
	 * 
	 * @param index指定的索引位置
	 */
	public Object get(int index) {
		if (index < 0 || index > size)
			throw new RuntimeException("索引越界！！");
		// return null;
		Node node = root;
		// 循环获取到指定索引位置的数据
		for (int i = 0; i < index; i++) {
			node = node.getNext();
		}
		// System.out.println(node);
		// 返回指定索引位置的元素
		return node.getObj();
	}

 
4.在指定索引处添加一个节点原理也和删除的类似，即新建一个节点，把要添加的内容赋给它，然后再让它上一个节点指向它并让它指向下一个节点。因此需要先获取指定索引上一个和指定索引处的节点，具体代码实现如下:

	/**
	 * 在指定索引下插入节点
	 * 
	 * @param index
	 * @param obj
	 */
	public void insertlndexObj(int index, Object obj) {
		if (index < 0 || index > size) {
			throw new RuntimeException("索引越界！！");
		} else {
			// 创建一个新的节点
			Node newNode = new Node(obj);
			if (index == 0) {// 如果链表没有节点
				root = newNode;
			} else {
				// 得到当前的节点
				Node node1 = root;
				Node node2 = root;
				// 循环获取到指定索引位置的数据
				for (int i = 0; i < index-1; i++) {
					node1 = node1.getNext();
				}
				for (int i = 0; i < index; i++) {
					node2 = node2.getNext();
				}
				node1.setNext(newNode);
				newNode.setNext(node2);
				
			}
		}
	}

 
5.修改指定索引index处的节点时，只需从头节点0开始，循环index次找到需要修改的节点直接修改即可，即

/**
	 * 修改节点对象
	 * 
	 * @return
	 */
	public Object Update(int index, Object obj) {
		if (index < 0 || index > size) {
			throw new java.lang.RuntimeException("下标越界：" + index + ",size: "
					+ size);
		} else {
			// 得到当前的节点
			Node node = root;
			// 循环获取到指定索引位置的数据
			for (int i = 0; i < index; i++) {
				node = node.getNext();
			}
			node.setObj(obj);
			return node.getObj();

		}
	}

 
数组与链表相比，修改就会有所不便。数组的长度是一开始就定义好的，无法修改，所以需要增删时需要重新定义一个符合条件长度的数组，然后再通过代码实现需要的功能。
1.需要在数组中添加一个数据时，先新建一个比原数组长度多1个单位的数组，然后从0开始遍历原数组的长度，将内容对应赋给新数组，再将需要添加的数据赋给最后一个节点，下标即为原来的A数组长度,最后再把新数组的地址赋给原数组，就实现了对原数组的覆盖

// 向队列中加入一个学生对象
	public void add(Student st) {
		// 1.新建一个数组，数组的长度是原数组长度+1
		Student[] srcB = new Student[srcA.length + 1];
		// 2.将原数组中的数据放入新数组
		for (int i = 0; i < srcA.length; i++) {
			srcB[i] = srcA[i];
		}
		// 3.将要加入的对象放入新数组的最后一位
		srcB[srcA.length] = st;
		// 将srcB数组的地址赋给srcA
		srcA = srcB;
	}

 
2.取得指定位置的对象相比较链表就会方便很多，直接查询指定的下标即可。

/**
	 * 取得队列中指定位置的一个对象
	 */
	public Student get(int index) {
		// 判断索引是否越界
		if (index < 0 || index >= srcA.length) {
			throw new RuntimeException("索引越界！");
		}
		return srcA[index];
	}

3. 在指定索引处插入数据，删除指定索引数据的数据都差不多，也是需要通过一个新数组来实现，或长度增加或减少，只是插入数据时单独多赋一个数据进去，分三个循环赋值，删除数据直接忽视需要删除的数据，从断点处两次循环就可以了。

/**
	 * 在指定索引处插入数据
	 * 
	 * @param index
	 * @param obj
	 */
	public void insert(int index, Student obj) {
		if (index < 0 || index >= srcA.length) {
			throw new RuntimeException("下标越界");
		} else {
			Student[] srcB = new Student[srcA.length + 1];
			for (int i = 0; i < index; i++) {
				srcB[i] = srcA[i];
			}
			srcB[index] = obj;
			for (int i = index; i < srcA.length; i++) {
				srcB[i + 1] = srcA[i];
			}
			// 将srcB数组的地址赋给srcA
			srcA = srcB;
		}
	}
	/**
	 * 删除指定索引数据
	 * 
	 * @return
	 */
	public void delete(int index) {
		if (index < 0 || index >= srcA.length) {
			throw new RuntimeException("下标越界");
		} else {
			Student[] srcB = new Student[srcA.length - 1];
			for (int i = 0; i < index; i++) {
				srcB[i] = srcA[i];
			}
			for (int i = index; i < srcA.length - 1; i++) {
				srcB[i] = srcA[i + 1];
			}
			// 将srcB数组的地址赋给srcA
			srcA = srcB;
		}
	}

 4. 根据索引修改数据直接找到索引处更改即可

/**
	 * 根据索引修改数组队列的对象
	 * 
	 * @param index
	 * @param obj
	 */
	public void update(int index, Student obj) {
		srcA[index] = obj;
	}

 

 

评论

1 楼 chentingk 2014-11-19  

代码好丰富