三郎数据结构学习笔记:双向循环链表(判断是否对称)附源码
发布日期:2021-06-29 20:03:54
浏览次数:3
分类:技术文章
本文共 2591 字,大约阅读时间需要 8 分钟。
双向循环链表
题目
建立一个带头结点的双向循环链表, 赋值,判断是否对称,写出算法计算时间复杂度
思想
travel the Link ;遍历链表
put values into a array ;赋值给一个数组 compare the array to know whether it belong to symmetry 比较数组是否对称 采用问题转化的思想 将链表问题转换成数组问题,大大降低了思考难度 时间复杂度O(n^2) 因为有两个for循环实验结果
比较次数本来可以更少点,但是我就不改了,分个数奇数偶数
链表数值:1 2 3 2 1 链表数值:1 2 3 2 3完整源代码
/* * Author:sanlang * time:2020.11.5 * function:建立一个带头结点的双向循环链表,赋值,判断是否对称,写出算法计算时间复杂度 * my view:travel the Link ;put values into a array ;compare the array to know whether symmetry * */public class DoubleLinkSys { public static void main(String[] args) { DoubleLinkdoubleLink = new DoubleLink<>(); doubleLink.initlist(); doubleLink.add(1); doubleLink.add(2); doubleLink.add(3); doubleLink.add(2); doubleLink.add(1); doubleLink.print(); int array[]=new int[5]; //5是长度,不是最大下标 ,下标范围0-4 for( int i=0; i<5 ;i++){ array[i]=doubleLink.get(i); System.out.println(array[i]); } System.out.println("判断是否对称开始:"); for(int m=0;m<4;m++){ if (array[m]==array[4-m]){ System.out.println("匹配"); } else System.out.println("不匹配"); } }}class Node { public Anytype data;//数据 public Node prev;//前一个节点 public Node next;//后一个节点 public Node(Anytype data,Node prev,Node next){ this.data=data; this.prev=prev; this.next=next; }}class DoubleLink { Node head;//头指针 Node end;//尾节点 int size;//记录链表长度 //初始化链表 public void initlist(){ end=new Node<>(null,null,null); head=new Node<>(null,null,end); end.prev=head; end.next=head; size=0; } //获取长度 public int length(){ return size; } //获取节点 public Node getNode(int index){ Node n; if(index>=size/2){ n=end; for(int i=length();i>index;i--){ n=n.prev; } return n; } else{ n=head; for(int i=0;i<=index;i++){ n=n.next; } return n; } } //添加元素 public void add(AnyType a){ Node renode=new Node<>(a,getNode(size-1),end); renode.prev.next=renode; renode.next.prev=renode; size++; } //插入元素 public void insert(int i,AnyType a){ Node n=getNode(i); Node renode=new Node<>(a,n.prev,n); n.prev.next=renode; n.prev=renode; size++; } //删除元素 public AnyType remove(int i){ Node n=getNode(i); AnyType data=n.data; n.prev.next=n.next; n.next.prev=n.prev; size--; return data; } //获取i位置的数据 public AnyType get(int i){ return getNode(i).data; } //为i位置元素重新赋值 public AnyType set(int i,AnyType a){ Node n=getNode(i); AnyType old=n.data; n.data=a; return old; } //清空链表 public void clear(){ initlist(); } public void print(){ for(int i=0;i
转载地址:https://blog.csdn.net/m0_51684972/article/details/109519419 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月29日 20时33分11秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
文章标题
2021-07-03
算法-动态规划
2021-07-03
算法-3个水桶8升水
2021-07-03
算法-稳定匹配
2019-04-30
管道堵住问题的定位
2019-04-30
ssh问题
2019-04-30
struct union and endian
2019-04-30
a bug related with extern
2019-04-30
cbwfq移植的思考
2019-04-30
TCE1保序功能的开发
2019-04-30
TCE1保序功能开发-----续
2019-04-30
低温故障处理
2019-04-30
联想G455 XP/MAC 双系统安装
2019-04-30
学习cocoa编程-.Cocoa.Programming
2019-04-30
第3章 Object c
2019-04-30
第4章 memory management
2019-04-30
第5章 target/action
2019-04-30
第6章 helper object
2019-04-30
第7章 Key-Value Coding; Key-Value Observing
2019-04-30
第8章 NSArrayController
2019-04-30