数据结构链表实现代码(java语言版)
- 格式：docx
- 大小：28.25 KB
- 文档页数：14
package link;
//链表的基本类（每一个节点）
publicclass Link {
//有两个属性
//数据域
privateintdata=-1; //-1表达是没有数据
//指针域
private Link next=null; //空指针
publicintgetData() {
returndata;
}
publicvoidsetData(int data) {
this.data = data;
}
public Link getNext() {
returnnext;
}
publicvoidsetNext(Link next) {
this.next = next;
}
}
package link;
importjava.util.Scanner;
//算法类对于链表的所有的操作
publicclass Algorithm {
//链表的初始化：创建一个空的头节点
publicvoidlink_ininal(Link H){
H=newLink();
}
//创建新节点封装节点
public Link link_new(int x){
Link p=new Link();
p.setData(x);
return p;
}
//表头插入法创建链表
publicvoidlink_topfound(Link H){
Scanner sc=newScanner(System.in);
int x;
Link p;
System.out.println("请输入数据，输入0结束：");
x=sc.nextInt();
while(x != 0){
//对x封装
p=link_new(x);
//1。先让p连接H的下一个节点
p.setNext(H.getNext());
//2。H连接p
H.setNext(p);
System.out.println("请输入数据，输入0结束：");
x=sc.nextInt();
} }
//输出链表
publicvoidlink_output(Link H){
Link p;
//p的初次站位
p=H.getNext();
while(p != null){
//p节点的data值输出来
System.out.print(p.getData()+" ");
//p向后走
p=p.getNext();
}
System.out.println();
}
public Link link_findend(Link H){
Link q;
q=H;
while(q.getNext() != null){
q=q.getNext();
}
return q;
}
//表尾法创建链表
publicvoidlink_endfound(Link H){
Scanner sc=newScanner(System.in);
//需要一个总是站到表尾的哨兵q
int x;
//哨兵q应该站在当前链表的最后一个节点上
Link q=link_findend(H); Link p;
System.out.println("请输入数据，输入0结束：");
x=sc.nextInt();
while(x != 0){
//封装
p=link_new(x);
//q链接p
q.setNext(p);
//q先后移动
q=q.getNext();
System.out.println("请输入数据，输入0结束：");
x=sc.nextInt();
}
}
//链表的定位操作,返回找到的节点
public Link link_find(Link H,int x){
Link p;
//p初始站位
p=H.getNext();
while(p != null){
if(p.getData() == x){
break;
}
//p后走
p=p.getNext();
}
//找到 p节点没有找到就是null
return p; }
//链表的删除
publicbooleanlink_del(Link H,int x){
Link p,q;
boolean f=false; //删除失败
//站位
p=H.getNext();
q=H;
while(p != null){
if(p.getData() == x){
break;
}
//2人都向后走
p=p.getNext();
q=q.getNext();
}
//删除：如果删除成功，f=true
if(p != null){ //找到了，实现删除
q.setNext(p.getNext());
f=true;
}
return f;
}
//定位插入
publicvoidlink_in(Link H,Linkp,int x){
//给x封装
Link s=link_new(x);
//把s插入到p的后边
//1 s连接p的下一个节点 s.setNext(p.getNext());
//2 p连接s
p.setNext(s);
}
//链表的变异的冒泡排序
publicvoidlink_order(Link H){
Link p,q;
int t;
//外层表示趟数
for(q=H.getNext(); q.getNext()!= null;
q=q.getNext()){
for(p=H.getNext();p.getNext() !=
null;p=p.getNext()){
//开始比较p的数据和p的下一个节点的数据
if(p.getData() >p.getNext().getData()){
t=p.getData();
p.setData(p.getNext().getData());
p.getNext().setData(t);
}
}
}
}
//有序插入(重写)
publicvoidlink_in(Link H,int x){
Link q,p,s;
p=H.getNext();
q=H;
while( p!=null&&p.getData() < x ){ p=p.getNext();
q=q.getNext();
}
//x节点插入到q和p之间
s=link_new(x);
//1 s连上p
s.setNext(p);
//2 q连上s
q.setNext(s);
}
//链表的逆序
public Link link_revert(Link H){
//生成一个新的链表的头结点
Link H2=newLink();
Link s;
//循环的条件就是H链表后面还有节点吗
while(H.getNext() != null){
//循环完成以下操作
//1 从H上截取一个节点
s=H.getNext();
H.setNext(s.getNext());
//2 以表头插入法的方法把截取的节点插入到H2链表
//s指向H2的下一个节点
s.setNext(H2.getNext());
//H2指向s
H2.setNext(s);
}
return H2;
}
}
package link;
publicclass Menu {
void display()
{
System.out.printf("|--------------------------------------------------------------------------|\n");
System.out.printf("|------------------------------链表操作-------------------------------------|\n");
System.out.printf("|--------------------------------------------------------------------------|\n");
System.out.printf(" |----------- 1.创建链表
-----------|\n");
System.out.printf(" |----------- 2.输出链表内容
-----------|\n");
System.out.printf(" |----------- 3.链表的定位
------------|\n");
System.out.printf(" |----------- 4.链表中删除指定值的结点 ------------|\n");
System.out.printf(" |----------- 5.链表的定位插入
------------|\n");
