数据结构和算法是程序的灵魂,基本的数据结构分为:线性结构、树、图。线性结构又分为顺序实现的线性结构和链式实现的线性结构。链式线性结构是非随机存取结构,其get()、set()的时间复杂度是O(N);若已知要插入或删除的节点位置的话,其insert()、remove()的时间复杂度为O(1)。否则需要进行遍历操作,这时insert()、remove()的时间复杂度为O(N)。
首次写博客,望各位大牛拍砖来助学习。
以下 是单链表的实现代码:
线性表的抽象数据类型: package dataStructtion.linear; /** * 线性表的抽象数据类型 * @author xiucai * @param <T> */ public interface LList<T> { /** * 判断是否为空 * @return */ public boolean isEmpty(); /** * 返回线性表长度 * @return */ public int length(); /** * 返回下标为i的元素(i>=0) * @param i * @return */ public T get(int i); /** * 设置下标为i的元素值为t * @param i * @param t */ public void set(int i,T t); /** * 在下标为i的位置插入元素t * @param i * @param t */ public void insert(int i,T t); /** * 在线性表末尾追加元素t * @param t */ public void append(T t); /** * 移除下标为i的元素 * @param i * @return */ public T remove(int i); /** * 移除线性表所有元素 */ public void removeAll(); /** * 查找,返回首次出现的关键字为key的元素 * @param t * @return */ public T search(T t); /** * 判断线性表是否包含元素t * @param t * @return */ public boolean contain(T t); } 单节点的数据结构: package dataStructtion.linear; /** * 链表的单个节点 * @author xiucai * @param <T> */ public class Node<T> { public Object data;//存放数据 public Node<T> next;//后继 //初始化节点 public Node(Object data,Node<T> next){ this.data=data; this.next=next; } public Node(){ this(null,null); } //重写toString方法,用于输出 public String toString(){ return this.data.toString(); } //重写equals方法,用于比较 public boolean equals(Object data){ if (this.data==data) return true; if(data instanceof Node){ Node<T> node=(Node<T>)data; if(this.data==node.data&&this.next==node.next) return true; } return false; } } 单链表的实现类: package dataStructtion.linear; /** * 线性表的单链表表示与实现 * @author xiucai * @param <T> */ public class SingleLinkedList<T> implements LList<T> { private Node<T> head;//头结点 private int len;//链表长度 //初始化单链表 public SingleLinkedList(){ head=new Node<T>(); len=0; } @Override public boolean isEmpty() { // TODO Auto-generated method stub return len==0; } //获取单链表的长度 @Override public int length() { // TODO Auto-generated method stub return len; } //获取第i下标的元素 @Override public T get(int i) { // TODO Auto-generated method stub if(i<0||i>this.len) throw new IndexOutOfBoundsException(i+"下标越界"); Node<T> node=this.head.next; for(int j=0;node!=null&&j<i;j++){ node=node.next; } return (T)node.data; } //设置第i个元素为t @Override public void set(int i, T t) { // TODO Auto-generated method stub if(i<0||i>this.len) throw new IndexOutOfBoundsException(i+"下标越界"); if(t==null) return ; Node<T> node=this.head; for(int j=0;node.next!=null&&j<i;j++){ node=node.next; } node.data=t; } //在第i个位置插入元素t @Override public void insert(int i, T t) { // TODO Auto-generated method stub if(i<0||i>this.len) throw new IndexOutOfBoundsException(i+"下标越界"); if(t==null) return ; Node<T> node=this.head; for(int j=0;node.next!=null&&j<i-1;j++){ node=node.next; } Node<T> p=new Node<T>(t,node.next); node.next=p; len++; } //在单链表末尾追加元素t @Override public void append(T t) { // TODO Auto-generated method stub if(t==null) return ; Node<T> node=this.head; for(int i=0;node.next!=null&&i<this.len;i++){ node=node.next; } node.next=new Node<T>(t,null); len++; } //移除第i下标的元素 @Override public T remove(int i) { // TODO Auto-generated method stub if(i<0||i>this.len) throw new IndexOutOfBoundsException(i+"下标越界"); Node<T> node=this.head; for(int j=0;node.next!=null&&j<=i-1;j++){ node=node.next; } T t=(T)node.next.data; node.next=node.next.next; len--; return t; } //清空单链表 @Override public void removeAll() { // TODO Auto-generated method stub this.head.next=null; this.len=0; } //寻找值为t的元素 @Override public T search(T t) { // TODO Auto-generated method stub if(t==null) return null; Node<T> node=this.head; for(int i=0;node.next!=null&&i<this.len;i++){ if(node.next.data.equals(t)) return (T)node.next.data; node=node.next; } return null; } //判断单链表是否包含t元素 @Override public boolean contain(T t) { // TODO Auto-generated method stub return this.search(t)!=null; } //重写toString,用于输出 @Override public String toString(){ Node<T> node=this.head; String string="["; for(int i=0;node.next!=null&&i<this.len;i++){ string+=node.next.data+" "; node=node.next; } return string+"]"; } } 此类为测试类: package dataStructtion.linear; /** * 此类用于测试 * @author xiucai */ public class SingleLinkTest { public static void main(String[] args) { SingleLinkedList<String> s=new SingleLinkedList<String>(); s.insert(0, "aaa"); s.append("bbb"); System.out.println(s); System.out.println(s.length()); System.out.println(s.search("aaa")); System.out.println(s.contain("aaa")); for(int i=0;i<s.length();i++){ System.out.println(s.get(i)); } System.out.println(s.remove(0)); System.out.println(s); s.removeAll(); System.out.println(s.length()); System.out.println(s); } }
相关推荐
链表实现线性表的基本功能,继而更进一步地去活学活用的用好这个基本数据结构,最后更好的编程续写出更完美的程序片段
线性表,单链表,栈的代码实现,java简单实现,内附有代码少许注释
数据结构,单链表的12种操作的实现。更多详细内容请见http://blog.csdn.net/zhongkelee
http://www.miaokuanghua.blog.163.com/
将带头结点的单链表实现线性表的功能
数据结构C语言版-线性表的单链表存储结构表示和实现优质资料.doc
单链表的类定义和类实现,常见操作,插入、删除。
数据结构C语言版-线性表的单链表存储结构表示和实现.doc
【程序源码 3-2】单链表实现线性表的功能( DEV C版 ).exe
C/C++实现单链表,双链表,静态链表,以及用链表实现多项式的运算代码
C用类实现单链表操作C用类实现单链表操作C用类实现单链表操作
带头结点的单链表结构实现线性表操作.cpp
c语言实现线性表的一些基本功能。 void main () { printf("*********************顺序表****************************"); printf("\n"); SequenceList(); printf("\n\n\n"); printf("*****************...
单链表实现的多项式相加的内容,虽然不难,但是对于单链表创建的理解还是很有好处的。
数据结构中利用线性表和单链表实现筛选素数的功能。
内容和要求 单链表操作 和 栈、队列的... 4)定义一个顺序栈和循环队列,实现将队列中所有元素逆置。 实验数据:1)线性表为 6,2,11,5,2,4,2; 2)x=2; 3) k=5 或 k=10; 4)队列中的数据为 1,2,3,4,5,6
数据结构实验内容:线性表(顺序表实现)、线性表(单链表实现)、栈、字符串、多维数组(三元组表存矩阵)、二叉树(二叉链表和顺序表存储)、邻接表存图以及图的遍历、排序 实验报告部分只要求了线性表、栈、多维...
适用于初学者 非常简单! 电子版下载通过指针实现单链表结点的传递