首页 > 代码库 > (java描述)关于链表的代码-----单双、循环链表、约瑟夫环、多项式相加

(java描述)关于链表的代码-----单双、循环链表、约瑟夫环、多项式相加

  1. 将链表头尾倒置
  2. 将几个链表合并成一个新的链表,将链表中重复的节点去掉,并按大小排序
  3. 双向循环链表
  4. 单向循环链表(约瑟夫循环)
  5. 多项式相加

程序源代码

单链表、单向循环链表结点类

package javab;

 

public class Node {

int data;

Node next;

public Node(int data){

this.data=data;

}

}

第一题代码:

package javab;

 

import java.util.Scanner;

 

public class Invertion {

static Node create(){

Node head=null,p=null,t=null;

Scanner reader=new Scanner(System.in);

int d=0;

int i=1;

while(true){

d=reader.nextInt();

if(d==0) break;

if(i==1){

head=new Node(d);

t=head;

i++;

}

else{

p=new Node(d);

p.next=null;

t.next=p;

t=p;

}

}

return head;

}

static Node invert(Node h){

Node p,q,r;

p=h;

q=p.next;

while(q!=null){

r=q.next;

q.next=p;

p=q;

q=r;

}

h.next=null;

h=p;

return h;

}

static void disp(Node h){

Node p=h;

if(p==null){

System.out.println("空表!");

}

while(p!=null){

System.out.print(p.data+"  ");

p=p.next;

}

System.out.println();

}

public static void main(String[] args) {

// TODO Auto-generated method stub

System.out.println("输入数字创建链表,以0结束:  ");

Node h;

h=create();

disp(h);

System.out.println("倒序输出为:  ");

Node h1=invert(h);

disp(h1);

}

 

}

代码:

package javab;

 

import java.util.Scanner;

 

public class OrderDelete {

static int i=0,m=0,n=0;

static Node create(){

Node head=null,p=null,t=null;

Scanner reader=new Scanner(System.in);

int d=0;

while(true){

d=reader.nextInt();

if(d==0) break;

if(i==0){

head=new Node(d);

t=head;

}

else{

p=new Node(d);

p.next=null;

t.next=p;

t=p;

}

i++;

}

m++;

if(m==1){

n=i;i=0;

}

if(m==2){

n=n+i;i=0;

}

if(m==3){

n=n+i;

}

return head;

}

static void disp(Node h){

Node p=h;

if(p==null){

System.out.println("空表!");

}

while(p!=null){

System.out.print(p.data+"  ");

p=p.next;

}

System.out.println();

}

static Node order(Node h){

Node a,b,temp=new Node(1);

for(int j=1;j<n;j++){

a=h;

b=a.next;

for(int x=1;x<n;x++){

if(a.data>b.data){

temp.data=a.data;

a.data=b.data;

b.data=temp.data;

a=b;

b=a.next;

}

else{

a=b;

b=a.next;

}

}

}

return h;

}

static Node dele(Node h){

Node a=h;

Node b=a.next;

do{

if(b!=null&&a.data==b.data){

a.next=a.next.next;

b=a.next;

}

if(b!=null&&a.data!=b.data){

a=b;

b=b.next;

}

}while(b!=null);

return h;

}

static Node combine(Node h1,Node h2,Node h3){

Node head1=h1,head2=h2,head3=h3;

Node t=head1.next;

while(t.next!=null){

t=t.next;

}

t.next=head2;

while(t.next!=null){

t=t.next;

}

t.next=head3;

return head1;

}

public static void main(String[] args) {

// TODO Auto-generated method stub

System.out.println("输入第一个数组创建第一个链表,以0结束:  ");

Node h1,h2,h3;

h1=create();

System.out.println("输入第二个数组创建第二个链表,以0结束:  ");

h2=create();

System.out.println("输入第三个数组创建第三个链表,以0结束:  ");

h3=create();

h1=combine(h1,h2,h3);

System.out.println("合并后的数组:");

disp(h1);

System.out.println("合并后的数组排序:");

h1=order(h1);

disp(h1);

System.out.println("合并排序后的数组删去重复数字:");

h1=dele(h1);

disp(h1);

}

 

}

第三题代码:

package javab;

 

public class DulNode {

int     data;

DulNode  next;

DulNode  prior;

public DulNode(int data){

this.data=data;

}

}

链表类

package javab;

 

import java.util.Scanner;

 

