线性表java实现
2024-08-29 18:19:03
顺序表
public class SequenceList {
/*
* content,节点内容
* location,节点在表中的位置(序号)
* */
private String content;
private int location;
SequenceList(String content, int location){
this.content = content;
this.location = location;
}
SequenceList(){
this.content = "-1";
this.location = -1;
}
public String getContent() {
return content;
}
public void setContent(String content) {
this.content = content;
}
public int getLocation() {
return location;
}
public void setLocation(int location) {
this.location = location;
}
}
顺序表的各个操作
遍历
/*
* 遍历顺序表
* */
public static void showList(SequenceList[] list){
for(SequenceList one:list){
if(one!=null)
System.out.println("location = "+one.getLocation()+",content = "+one.getContent());
else
break;
}
}
插入
/*
* 插入节点
* */
public static void insertItem(SequenceList[] list, SequenceList item, int currentListLength, int insertLocation){
list[currentListLength] = new SequenceList();
if(currentListLength<insertLocation){
System.out.println("插入位置不在线性表内");
}else if(currentListLength==insertLocation+1){
System.out.println("线性表已满");
}else {
for(int i = currentListLength;i>insertLocation;i--){
list[i] = list[i-1];
list[i].setLocation(i);//重新设置节点位置
}
list[insertLocation] = item;
currentListLength++;
} }
获得特定位置的节点
/*
* 获得特定位置的节点
* */
public static SequenceList getSpecificItem(SequenceList[] list, int location){
for(SequenceList one:list){
if(one.getLocation()==location){
return one;
}
}
return null;
}
获得某个节点的位置
/*
* 获得某个节点的位置
* */
public static int getItemLocation(SequenceList[] list, String content){
for(SequenceList one:list){
if(one.getContent().equals(content)){
return one.getLocation();
}
}
return -1;
}
删除某个位置的节点
/*
* 删除节点
* */
public static void deleteItem(SequenceList[] list, int location){
for(int i = location;;i++){
if(list[i+1]==null){
list[i] = null;
break;
}
list[i] = list[i+1];
list[i].setLocation(i);//重新设置节点位置
}
}
测试
public static void main(String[] args) {
SequenceList[] lists = new SequenceList[20];
for(int i = 0;i < 6;i++){
lists[i] = new SequenceList();
lists[i].setContent(String.valueOf(i));
lists[i].setLocation(i);
}
insertItem(lists,new SequenceList("a",5),6,5);
showList(lists);
deleteItem(lists,5);
showList(lists);
System.out.println("5号位的内容是"+getSpecificItem(lists,5).getContent());
System.out.println("内容为2的位置是"+getItemLocation(lists,"2"));
}
结果
location = 0,content = 0
location = 1,content = 1
location = 2,content = 2
location = 3,content = 3
location = 4,content = 4
location = 5,content = a
location = 6,content = 5
location = 0,content = 0
location = 1,content = 1
location = 2,content = 2
location = 3,content = 3
location = 4,content = 4
location = 5,content = 5
5号位的内容是5
内容为2的位置是2
链表
节点类
public class SingleLinkList {
int data;//序号
SingleLinkList next;
SingleLinkList(){}
SingleLinkList(int data){
this.data = data;
}
}
插入节点
/*
* 插入节点到相应的位置
* */
public static void insertNode(SingleLinkList list,SingleLinkList item,int location){
SingleLinkList tempList = list;
while(tempList!=null){
if(tempList.data==location){
item.next = tempList.next;
item.data = tempList.data+1;
tempList.next = item;
break;
}else {
tempList = tempList.next;
}
}
item = item.next;
while (item!=null){
//重新编号排序
item.data++;
item = item.next;
}
}
删除节点
/*
* 删除相应节点
* */
public static void deleteNode(SingleLinkList list,int data){
SingleLinkList tempList = list;
while (tempList!=null){
//System.out.println(tempList.data);
if(tempList.data == data-1){
if(tempList.next.next!=null){
tempList.next = tempList.next.next;
tempList = tempList.next;
break;
}
else
tempList.next = null;
break;
}
tempList = tempList.next;
}
while (tempList!=null){
//重新编号排序
tempList.data--;
tempList = tempList.next;
}
}
获得特定位置的节点
/*
*获得特定位置的节点
* */
public static SingleLinkList getSpecificNode(SingleLinkList list,int location){
while (list!=null){
if(list.data==location){
return list;
}else {
list = list.next;
}
}
return null;
}
遍历
/*
* 遍历单链表
* */
public static void showList(SingleLinkList list){
while (list!=null){
System.out.println(list.data);
list = list.next;
}
}
反转单链表
/*
* 单链表反转
* */
public static SingleLinkList reserveList(SingleLinkList list){
SingleLinkList prevNode = null;//前一个节点
SingleLinkList currentNode = list;//当前节点
SingleLinkList reserveHead = null;//反转后的头节点
while (currentNode!=null){
SingleLinkList nextNode = currentNode.next;
if(nextNode==null){
reserveHead = currentNode;
}
currentNode.next = prevNode;
prevNode = currentNode;
currentNode = nextNode;
}
return reserveHead;
}
测试类
public static void main(String[] args) {
SingleLinkList head = new SingleLinkList(-1);
SingleLinkList list = head;
for (int i = 0;i < 5;i++){
list.next = new SingleLinkList(i);
list = list.next;
}
showList(head.next);
System.out.println("得到二号位置的节点");
System.out.println(getSpecificNode(head.next,2).data);
insertNode(head.next,new SingleLinkList(2),2);
System.out.println("在二号位置插入节点后");
showList(head.next);
deleteNode(head.next,2);
System.out.println("删除二号位置的节点");
showList(head.next);
System.out.println("反转链表后");
showList(reserveList(head.next));
}
结果
循环链表
循环链表是指收尾相接的链表
链表类
public class LoopList {
int data;
LoopList next;
public LoopList(int data) {
this.data = data;
}
public LoopList(){}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public LoopList getNext() {
return next;
}
public void setNext(LoopList next) {
this.next = next;
}
}
创建循环链表
/*
* 传入各结点的数据,返回头结点
* */
public static LoopList createLoopList(int[] data){
LoopList head = new LoopList(0);
LoopList temp = head;
for(int i=0;i<data.length;i++){
LoopList node = new LoopList(data[i]);
temp.setNext(node);
temp = temp.getNext();
}
temp.setNext(head.getNext());
return head.getNext();
}
其余操作都跟单链表类似,不详细写了
双向链表
双向链表类
import java.util.DuplicateFormatFlagsException;
public class DoubleLinkList {
int data;
DoubleLinkList prev;
DoubleLinkList next;
public DoubleLinkList(){}
public DoubleLinkList(int data){
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public DoubleLinkList getPrev() {
return prev;
}
public void setPrev(DoubleLinkList prev) {
this.prev = prev;
}
public DoubleLinkList getNext() {
return next;
}
public void setNext(DoubleLinkList next) {
this.next = next;
}
}
创建双向链表
/*
* 创建双向链表
* */
public static DoubleLinkList createList(int[] data)
{
DoubleLinkList head = new DoubleLinkList(-1);
DoubleLinkList alter = head;
for(int i = 0;i < data.length;i++){
DoubleLinkList node = new DoubleLinkList(data[i]);
alter.setNext(node);
node.setPrev(alter);
alter = alter.getNext();
}
return head.getNext();
}
向特定位置插入元素
/*
* 插入元素
* */
public static boolean insert(DoubleLinkList head,int location,DoubleLinkList node){
for(int i = 0;i < location-1;i++){
head = head.getNext();
}
DoubleLinkList locationNode = head.getNext();
head.setNext(node);
node.setPrev(head);
node.setNext(locationNode);
locationNode.setPrev(node);
return true;
}
删除特定位置的元素
/*
* 删除元素
* */
public static boolean delete(DoubleLinkList head,int location){
for(int i = 0;i < location-1;i++){
head = head.getNext();
}
DoubleLinkList locationNode = head.getNext().getNext();
head.setNext(locationNode);
locationNode.setPrev(head);
return true;
}
好了 线性表这一章节的基本实现完了,下一篇轮到栈和队列了
最新文章
- 错误：违反并发性: DeleteCommand 影响了预期 1 条记录中的 0 条
- Linux--装好之后要做的几件事（转）
- Linux 下的常用工具
- JAVA实例，求用户输入的整数是否是偶数
- 安装Cygwin
- jQuery的css()方法
- 循序渐进DB2(第2版)——DBA系统管理、运维与应用案例
- ios开发必备第三方库
- java设计模式--结构型模式--组合模式
- 算法分析-快速排序QUICK-SORT
- shell学习之变量、判断、重复动作
- Java的位运算符具体解释实例——与（&amp;）、非（~）、或（|）、异或（^）
- python编码问题之\"encode\"&\"decode\"
- Servlet之Listener监听器
- 基于Spring和Mybatis拦截器实现数据库操作读写分离
- 痞子衡嵌入式：语音处理工具Jays-PySPEECH诞生记（5）- 语音识别实现(SpeechRecognition, PocketSphinx0.1.15)
- 【安卓进阶】Scroller理解与应用
- 【js】深拷贝一文中的几个错误点
- 关于wifi网络基本原理了解
- [20171107]dbms_shared_pool.pin补充.txt