关于线性表的思考

线性表的思考

之前在学习C的时候，曾经用C实现过基本的数据结构。现在对计算机体系有了较全面，较深入的认识后，想对之前的数据结构重新梳理，构建自己的知识体系。

以前学C的时候一直都不在状态，虽然课程设计什么的都能够独立完成，但是历程很心酸，现在回想一下，主要是自己在用代码实现逻辑的时候，太混乱，加上对C中的指针并未真正的理解，毕竟大一才真正接触计算机，我经常这样安慰自己。

那么现在先简单记录一下对以前不懂的地方的重新理解。

首先是指针，所谓指针，就是地址。理解地址这个概念，首先还要先理解计算机的内存模型，理解变量空间值这些基本的概念。然后是指针变量，所谓指针变量，就是存放指针的变量，也可以说是存放地址的变量。在C中，很多时候我们不会过分去区分指针和指针变量，很多时候都说指针来代替指针变量，如果理解得通就好，我个人喜欢对两者加以区分，这样我的逻辑才不会乱。
然后是关于指针变量的使用，在C里，我们会用malloc()之类的函数去申请空间；在java，会用操作符new去为变量申请内存空间；请注意，无论是C还是Java，经过上述操作后都会返回一个地址给指针变量。

String str = new String("i am a string！");//比如这里通过new操作后，会返回一个字符串"i am a string"的所在内存地址给str，而str就是存放String类型变量的指针变量。

以前我会想那str是放在内存中的哪里，学了汇编和jvm的一些东西后，原来str也在内存中，只是在一个叫栈的内存中。在那个内存里就放着str字符串所在内存的地址，通过这个地址可以拿到他的值。

然后是线性表的实现

import sun.applet.Main;
/**
 * 节点类
 * @author john
 *
 */
class LNode{
	private int data;
	private LNode next;
	public int getData() {
		return data;
	}
	public LNode getNext() {
		return next;
	}
	public void setData(int data) {
		this.data = data;
	}
	public void setNext(LNode next) {
		this.next = next;
	}
}
/**
 * 在这里说一下下面的方法中常出现的cursor这个游标变量，其实他就是一个临时变量，头结点指针不能移动，移了就丢了整个链表，那么就要一个临时变量来负责遍历。
 * 整个线性表可以这样理解，头结点就是数组名，cursor就是我们用来循环打印数组用到的临时变量i。
 * @author john
 *
 */
public class LinkList {
	public LNode head;//头节点指针变量，链表入口
	/**
	 * 初始化链表
	 * @param datas 数组结点
	 */
	public void initList(int [] datas) {
		LNode tail = new LNode();//为结点分配堆内存，尾指针变量指向其。
		head=tail;//开始时候头指针变量与尾指针变量指向同一个结点。
		for (int i = 0; i < datas.length; i++) {
			LNode newNode = new LNode();
			newNode.setData(datas[i]);
			newNode.setNext(null);
			tail.setNext(newNode);
			tail=newNode;
		}		
	}
	/**
	 * 查找结点是否存在某个值
	 * @param value 被查找的值
	 * @return 找到返回真，否则假
	 */
	public boolean searchInLink(int value){
		LNode cursor;//一个游标指针变量，用来遍历链表
		cursor = head;
		while(cursor.getNext()!=null){//如果下一个结点不空
			cursor = cursor.getNext();//cursor指向其
			if(cursor.getData()==value){
				System.out.println("找到"+value);
				return true;
			}
		}
		return false;
	}
	public boolean deleteFromList(int value){
		LNode cursor;//同理，只是用它来遍历链表
		cursor = head;
		while (cursor.getNext()!=null) {
			
			if(cursor.getNext().getData()==value){
				LNode deleteNode = cursor.getNext();//定义一个节点变量指向要被删除的节点
				cursor.setNext(deleteNode.getNext());//被删除的节点的上一个节点指向被删除的节点的下一个节点。
				System.out.println("删除成功"+deleteNode.getData());
				return true;
			}
			cursor = cursor.getNext();
		}
		System.out.println("没有，删除失败");
		return false;
	}
	public void printLink() {
		LNode cursor;//同理，只是用它来遍历链表
		cursor = head;
		while (cursor.getNext()!=null) {
			cursor = cursor.getNext();
			System.out.println(cursor.getData());
			}
		}
	public static void main(String[] args) {
			int[] datas = {1,2,3,4,5,6};//数组常量只有在初始化的时候才能进行
			LinkList linkList = new LinkList();
			linkList.initList(datas);
			linkList.printLink();
			linkList.searchInLink(5);
			linkList.deleteFromList(6);
			linkList.printLink();
	}
}

