1.java实现节点
/**
* 节点
* @luminous-xin
* @param <T>
*/
public class Node<T> {
T data;
Node<T> next;
public Node(Node<T> n){
next = n;
}
public Node(T obj,Node<T> n){
data = obj;
next = n;
}
public T getData(){
return data;
}
public Node<T> getNext(){
return next;
}
}
2.java实现链表
/**
* 链表
* @author luminous-xin
* @param <T>
*/
public class ListLink<T> {
//头指针
private Node<T> head;
//单链表的长度
private int length; //构造一个空的链表
public ListLink() {
length = 0;
head = new Node<T>(null);
} //获取链表头节点的位置
public Node<T> getHead() {
return head;
} //在链表中插入一个元素
public boolean add(T obj, int pos) {
if (pos < 1 || pos > length + 1) {
System.out.println("pos值不合法");
return false;
}
int num = 1;
Node<T> p = head, q = head.next;
while (num < pos) {
p = q;
q = q.next;
num++;
}
p.next = new Node<T>(obj, q);
length++;
return true; } //删除链表中某各元素
public T remove(int pos) {
if (isEnpty()) {
System.out.println("链表为空表");
return null;
}
if (pos < 1 || pos > length + 1) {
System.out.println("pos值不合法");
return null;
}
int num = 1;
Node<T> p = head, q = head.next;
while (num < pos) {
p = q;
q = q.next;
num++;
}
p.next = q.next;
length--;
return q.data;
} //获取链表中一个元素的值
public T value(int pos) {
if (isEnpty()) {
System.out.println("链表为空表");
return null;
}
if (pos < 1 || pos > length + 1) {
System.out.println("pos值不合法");
return null;
}
int num = 1;
Node<T> p = head, q = head.next;
while (num < pos) {
p = q;
q = q.next;
num++;
}
return q.data;
} //在链表中查找一个元素，返回该元素下标的索引
public int find(T obj) {
if (isEnpty()) {
System.out.println("链表为空表");
return -1;
}
int num = 1; Node<T> p = head, q = head.next;
while (q!= null) {
if (obj.equals(q.data)) {
return num;
}
p = q;
q = q.next;
num++;
}
return -1;
/* Node<T> p = head.next;
while (p != null) {
if (p.data.equals(obj) == false) {
p = p.next;
num++;
} else break; }
if (p == null) {
return -1;
}
return num;*/
} //更新链表中某各元素
public boolean modify(T obj, int pos) {
if (isEnpty()) {
System.out.println("链表为空表");
return false;
}
if (pos < 1 || pos > length + 1) {
System.out.println("pos值不合法");
return false;
}
int num = 1;
Node<T> q = head.next;
while (num < pos) {
q = q.next;
num++;
}
q.data = obj;
return true;
} //判空
public boolean isEnpty() {
return length == 0;
} //求链表中数据元素的个数
public int size() {
return length;
} //一次访问链表中每个元素并输出
public void nextOrder() {
Node<T> q = head.next;
while (q != null) {
System.out.println(q.data);
q = q.next;
}
} //销毁一个已经存在的链表
public void clear() {
length = 0;
head.next = null;
} public static void main(String[] args) {
ListLink<Integer> l = new ListLink<>();
int i;
int a[] = {23, 56, 12, 49, 35};
for (i = 0; i < a.length; i++) {
l.add(a[i], i + 1);
}
System.out.println("单链表中的数据元素为：");
l.nextOrder();
System.out.println(l.find(5)); }
3.java实现顺序表
/**
* 顺序表
* @author luminous-xin
* @param <T>
*/
public class SequenceList<T> {
final int maxSize = 10; //顺序表中一维数组的长度
private T[] listArray; //存储元素的数组对象
private int length; //保存顺序表的当前长度
public SequenceList(){ //构造一个空的线性表
length = 0;
listArray = (T[])new Object[maxSize];
}
public SequenceList(int n){
if(n <= 0){
System.out.println("error");
System.exit(1);
}
length = 0;
listArray = (T[])new Object[n];
}
public boolean add(T obj , int pos){ //在线性表中插入一个新元素
if(pos < 1 || pos > length + 1){ //检验插入位置的有效性
System.out.println("pos不合法");
return false;
}
if(length == listArray.length){ //扩容
T[] p = (T[])new Object[length*2];
for (int i = 0; i < length; i++) {
listArray = p;
}
}
for (int i = length; i > pos; i--) { //插入
listArray[i] = listArray[i-1];
}
listArray[pos-1] = obj;
length++;
return true;
}
public T remove(int pos){ //在线性表中删除一个元素
if(isEmpty()){
System.out.println("顺序表为空，无法执行删除操作");
return null;
}else{
if(pos<1 || pos >length){
System.out.println("pos不合法");
return null;
} T x = listArray[pos-1]; //备份被删除的元素，将其作为返回值返回
for (int i = pos ; i <= length; i++) {
listArray[i-1] = listArray[i];
}
length++;
return x;
}
} public int find(T obj){ //在线性表中查找一个元素
if(isEmpty()){
System.out.println("顺序表为空");
return -1;
}else{
for(int i = 0 ; i <length ; i++){
if(listArray[i].equals(obj)){
return i + 1; //返回该元素的位置
}
}
return -1;
}
}
public T value(int pos){ //获取线性表中的一个元素
if(isEmpty()){
System.out.println("顺序表为空");
}else{
if(pos < 1 || pos > length +1){
System.out.println("pos值不合法");
}
}
return listArray[pos - 1];
}
public boolean modify(T obj,int pos){ //更新线性表中的某各元素
if(isEmpty()){
System.out.println("顺序表为空");
return false;
}else{
if(pos < 1 || pos > length ){
System.out.println("pos值不合法");
return false;
}
}
listArray[pos-1] = obj;
return true;
}
public boolean isEmpty(){ //判空
return length == 0;
}
public int size(){ //求线性表中数据元素的个数
return length;
}
public void nextOrder(){ //一次访问栈中的每个元素并输出
for(int i = 0 ; i< length; i++ ){
System.out.println(listArray[i]);
}
}
public void clear(){ //销毁一个已经存在的线性表
length = 0;
} }
4.链表的应用，合并两个有序链表
public class Chap2_2 {
public static <T extends Comparable> void MergeList_L(ListLink<T> la, ListLink<T> lb ,ListLink<T> lc){
Node<T> pa,pb,pc;
pa = la.getHead().next;
pb = lb.getHead().next;
pc = lc.getHead();
while(pa != null && pb != null){
if(pa.data.compareTo(pb.data)<0){
pc.next = pa;
pc = pa ;
pa = pa.next;
}else{
pc.next = pb;
pc = pb;
pb = pb.next;
}
while (pa != null){
pc.next = pa;
pc = pc.next;
pa = pa.next;
}
while (pb != null){
pc.next = pb;
pc = pb;
pb = pb.next;
}
la.clear();
lb.clear();
}
}
public static void main(String[] args) {
int i,j,k = 0;
int[] b = {12,23,35,49,56};
int[] a = {10,15,20};
ListLink<Integer> la = new ListLink<>();
ListLink<Integer> lb = new ListLink<>();
ListLink<Integer> lc = new ListLink<>();
for ( i = 0; i < a.length; i++) {
la.add(a[i],i+1);
}
System.out.println("单链表a中的元素为：");
la.nextOrder();
for (j = 0; j < b.length; j++) {
lb.add(b[j],j+1);
}
System.out.println("单链表b中的数据元素为：");
lb.nextOrder();
MergeList_L(la,lb,lc);
System.out.println("单链表c中的元素为：");
lc.nextOrder();
}
}
5.java实现顺序栈
/**
* 顺序栈
* @author luminous-xin
* @param <T>
*/
public class SequenceStack<T> {
final int maxSize = 10;
private T[] stackArray;
private int top;
//各方法的具体实现后有详细描述
public SequenceStack(){
top = -1;
stackArray = (T[])new Object[maxSize];
}
public SequenceStack(int n){
if(n<=0){
System.out.println("数组长度要大于零，否则退出程序运行！");
System.exit(1);
}
top = -1;
stackArray = (T[])new Object[n];
}
//在栈顶位置插入一个新元素
public void push(T obj){
if(top == stackArray.length-1){
T[] p = (T[])new Object[top*2+2];
for (int i = 0; i <= top; i++){
p[i] = stackArray[i];
}
stackArray = p;
} top++;
stackArray[top] = obj;
}
//删除栈顶元素
public T pop(){
if(top == -1) {
System.out.println("数据栈已空，无法删除元素");
return null;
}
top--;
return stackArray[top+1];
}
//取栈顶数据元素
public T getHead(){
if (top == -1){
System.out.println("数据栈已空，无法删除元素");
return null;
}
return stackArray[top];
}
//判断当前栈是否为空
public boolean isEmpty(){
return top == -1;
}
//求出栈中元素的个数
public int size(){
return top +1;
}
//依次访问栈中元素并输出
public void nextOrder(){
for(int i = top ; i >= 0;i--){
System.out.println(stackArray[i]);
}
}
//销毁一个已经存在的栈
public void clear(){
top = -1;
}
}
6.java实现链栈
/**
* 链栈
* @luminous-xin
* @param <T>
*/
public class LinkStack<T> {
private Node<T> top; //栈顶指针
private int length; //存储栈的长度
public LinkStack(){ //构造一个空的栈
length = 0;
top = null;
}
public void push(T obj){ //入栈
top = new Node<T>(obj,top);
length++;
}
public T pop(){ //出栈
if(top == null){
System.out.println("栈已空，无法删除");
return null;
}
T x = top.data;
top = top.next;
length--;
return x;
}
public T getHead(){ //取栈顶元素
if(top == null){
System.out.println("栈已空，无法删除");
return null;
}
return top.data;
}
public int size(){ //求出栈中元素的个数
return length;
}
public boolean isEmpty(){ //判断栈是否为空
if (top ==null){
return true;
}
return false;
}
public void nextOrder(){ //便利栈
Node<T> p = top;
while (p != null){
System.out.println(p.data);
p = p.next;
}
} public void clear(){ //销毁一个栈
top = null;
}
}
7.java实现顺序链表
import org.omg.CORBA.Object; /**
* 循环队列
* @author luminous
* @param <T>
*/
public class SequenceQueue<T> {
final int maxSize = 10;
private T queueArray[];
private int front, rear; public SequenceQueue() {
rear = front = 0;
queueArray = (T[]) new Object[maxSize];
} public void enQueue(T obj) { //入队
if ((rear + 1) % queueArray.length == front) {
T[] p = (T[]) new Object[queueArray.length * 2];
if (rear == ((T[]) queueArray).length) {
for (int i = 0; i <= rear; i++) {
p[i] = queueArray[i];
}
} else {
int i,j = 1;
for (i = front + 1; i<queueArray.length;i++,j++)
p[j] = queueArray[i];
for (i = 0;i<= rear ; i++,j++)
p[j] = queueArray[i];
front = 0;
rear = queueArray.length-1;
}
queueArray = p;
}
rear = (rear+1)%queueArray.length;
queueArray[rear] = obj;
}
public T DeQueue(){ //出队
if(isEmpty()){
System.out.println("队列已空，无法出队！");
return null;
}
front = (front +1)%queueArray.length;
return queueArray[front]; }
public T getTop(){ //取出头元素
if(isEmpty()){
System.out.println("队列已空，无法读取元素！");
return null;
}
return queueArray[(front+1)%queueArray.length] ;
}
public boolean isEmpty(){ //队列的非空队列
return front==rear;
}
public int size(){ //求队列长度
return (rear - front +queueArray.length)%queueArray.length;
}
public void nextOrder(){ //遍历队列
int i,j = front ;
for (i = 1; i < size(); i++) {
j = (j+1)%queueArray.length;
System.out.println(queueArray[j]); }
}
public void clear(){ //清空队列
front = rear =0;
}
}