首页 > 代码库 > (java描述)关于链表的代码-----单双、循环链表、约瑟夫环、多项式相加
(java描述)关于链表的代码-----单双、循环链表、约瑟夫环、多项式相加
- 将链表头尾倒置
- 将几个链表合并成一个新的链表，将链表中重复的节点去掉，并按大小排序
- 双向循环链表
- 单向循环链表（约瑟夫循环）
- 多项式相加
程序源代码
单链表、单向循环链表结点类
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);
}
}