简单双向循环链表实现


/**
 * 双向循环链表的结点类
 * @author john
 */
class DoubleLNode {
	private int data;//结点数据
	private DoubleLNode preNode;//前驱结点
	private DoubleLNode nextNode;//后续结点
	public int getData() {
		return data;
	}
	public DoubleLNode getPreNode() {
		return preNode;
	}
	public DoubleLNode getNextNode() {
		return nextNode;
	}
	public void setData(int data) {
		this.data = data;
	}
	public void setPreNode(DoubleLNode preNode) {
		this.preNode = preNode;
	}
	public void setNextNode(DoubleLNode nextNode) {
		this.nextNode = nextNode;
	}
}
public class DoubleLinkList {
	public DoubleLNode head;//头结点
	public int size;//链表大小
	/**
	 * 初始化一个双向循环链表
	 * @param datas
	 */
	public void initList(int[] datas) {
		head = new DoubleLNode();
		head.setNextNode(head);//让后续指针变量指向头，主要是在判断是否链表只有头结点的时候方便判断
		head.setPreNode(head);//同上
		DoubleLNode tail;//定义一个尾指针变量
		tail = head;//首先尾指针变量是指向头指针结点。
		for(int i = 0;i<datas.length;i++){
			DoubleLNode newDNode = new DoubleLNode();
			newDNode.setData(datas[i]);//设置结点值
			newDNode.setPreNode(tail);
			tail.setNextNode(newDNode);
			newDNode.setNextNode(head);
			head.setPreNode(newDNode);		
			tail=newDNode;//tail指针变量指向最新的结点
		}		
	}
	/**
	 * 顺序打印一个双向循环链表
	 */
	public void printListNormally() {
		DoubleLNode cursor ;//定义一个游标指针变量
		cursor = head;
		while(cursor.getNextNode()!=head){
			cursor = cursor.getNextNode();
			System.out.println(cursor.getData());
		}
	}
	
	/**
	 * 倒叙打印
	 */
	public void printNotNormal() {
		DoubleLNode cursor ;//定义一个游标指针变量
		cursor = head;
		while(cursor.getPreNode()!=head){
			cursor = cursor.getPreNode();
			System.out.println(cursor.getData());
		}
	}
	
	/**
	 * 简单地最末尾的位置插入
	 * @param value 插入的数值
	 */
	public void insertIntoList(int value) {
		DoubleLNode newLNode = new DoubleLNode();
		newLNode.setData(value);
		DoubleLNode lastLNode;//最后的那个结点
		lastLNode = head.getPreNode();
		lastLNode.setNextNode(newLNode);
		newLNode.setPreNode(lastLNode);
		newLNode.setNextNode(head);
		head.setPreNode(newLNode);
	}
	
	public static void main(String[] args) {
		int [] a = {1,2,3,4,5,6};
		DoubleLinkList doubleLinkList  = new DoubleLinkList();
		doubleLinkList.initList(a);
		System.out.println("顺序打印");
		doubleLinkList.printListNormally();
		System.out.println("倒序打印");
		doubleLinkList.printNotNormal();
		doubleLinkList.insertIntoList(10);
		System.out.println("插入后顺序打印");
		doubleLinkList.printListNormally();
		System.out.println("插入后倒序打印");
		doubleLinkList.printNotNormal();
	}
	
	
}