⑴ java版遞歸演算法實現單鏈表的求長度、查找、替換等操作
首先，你實現鏈表的時候肯定是有一個變數記錄鏈表大小的，求長度，直接獲取鏈表大小就可以。
查找：有兩種，一種是下標查找，還有一種是對象查找。其實底層歸根結底都是用的index下標查找。 替換也是同道理。你要明白鏈表的原理，我相信你就不會問遞歸去做這些操作。
因為你查找只要給出下標，直接在for循環在0到你給定的下標內循環就能取到，如果你給的下標在鏈表大小/2 的後半部分，你可以倒序循環；當然這只是一種思路，希望能幫到你
⑵ 用java單鏈表實現一元多項式相加的演算法。（）
public class Test {
public static void main(String[] args) {
try{
LinkList list1 = new LinkList();
LinkList list2 = new LinkList();
LinkList list3 = null;
list1.addAt(0, new Item(1, 5));
list1.addAt(1, new Item(-1.5, 3));
list1.addAt(2, new Item(1, 1));
list2.addAt(0, new Item(0.5, 5));
list2.addAt(1, new Item(0.5, 4));
list2.addAt(2, new Item(1.5, 3));
list2.addAt(3, new Item(3, 0));
list3 = mergeLinkList(list1, list2);
System.out.println("一元多項式的相加過程：");
list1.listAll();
System.out.println(" + ");
list2.listAll();
System.out.println(" = ");
list3.listAll();
}
catch(Exception e){
e.printStackTrace();
}
}
//兩個一元多項式相加，返回新的一元多項式
public static LinkList mergeLinkList(LinkList list1, LinkList list2){
int i = 0;
Item item = new Item();
Node curr1, curr2;
LinkList list3 = new LinkList();
curr1 = list1.getHead().getNext();
curr2 = list2.getHead().getNext();
while(curr1 != null && curr2 != null){
if(curr1.getData().getExp() > curr2.getData().getExp()){
item = curr1.getData();
list3.addAt(i, item);
curr1 = curr1.getNext();
i++;
}
else if(curr1.getData().getExp() < curr2.getData().getExp()){
item = curr2.getData();
list3.addAt(i, item);
curr2 = curr2.getNext();
i++;
}
else{
item = new Item(curr1.getData().getCoef() + curr2.getData().getCoef(), curr1.getData().getExp());
if(item.getCoef() != 0){
list3.addAt(i, item);
i++;
}
curr1 = curr1.getNext();
curr2 = curr2.getNext();
}
}
while(curr1 != null){
item = curr1.getData();
list3.addAt(i++, item);
curr1 = curr1.getNext();
}
while(curr2 != null){
item = curr2.getData();
list3.addAt(i++, item);
curr2 = curr2.getNext();
}
return list3;
}
}
/**
* 一元多項式的一般項類
*/
class Item{
private double coef; //一元多項式的一般項的系數
private int exp; //一元多項式的一般項的指數
public Item(){
this.coef = 0.0;
this.exp = 0;
}
public Item(double coef, int exp){
this.coef = coef;
this.exp = exp;
}
public double getCoef(){
return this.coef;
}
public void setCoef(double coef){
this.coef = coef;
}
public int getExp(){
return this.exp;
}
public void setExp(int exp){
this.exp = exp;
}
}
/**
* 鏈表結點類
*/
class Node{
private Item data;
private Node next; //鏈表結點的指針域，指向直接後繼結點
public Node(){
data = null;
next = null;
}
public Node(Item data, Node next){
this.data = data;
this.next = next;
}
public Item getData(){
return this.data;
}
public void setData(Item data){
this.data = data;
}
public Node getNext(){
return this.next;
}
public void setNext(Node next){
this.next = next;
}
}
/**
* 鏈表類
*/
class LinkList{
private Node head = null; //頭結點指針
private int size = 0;
public LinkList(){
head = new Node();
size = 0;
}
//在i位置插入元素elem
public boolean addAt(int i, Item elem) {
if(i < 0 || i > size){
return false;
}
Node pre,curr;
int pos;
for(pre=head; i>0 && pre.getNext()!=null; i--,pre=pre.getNext());
curr = new Node(elem, pre.getNext());
pre.setNext(curr);
size++;
return true;
}
//刪除i位置的元素
public boolean removeAt(int i) {
if(i < 0 || i >= size){
return false;
}
Node pre,curr;
for(pre=head; i>0 && pre.getNext()!=null; i--,pre=pre.getNext());
curr = pre.getNext();
pre.setNext(curr.getNext());
size--;
return true;
}
//根據值value查詢結點是否存在，若存在返回位置，否則返回-1
public int findByValue(Item value){
Node curr;
int pos;
for(pos=0,curr=head.getNext(); curr!=null; pos++,curr=curr.getNext()){
if(curr.getData().toString().equals(value.toString())){
break;
}
}
if(curr==null){
return -1;
}
return pos;
}
public Node getHead(){
return this.head;
}
public void setHead(Node head){
this.head = head;
}
public int getSize(){
return this.size;
}
public boolean isEmpty(){
return (size==0);
}
public void listAll(){
for(Node curr=head.getNext(); curr!=null; curr=curr.getNext()){
System.out.print("(" + curr.getData().getCoef() + ", " + curr.getData().getExp() + ")\t");
}
System.out.println();
}
}
⑶ 求java 單鏈表基本操作的實現
/*
注意：鏈表的結點數量用size表示，結點的位置為0~size-1
*/
import java.util.Scanner;
public class Test7 {
public static void main(String[] args) {
try{
LinkList list = new LinkList();
Integer value;
int pos = 0;
Scanner input = new Scanner(System.in);
String choice = null;
//測試A
while(true){
System.out.print("請輸入待插入結點的值(x或X退出)：");
choice = input.next();
if(choice.toUpperCase().equals("X")){
break;
}
value = Integer.valueOf(choice);
if(list.addAt(pos, value) == true){
System.out.println("插入值為 " + value + " 的結點到當前鏈表成功!");
pos++;
}
else{
System.out.println("插入結點失敗!");
}
}
System.out.print("當前鏈表所有結點：");
list.listAll();
//測試B
while(true){
System.out.print("請輸入待查詢結點的值(x或X退出)：");
choice = input.next();
if(choice.toUpperCase().equals("X")){
break;
}
value = Integer.valueOf(choice);
pos = list.findByValue(value);
if(pos == -1){
System.out.println("當前鏈表中不存在值為 " + value + " 的結點");
}
else{
System.out.println("值為 " + value + " 的結點在當前鏈表中的位置為 " + pos);
}
}
//測試C
while(true){
System.out.print("請輸入待刪除結點的位置[0~" + (list.getSize()-1) + "](x或X退出)：");
choice = input.next();
if(choice.toUpperCase().equals("X")){
break;
}
pos = Integer.valueOf(choice);
if(list.removeAt(pos) == true){
System.out.println("刪除當前鏈表中 " + pos + " 位置的結點成功!");
}
else{
System.out.println("刪除結點失敗!");
}
}
System.out.print("當前鏈表所有結點：");
list.listAll();
}
catch(Exception e){
e.printStackTrace();
}
}
}
/**
* 鏈表結點類
*/
class Node{
private Object data; //鏈表結點的數據域
private Node next; //鏈表結點的指針域，指向直接後繼結點
public Node(){
data = null;
next = null;
}
public Node(Object data, Node next){
this.data = data;
this.next = next;
}
public Object getData(){
return this.data;
}
public void setData(Object data){
this.data = data;
}
public Node getNext(){
return this.next;
}
public void setNext(Node next){
this.next = next;
}
}
/**
* 鏈表類
*/
class LinkList{
private Node head = null; //頭結點指針
private int size = 0;
public LinkList(){
head = new Node();
size = 0;
}
//在i位置插入元素elem
public boolean addAt(int i, Object elem) {
if(i < 0 || i > size){
return false;
}
Node pre,curr;
int pos;
for(pre=head; i>0 && pre.getNext()!=null; i--,pre=pre.getNext());
curr = new Node(elem, pre.getNext());
pre.setNext(curr);
size++;
return true;
}
//刪除i位置的元素
public boolean removeAt(int i) {
if(i < 0 || i >= size){
return false;
}
Node pre,curr;
for(pre=head; i>0 && pre.getNext()!=null; i--,pre=pre.getNext());
curr = pre.getNext();
pre.setNext(curr.getNext());
size--;
return true;
}
//根據值value查詢結點是否存在，若存在返回位置，否則返回-1
public int findByValue(Object value){
Node curr;
int pos;
for(pos=0,curr=head.getNext(); curr!=null; pos++,curr=curr.getNext()){
if(curr.getData().toString().equals(value.toString())){
break;
}
}
if(curr==null){
return -1;
}
return pos;
//return (curr!=null ? pos : -1);
}
public int getSize(){
return size;
}
public boolean isEmpty(){
return (size==0);
}
public void listAll(){
for(Node curr=head.getNext(); curr!=null; curr=curr.getNext()){
System.out.print(curr.getData() + "\t");
}
System.out.println();
}
}
⑷ java如何實現鏈表
鏈表是一種重要的數據結構，在程序設計中佔有很重要的地位。C語言和C＋＋語言中是用指針來實現鏈表結構的，由於Java語言不提供指針，所以有人認為在Java語言中不能實現鏈表，其實不然，Java語言比C和C＋＋更容易實現鏈表結構。Java語言中的對象引用實際上是一個指針（本文中的指針均為概念上的意義，而非語言提供的數據類型），所以我們可以編寫這樣的類來實現鏈表中的結點。
class Node
{
Object data;
Node next;//指向下一個結點
}
將數據域定義成Object類是因為Object類是廣義超類，任何類對象都可以給其賦值，增加了代碼的通用性。為了使鏈表可以被訪問還需要定義一個表頭，表頭必須包含指向第一個結點的指針和指向當前結點的指針。為了便於在鏈表尾部增加結點，還可以增加一指向鏈表尾部的指針，另外還可以用一個域來表示鏈表的大小，當調用者想得到鏈表的大小時，不必遍歷整個鏈表。下圖是這種鏈表的示意圖：
鏈表的數據結構
我們可以用類List來實現鏈表結構，用變數Head、Tail、Length、Pointer來實現表頭。存儲當前結點的指針時有一定的技巧，Pointer並非存儲指向當前結點的指針，而是存儲指向它的前趨結點的指針,當其值為null時表示當前結點是第一個結點。那麼為什麼要這樣做呢？這是因為當刪除當前結點後仍需保證剩下的結點構成鏈表，如果Pointer指向當前結點，則會給操作帶來很大困難。那麼如何得到當前結點呢，我們定義了一個方法cursor(),返回值是指向當前結點的指針。類List還定義了一些方法來實現對鏈表的基本操作，通過運用這些基本操作我們可以對鏈表進行各種操作。例如reset()方法使第一個結點成為當前結點。insert(Object d)方法在當前結點前插入一個結點，並使其成為當前結點。remove()方法刪除當前結點同時返回其內容，並使其後繼結點成為當前結點，如果刪除的是最後一個結點，則第一個結點變為當前結點。
鏈表類List的源代碼如下：
import java.io.*;
public class List
{
/*用變數來實現表頭*/
private Node Head=null;
private Node Tail=null;
private Node Pointer=null;
private int Length=0;
public void deleteAll()
/*清空整個鏈表*/
{
Head=null;
Tail=null;
Pointer=null;
Length=0;
}
public void reset()
/*鏈表復位，使第一個結點成為當前結點*/
{
Pointer=null;
}
public boolean isEmpty()
/*判斷鏈表是否為空*/
{
return(Length==0);
}
public boolean isEnd()
/*判斷當前結點是否為最後一個結點*/
{
if(Length==0)
throw new java.lang.NullPointerException();
else if(Length==1)
return true;
else
return(cursor()==Tail);
}
public Object nextNode()
/*返回當前結點的下一個結點的值，並使其成為當前結點*/
{
if(Length==1)
throw new java.util.NoSuchElementException();
else if(Length==0)
throw new java.lang.NullPointerException();
else
{
Node temp=cursor();
Pointer=temp;
if(temp!=Tail)
return(temp.next.data);
else
throw new java.util.NoSuchElementException();
}
}
public Object currentNode()
/*返回當前結點的值*/
{
Node temp=cursor();
return temp.data;
}
public void insert(Object d)
/*在當前結點前插入一個結點，並使其成為當前結點*/
{
Node e=new Node(d);
if(Length==0)
{
Tail=e;
Head=e;
}
else
{
Node temp=cursor();
e.next=temp;
if(Pointer==null)
Head=e;
else
Pointer.next=e;
}
Length＋＋;
}
public int size()
/*返回鏈表的大小*/
{
return (Length);
}
public Object remove()
/*將當前結點移出鏈表，下一個結點成為當前結點，如果移出的結點是最後一個結點，則第一個結點成為當前結點*/
{
Object temp;
if(Length==0)
throw new java.util.NoSuchElementException();
else if(Length==1)
{
temp=Head.data;
deleteAll();
}
else
{
Node cur=cursor();
temp=cur.data;
if(cur==Head)
Head=cur.next;
else if(cur==Tail)
{
Pointer.next=null;
Tail=Pointer;
reset();
}
else
Pointer.next=cur.next;
Length－－;
}
return temp;
}
private Node cursor()
/*返回當前結點的指針*/
{
if(Head==null)
throw new java.lang.NullPointerException();
else if(Pointer==null)
return Head;
else
return Pointer.next;
}
public static void main(String[] args)
/*鏈表的簡單應用舉例*/
{
List a=new List ();
for(int i=1;i<=10;i＋＋)
a.insert(new Integer(i));
System.out.println(a.currentNode());
while(!a.isEnd())
System.out.println(a.nextNode());
a.reset();
while(!a.isEnd())
{
a.remove();
}
a.remove();
a.reset();
if(a.isEmpty())
System.out.println("There is no Node in List \n");
System.in.println("You can press return to quit\n");
try
{
System.in.read();
//確保用戶看清程序運行結果
}
catch(IOException e)
{}
}
}
class Node
/*構成鏈表的結點定義*/
{
Object data;
Node next;
Node(Object d)
{
data=d;
next=null;
}
}
讀者還可以根據實際需要定義新的方法來對鏈表進行操作。雙向鏈表可以用類似的方法實現只是結點的類增加了一個指向前趨結點的指針。
可以用這樣的代碼來實現：
class Node
{
Object data;
Node next;
Node previous;
Node(Object d)
{
data=d;
next=null;
previous=null;
}
}
當然，雙向鏈表基本操作的實現略有不同。鏈表和雙向鏈表的實現方法，也可以用在堆棧和隊列的實現中，這里就不再多寫了，有興趣的讀者可以將List類的代碼稍加改動即可。
希望對你有幫助。
⑸ 用java單鏈表實現一元多項式相加的演算法
public class Test {
public static void main(String[] args) {
try{
LinkList list1 = new LinkList();
LinkList list2 = new LinkList();
LinkList list3 = null;
list1.addAt(0, new Item(1, 5));
list1.addAt(1, new Item(-1.5, 3));
list1.addAt(2, new Item(1, 1));
list2.addAt(0, new Item(0.5, 5));
list2.addAt(1, new Item(0.5, 4));
list2.addAt(2, new Item(1.5, 3));
list2.addAt(3, new Item(3, 0));
list3 = mergeLinkList(list1, list2);
System.out.println("一元多項式的相加過程：");
list1.listAll();
System.out.println(" + ");
list2.listAll();
System.out.println(" = ");
list3.listAll();
}
catch(Exception e){
e.printStackTrace();
}
}
/**
* 一元多項式的一般項類
*/
class Item{
private double coef; //一元多項式的一般項的系數
private int exp; //一元多項式的一般項的指數
public Item(){
this.coef = 0.0;
this.exp = 0;
}
public Item(double coef, int exp){
this.coef = coef;
this.exp = exp;
}
public double getCoef(){
return this.coef;
}
public void setCoef(double coef){
this.coef = coef;
}
public int getExp(){
return this.exp;
}
public void setExp(int exp){
this.exp = exp;
}
}
/**
* 鏈表結點類
*/
class Node{
private Item data;
private Node next; //鏈表結點的指針域，指向直接後繼結點
public Node(){
data = null;
next = null;
}
public Node(Item data, Node next){
this.data = data;
this.next = next;
}
public Item getData(){
return this.data;
}
public void setData(Item data){
this.data = data;
}
public Node getNext(){
return this.next;
}
public void setNext(Node next){
this.next = next;
}
}
/**
* 鏈表類
*/
class LinkList{
private Node head = null; //頭結點指針
private int size = 0;
public LinkList(){
head = new Node();
size = 0;
}
//在i位置插入元素elem
public boolean addAt(int i, Item elem) {
if(i < 0 || i > size){
return false;
}
Node pre,curr;
int pos;
for(pre=head; i>0 && pre.getNext()!=null; i--,pre=pre.getNext());
curr = new Node(elem, pre.getNext());
pre.setNext(curr);
size++;
return true;
}
//刪除i位置的元素
public boolean removeAt(int i) {
if(i < 0 || i >= size){
return false;
}
Node pre,curr;
for(pre=head; i>0 && pre.getNext()!=null; i--,pre=pre.getNext());
curr = pre.getNext();
pre.setNext(curr.getNext());
size--;
return true;
}
java是一種可以撰寫跨平台應用軟體的面向對象的程序設計語言。Java技術具有卓越的通用性、高效性、平台移植性和安全性，廣泛應用於PC、數據中心、游戲控制台、科學超級計算機、行動電話和互聯網，同時擁有全球最大的開發者專業社群。
⑹ 求單鏈表的長度的遞歸演算法(java)
package cn.uestc.fz;
class Node{
int data;
Node next;
public Node(int data,Node next){
this.data=data;
this.next=next;
}
}
public class LinkedList {
Node head;
public void add(Node node){
if(head==null)
head=node;
else{
Node p=head;
while(p.next!=null)
p=p.next;
p.next=node;
}
}
public int length(){
return this.length(head);
}
public int length(Node node){
if(node==null)
return 0;
else if(node.next==null)
return 1;
else
return 1+this.length(node.next);
}
public void printList(){
Node p=head;
while(p!=null){
System.out.print(p.data+"->");
p=p.next;
}
System.out.println();
}
public static void main(String args[]){
LinkedList list = new LinkedList();
list.add(new Node(1,null));
list.add(new Node(2,null));
list.add(new Node(3,null));
list.add(new Node(4,null));
list.add(new Node(5,null));
list.add(new Node(6,null));
list.printList();
System.out.println(list.length());
}
}
剛寫的。
⑺ java數據結構單鏈表
你的問題很好理解。但是你的代碼問題嚴重。
1、你想用java代碼實現還是c代碼實現？從你的代碼看是c語言
2、第一段代碼中的結構體nod是不是應該寫成Node？
3、inset函數中，鏈表L是有變化的，所以要用指針。結點s是不改變的，所以不應該用指針
4、既然s不是用指針，後面的s->next自然也不能這么寫了。
⑻ 急急急 如何用Java語言實現判斷一個鏈表是否存在循環連接的演算法
編寫兩個java類，一個為Linkitem.java，另一個為測試類LinklistTest.java，分別如下：
*****************************************************
//Linkitem.java
public class Linkitem {
Linkitem previous;
String data;
Linkitem next;
public Linkitem() {
}
public Linkitem(Linkitem previous, String data, Linkitem next) {
super();
this.previous = previous;
this.data = data;
this.next = next;
}
public Linkitem getPrevious() {
return previous;
}
public void setPrevious(Linkitem previous) {
this.previous = previous;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public Linkitem getNext() {
return next;
}
public void setNext(Linkitem next) {
this.next = next;
}
}
*****************************************************
//LinklistTest.java
import java.util.ArrayList;
public class LinklistTest {
public static void main(String[] args) {
//初始化鏈表項
Linkitem a = new Linkitem(null, "a", null);
Linkitem b = new Linkitem(null, "b", null);
Linkitem c = new Linkitem(null, "c", null);
Linkitem d = new Linkitem(null, "d", null);
a.setPrevious(d);
a.setNext(b);
b.setPrevious(a);
b.setNext(c);
c.setPrevious(b);
c.setNext(d);
d.setPrevious(c);
d.setNext(a);
//新建存放鏈表的數組列表
ArrayList<Linkitem> list = new ArrayList<Linkitem>();
//添加個鏈表項
list.add(a);
list.add(b);
list.add(c);
list.add(d);
//是否為循環鏈表的判斷變數
boolean link = false;
Linkitem start = a;
Linkitem current = a;
//判斷循環鏈表
for (int i = 0; i < list.size(); i++) {
current = current.next;
if (start.data.equals(current.data)) {
link = true;
}
}
//輸出
if (link == true) {
System.out.println("此鏈表為循環鏈表。");
} else {
System.out.println("此鏈表不是循環鏈表。");
}
}
}
*****************************************************
運行結果為：
此鏈表為循環鏈表。
⑼ JAVA 語言！定義單鏈表，完成下了演算法： 1、從鍵盤上依次輸入21、18、30、75、42、56，逆序創建單鏈表
我想java.util.LinkedList的源碼可以幫助你解決大部分問題，包括你想要的這5個功能實現。
⑽ 使用java設計演算法，完成將兩個有序遞增的單鏈表合並為一個有序遞增的單鏈表，重復的元素只出現一次。
type
point=^node;
node=record
data:integer;
next:point;
end;
var h1,h2,h:point;
procere prt(p:point); //列印鏈表
begin
p:=p^.next;
while p<>nil do
begin
write(p^.data,' ');
p:=p^.next;
end;
writeln;
end;
procere creat(var h:point); //建立鏈表
var x:integer; p,q:^node;
begin
writeln('請輸入升序的數，負數結束：');
new(h);
p:=h;
read(x);
while(x>=0)do
begin
new(q);
q^.data:=x;
p^.next:=q;
p:=q;
read(x);
end;
p^.next:=nil;
end;
function merge_link(var p,q:point):point; //升序合並二個升序鏈表
var h,w:^node;
begin
w:=p; p:=p^.next; dispose(w); //回收一個頭結點，p指向首個數據結點
w:=q; h:=q; q:=q^.next; //h:合並後的頭結點，q指向首個數據結點
while (p<>nil)and(q<>nil) do //當二個鏈表都不空時
if(p^.data<q^.data) then //選一個小的結點
begin
w^.next:=p; //把小結點鏈入
p:=p^.next; //跳過此結點
w:=w^.next; //w指向當前合並後鏈表的尾結點
end
else
begin //下面三行作用同上
w^.next:=q;
q:=q^.next;
w:=w^.next;
end;
if p<>nil then w^.next:=p; //將未完的鏈表接入
if q<>nil then w^.next:=q; //將未完的鏈表接入
merge_link:=h; //返回合並後的鏈表頭指針
end;
begin
creat(h1);
creat(h2);
h:=merge_link(h1,h2);
writeln('合並後的鏈表：');
prt(h);