数据结构——线性表
什么是线性表？
线性表是具有相同类型的n个元素（n>=0）的有限序列。
1.顺序表
- 线性表采用顺序存储方式
- 其逻辑顺序和物理顺序相同
问题：需要连续存储空间，插入等操作需要移动大量元素，时间复杂度高。
2.单链表
线性表采用链式存储方式称为单链表。
链式存储是采用节点来进行存储的。
每个节点包括data域和next域。（不一定连续存储）
20190808125703566
- 单链表反转
- 单链表的增删改查
- 约瑟夫环
单链表反转
20190808115959474
20190808115959474
20190808115940644
单链表的增删改查
import java.util.Stack;
//定义单个节点
class Node
{
public String data; //定义数据节点
public Node next; //定义指向下一个节点的指针
public Node() {
}
public Node(String data) {
this.data = data;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public String toString() {
return "Note{" +
"data='" + data + '\'' +
'}';
}
}
public class Operation
{
//初始化头结点
private static Node head = new Node();
private static Node reverseHead = new Node();
//插入节点（头插）
public void insertToHead(Node node)
{
Node temp = head;
//头插法需要设置head.next和node.next的值。其中nodeNext指向headNext，而headNext指向node。
//由于是赋值的关系，二者顺序不可颠倒
node.next=temp.next;
temp.next=node;
}
//插入节点（尾插）
public void insertToLast(Node node)
{
Node temp = head;
while (true)
{
if(temp.next==null)
{break;}
temp=temp.next;
}
temp.next=node;
}
//插入节点（指定位置k之后）
public void insertToK(Node node,int k)
{
Node temp = head;
for(int i=0;i<k;i++)
{
temp=temp.next;
}
node.next=temp.next;
temp.next=node;
}
//删除第m个节点
public void deleteM(int m)
{
Node temp = head;
for(int i=0;i<m-1;i++)
{
temp=temp.next;
}
temp.next=temp.next.next;
}
//修改第n个节点（n）
public void updateN(int n)
{
Node temp = head;
for(int i=0;i<n;i++)
{
temp=temp.next;
}
temp.data="up";
}
//递归反转
public Node reverseLinkedList(Node node) {
if (node == null || node.next == null) {
return node;
} else {
Node headNode = reverseLinkedList(node.next);
node.next.next = node;
node.next = null;
return headNode;
}
}
//遍历反转
public Node reserveByFor(Node head)
{
Node cur = head.next;
Node next = null;
Node Rhead = new Node();
while(true)
{
if(cur==null)
{
break;
}
else
{
next=cur.next;
cur.next=Rhead.next;
Rhead.next=cur;
cur=next;
}
}
head.next=Rhead.next;
return head;
}
//print(last to first)
public void printLtoF(Node head)
{
Stack<Node>stack = new Stack<>();
Node cur = head.next;
while (cur!=null)
{
stack.push(cur);
cur=cur.next;
}
while (stack.size()>0)
{
System.out.println(stack.pop());
}
}
public static void main(String[] args)
{
Operation operation = new Operation();
operation.insertToHead(new Node("A"));
operation.insertToHead(new Node("B"));
operation.insertToHead(new Node("C"));
operation.insertToLast(new Node("1"));
operation.insertToLast(new Node("2"));
operation.insertToLast(new Node("3"));
// operation.insertToK(new Node("k"),2);
// operation.deleteM(3);
// operation.updateN(1);
Node temp =head;
//遍历链表
while(true)
{
if(temp.next==null)
{break;}
else
{
temp=temp.next;
System.out.println(temp.toString());
}
}
System.out.println("//1.求单链表中有效节点个数.");
temp=head;
int count=0;
while(true)
{
if(temp.next==null)
{break;}
else
{
temp=temp.next;
count++;
}
}
System.out.println(count);
System.out.println("//2.查找单链表中倒数第K=3个节点");
temp=head;
//获取链表总长
int length=0;
while (true)
{
if(temp.next==null)
{break;}
else
{
temp=temp.next;
length++;
}
}
temp=head;
for(int i=0;i<length-2;i++)
{
temp=temp.next;
}
System.out.println(temp.data);
System.out.println("3.实现单链表的反转");
// temp=operation.reverseLinkedList(head);
temp = operation.reserveByFor(head);
//遍历链表
while(true)
{
if(temp.next==null)
{break;}
else
{
temp=temp.next;
System.out.println(temp.toString());
}
}
System.out.println("4.从尾到头打印单链表");
temp = head;
operation.printLtoF(temp);
}
}
2019080812432676
单向环形链表输出约瑟夫环
2019080816052262
//定义单个节点
class Node
{
public String data; //定义数据节点
public Node next; //定义指向下一个节点的指针
public Node() {
}
public Node(String data) {
this.data = data;
}
@Override
public String toString() {
return "Note{" +
"data='" + data + '\'' +
'}';
}
}
public class Operation
{
//初始化头结点
private static Node head = new Node();
//尾插法
public void add(Node node)
{
Node temp = head;
while (true)
{
if(temp.next==null)
{break;}
temp=temp.next;
}
temp.next=node;
}
//创建单向环形链表
public Node createCircle(int n)
{
//创建单链表
for(int i=0;i<n;i++)
{
add(new Node("No:"+(i+1)));
}
//遍历链表
Node temp = head;
while(temp.next!=null)
{
temp=temp.next;
System.out.println(temp);
}
Node last = temp;
temp=head;
last.next=head.next; //连接首尾
System.out.println("last为最后一个数5：");
System.out.println(last);
System.out.println("循环两遍单向环形链表：");
int count=2*n;
while(last!=null)
{
if(count==0)
{
break;
}
System.out.println(last.next);
last=last.next;
count--;
}
System.out.println("last="+last.data);
return last;
}
public static void JosephusProblem(int n, int k, int m, Node last)
{
//定位到第k个节点,输出k+1个节点并删除，并让last定位到第k个节点
Node temp = last;
for(int i=0;i<k;i++) //定位到第k个节点
{
temp=temp.next;
}
System.out.println("第一次输出"+temp.next.data);//输出
temp.next=temp.next.next; //删除第K+1个节点
last=temp.next;
for(int i=0;i<n-1;i++)
{
temp=last;
System.out.println("第二次输出"+temp.next.data);
temp.next=temp.next.next;
last=temp.next;
}
}
public static void main(String[] args)
{
Operation operation = new Operation();
//定义人数
int n=5;
Node last = operation.createCircle(n);
//定义从第几个节点开始数
int k=1;
//定义数的次数
int m=2;
System.out.println("输出约瑟夫环：");
JosephusProblem(n,k,m,last);
}
}
20190808160504403
3.双向链表
双向链表与单向链表的区别
单向列表只能从前往后查找，而双向链表可以向前向后查找。 单向链表删除节点需要依靠辅助节点，而双向链表可以实现自我删除。
双向链表与单项列表的实际区别在于多了一个pre域。
20190808125632756
双向链表增删改查
import java.util.Stack;
//定义单个节点
class Node
{
public String data; //定义数据节点
public Node next; //定义指向下一个节点的指针
public Node pre; //定义指向上一个节点的指针
public Node() {
}
public Node(String data) {
this.data = data;
}
@Override
public String toString() {
return "Note{" +
"data='" + data + '\'' +
'}';
}
}
public class Operation
{
//初始化头结点
private static Node head = new Node();
//插入节点（尾插法）
public void addNode(Node node)
{
Node temp = head;
while(true)
{
if(temp.next==null)
{
break;
}
temp=temp.next;
}
temp.next=node;
node.pre=temp;
}
//插入节点(头插法)
public void addNodeToHead(Node node)
{
Node temp = head;
node.pre=temp;
node.next=temp.next;
temp.next.pre=node;
temp.next=node;
}
//插入到第k个节点后
public void addToK(Node node,int k)
{
Node temp = head;
for(int i=0;i<k;i++)
{
temp=temp.next;
}
//先建立单链表联系
node.next=temp.next;
temp.next=node;
//建立pre指向
node.pre=temp;
node.next.pre=node;
}
//删除第n个结点
public void deleteNode(int n)
{
Node temp = head;
for(int i=0;i<n;i++)
{
temp=temp.next;
}
temp.next.pre=temp.pre;
temp.pre.next=temp.next;
}
public void list()
{
//遍历链表
Node temp = head;
while(temp.next!=null)
{
temp=temp.next;
System.out.println(temp.toString());
}
System.out.println("=============");
}
//修改第m个结点
public void update(int m)
{
Node temp = head;
for(int i=0;i<m;i++)
{
temp=temp.next;
}
temp.data="up";
}
public static void main(String[] args)
{
Operation operation = new Operation();
operation.addNode(new Node("A"));
operation.addNode(new Node("B"));
operation.addNode(new Node("C"));
operation.addNode(new Node("D"));
operation.addNodeToHead(new Node("head1"));
operation.addNodeToHead(new Node("head2"));
operation.addNodeToHead(new Node("head3"));
//遍历链表
operation.list();
System.out.println("删除第n个节点");
operation.deleteNode(3);
//遍历链表
operation.list();
System.out.println("修改第m个节点");
operation.update(3);
operation.list();
System.out.println("插入到第k个节点后");
operation.addToK(new Node("k" ),3);
operation.list();
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019-08-10 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
腾讯云开发者