public class DulLink {

static DulNode create(){

DulNode tail=null,head=null,p=null;

Scanner reader=new Scanner(System.in);

int d=0;

int i=1;

while(true){

d=reader.nextInt();

//System.out.println(d);

if(d==0) break;

if(i==1){

head=new DulNode(d);

//System.out.println(head.data);

//head.prior=head;

//head.next=head;

tail=head;

i++;

}

else{

 

p=new DulNode(d);

tail.next=p;

p.prior=tail;

p.next=head;

tail=p;

head.prior=tail;

//tail.next=p;

 

//head.prior=p;

 

////p.prior=tail;

//tail=p;

//tail.next=head;

 

}

 }

return head;

}

static void insert(int i,int x,DulNode h){

DulNodes,p;

int j;

p=h.next;

j=2;

while(j<i&&p!=h){

p=p.next;

j++;

}

if(j==i){

s=new DulNode(x);

s.prior=p.prior;

p.prior.next=s;

s.next=p;

p.prior=s;

}

}

static void dele(DulNode h,int i){

int s;

DulNode p;

int j;

p=h.next;

j=2;

while(p!=h&&j<i){

j++;

p=p.next;

}

if(j==i){

s=p.data;

p.prior.next=p.next;

p.next.prior=p.prior;

p=null;

}

}

static void disp(DulNode h){

DulNode p=h;

System.out.print(p.data+"  ");

//System.out.println(p.prior.data);

p=p.next;

while(p!=h){

System.out.print(p.data+"  ");

//System.out.println(p.prior.data);

p=p.next;

 

}

System.out.println();

//System.out.println(p.data);

}

public static void main(String[] args) {

// TODO Auto-generated method stub

DulNode h;

System.out.println("创建一个新的双向循环链表:");

h=create();

disp(h);

System.out.println("插入一个数:");

insert(3,25,h);

disp(h);

System.out.println("删掉第四个数:");

dele(h,4);

disp(h);

}

}

第四题代码:

package javab;

 

import java.util.Scanner;

 

public class YueSe {

static Node create(int n){

Node head=new Node(1);

Node news=null;

Node t=null;

for(int i=1;i<n+1;i++){

if(i==1)

{

t=head;

}

else

{

news=new Node(i);

 

news.next=null;

   t.next=news;

t=news;

}

 

}

t.next=head;

return head;

}

static void pick(Node head,int m,int s){

Node p=head;

while(p!=p.next){

if(p.data==s){

 

for(int s1=s;s1<s+m-2;s1++){

p=p.next;

}

System.out.print(p.next.data+"");

p.next=p.next.next;

p=p.next;

s=p.data;

}

else

p=p.next;

}

System.out.print(p.data+"");

}

 

public static void main(String[] args) {

// TODO Auto-generated method stub

int n,m,s;

Scanner reader=new Scanner(System.in);

     System.out.println("请输入围在桌子上的人数n:");

      n=reader.nextInt();

      System.out.println("请输入要从第几个人开始报数s:");

      s=reader.nextInt();

      System.out.println("请输入当报数到第几人时要出局m:");

      m=reader.nextInt();

      Node head;

      head=create(n);

      pick(head,m,s);

}

 

}

第五题代码:

package javab;

//结点类

public class JD {

int coef,exp;

JD  next;

public JD(int coef,int exp){

this.coef=coef;

this.exp=exp;

}

}

package javab;

 

import java.util.Scanner;

 

public class More {

static JD create(){

JD head=null,p=null,t=null;

Scanner reader=new Scanner(System.in);

System.out.println("输入多项式的项数:");

int n=reader.nextInt();

System.out.println("请依次输入该多项式的系数和指数(指数顺序从小到大):");

int a,b;

for(int i=1;i<=n;i++){

if(i==1){

a=reader.nextInt();

b=reader.nextInt();

head=new JD(a,b);

t=head;

}

else{

a=reader.nextInt();

b=reader.nextInt();

p=new JD(a,b);

p.next=null;

t.next=p;

t=p;

}

}

return head;

}

static void dxsxj(JD ha,JD hb){

JD p,q,r,pre;

int x;

p=ha.next;

q=hb.next;

pre=ha;

while(p!=null&&q!=null){

if(p.exp==q.exp){

x=p.coef+q.coef;

if(x!=0){

p.coef=x;

pre=p;

}else{

pre.next=p.next;

p=null;

}

p=pre.next;

r=q;

q=q.next;

r=null;

}else if(p.exp>q.exp){

r=q.next;

q.next=p;

pre.next=q;

pre=q;

q=r;

}else{

pre=p;

p=p.next;

}

}

if(q!=null)

pre.next=q;

hb=null;

}

static void disp(JD h){

JD p=h;

if(p==null){

System.out.println("空表!");

}

while(p!=null){

System.out.print(p.coef+"X");

System.out.print("("+p.exp+")");

p=p.next;

if(p!=null)

System.out.print(" + ");

}

System.out.println();

}

public static void main(String[] args) {

// TODO Auto-generated method stub

System.out.println("创建第一个多项式:  ");

JD h1=create();

disp(h1);

System.out.println("创建第二个多项式:  ");

JD h2=create();

disp(h2);

System.out.println("两个多项式相加的结果为:  ");

dxsxj(h1,h2);

disp(h1);

}

 

}